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) ∅