gpa_cube_max_le_one_false
theoremverifiederratum
The 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 vertices the maximum is 2.
Statement
open Finset in theorem gpa_cube_max_le_one_false : ¬ (∀ (k : ℕ) (e : Fin k → Fin k → ℝ), (∀ i j, e i j = 0 ∨ e i j = 1) → ∀ x : Fin k → ℝ, x ∈ gpa_cube k → gpa_uStar e x ≤ 1)
- Corrects
- Generalized Principal-Agency: Contracts, Information, Games and Beyond, WINE 2024 (arXiv:2209.01146v2), Section 5.3 / Appendix 13.2: the auxiliary claim max over [0,1]^k of u* <= 1 used to derive Eq. (5.4) is false (value 2 on the 3-vertex path)
- Verified
- 27 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 7
- 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_adjMat_zero_oneThe adjacency matrix is a 0/1 matrix, as required in Section 5.3 of arXiv:2209.01146.
- gpa_rhs_attainThe value α(G) is attained on the cube, at the indicator vector of a maximum independent set.
- gpa_path3The path 0 - 2 - 1 on three vertices.
- gpa_path3_indepIn the path 0 - 2 - 1, {0, 1} is a maximum independent set.
Read back from the Lean
It is not the case that for every natural number $k$, every matrix $e : \mathrm{Fin}\ k \to \mathrm{Fin}\ k \to \mathbb{R}$ whose entries are all in $\{0, 1\}$, and every vector $x : \mathrm{Fin}\ k \to \mathbb{R}$ in gpa_cube k, gpa_uStar e x ≤ 1.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
open Finset in/-- The 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 vertices the maximum is `2`. -/theorem gpa_cube_max_le_one_false : ¬ (∀ (k : ℕ) (e : Fin k → Fin k → ℝ), (∀ i j, e i j = 0 ∨ e i j = 1) → ∀ x : Fin k → ℝ, x ∈ gpa_cube k → gpa_uStar e x ≤ 1) := by intro h obtain ⟨hI, _⟩ := gpa_path3_indep obtain ⟨hmem, hval⟩ := gpa_rhs_attain gpa_path3 {0, 1} hI have := h 3 (gpa_adjMat gpa_path3) (gpa_adjMat_zero_one gpa_path3) _ hmem rw [hval] at this have hc : ({0, 1} : Finset (Fin 3)).card = 2 := by decide rw [hc] at this norm_num at this