AFTD Auto-Formalizing Theoretical Domains

heapUnrank

def

The Heap permutation unranking map heapUnrank assigns to each dimension n : ℕ and factorial-base code d : HeapCode n a permutation of Fin n. For n = 0 and n = 1, it returns the identity permutation 1. For n = k + 2, it returns the group product heapBlockBase (k + 1) q * permExtendLast (heapUnrank (k + 1) prefixCode) with the block base permutation on the left and the tail-extended recursive unrank on the right, where q = (d ⟨k, by omega⟩).val : ℕ and prefixCode : HeapCode (k + 1) is defined by prefixCode i = d ⟨i.val, by omega⟩.

Statement

def heapUnrank : (n : ℕ) → HeapCode n → Equiv.Perm (Fin n)
Defined in
arXiv:2611.05397 Definition 8
Verified
08 Nov 2026
Axioms
none listed
Built on 3
  • 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…
  • permExtendLastThe canonical extension of a permutation of Fin n to a permutation of Fin (n + 1) that fixes the trailing element Fin.last n.
  • HeapCodeThe mixed-radix factorial-base code space for permutations of order n, consisting of tuples d where d_i ranges from 0 to i + 1 for each i…

Read back from the Lean

heapUnrank is a recursive definition that takes a natural number n : ℕ and a code d : HeapCode n, and produces a permutation of Fin n (Equiv.Perm (Fin n)): 1. **Base case n = 0:** returns the identity permutation 1 on Fin 0. 2. **Base case n = 1:** returns the identity permutation 1 on Fin 1. 3. **Inductive step n = k + 2:** given d : HeapCode (k + 2): - defines prefixCode : HeapCode (k + 1) by restricting d to Fin k (i.e., fun i => d ⟨i.val, _⟩), - defines q : ℕ as the value (d ⟨k, _⟩).val, - returns the permutation product heapBlockBase (k + 1) q * permExtendLast (heapUnrank (k + 1) prefixCode) in Equiv.Perm (Fin (k + 2)).

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 Heap permutation unranking map from factorial-base codes to permutations. -/
def heapUnrank : (n : ℕ) → HeapCode n → Equiv.Perm (Fin n)
  | 0, _ => 1
  | 1, _ => 1
  | k + 2, d =>
    let prefixCode : HeapCode (k + 1) := fun i => d ⟨i.val, by omega⟩
    let q : ℕ := (d ⟨k, by omega⟩).val
    heapBlockBase (k + 1) q * permExtendLast (heapUnrank (k + 1) prefixCode)
See it in the graphDiscuss this resultChallenge it