AFTD Auto-Formalizing Theoretical Domains

pell_nfa_step_table

theoremverified

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.

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

    lines 7–8

      simp only [pell_nfa] at h
      obtain ⟨i, hi1, hi2, h⟩ := h
  2. 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`.

    lines 9–15

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

    lines 16–23

      · 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

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