AFTD Auto-Formalizing Theoretical Domains

pell_step_iff

theoremverified

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

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

    lines 9–13

      constructor
      · intro h
        simp only [pell_nfa] at h
        obtain ⟨i, hi1, hi2, h⟩ := h
        rcases h with ⟨hk, hpq⟩ | ⟨hk, hpq⟩
  2. 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.

    lines 14–18

        · 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⟩
  3. 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`.

    lines 19–31

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

    lines 32–34

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

    lines 35–38

    uses Or.inr

        · refine ⟨p.val, by omega, by omega, ?_⟩
          left
          refine ⟨by omega, Or.inr ⟨by omega, ?_⟩⟩
          rcases hq with h | h <;> omega
  6. 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.

    lines 39–41

    uses Or.inr, Or.inl

        · refine ⟨n - 2, by omega, by omega, ?_⟩
          right
          refine ⟨by omega, Or.inr (Or.inl ⟨by omega, by omega⟩)⟩
  7. 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`.

    lines 42–45

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

    lines 46–48

    uses Or.inl

        · refine ⟨p.val, by omega, by omega, ?_⟩
          right
          refine ⟨by omega, Or.inl ⟨by omega, by omega⟩⟩
  9. 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`.

    lines 49–52

    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.

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

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