AFTD Auto-Formalizing Theoretical Domains

recurrence_b_map_fixed_point_unique

theoremverified

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

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.

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

    lines 3–4

      constructor
      · intro hw
  2. 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.

    lines 5–17

    uses dif_pos

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

    lines 18–27

    uses dif_neg

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

    lines 28–30

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

    lines 31–33

        ext ⟨i, hi⟩
        rw [hall i hi, hc]
        rfl
  6. 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`.

    lines 34–35

    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

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

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