AFTD Auto-Formalizing Theoretical Domains

heapBlockBase

def

The 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 identity, and the (q + 1)-th obtained from the q-th by composing with the tail-extended final permutation of order n and the block transition swap.

Statement

def heapBlockBase (n : ℕ) : ℕ → Equiv.Perm (Fin (n + 1))
Defined in
arXiv:2611.05397 Definition 7
Verified
08 Nov 2026
Axioms
none listed
Built on 3
  • heapBlockSwapThe top-level transposition swap between block j and block j + 1 in the order-(n + 1) Heap algorithm, which for j < n swaps the trailing…
  • permExtendLastThe canonical extension of a permutation of Fin n to a permutation of Fin (n + 1) that fixes the trailing element Fin.last n.
  • heap_final_permThe permutation of Fin m induced by the final arrangement array of the order-m Heap algorithm.
Used by 2
  • 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)!…
  • 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

heapBlockBase is a function that takes a natural number n : ℕ and recursively defines a sequence of permutations of Fin (n + 1) indexed by q : ℕ: - Base case: heapBlockBase n 0 is the identity permutation on Fin (n + 1). - Inductive step: heapBlockBase n (q + 1) is the group product heapBlockBase n q * permExtendLast (heap_final_perm n) * heapBlockSwap n q in Equiv.Perm (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

/-- The block base permutation C_{n+1, q} of the order-(n + 1) Heap algorithm. -/
def heapBlockBase (n : ℕ) : ℕ → Equiv.Perm (Fin (n + 1))
  | 0 => 1
  | q + 1 => heapBlockBase n q * permExtendLast (heap_final_perm n) * heapBlockSwap n q
See it in the graphDiscuss this resultChallenge it