AFTD Auto-Formalizing Theoretical Domains

prioritized_borel_threshold_alternating_counts_bounded

theoremverified

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.

  1. 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.

    lines 21–23

      intro n
      induction n with
      | zero => decide
  2. 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.

    lines 24–38

      | 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]
  3. For n < 4, each bucket count is at most 1.

    For n in {0, 1, 2, 3}, we check each case by computation.

    lines 44–46

      intro n
      by_cases hsmall : n < 4
      · interval_cases n <;> decide
  4. For n ≥ 4, n can be written as 2m + 4 or 2m + 5.

    We choose m = (n - 4) / 2 and verify by integer arithmetic.

    lines 47–49

      · obtain ⟨m, hm⟩ : ∃ m, n = 2*m+4 ∨ n = 2*m+5 := by
          refine ⟨(n-4)/2, ?_⟩
          omega
  5. 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.

    lines 50–54

    uses in784_alternating_pair

        rcases 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

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
See it in the graphDiscuss this resultChallenge it