recurrence_b_map_fixed_point_unique
For 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.
Statement
theorem recurrence_b_map_fixed_point_unique (k : ℕ) (hk : 2 ≤ k) (w : Fin k → ZMod 3) : recurrence_b_map k w = w ↔ w = 0- Source
- arXiv:2610.34300 Proposition 7
- Verified
- 30 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- 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).
- recurrence_b_map_zeroThe state transition map of recurrence (B) on (ℤ/3ℤ)^k maps the zero vector to the zero vector.
- Used by 1
- recurrence_b_transition_bijective_and_orbit_periodic_and_unique_fixed_pointFor any integer k ≥ 2, the transition map of recurrence (B) on (ℤ/3ℤ)^k is bijective, every orbit is purely periodic (for every state w,…
Read back from the Lean
For every natural number $k$ such that $2 \le k$, and for every vector $w : \text{Fin } k \to \mathbb{Z}/3\mathbb{Z}$, $w$ is a fixed point of recurrence_b_map k (that is, recurrence_b_map k w = w) if and only if $w$ is the zero vector ($w = 0$).
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 splits the equivalence into two directions. The backward direction holds immediately because the zero state is known to map to itself. For the forward direction, assuming w is a fixed point, the shift property of the recurrence map forces all coordinates of w to equal w 0 by induction. The boundary condition at coordinate k - 1 then yields the scalar equation w 0 + (w 0)² = w 0 in ℤ/3ℤ, whose only solution is w 0 = 0, forcing the entire vector w to be zero.
The equivalence splits into showing that any fixed point w is 0, and that 0 is a fixed point.
We split the if-and-only-if statement into two implications using `constructor`. For the forward direction, we assume `recurrence_b_map k w = w` (named `hw`) and set out to show that `w = 0`.
constructor · intro hw
All coordinates of w are identical: w j = w 0 for every index j < k.
We proceed by induction on `j`. The base case j = 0 is an identity. For the inductive step j + 1 < k, the definition of `recurrence_b_map` evaluates via `dif_pos` to (T(w)) j = w (j + 1). Because w is a fixed point, (T(w)) j = w j, so w (j + 1) = w j. By the induction hypothesis, w j = w 0, which implies w (j + 1) = w 0.
uses
dif_poshave hall : ∀ (j : ℕ) (hj : j < k), w ⟨j, hj⟩ = w ⟨0, by omega⟩ := by intro j induction' j with j ih · intro hj rfl · intro hj have hj' : j < k := by omega have hstep : (recurrence_b_map k w) ⟨j, hj'⟩ = w ⟨j + 1, hj⟩ := by dsimp [recurrence_b_map] rw [dif_pos hj] have heq : (recurrence_b_map k w) ⟨j, hj'⟩ = w ⟨j, hj'⟩ := by rw [hw] rw [hstep] at heq rw [heq, ih hj']
The initial component satisfies w 0 + (w 0)² = w 0 in ℤ/3ℤ.
At the last coordinate k - 1, the condition (k - 1) + 1 < k fails, so the definition of `recurrence_b_map` evaluates via `dif_neg` to (T(w)) (k - 1) = w 0 + (w (k - 1))². Since w is a fixed point, this equals w (k - 1). Substituting the fact that all coordinates equal w 0 (so w (k - 1) = w 0) yields w 0 + (w 0)² = w 0.
uses
dif_neghave hlast : (recurrence_b_map k w) ⟨k - 1, by omega⟩ = w ⟨0, by omega⟩ + (w ⟨k - 1, by omega⟩)^2 := by dsimp [recurrence_b_map] have hnot : ¬ (k - 1 + 1 < k) := by omega rw [dif_neg hnot] have heq_last : (recurrence_b_map k w) ⟨k - 1, by omega⟩ = w ⟨k - 1, by omega⟩ := by rw [hw] rw [hlast] at heq_last have h0_eq : w ⟨k - 1, by omega⟩ = w ⟨0, by omega⟩ := hall (k - 1) (by omega) rw [h0_eq] at heq_last
The initial component w 0 equals 0.
In the finite field ℤ/3ℤ, the only element satisfying c + c² = c is c = 0. This is established by exhaustively evaluating the polynomial relation on each element of ℤ/3ℤ via `decide`. Applying this to w 0 gives w 0 = 0.
have hc : w ⟨0, by omega⟩ = 0 := by have hdec : ∀ c : ZMod 3, c + c ^ 2 = c → c = 0 := by decide exact hdec (w ⟨0, by omega⟩) heq_last
The entire vector w is the zero vector.
By componentwise extensionality, two vectors in (ℤ/3ℤ)^k are equal if they agree at every index i < k. Since every coordinate w i equals w 0, and w 0 = 0, every coordinate is 0.
ext ⟨i, hi⟩ rw [hall i hi, hc] rfl
The zero vector is a fixed point of recurrence_b_map.
For the reverse implication, assuming w = 0, the goal is `recurrence_b_map k 0 = 0`, which holds directly by the lemma `recurrence_b_map_zero`.
uses
recurrence_b_map_zero· rintro rfl exact recurrence_b_map_zero k
dif_pos- in a dependent if-then-else expression `if h : c then t else e`, when the condition `c` holds, the expression evaluates to `t`
dif_neg- in a dependent if-then-else expression `if h : c then t else e`, when the condition `c` fails, the expression evaluates to `e`
recurrence_b_map_zero- the recurrence (B) transition map maps the zero vector to the zero vector
- Finite case checking (`decide`) is used in step 4 to verify that c + c² = c implies c = 0 for all elements of ℤ/3ℤ by exhausting the three elements {0, 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
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.
/-- Unique fixed point of recurrence B is 0 for k ≥ 2. -/theorem recurrence_b_map_fixed_point_unique (k : ℕ) (hk : 2 ≤ k) (w : Fin k → ZMod 3) : recurrence_b_map k w = w ↔ w = 0 := by constructor · intro hw have hall : ∀ (j : ℕ) (hj : j < k), w ⟨j, hj⟩ = w ⟨0, by omega⟩ := by intro j induction' j with j ih · intro hj rfl · intro hj have hj' : j < k := by omega have hstep : (recurrence_b_map k w) ⟨j, hj'⟩ = w ⟨j + 1, hj⟩ := by dsimp [recurrence_b_map] rw [dif_pos hj] have heq : (recurrence_b_map k w) ⟨j, hj'⟩ = w ⟨j, hj'⟩ := by rw [hw] rw [hstep] at heq rw [heq, ih hj'] have hlast : (recurrence_b_map k w) ⟨k - 1, by omega⟩ = w ⟨0, by omega⟩ + (w ⟨k - 1, by omega⟩)^2 := by dsimp [recurrence_b_map] have hnot : ¬ (k - 1 + 1 < k) := by omega rw [dif_neg hnot] have heq_last : (recurrence_b_map k w) ⟨k - 1, by omega⟩ = w ⟨k - 1, by omega⟩ := by rw [hw] rw [hlast] at heq_last have h0_eq : w ⟨k - 1, by omega⟩ = w ⟨0, by omega⟩ := hall (k - 1) (by omega) rw [h0_eq] at heq_last have hc : w ⟨0, by omega⟩ = 0 := by have hdec : ∀ c : ZMod 3, c + c ^ 2 = c → c = 0 := by decide exact hdec (w ⟨0, by omega⟩) heq_last ext ⟨i, hi⟩ rw [hall i hi, hc] rfl · rintro rfl exact recurrence_b_map_zero k