AFTD Auto-Formalizing Theoretical Domains

recurrence_b_map_orbit_periodic

theoremverified

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

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|.

  1. 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.

    lines 3–4

    uses recurrence_b_map_bijective

      have hinj : Function.Injective (recurrence_b_map k) :=
        (recurrence_b_map_bijective k hk).1
  2. There 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).

    lines 5–10

    uses Fintype.exists_ne_map_eq_of_card_lt

      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
  3. 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.

    line 11

    uses lt_or_gt_of_ne

      rcases lt_or_gt_of_ne hne with hlt | hlt
  4. 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.

    lines 12–19

    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
  5. 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.

    lines 20–27

    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.

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

/-- 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
See it in the graphDiscuss this resultChallenge it