spr_opt_capacity_le
theoremverifiedoriginal
For every integer k ≥ 1, board size n ∈ {2k - 1, 2k}, and horizon t, the sign-preservation-with-reuse minimax value satisfies spr_opt n t ≤ k.
Statement
theorem spr_opt_capacity_le
(k : ℕ) (hk : 1 ≤ k) (n : ℕ) (hn : n = 2 * k - 1 ∨ n = 2 * k) (t : ℕ) :
spr_opt n t ≤ k- Related work
- arXiv:2410.07623 (Explicit asymptotic bounds for sequential calibration beyond T^{2/3})
- Verified
- 12 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- spr_optopt(n, t): the number of signs remaining at the end of the sign-preservation-with-reuse game with n cells and at most t rounds, under…
- spr_sign_countThe number of signs on a board of the sign-preservation-with-reuse game with n cells, each empty or holding a plus or a minus.
- spr_valueThe minimax value of the sign-preservation-with-reuse game with r rounds left from a given board: the pointer (maximizer) may stop or…
- spr_moveThe board after the labeler empties the cells of a set R and places the sign s in the selected cell j.
Read back from the Lean
For all natural numbers $k$, $n$, and $t$, if $1 \le k$ and $n = 2k - 1$ or $n = 2k$, then $\operatorname{spr\_opt}(n, t) \le k$.
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 Finsetdef spr_opt_capacity_le_inv (n : ℕ) (b : Fin n → Option Bool) : Prop := (∀ i : Fin n, b i = none ∨ b i = some (decide ((i : ℕ) % 2 = 1))) ∧ (∀ i₁ i₂ : Fin n, (b i₁).isSome → (b i₂).isSome → (i₁ : ℕ) / 2 = (i₂ : ℕ) / 2 → i₁ = i₂)lemma spr_opt_capacity_le_inv_none (n : ℕ) : spr_opt_capacity_le_inv n (fun _ => none) := ⟨fun _ => Or.inl rfl, fun _ _ h₁ => by simp at h₁⟩lemma spr_opt_capacity_le_div_two_eq_cases {i j : ℕ} (hdiv : i / 2 = j / 2) (hne : i ≠ j) : (i < j ∧ i % 2 = 0 ∧ j % 2 = 1) ∨ (j < i ∧ j % 2 = 0 ∧ i % 2 = 1) := by have hi := Nat.div_add_mod i 2 have hj := Nat.div_add_mod j 2 have hmi : i % 2 < 2 := Nat.mod_lt i (by decide) have hmj : j % 2 < 2 := Nat.mod_lt j (by decide) omegalemma spr_opt_capacity_le_legal_move {n : ℕ} (b : Fin n → Option Bool) (j : Fin n) (hj : b j = none) (hinv : spr_opt_capacity_le_inv n b) : let R : Finset (Fin n) := univ.filter (fun i => (i : ℕ) / 2 = (j : ℕ) / 2 ∧ (b i).isSome) ∀ i ∈ R, (i < j ∧ b i = some false) ∨ (j < i ∧ b i = some true) := by intro R i hi simp only [R, mem_filter, mem_univ, true_and] at hi have hne : (i : ℕ) ≠ (j : ℕ) := by intro heq have : i = j := Fin.ext heq have hbs := hi.2 rw [this, hj] at hbs contradiction have hcases := spr_opt_capacity_le_div_two_eq_cases hi.1 hne have hbi : b i = some (decide ((i : ℕ) % 2 = 1)) := by rcases hinv.1 i with h | h · have := hi.2; simp [h] at this · exact h rcases hcases with ⟨hlt, hmod, _⟩ | ⟨hlt, _, hmod⟩ · left refine ⟨Fin.lt_def.2 hlt, ?_⟩ rw [hbi, show decide ((i : ℕ) % 2 = 1) = false by simp [hmod]] · right refine ⟨Fin.lt_def.2 hlt, ?_⟩ rw [hbi, show decide ((i : ℕ) % 2 = 1) = true by simp [hmod]]lemma spr_opt_capacity_le_inv_move {n : ℕ} (b : Fin n → Option Bool) (j : Fin n) (hinv : spr_opt_capacity_le_inv n b) : let R : Finset (Fin n) := univ.filter (fun i => (i : ℕ) / 2 = (j : ℕ) / 2 ∧ (b i).isSome) let s : Bool := decide ((j : ℕ) % 2 = 1) spr_opt_capacity_le_inv n (spr_move b j R s) := by dsimp set R : Finset (Fin n) := univ.filter (fun i => (i : ℕ) / 2 = (j : ℕ) / 2 ∧ (b i).isSome) set s : Bool := decide ((j : ℕ) % 2 = 1) obtain ⟨h_parity, hinj⟩ := hinv constructor · intro i simp only [spr_move] split_ifs with h1 h2 · rw [h1]; right; rfl · left; rfl · exact h_parity i · intro i₁ i₂ h₁ h₂ hdiv simp only [spr_move] at h₁ h₂ by_cases h1 : i₁ = j · by_cases h2 : i₂ = j · rw [h1, h2] · exfalso simp only [if_neg h2] at h₂ split_ifs at h₂ with hR · contradiction have h_in_R : i₂ ∈ R := by simp only [R, mem_filter, mem_univ, true_and] exact ⟨by rw [← hdiv, h1], h₂⟩ exact hR h_in_R · by_cases h2 : i₂ = j · exfalso simp only [if_neg h1] at h₁ split_ifs at h₁ with hR · contradiction have h_in_R : i₁ ∈ R := by simp only [R, mem_filter, mem_univ, true_and] exact ⟨by rw [hdiv, h2], h₁⟩ exact hR h_in_R · simp only [if_neg h1] at h₁ simp only [if_neg h2] at h₂ split_ifs at h₁ with hR1 · contradiction split_ifs at h₂ with hR2 · contradiction exact hinj i₁ i₂ h₁ h₂ hdivlemma spr_opt_capacity_le_sign_count_le_of_inv {n k : ℕ} (hn : n ≤ 2 * k) (b : Fin n → Option Bool) (hinv : spr_opt_capacity_le_inv n b) : spr_sign_count b ≤ k := by have h_maps : Set.MapsTo (fun i : Fin n => (i : ℕ) / 2) ↑(univ.filter fun i : Fin n => (b i).isSome) ↑(range k) := by intro i hi simp only [mem_coe, mem_filter, mem_univ, true_and] at hi simp only [mem_coe, mem_range] have : (i : ℕ) < 2 * k := lt_of_lt_of_le i.isLt hn exact Nat.div_lt_of_lt_mul this have h_inj : Set.InjOn (fun i : Fin n => (i : ℕ) / 2) ↑(univ.filter fun i : Fin n => (b i).isSome) := by intro i₁ h₁ i₂ h₂ heq simp only [mem_coe, mem_filter, mem_univ, true_and] at h₁ h₂ exact hinv.2 i₁ i₂ h₁ h₂ heq have h := Finset.card_le_card_of_injOn (fun i : Fin n => (i : ℕ) / 2) h_maps h_inj rw [card_range] at h exact hlemma spr_opt_capacity_le_value_le_of_inv {n k : ℕ} (hn : n ≤ 2 * k) (t : ℕ) (b : Fin n → Option Bool) (hinv : spr_opt_capacity_le_inv n b) : spr_value n t b ≤ k := by induction t generalizing b with | zero => rw [spr_value.eq_1] exact spr_opt_capacity_le_sign_count_le_of_inv hn b hinv | succ r ih => rw [spr_value.eq_2] apply Nat.max_le.2 refine ⟨spr_opt_capacity_le_sign_count_le_of_inv hn b hinv, ?_⟩ apply Finset.sup_le intro j hj have hj_none : b j = none := (Finset.mem_filter.1 hj).2 let R : Finset (Fin n) := univ.filter (fun i => (i : ℕ) / 2 = (j : ℕ) / 2 ∧ (b i).isSome) let s : Bool := decide ((j : ℕ) % 2 = 1) have hp_mem : (R, s) ∈ (Finset.univ : Finset (Finset (Fin n) × Bool)).filter fun p => ∀ i ∈ p.1, (i < j ∧ b i = some false) ∨ (j < i ∧ b i = some true) := by rw [Finset.mem_filter] exact ⟨Finset.mem_univ _, spr_opt_capacity_le_legal_move b j hj_none hinv⟩ have h_next : spr_opt_capacity_le_inv n (spr_move b j R s) := spr_opt_capacity_le_inv_move b j hinv exact le_trans (Finset.inf'_le _ hp_mem) (ih (spr_move b j R s) h_next)/-- The capacity ceiling for sign preservation with reuse on linear boards: on boards of size 2k - 1 and 2k, the minimax value never exceeds k. -/theorem spr_opt_capacity_le (k : ℕ) (hk : 1 ≤ k) (n : ℕ) (hn : n = 2 * k - 1 ∨ n = 2 * k) (t : ℕ) : spr_opt n t ≤ k := by have _ := hk have hn_le : n ≤ 2 * k := by rcases hn with rfl | rfl · exact Nat.sub_le (2 * k) 1 · exact le_rfl exact spr_opt_capacity_le_value_le_of_inv hn_le t (fun _ => none) (spr_opt_capacity_le_inv_none n)