prefixReversal_involutive
Applying a prefix reversal of length k twice in Equiv.Perm (Fin n) yields the identity permutation.
Statement
theorem prefixReversal_involutive (n k : ℕ) :
prefixReversal n k * prefixReversal n k = 1- Source
- arXiv:2610.30892 Section 1
- Verified
- 24 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- prefixReversalFor integers n and k, prefixReversal n k is the permutation in the symmetric group Equiv.Perm (Fin n) that reverses the first k elements…
Read back from the Lean
For all natural numbers $n$ and $k$, the permutation prefixReversal n k of Fin n composed with itself is equal to the identity permutation $1$ on Fin n (that is, prefixReversal n k is an involution).
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
A prefix reversal is defined as a permutation whose forward and inverse maps are identical. Consequently, its `left_inv` field proves that applying the operation twice restores any input, and extensionality of equivalences (`Equiv.ext`) immediately lifts this pointwise involution to equality with the identity permutation in the symmetric group.
Applying the prefix reversal twice equals the identity permutation: $\text{prefixReversal}(n, k) * \text{prefixReversal}(n, k) = 1$.
By extensionality for equivalences (`Equiv.ext`), two permutations are equal if they agree on every element. Because the definition of `prefixReversal` uses the exact same function for both its forward map and inverse map, its built-in `left_inv` field already proves that applying the permutation twice pointwise yields the original element, matching the pointwise action of the identity permutation $1$.
uses
Equiv.extprefixReversal n k * prefixReversal n k = 1 := Equiv.ext (prefixReversal n k).left_inv
Equiv.ext- Two equivalences (or permutations) are equal if and only if they agree on every input element.
- The definition of `prefixReversal` specifies `invFun` using the exact same formula as `toFun`. Consequently, the `left_inv` proof field of the equivalence is definitionally identical to the pointwise involution property $(f \circ f)(x) = x$, allowing it to be supplied directly to `Equiv.ext`.
Written by a model (gemini-3.8-flash) from the Lean source alone (no goal states were available). Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
/-- Every prefix reversal permutation is an involution. -/theorem prefixReversal_involutive (n k : ℕ) : prefixReversal n k * prefixReversal n k = 1 := Equiv.ext (prefixReversal n k).left_inv