pell_nfa_has_singleton_sccs
For every natural number n, the n-state Pell NFA pell_nfa n has singleton strongly connected components.
Statement
theorem pell_nfa_has_singleton_sccs (n : ℕ) : nfa_has_singleton_sccs (pell_nfa n)- Source
- arXiv:2610.08525 Appendix A
- Verified
- 25 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- nfa_has_singleton_sccsAn NFA M has singleton strongly connected components if for all states p and q, whenever q is reachable from {p} by some word and p is…
- 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…
Read back from the Lean
For every natural number $n$, the nondeterministic finite automaton pell_nfa n has singleton strongly connected components; that is, for all states $p, q : \text{Fin } n$, if $q$ is reachable from $p$ on some input word $w_1$ (meaning $q \in (\text{pell\_nfa } n).\text{evalFrom } \{p\}\, w_1$) and $p$ is reachable from $q$ on some input word $w_2$ (meaning $p \in (\text{pell\_nfa } n).\text{evalFrom } \{q\}\, w_2$), then $p = q$.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The theorem establishes that the strongly connected components of the Pell automaton are singletons, meaning that mutual reachability between any two states implies they are identical. The proof first shows by induction on the input word that reachability is weakly monotonic with respect to state indices: according to the transition table, every step either stays at the current state or advances to a state with a larger index. For any mutually reachable states p and q, this monotonicity implies both p.val ≤ q.val and q.val ≤ p.val, forcing p = q by antisymmetry.
In the base case w = [], reachability implies p.val ≤ q.val.
We proceed by induction on w, generalizing over p. For the empty word nil, evaluating the Pell NFA from {p} leaves the set unchanged, so q ∈ {p}, which means q = p. Substituting q = p, the inequality p.val ≤ p.val holds by reflexivity.
uses
NFA.evalFrom_nil,Set.mem_singleton_iffinduction w generalizing p with | nil => simp only [NFA.evalFrom_nil, Set.mem_singleton_iff] at h subst h rfl
In the inductive step for w = a :: w', reachability factors through an intermediate state r reachable in one step from p.
Evaluating the Pell NFA on a :: w' from {p} is equivalent to evaluating w' from the set of states reachable from {p} on symbol a. Rewriting this set evaluation into existential form yields an intermediate state r ∈ step p a such that q is reachable from {r} along w'.
uses
NFA.evalFrom_cons,NFA.stepSet_singleton,NFA.mem_evalFrom_iff_exists| cons a w' ih => simp only [NFA.evalFrom_cons, NFA.stepSet_singleton] at h rw [NFA.mem_evalFrom_iff_exists] at h rcases h with ⟨r, hr, hq⟩Any single transition from p to r satisfies p.val ≤ r.val.
Applying pell_nfa_step_table to r ∈ step p a yields three cases: either r = p or r = p + 1; r = p or r = p + 2; or r = p + 1 or r = p + 2. In each case, linear arithmetic (omega) verifies that p.val ≤ r.val.
uses
pell_nfa_step_tablehave h1 : p.val ≤ r.val := by have htab := pell_nfa_step_table n hr rcases htab with ⟨-, h⟩ | ⟨-, h⟩ | ⟨-, h⟩ · rcases h with h | h <;> omega · rcases h with h | h <;> omega · rcases h with h | h <;> omega
The inductive step is complete: p.val ≤ q.val.
Applying the induction hypothesis to the remaining path r xrightarrow{w'} q gives r.val ≤ q.val. Combining this with the one-step inequality p.val ≤ r.val, linear arithmetic (omega) concludes p.val ≤ q.val.
have h2 : r.val ≤ q.val := ih hq omega
Mutually reachable states p and q satisfy both p.val ≤ q.val and q.val ≤ p.val.
To prove that all strongly connected components are singletons, suppose q is reachable from p by a word w1 and p is reachable from q by a word w2. Applying pell_nfa_has_singleton_sccs_evalFrom_le in each direction yields p.val ≤ q.val and q.val ≤ p.val.
uses
pell_nfa_has_singleton_sccs_evalFrom_leintro p q ⟨w1, hw1⟩ ⟨w2, hw2⟩ have h1 := pell_nfa_has_singleton_sccs_evalFrom_le n w1 hw1 have h2 := pell_nfa_has_singleton_sccs_evalFrom_le n w2 hw2
p = q, establishing that every strongly connected component is a singleton.
By extensionality for Fin n, the states p and q are equal if and only if their underlying numerical values are equal. From p.val ≤ q.val and q.val ≤ p.val, linear arithmetic (omega) forces p.val = q.val, whence p = q.
ext omega
NFA.evalFrom_nil- Evaluating an automaton from a set of states S on the empty word yields S.
Set.mem_singleton_iff- An element belongs to a singleton set {b} if and only if it equals b.
NFA.evalFrom_cons- Evaluating an automaton on a word a :: x from a set S is equal to evaluating on x from the set of states reachable in one step from S on symbol a.
NFA.stepSet_singleton- The set of states reachable in one step from a singleton set {s} on input symbol a is the transition set step s a.
NFA.mem_evalFrom_iff_exists- A state is in the evaluation of an automaton from a set S on word x if and only if it is reachable on x from some state in S.
pell_nfa_step_table- Any transition from state p to state q in the Pell NFA implies that q is p, p + 1, or p + 2.
pell_nfa_has_singleton_sccs_evalFrom_le- If state q is reachable from state p along word w in the Pell NFA, then the index of p is less than or equal to the index of q.
- In Lean, automaton states are represented as elements of Fin n, so proving two states equal reduces via ext to proving equality of their underlying natural number indices.
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.
lemma pell_nfa_has_singleton_sccs_evalFrom_le (n : ℕ) (w : List (Fin 5)) {p q : Fin n} (h : q ∈ (pell_nfa n).evalFrom {p} w) : p.val ≤ q.val := by induction w generalizing p with | nil => simp only [NFA.evalFrom_nil, Set.mem_singleton_iff] at h subst h rfl | cons a w' ih => simp only [NFA.evalFrom_cons, NFA.stepSet_singleton] at h rw [NFA.mem_evalFrom_iff_exists] at h rcases h with ⟨r, hr, hq⟩ have h1 : p.val ≤ r.val := by have htab := pell_nfa_step_table n hr rcases htab with ⟨-, h⟩ | ⟨-, h⟩ | ⟨-, h⟩ · rcases h with h | h <;> omega · rcases h with h | h <;> omega · rcases h with h | h <;> omega have h2 : r.val ≤ q.val := ih hq omega/-- The Pell NFA has singleton strongly connected components. -/theorem pell_nfa_has_singleton_sccs (n : ℕ) : nfa_has_singleton_sccs (pell_nfa n) := by intro p q ⟨w1, hw1⟩ ⟨w2, hw2⟩ have h1 := pell_nfa_has_singleton_sccs_evalFrom_le n w1 hw1 have h2 := pell_nfa_has_singleton_sccs_evalFrom_le n w2 hw2 ext omega