pell_nfa_step_table
In 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 ≡ p+1 (mod 5) and q = p or q = p+2; (iii) k ≡ p+2 (mod 5) and q = p+1 or q = p+2. In particular all transitions are nondecreasing in the state index and jump by at most 2, and the letters of residues k ≡ p+3, p+4 (mod 5) are dead at p.
Statement
theorem pell_nfa_step_table (n : ℕ) {p q : Fin n} {k : Fin 5}
(h : q ∈ (pell_nfa n).step p k) :
(k.val = p.val % 5 ∧ (q.val = p.val ∨ q.val = p.val + 1)) ∨
(k.val = (p.val + 1) % 5 ∧ (q.val = p.val ∨ q.val = p.val + 2)) ∨
(k.val = (p.val + 2) % 5 ∧ (q.val = p.val + 1 ∨ q.val = p.val + 2))- Source
- step towards finitely_ambiguous_nfa_pell_lower_bound
- Verified
- 19 Oct 2026
- Axioms
Quot.soundpropext- Built on 1
- 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…
- Used by 3
- pell_nfa_no_idaThe Pell automaton A_n does not comply with IDA: there are no distinct states p, q and no word v such that p is reachable from p by v, q…
- pell_run_level_le_start_add_twoIn 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…
- pell_nfa_has_singleton_sccsFor every natural number n, the n-state Pell NFA pell_nfa n has singleton strongly connected components.
The proof, explained
The proof unfolds the definition of `pell_nfa` to extract the internal index $i$ governing the transition from $p$ to $q$ on letter $k$. It then performs a case analysis on the five possible configurations of $(p, q)$ relative to $i$ specified by the automaton. In each case, expressing $i$ in terms of $p$ immediately matches one of the three clauses in the theorem, and integer linear and modular arithmetic (`omega`) verifies the claim.
The transition assumption $q \in \operatorname{step}(p, k)$ unfolds into an existential witness $i$ satisfying $1 \le i \le n - 2$ and one of two main transition conditions.
Unfolding the definition of the automaton `pell_nfa` in $h$ shows that a transition from state $p$ to state $q$ on letter $k$ is parameterized by an integer index $i$ with $1 \le i$ and $i + 2 \le n$. We unpack $i$, these bounds, and the disjunctive condition on $k, p, q$.
simp only [pell_nfa] at h obtain ⟨i, hi1, hi2, h⟩ := h
In the case where $k \equiv i \pmod 5$, the step satisfies either clause (ii) or clause (i) of the theorem.
We split on the outer disjunction. Here $k \equiv i \pmod 5$, and there are two possible configurations for $p$: 1. $p = i - 1$ and $q \in \{i - 1, i + 1\}$: Since $1 \le i$, we have $i = p + 1$, which gives $k \equiv p + 1 \pmod 5$ and $q \in \{p, p + 2\}$. This matches clause (ii), so we choose the middle disjunct (`right; left`) and close the arithmetic with `omega`. 2. $p = i$ and $q \in \{i, i + 1\}$: Here $k \equiv p \pmod 5$ and $q \in \{p, p + 1\}$. This matches clause (i), so we choose the first disjunct (`left`) and close with `omega`.
rcases h with h | h · obtain ⟨hk, hpq⟩ := h rcases hpq with ⟨hp1, hq⟩ | ⟨hp2, hq⟩ · right; left exact ⟨by omega, by rcases hq with hq | hq <;> omega⟩ · left exact ⟨by omega, by rcases hq with hq | hq <;> omega⟩
In the case where $k \equiv i + 1 \pmod 5$, the step satisfies clause (ii), clause (i), or clause (iii) of the theorem.
In the second outer branch, $k \equiv i + 1 \pmod 5$. The transition definition provides three subcases: 1. $p = i$ and $q = i$: Then $k \equiv p + 1 \pmod 5$ and $q = p$, matching clause (ii) (`right; left`). 2. $p = i + 1$ and $q = i + 1$: Then $k \equiv p \pmod 5$ and $q = p$, matching clause (i) (`left`). 3. $p = i - 1$ and $q \in \{i, i + 1\}$: Since $i = p + 1$, we obtain $k \equiv p + 2 \pmod 5$ and $q \in \{p + 1, p + 2\}$, matching clause (iii) (`right; right`). In all three cases, linear and modular arithmetic (`omega`) closes the goals.
· obtain ⟨hk, hpq⟩ := h rcases hpq with ⟨hp1, hq1⟩ | ⟨hp2, hq2⟩ | ⟨hp3, hq⟩ · right; left exact ⟨by omega, by omega⟩ · left exact ⟨by omega, by omega⟩ · right; right exact ⟨by omega, by rcases hq with hq | hq <;> omega⟩
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.
/-- Local transition table of `pell_nfa n`: from state ⟨p⟩ only the three letters of residue p, p+1, p+2 (mod 5) are readable, and they act by staying or by jumping one/two places. -/theorem pell_nfa_step_table (n : ℕ) {p q : Fin n} {k : Fin 5} (h : q ∈ (pell_nfa n).step p k) : (k.val = p.val % 5 ∧ (q.val = p.val ∨ q.val = p.val + 1)) ∨ (k.val = (p.val + 1) % 5 ∧ (q.val = p.val ∨ q.val = p.val + 2)) ∨ (k.val = (p.val + 2) % 5 ∧ (q.val = p.val + 1 ∨ q.val = p.val + 2)) := by simp only [pell_nfa] at h obtain ⟨i, hi1, hi2, h⟩ := h rcases h with h | h · obtain ⟨hk, hpq⟩ := h rcases hpq with ⟨hp1, hq⟩ | ⟨hp2, hq⟩ · right; left exact ⟨by omega, by rcases hq with hq | hq <;> omega⟩ · left exact ⟨by omega, by rcases hq with hq | hq <;> omega⟩ · obtain ⟨hk, hpq⟩ := h rcases hpq with ⟨hp1, hq1⟩ | ⟨hp2, hq2⟩ | ⟨hp3, hq⟩ · right; left exact ⟨by omega, by omega⟩ · left exact ⟨by omega, by omega⟩ · right; right exact ⟨by omega, by rcases hq with hq | hq <;> omega⟩