AFTD Auto-Formalizing Theoretical Domains

flag_hash_offset

def

Given a group G, a natural number k, prime quotient orders p : Fin k → ℕ, a prime composition series series : GroupPrimeCompositionSeries G k p, flag representatives reps : FlagRepresentatives series, and an index j : Fin (∏ i : Fin k, p i), flag_hash_offset reps j is the product in G in reverse order (from k - 1 down to 0) of reps.g i (d i) for i : Fin k, where each digit d i : Fin (p i) has value (j.val / ∏ a ∈ Finset.univ.filter (fun a : Fin k => a < i), p a) % p i.

Statement

def flag_hash_offset {G : Type*} [Group G] {k : ℕ} {p : Fin k → ℕ}
    {series : GroupPrimeCompositionSeries G k p} (reps : FlagRepresentatives series)
    (j : Fin (∏ i : Fin k, p i)) : G
Defined in
arXiv:2610.31363: A Sharp Analysis of Fixed Offset Hash Tables
Verified
01 Nov 2026
Axioms
none listed
Built on 2
  • GroupPrimeCompositionSeriesA prime composition series of length k for group G with prime quotient orders p : Fin k → ℕ is a chain of subgroups H_0 = ⊥ ≤ ... ≤ H_k =…
  • FlagRepresentativesFor a prime composition series series, FlagRepresentatives bundles a family of group elements g : (i : Fin k) → Fin (p i) → G such that…
Used by 1
  • flag_hash_offset_zeroFor any group G, natural number k, prime quotient orders p : Fin k → ℕ, prime composition series series : GroupPrimeCompositionSeries G k…

Read back from the Lean

Given a group G, a natural number k, a sequence of natural numbers p : Fin k → ℕ, a composition series series : GroupPrimeCompositionSeries G k p, a set of representatives reps : FlagRepresentatives series, and an index j : Fin (∏ i : Fin k, p i), flag_hash_offset reps j defines the element of G obtained by: 1. Decomposing j into mixed-radix digits d i : Fin (p i) for each i : Fin k, where (d i).val = (j.val / ∏ a < i, p a) % p i. 2. Evaluating reps.g i (d i) for each i : Fin k. 3. Forming the list [reps.g 0 (d 0), reps.g 1 (d 1), ..., reps.g (k - 1) (d (k - 1))], reversing it to [reps.g (k - 1) (d (k - 1)), ..., reps.g 0 (d 0)], and computing its product in G, yielding reps.g (k - 1) (d (k - 1)) * ... * reps.g 0 (d 0) (or 1 if k = 0).

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 offset sequence element in a solvable group flag hash table defined by mixed-radix digits. -/
def flag_hash_offset {G : Type*} [Group G] {k : ℕ} {p : Fin k → ℕ}
    {series : GroupPrimeCompositionSeries G k p} (reps : FlagRepresentatives series)
    (j : Fin (∏ i : Fin k, p i)) : G :=
  let d (i : Fin k) : Fin (p i) :=
    ⟨(j.val / ∏ a ∈ Finset.univ.filter (fun (a : Fin k) => a < i), p a) % p i,
     Nat.mod_lt _ (series.prime i).pos⟩
  (List.ofFn (fun i : Fin k => reps.g i (d i))).reverse.prod
See it in the graphDiscuss this resultChallenge it