AFTD Auto-Formalizing Theoretical Domains

recurrence_b_map_zero

theoremverified

The state transition map of recurrence (B) on (ℤ/3ℤ)^k maps the zero vector to the zero vector.

Statement

theorem recurrence_b_map_zero (k : ℕ) : recurrence_b_map k 0 = 0
Source
arXiv:2610.34300 Proposition 7
Verified
30 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • recurrence_b_mapThe state transition map T : (ℤ/3ℤ)^k → (ℤ/3ℤ)^k for recurrence (B), sending (w_0, ..., w_{k-1}) to (w_1, ..., w_{k-1}, w_0 + w_{k-1}^2).
Used by 1
  • recurrence_b_map_fixed_point_uniqueFor any integer k ≥ 2, a state w in (ℤ/3ℤ)^k is a fixed point of the transition map of recurrence (B) if and only if w is the zero vector.

Read back from the Lean

For every natural number $k$, applying recurrence_b_map k to the zero function on $\text{Fin } k \to \mathbb{Z}/3\mathbb{Z}$ yields the zero function on $\text{Fin } k \to \mathbb{Z}/3\mathbb{Z}$.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The proof proceeds by function extensionality, showing that the vector `recurrence_b_map k 0` equals the zero vector componentwise. For each coordinate $i$, unfolding `recurrence_b_map` yields either an entry of the zero vector or $0 + 0^2$, both of which simplify to $0$ in $\mathbb{Z}/3\mathbb{Z}$.

  1. It suffices to show that `recurrence_b_map k 0` and the zero vector agree on every component $i \in \text{Fin } k$.

    By function extensionality (`ext i`), two elements of $\text{Fin } k \to \mathbb{Z}/3\mathbb{Z}$ are equal if they evaluate to the same value at every coordinate $i$.

    line 3

      ext i
  2. For every coordinate $i$, `recurrence_b_map k 0 i = 0 i`. automation

    Unfolding the definition of `recurrence_b_map`, for any index $i$, the map either looks up an entry of the input vector or computes the sum of the first entry and the square of the last. Since the input is the zero vector, every entry is $0$, and $0 + 0^2 = 0$ in $\mathbb{Z}/3\mathbb{Z}$, so both branches evaluate to $0$.

    line 4

    uses recurrence_b_map

      simp [recurrence_b_map]
recurrence_b_map
The recurrence (B) transition map on $(\mathbb{Z}/3\mathbb{Z})^k$, which shifts coordinates $i \mapsto w_{i+1}$ when $i + 1 < k$, and sets the last coordinate to $w_0 + w_{k-1}^2$.

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

/-- The zero state is mapped to zero under recurrence B. -/theorem recurrence_b_map_zero (k : ℕ) : recurrence_b_map k 0 = 0 := by  ext i  simp [recurrence_b_map]
See it in the graphDiscuss this resultChallenge it