AFTD Auto-Formalizing Theoretical Domains

gpa_eq54_fails_of_indep

theoremverifiederratum

Eq. (5.4) of arXiv:2209.01146 (max_{Δ_k} (u* - h) = (1/k) max_{[0,1]^k} u*) fails on every graph whose independence number α satisfies 2 ≤ α < k: the two sides are 1 - 1/α + 1/k and α/k, and the first is strictly larger.

Statement

open Finset in
theorem gpa_eq54_fails_of_indep {k : ℕ} (G : SimpleGraph (Fin k)) [DecidableRel G.Adj]
    (I : Finset (Fin k)) (hI : gpa_indep G I) (hmax : ∀ S, gpa_indep G S → S.card ≤ I.card)
    (h2 : 2 ≤ I.card) (hk : I.card < k) (L R : ℝ)
    (hL : IsGreatest (gpa_lhsSet (gpa_adjMat G)) L)
    (hR : IsGreatest (gpa_rhsSet (gpa_adjMat G)) R) :
    R / (k : ℝ) < L
Corrects
Generalized Principal-Agency: Contracts, Information, Games and Beyond, WINE 2024 (arXiv:2209.01146v2), Section 5.3, Eq. (5.4) in the proof of Theorem 5: fails for every graph with independence number 2 <= alpha < k (sides 1 - 1/alpha + 1/k and alpha/k)
Verified
27 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 6
  • 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_lhsSetThe set of values u*(σ) - h(σ) over the simplex (left side of Eq. (5.4)).
  • gpa_rhsSetThe set of values u*(x) over the cube (right side of Eq. (5.4), before dividing by k).
  • gpa_indepAn independent set of the graph G.
  • gpa_lhs_isGreatestExact value of the left side of Eq. (5.4) of arXiv:2209.01146 on the independent-set instances: max_{σ ∈ Δ_k} u*(σ) - h(σ) = 1 - 1/α(G) +…
  • 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).
Used by 1
  • gpa_eq54_falseEq. (5.4) in the proof of Theorem 5 (hardness of costly information acquisition) of arXiv:2209.01146 is false: it is not true that for…

Read back from the Lean

For any natural number $k$, any simple graph $G$ on vertices $\mathrm{Fin}\; k$ with decidable adjacency, and any subset of vertices $I \subseteq \mathrm{Fin}\; k$, assume: 1. $I$ is an independent set in $G$ (gpa_indep G I). 2. $I$ has maximum cardinality among all independent sets in $G$ (for all $S \subseteq \mathrm{Fin}\; k$, if $S$ is independent in $G$, then $|S| \le |I|$). 3. $|I| \ge 2$. 4. $|I| < k$. 5. $L \in \mathbb{R}$ is the greatest element of the set $\mathrm{gpa\_lhsSet}(\mathrm{gpa\_adjMat}(G))$. 6. $R \in \mathbb{R}$ is the greatest element of the set $\mathrm{gpa\_rhsSet}(\mathrm{gpa\_adjMat}(G))$. Then $R / k < L$.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

open Finset in/-- Eq. (5.4) of arXiv:2209.01146 (`max_{Δ_k} (u* - h) = (1/k) max_{[0,1]^k} u*`) fails on every graph whose independence number `α` satisfies `2 ≤ α < k`: the two sides are `1 - 1/α + 1/k` and `α/k`, and the first is strictly larger. -/theorem gpa_eq54_fails_of_indep {k : ℕ} (G : SimpleGraph (Fin k)) [DecidableRel G.Adj]    (I : Finset (Fin k)) (hI : gpa_indep G I) (hmax : ∀ S, gpa_indep G S → S.card ≤ I.card)    (h2 : 2 ≤ I.card) (hk : I.card < k) (L R : ℝ)    (hL : IsGreatest (gpa_lhsSet (gpa_adjMat G)) L)    (hR : IsGreatest (gpa_rhsSet (gpa_adjMat G)) R) :    R / (k : ℝ) < L := by  have hL' := gpa_lhs_isGreatest G I hI hmax (by omega) hk.le  have hR' := gpa_rhs_isGreatest G I hI hmax  rw [hL.unique hL', hR.unique hR']  have haR : (2 : ℝ) ≤ I.card := by exact_mod_cast h2  have hkR : (I.card : ℝ) + 1 ≤ k := by exact_mod_cast hk  have hapos : (0 : ℝ) < I.card := by linarith  have hkpos : (0 : ℝ) < k := by linarith  rw [div_lt_iff₀ hkpos]  have e : (1 - 1 / (I.card : ℝ) + 1 / (k : ℝ)) * k      = k - k / (I.card : ℝ) + 1 := by field_simp  rw [e]  -- need: a < k - k/a + 1, i.e. (a-1)(k-a) > 0 after multiplying by a  rw [← sub_pos]  have : (k : ℝ) - k / (I.card : ℝ) + 1 - I.card      = ((I.card : ℝ) - 1) * ((k : ℝ) - I.card) / I.card := by field_simp; ring  rw [this]  apply div_pos _ hapos  apply mul_pos <;> linarith
See it in the graphDiscuss this resultChallenge it