AFTD Auto-Formalizing Theoretical Domains

team_thm4_part2_exists_false

theoremverifiederratum

Even the existential reading of Theorem 4 (2) of arXiv:2605.21234 is false, for every function ε in place of o(1): on the (2m+3)-player strengthened instance the all-1/2 identity is the unique maximum-weight matching (so the error term is 0), it wins with probability 1/2, and the optimal line-up wins with probability at least 1/2 + 1/40.

Statement

open Finset in
theorem team_thm4_part2_exists_false (ε : ℕ → ℝ) (N : ℕ) : ¬ team_thm4_part2_exists ε N
Corrects
The Team Order Problem: Maximizing the Probability of Matching Being Large Enough, SAGT 2024 (arXiv:2605.21234), Section 6, Theorem 4(2), even in its existential reading (some maximum-weight matching satisfies the bound): false for every o(1) function; unique all-1/2 maximum-weight matching, gap at least 1/40
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_P2The strengthened instance: p(i,i) = 1/2, p(i, i+1 mod n) = 1/2 - v'_i + v'_{i+1} - τ, all other entries 0.
  • team_P2_boundsAll entries of the strengthened Team Order instance are probabilities in [0,1].
  • team_weight2_idIn the strengthened instance the identity line-up has weight n/2.
  • team2_unique_maxWeightThe identity is the unique maximum-weight matching of the strengthened instance.
  • team_id_winProb2In the strengthened instance the identity line-up (all edges 1/2) wins with probability exactly 1/2.
  • team_rot_winProb2The rotation line-up of the strengthened instance wins with probability at least 1/2 + 1/40.
  • team_thm4_part2_existsTheorem 4 (2) of arXiv:2605.21234 under its most generous (existential) reading: some maximum-weight matching M* satisfies the bound.

Read back from the Lean

The declaration team_thm4_part2_exists_false asserts that for every function ε : ℕ → ℝ and every natural number N : ℕ, the proposition team_thm4_part2_exists ε N does not hold (is false). Here, team_thm4_part2_exists ε N is the proposition that: For every natural number n ≥ N, for every matrix/function P : Fin n → Fin n → ℝ, if 0 ≤ P i j ≤ 1 for all i, j : Fin n, then for every permutation O : Equiv.Perm (Fin n) that is optimal (i.e., team_winProb P σ ≤ team_winProb P O for all permutations σ), there exists a permutation Mstar : Equiv.Perm (Fin n) such that: 1. Mstar has maximum weight (i.e., team_weight P σ ≤ team_weight P Mstar for all permutations σ), and 2. If (n : ℝ) / 2 - Real.sqrt n * Real.log n ≤ team_weight P Mstar and team_weight P Mstar ≤ (n : ℝ) / 2 + Real.sqrt n * Real.log n, then: team_winProb P O ≤ team_winProb P Mstar + ((4 + ε n) / ((n : ℝ) + 1)) * ∑ i : Fin n, (P i (Mstar i) - 1 / 2) ^ 2. Therefore, the theorem asserts that for any ε : ℕ → ℝ and any N : ℕ, there exists some n ≥ N, some P : Fin n → Fin n → ℝ with values in [0, 1], and some permutation O maximizing team_winProb P ·, such that every permutation Mstar fails the conjunction: either Mstar does not maximize team_weight P ·, or team_weight P Mstar falls in [n / 2 - √n ln n, n / 2 + √n ln n] and team_winProb P O > team_winProb P Mstar + ((4 + ε n) / (n + 1)) * ∑ i, (P i (Mstar i) - 1/2)^2.

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/-- Even the existential reading of Theorem 4 (2) of arXiv:2605.21234 is false, for every function `ε` in place of `o(1)`: on the `(2m+3)`-player strengthened instance the all-`1/2` identity is the unique maximum-weight matching (so the error term is `0`), it wins with probability `1/2`, and the optimal line-up wins with probability at least `1/2 + 1/40`. -/theorem team_thm4_part2_exists_false (ε : ℕ → ℝ) (N : ℕ) : ¬ team_thm4_part2_exists ε N := by  intro h  obtain ⟨O, -, hO⟩ := Finset.exists_max_image (univ : Finset (Equiv.Perm (Fin (2 * N + 3))))    (team_winProb (team_P2 N)) ⟨1, Finset.mem_univ _⟩  have hOpt : team_isOptimal (team_P2 N) O := fun σ => hO σ (Finset.mem_univ _)  obtain ⟨M, hM, hbound⟩ := h (2 * N + 3) (by omega) (team_P2 N) (team_P2_bounds N) O hOpt  have hM1 : M = 1 := (team2_unique_maxWeight N M).1 hM  subst hM1  have hn : (((2 * N + 3 : ℕ) : ℝ)) / 2 = team_weight (team_P2 N) 1 := (team_weight2_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 := hbound (by linarith) (by linarith)  have hsq : ∑ i : Fin (2 * N + 3), (team_P2 N i ((1 : Equiv.Perm (Fin (2 * N + 3))) i) - 1 / 2) ^ 2      = 0 := by    apply Finset.sum_eq_zero    intro i _    simp [team_P2]  rw [hsq, mul_zero, add_zero, team_id_winProb2] at key  have hrot := hOpt (finRotate (2 * N + 3))  have := team_rot_winProb2 N  linarith
See it in the graphDiscuss this resultChallenge it