group_hash_probe_tail_count_t_zero_succ
For any finite group G with decidable equality, table size n : ℕ with 0 < n, offset sequence r : Fin n → G, and natural number c, the probe tail count when inserting into an empty table group_hash_probe_tail_count G n r 0 (c + 1) is equal to 0.
Statement
theorem group_hash_probe_tail_count_t_zero_succ (G : Type*) [Group G] [Fintype G] [DecidableEq G] (n : ℕ) (r : Fin n → G) (c : ℕ) (hn : 0 < n) : group_hash_probe_tail_count G n r 0 (c + 1) = 0
- Source
- arXiv:2610.31363: A Sharp Analysis of Fixed Offset Hash Tables, serving OP-808
- Verified
- 02 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 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_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…
- 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…
Read back from the Lean
For any finite group $G$ with decidable equality, any natural number $n$, any probe sequence $r : \mathrm{Fin}\ n \to G$, and any natural number $c$, if $0 < n$, then group_hash_probe_tail_count G n r 0 (c + 1) = 0.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The probe tail count for threshold c + 1 counts the number of pairs (A, q) of an insertion sequence of length t and a query element q whose first c + 1 probes all hit occupied slots. When t = 0, no elements have been inserted, so the table has no occupied slots. Because c + 1 > 0, the condition requires the 0-th probe to hit an occupied slot, which is impossible in an empty table; hence no such pairs exist and the count is 0.
The probe tail count is zero if and only if no configuration (A, q) satisfies the condition that its first c + 1 probe slots are occupied.
Unfolding `group_hash_probe_tail_count`, the tail count is defined as the cardinality of the filtered set of pairs (A, q) whose first c + 1 probes hit occupied slots. A finite set has cardinality zero if and only if it is empty (`Finset.card_eq_zero`), and a filtered set is empty if and only if no element satisfies the filtering condition (`Finset.filter_eq_empty_iff`).
uses
Finset.card_eq_zero,Finset.filter_eq_empty_iffunfold group_hash_probe_tail_count simp only [Finset.card_eq_zero, Finset.filter_eq_empty_iff]
Assuming such a pair (A, q) exists, its initial probe slot q * r(0) must be occupied in the hash table.
Assume for contradiction that there is a pair x = (A, q) satisfying the probe condition h. Because the table size n is positive (0 < n), index 0 is a valid table slot index ⟨0, hn⟩ ∈ Fin n. Since the probe threshold c + 1 is positive (0 < c + 1 by `Nat.succ_pos`), instantiating h at index 0 implies that the 0-th probe slot q * r(0) must be in the set of occupied slots.
uses
Nat.succ_posintro x hx h have hmem := h ⟨0, hn⟩ (Nat.succ_pos c)
A contradiction is reached because an empty table has no occupied slots. automation
The table has length t = 0, so the sequence of inserted elements A : Fin 0 → G forms an empty list List.ofFn A. By definition of `group_hash_occupied_slots`, an empty list leaves the set of occupied slots empty (∅). The derived membership q * r(0) ∈ ∅ simplifies to False, closing the goal.
simp [group_hash_occupied_slots] at hmem
Finset.card_eq_zero- A finite set has cardinality 0 if and only if it is the empty set.
Finset.filter_eq_empty_iff- Filtering a finite set by a predicate yields the empty set if and only if no element of the set satisfies the predicate.
Nat.succ_pos- The successor of any natural number is strictly positive (0 < n + 1).
- In line 9, `simp` unfolds the definition of `group_hash_occupied_slots` on `List.ofFn x.1`, which evaluates to `∅` because `x.1 : Fin 0 → G` represents an empty sequence, and automatically derives `False` from the impossible membership in `∅`.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- The probe tail count for positive threshold when inserting into an empty table is 0. -/theorem group_hash_probe_tail_count_t_zero_succ (G : Type*) [Group G] [Fintype G] [DecidableEq G] (n : ℕ) (r : Fin n → G) (c : ℕ) (hn : 0 < n) : group_hash_probe_tail_count G n r 0 (c + 1) = 0 := by unfold group_hash_probe_tail_count simp only [Finset.card_eq_zero, Finset.filter_eq_empty_iff] intro x hx h have hmem := h ⟨0, hn⟩ (Nat.succ_pos c) simp [group_hash_occupied_slots] at hmem