group_hash_insert_step
Given 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 a : G, group_hash_insert_step n r T a is the updated set of occupied slots in Finset G obtained by adding a * r j to T for the minimal index j : Fin n such that a * r j ∉ T, or returning T unchanged if no such candidate index exists.
Statement
def group_hash_insert_step {G : Type*} [Group G] [DecidableEq G] (n : ℕ) (r : Fin n → G) (T : Finset G) (a : G) : Finset G
- Defined in
- arXiv:2610.31363; OP-808
- Verified
- 01 Nov 2026
- Axioms
- none listed
- Used by 2
- 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…
- 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…
Read back from the Lean
Given a group G with decidable equality, a natural number n, a function r : Fin n → G, a finite set T : Finset G, and an element a : G, group_hash_insert_step n r T a is the finite set of elements of G defined as follows: let candidates be the finite set of all indices j : Fin n such that a * r j ∉ T. If candidates is nonempty, return T ∪ {a * r j_min}, where j_min is the minimum element of candidates under the standard linear order on Fin n. Otherwise (if candidates is empty, i.e., a * r j ∈ T for all j : Fin n), return T.
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
/-- Insertion step of open addressing hash table on a finite group G using offset sequence r. -/ def group_hash_insert_step {G : Type*} [Group G] [DecidableEq G] (n : ℕ) (r : Fin n → G) (T : Finset G) (a : G) : Finset G := let candidates := Finset.univ.filter (fun j : Fin n => a * r j ∉ T) if h : candidates.Nonempty then T ∪ {a * r (candidates.min' h)} else T