AFTD Auto-Formalizing Theoretical Domains

pell_run_level_le_start_add_two

theoremverified

In the Pell automaton A_n, if a run starting at state p reads only letters congruent to c_p or to c_{p+1} (mod 5), then at every time its state is one of p, p+1, p+2 — equivalently the state index never exceeds (index of p) + 2.

Statement

theorem pell_run_level_le_start_add_two (n : ℕ) (w : List (Fin 5))
    (r : Fin (w.length + 1) → Fin n)
    (hr : ∀ i : Fin w.length, r i.succ ∈ (pell_nfa n).step (r i.castSucc) (w.get i))
    (hw : ∀ i : Fin w.length, (w.get i).val = (r 0).val % 5 ∨ (w.get i).val = ((r 0).val + 1) % 5)
    (i : Fin (w.length + 1)) : (r i).val ≤ (r 0).val + 2
Source
step towards optimal_asymptotic_base_constant_finitely_ambiguous_nfa
Verified
20 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • pell_nfaFor every n, the 5-letter automaton A_n of the paper's lower bound: a chain q_1,…,q_n in which, for each 1 ≤ i ≤ n-2, the letter c_i…
  • pell_nfa_step_tableIn A_n, if q is reachable from p in one step on letter k, then one of the following holds: (i) k ≡ p (mod 5) and q = p or q = p+1; (ii) k…

The proof, explained

The theorem is proved by induction on the position $i$ along the run. In the base case $i = 0$, the inequality $r(0) \le r(0) + 2$ is trivial. For the inductive step, the transition table of the Pell automaton limits each step to an increase of at most 2, with the exact state increment constrained by the input letter modulo 5; because the input letters only take values congruent to $r(0)$ or $r(0) + 1 \pmod 5$, modular arithmetic rules out any transition that would advance the state index beyond $r(0) + 2$.

  1. The bound is set up for induction over all positions $i$, and the base case $i = 0$ holds.

    To allow induction on the position along the run, we introduce an auxiliary lemma `main` stating that $(r(i)).\mathrm{val} \le (r(0)).\mathrm{val} + 2$ for all $i \in \{0, \dots, |w|\}$, and proceed by induction on $i$ using `Fin.induction`. For the base case $i = 0$, the inequality $(r(0)).\mathrm{val} \le (r(0)).\mathrm{val} + 2$ is solved directly by simplification (`simp`).

    lines 7–10

    uses Fin.induction

      have main : ∀ i : Fin (w.length + 1), (r i).val ≤ (r 0).val + 2 := by
        intro i
        induction i using Fin.induction with
        | zero => simp
  2. The bound is preserved across transitions: if $(r(j)).\mathrm{val} \le (r(0)).\mathrm{val} + 2$, then $(r(j+1)).\mathrm{val} \le (r(0)).\mathrm{val} + 2$. automation

    For the induction step at index $j$, we apply `pell_nfa_step_table` to the transition hypothesis `hr j` to obtain `hs`, which limits the step from $r(j)$ to $r(j+1)$ to three cases, each pairing a residue for $w_j \pmod 5$ with at most two candidate values for $r(j+1)$ (at most $r(j)+2$). Specializing the input hypothesis `hw` to index $j$ yields `hwj`, asserting that $w_j$ is congruent to $r(0)$ or $r(0)+1 \pmod 5$. Destructuring `hs` via `rcases` into six cases, we substitute the transition equalities and call `omega`. In each case, linear integer arithmetic modulo 5 proves that $r(j+1) \le r(0) + 2$: any transition that would advance the state past $r(0) + 2$ requires an input symbol residue modulo 5 that is incompatible with `hwj`.

    lines 11–15

    uses pell_nfa_step_table

        | succ j ih =>
          have hs := pell_nfa_step_table n (hr j)
          have hwj := hw j
          rcases hs with ⟨h1, h2 | h2⟩ | ⟨h1, h2 | h2⟩ | ⟨h1, h2 | h2⟩ <;>
            simp only [h1, h2] at * <;> omega
  3. The inequality $(r(i)).\mathrm{val} \le (r(0)).\mathrm{val} + 2$ holds for the original index $i$.

    Specializing the universally quantified induction result `main` to the target index $i$ completes the proof.

    line 16

      exact main i
Fin.induction
Induction principle for `Fin (n + 1)`: to prove a property for all elements of `Fin (n + 1)`, it suffices to establish the base case for `0` and the inductive step from `j.castSucc` to `j.succ`.
pell_nfa_step_table
Transition table for the Pell automaton: any valid step from state $p$ to state $q$ reading symbol $k$ satisfies one of three cases: $k \equiv p \pmod 5$ and $q \in \{p, p+1\}$; $k \equiv p+1 \pmod 5$ and $q \in \{p, p+2\}$; or $k \equiv p+2 \pmod 5$ and $q \in \{p+1, p+2\}$.

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

/-- Structural fact behind finite ambiguity of the Pell automaton: a run that only ever reads letters congruent to c_p or c_{p+1} (mod 5) never climbs above the state two places beyond its starting state. -/theorem pell_run_level_le_start_add_two (n : ℕ) (w : List (Fin 5))    (r : Fin (w.length + 1) → Fin n)    (hr : ∀ i : Fin w.length, r i.succ ∈ (pell_nfa n).step (r i.castSucc) (w.get i))    (hw : ∀ i : Fin w.length, (w.get i).val = (r 0).val % 5 ∨ (w.get i).val = ((r 0).val + 1) % 5)    (i : Fin (w.length + 1)) : (r i).val ≤ (r 0).val + 2 := by  have main : ∀ i : Fin (w.length + 1), (r i).val ≤ (r 0).val + 2 := by    intro i    induction i using Fin.induction with    | zero => simp    | succ j ih =>      have hs := pell_nfa_step_table n (hr j)      have hwj := hw j      rcases hs with ⟨h1, h2 | h2⟩ | ⟨h1, h2 | h2⟩ | ⟨h1, h2 | h2⟩ <;>        simp only [h1, h2] at * <;> omega  exact main i
See it in the graphDiscuss this resultChallenge it