team_gap
theoremverifiedoriginal
Quantitative form: on the instance of size 2m+3, the optimal line-up beats the all-1/2 maximum-weight matching by at least 1/16, while the error term of Theorem 4 (2) of arXiv:2605.21234 is 0.
Statement
open Finset in theorem team_gap (m : ℕ) (O : Equiv.Perm (Fin (2 * m + 3))) (hO : team_isOptimal (team_P m) O) : team_isMaxWeight (team_P m) 1 ∧ team_weight (team_P m) 1 = ((2 * m + 3 : ℕ) : ℝ) / 2 ∧ ∑ i : Fin (2 * m + 3), (team_P m i ((1 : Equiv.Perm (Fin (2 * m + 3))) i) - 1 / 2) ^ 2 = 0 ∧ team_winProb (team_P m) 1 + 1 / 16 ≤ team_winProb (team_P m) O
- Related work
- operator (Claude), 2026-10-05: counterexample to Theorem 4(2) of The Team Order Problem: Maximizing the Probability of Matching Being Large Enough, SAGT 2024 (arXiv:2605.21234), Section 6, Theorem 4(2); n = 2m+3 players, the identity line-up is the unique maximum-weight matching with all edges 1/2 (so the error term vanishes for every o(1) function), yet a rotation wins with probability at least 1/2 + 1/40; found by a search agent, checked by the Lean kernel
- Verified
- 05 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 9
- 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_isMaxWeightπ is a maximum-weight perfect matching.
- team_isOptimalπ is an optimal line-up (maximises the winning probability).
- team_PThe instance: p(i,i) = 1/2, p(i, i+1 mod n) = team_w i, all other entries 0.
- 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.
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/-- Quantitative form: on the instance of size `2m+3`, the optimal line-up beats the all-`1/2` maximum-weight matching by at least `1/16`, while the error term of Theorem 4 (2) of arXiv:2605.21234 is `0`. -/theorem team_gap (m : ℕ) (O : Equiv.Perm (Fin (2 * m + 3))) (hO : team_isOptimal (team_P m) O) : team_isMaxWeight (team_P m) 1 ∧ team_weight (team_P m) 1 = ((2 * m + 3 : ℕ) : ℝ) / 2 ∧ ∑ i : Fin (2 * m + 3), (team_P m i ((1 : Equiv.Perm (Fin (2 * m + 3))) i) - 1 / 2) ^ 2 = 0 ∧ team_winProb (team_P m) 1 + 1 / 16 ≤ team_winProb (team_P m) O := by refine ⟨team_id_maxWeight m, team_weight_id m, ?_, ?_⟩ · apply Finset.sum_eq_zero intro i _ simp [team_P] · have := hO (finRotate (2 * m + 3)) rw [team_rot_winProb] at this rw [team_id_winProb] linarith