pell_run_level_le_start_add_two
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$.
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`).
uses
Fin.inductionhave main : ∀ i : Fin (w.length + 1), (r i).val ≤ (r 0).val + 2 := by intro i induction i using Fin.induction with | zero => simp
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`.
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 * <;> omegaThe 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.
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\}$.
- In line 15, `omega` automatically discharges all six case branches using linear integer arithmetic with modular constraints (modulo 5), ruling out candidate transitions whose required symbol residue conflicts with the hypothesis on the input word.
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.
/-- 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