pell_nfa_is_trim
The n-state Pell NFA pell_nfa n is trim: every state is reachable from the start state and can reach an accept state.
Statement
theorem pell_nfa_is_trim (n : ℕ) (hn : 3 ≤ n) : nfa_is_trim (pell_nfa n)- Source
- step towards finitely_ambiguous_nfa_pell_lower_bound
- Verified
- 19 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…
- nfa_is_trimAn NFA M is trim if every state q is reachable from the start states by some word and co-reachable (can reach an accept state by some word).
The proof, explained
To show that the Pell NFA with n ≥ 3 states is trim, we show that every state q is reachable from the initial state 0 and can reach the unique accept state n - 1. We establish this by constructing a directed path along the linear chain 0 → 1 → ... → n - 1. A helper lemma shows that from any state p < n - 1, a single step along the chain to p + 1 is valid under a designated input letter (letter 2 when p = 0, and p % 5 when p > 0). By induction on the distance m, any state p + m is reachable from state p by walking this chain. Setting p = 0 gives reachability from the start state to q, and setting p = q gives reachability from q to the accept state n - 1.
The stepping letter from state p is well-defined as an element of Fin 5: it is 2 when p = 0, and p % 5 when p > 0.
When p > 0, the remainder p % 5 is strictly less than 5 by Nat.mod_lt, since 0 < 5 is verified by numerical computation (norm_num).
uses
Nat.mod_lt/-- The letter of the `p`-th chain step: `2` from the first state, `p % 5` above. -/ def pell_nfa_is_trim_letter (p : ℕ) : Fin 5 := if p = 0 then 2 else ⟨p % 5, Nat.mod_lt p (by norm_num)⟩
A single chain step from p to p + 1 reduces to finding an index i that satisfies the Pell NFA transition relation.
We fix states s and q with values p and p + 1. Unfolding the definition of pell_nfa, pell_nfa_is_trim_letter, and set comprehension membership via Set.mem_ofPred_eq, and substituting the values of s and q, the goal is to find an index i such that 1 ≤ i and i + 2 ≤ n satisfying the transition formula.
uses
pell_nfa,pell_nfa_is_trim_letter,Set.mem_ofPred_eqtheorem pell_nfa_is_trim_step_succ (n p : ℕ) (hn : 3 ≤ n) (hp : p + 1 < n) : ∀ (s q : Fin n), s.val = p → q.val = p + 1 → q ∈ (pell_nfa n).step s (pell_nfa_is_trim_letter p) := by intro s q hs hq simp only [pell_nfa, pell_nfa_is_trim_letter, Set.mem_ofPred_eq] rw [hs, hq]
For p = 0, state 0 transitions to state 1 with letter 2.
We split on whether p = 0. When p = 0, the stepping letter is 2. Choosing index i = 1, the bounds 1 ≤ 1 and 1 + 2 ≤ n hold since n ≥ 3, and numerical evaluation (norm_num) verifies the second clause with (1 + 1) % 5 = 2, transitioning from 0 = i - 1 to 1 = i.
by_cases hp0 : p = 0 · rw [hp0] refine ⟨1, by norm_num, by omega, ?_⟩ norm_num
For p > 0, state p transitions to state p + 1 with letter p % 5.
When p ≠ 0, we choose index i = p. Since p ≥ 1 and p + 1 < n, we have 1 ≤ p and p + 2 ≤ n. Simplifying with if_neg hp0 reduces the letter to p % 5 = i % 5, which satisfies the first transition clause from p = i to p + 1 = i + 1.
uses
if_neg· refine ⟨p, by omega, by omega, ?_⟩ simp only [if_neg hp0] simp /-- From a state of value `p` one reaches any state of value `p + m` by walking the chain. -/
Any state q of value p + m is reachable from state s of value p; in the base case m = 0, the empty word suffices.
We induct on m. In the base case m = 0, the values of q and s are both p, so q = s by Fin.ext. Running the empty word [] from {s} keeps the automaton in {s} by NFA.evalFrom_nil and Set.mem_singleton_iff, reaching q.
uses
NFA.evalFrom_nil,Set.mem_singleton_iff,Fin.exttheorem pell_nfa_is_trim_reach_fwd (n : ℕ) (hn : 3 ≤ n) : ∀ (m p : ℕ), p + m < n → ∀ (s q : Fin n), s.val = p → q.val = p + m → ∃ w, q ∈ (pell_nfa n).evalFrom {s} w := by intro m induction m with | zero => intro p hp s q hs hq exact ⟨[], by simp only [NFA.evalFrom_nil, Set.mem_singleton_iff]; exact Fin.ext (by omega)⟩
In the induction step, extending a path of length m by one chain step reaches state q of value p + m + 1.
By the induction hypothesis, there is a word w reaching the state with value p + m from s. By pell_nfa_is_trim_step_succ, reading pell_nfa_is_trim_letter (p + m) transitions from value p + m to state q with value p + m + 1. Appending this letter to w and rewriting via NFA.evalFrom_append, NFA.evalFrom_singleton, and NFA.mem_stepSet confirms that q is reached.
uses
pell_nfa_is_trim_step_succ,pell_nfa_is_trim_letter,NFA.evalFrom_append,NFA.evalFrom_singleton,NFA.mem_stepSet| succ m ih => intro p hp s q hs hq have hpm : p + m < n := by omega obtain ⟨w, hw⟩ := ih p hpm s ⟨p + m, hpm⟩ hs rfl have hstep : q ∈ (pell_nfa n).step ⟨p + m, hpm⟩ (pell_nfa_is_trim_letter (p + m)) := by refine pell_nfa_is_trim_step_succ n (p + m) hn (by omega) _ q rfl ?_ show (↑q : ℕ) = p + m + 1 omega refine ⟨w ++ [pell_nfa_is_trim_letter (p + m)], ?_⟩ simp only [NFA.evalFrom_append, NFA.evalFrom_singleton, NFA.mem_stepSet] exact ⟨_, hw, hstep⟩Every state q in the Pell NFA is reachable from the start state.
Applying pell_nfa_is_trim_reach_fwd with start value 0 and distance q.val yields a word w reaching q from state 0. Since state 0 is the start state of pell_nfa n, NFA.mem_evalFrom_iff_exists.mpr shows that q is reachable from the NFA's start set.
uses
pell_nfa_is_trim_reach_fwd,NFA.mem_evalFrom_iff_exists.mpr/-- The n-state Pell NFA pell_nfa n is trim for n ≥ 3. -/ theorem pell_nfa_is_trim (n : ℕ) (hn : 3 ≤ n) : nfa_is_trim (pell_nfa n) := by intro q constructor · obtain ⟨w, hw⟩ := pell_nfa_is_trim_reach_fwd n hn q.val 0 (by omega) ⟨0, by omega⟩ q rfl (by omega) exact ⟨w, NFA.mem_evalFrom_iff_exists.mpr ⟨⟨0, by omega⟩, rfl, hw⟩⟩
Every state q in the Pell NFA can reach an accept state, completing the proof that the NFA is trim.
The accept condition in pell_nfa n is val + 1 = n, which corresponds uniquely to state n - 1. Applying pell_nfa_is_trim_reach_fwd from q with distance n - 1 - q.val yields a word w reaching state n - 1 from q. Since (n - 1) + 1 = n, state n - 1 is an accept state, proving that pell_nfa n is trim.
uses
pell_nfa_is_trim_reach_fwd· obtain ⟨w, hw⟩ := pell_nfa_is_trim_reach_fwd n hn (n - 1 - q.val) q.val (by omega) q ⟨n - 1, by omega⟩ rfl (by simp; omega) exact ⟨w, ⟨n - 1, by omega⟩, by show (n - 1) + 1 = n; omega, hw⟩
Nat.mod_lt- For any natural numbers x and y with y > 0, the remainder x % y satisfies x % y < y.
pell_nfa- The definition of the Pell NFA on n states with alphabet Fin 5, having start state 0, accept state n - 1, and transition relation defined by modular arithmetic conditions.
pell_nfa_is_trim_letter- The stepping letter for state value p, defined as 2 if p = 0, and p % 5 (in Fin 5) if p > 0.
Set.mem_ofPred_eq- Membership of an element x in a set defined by a predicate {y | p y} is definitionally equivalent to p x.
if_neg- If a proposition c is false, then the conditional expression if c then t else e evaluates to e.
NFA.evalFrom_nil- Evaluating an NFA on the empty word [] from a state set S leaves the set S unchanged.
Set.mem_singleton_iff- An element a belongs to the singleton set {b} if and only if a = b.
Fin.ext- Two elements of Fin n are equal if and only if their underlying natural number values are equal.
pell_nfa_is_trim_step_succ- In the Pell NFA with n ≥ 3 states, if p + 1 < n, then reading letter pell_nfa_is_trim_letter p transitions from any state with value p to any state with value p + 1.
NFA.evalFrom_append- Evaluating an NFA on a concatenated word x ++ y from state set S equals evaluating on y starting from the set of states reached after reading x.
NFA.evalFrom_singleton- Evaluating an NFA on a single-letter word [a] from state set S equals the one-step set transition stepSet S a.
NFA.mem_stepSet- A state s belongs to stepSet S a if and only if s is reachable in one step on letter a from some state t in S.
pell_nfa_is_trim_reach_fwd- In the Pell NFA with n ≥ 3 states, for any p and m with p + m < n, any state of value p + m is reachable by some word starting from any state of value p.
NFA.mem_evalFrom_iff_exists.mpr- If a state is reachable on word w from the singleton {t} for some t in S, then it is reachable on word w from the set of states S.
- The stepping letters are chosen differently for the first transition (p = 0, which uses letter 2) versus subsequent transitions (p > 0, which use letter p % 5) to match the two clauses in the definition of the Pell NFA transition relation. Small arithmetic verifications ensuring indices lie within the valid range [1, n-2] and satisfy the modular congruence conditions are handled by omega and norm_num.
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.
/-- The letter of the `p`-th chain step: `2` from the first state, `p % 5` above. -/def pell_nfa_is_trim_letter (p : ℕ) : Fin 5 := if p = 0 then 2 else ⟨p % 5, Nat.mod_lt p (by norm_num)⟩/-- A single chain step: from a state of value `p` the letter `pell_nfa_is_trim_letter p` reaches anystate of value `p + 1`. -/theorem pell_nfa_is_trim_step_succ (n p : ℕ) (hn : 3 ≤ n) (hp : p + 1 < n) : ∀ (s q : Fin n), s.val = p → q.val = p + 1 → q ∈ (pell_nfa n).step s (pell_nfa_is_trim_letter p) := by intro s q hs hq simp only [pell_nfa, pell_nfa_is_trim_letter, Set.mem_ofPred_eq] rw [hs, hq] by_cases hp0 : p = 0 · rw [hp0] refine ⟨1, by norm_num, by omega, ?_⟩ norm_num · refine ⟨p, by omega, by omega, ?_⟩ simp only [if_neg hp0] simp/-- From a state of value `p` one reaches any state of value `p + m` by walking the chain. -/theorem pell_nfa_is_trim_reach_fwd (n : ℕ) (hn : 3 ≤ n) : ∀ (m p : ℕ), p + m < n → ∀ (s q : Fin n), s.val = p → q.val = p + m → ∃ w, q ∈ (pell_nfa n).evalFrom {s} w := by intro m induction m with | zero => intro p hp s q hs hq exact ⟨[], by simp only [NFA.evalFrom_nil, Set.mem_singleton_iff]; exact Fin.ext (by omega)⟩ | succ m ih => intro p hp s q hs hq have hpm : p + m < n := by omega obtain ⟨w, hw⟩ := ih p hpm s ⟨p + m, hpm⟩ hs rfl have hstep : q ∈ (pell_nfa n).step ⟨p + m, hpm⟩ (pell_nfa_is_trim_letter (p + m)) := by refine pell_nfa_is_trim_step_succ n (p + m) hn (by omega) _ q rfl ?_ show (↑q : ℕ) = p + m + 1 omega refine ⟨w ++ [pell_nfa_is_trim_letter (p + m)], ?_⟩ simp only [NFA.evalFrom_append, NFA.evalFrom_singleton, NFA.mem_stepSet] exact ⟨_, hw, hstep⟩/-- The n-state Pell NFA pell_nfa n is trim for n ≥ 3. -/theorem pell_nfa_is_trim (n : ℕ) (hn : 3 ≤ n) : nfa_is_trim (pell_nfa n) := by intro q constructor · obtain ⟨w, hw⟩ := pell_nfa_is_trim_reach_fwd n hn q.val 0 (by omega) ⟨0, by omega⟩ q rfl (by omega) exact ⟨w, NFA.mem_evalFrom_iff_exists.mpr ⟨⟨0, by omega⟩, rfl, hw⟩⟩ · obtain ⟨w, hw⟩ := pell_nfa_is_trim_reach_fwd n hn (n - 1 - q.val) q.val (by omega) q ⟨n - 1, by omega⟩ rfl (by simp; omega) exact ⟨w, ⟨n - 1, by omega⟩, by show (n - 1) + 1 = n; omega, hw⟩