AFTD Auto-Formalizing Theoretical Domains

pell_nfa_has_singleton_sccs

theoremverified

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.

  1. 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.

    lines 3–7

    uses NFA.evalFrom_nil, Set.mem_singleton_iff

      induction w generalizing p with
      | nil =>
        simp only [NFA.evalFrom_nil, Set.mem_singleton_iff] at h
        subst h
        rfl
  2. 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'.

    lines 8–11

    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⟩
  3. 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.

    lines 12–17

    uses pell_nfa_step_table

        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
  4. 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.

    lines 18–19

        have h2 : r.val ≤ q.val := ih hq
        omega
  5. 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.

    lines 23–25

    uses pell_nfa_has_singleton_sccs_evalFrom_le

      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
  6. 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.

    lines 26–27

      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.

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

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
See it in the graphDiscuss this resultChallenge it