AFTD Auto-Formalizing Theoretical Domains

cyclic_rotate_left_bijective

theoremverified

For any positive natural number k and any type α, cyclic_rotate_left k is a bijection on Fin k → α.

Statement

theorem cyclic_rotate_left_bijective (k : ℕ) (hk : 0 < k) (α : Type*) :
    Function.Bijective (cyclic_rotate_left (α := α) k)
Source
step towards dual_melas_adjacent_cyclic_patterns_bivariate_poisson_limit
Verified
04 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • cyclic_rotate_leftGiven a type α, a natural number k, and a word w : Fin k → α, cyclic_rotate_left k w is the function Fin k → α mapping each index j : Fin…
Used by 1

The proof, explained

The theorem proves that cyclic_rotate_left k is a bijection by explicitly defining its two-sided inverse, which cyclically rotates indices in the opposite direction by shifting by k - 1 modulo k. Verifying that this candidate is both a left and right inverse reduces via extensionality to proving that the combined index shifts modulo k simplify back to the original index. Both directions are completed by modular arithmetic, splitting into cases based on whether the index is zero or whether shifting by 1 causes an overflow modulo k.

  1. To prove that cyclic_rotate_left k is bijective, it suffices to construct a two-sided inverse.

    By Function.bijective_iff_has_inverse.2, exhibiting a function that is both a left and right inverse proves bijectivity. We define the candidate inverse g(w) sending an index j to w((j + k - 1) % k), which is well-defined because j < k implies k > 0 via pos_of_gt, ensuring (j + k - 1) % k < k via Nat.mod_lt.

    line 4

    uses Function.bijective_iff_has_inverse.2, Nat.mod_lt, pos_of_gt

      refine Function.bijective_iff_has_inverse.2 ⟨fun w j => w ⟨(j.val + k - 1) % k, Nat.mod_lt _ (pos_of_gt j.isLt)⟩, ?_, ?_⟩
  2. Showing that the candidate is a left inverse reduces to the index identity ((j + k - 1) % k + 1) % k = j for every index j.

    Given an arbitrary word w and index j, evaluating the composition of cyclic_rotate_left k and the candidate inverse simplifies to evaluating w at index ((j + k - 1) % k + 1) % k. By extensionality, it suffices to show this index equals j, using the fact that j < k.

    lines 5–11

      · intro w
        funext j
        dsimp [cyclic_rotate_left]
        congr 1
        ext
        dsimp
        have hj := j.isLt
  3. When j = 0, the left-inverse index identity ((0 + k - 1) % k + 1) % k = 0 holds.

    We split into cases on whether j = 0 or j > 0 using Nat.eq_zero_or_pos. In the case j = 0, the expression simplifies by Nat.zero_add to ((k - 1) % k + 1) % k. Since k > 0, we have k - 1 < k, so (k - 1) % k = k - 1 by Nat.mod_eq_of_lt. Then k - 1 + 1 = k, and k % k = 0 by Nat.mod_self.

    lines 12–18

    uses Nat.eq_zero_or_pos, Nat.zero_add, Nat.mod_eq_of_lt, Nat.mod_self

        rcases Nat.eq_zero_or_pos j.val with hj0 | hj_pos
        · rw [hj0]
          simp only [Nat.zero_add]
          have : k - 1 < k := by omega
          rw [Nat.mod_eq_of_lt this]
          have : k - 1 + 1 = k := by omega
          rw [this, Nat.mod_self]
  4. When j > 0, the left-inverse index identity ((j + k - 1) % k + 1) % k = j holds.

    Since j > 0, we can rewrite j + k - 1 as (j - 1) + k. By Nat.add_mod_right, ((j - 1) + k) % k = (j - 1) % k. Because j - 1 < j < k, Nat.mod_eq_of_lt gives j - 1. Adding 1 yields j, and since j < k, j % k = j by Nat.mod_eq_of_lt.

    lines 19–24

    uses Nat.add_mod_right, Nat.mod_eq_of_lt

        · have h1 : j.val + k - 1 = (j.val - 1) + k := by omega
          rw [h1, Nat.add_mod_right]
          have h2 : j.val - 1 < k := by omega
          rw [Nat.mod_eq_of_lt h2]
          have h3 : j.val - 1 + 1 = j.val := by omega
          rw [h3, Nat.mod_eq_of_lt hj]
  5. Showing that the candidate is a right inverse reduces to the index identity ((j + 1) % k + k - 1) % k = j for every index j.

    Applying cyclic_rotate_left k after the candidate inverse evaluates w at index ((j + 1) % k + k - 1) % k. By extensionality, it suffices to show this index equals j, again using j < k.

    lines 25–31

      · intro w
        funext j
        dsimp [cyclic_rotate_left]
        congr 1
        ext
        dsimp
        have hj := j.isLt
  6. When j + 1 < k, the right-inverse index identity ((j + 1) % k + k - 1) % k = j holds.

    We split on whether j + 1 < k or j + 1 ≥ k using lt_or_ge. When j + 1 < k, the inner modulo evaluates to j + 1 by Nat.mod_eq_of_lt. Then j + 1 + k - 1 = j + k, and (j + k) % k = j % k by Nat.add_mod_right. Since j < k, Nat.mod_eq_of_lt yields j.

    lines 32–37

    uses lt_or_ge, Nat.mod_eq_of_lt, Nat.add_mod_right

        rcases lt_or_ge (j.val + 1) k with h | h
        · rw [Nat.mod_eq_of_lt h]
          have : j.val + 1 + k - 1 = j.val + k := by omega
          rw [this]
          have : (j.val + k) % k = j.val % k := Nat.add_mod_right j.val k
          rw [this, Nat.mod_eq_of_lt hj]
  7. When j + 1 ≥ k, the right-inverse index identity ((j + 1) % k + k - 1) % k = j holds.

    Since j < k and j + 1 ≥ k, we must have j + 1 = k. Replacing j + 1 by k yields (k % k + k - 1) % k = (0 + k - 1) % k = (k - 1) % k by Nat.mod_self and Nat.zero_add. Since k > 0, k - 1 < k, so (k - 1) % k = k - 1 by Nat.mod_eq_of_lt. Finally, k - 1 = j holds because j + 1 = k.

    lines 38–42

    uses Nat.mod_self, Nat.zero_add, Nat.mod_eq_of_lt

        · have : j.val + 1 = k := by omega
          rw [this, Nat.mod_self, Nat.zero_add]
          have : k - 1 < k := by omega
          rw [Nat.mod_eq_of_lt this]
          omega
Function.bijective_iff_has_inverse.2
A function is bijective if there exists another function that is both a left and right inverse to it.
Nat.mod_lt
For any natural numbers x and y with y > 0, the remainder x % y is strictly less than y.
pos_of_gt
In a preordered type where 0 is a minimal element, if a < b then 0 < b.
Nat.eq_zero_or_pos
Every natural number is either equal to 0 or strictly positive.
Nat.zero_add
Adding zero to any natural number n on the left gives n (0 + n = n).
Nat.mod_eq_of_lt
If a natural number a is strictly less than b, then a % b = a.
Nat.mod_self
Any natural number modulo itself is zero (n % n = 0).
Nat.add_mod_right
Adding z to x before taking the remainder modulo z does not change the remainder: (x + z) % z = x % z.
lt_or_ge
In a linear order, for any two elements a and b, either a < b or b ≤ a.

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

/-- cyclic_rotate_left is a bijection on Fin k → α for positive k. -/theorem cyclic_rotate_left_bijective (k : ℕ) (hk : 0 < k) (α : Type*) :    Function.Bijective (cyclic_rotate_left (α := α) k) := by  refine Function.bijective_iff_has_inverse.2 ⟨fun w j => w ⟨(j.val + k - 1) % k, Nat.mod_lt _ (pos_of_gt j.isLt)⟩, ?_, ?_⟩  · intro w    funext j    dsimp [cyclic_rotate_left]    congr 1    ext    dsimp    have hj := j.isLt    rcases Nat.eq_zero_or_pos j.val with hj0 | hj_pos    · rw [hj0]      simp only [Nat.zero_add]      have : k - 1 < k := by omega      rw [Nat.mod_eq_of_lt this]      have : k - 1 + 1 = k := by omega      rw [this, Nat.mod_self]    · have h1 : j.val + k - 1 = (j.val - 1) + k := by omega      rw [h1, Nat.add_mod_right]      have h2 : j.val - 1 < k := by omega      rw [Nat.mod_eq_of_lt h2]      have h3 : j.val - 1 + 1 = j.val := by omega      rw [h3, Nat.mod_eq_of_lt hj]  · intro w    funext j    dsimp [cyclic_rotate_left]    congr 1    ext    dsimp    have hj := j.isLt    rcases lt_or_ge (j.val + 1) k with h | h    · rw [Nat.mod_eq_of_lt h]      have : j.val + 1 + k - 1 = j.val + k := by omega      rw [this]      have : (j.val + k) % k = j.val % k := Nat.add_mod_right j.val k      rw [this, Nat.mod_eq_of_lt hj]    · have : j.val + 1 = k := by omega      rw [this, Nat.mod_self, Nat.zero_add]      have : k - 1 < k := by omega      rw [Nat.mod_eq_of_lt this]      omega
See it in the graphDiscuss this resultChallenge it