prefixReversal
def
For integers n and k, prefixReversal n k is the permutation in the symmetric group Equiv.Perm (Fin n) that reverses the first k elements (indices 0 through k - 1) and fixes all remaining elements.
Statement
def prefixReversal (n : ℕ) (k : ℕ) : Equiv.Perm (Fin n)- Defined in
- arXiv:2610.30892 Section 1
- Verified
- 23 Oct 2026
- Axioms
- none listed
- Used by 7
- prefix_reversal_groupThe subgroup of the symmetric group on n positions generated by prefix reversals of lengths k, m and n.
- prefix_reversal_six_five_three_not_topIn the symmetric group Equiv.Perm (Fin 6), the subgroup generated by the three prefix reversals of lengths 3, 5, and 6 does not equal the…
- prefix_reversal_gcd_diff_necessaryIf three prefix reversals of lengths k, m, n with 2 ≤ k < m < n generate the symmetric group Equiv.Perm (Fin n), then gcd(n - m, n - k) = 1.
- prefixReversal_involutiveApplying a prefix reversal of length k twice in Equiv.Perm (Fin n) yields the identity permutation.
- not_prefix_reversal_sum_bound_necessaryThe statement
prefix_reversal_sum_bound_necessaryis false: The statement claims that m + k ≥ n + 1 is a necessary condition for prefix… - prefix_reversal_necessary_conditions_not_sufficientIt is not the case that for all natural numbers 2 ≤ k < m < n satisfying 2 * m > n, at least one of k, m, n even, at least one of k, m, n…
- prefix_reversal_group_le_iffThe generated subgroup is contained in H exactly when all three specified prefix reversals lie in H.
Read back from the Lean
Definition of prefixReversal n k, a permutation of Fin n (Equiv.Perm (Fin n)) parameterized by natural numbers n and k. Both the forward and inverse maps send an element j : Fin n to k - 1 - j.val (as an element of Fin n) if j.val < k and k ≤ n, and to j itself otherwise.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- The prefix reversal permutation in Equiv.Perm (Fin n) reversing the first k elements. -/ def prefixReversal (n : ℕ) (k : ℕ) : Equiv.Perm (Fin n) := { toFun := fun j => if h : j.val < k ∧ k ≤ n then ⟨k - 1 - j.val, by omega⟩ else j invFun := fun j => if h : j.val < k ∧ k ≤ n then ⟨k - 1 - j.val, by omega⟩ else j left_inv := by intro ⟨j, hj⟩ dsimp by_cases h : j < k ∧ k ≤ n · rw [dif_pos h] have h' : k - 1 - j < k ∧ k ≤ n := by omega rw [dif_pos h'] apply Fin.ext; dsimp; omega · rw [dif_neg h, dif_neg h] right_inv := by intro ⟨j, hj⟩ dsimp by_cases h : j < k ∧ k ≤ n · rw [dif_pos h] have h' : k - 1 - j < k ∧ k ≤ n := by omega rw [dif_pos h'] apply Fin.ext; dsimp; omega · rw [dif_neg h, dif_neg h] }