permExtendLast
The canonical extension of a permutation of Fin n to a permutation of Fin (n + 1) that fixes the trailing element Fin.last n.
Statement
def permExtendLast {n : ℕ} (e : Equiv.Perm (Fin n)) : Equiv.Perm (Fin (n + 1))- Defined in
- arXiv:2611.05397 Definition 6
- Verified
- 08 Nov 2026
- Axioms
- none listed
- Used by 3
- heapPermSeqThe r-th permutation in the Heap output sequence of order n, defined for order k + 2 by decomposing r into block index q = r / (k + 1)!…
- heapBlockBaseThe block base permutation for the q-th block of the order-(n + 1) Heap algorithm, defined recursively with the 0-th block base as the…
- heapUnrankThe Heap permutation unranking map heapUnrank assigns to each dimension n : ℕ and factorial-base code d : HeapCode n a permutation of Fin…
Read back from the Lean
Definition of permExtendLast: given an implicit natural number $n$ and a permutation $e$ of $\mathrm{Fin}(n)$, it constructs a permutation of $\mathrm{Fin}(n + 1)$ by composing:
1. finSuccEquiv' (Fin.last n), which identifies $\mathrm{Fin}(n + 1)$ with $\mathrm{Option}(\mathrm{Fin}(n))$ by sending $\mathrm{Fin.last}(n)$ to $\mathrm{none}$ and other elements to $\mathrm{some}(\cdot)$;
2. Equiv.optionCongr e, which acts on $\mathrm{Option}(\mathrm{Fin}(n))$ by fixing $\mathrm{none}$ and applying $e$ to the argument of $\mathrm{some}$;
3. (finSuccEquiv' (Fin.last n)).symm, which maps $\mathrm{Option}(\mathrm{Fin}(n))$ back to $\mathrm{Fin}(n + 1)$.
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
/-- Extend a permutation of Fin n to Fin (n + 1) fixing the last element. -/ def permExtendLast {n : ℕ} (e : Equiv.Perm (Fin n)) : Equiv.Perm (Fin (n + 1)) := (finSuccEquiv' (Fin.last n)).trans ((Equiv.optionCongr e).trans (finSuccEquiv' (Fin.last n)).symm)