AFTD Auto-Formalizing Theoretical Domains

recurrence_b_map_bijective

theoremverified

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

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.

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

    lines 3–5

      intro w
      ext ⟨i, hi⟩
      dsimp [recurrence_b_inv, recurrence_b_map]
  2. 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.

    lines 6–16

    uses if_pos, dif_neg, dif_pos, Fin.ext, add_sub_cancel_right

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

    lines 17–24

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

    lines 28–30

    uses recurrence_b_map_bijective_left_inv, Finite.injective_iff_bijective.mp

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

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

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