pell_run_encard_eq_count
The set of accepting runs of u_n in A_n has encard equal to the number of runs from q_1 to q_n.
Statement
open Classical in theorem pell_run_encard_eq_count (n : ℕ) (hn : 3 ≤ n) : Set.encard {r : Fin ((pell_word n).length + 1) → Fin n | r 0 ∈ (pell_nfa n).start ∧ r (Fin.last (pell_word n).length) ∈ (pell_nfa n).accept ∧ ∀ i : Fin (pell_word n).length, r i.succ ∈ (pell_nfa n).step (r i.castSucc) ((pell_word n).get i)} = (nfa_run_count_list (pell_nfa n) (pell_word n) ⟨0, by omega⟩ ⟨n - 1, by omega⟩ : ℕ∞)
- Source
- step towards pell_nfa_run_count_lower_bound
- Verified
- 19 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- nfa_run_count_listThe number of runs of the word w in the NFA M from state p to state q: state sequences of length |w|+1 that start at p, end at q and…
- pell_wordThe word u_n = c_1 c_2 c_2 c_3 c_3 c_4 ⋯ c_(n-2) c_(n-1), i.e. the concatenation, over 1 ≤ i ≤ n-2, of the two-letter block c_i c_(i+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…
The proof, explained
The theorem shows that the extended cardinality of accepting runs of the Pell word in the Pell automaton equals the run count from state 0 to state n - 1. The proof first characterizes the set of accepting runs as the set of runs starting at state 0 and ending at state n - 1, since the automaton's start and accept sets are singletons containing 0 and n - 1, respectively. Finally, rewriting along this set equality and unfolding the definition of the run count expresses both sides as the cardinality of the underlying finite set of runs in ℕ∞.
The initial state 0 and target state n - 1 are well-defined elements of Fin n.
The theorem statement uses the states ⟨0, ·⟩ and ⟨n - 1, ·⟩ in Fin n. Under the assumption 3 ≤ n, linear arithmetic (`omega`) verifies 0 < n and n - 1 < n, ensuring both state expressions are well-typed.
= (nfa_run_count_list (pell_nfa n) (pell_word n) ⟨0, by omega⟩ ⟨n - 1, by omega⟩ : ℕ∞) := by
The set of accepting runs of pell_word n in pell_nfa n is identical to the set of runs from state 0 to state n - 1.
We establish the auxiliary equality `hset` by set extensionality (`ext r`). Unfolding the definition of `pell_nfa`, a run is accepting if its initial state has value 0 and its final state has value satisfying `q.val + 1 = n`. Since states belong to `Fin n`, equality of elements is equivalent to equality of their values via `Fin.ext_iff`. For any accepting run, the initial state must be ⟨0, ·⟩ and, since `q.val + 1 = n`, the final state must be ⟨n - 1, ·⟩ by linear arithmetic. Conversely, any run starting at ⟨0, ·⟩ and ending at ⟨n - 1, ·⟩ satisfies the start condition (0 = 0) and the accept condition ((n - 1) + 1 = n). The step conditions are identical on both sides.
uses
pell_nfa,Set.mem_setOf_eq,Fin.ext_iff,Fin.val_mkhave hset : {r : Fin ((pell_word n).length + 1) → Fin n | r 0 ∈ (pell_nfa n).start ∧ r (Fin.last (pell_word n).length) ∈ (pell_nfa n).accept ∧ ∀ i : Fin (pell_word n).length, r i.succ ∈ (pell_nfa n).step (r i.castSucc) ((pell_word n).get i)} = {r : Fin ((pell_word n).length + 1) → Fin n | r 0 = ⟨0, by omega⟩ ∧ r (Fin.last (pell_word n).length) = ⟨n - 1, by omega⟩ ∧ ∀ i : Fin (pell_word n).length, r i.succ ∈ (pell_nfa n).step (r i.castSucc) ((pell_word n).get i)} := by ext r simp only [pell_nfa, Set.mem_setOf_eq] constructor · rintro ⟨h1, h2, h3⟩ refine ⟨?_, ?_, h3⟩ · rw [Fin.ext_iff]; exact h1 · rw [Fin.ext_iff]; simp only [Fin.val_mk]; omega · rintro ⟨h1, h2, h3⟩ refine ⟨?_, ?_, h3⟩ · rw [h1] · rw [h2]; simp only [Fin.val_mk]; omega
The extended cardinality of the set of accepting runs equals the run count from state 0 to state n - 1 in ℕ∞.
Rewriting with the set equality `hset`, the accepting runs are replaced by runs from 0 to n - 1. By `Set.encard_eq_coe_toFinset_card`, the extended cardinality of this finite set of runs is represented as the coercion of its finset cardinality. Unfolding `nfa_run_count_list`, the right-hand side is defined as the natural cardinality (`ncard`) of the same set of runs, which by `Set.ncard_eq_toFinset_card'` also equals the coercion of its finset cardinality. Both sides are identical, concluding the proof.
uses
Set.encard_eq_coe_toFinset_card,nfa_run_count_list,Set.ncard_eq_toFinset_card'rw [hset] rw [Set.encard_eq_coe_toFinset_card] unfold nfa_run_count_list rw [Set.ncard_eq_toFinset_card']
pell_nfa- The non-deterministic finite automaton for the Pell language on states `Fin n`, with start states satisfying `p.val = 0` and accept states satisfying `q.val + 1 = n`.
Set.mem_setOf_eq- An element `x` belongs to the set `{y | p y}` if and only if the predicate `p x` holds.
Fin.ext_iff- Two elements of `Fin n` are equal if and only if their underlying natural values are equal.
Fin.val_mk- For `m < n`, the value of the `Fin n` element `⟨m, h⟩` as a natural number is `m`.
Set.encard_eq_coe_toFinset_card- For a finite set `s`, its extended cardinality in `ℕ∞` equals the coercion of the cardinality of its associated `Finset`.
nfa_run_count_list- The number of runs of automaton `M` on word `w` from state `p` to state `q`, defined as the cardinality (`ncard`) of the set of valid runs.
Set.ncard_eq_toFinset_card'- For a finite set `s`, its natural number cardinality `ncard` equals the cardinality of its associated `Finset`.
- In Lean, states are typed as elements of `Fin n` (natural numbers strictly less than `n`), which requires explicit proofs that `0 < n` and `n - 1 < n` to construct the states `⟨0, ·⟩` and `⟨n - 1, ·⟩`.
- Lean distinguishes between extended cardinality `encard` (taking values in `ℕ∞ = WithTop ℕ`) and finite cardinality `ncard` (in `ℕ`). The equality between them is reconciled by converting both to the cardinality of the underlying finite set (`toFinset.card`).
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.
open Classical in/-- The set of accepting runs of u_n in A_n has the same cardinality as the run count from q_1 to q_n. -/theorem pell_run_encard_eq_count (n : ℕ) (hn : 3 ≤ n) : Set.encard {r : Fin ((pell_word n).length + 1) → Fin n | r 0 ∈ (pell_nfa n).start ∧ r (Fin.last (pell_word n).length) ∈ (pell_nfa n).accept ∧ ∀ i : Fin (pell_word n).length, r i.succ ∈ (pell_nfa n).step (r i.castSucc) ((pell_word n).get i)} = (nfa_run_count_list (pell_nfa n) (pell_word n) ⟨0, by omega⟩ ⟨n - 1, by omega⟩ : ℕ∞) := by have hset : {r : Fin ((pell_word n).length + 1) → Fin n | r 0 ∈ (pell_nfa n).start ∧ r (Fin.last (pell_word n).length) ∈ (pell_nfa n).accept ∧ ∀ i : Fin (pell_word n).length, r i.succ ∈ (pell_nfa n).step (r i.castSucc) ((pell_word n).get i)} = {r : Fin ((pell_word n).length + 1) → Fin n | r 0 = ⟨0, by omega⟩ ∧ r (Fin.last (pell_word n).length) = ⟨n - 1, by omega⟩ ∧ ∀ i : Fin (pell_word n).length, r i.succ ∈ (pell_nfa n).step (r i.castSucc) ((pell_word n).get i)} := by ext r simp only [pell_nfa, Set.mem_setOf_eq] constructor · rintro ⟨h1, h2, h3⟩ refine ⟨?_, ?_, h3⟩ · rw [Fin.ext_iff]; exact h1 · rw [Fin.ext_iff]; simp only [Fin.val_mk]; omega · rintro ⟨h1, h2, h3⟩ refine ⟨?_, ?_, h3⟩ · rw [h1] · rw [h2]; simp only [Fin.val_mk]; omega rw [hset] rw [Set.encard_eq_coe_toFinset_card] unfold nfa_run_count_list rw [Set.ncard_eq_toFinset_card']