AFTD Auto-Formalizing Theoretical Domains

gpa_nbr_ge

lemmaverified

A single neighbour's coordinate is bounded by the neighbour sum.

Statement

open Finset in
lemma gpa_nbr_ge {k : ℕ} (G : SimpleGraph (Fin k)) [DecidableRel G.Adj]
    (σ : Fin k → ℝ) (hσ : ∀ i, 0 ≤ σ i) (i j : Fin k) (hij : G.Adj i j) :
    σ j ≤ ∑ l, gpa_adjMat G i l * σ l
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 1
  • 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…
Used by 1
  • 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 ∈…

Lean source view module on GitHub

open Finset in/-- A single neighbour's coordinate is bounded by the neighbour sum. -/lemma gpa_nbr_ge {k : ℕ} (G : SimpleGraph (Fin k)) [DecidableRel G.Adj]    (σ : Fin k → ℝ) (hσ : ∀ i, 0 ≤ σ i) (i j : Fin k) (hij : G.Adj i j) :    σ j ≤ ∑ l, gpa_adjMat G i l * σ l := by  have h1 : gpa_adjMat G i j * σ j = σ j := by simp [gpa_adjMat, hij]  rw [← h1]  apply Finset.single_le_sum (f := fun l => gpa_adjMat G i l * σ l)  · intro l _    unfold gpa_adjMat    split_ifs <;> nlinarith [hσ l]  · exact Finset.mem_univ j
See it in the graphDiscuss this resultChallenge it