team_rot_winProb2
lemmaverified
The rotation line-up of the strengthened instance wins with probability at least 1/2 + 1/40.
Statement
lemma team_rot_winProb2 (m : ℕ) :
1 / 2 + 1 / 40 ≤ team_winProb (team_P2 m) (finRotate (2 * m + 3))- Source
- step towards team_thm4_part2_false / team_thm4_part2_exists_false (The Team Order Problem: Maximizing the Probability of Matching Being Large Enough, SAGT 2024 (arXiv:2605.21234), Section 6, Theorem 4(2))
- Verified
- 06 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 12
- team_tailPoisson-binomial upper tail: team_tail [q₁, …, qₙ] t is the probability that at least t of n independent events with success probabilities…
- 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_tauSlack parameter τ_m = 1/(100(m+1)).
- team_tau_posThe slack tau = 1/(100(m+1)) is positive.
- team_tau_leThe slack tau is at most 1/100.
- team_tau_mul_le2 tau m is at most 1/50.
- 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_T2The list 0, b, 0, b, …, b, 0 (m copies of b).
- team_tail_nonnegUpper-tail probabilities of independent events with probabilities in [0,1] are nonnegative.
- team_T2_memIf b is in [0,1], every entry of the list 0,b,...,0 is in [0,1].
- team_T2_tailFor the list 0,b,...,0 with m copies of b, the probability of at least m successes is at least b^m.
- team_rot_list2The edge probabilities of the rotation in the strengthened instance are 3/4 - 3tau/2, 3/4 - 3tau/2, followed by 0, 1-2tau, 0, ..., 0.
- Used by 2
- team_thm4_part2_exists_falseEven 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…
- team_gap_uniqueQuantitative form of the strengthened counterexample: for every m, the identity is the unique maximum-weight matching, its edges are all…
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.
/-- The rotation line-up of the strengthened instance wins with probability at least `1/2 + 1/40`. -/lemma team_rot_winProb2 (m : ℕ) : 1 / 2 + 1 / 40 ≤ team_winProb (team_P2 m) (finRotate (2 * m + 3)) := by unfold team_winProb rw [team_rot_list2, show (2 * m + 3) / 2 + 1 = m + 2 by omega] set τ := team_tau m with hτ have ht0 := team_tau_pos m have ht1 := team_tau_le m have ht2 := team_tau_mul_le m set a : ℝ := 3 / 4 - 3 / 2 * τ with ha set b : ℝ := 1 - 2 * τ with hb have hb01 : 0 ≤ b ∧ b ≤ 1 := by constructor <;> linarith have hmem := team_T2_mem b hb01 m have hT := team_T2_tail b hb01 m have n1 := team_tail_nonneg _ hmem (m + 1) have n0 := team_tail_nonneg _ hmem m have n2 := team_tail_nonneg _ hmem (m + 2) -- Bernoulli: b^m ≥ 1 - 2τm ≥ 49/50 have hbern : 1 + (m : ℝ) * (-2 * τ) ≤ (1 + (-2 * τ)) ^ m := one_add_mul_le_pow (by linarith) m have hbm : (49 / 50 : ℝ) ≤ b ^ m := by rw [hb, show 1 - 2 * τ = 1 + (-2 * τ) by ring] nlinarith have ha0 : (147 / 200 : ℝ) ≤ a := by rw [ha]; linarith have ha1 : a ≤ 1 := by rw [ha]; linarith simp only [team_tail] rw [show m + 2 - 1 - 1 = m by omega, show m + 2 - 1 = m + 1 by omega] have hT' : (49 / 50 : ℝ) ≤ team_tail (team_T2 b m) m := le_trans hbm hT have hsq : (147 / 200 : ℝ) * (147 / 200) ≤ a * a := by nlinarith nlinarith [mul_nonneg (sub_nonneg.2 ha1) n1, mul_nonneg (sub_nonneg.2 ha1) n2, mul_nonneg (sub_nonneg.2 ha1) (mul_nonneg (sub_nonneg.2 ha1) n2), mul_nonneg (by linarith : (0 : ℝ) ≤ a) (mul_nonneg (sub_nonneg.2 ha1) n1), mul_nonneg (sub_nonneg.2 ha1) (mul_nonneg (by linarith : (0 : ℝ) ≤ a) n1)]