team_thm4_part2_false
theoremverifiederratum
Theorem 4 (2) of arXiv:2605.21234 is false, whatever function is used for its o(1) term: for every m, on the (2m+3)-player instance the identity line-up is a maximum-weight matching with all edge probabilities 1/2 (so w(M*) = n/2 and the error term vanishes) and wins with probability 1/2, while the optimal line-up wins with probability at least 9/16.
Statement
open Finset in theorem team_thm4_part2_false (ε : ℕ → ℝ) (N : ℕ) : ¬ team_thm4_part2 ε N
- Corrects
- The Team Order Problem: Maximizing the Probability of Matching Being Large Enough, SAGT 2024 (arXiv:2605.21234), Section 6, Theorem 4(2) (near weight n/2 an optimal line-up beats a maximum-weight matching M* by at most (4 + o(1))/(n+1) * sum over M* of (p_e - 1/2)^2): false for every choice of the o(1) term; (2m+3)-player instance with an all-1/2 maximum-weight matching and a gap of 1/16
- Verified
- 27 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 10
- team_weightA line-up of team 1 against the fixed line-up of team 2 is a perfect matching, i.e. a permutation π of the n positions (player i of team 1…
- team_winProbWinning probability of a line-up in the Team Order problem of arXiv:2605.21234: team 1 wins if it wins at least ⌊n/2⌋ + 1 of the n…
- team_isOptimalπ is an optimal line-up (maximises the winning probability).
- team_thm4_part2Theorem 4 (2) of arXiv:2605.21234, with the o(1) term made explicit as a function ε: for all large n, every instance, every maximum-weight…
- team_PThe instance: p(i,i) = 1/2, p(i, i+1 mod n) = team_w i, all other entries 0.
- team_P_boundsAll entries of the first Team Order instance are probabilities in [0,1].
- team_weight_idThe identity line-up has weight n/2.
- team_id_maxWeightThe identity line-up (all edges 1/2) is a maximum-weight matching.
- team_id_winProbThe identity line-up wins with probability exactly 1/2.
- team_rot_winProbThe rotation line-up wins with probability 9/16.
Read back from the Lean
For every function ε : ℕ → ℝ and every natural number N : ℕ, the statement team_thm4_part2 ε N is false (its negation holds).
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/-- Theorem 4 (2) of arXiv:2605.21234 is false, whatever function is used for its `o(1)` term: for every `m`, on the `(2m+3)`-player instance the identity line-up is a maximum-weight matching with all edge probabilities `1/2` (so `w(M*) = n/2` and the error term vanishes) and wins with probability `1/2`, while the optimal line-up wins with probability at least `9/16`. -/theorem team_thm4_part2_false (ε : ℕ → ℝ) (N : ℕ) : ¬ team_thm4_part2 ε N := by intro h obtain ⟨O, -, hO⟩ := Finset.exists_max_image (univ : Finset (Equiv.Perm (Fin (2 * N + 3)))) (team_winProb (team_P N)) ⟨1, Finset.mem_univ _⟩ have hOpt : team_isOptimal (team_P N) O := fun σ => hO σ (Finset.mem_univ _) have hn : (((2 * N + 3 : ℕ) : ℝ)) / 2 = team_weight (team_P N) 1 := (team_weight_id N).symm have hsl : 0 ≤ Real.sqrt ((2 * N + 3 : ℕ) : ℝ) * Real.log ((2 * N + 3 : ℕ) : ℝ) := mul_nonneg (Real.sqrt_nonneg _) (Real.log_nonneg (by norm_cast; omega)) have key := h (2 * N + 3) (by omega) (team_P N) (team_P_bounds N) 1 O (team_id_maxWeight N) hOpt (by linarith) (by linarith) have hsq : ∑ i : Fin (2 * N + 3), (team_P N i ((1 : Equiv.Perm (Fin (2 * N + 3))) i) - 1 / 2) ^ 2 = 0 := by apply Finset.sum_eq_zero intro i _ simp [team_P] rw [hsq, mul_zero, add_zero, team_id_winProb] at key have hrot := hOpt (finRotate (2 * N + 3)) rw [team_rot_winProb] at hrot linarith