recurrence_b_map_zero
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}$.
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$.
ext iFor 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$.
uses
recurrence_b_mapsimp [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$.
- The `simp` tactic handles both branches of the conditional definition of `recurrence_b_map` and simplifies the ring operations on zero in $\mathbb{Z}/3\mathbb{Z}$ automatically.
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.
/-- 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]