AFTD Auto-Formalizing Theoretical Domains

gpa_rhs_attain

lemmaverified

The value α(G) is attained on the cube, at the indicator vector of a maximum independent set.

Statement

open Finset in
lemma gpa_rhs_attain {k : ℕ} (G : SimpleGraph (Fin k)) [DecidableRel G.Adj]
    (I : Finset (Fin k)) (hI : gpa_indep G I) :
    (fun i => if i ∈ I then (1 : ℝ) else 0) ∈ gpa_cube k ∧
      gpa_uStar (gpa_adjMat G) (fun i => if i ∈ I then (1 : ℝ) else 0) = I.card
Source
step towards gpa_eq54_false / gpa_eq54_fails_of_indep (Generalized Principal-Agency: Contracts, Information, Games and Beyond, WINE 2024 (arXiv:2209.01146v2), Sec. 5.3, Eq. (5.4))
Verified
06 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5
  • gpa_adjMatThe 0/1 matrix e of arXiv:2209.01146, Section 5.3 (taken from the maximum-independent-set instances of the cited convex-maximisation…
  • gpa_uStarThe principal's utility of arXiv:2209.01146, Section 5.3: u*(σ) = Σ_i max{σ_i - Σ_j e_{ij} σ_j, 0} for a 0/1 matrix e.
  • gpa_cubeThe unit cube [0,1]^k.
  • gpa_indepAn independent set of the graph G.
  • gpa_nbr_nonnegNeighbour sums are nonnegative for nonnegative vectors.
Used by 2
  • gpa_rhs_isGreatestExact value of the right side of Eq. (5.4) of arXiv:2209.01146 (before the factor 1/k): max_{x ∈ [0,1]^k} u*(x) = α(G).
  • gpa_cube_max_le_one_falseThe auxiliary claim max_{x ∈ [0,1]^k} u*(x) ≤ 1 used in the proof of Eq. (5.4) of arXiv:2209.01146 is false: on the path with three…

Lean source view module on GitHub

open Finset in/-- The value `α(G)` is attained on the cube, at the indicator vector of a maximum independent set. -/lemma gpa_rhs_attain {k : ℕ} (G : SimpleGraph (Fin k)) [DecidableRel G.Adj]    (I : Finset (Fin k)) (hI : gpa_indep G I) :    (fun i => if i ∈ I then (1 : ℝ) else 0) ∈ gpa_cube k ∧      gpa_uStar (gpa_adjMat G) (fun i => if i ∈ I then (1 : ℝ) else 0) = I.card := by  classical  refine ⟨fun i => by dsimp only; constructor <;> split_ifs <;> norm_num, ?_⟩  unfold gpa_uStar  have hterm : ∀ i, max ((if i ∈ I then (1 : ℝ) else 0) -      ∑ j, gpa_adjMat G i j * (if j ∈ I then (1 : ℝ) else 0)) 0 =      if i ∈ I then 1 else 0 := by    intro i    by_cases hi : i ∈ I    · have hz : ∑ j, gpa_adjMat G i j * (if j ∈ I then (1 : ℝ) else 0) = 0 := by        apply Finset.sum_eq_zero        intro j _        by_cases hj : j ∈ I        · have : ¬ G.Adj i j := hI i hi j hj          simp [gpa_adjMat, this]        · simp [hj]      rw [hz]; simp [hi]    · have hnn := gpa_nbr_nonneg G (fun j => if j ∈ I then (1 : ℝ) else 0)        (fun j => by split_ifs <;> norm_num) i      simp only [hi, if_false]      exact max_eq_right (by linarith)  simp_rw [hterm]  simp
See it in the graphDiscuss this resultChallenge it