AFTD Auto-Formalizing Theoretical Domains

gpa_rhs_upper

lemmaverified

Upper bound on the cube: u*(x) ≤ α(G) for every x ∈ [0,1]^k.

Statement

open Finset in
lemma gpa_rhs_upper {k : ℕ} (G : SimpleGraph (Fin k)) [DecidableRel G.Adj]
    (a : ℕ) (hα : ∀ S, gpa_indep G S → S.card ≤ a)
    (x : Fin k → ℝ) (hx : x ∈ gpa_cube k) :
    gpa_uStar (gpa_adjMat G) x ≤ a
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_uStar_le_indepKey structural lemma: for a nonnegative vector, the coordinates with a positive term of u* form an independent set P, and u*(σ) ≤ Σ_{i ∈…
Used by 1
  • 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).

Lean source view module on GitHub

open Finset in/-- Upper bound on the cube: `u*(x) ≤ α(G)` for every `x ∈ [0,1]^k`. -/lemma gpa_rhs_upper {k : ℕ} (G : SimpleGraph (Fin k)) [DecidableRel G.Adj]    (a : ℕ) (hα : ∀ S, gpa_indep G S → S.card ≤ a)    (x : Fin k → ℝ) (hx : x ∈ gpa_cube k) :    gpa_uStar (gpa_adjMat G) x ≤ a := by  obtain ⟨P, hP, hle⟩ := gpa_uStar_le_indep G x (fun i => (hx i).1)  have h1 : ∑ i ∈ P, x i ≤ ∑ _i ∈ P, (1 : ℝ) := Finset.sum_le_sum (fun i _ => (hx i).2)  have h2 : (P.card : ℝ) ≤ a := by exact_mod_cast hα P hP  simp at h1  linarith
See it in the graphDiscuss this resultChallenge it