AFTD Auto-Formalizing Theoretical Domains

group_hash_occupied_slots

def

The 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 of size n using offset sequence r : Fin n → G.

Statement

def group_hash_occupied_slots {G : Type*} [Group G] [DecidableEq G]
    (n : ℕ) (r : Fin n → G) (A : List G) : Finset G
Defined in
arXiv:2610.31363; OP-808
Verified
01 Nov 2026
Axioms
none listed
Built on 1
  • group_hash_insert_stepGiven a group G with decidable equality, table size n, offset sequence r : Fin n → G, a finite set of occupied slots T : Finset G, and key…
Used by 3
  • group_hash_probe_tail_countGiven 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_zero_tailFor any finite group G with decidable equality, table size n : ℕ, offset sequence r : Fin n → G, and insertion length t : ℕ, the probe…
  • group_hash_probe_tail_count_t_zero_succFor any finite group G with decidable equality, table size n : ℕ with 0 < n, offset sequence r : Fin n → G, and natural number c, the…

Read back from the Lean

For a group $G$ with decidable equality, a natural number $n$, a family of group elements $r : \mathrm{Fin}\ n \to G$, and a list of elements $A$ in $G$, group_hash_occupied_slots n r A is defined as the finite set of elements in $G$ obtained by left-folding group_hash_insert_step n r over the list $A$, starting with the empty set $\emptyset$.

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

/-- Set of occupied slots after sequentially inserting a list of keys A into an initially empty group hash table. -/
def group_hash_occupied_slots {G : Type*} [Group G] [DecidableEq G]
    (n : ℕ) (r : Fin n → G) (A : List G) : Finset G := A.foldl (group_hash_insert_step n r) ∅
See it in the graphDiscuss this resultChallenge it