pell_prefix_first_letter_vector
After appending only the letter c_(i+1) to the prefix, the run counts are P(i+1)-P(i) at q_i, 2P(i) at q_(i+1), (P(i+1)-P(i))+2P(i) at q_(i+2), and vanish at every other state.
Statement
open Classical in theorem pell_prefix_first_letter_vector (n i : ℕ) (hn : 3 ≤ n) (h1 : 1 ≤ i) (hi : i + 1 ≤ n - 2) (hzero : ∀ s : Fin n, s.val ≠ i → s.val ≠ i + 1 → s.val ≠ i + 2 → nfa_run_count_list (pell_nfa n) (pell_word_prefix i) ⟨0, by omega⟩ s = 0) (hx : nfa_run_count_list (pell_nfa n) (pell_word_prefix i) ⟨0, by omega⟩ ⟨i, by omega⟩ = pell_number (i + 1) - pell_number i) (hy : nfa_run_count_list (pell_nfa n) (pell_word_prefix i) ⟨0, by omega⟩ ⟨i + 1, by omega⟩ = 2 * pell_number i) (s : Fin n) : nfa_run_count_list (pell_nfa n) (pell_word_prefix i ++ [⟨(i + 1) % 5, by omega⟩]) ⟨0, by omega⟩ s = (if s.val = i then (pell_number (i + 1) - pell_number i) else 0) + (if s.val = i + 1 then (2 * pell_number i) else 0) + (if s.val = i + 2 then ((pell_number (i + 1) - pell_number i) + 2 * pell_number i) else 0)
- Source
- step towards pell_prefix_block_step
- Verified
- 20 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 7
- nfa_run_count_list_concatNumber of runs on w++[a] from p to q equals the sum over s of the number of runs on w from p to s, taken over the predecessors s of q on…
- pell_step_iffClosed form of the transitions of A_n: q is reachable from p in one step on letter k iff one of five explicit arithmetic conditions holds…
- finset_sum_eq_three_of_offA finite sum of an ℕ-valued function that vanishes off three distinct points equals the sum of the three values f a + f b + f c.
- pell_word_prefixThe prefix v_j of u_n consisting of its first j two-letter blocks, v_j = c_1c_2 c_2c_3 … c_jc_(j+1), built by appending one block at a…
- 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_numberThe Pell numbers are defined by P(0) = 0, P(1) = 1, and P(m+2) = P(m) + 2 P(m+1).
- 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…
The proof, explained
The theorem calculates the run counts of the Pell NFA after appending the letter $c_{i+1} = (i+1) \pmod 5$ to the prefix of length $2i$. By the dynamic programming step for NFA run counts (`nfa_run_count_list_concat`), the count at any state $s$ is the sum over all predecessor states $t$ of the prefix count at $t$ whenever a transition from $t$ to $s$ on $c_{i+1}$ is possible. Transitions from state $i$ reach $\{i, i+2\}$, transitions from state $i+1$ reach $\{i+1, i+2\}$, and state $i+2$ has no valid transitions on this letter. Because prefix counts vanish off $\{i, i+1, i+2\}$, the sum reduces to these three states, matching the claimed values at $i$, $i+1$, and $i+2$.
The state indices $0$, $i$, $i+1$ and the letter $(i+1) \pmod 5$ appearing in the statement are well-defined elements of $\mathrm{Fin}\ n$ and $\mathrm{Fin}\ 5$.
The hypotheses $3 \le n$, $1 \le i$, and $i+1 \le n-2$ imply the range inequalities $0 < n$, $i < n$, $i+1 < n$, and $(i+1) \pmod 5 < 5$, each verified inline in the type signatures by linear arithmetic (`omega`).
nfa_run_count_list (pell_nfa n) (pell_word_prefix i) ⟨0, by omega⟩ s = 0) (hx : nfa_run_count_list (pell_nfa n) (pell_word_prefix i) ⟨0, by omega⟩ ⟨i, by omega⟩ = pell_number (i + 1) - pell_number i) (hy : nfa_run_count_list (pell_nfa n) (pell_word_prefix i) ⟨0, by omega⟩ ⟨i + 1, by omega⟩ = 2 * pell_number i) (s : Fin n) : nfa_run_count_list (pell_nfa n) (pell_word_prefix i ++ [⟨(i + 1) % 5, by omega⟩]) ⟨0, by omega⟩ s = (if s.val = i then (pell_number (i + 1) - pell_number i) else 0) + (if s.val = i + 1 then (2 * pell_number i) else 0) + (if s.val = i + 2 then ((pell_number (i + 1) - pell_number i) + 2 * pell_number i) else 0) := by
State $s$ is reachable from state $i$ on reading letter $(i+1) \pmod 5$ if and only if $s = i$ or $s = i+2$.
Rewriting with `pell_step_iff` expands the transition relation into five possible clauses. Four of these require the letter modulo 5 to be $i \pmod 5$ or $(i+2) \pmod 5$, which contradicts $(i+1) \pmod 5$ by modular arithmetic (`omega`). Only the third clause is compatible, which requires $s = i$ or $s = i+2$.
uses
pell_step_iffhave h_step_i : s ∈ (pell_nfa n).step ⟨i, by omega⟩ ⟨(i + 1) % 5, by omega⟩ ↔ (s.val = i ∨ s.val = i + 2) := by have h := @pell_step_iff n hn ⟨i, by omega⟩ s ⟨(i + 1) % 5, by omega⟩ dsimp at h rw [h] constructor · rintro (⟨hmod, -⟩ | ⟨hmod, -⟩ | ⟨-, -, hq⟩ | ⟨-, h2, -⟩ | ⟨hmod, -⟩) · exfalso; omega · exfalso; omega · exact hq · exfalso; omega · exfalso; omega · intro hq right; right; left refine ⟨rfl, by omega, hq⟩
State $s$ is reachable from state $i+1$ on reading letter $(i+1) \pmod 5$ if and only if $s = i+1$ or $s = i+2$.
Applying `pell_step_iff` to state $i+1$ with letter $(i+1) \pmod 5$, modular arithmetic rules out all cases except the first clause, which allows transitions to $i+1$ and $(i+1)+1 = i+2$.
uses
pell_step_iffhave h_step_ip1 : s ∈ (pell_nfa n).step ⟨i + 1, by omega⟩ ⟨(i + 1) % 5, by omega⟩ ↔ (s.val = i + 1 ∨ s.val = i + 2) := by have h := @pell_step_iff n hn ⟨i + 1, by omega⟩ s ⟨(i + 1) % 5, by omega⟩ dsimp at h rw [h] constructor · rintro (⟨-, -, -, hq⟩ | ⟨-, h2, -⟩ | ⟨hmod, -⟩ | ⟨hmod, -⟩ | ⟨hmod, -⟩) · exact hq · exfalso; omega · exfalso; omega · exfalso; omega · exfalso; omega · intro hq left refine ⟨rfl, by omega, by omega, hq⟩
No transition is possible from state $i+2$ on reading letter $(i+1) \pmod 5$.
Applying `pell_step_iff` to state $i+2$, every clause requires the input letter modulo 5 to be $(i+2) \pmod 5$, $(i+3) \pmod 5$, or $(i+4) \pmod 5$. Since the letter is $(i+1) \pmod 5$, linear integer arithmetic (`omega`) derives a contradiction in all five cases.
uses
pell_step_iffhave h_step_ip2 : s ∉ (pell_nfa n).step ⟨i + 2, by omega⟩ ⟨(i + 1) % 5, by omega⟩ := by have h := @pell_step_iff n hn ⟨i + 2, by omega⟩ s ⟨(i + 1) % 5, by omega⟩ dsimp at h rw [h] rintro (⟨hmod, -⟩ | ⟨hmod, -⟩ | ⟨hmod, -⟩ | ⟨hmod, -⟩ | ⟨hmod, -⟩) <;> (exfalso; omega)
The run count to state $s$ after appending the letter equals $\sum_{t : \mathrm{Fin}\ n} g(t)$, where $g(t)$ is the prefix run count to $t$ if $t$ can step to $s$, and 0 otherwise.
Applying `nfa_run_count_list_concat` expresses the run count for the extended prefix as a sum over all predecessor states $t$ of the prefix run count to $t$ when $t$ can transition to $s$ on the appended letter, and 0 otherwise. Defining $g(t)$ as this summand rephrases the goal as $\sum_t g(t) = \dots$.
uses
nfa_run_count_list_concatrw [nfa_run_count_list_concat] let g : Fin n → ℕ := fun t => if s ∈ (pell_nfa n).step t ⟨(i + 1) % 5, by omega⟩ then nfa_run_count_list (pell_nfa n) (pell_word_prefix i) ⟨0, by omega⟩ t else 0 change (∑ t : Fin n, g t) = _
The states $i$, $i+1$, and $i+2$ in $\mathrm{Fin}\ n$ are pairwise distinct.
Because their underlying numerical values $i$, $i+1$, and $i+2$ are strictly increasing, injecting into $\mathbb{N}$ shows they cannot be equal.
have hab : (⟨i, by omega⟩ : Fin n) ≠ ⟨i + 1, by omega⟩ := by intro h; injection h with h; omega have hac : (⟨i, by omega⟩ : Fin n) ≠ ⟨i + 2, by omega⟩ := by intro h; injection h with h; omega have hbc : (⟨i + 1, by omega⟩ : Fin n) ≠ ⟨i + 2, by omega⟩ := by intro h; injection h with h; omega
The sum $g(i) + g(i+1) + g(i+2)$ evaluates to the expected run counts for every state $s$.
Rewriting with `finset_sum_eq_three_of_off` reduces the sum over all states to $g(i) + g(i+1) + g(i+2)$. Substituting the prefix counts $hx$ and $hy$ at states $i$ and $i+1$, replacing the step conditions using `if_congr` with `h_step_i` and `h_step_ip1`, and simplifying the impossible transition from $i+2$ using `if_neg` leaves an expression in terms of conditionals on $s = i$, $s = i+1$, and $s = i+2$. A case split on these conditions (`split_ifs`) followed by linear arithmetic (`omega`) matches the claimed formula in every branch.
uses
finset_sum_eq_three_of_off,if_congr,if_negrw [finset_sum_eq_three_of_off g hab hac hbc] · dsimp [g] rw [hx, hy] rw [if_congr h_step_i rfl rfl] rw [if_congr h_step_ip1 rfl rfl] rw [if_neg h_step_ip2] split_ifs <;> omega
The function $g(t)$ vanishes for all states $t$ distinct from $i$, $i+1$, and $i+2$.
For any state $t \notin \{i, i+1, i+2\}$, the hypothesis `hzero` implies that the prefix run count to $t$ is 0. Since $g(t)$ is either that run count or 0, it reduces to 0 in both branches.
· intro t hti htip1 htip2 dsimp [g] have hzt : nfa_run_count_list (pell_nfa n) (pell_word_prefix i) ⟨0, by omega⟩ t = 0 := by apply hzero t · intro h; apply hti; ext; exact h · intro h; apply htip1; ext; exact h · intro h; apply htip2; ext; exact h rw [hzt] split_ifs <;> rfl
pell_step_iff- Characterizes the transition relation of `pell_nfa n` from state $p$ on symbol $k$ as a disjunction of five possible conditions on $p$ and $k \pmod 5$.
nfa_run_count_list_concat- The number of runs of an NFA on a word extended by a single letter $a$ from $p$ to $q$ equals the sum over all intermediate states $s$ of the runs on $w$ to $s$ that can transition to $q$ on $a$.
finset_sum_eq_three_of_off- If a function on a finite type vanishes outside three pairwise distinct elements $a, b, c$, its sum over the entire type equals $f(a) + f(b) + f(c)$.
if_congr- An if-then-else expression is unchanged when replacing the condition by an equivalent proposition and the branches by equal values.
if_neg- If the condition of an if-then-else expression is false, the expression simplifies to the else-branch.
- The theorem statement contains inline proofs `by omega` (lines 5–11) to certify that the state indices $0$, $i$, and $i+1$ are strictly less than $n$ and that $(i+1) \pmod 5 < 5$.
- The analysis of the possible transitions from states $i$, $i+1$, and $i+2$ relies on ruling out incompatible congruence classes modulo 5 via linear and modular arithmetic handled by `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
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/-- One-letter DP step: appending the single letter c_(i+1) to `pell_word_prefix i` maps the vector (x at q_i, y at q_(i+1)), vanishing off q_i,q_(i+1),q_(i+2), to (x at q_i, y at q_(i+1), x+y at q_(i+2)), zero everywhere else. -/theorem pell_prefix_first_letter_vector (n i : ℕ) (hn : 3 ≤ n) (h1 : 1 ≤ i) (hi : i + 1 ≤ n - 2) (hzero : ∀ s : Fin n, s.val ≠ i → s.val ≠ i + 1 → s.val ≠ i + 2 → nfa_run_count_list (pell_nfa n) (pell_word_prefix i) ⟨0, by omega⟩ s = 0) (hx : nfa_run_count_list (pell_nfa n) (pell_word_prefix i) ⟨0, by omega⟩ ⟨i, by omega⟩ = pell_number (i + 1) - pell_number i) (hy : nfa_run_count_list (pell_nfa n) (pell_word_prefix i) ⟨0, by omega⟩ ⟨i + 1, by omega⟩ = 2 * pell_number i) (s : Fin n) : nfa_run_count_list (pell_nfa n) (pell_word_prefix i ++ [⟨(i + 1) % 5, by omega⟩]) ⟨0, by omega⟩ s = (if s.val = i then (pell_number (i + 1) - pell_number i) else 0) + (if s.val = i + 1 then (2 * pell_number i) else 0) + (if s.val = i + 2 then ((pell_number (i + 1) - pell_number i) + 2 * pell_number i) else 0) := by have h_step_i : s ∈ (pell_nfa n).step ⟨i, by omega⟩ ⟨(i + 1) % 5, by omega⟩ ↔ (s.val = i ∨ s.val = i + 2) := by have h := @pell_step_iff n hn ⟨i, by omega⟩ s ⟨(i + 1) % 5, by omega⟩ dsimp at h rw [h] constructor · rintro (⟨hmod, -⟩ | ⟨hmod, -⟩ | ⟨-, -, hq⟩ | ⟨-, h2, -⟩ | ⟨hmod, -⟩) · exfalso; omega · exfalso; omega · exact hq · exfalso; omega · exfalso; omega · intro hq right; right; left refine ⟨rfl, by omega, hq⟩ have h_step_ip1 : s ∈ (pell_nfa n).step ⟨i + 1, by omega⟩ ⟨(i + 1) % 5, by omega⟩ ↔ (s.val = i + 1 ∨ s.val = i + 2) := by have h := @pell_step_iff n hn ⟨i + 1, by omega⟩ s ⟨(i + 1) % 5, by omega⟩ dsimp at h rw [h] constructor · rintro (⟨-, -, -, hq⟩ | ⟨-, h2, -⟩ | ⟨hmod, -⟩ | ⟨hmod, -⟩ | ⟨hmod, -⟩) · exact hq · exfalso; omega · exfalso; omega · exfalso; omega · exfalso; omega · intro hq left refine ⟨rfl, by omega, by omega, hq⟩ have h_step_ip2 : s ∉ (pell_nfa n).step ⟨i + 2, by omega⟩ ⟨(i + 1) % 5, by omega⟩ := by have h := @pell_step_iff n hn ⟨i + 2, by omega⟩ s ⟨(i + 1) % 5, by omega⟩ dsimp at h rw [h] rintro (⟨hmod, -⟩ | ⟨hmod, -⟩ | ⟨hmod, -⟩ | ⟨hmod, -⟩ | ⟨hmod, -⟩) <;> (exfalso; omega) rw [nfa_run_count_list_concat] let g : Fin n → ℕ := fun t => if s ∈ (pell_nfa n).step t ⟨(i + 1) % 5, by omega⟩ then nfa_run_count_list (pell_nfa n) (pell_word_prefix i) ⟨0, by omega⟩ t else 0 change (∑ t : Fin n, g t) = _ have hab : (⟨i, by omega⟩ : Fin n) ≠ ⟨i + 1, by omega⟩ := by intro h; injection h with h; omega have hac : (⟨i, by omega⟩ : Fin n) ≠ ⟨i + 2, by omega⟩ := by intro h; injection h with h; omega have hbc : (⟨i + 1, by omega⟩ : Fin n) ≠ ⟨i + 2, by omega⟩ := by intro h; injection h with h; omega rw [finset_sum_eq_three_of_off g hab hac hbc] · dsimp [g] rw [hx, hy] rw [if_congr h_step_i rfl rfl] rw [if_congr h_step_ip1 rfl rfl] rw [if_neg h_step_ip2] split_ifs <;> omega · intro t hti htip1 htip2 dsimp [g] have hzt : nfa_run_count_list (pell_nfa n) (pell_word_prefix i) ⟨0, by omega⟩ t = 0 := by apply hzero t · intro h; apply hti; ext; exact h · intro h; apply htip1; ext; exact h · intro h; apply htip2; ext; exact h rw [hzt] split_ifs <;> rfl