AFTD Auto-Formalizing Theoretical Domains

heap_final_perm

def

The permutation of Fin m induced by the final arrangement array of the order-m Heap algorithm.

Statement

def heap_final_perm (m : ℕ) : Equiv.Perm (Fin m)
Defined in
arXiv:2611.05397 Definition 3 and Theorem 5
Verified
05 Nov 2026
Axioms
none listed
Used by 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…

Read back from the Lean

heap_final_perm defines a function mapping each natural number m : ℕ to a permutation of Fin m (Equiv.Perm (Fin m)), given by cases: 1. If m % 2 = 1 ∧ 3 ≤ m (i.e., m is odd and m ≥ 3), it is the swap (transposition) of 0 and m - 1. 2. Otherwise, if 4 ≤ m (i.e., m is even and m ≥ 4), it is the cyclic permutation List.formPerm on the list whose first element is 0, followed by mid (the elements m - 3, m - 4, ..., 1 obtained by reversing List.range (m - 3) and adding 1 to each element), followed by m - 2 and m - 1. 3. Otherwise, if m = 2, it is the swap (transposition) of 0 and 1. 4. Otherwise (i.e., m = 0 or m = 1), it is the identity permutation 1 on Fin m.

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 permutation of `Fin m` induced by the final arrangement array of the order-`m` Heap algorithm. -/
def heap_final_perm (m : ℕ) : Equiv.Perm (Fin m) :=
  if hm : m % 2 = 1 ∧ 3 ≤ m then
    Equiv.swap ⟨0, by omega⟩ ⟨m - 1, by omega⟩
  else if h4 : 4 ≤ m then
    let zero : Fin m := ⟨0, by omega⟩
    let mid : List (Fin m) := ((List.range (m - 3)).reverse.filterMap (fun i =>
      if hi : i + 1 < m then some ⟨i + 1, hi⟩ else none))
    let penultimate : Fin m := ⟨m - 2, by omega⟩
    let last : Fin m := ⟨m - 1, by omega⟩
    List.formPerm (zero :: (mid ++ [penultimate, last]))
  else if hm2 : m = 2 then
    Equiv.swap ⟨0, by omega⟩ ⟨1, by omega⟩
  else
    1
See it in the graphDiscuss this resultChallenge it