pell_prefix_base_count
theoremverified
The prefix c_1c_2 has 1 run from q_1 to q_2, 2 runs from q_1 to q_3, 1 run from q_1 to q_4, and no runs to any other state, in A_n.
Statement
open Classical in theorem pell_prefix_base_count (n : ℕ) (hn : 3 ≤ n) (s : Fin n) : nfa_run_count_list (pell_nfa n) (pell_word_prefix 1) ⟨0, by omega⟩ s = (if s.val = 1 then 1 else 0) + (if s.val = 2 then 2 else 0) + (if s.val = 3 then 1 else 0)
- Source
- step towards pell_nfa_run_count_lower_bound
- Verified
- 29 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 6
- 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…
- nfa_run_count_list_nilThere is exactly one empty run from p to q if p = q and none otherwise.
- 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…
- 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…
- 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 proof expands the prefix c_1c_2, uses the count after c_1, and evaluates transitions on c_2.
Prefix count is as claimed
By expanding the prefix and using the lemmas.
theorem pell_prefix_base_count (n : ℕ) (hn : 3 ≤ n) (s : Fin n) : nfa_run_count_list (pell_nfa n) (pell_word_prefix 1) ⟨0, by omega⟩ s = (if s.val = 1 then 1 else 0) + (if s.val = 2 then 2 else 0) + (if s.val = 3 then 1 else 0) := by have hp : pell_word_prefix 1 = ([] ++ [⟨1, by decide⟩]) ++ [⟨2, by decide⟩] := rfl rw [hp, nfa_run_count_list_concat] simp_rw [pell_prefix_base_count_count_c1 n hn] let f : Fin n → ℕ := fun s1 => if s ∈ (pell_nfa n).step s1 ⟨2, by decide⟩ then (if s1.val = 0 ∨ s1.val = 2 then 1 else 0) else 0 change (∑ s1 : Fin n, f s1) = _ rw [pell_prefix_base_count_sum_two_fin n hn f] · have h0 := pell_prefix_base_count_step_q0_c2 n hn s have h2 := pell_prefix_base_count_step_q2_c2 n hn s dsimp [f] split_ifs <;> (try tauto) <;> (try omega) · intro x h0 h2 dsimp [f] split_ifs with h1 h3 · cases h3 <;> contradiction · rfl · rfl
- Unresolved check: no step explains line(s) 2, 4, 5, 6, 7, 8, 9, 14, 15, 16, 17, 18, 19, 20, 21, 22, 26, 27, 28, 29 -- every tactic of the proof has to belong to some step
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.
lemma pell_prefix_base_count_count_c1 (n : ℕ) (hn : 3 ≤ n) (s1 : Fin n) : nfa_run_count_list (pell_nfa n) ([] ++ [⟨1, by decide⟩]) ⟨0, by omega⟩ s1 = if s1.val = 0 ∨ s1.val = 2 then 1 else 0 := by rw [nfa_run_count_list_concat] simp_rw [nfa_run_count_list_nil] rw [Finset.sum_eq_single (⟨0, by omega⟩ : Fin n)] · have h_iff : s1 ∈ (pell_nfa n).step ⟨0, by omega⟩ ⟨1, by decide⟩ ↔ s1.val = 0 ∨ s1.val = 2 := by rw [pell_step_iff n hn] change (1 = 0 % 5 ∧ 1 ≤ 0 ∧ 0 + 2 ≤ n ∧ (s1.val = 0 ∨ s1.val = 0 + 1)) ∨ (1 = 0 % 5 ∧ 0 + 1 = n ∧ s1.val = 0) ∨ (1 = (0 + 1) % 5 ∧ 0 + 3 ≤ n ∧ (s1.val = 0 ∨ s1.val = 0 + 2)) ∨ (1 = (0 + 1) % 5 ∧ 0 + 2 = n ∧ s1.val = 0) ∨ (1 = (0 + 2) % 5 ∧ 0 + 3 ≤ n ∧ (s1.val = 0 + 1 ∨ s1.val = 0 + 2)) ↔ s1.val = 0 ∨ s1.val = 2 omega split_ifs <;> aesop · intro b _ hb split_ifs with h1 h2 · subst h2; contradiction · rfl · rfl · intro h exact False.elim (h (Finset.mem_univ _))lemma pell_prefix_base_count_sum_two_fin (n : ℕ) (hn : 3 ≤ n) (f : Fin n → ℕ) (h_zero : ∀ x : Fin n, x.val ≠ 0 → x.val ≠ 2 → f x = 0) : (∑ x : Fin n, f x) = f ⟨0, by omega⟩ + f ⟨2, by omega⟩ := by let q0 : Fin n := ⟨0, by omega⟩ let q2 : Fin n := ⟨2, by omega⟩ have hne : q0 ≠ q2 := by intro h have h2 : q0.val = q2.val := congrArg Fin.val h change 0 = 2 at h2 contradiction have hsub : ({q0, q2} : Finset (Fin n)) ⊆ Finset.univ := Finset.subset_univ _ have heq : (∑ x : Fin n, f x) = ∑ x ∈ ({q0, q2} : Finset (Fin n)), f x := by apply (Finset.sum_subset hsub _).symm intro x _ hx apply h_zero · intro h0 apply hx simp only [Finset.mem_insert, Finset.mem_singleton] left ext exact h0 · intro h2 apply hx simp only [Finset.mem_insert, Finset.mem_singleton] right ext exact h2 rw [heq, Finset.sum_pair hne]lemma pell_prefix_base_count_step_q0_c2 (n : ℕ) (hn : 3 ≤ n) (s : Fin n) : s ∈ (pell_nfa n).step ⟨0, by omega⟩ ⟨2, by decide⟩ ↔ s.val = 1 ∨ s.val = 2 := by rw [pell_step_iff n hn] change (2 = 0 % 5 ∧ 1 ≤ 0 ∧ 0 + 2 ≤ n ∧ (s.val = 0 ∨ s.val = 0 + 1)) ∨ (2 = 0 % 5 ∧ 0 + 1 = n ∧ s.val = 0) ∨ (2 = (0 + 1) % 5 ∧ 0 + 3 ≤ n ∧ (s.val = 0 ∨ s.val = 0 + 2)) ∨ (2 = (0 + 1) % 5 ∧ 0 + 2 = n ∧ s.val = 0) ∨ (2 = (0 + 2) % 5 ∧ 0 + 3 ≤ n ∧ (s.val = 0 + 1 ∨ s.val = 0 + 2)) ↔ s.val = 1 ∨ s.val = 2 omegalemma pell_prefix_base_count_step_q2_c2 (n : ℕ) (hn : 3 ≤ n) (s : Fin n) : s ∈ (pell_nfa n).step ⟨2, by omega⟩ ⟨2, by decide⟩ ↔ s.val = 2 ∨ s.val = 3 := by rw [pell_step_iff n hn] change (2 = 2 % 5 ∧ 1 ≤ 2 ∧ 2 + 2 ≤ n ∧ (s.val = 2 ∨ s.val = 2 + 1)) ∨ (2 = 2 % 5 ∧ 2 + 1 = n ∧ s.val = 2) ∨ (2 = (2 + 1) % 5 ∧ 2 + 3 ≤ n ∧ (s.val = 2 ∨ s.val = 2 + 2)) ∨ (2 = (2 + 1) % 5 ∧ 2 + 2 = n ∧ s.val = 2) ∨ (2 = (2 + 2) % 5 ∧ 2 + 3 ≤ n ∧ (s.val = 2 + 1 ∨ s.val = 2 + 2)) ↔ s.val = 2 ∨ s.val = 3 have : s.val < n := s.isLt omegaopen Classical in/-- After the first block the count vector of the prefix v_1 = c_1c_2 has exactly 1 run at state q_2, 2 runs at q_3 and 1 run at q_4, and nothing elsewhere. -/theorem pell_prefix_base_count (n : ℕ) (hn : 3 ≤ n) (s : Fin n) : nfa_run_count_list (pell_nfa n) (pell_word_prefix 1) ⟨0, by omega⟩ s = (if s.val = 1 then 1 else 0) + (if s.val = 2 then 2 else 0) + (if s.val = 3 then 1 else 0) := by have hp : pell_word_prefix 1 = ([] ++ [⟨1, by decide⟩]) ++ [⟨2, by decide⟩] := rfl rw [hp, nfa_run_count_list_concat] simp_rw [pell_prefix_base_count_count_c1 n hn] let f : Fin n → ℕ := fun s1 => if s ∈ (pell_nfa n).step s1 ⟨2, by decide⟩ then (if s1.val = 0 ∨ s1.val = 2 then 1 else 0) else 0 change (∑ s1 : Fin n, f s1) = _ rw [pell_prefix_base_count_sum_two_fin n hn f] · have h0 := pell_prefix_base_count_step_q0_c2 n hn s have h2 := pell_prefix_base_count_step_q2_c2 n hn s dsimp [f] split_ifs <;> (try tauto) <;> (try omega) · intro x h0 h2 dsimp [f] split_ifs with h1 h3 · cases h3 <;> contradiction · rfl · rfl