AFTD Auto-Formalizing Theoretical Domains

pell_prefix_first_letter_vector

theoremverified

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

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

    lines 5–14

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

    lines 15–28

    uses pell_step_iff

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

    lines 29–42

    uses pell_step_iff

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

    lines 43–48

    uses pell_step_iff

      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)
    
  5. 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$.

    lines 49–53

    uses nfa_run_count_list_concat

      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) = _
  6. 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.

    lines 54–56

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

    lines 57–63

    uses finset_sum_eq_three_of_off, if_congr, if_neg

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

    lines 64–72

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

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

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