prioritized_borel_threshold_alternating_counts_bounded
In the smallest threshold-strategy fork, on the fixed alternating c1,c2 branch, the recurrence counting compatible hidden histories has at most one history in each state-and-memory bucket at every depth. Thus the conjectured growth on that particular branch is false.
Statement
theorem prioritized_borel_threshold_alternating_counts_bounded :
∀ n, (in784_count_run n).h0 ≤ 1 ∧ (in784_count_run n).h1 ≤ 1 ∧
(in784_count_run n).p0 ≤ 1 ∧ (in784_count_run n).p1 ≤ 1 ∧
(in784_count_run n).q0 ≤ 1 ∧ (in784_count_run n).q1 ≤ 1- Source
- Filed by the prover as a step towards another result
- Verified
- 12 Nov 2026
- Axioms
Quot.soundpropext
The proof, explained
The proof proceeds in two parts: first, an inductive lemma shows that for depths n ≥ 4, the state of the recurrence alternates strictly between two 2-periodic configurations. Second, the main theorem bounds the counts by checking the base cases n < 4 directly by finite evaluation, and applying the alternating cycle to bound the counts by 1 for all larger depths.
For n = 0, the alternating pair holds by direct computation.
We proceed by induction on n. In the base case n = 0, the values for steps 4 and 5 are checked by direct computation.
intro n induction n with | zero => decide
The alternating pair holds for n + 1 given the induction hypothesis for n.
Using the induction hypothesis and the recurrence step definition, we show the values at 2(n+1)+4 and 2(n+1)+5 match the target states.
| succ n ih => rcases ih with ⟨heven, hodd⟩ have heq1 : 2 * (n+1) + 4 = (2*n+5)+1 := by omega have heq2 : 2 * (n+1) + 5 = (2*n+6)+1 := by omega have hmod1 : (2*n+5) % 2 = 1 := by omega have hmod2 : (2*n+6) % 2 = 0 := by omega have hnext : in784_count_run (2*n+6) = ⟨0, 1, 0, 0, 0, 1⟩ := by have hn : 2*n+6 = (2*n+5)+1 := by omega rw [hn, in784_count_run, hodd] simp [in784_count_step, hmod1] constructor · rw [show 2 * (n+1) + 4 = 2*n+6 by omega] exact hnext · rw [heq2, in784_count_run, hnext] simp [in784_count_step, hmod2]For n < 4, each bucket count is at most 1.
For n in {0, 1, 2, 3}, we check each case by computation.
intro n by_cases hsmall : n < 4 · interval_cases n <;> decide
For n ≥ 4, n can be written as 2m + 4 or 2m + 5.
We choose m = (n - 4) / 2 and verify by integer arithmetic.
· obtain ⟨m, hm⟩ : ∃ m, n = 2*m+4 ∨ n = 2*m+5 := by refine ⟨(n-4)/2, ?_⟩ omega
For n ≥ 4, each bucket count is at most 1.
We substitute the values from the alternating pair lemma and check that all coordinates are ≤ 1.
uses
in784_alternating_pairrcases hm with rfl | rfl · rw [(in784_alternating_pair m).1] decide · rw [(in784_alternating_pair m).2] decide
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
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.
structure In784Counts where h0 : ℕ h1 : ℕ p0 : ℕ p1 : ℕ q0 : ℕ q1 : ℕ deriving DecidableEqdef in784_count_step (c : In784Counts) (b : Bool) : In784Counts := ⟨c.q0, c.q1, if b then c.h0 else 0, if b then c.h1 else 0, c.q0 + if b then c.p1 else 0, c.q1 + if b then 0 else c.p0⟩def in784_count_run : ℕ → In784Counts | 0 => ⟨1, 0, 0, 0, 0, 0⟩ | n + 1 => in784_count_step (in784_count_run n) (decide (n % 2 = 0))theorem in784_alternating_pair : ∀ n, in784_count_run (2*n+4) = ⟨0, 1, 0, 0, 0, 1⟩ ∧ in784_count_run (2*n+5) = ⟨0, 1, 0, 1, 0, 1⟩ := by intro n induction n with | zero => decide | succ n ih => rcases ih with ⟨heven, hodd⟩ have heq1 : 2 * (n+1) + 4 = (2*n+5)+1 := by omega have heq2 : 2 * (n+1) + 5 = (2*n+6)+1 := by omega have hmod1 : (2*n+5) % 2 = 1 := by omega have hmod2 : (2*n+6) % 2 = 0 := by omega have hnext : in784_count_run (2*n+6) = ⟨0, 1, 0, 0, 0, 1⟩ := by have hn : 2*n+6 = (2*n+5)+1 := by omega rw [hn, in784_count_run, hodd] simp [in784_count_step, hmod1] constructor · rw [show 2 * (n+1) + 4 = 2*n+6 by omega] exact hnext · rw [heq2, in784_count_run, hnext] simp [in784_count_step, hmod2]theorem prioritized_borel_threshold_alternating_counts_bounded : ∀ n, (in784_count_run n).h0 ≤ 1 ∧ (in784_count_run n).h1 ≤ 1 ∧ (in784_count_run n).p0 ≤ 1 ∧ (in784_count_run n).p1 ≤ 1 ∧ (in784_count_run n).q0 ≤ 1 ∧ (in784_count_run n).q1 ≤ 1 := by intro n by_cases hsmall : n < 4 · interval_cases n <;> decide · obtain ⟨m, hm⟩ : ∃ m, n = 2*m+4 ∨ n = 2*m+5 := by refine ⟨(n-4)/2, ?_⟩ omega rcases hm with rfl | rfl · rw [(in784_alternating_pair m).1] decide · rw [(in784_alternating_pair m).2] decide