cyclic_rotate_left_bijective
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
- dual_melas_pattern_count_cyclic_rotate_left_sumFor any field F finite-dimensional over ZMod 2, positive natural number k, and elements α, c ∈ F, the sum over all words w : Fin k → ZMod…
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.
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.
uses
Function.bijective_iff_has_inverse.2,Nat.mod_lt,pos_of_gtrefine Function.bijective_iff_has_inverse.2 ⟨fun w j => w ⟨(j.val + k - 1) % k, Nat.mod_lt _ (pos_of_gt j.isLt)⟩, ?_, ?_⟩
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.
· intro w funext j dsimp [cyclic_rotate_left] congr 1 ext dsimp have hj := j.isLt
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.
uses
Nat.eq_zero_or_pos,Nat.zero_add,Nat.mod_eq_of_lt,Nat.mod_selfrcases 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]
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.
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]
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.
· intro w funext j dsimp [cyclic_rotate_left] congr 1 ext dsimp have hj := j.isLt
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.
uses
lt_or_ge,Nat.mod_eq_of_lt,Nat.add_mod_rightrcases 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]
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.
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.
- Several arithmetic facts and bounds over ℕ (such as k - 1 < k for k > 0, and j + 1 = k from j < k and j + 1 ≥ k) are discharged directly by the linear arithmetic tactic omega.
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.
/-- 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