recurrence_b_map_orbit_periodic
For 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 m > 0 such that the m-th iterate of the map on w is w.
Statement
theorem recurrence_b_map_orbit_periodic (k : ℕ) (hk : 2 ≤ k) (w : Fin k → ZMod 3) : ∃ m > 0, (recurrence_b_map k)^[m] w = w- 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_bijectiveFor any integer k ≥ 2, the transition map of recurrence (B) on (ℤ/3ℤ)^k is bijective.
- 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$, given a proof that $2 \le k$, and for every function $w : \mathrm{Fin}\ k \to \mathbb{Z}/3\mathbb{Z}$, there exists a natural number $m > 0$ such that the $m$-th iterate of $\mathrm{recurrence\_b\_map}(k)$ applied to $w$ equals $w$.
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
Because the state space (Fin k → ZMod 3) is finite, the pigeonhole principle implies that the sequence of iterates of any state w must eventually collide, producing two distinct times i and j at which the states coincide. Decomposing the larger index as the sum of the smaller index and their difference expresses this collision as f^[min](f^[|j - i|](w)) = f^[min](w). Because the recurrence map is bijective (and hence injective) for k ≥ 2, its iterates are also injective; cancelling the outer iterate yields f^[|j - i|](w) = w, establishing pure periodicity with strictly positive period |j - i|.
The transition map recurrence_b_map k is injective.
For k ≥ 2, the recurrence map is bijective by recurrence_b_map_bijective, so its injectivity follows directly.
uses
recurrence_b_map_bijectivehave hinj : Function.Injective (recurrence_b_map k) := (recurrence_b_map_bijective k hk).1There exist two distinct iteration indices whose iterates on w coincide.
Let N be the cardinality of the finite state space (Fin k → ZMod 3). The index set Fin (N + 1) has cardinality N + 1 > N. Applying the pigeonhole principle (Fintype.exists_ne_map_eq_of_card_lt) to the mapping i ↦ f^[i](w) from Fin (N + 1) into the state space produces distinct indices i ≠ j such that f^[i](w) = f^[j](w).
uses
Fintype.exists_ne_map_eq_of_card_ltlet N := Fintype.card (Fin k → ZMod 3) have hcard : Fintype.card (Fin (N + 1)) > Fintype.card (Fin k → ZMod 3) := by simp [N] obtain ⟨i, j, hne, heq⟩ := Fintype.exists_ne_map_eq_of_card_lt (fun i : Fin (N + 1) => (recurrence_b_map k)^[(i : ℕ)] w) hcard
The collision indices satisfy either i < j or j < i.
Since i ≠ j and Fin (N + 1) is linearly ordered, lt_or_gt_of_ne separates the relation into two cases: i < j or j < i.
uses
lt_or_gt_of_nercases lt_or_gt_of_ne hne with hlt | hlt
In the case i < j, the positive difference m = j - i satisfies f^[m](w) = w.
Since i < j, the difference m = j - i is strictly positive (Nat.sub_pos_of_lt and Fin.lt_def.mp). Writing j = i + (j - i) via Nat.add_sub_of_le and le_of_lt, the iterate identity Function.iterate_add_apply rewrites f^[j](w) = f^[i](w) as f^[i](f^[j - i](w)) = f^[i](w). Because f is injective, its iterate f^[i] is injective by Function.Injective.iterate, allowing f^[i] to be cancelled on both sides to conclude f^[j - i](w) = w.
uses
Nat.sub_pos_of_lt,Fin.lt_def.mp,Nat.add_sub_of_le,le_of_lt,Function.iterate_add_apply,Function.Injective.iterate· refine ⟨(j : ℕ) - (i : ℕ), Nat.sub_pos_of_lt (Fin.lt_def.mp hlt), ?_⟩ have hji : (j : ℕ) = (i : ℕ) + ((j : ℕ) - (i : ℕ)) := by exact (Nat.add_sub_of_le (le_of_lt (Fin.lt_def.mp hlt))).symm have hcancel : (recurrence_b_map k)^[(i : ℕ)] ((recurrence_b_map k)^[((j : ℕ) - (i : ℕ))] w) = (recurrence_b_map k)^[(i : ℕ)] w := by rw [← Function.iterate_add_apply, ← hji] exact heq.symm exact (Function.Injective.iterate hinj (i : ℕ)) hcancel
In the case j < i, the positive difference m = i - j satisfies f^[m](w) = w.
Symmetrically, setting m = i - j yields m > 0 (Nat.sub_pos_of_lt and Fin.lt_def.mp). Writing i = j + (i - j) via Nat.add_sub_of_le and le_of_lt, Function.iterate_add_apply rewrites f^[i](w) = f^[j](w) as f^[j](f^[i - j](w)) = f^[j](w). Cancelling f^[j] using the injectivity of iterates (Function.Injective.iterate) gives f^[i - j](w) = w.
uses
Nat.sub_pos_of_lt,Fin.lt_def.mp,Nat.add_sub_of_le,le_of_lt,Function.iterate_add_apply,Function.Injective.iterate· refine ⟨(i : ℕ) - (j : ℕ), Nat.sub_pos_of_lt (Fin.lt_def.mp hlt), ?_⟩ have hij : (i : ℕ) = (j : ℕ) + ((i : ℕ) - (j : ℕ)) := by exact (Nat.add_sub_of_le (le_of_lt (Fin.lt_def.mp hlt))).symm have hcancel : (recurrence_b_map k)^[(j : ℕ)] ((recurrence_b_map k)^[((i : ℕ) - (j : ℕ))] w) = (recurrence_b_map k)^[(j : ℕ)] w := by rw [← Function.iterate_add_apply, ← hij] exact heq exact (Function.Injective.iterate hinj (j : ℕ)) hcancel
recurrence_b_map_bijective- For k ≥ 2, the transition map of recurrence (B) on (ℤ/3ℤ)^k is bijective.
Fintype.exists_ne_map_eq_of_card_lt- If the cardinality of the domain is strictly greater than the cardinality of the codomain, any map between them sends two distinct elements to the same value (the pigeonhole principle).
lt_or_gt_of_ne- In a linear order, two distinct elements satisfy either a < b or b < a.
Nat.sub_pos_of_lt- For natural numbers with m < n, the difference n - m is strictly positive.
Fin.lt_def.mp- A strict inequality between elements of Fin n implies the strict inequality of their underlying natural numbers.
Nat.add_sub_of_le- For natural numbers with a ≤ b, adding the difference back recovers the larger number: a + (b - a) = b.
le_of_lt- In a preorder, a strict inequality a < b implies the non-strict inequality a ≤ b.
Function.iterate_add_apply- The (m + n)-th iterate of a function f equals the m-th iterate applied to the n-th iterate: f^[m + n](x) = f^[m](f^[n](x)).
Function.Injective.iterate- If a function f is injective, then each of its iterates f^[n] is also injective.
- The proof splits into two symmetric branches (i < j and j < i) to handle the inequality i ≠ j obtained from the pigeonhole principle, an argument that in informal mathematics is usually streamlined by assuming i < j without loss of generality.
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.
/-- Pure periodicity of orbits of recurrence B for k ≥ 2. -/theorem recurrence_b_map_orbit_periodic (k : ℕ) (hk : 2 ≤ k) (w : Fin k → ZMod 3) : ∃ m > 0, (recurrence_b_map k)^[m] w = w := by have hinj : Function.Injective (recurrence_b_map k) := (recurrence_b_map_bijective k hk).1 let N := Fintype.card (Fin k → ZMod 3) have hcard : Fintype.card (Fin (N + 1)) > Fintype.card (Fin k → ZMod 3) := by simp [N] obtain ⟨i, j, hne, heq⟩ := Fintype.exists_ne_map_eq_of_card_lt (fun i : Fin (N + 1) => (recurrence_b_map k)^[(i : ℕ)] w) hcard rcases lt_or_gt_of_ne hne with hlt | hlt · refine ⟨(j : ℕ) - (i : ℕ), Nat.sub_pos_of_lt (Fin.lt_def.mp hlt), ?_⟩ have hji : (j : ℕ) = (i : ℕ) + ((j : ℕ) - (i : ℕ)) := by exact (Nat.add_sub_of_le (le_of_lt (Fin.lt_def.mp hlt))).symm have hcancel : (recurrence_b_map k)^[(i : ℕ)] ((recurrence_b_map k)^[((j : ℕ) - (i : ℕ))] w) = (recurrence_b_map k)^[(i : ℕ)] w := by rw [← Function.iterate_add_apply, ← hji] exact heq.symm exact (Function.Injective.iterate hinj (i : ℕ)) hcancel · refine ⟨(i : ℕ) - (j : ℕ), Nat.sub_pos_of_lt (Fin.lt_def.mp hlt), ?_⟩ have hij : (i : ℕ) = (j : ℕ) + ((i : ℕ) - (j : ℕ)) := by exact (Nat.add_sub_of_le (le_of_lt (Fin.lt_def.mp hlt))).symm have hcancel : (recurrence_b_map k)^[(j : ℕ)] ((recurrence_b_map k)^[((i : ℕ) - (j : ℕ))] w) = (recurrence_b_map k)^[(j : ℕ)] w := by rw [← Function.iterate_add_apply, ← hij] exact heq exact (Function.Injective.iterate hinj (j : ℕ)) hcancel