pell_step_iff
Closed 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 (letter k congruent to p, p+1 or p+2 mod 5, with the state bounds of the gadget and the two boundary cases where the top of the chain is reached).
Statement
theorem pell_step_iff (n : ℕ) (hn : 3 ≤ n) {p q : Fin n} {k : Fin 5} :
q ∈ (pell_nfa n).step p k ↔
(k.val = p.val % 5 ∧ 1 ≤ p.val ∧ p.val + 2 ≤ n ∧ (q.val = p.val ∨ q.val = p.val + 1)) ∨
(k.val = p.val % 5 ∧ p.val + 1 = n ∧ q.val = p.val) ∨
(k.val = (p.val + 1) % 5 ∧ p.val + 3 ≤ n ∧ (q.val = p.val ∨ q.val = p.val + 2)) ∨
(k.val = (p.val + 1) % 5 ∧ p.val + 2 = n ∧ q.val = p.val) ∨
(k.val = (p.val + 2) % 5 ∧ p.val + 3 ≤ n ∧ (q.val = p.val + 1 ∨ q.val = p.val + 2))- Source
- step towards pell_nfa_run_count_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 2
- pell_prefix_first_letter_vectorAfter 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…
- pell_prefix_base_countThe 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.
The proof, explained
The proof establishes the logical equivalence by demonstrating both directions separately. For the forward direction (⇒), it unfolds the definition of `pell_nfa`, extracts the existential gadget index `i`, and analyzes the resulting cases on `p`, `q`, and `k`, distinguishing the internal transitions from the top-boundary transitions where `p + 1 = n` or `p + 2 = n`. For the backward direction (⇐), it inspects each of the five disjunctive arithmetic conditions and provides an explicit gadget index witness—either `i = p`, `i = p + 1`, or `i = n - 2`—verifying in each case that the transition relation's range constraints and congruences are satisfied via linear integer arithmetic (`omega`).
In the forward direction, assuming `q` is reachable from `p` on letter `k` yields a gadget index `i` with `1 ≤ i ≤ n - 2`, reducing the goal to the two cases `k ≡ i mod 5` and `k ≡ i + 1 mod 5`.
We split the bi-implication into forward and backward directions with `constructor`. For the forward direction, assuming `q ∈ step p k`, we unfold the definition of `pell_nfa` to extract a gadget index `i` satisfying `1 ≤ i` and `i + 2 ≤ n`, and split into cases based on whether `k.val = i % 5` or `k.val = (i + 1) % 5`.
constructor · intro h simp only [pell_nfa] at h obtain ⟨i, hi1, hi2, h⟩ := h rcases h with ⟨hk, hpq⟩ | ⟨hk, hpq⟩
When `k ≡ i mod 5`, either condition 3 holds (if `p = i - 1`) or condition 1 holds (if `p = i`).
From the first branch of the automaton definition, either `p = i - 1` and `q ∈ {i - 1, i + 1}`, or `p = i` and `q ∈ {i, i + 1}`. In the first subcase, `k ≡ p + 1 mod 5`, `p + 3 ≤ n`, and `q ∈ {p, p + 2}`, which matches condition 3. In the second subcase, `k ≡ p mod 5`, `1 ≤ p`, `p + 2 ≤ n`, and `q ∈ {p, p + 1}`, which matches condition 1. Linear arithmetic (`omega`) verifies the bounds and equalities in each branch.
· rcases hpq with ⟨hp, hq⟩ | ⟨hp, hq⟩ · right; right; left exact ⟨by omega, by omega, by rcases hq with h | h <;> omega⟩ · left exact ⟨by omega, by omega, by omega, by rcases hq with h | h <;> omega⟩
When `k ≡ i + 1 mod 5`, depending on `p` and boundary conditions, one of the five conditions holds, completing the forward direction.
The second branch of the automaton definition gives three subcases: - If `p = i` and `q = i`, we branch on whether `p + 2 = n`. If it is, condition 4 holds (`k ≡ p + 1 mod 5`, `p + 2 = n`, `q = p`); otherwise `p + 3 ≤ n`, which satisfies condition 3. - If `p = i + 1` and `q = i + 1`, we branch on whether `p + 1 = n`. If it is, condition 2 holds (`k ≡ p mod 5`, `p + 1 = n`, `q = p`); otherwise `p + 2 ≤ n` and `1 ≤ p`, satisfying condition 1. - If `p = i - 1` and `q ∈ {i, i + 1}`, then `k ≡ p + 2 mod 5`, `p + 3 ≤ n`, and `q ∈ {p + 1, p + 2}`, satisfying condition 5. All arithmetic constraints are verified by `omega`.
· rcases hpq with ⟨hp, hq⟩ | ⟨hp, hq⟩ | ⟨hp, hq⟩ · by_cases hb : p.val + 2 = n · right; right; right; left exact ⟨by omega, by omega, by omega⟩ · right; right; left exact ⟨by omega, by omega, by omega⟩ · by_cases hb : p.val + 1 = n · right; left exact ⟨by omega, by omega, by omega⟩ · left exact ⟨by omega, by omega, by omega, by omega⟩ · right; right; right; right exact ⟨by omega, by omega, by rcases hq with h | h <;> omega⟩
In the backward direction, we assume the five-way disjunction and unpack the goal into five separate arithmetic cases.
For the converse implication, we assume one of the five explicit arithmetic conditions holds and unfold `pell_nfa`. The goal is to provide a gadget index `i` with `1 ≤ i ≤ n - 2` witnessing that `q ∈ step p k`. We split the hypothesis into its five disjunctive cases.
· intro h simp only [pell_nfa] rcases h with ⟨hk, hp1, hp2, hq⟩ | ⟨hk, hpn, hq⟩ | ⟨hk, hp3, hq⟩ | ⟨hk, hpn2, hq⟩ | ⟨hk, hp3', hq⟩
Under condition 1, setting the gadget witness `i = p` proves `q ∈ step p k`.
Condition 1 gives `1 ≤ p`, `p + 2 ≤ n`, `k ≡ p mod 5`, and `q ∈ {p, p + 1}`. Choosing `i = p` satisfies `1 ≤ i` and `i + 2 ≤ n`. We select the first branch of the automaton transition (`k ≡ i mod 5`) and its second sub-branch (`p = i` and `q ∈ {i, i + 1}`) using `Or.inr`. Linear arithmetic (`omega`) closes all side conditions.
uses
Or.inr· refine ⟨p.val, by omega, by omega, ?_⟩ left refine ⟨by omega, Or.inr ⟨by omega, ?_⟩⟩ rcases hq with h | h <;> omega
Under condition 2, setting the top gadget witness `i = n - 2` proves `q ∈ step p k`.
Condition 2 corresponds to the top-boundary state where `p + 1 = n`, `q = p`, and `k ≡ p mod 5`. Since `3 ≤ n`, setting `i = n - 2` yields `1 ≤ i` and `i + 2 ≤ n`. Then `p = i + 1` and `k ≡ i + 1 mod 5`. We select the second branch of the automaton (`k ≡ i + 1 mod 5`) and navigate to the middle sub-branch (`p = i + 1 ∧ q = i + 1`) via `Or.inr (Or.inl ...)`, with `omega` checking the arithmetic.
uses
Or.inr,Or.inl· refine ⟨n - 2, by omega, by omega, ?_⟩ right refine ⟨by omega, Or.inr (Or.inl ⟨by omega, by omega⟩)⟩
Under condition 3, setting `i = p + 1` proves `q ∈ step p k`.
Condition 3 specifies `p + 3 ≤ n`, `k ≡ p + 1 mod 5`, and `q ∈ {p, p + 2}`. Setting `i = p + 1` guarantees `1 ≤ i` and `i + 2 ≤ n`. Then `k ≡ i mod 5`, `p = i - 1`, and `q ∈ {i - 1, i + 1}`. We choose the first branch (`k ≡ i mod 5`) and select the first sub-branch using `Or.inl`, completed by `omega`.
uses
Or.inl· refine ⟨p.val + 1, by omega, by omega, ?_⟩ left refine ⟨by omega, Or.inl ⟨by omega, ?_⟩⟩ rcases hq with h | h <;> omega
Under condition 4, setting `i = p` proves `q ∈ step p k`.
Condition 4 is the boundary case where `p + 2 = n`, `q = p`, and `k ≡ p + 1 mod 5`. Since `3 ≤ n`, `p ≥ 1`. Setting `i = p` gives `1 ≤ i ≤ n - 2`, with `k ≡ i + 1 mod 5` and `p = q = i`. We select the second branch (`k ≡ i + 1 mod 5`) and its first sub-branch via `Or.inl`, closed by `omega`.
uses
Or.inl· refine ⟨p.val, by omega, by omega, ?_⟩ right refine ⟨by omega, Or.inl ⟨by omega, by omega⟩⟩
Under condition 5, setting `i = p + 1` proves `q ∈ step p k`.
Condition 5 specifies `p + 3 ≤ n`, `k ≡ p + 2 mod 5`, and `q ∈ {p + 1, p + 2}`. Choosing `i = p + 1` satisfies `1 ≤ i` and `i + 2 ≤ n`. Then `k ≡ i + 1 mod 5`, `p = i - 1`, and `q ∈ {i, i + 1}`. We select the second branch (`k ≡ i + 1 mod 5`) and navigate to the third sub-branch via nested `Or.inr`, with all checks completed by `omega`.
uses
Or.inr· refine ⟨p.val + 1, by omega, by omega, ?_⟩ right refine ⟨by omega, Or.inr (Or.inr ⟨by omega, ?_⟩)⟩ rcases hq with h | h <;> omega
Or.inl- Given a proof of `a`, proves the disjunction `a ∨ b` by its left disjunct.
Or.inr- Given a proof of `b`, proves the disjunction `a ∨ b` by its right disjunct.
- All arithmetic checks on indices, inequalities, and modular congruences modulo 5 are automatically discharged by Lean's `omega` decision procedure for Presburger arithmetic.
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.
/-- Explicit closed form of the transition relation of the Pell automaton. -/theorem pell_step_iff (n : ℕ) (hn : 3 ≤ n) {p q : Fin n} {k : Fin 5} : q ∈ (pell_nfa n).step p k ↔ (k.val = p.val % 5 ∧ 1 ≤ p.val ∧ p.val + 2 ≤ n ∧ (q.val = p.val ∨ q.val = p.val + 1)) ∨ (k.val = p.val % 5 ∧ p.val + 1 = n ∧ q.val = p.val) ∨ (k.val = (p.val + 1) % 5 ∧ p.val + 3 ≤ n ∧ (q.val = p.val ∨ q.val = p.val + 2)) ∨ (k.val = (p.val + 1) % 5 ∧ p.val + 2 = n ∧ q.val = p.val) ∨ (k.val = (p.val + 2) % 5 ∧ p.val + 3 ≤ n ∧ (q.val = p.val + 1 ∨ q.val = p.val + 2)) := by constructor · intro h simp only [pell_nfa] at h obtain ⟨i, hi1, hi2, h⟩ := h rcases h with ⟨hk, hpq⟩ | ⟨hk, hpq⟩ · rcases hpq with ⟨hp, hq⟩ | ⟨hp, hq⟩ · right; right; left exact ⟨by omega, by omega, by rcases hq with h | h <;> omega⟩ · left exact ⟨by omega, by omega, by omega, by rcases hq with h | h <;> omega⟩ · rcases hpq with ⟨hp, hq⟩ | ⟨hp, hq⟩ | ⟨hp, hq⟩ · by_cases hb : p.val + 2 = n · right; right; right; left exact ⟨by omega, by omega, by omega⟩ · right; right; left exact ⟨by omega, by omega, by omega⟩ · by_cases hb : p.val + 1 = n · right; left exact ⟨by omega, by omega, by omega⟩ · left exact ⟨by omega, by omega, by omega, by omega⟩ · right; right; right; right exact ⟨by omega, by omega, by rcases hq with h | h <;> omega⟩ · intro h simp only [pell_nfa] rcases h with ⟨hk, hp1, hp2, hq⟩ | ⟨hk, hpn, hq⟩ | ⟨hk, hp3, hq⟩ | ⟨hk, hpn2, hq⟩ | ⟨hk, hp3', hq⟩ · refine ⟨p.val, by omega, by omega, ?_⟩ left refine ⟨by omega, Or.inr ⟨by omega, ?_⟩⟩ rcases hq with h | h <;> omega · refine ⟨n - 2, by omega, by omega, ?_⟩ right refine ⟨by omega, Or.inr (Or.inl ⟨by omega, by omega⟩)⟩ · refine ⟨p.val + 1, by omega, by omega, ?_⟩ left refine ⟨by omega, Or.inl ⟨by omega, ?_⟩⟩ rcases hq with h | h <;> omega · refine ⟨p.val, by omega, by omega, ?_⟩ right refine ⟨by omega, Or.inl ⟨by omega, by omega⟩⟩ · refine ⟨p.val + 1, by omega, by omega, ?_⟩ right refine ⟨by omega, Or.inr (Or.inr ⟨by omega, ?_⟩)⟩ rcases hq with h | h <;> omega