AFTD Auto-Formalizing Theoretical Domains

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

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