recurrence_b_map_bijective
For any integer k ≥ 2, the transition map of recurrence (B) on (ℤ/3ℤ)^k is bijective.
Statement
theorem recurrence_b_map_bijective (k : ℕ) (hk : 2 ≤ k) : Function.Bijective (recurrence_b_map k)- 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_invThe inverse transition map for recurrence (B) on (ℤ/3ℤ)^k for k ≥ 2, sending (u_0, ..., u_{k-1}) to (u_{k-1} - u_{k-2}^2, u_0, ...,…
- Used by 2
- 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,…
- recurrence_b_map_orbit_periodicFor any integer k ≥ 2, every orbit of the transition map of recurrence (B) on (ℤ/3ℤ)^k is purely periodic: for every state w, there exists…
Read back from the Lean
For any natural number $k$ satisfying $2 \le k$, the function recurrence_b_map k from $(\text{Fin } k \to \mathbb{Z}/3\mathbb{Z})$ to $(\text{Fin } k \to \mathbb{Z}/3\mathbb{Z})$ is bijective.
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 shows that `recurrence_b_map k` is bijective by constructing an explicit left inverse, `recurrence_b_inv k hk`. For any state w, the composition recovers w 0 at the boundary via the cancellation (w 0 + w (k-1)^2) - w (k-1)^2 = w 0, and recovers w i for i > 0 by shifting back one position. Because the state space (ℤ/3ℤ)^k is finite, the existence of a left inverse implies injectivity, which in turn implies bijectivity.
To show that `recurrence_b_inv` is a left inverse of `recurrence_b_map`, it suffices to verify that for any state w and index i < k, the i-th component of (recurrence_b_inv (recurrence_b_map w)) equals w i.
We introduce an arbitrary state w and use functional extensionality to reduce the equality of states to component-wise equality at an arbitrary index i < k. We then unfold the definitions of `recurrence_b_inv` and `recurrence_b_map`.
intro w ext ⟨i, hi⟩ dsimp [recurrence_b_inv, recurrence_b_map]
The reconstructed state agrees with w at index i = 0.
When i = 0, `recurrence_b_inv` computes u (k - 1) - (u (k - 2))^2, where u = recurrence_b_map w. For the boundary component u (k - 1), the condition (k - 1) + 1 < k is false, so `recurrence_b_map` yields w 0 + (w (k - 1))^2. For u (k - 2), since k ≥ 2, (k - 2) + 1 = k - 1 < k, so `recurrence_b_map` shifts it to w (k - 1). Subtracting (w (k - 1))^2 cancels the quadratic term, leaving w 0, which matches w i.
uses
if_pos,dif_neg,dif_pos,Fin.ext,add_sub_cancel_rightby_cases h0 : i = 0 · rw [if_pos h0] have h1 : ¬ (k - 1 + 1 < k) := by omega have h2 : k - 2 + 1 < k := by omega rw [dif_neg h1, dif_pos h2] subst h0 have heq : (⟨k - 2 + 1, h2⟩ : Fin k) = ⟨k - 1, by omega⟩ := by apply Fin.ext dsimp omega rw [heq, add_sub_cancel_right]
The reconstructed state agrees with w at any index i ≠ 0, completing the proof that `recurrence_b_inv` is a left inverse.
When i ≠ 0, `recurrence_b_inv` looks up u (i - 1). Because i ≠ 0 and i < k, we have (i - 1) + 1 = i < k, so `recurrence_b_map` evaluates on its first branch to w ((i - 1) + 1) = w i. Identifying the index (i - 1) + 1 with i in Fin k establishes equality with w i.
uses
if_neg,dif_pos,Fin.ext· rw [if_neg h0] have h1 : i - 1 + 1 < k := by omega rw [dif_pos h1] have heq : (⟨i - 1 + 1, h1⟩ : Fin k) = ⟨i, hi⟩ := by apply Fin.ext dsimp omega rw [heq]
The transition map `recurrence_b_map k` is bijective on (ℤ/3ℤ)^k.
Because `recurrence_b_inv` is a left inverse of `recurrence_b_map k`, the transition map is injective. Since the state space (Fin k → ZMod 3) is a finite type, any injective map from this type to itself is automatically bijective.
uses
recurrence_b_map_bijective_left_inv,Finite.injective_iff_bijective.mphave hlinv := recurrence_b_map_bijective_left_inv k hk have hinj : Function.Injective (recurrence_b_map k) := hlinv.injective exact Finite.injective_iff_bijective.mp hinj
if_pos- In a conditional expression `if c then t else e`, if c is true, the value is t.
dif_neg- In a dependent conditional expression `if h : c then t else e`, if c is false, the value is the else-branch.
dif_pos- In a dependent conditional expression `if h : c then t else e`, if c is true, the value is the then-branch.
Fin.ext- Two elements of `Fin n` are equal if and only if their underlying natural numbers are equal.
add_sub_cancel_right- In an additive group, (a + b) - b = a.
if_neg- In a conditional expression `if c then t else e`, if c is false, the value is e.
recurrence_b_map_bijective_left_inv- For any k ≥ 2, `recurrence_b_inv k hk` is a left inverse of `recurrence_b_map k`.
Finite.injective_iff_bijective.mp- An injective map from a finite type to itself is bijective.
- In Lean, indices are elements of `Fin k`, so shifts and boundary checks require explicit arithmetic proofs (via `omega` and `Fin.ext`) that have no informal counterpart.
- Rather than proving that `recurrence_b_inv` is also a right inverse, bijectivity is deduced from injectivity using the finiteness of the state space (ℤ/3ℤ)^k.
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.
theorem recurrence_b_map_bijective_left_inv (k : ℕ) (hk : 2 ≤ k) : Function.LeftInverse (recurrence_b_inv k hk) (recurrence_b_map k) := by intro w ext ⟨i, hi⟩ dsimp [recurrence_b_inv, recurrence_b_map] by_cases h0 : i = 0 · rw [if_pos h0] have h1 : ¬ (k - 1 + 1 < k) := by omega have h2 : k - 2 + 1 < k := by omega rw [dif_neg h1, dif_pos h2] subst h0 have heq : (⟨k - 2 + 1, h2⟩ : Fin k) = ⟨k - 1, by omega⟩ := by apply Fin.ext dsimp omega rw [heq, add_sub_cancel_right] · rw [if_neg h0] have h1 : i - 1 + 1 < k := by omega rw [dif_pos h1] have heq : (⟨i - 1 + 1, h1⟩ : Fin k) = ⟨i, hi⟩ := by apply Fin.ext dsimp omega rw [heq]/-- Bijectivity of the transition map of recurrence B for k ≥ 2. -/theorem recurrence_b_map_bijective (k : ℕ) (hk : 2 ≤ k) : Function.Bijective (recurrence_b_map k) := by have hlinv := recurrence_b_map_bijective_left_inv k hk have hinj : Function.Injective (recurrence_b_map k) := hlinv.injective exact Finite.injective_iff_bijective.mp hinj