AFTD Auto-Formalizing Theoretical Domains

group_hash_probe_tail_count

def

Given a finite group G with decidable equality, a table size n : ℕ, an offset sequence r : Fin n → G, and natural numbers t and c, group_hash_probe_tail_count G n r t c is the cardinality of the finset of pairs (A, q) in (Fin t → G) × G such that for all j : Fin n with (j : ℕ) < c, q * r j belongs to group_hash_occupied_slots n r (List.ofFn A).

Statement

def group_hash_probe_tail_count (G : Type*) [Group G] [Fintype G] [DecidableEq G]
    (n : ℕ) (r : Fin n → G) (t c : ℕ) : ℕ
Defined in
arXiv:2610.31363: A Sharp Analysis of Fixed Offset Hash Tables
Verified
01 Nov 2026
Axioms
none listed
Built on 1
  • group_hash_occupied_slotsThe set of occupied slots in Finset G after sequentially inserting a list of keys A : List G into an initially empty hash table on group G…
Used by 2

Read back from the Lean

group_hash_probe_tail_count G n r t c defines the number (cardinality) of pairs (A, q) ∈ (Fin t → G) × G (where G is a finite group with decidable equality, n, t, c : ℕ, and r : Fin n → G) such that for every probe index j : Fin n with (j : ℕ) < c, the element q * r j belongs to group_hash_occupied_slots n r (List.ofFn A).

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 number of insertion histories and query keys requiring strictly more than c probes. -/
def group_hash_probe_tail_count (G : Type*) [Group G] [Fintype G] [DecidableEq G]
    (n : ℕ) (r : Fin n → G) (t c : ℕ) : ℕ :=
  ((Finset.univ : Finset ((Fin t → G) × G)).filter fun (A, q) =>
    ∀ j : Fin n, (j : ℕ) < c → q * r j ∈ group_hash_occupied_slots n r (List.ofFn A)).card
See it in the graphDiscuss this resultChallenge it