group_hash_probe_tail_count
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
- 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
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