prime_fixed_offset_linear_probe_tail_prob_interior_t_pred
At load t = p - 1 (one empty slot), every bijective offset sequence has identical probe tail probabilities, matching linear probing.
Statement
theorem prime_fixed_offset_linear_probe_tail_prob_interior_t_pred
(p : ℕ) [Fact (Nat.Prime p)]
(r : Fin p → ZMod p) (hr_bij : Function.Bijective r) (hr0 : r 0 = 0)
(k : ℕ) (hk2 : 2 ≤ k) (hkt : k ≤ p - 1) (ht : p - 1 < p) :
hash_probe_tail_prob p r (p - 1) k ≤ hash_probe_tail_prob p (linear_probe_offset p) (p - 1) k- Source
- step towards prime_fixed_offset_linear_probe_tail_prob_interior_le
- Verified
- 02 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- hash_probe_tail_probFor a table size n with [NeZero n], an offset sequence r : Fin n → ZMod n, and natural numbers t and k, hash_probe_tail_prob n r t k is…
- linear_probe_offsetGiven a natural number n, linear_probe_offset n is the function from Fin n to ZMod n that maps each index j : Fin n to its canonical…
- hash_probe_tail_countThe number of pairs of an insertion sequence of length t and an additional query slot whose insertion cost under offset sequence r…
- hash_occupied_slots_cardFor any table size n with [NeZero n], any bijective offset sequence r : Fin n → ZMod n, and any list of keys A with length at most n, the…
- hash_occupied_slotsThe set of occupied slots in Finset (ZMod n) after sequentially inserting a list A : List (ZMod n) into an initially empty hash table of…
The proof, explained
At load t = p - 1, exactly one slot e of the table is empty. For any fixed set of p - 1 occupied slots, an initial probe slot q needs at least k probes if and only if none of the first k probes land on e, which forbids exactly k distinct starting positions {e - r(j) | j < k} by injectivity of r, leaving p - k valid start positions. Summing over all insertion sequences, the tail count is identically ∑_A (p - k) for any bijective offset sequence, matching linear probing exactly. Consequently, the probe tail probabilities are equal, establishing the inequality.
The complement of the occupied slots occ contains exactly one slot e ∈ ZMod n, so occᶜ = {e}.
The table has size n, and the occupied set has cardinality n - 1. Its complement therefore has cardinality n - (n - 1) = 1, meaning there is a unique unoccupied slot e.
uses
Finset.card_univ,ZMod.card,Finset.card_compl,Nat.pos_of_ne_zero,NeZero.ne,Finset.card_eq_one.mphave hcard_univ : (Finset.univ : Finset (ZMod n)).card = n := by rw [Finset.card_univ, ZMod.card] have hcompl : occᶜ.card = 1 := by rw [Finset.card_compl, ZMod.card, hocc] have hp : 0 < n := Nat.pos_of_ne_zero (NeZero.ne n) omega obtain ⟨e, he⟩ := Finset.card_eq_one.mp hcompl
A slot x is occupied if and only if x ≠ e.
Since occᶜ = {e}, an element x is outside occ if and only if x = e. Taking the contrapositive gives x ∈ occ ↔ x ≠ e.
uses
Finset.mem_compl,Finset.mem_singletonhave hmem : ∀ x : ZMod n, x ∈ occ ↔ x ≠ e := by intro x have hx : x ∈ occᶜ ↔ x ∈ ({e} : Finset (ZMod n)) := by rw [he] simp only [Finset.mem_compl, Finset.mem_singleton] at hx constructor · intro h1 h2; exact (hx.mpr h2) h1 · intro h1; by_contra h2; exact h1 (hx.mp h2)
The set of query starting slots q whose first k probes all land in occ is the complement of B = {e - r(j) | j ∈ Fin n, j < k}.
A query starting at q has q + r(j) ∈ occ for all j < k if and only if q + r(j) ≠ e for all j < k, which is equivalent to q ≠ e - r(j) for all j < k. Thus, q avoids exactly the set of offsets B subtracted from e.
uses
Finset.mem_filter,Finset.mem_sdiff,Finset.mem_univ,true_and,Finset.mem_imageset J : Finset (Fin n) := Finset.univ.filter (fun j : Fin n => j.val < k) with hJ set B : Finset (ZMod n) := J.image (fun j => e - r j) with hB have hS : (Finset.univ.filter (fun q : ZMod n => ∀ j : Fin n, j.val < k → q + r j ∈ occ)) = (Finset.univ : Finset (ZMod n)) \ B := by ext q simp only [Finset.mem_filter, Finset.mem_sdiff, Finset.mem_univ, true_and] constructor · intro h hqB rw [hB, hJ, Finset.mem_image] at hqB obtain ⟨j, hj, hq⟩ := hqB rw [Finset.mem_filter] at hj obtain ⟨-, hjk⟩ := hj have hconj : q + r j = e := by rw [← hq]; abel exact (hmem _).mp (h j hjk) hconj · intro hqB j hjk rw [hmem] intro hq_eq apply hqB rw [hB, hJ, Finset.mem_image] exact ⟨j, by rw [Finset.mem_filter]; exact ⟨Finset.mem_univ _, hjk⟩, by rw [← hq_eq]; abel⟩
The number of starting slots q requiring at least k probes is exactly n - k.
Because r is injective, the map j ↦ e - r(j) is injective, so |B| = |{j : Fin n | j < k}| = min(n, k) = k. The number of qualifying start slots is the size of the complement (ZMod n) \ B, which is n - |B| = n - k.
uses
Finset.card_sdiff,Finset.inter_univ,Finset.card_image_of_injective,Fin.card_filter_val_lt,Nat.min_eq_right,congrArgrw [hS, Finset.card_sdiff, Finset.inter_univ, hcard_univ] have hBcard : B.card = k := by rw [hB, Finset.card_image_of_injective _ ?_] · rw [hJ, Fin.card_filter_val_lt, Nat.min_eq_right (by omega)] · intro j1 j2 h simp only at h have h' : r j1 = r j2 := by have := congrArg (fun x => e - x) h simpa using this exact hr h' rw [hBcard]
For any bijective offset sequence r, the probe tail count hash_probe_tail_count n r (n - 1) k equals ∑_A (n - k) over all insertion sequences A.
We express the tail count as a sum over insertion sequences A of length n - 1 and start slots q. For every sequence A, inserting n - 1 elements with a bijective offset sequence occupies exactly n - 1 slots. By the probe fiber cardinality lemma, exactly n - k starting slots q satisfy the condition for each A, making the sum identically ∑_A (n - k).
uses
Finset.card_eq_sum_ones,Finset.sum_filter,Fintype.sum_prod_type,Finset.sum_congr,Finset.card_filter,prime_fixed_offset_linear_probe_tail_prob_interior_t_pred_probe_fiber_card,hash_occupied_slots_cardhave h1 : hash_probe_tail_count n r (n - 1) k = ∑ x : (Fin (n - 1) → ZMod n) × ZMod n, (if (∀ j : Fin n, j.val < k → x.2 + r j ∈ hash_occupied_slots n r (List.ofFn x.1)) then (1:ℕ) else 0) := by rw [hash_probe_tail_count, Finset.card_eq_sum_ones, Finset.sum_filter] rw [h1, Fintype.sum_prod_type] refine Finset.sum_congr rfl (fun A _ => ?_) rw [← Finset.card_filter] exact prime_fixed_offset_linear_probe_tail_prob_interior_t_pred_probe_fiber_card n r hr.injective _ (by rw [hash_occupied_slots_card n r hr (List.ofFn A) (by simp)] simp) k hk
Linear probing offset function linear_probe_offset p is injective.
If j₁ and j₂ in Fin p have j₁ ≡ j₂ (mod p), then since j₁, j₂ < p, their remainders modulo p are their actual values, giving j₁ = j₂.
uses
ZMod.natCast_eq_natCast_iff',Nat.mod_eq_of_lt,Fin.extintro j1 j2 h simp only [linear_probe_offset] at h have h' : (j1.val : ℕ) % p = (j2.val : ℕ) % p := (ZMod.natCast_eq_natCast_iff' _ _ _).mp h rw [Nat.mod_eq_of_lt j1.isLt, Nat.mod_eq_of_lt j2.isLt] at h' exact Fin.ext h'
Linear probing offset function linear_probe_offset p is bijective.
An injective map between two finite sets of the same cardinality p is bijective.
uses
Fintype.bijective_iff_injective_and_card,prime_fixed_offset_linear_probe_tail_prob_interior_t_pred_linear_probe_injective,ZMod.cardrw [Fintype.bijective_iff_injective_and_card] exact ⟨prime_fixed_offset_linear_probe_tail_prob_interior_t_pred_linear_probe_injective p, by simp [ZMod.card]⟩
The probe tail count for r equals the probe tail count for linear probing.
Both r and the linear probing offset sequence are bijective maps on Fin p. Therefore, by the common tail count lemma, both tail counts evaluate to the exact same sum ∑_A (p - k).
uses
prime_fixed_offset_linear_probe_tail_prob_interior_t_pred_tail_count_common,prime_fixed_offset_linear_probe_tail_prob_interior_t_pred_linear_probe_bijectivehave h_eq : hash_probe_tail_count p r (p - 1) k = hash_probe_tail_count p (linear_probe_offset p) (p - 1) k := by rw [prime_fixed_offset_linear_probe_tail_prob_interior_t_pred_tail_count_common p r hr_bij k hkt, prime_fixed_offset_linear_probe_tail_prob_interior_t_pred_tail_count_common p (linear_probe_offset p) (prime_fixed_offset_linear_probe_tail_prob_interior_t_pred_linear_probe_bijective p) k hkt]
The probe tail probability for r is bounded by that of linear probing.
By definition, hash_probe_tail_prob divides the tail count by p^(t + 1). Since the tail counts for r and linear probing are equal, the resulting probabilities are equal, which implies the inequality ≤.
unfold hash_probe_tail_prob rw [h_eq]
Finset.card_univ- The cardinality of the universal finset of a finite type equals the cardinality of the type.
ZMod.card- The cardinality of the finite ring ZMod n is n.
Finset.card_compl- The cardinality of the complement of a subset s is the cardinality of the universe minus the cardinality of s.
Nat.pos_of_ne_zero- A natural number that is nonzero is strictly positive.
NeZero.ne- An element of a type with a NeZero instance is not equal to zero.
Finset.card_eq_one.mp- A finset with cardinality 1 is a singleton containing a unique element.
Finset.mem_compl- An element belongs to the complement of a finset if and only if it does not belong to the finset.
Finset.mem_singleton- An element belongs to a singleton {a} if and only if it equals a.
Finset.mem_filter- An element belongs to the filter of a finset by a predicate if and only if it belongs to the finset and satisfies the predicate.
Finset.mem_sdiff- An element belongs to the set difference s \ t if and only if it belongs to s and does not belong to t.
Finset.mem_univ- Every element of a finite type belongs to its universal finset.
true_and- The conjunction of True and p is logically equivalent to p.
Finset.mem_image- An element b belongs to the image f(s) if and only if there exists a ∈ s with f(a) = b.
Finset.card_sdiff- The cardinality of the set difference t \ s equals |t| - |s ∩ t|.
Finset.inter_univ- The intersection of any finset with the universal finset is the finset itself.
Finset.card_image_of_injective- The image of a finset under an injective function has the same cardinality as the finset.
Fin.card_filter_val_lt- The number of elements in Fin n whose natural value is strictly less than m is min(n, m).
Nat.min_eq_right- If b ≤ a, then the minimum min(a, b) equals b.
congrArg- Applying the same function to equal arguments produces equal results.
Finset.card_eq_sum_ones- The cardinality of a finset equals the sum of 1 over all its elements.
Finset.sum_filter- Summing a function over a filtered finset equals summing over the whole finset with an indicator condition.
Fintype.sum_prod_type- A sum over a product type α₁ × α₂ can be evaluated as an iterated sum.
Finset.sum_congr- Sums over equal sets with equal terms are equal.
Finset.card_filter- The cardinality of a filtered subset equals the sum over the finset of the indicator of the condition.
prime_fixed_offset_linear_probe_tail_prob_interior_t_pred_probe_fiber_card- For an injective offset function on a table of size n, any occupied set of size n - 1, and k ≤ n - 1, exactly n - k starting slots have their first k probes all land in occupied slots.
hash_occupied_slots_card- For any bijective offset sequence, inserting A elements into an empty table of size n occupies exactly |A| slots (provided |A| ≤ n).
ZMod.natCast_eq_natCast_iff'- Two natural numbers have the same canonical image in ZMod c if and only if they have the same remainder modulo c.
Nat.mod_eq_of_lt- If a < b, then the remainder a mod b is equal to a.
Fin.ext- Two elements of Fin n are equal if their underlying natural values are equal.
Fintype.bijective_iff_injective_and_card- A function between finite types of equal cardinality is bijective if and only if it is injective.
prime_fixed_offset_linear_probe_tail_prob_interior_t_pred_linear_probe_injective- The linear probing offset function j ↦ (j : ZMod p) on Fin p is injective.
prime_fixed_offset_linear_probe_tail_prob_interior_t_pred_tail_count_common- For any bijective offset sequence and k ≤ n - 1, the probe tail count at load n - 1 is identically ∑_A (n - k).
prime_fixed_offset_linear_probe_tail_prob_interior_t_pred_linear_probe_bijective- The linear probing offset function on Fin p is bijective.
- Although the theorem conclusion is stated as an inequality ≤, the probe tail probabilities for any bijective offset sequence and linear probing are in fact identical at load t = p - 1.
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.
private lemma prime_fixed_offset_linear_probe_tail_prob_interior_t_pred_probe_fiber_card (n : ℕ) [NeZero n] (r : Fin n → ZMod n) (hr : Function.Injective r) (occ : Finset (ZMod n)) (hocc : occ.card = n - 1) (k : ℕ) (hk : k ≤ n - 1) : (Finset.univ.filter (fun q : ZMod n => ∀ j : Fin n, j.val < k → q + r j ∈ occ)).card = n - k := by have hcard_univ : (Finset.univ : Finset (ZMod n)).card = n := by rw [Finset.card_univ, ZMod.card] have hcompl : occᶜ.card = 1 := by rw [Finset.card_compl, ZMod.card, hocc] have hp : 0 < n := Nat.pos_of_ne_zero (NeZero.ne n) omega obtain ⟨e, he⟩ := Finset.card_eq_one.mp hcompl have hmem : ∀ x : ZMod n, x ∈ occ ↔ x ≠ e := by intro x have hx : x ∈ occᶜ ↔ x ∈ ({e} : Finset (ZMod n)) := by rw [he] simp only [Finset.mem_compl, Finset.mem_singleton] at hx constructor · intro h1 h2; exact (hx.mpr h2) h1 · intro h1; by_contra h2; exact h1 (hx.mp h2) set J : Finset (Fin n) := Finset.univ.filter (fun j : Fin n => j.val < k) with hJ set B : Finset (ZMod n) := J.image (fun j => e - r j) with hB have hS : (Finset.univ.filter (fun q : ZMod n => ∀ j : Fin n, j.val < k → q + r j ∈ occ)) = (Finset.univ : Finset (ZMod n)) \ B := by ext q simp only [Finset.mem_filter, Finset.mem_sdiff, Finset.mem_univ, true_and] constructor · intro h hqB rw [hB, hJ, Finset.mem_image] at hqB obtain ⟨j, hj, hq⟩ := hqB rw [Finset.mem_filter] at hj obtain ⟨-, hjk⟩ := hj have hconj : q + r j = e := by rw [← hq]; abel exact (hmem _).mp (h j hjk) hconj · intro hqB j hjk rw [hmem] intro hq_eq apply hqB rw [hB, hJ, Finset.mem_image] exact ⟨j, by rw [Finset.mem_filter]; exact ⟨Finset.mem_univ _, hjk⟩, by rw [← hq_eq]; abel⟩ rw [hS, Finset.card_sdiff, Finset.inter_univ, hcard_univ] have hBcard : B.card = k := by rw [hB, Finset.card_image_of_injective _ ?_] · rw [hJ, Fin.card_filter_val_lt, Nat.min_eq_right (by omega)] · intro j1 j2 h simp only at h have h' : r j1 = r j2 := by have := congrArg (fun x => e - x) h simpa using this exact hr h' rw [hBcard]private lemma prime_fixed_offset_linear_probe_tail_prob_interior_t_pred_tail_count_common (n : ℕ) [NeZero n] (r : Fin n → ZMod n) (hr : Function.Bijective r) (k : ℕ) (hk : k ≤ n - 1) : hash_probe_tail_count n r (n - 1) k = ∑ _A : Fin (n - 1) → ZMod n, (n - k) := by have h1 : hash_probe_tail_count n r (n - 1) k = ∑ x : (Fin (n - 1) → ZMod n) × ZMod n, (if (∀ j : Fin n, j.val < k → x.2 + r j ∈ hash_occupied_slots n r (List.ofFn x.1)) then (1:ℕ) else 0) := by rw [hash_probe_tail_count, Finset.card_eq_sum_ones, Finset.sum_filter] rw [h1, Fintype.sum_prod_type] refine Finset.sum_congr rfl (fun A _ => ?_) rw [← Finset.card_filter] exact prime_fixed_offset_linear_probe_tail_prob_interior_t_pred_probe_fiber_card n r hr.injective _ (by rw [hash_occupied_slots_card n r hr (List.ofFn A) (by simp)] simp) k hkprivate lemma prime_fixed_offset_linear_probe_tail_prob_interior_t_pred_linear_probe_injective (p : ℕ) [NeZero p] : Function.Injective (linear_probe_offset p) := by intro j1 j2 h simp only [linear_probe_offset] at h have h' : (j1.val : ℕ) % p = (j2.val : ℕ) % p := (ZMod.natCast_eq_natCast_iff' _ _ _).mp h rw [Nat.mod_eq_of_lt j1.isLt, Nat.mod_eq_of_lt j2.isLt] at h' exact Fin.ext h'private lemma prime_fixed_offset_linear_probe_tail_prob_interior_t_pred_linear_probe_bijective (p : ℕ) [NeZero p] : Function.Bijective (linear_probe_offset p) := by rw [Fintype.bijective_iff_injective_and_card] exact ⟨prime_fixed_offset_linear_probe_tail_prob_interior_t_pred_linear_probe_injective p, by simp [ZMod.card]⟩/-- At load t = p - 1 (one empty slot), every bijective offset sequence has identical probe tail probabilities, matching linear probing. -/theorem prime_fixed_offset_linear_probe_tail_prob_interior_t_pred (p : ℕ) [Fact (Nat.Prime p)] (r : Fin p → ZMod p) (hr_bij : Function.Bijective r) (hr0 : r 0 = 0) (k : ℕ) (hk2 : 2 ≤ k) (hkt : k ≤ p - 1) (ht : p - 1 < p) : hash_probe_tail_prob p r (p - 1) k ≤ hash_probe_tail_prob p (linear_probe_offset p) (p - 1) k := by have h_eq : hash_probe_tail_count p r (p - 1) k = hash_probe_tail_count p (linear_probe_offset p) (p - 1) k := by rw [prime_fixed_offset_linear_probe_tail_prob_interior_t_pred_tail_count_common p r hr_bij k hkt, prime_fixed_offset_linear_probe_tail_prob_interior_t_pred_tail_count_common p (linear_probe_offset p) (prime_fixed_offset_linear_probe_tail_prob_interior_t_pred_linear_probe_bijective p) k hkt] unfold hash_probe_tail_prob rw [h_eq]