group_hash_probe_tail_count_zero_tail
For any finite group G with decidable equality, table size n : ℕ, offset sequence r : Fin n → G, and insertion length t : ℕ, the probe tail count group_hash_probe_tail_count G n r t 0 is equal to (Fintype.card G) ^ (t + 1).
Statement
theorem group_hash_probe_tail_count_zero_tail (G : Type*) [Group G] [Fintype G] [DecidableEq G] (n : ℕ) (r : Fin n → G) (t : ℕ) : group_hash_probe_tail_count G n r t 0 = (Fintype.card G) ^ (t + 1)
- 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 2
- 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…
Read back from the Lean
For any finite group G with decidable equality, any natural number n, any function r : Fin n → G, and any natural number t, the quantity group_hash_probe_tail_count G n r t 0 is equal to (Fintype.card G) ^ (t + 1).
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 0 measures the number of insertion histories and query keys for which the first 0 probe positions are occupied. Because the requirement for indices j < 0 has an impossible premise, it holds vacuously for all keys and insertion sequences. The filtered set is therefore the entire universal set of pairs in (Fin t → G) × G, whose cardinality is |G|^t · |G| = |G|^(t + 1).
The condition defining the probe tail count simplifies to a vacuously true statement for all pairs of insertion histories and query keys.
Unfolding `group_hash_probe_tail_count` expresses the quantity as the cardinality of a filtered subset of pairs (A, q) ∈ (Fin t → G) × G. The filtering condition specifies that for every probe index j : Fin n, if j < 0 then the j-th probe is occupied. Since no natural number is strictly less than 0 (`Nat.not_lt_zero`), the premise is false, so the implication is vacuously true (`false_implies`), reducing the filter condition to `∀ j, True`.
uses
Nat.not_lt_zero,false_impliesunfold group_hash_probe_tail_count simp only [Nat.not_lt_zero, false_implies]
Filtering by a universally true condition reduces the set to the full universal set, leaving the cardinality computation and the universal validity as subgoals.
By `Finset.filter_true_of_mem`, filtering a finite set by a predicate that holds everywhere returns the set itself. Here, this replaces the filtered set with `Finset.univ`, leaving two subgoals: computing the cardinality of `Finset.univ` and verifying that the condition `∀ j, True` holds for every element.
uses
Finset.filter_true_of_memrw [Finset.filter_true_of_mem]The cardinality of the universal set of pairs in (Fin t → G) × G is |G|^(t + 1).
By `Finset.card_univ`, the size of `Finset.univ` is the cardinality of the product type (Fin t → G) × G. Using `Fintype.card_prod` and `Fintype.card_fun`, this factors as |G|^|Fin t| * |G| = |G|^t * |G|. Rewriting with `pow_succ` and commutativity of multiplication (`mul_comm`) simplifies this to |G|^(t + 1), completing the main equality.
uses
Finset.card_univ,Fintype.card_prod,Fintype.card_fun,pow_succ,mul_comm· rw [Finset.card_univ, Fintype.card_prod, Fintype.card_fun] simp [pow_succ, mul_comm]
The filter condition holds for every element of the universal set.
For any element x in the universal set and any index j : Fin n, the statement to check is simply `True`, which holds trivially.
· intro x _; simp
Nat.not_lt_zero- No natural number is strictly less than 0.
false_implies- An implication whose premise is false is logically equivalent to true.
Finset.filter_true_of_mem- Filtering a finite set by a predicate that holds for all of its members leaves the set unchanged.
Finset.card_univ- The cardinality of the universal finset of a finite type is the cardinality of the type itself.
Fintype.card_prod- The cardinality of a product type α × β is the product of the cardinalities of α and β.
Fintype.card_fun- The cardinality of the function type α → β is the cardinality of β raised to the cardinality of α.
pow_succ- For any element a and natural number n, a^(n + 1) = a^n * a.
mul_comm- Multiplication is commutative: a * b = b * a.
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 threshold 0 equals the total number of insertion histories and query keys. -/theorem group_hash_probe_tail_count_zero_tail (G : Type*) [Group G] [Fintype G] [DecidableEq G] (n : ℕ) (r : Fin n → G) (t : ℕ) : group_hash_probe_tail_count G n r t 0 = (Fintype.card G) ^ (t + 1) := by unfold group_hash_probe_tail_count simp only [Nat.not_lt_zero, false_implies] rw [Finset.filter_true_of_mem] · rw [Finset.card_univ, Fintype.card_prod, Fintype.card_fun] simp [pow_succ, mul_comm] · intro x _; simp