hash_probe_expected_cost_two
After two insertions the expected cost is 1+2/n+(3+[2r₁=0])/n².
Statement
theorem hash_probe_expected_cost_two (n : ℕ) [NeZero n] (hn : 2 < n) (r : Fin n → ZMod n) (hr : Function.Bijective r) (hr0 : r 0 = 0) : hash_probe_expected_cost n r 2 = 1 + 2 / (n : ℝ) + (3 + (if r 1 + r 1 = 0 then (1 : ℝ) else 0)) / (n : ℝ)^2
- Source
- Unit-first fixed-offset mean-probe extremality; experiments 11670–11680 and arXiv:2610.31363.
- Verified
- 02 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 8
- hash_probe_expected_costFor a table size n with [NeZero n], an offset sequence r : Fin n → ZMod n, and a number of inserted keys t : ℕ, hash_probe_expected_cost n…
- 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…
- 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_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…
- hash_insert_stepGiven table size n, an offset sequence r : Fin n → ZMod n, a set of occupied slots T : Finset (ZMod n), and an element a : ZMod n,…
- hash_probe_tail_prob_zeroFor any table size n with [NeZero n], offset sequence r : Fin n → ZMod n, and number of inserted keys t, the 0-th tail probability of…
- hash_occupied_slots_nilFor any n and offset sequence r : Fin n → ZMod n, hash_occupied_slots n 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…
- Used by 1
- prime_fixed_offset_tail_prob_two_twoFor any odd prime p and any bijective offset sequence r : Fin p → ZMod p with r 0 = 0, the second tail probability at load t = 2 is…
The proof, explained
The proof computes the expected probe cost after two insertions into a hash table of size n > 2 with probe permutation r by summing tail probabilities. Since two keys occupy at most 2 slots, at most two consecutive probes can be occupied, meaning all tail probabilities for k ≥ 3 vanish. The tail probabilities for k = 0, 1, 2 are evaluated by counting configurations, where the two-probe collision count splits into cases depending on whether the two keys collide and whether 2 r 1 = 0. Summing the tail probabilities gives 1 + 2/n + (3 + [2 r 1 = 0])/n^2.
Appending an element to a list of inserted keys updates the occupied slots by one insertion step.
By definition, `hash_occupied_slots` folds `hash_insert_step` over the key list starting from the empty set. Rewriting with `List.foldl_append` reduces appending a singleton `[a]` to applying `hash_insert_step` to the accumulator.
uses
List.foldl_appendopen scoped BigOperators private lemma hx_occ_append (n : ℕ) (r : Fin n → ZMod n) (A : List (ZMod n)) (a : ZMod n) : hash_occupied_slots n r (A ++ [a]) = hash_insert_step n r (hash_occupied_slots n r A) a := by unfold hash_occupied_slots rw [List.foldl_append] rfl
If a is not in the occupied slots and r 0 = 0, inserting a simply adds {a} to the occupied slots.
The probe sequence begins at index 0 where r 0 = 0, meaning the probe location is a + r 0 = a. Since a ∉ T, probe index 0 is available, so the candidate set is nonempty and has minimum 0 (the least element of Fin n). The insertion step therefore places a at slot a, yielding T ∪ {a}.
uses
Finset.mem_filter,Finset.mem_univ,true_and,dif_pos,le_antisymm,Fin.zero_le,Finset.min'_leprivate lemma hx_insert_not_mem (n : ℕ) [NeZero n] (r : Fin n → ZMod n) (hr0 : r 0 = 0) (T : Finset (ZMod n)) (a : ZMod n) (ha : a ∉ T) : hash_insert_step n r T a = T ∪ {a} := by dsimp only [hash_insert_step] have h0 : (0 : Fin n) ∈ (Finset.univ.filter (fun j : Fin n => a + r j ∉ T)) := by simp only [Finset.mem_filter, Finset.mem_univ, true_and] simpa [hr0] using ha have hne : (Finset.univ.filter (fun j : Fin n => a + r j ∉ T)).Nonempty := ⟨0, h0⟩ rw [dif_pos hne] congr 1 have hmin : (Finset.univ.filter (fun j : Fin n => a + r j ∉ T)).min' hne = 0 := by apply le_antisymm _ (Fin.zero_le _) exact Finset.min'_le _ _ h0 rw [hmin] simp [hr0]
One insertion occupies {a}, and two distinct insertions a ≠ b occupy {a, b}.
Starting from an empty table, inserting [a] = [] ++ [a] yields {a} by `hx_insert_not_mem`. For two keys [a, b] = [a] ++ [b], the table becomes the result of inserting b into {a}. When a ≠ b, b ∉ {a}, so the insertion step directly forms {a, b}.
uses
List.nil_append,hash_occupied_slots_nil,List.cons_appendprivate lemma hx_occ_single (n : ℕ) [NeZero n] (r : Fin n → ZMod n) (hr0 : r 0 = 0) (a : ZMod n) : hash_occupied_slots n r [a] = {a} := by have h := hx_occ_append n r ([] : List (ZMod n)) a simp only [List.nil_append] at h rw [h, hash_occupied_slots_nil] rw [hx_insert_not_mem n r hr0 ∅ a (by simp)] simp private lemma hx_occ_two (n : ℕ) [NeZero n] (r : Fin n → ZMod n) (hr0 : r 0 = 0) (a b : ZMod n) : hash_occupied_slots n r [a, b] = hash_insert_step n r {a} b := by have h := hx_occ_append n r [a] b simp only [List.cons_append, List.nil_append] at h rw [h, hx_occ_single n r hr0 a] private lemma hx_occ_two_ne (n : ℕ) [NeZero n] (r : Fin n → ZMod n) (hr0 : r 0 = 0) (a b : ZMod n) (hab : a ≠ b) : hash_occupied_slots n r [a, b] = {a, b} := by rw [hx_occ_two n r hr0 a b] rw [hx_insert_not_mem n r hr0 {a} b (by simpa [eq_comm] using hab)] simp
If the same key a is inserted twice, the occupied slots are {a, a + r 1}.
The first insertion places a in slot a. The second insertion encounters an occupied slot at probe 0 since a + r 0 = a. Since r is injective and r 0 = 0, probe index j hits slot a if and only if j = 0. Thus the available candidate indices are all nonzero elements of Fin n. For n > 2, index 1 is nonzero and is the minimum nonzero element, so the second insertion places the key at slot a + r 1, yielding {a, a + r 1}.
uses
Finset.mem_erase,add_left_cancel,congrArg,Fin.val_one',Fin.val_zero,Nat.mod_eq_of_lt,Finset.min'_eq_iff,Fin.le_defprivate lemma hx_occ_two_eq (n : ℕ) [NeZero n] (r : Fin n → ZMod n) (hr : Function.Bijective r) (hr0 : r 0 = 0) (hn : 2 < n) (a : ZMod n) : hash_occupied_slots n r [a, a] = {a, a + r 1} := by rw [hx_occ_two n r hr0 a a] dsimp only [hash_insert_step] have hset : (Finset.univ.filter (fun j : Fin n => a + r j ∉ ({a} : Finset (ZMod n)))) = Finset.univ.erase (0 : Fin n) := by ext j simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_erase] constructor · intro hj refine ⟨?_, trivial⟩ intro hj0 subst hj0 exact hj (by simp [hr0]) · rintro ⟨hj0, -⟩ hmem have hrj : r j = 0 := by have hEq : a + r j = a + 0 := by simpa using hmem exact add_left_cancel hEq exact hj0 (hr.injective (by rw [hrj, hr0])) have h1mem : (1 : Fin n) ∈ Finset.univ.erase (0 : Fin n) := by rw [Finset.mem_erase] refine ⟨?_, Finset.mem_univ _⟩ intro h have h' := congrArg Fin.val h rw [Fin.val_one', Fin.val_zero, Nat.mod_eq_of_lt (by omega)] at h' omega have hne : (Finset.univ.erase (0 : Fin n)).Nonempty := ⟨1, h1mem⟩ rw [hset, dif_pos hne] have hmin : (Finset.univ.erase (0 : Fin n)).min' hne = 1 := by rw [Finset.min'_eq_iff] refine ⟨h1mem, ?_⟩ intro b hb rw [Finset.mem_erase] at hb obtain ⟨hb0, -⟩ := hb rw [Fin.le_def] have hbval : b.val ≠ 0 := by simpa using hb0 have h1 : (1 : Fin n).val = 1 := by rw [Fin.val_one'] exact Nat.mod_eq_of_lt (by omega) omega rw [hmin] simp
Counting when both h and h + d lie in a two-element set evaluates to an indicator sum.
Since d ≠ 0, h and h + d cannot be the same element. For a set {a, b} with a ≠ b, the sum over h evaluates to [a + d = b] + [b + d = a]. For a set {a, a + d}, h = a gives a + d which is in the set (contributing 1), while h = a + d gives a + 2d, which is in {a, a + d} if and only if 2d = 0 (since a + 2d = a + d would imply d = 0). Thus the sum is 1 + [2d = 0].
uses
Finset.sum_ite_mem,Finset.univ_inter,Finset.sum_pair,false_or,or_false,if_pos,if_negprivate lemma hx_sum_pair (n : ℕ) [NeZero n] (d a b : ZMod n) (hd : d ≠ 0) (hab : a ≠ b) : (∑ h : ZMod n, if h ∈ ({a, b} : Finset (ZMod n)) ∧ h + d ∈ ({a, b} : Finset (ZMod n)) then (1 : ℕ) else 0) = (if a + d = b then 1 else 0) + (if b + d = a then 1 else 0) := by have hcongr : ∀ h : ZMod n, (if h ∈ ({a, b} : Finset (ZMod n)) ∧ h + d ∈ ({a, b} : Finset (ZMod n)) then (1 : ℕ) else 0) = if h ∈ ({a, b} : Finset (ZMod n)) then (if h + d ∈ ({a, b} : Finset (ZMod n)) then (1 : ℕ) else 0) else 0 := by intro h; by_cases hh : h ∈ ({a, b} : Finset (ZMod n)) <;> simp [hh] simp_rw [hcongr] rw [Finset.sum_ite_mem] simp only [Finset.univ_inter] rw [Finset.sum_pair hab] have had : a + d ≠ a := by intro hh; apply hd have hEq : a + d = a + 0 := by simpa using hh exact add_left_cancel hEq have hbd : b + d ≠ b := by intro hh; apply hd have hEq : b + d = b + 0 := by simpa using hh exact add_left_cancel hEq simp only [Finset.mem_insert, Finset.mem_singleton, had, hbd, false_or, or_false] private lemma hx_sum_single (n : ℕ) [NeZero n] (d a : ZMod n) (hd : d ≠ 0) : (∑ h : ZMod n, if h ∈ ({a, a + d} : Finset (ZMod n)) ∧ h + d ∈ ({a, a + d} : Finset (ZMod n)) then (1 : ℕ) else 0) = 1 + (if d + d = 0 then 1 else 0) := by have hneq : a ≠ a + d := by intro hh; apply hd have hEq : a + d = a + 0 := by simpa [eq_comm] using hh exact add_left_cancel hEq have hcongr : ∀ h : ZMod n, (if h ∈ ({a, a + d} : Finset (ZMod n)) ∧ h + d ∈ ({a, a + d} : Finset (ZMod n)) then (1 : ℕ) else 0) = if h ∈ ({a, a + d} : Finset (ZMod n)) then (if h + d ∈ ({a, a + d} : Finset (ZMod n)) then (1 : ℕ) else 0) else 0 := by intro h; by_cases hh : h ∈ ({a, a + d} : Finset (ZMod n)) <;> simp [hh] simp_rw [hcongr] rw [Finset.sum_ite_mem] simp only [Finset.univ_inter] rw [Finset.sum_pair hneq] have hfirst : (if a + d ∈ ({a, a + d} : Finset (ZMod n)) then (1 : ℕ) else 0) = 1 := by simp rw [hfirst] congr 1 have hiff : ((a + d) + d ∈ ({a, a + d} : Finset (ZMod n))) ↔ (d + d = 0) := by simp only [Finset.mem_insert, Finset.mem_singleton] constructor · rintro (h | h) · have hEq : a + (d + d) = a + 0 := by calc a + (d + d) = (a + d) + d := by abel _ = a := h simpa using hEq exact add_left_cancel hEq · exfalso have hEq : (a + d) + d = (a + d) + 0 := by simpa [eq_comm] using h have hzero : d = 0 := add_left_cancel hEq exact hd hzero · intro hh left calc (a + d) + d = a + (d + d) := by abel _ = a + 0 := by rw [hh] _ = a := by abel by_cases hdd : d + d = 0 · rw [if_pos hdd, if_pos (hiff.mpr hdd)] · rw [if_neg hdd, if_neg (fun h => hdd (hiff.mp h))]
The condition that probes 0 and 1 hit occupied slots reduces to h, h + r 1 ∈ occ, and its sum over h depends on whether the two keys coincide.
In Fin n with n > 2, the probe indices j < 2 are exactly 0 and 1, so the probe requirement is h ∈ occ and h + r 1 ∈ occ. Splitting on whether the two inserted keys are equal (a = b) or distinct (a ≠ b), we substitute the occupied sets {a, a + r 1} or {a, b} into the previous two-element set sums.
uses
Fin.extprivate lemma hx_cond (n : ℕ) [NeZero n] (r : Fin n → ZMod n) (hr0 : r 0 = 0) (hn : 2 < n) (A : Fin 2 → ZMod n) (h : ZMod n) : (∀ j : Fin n, j.val < 2 → h + r j ∈ hash_occupied_slots n r (List.ofFn A)) ↔ h ∈ hash_occupied_slots n r (List.ofFn A) ∧ h + r 1 ∈ hash_occupied_slots n r (List.ofFn A) := by constructor · intro hh refine ⟨?_, ?_⟩ · simpa [hr0] using hh 0 (by simp) · exact hh 1 (by rw [Fin.val_one', Nat.mod_eq_of_lt (by omega)] omega) · rintro ⟨h0, h1⟩ j hj have hj' : j.val = 0 ∨ j.val = 1 := by omega rcases hj' with hj0 | hj1 · have hjeq : j = 0 := Fin.ext hj0 subst hjeq simpa [hr0] using h0 · have hjeq : j = 1 := by apply Fin.ext rw [Fin.val_one', Nat.mod_eq_of_lt (by omega)] exact hj1 subst hjeq exact h1 private lemma hx_inner (n : ℕ) [NeZero n] (r : Fin n → ZMod n) (hr : Function.Bijective r) (hr0 : r 0 = 0) (hn : 2 < n) (hd : r 1 ≠ 0) (a b : ZMod n) : (∑ h : ZMod n, if h ∈ hash_occupied_slots n r [a, b] ∧ h + r 1 ∈ hash_occupied_slots n r [a, b] then (1 : ℕ) else 0) = (if a = b then 1 else 0) + (if a = b then (if r 1 + r 1 = 0 then 1 else 0) else 0) + (if a + r 1 = b then 1 else 0) + (if b + r 1 = a then 1 else 0) := by by_cases hab : a = b · subst hab rw [hx_occ_two_eq n r hr hr0 hn a] rw [hx_sum_single n (r 1) a hd] have had : a + r 1 ≠ a := by intro hh; apply hd have hEq : a + r 1 = a + 0 := by simpa using hh exact add_left_cancel hEq simp [had] · rw [hx_occ_two_ne n r hr0 a b hab] rw [hx_sum_pair n (r 1) a b hd hab] simp [hab]
Functions Fin 2 → ZMod n correspond to pairs, two insertions occupy 2 slots, and early probe offsets are distinct.
The equivalence `finTwoArrowEquiv` turns sums over functions Fin 2 → ZMod n into double sums over pairs (a, b). By `hash_occupied_slots_card`, inserting 2 elements into a table of size n > 2 always occupies 2 slots. Since r is bijective and 0, 1, 2 are distinct in Fin n for n > 2, the probe offsets r 0 = 0, r 1, and r 2 are pairwise distinct.
uses
Fintype.sum_prod_type,Fintype.sum_equiv,finTwoArrowEquiv,hash_occupied_slots_card,List.length_ofFnprivate lemma hx_sum_arrow (n : ℕ) [NeZero n] (f : ZMod n → ZMod n → ℕ) : (∑ A : Fin 2 → ZMod n, f (A 0) (A 1)) = ∑ a, ∑ b, f a b := by rw [← Fintype.sum_prod_type (fun p : ZMod n × ZMod n => f p.1 p.2)] apply Fintype.sum_equiv (finTwoArrowEquiv (ZMod n)) intro A simp [finTwoArrowEquiv] private lemma hx_occ_card (n : ℕ) [NeZero n] (r : Fin n → ZMod n) (hr : Function.Bijective r) (hn : 2 < n) (A : Fin 2 → ZMod n) : (hash_occupied_slots n r (List.ofFn A)).card = 2 := by rw [hash_occupied_slots_card n r hr (List.ofFn A) (by rw [List.length_ofFn]; omega)] rw [List.length_ofFn] private lemma hx_one_ne_zero (n : ℕ) [NeZero n] (hn : 2 < n) (r : Fin n → ZMod n) (hr : Function.Bijective r) (hr0 : r 0 = 0) : r 1 ≠ 0 := by intro h have h1 : (1 : Fin n) = 0 := hr.injective (by rw [h, hr0]) have h2 := congrArg Fin.val h1 rw [Fin.val_one', Nat.mod_eq_of_lt (by omega), Fin.val_zero] at h2 omega private lemma hx_two_ne_zero (n : ℕ) [NeZero n] (hn : 2 < n) (r : Fin n → ZMod n) (hr : Function.Bijective r) (hr0 : r 0 = 0) : r 2 ≠ 0 := by intro h have h1 : (2 : Fin n) = 0 := hr.injective (by rw [h, hr0]) have h2 := congrArg Fin.val h1 have h2val : (2 : Fin n).val = 2 := by show 2 % n = 2 exact Nat.mod_eq_of_lt (by omega) rw [h2val, Fin.val_zero] at h2 omega private lemma hx_one_ne_two (n : ℕ) [NeZero n] (hn : 2 < n) (r : Fin n → ZMod n) (hr : Function.Bijective r) : r 1 ≠ r 2 := by intro h have h1 : (1 : Fin n) = 2 := hr.injective h have h2 := congrArg Fin.val h1 have h2val : (2 : Fin n).val = 2 := by show 2 % n = 2 exact Nat.mod_eq_of_lt (by omega) rw [Fin.val_one', Nat.mod_eq_of_lt (by omega), h2val] at h2 omega
The tail count for k = 2 probes is n * (3 + [2 r 1 = 0]).
The tail count sums over all pairs (a, b) the inner sum of probe hits. For each fixed a, summing over all b ∈ ZMod n gives: b = a contributes 1 + [2 r 1 = 0], b = a + r 1 contributes 1, and b = a - r 1 contributes 1, totaling 3 + [2 r 1 = 0] regardless of a. Summing this constant over all n choices of a multiplies it by n.
uses
Finset.card_filter,List.ofFn_succ,Finset.sum_add_distrib,Finset.sum_congr,Finset.sum_const,Finset.card_univ,ZMod.cardprivate lemma hx_tail_count_two (n : ℕ) [NeZero n] (r : Fin n → ZMod n) (hr : Function.Bijective r) (hr0 : r 0 = 0) (hn : 2 < n) (hd : r 1 ≠ 0) : hash_probe_tail_count n r 2 2 = n * (3 + (if r 1 + r 1 = 0 then 1 else 0)) := by unfold hash_probe_tail_count rw [Finset.card_filter, Fintype.sum_prod_type] simp only [hx_cond n r hr0 hn] have hofn : ∀ A : Fin 2 → ZMod n, List.ofFn A = [A 0, A 1] := fun A => by simp [List.ofFn_succ] simp only [hofn] rw [hx_sum_arrow n (fun a b => ∑ h : ZMod n, if h ∈ hash_occupied_slots n r [a, b] ∧ h + r 1 ∈ hash_occupied_slots n r [a, b] then (1 : ℕ) else 0)] simp only [hx_inner n r hr hr0 hn hd] have hstep : ∀ a : ZMod n, (Finset.univ.sum (fun b : ZMod n => (((if a = b then (1:ℕ) else 0) + (if a = b then (if r 1 + r 1 = 0 then (1:ℕ) else 0) else 0)) + (if a + r 1 = b then (1:ℕ) else 0)) + (if b + r 1 = a then (1:ℕ) else 0))) = 3 + (if r 1 + r 1 = 0 then (1:ℕ) else 0) := by intro a rw [Finset.sum_add_distrib, Finset.sum_add_distrib, Finset.sum_add_distrib] have h1 : (∑ b : ZMod n, if a = b then (1:ℕ) else 0) = 1 := by simp have h2 : (∑ b : ZMod n, if a = b then (if r 1 + r 1 = 0 then (1:ℕ) else 0) else 0) = (if r 1 + r 1 = 0 then (1:ℕ) else 0) := by simp have h3 : (∑ b : ZMod n, if a + r 1 = b then (1:ℕ) else 0) = 1 := by simp have h4 : (∑ b : ZMod n, if b + r 1 = a then (1:ℕ) else 0) = 1 := by rw [show (∑ b : ZMod n, if b + r 1 = a then (1:ℕ) else 0) = ∑ b : ZMod n, if b = a - r 1 then (1:ℕ) else 0 from by apply Finset.sum_congr rfl intro b _ by_cases h : b + r 1 = a · have hb : b = a - r 1 := by rw [← h]; abel simp [hb] · have hb : b ≠ a - r 1 := by intro hh; exact h (by rw [hh]; abel) simp [h, hb]] simp rw [h1, h2, h3, h4] omega simp only [hstep] rw [Finset.sum_const, Finset.card_univ, ZMod.card] simp
The tail count for k = 1 probe is 2 * n^2.
For k = 1, the condition requires only probe 0 to hit an occupied slot, so h must belong to the occupied set. Since every 2-key sequence occupies 2 slots, there are 2 choices of h for each of the n^2 pairs of keys, giving 2 * n^2 total pairs.
uses
Fintype.card_fun,Fintype.card_finprivate lemma hx_tail_count_one (n : ℕ) [NeZero n] (r : Fin n → ZMod n) (hr : Function.Bijective r) (hr0 : r 0 = 0) (hn : 2 < n) : hash_probe_tail_count n r 2 1 = 2 * n ^ 2 := by unfold hash_probe_tail_count rw [Finset.card_filter, Fintype.sum_prod_type] have hcond : ∀ (A : Fin 2 → ZMod n) (h : ZMod n), ((∀ j : Fin n, j.val < 1 → h + r j ∈ hash_occupied_slots n r (List.ofFn A)) ↔ h ∈ hash_occupied_slots n r (List.ofFn A)) := by intro A h constructor · intro hh simpa [hr0] using hh 0 (by simp) · intro hh j hj have hj0 : j.val = 0 := by omega have hjeq : j = 0 := Fin.ext hj0 subst hjeq simpa [hr0] using hh simp only [hcond] have hstep : ∀ A : Fin 2 → ZMod n, (∑ h : ZMod n, if h ∈ hash_occupied_slots n r (List.ofFn A) then (1:ℕ) else 0) = 2 := by intro A rw [← Finset.card_filter] have h2 : Finset.univ.filter (fun h : ZMod n => h ∈ hash_occupied_slots n r (List.ofFn A)) = hash_occupied_slots n r (List.ofFn A) := by ext h; simp rw [h2] exact hx_occ_card n r hr hn A simp only [hstep] rw [Finset.sum_const, Finset.card_univ, Fintype.card_fun, ZMod.card, Fintype.card_fin] simp [mul_comm]
The tail count for k ≥ 3 probes is 0.
If a key required 3 or more probes, then x + r 0, x + r 1, and x + r 2 would all have to belong to the occupied set. Since r is bijective, these 3 elements are pairwise distinct, so the occupied set would contain at least 3 elements. But two insertions occupy at most 2 slots, a contradiction.
uses
Finset.card_eq_zero,Finset.not_nonempty_iff_eq_empty,Finset.card_insert_of_notMem,Finset.card_singleton,Finset.card_le_cardprivate lemma hx_tail_count_three (n : ℕ) [NeZero n] (r : Fin n → ZMod n) (hr : Function.Bijective r) (hr0 : r 0 = 0) (hn : 2 < n) {k : ℕ} (hk : 3 ≤ k) : hash_probe_tail_count n r 2 k = 0 := by unfold hash_probe_tail_count rw [Finset.card_eq_zero, ← Finset.not_nonempty_iff_eq_empty] rintro ⟨⟨A, x⟩, hp⟩ simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hp have hr1 := hx_one_ne_zero n hn r hr hr0 have hr2 := hx_two_ne_zero n hn r hr hr0 have hr12 := hx_one_ne_two n hn r hr have h2val : (2 : Fin n).val = 2 := by show 2 % n = 2 exact Nat.mod_eq_of_lt (by omega) have h0val : (0 : Fin n).val = 0 := by simp have m0 : x + r 0 ∈ hash_occupied_slots n r (List.ofFn A) := hp 0 (by rw [h0val]; omega) have m1 : x + r 1 ∈ hash_occupied_slots n r (List.ofFn A) := hp 1 (by rw [Fin.val_one', Nat.mod_eq_of_lt (by omega)]; omega) have m2 : x + r 2 ∈ hash_occupied_slots n r (List.ofFn A) := hp 2 (by rw [h2val]; omega) have e01 : x + r 0 ≠ x + r 1 := by intro hh have h00 : r 0 = r 1 := add_left_cancel hh rw [hr0] at h00 exact hr1 h00.symm have e02 : x + r 0 ≠ x + r 2 := by intro hh have h00 : r 0 = r 2 := add_left_cancel hh rw [hr0] at h00 exact hr2 h00.symm have e12 : x + r 1 ≠ x + r 2 := fun hh => hr12 (add_left_cancel hh) have hsub : ({x + r 0, x + r 1, x + r 2} : Finset (ZMod n)) ⊆ hash_occupied_slots n r (List.ofFn A) := by intro y hy simp only [Finset.mem_insert, Finset.mem_singleton] at hy rcases hy with h | h | h · subst h; exact m0 · subst h; exact m1 · subst h; exact m2 have hcard3 : ({x + r 0, x + r 1, x + r 2} : Finset (ZMod n)).card = 3 := by rw [Finset.card_insert_of_notMem (by simp [e01, e02]), Finset.card_insert_of_notMem (by simp [e12]), Finset.card_singleton] have hle := Finset.card_le_card hsub rw [hcard3, hx_occ_card n r hr hn A] at hle omega
The tail probabilities for k = 0, 1, 2 are 1, 2/n, and (3 + [2 r 1 = 0])/n^2.
Dividing the tail counts by the total number of configurations n^(2+1) = n^3 gives: 1 for k = 0; (2n^2)/n^3 = 2/n for k = 1; and n(3 + [2 r 1 = 0])/n^3 = (3 + [2 r 1 = 0])/n^2 for k = 2.
uses
NeZero.ne,hash_probe_tail_prob_zero,hash_probe_tail_probtheorem hash_probe_expected_cost_two (n : ℕ) [NeZero n] (hn : 2 < n) (r : Fin n → ZMod n) (hr : Function.Bijective r) (hr0 : r 0 = 0) : hash_probe_expected_cost n r 2 = 1 + 2 / (n : ℝ) + (3 + (if r 1 + r 1 = 0 then (1 : ℝ) else 0)) / (n : ℝ)^2 := by have hn0 : (n : ℝ) ≠ 0 := by have h : n ≠ 0 := NeZero.ne n positivity have hd : r 1 ≠ 0 := hx_one_ne_zero n hn r hr hr0 have h0 : hash_probe_tail_prob n r 2 0 = 1 := hash_probe_tail_prob_zero n r 2 have h1 : hash_probe_tail_prob n r 2 1 = 2 / (n : ℝ) := by rw [hash_probe_tail_prob, hx_tail_count_one n r hr hr0 hn] push_cast rw [show (n : ℝ) ^ 3 = (n : ℝ) ^ 2 * (n : ℝ) by ring] field_simp have h2 : hash_probe_tail_prob n r 2 2 = (3 + (if r 1 + r 1 = 0 then (1 : ℝ) else 0)) / (n : ℝ)^2 := by rw [hash_probe_tail_prob, hx_tail_count_two n r hr hr0 hn hd] by_cases hh : r 1 + r 1 = 0 · simp only [if_pos hh] have e1 : ((n * (3 + 1) : ℕ) : ℝ) = (n : ℝ) * 4 := by push_cast; ring rw [e1, show (n : ℝ) ^ 3 = (n : ℝ) * (n : ℝ) ^ 2 by ring] field_simp norm_num · simp only [if_neg hh] have e1 : ((n * 3 : ℕ) : ℝ) = (n : ℝ) * 3 := by push_cast; ring rw [e1, show (n : ℝ) ^ 3 = (n : ℝ) * (n : ℝ) ^ 2 by ring] field_simp norm_num
The expected probe cost is 1 + 2/n + (3 + [2 r 1 = 0])/n^2.
By definition, the expected probe cost is the sum of tail probabilities for k ∈ {0, ..., n}. Since the tail probability is 0 for all k ≥ 3, the sum reduces to k ∈ {0, 1, 2}. Substituting the three calculated probabilities and simplifying with ring arithmetic yields the theorem statement.
uses
Finset.mem_range,Finset.sum_subset,Finset.sum_insertunfold hash_probe_expected_cost have hsub : ({0, 1, 2} : Finset ℕ) ⊆ Finset.range (n + 1) := by intro x hx simp only [Finset.mem_insert, Finset.mem_singleton] at hx simp only [Finset.mem_range] rcases hx with h | h | h <;> omega have hzero : ∀ x ∈ Finset.range (n + 1), x ∉ ({0, 1, 2} : Finset ℕ) → hash_probe_tail_prob n r 2 x = 0 := by intro x _ hx2 simp only [Finset.mem_insert, Finset.mem_singleton, not_or] at hx2 have hx3 : 3 ≤ x := by omega rw [hash_probe_tail_prob, hx_tail_count_three n r hr hr0 hn hx3] simp rw [← Finset.sum_subset hsub hzero] rw [Finset.sum_insert (by simp), Finset.sum_insert (by simp), Finset.sum_singleton] rw [h0, h1, h2] ring
List.foldl_append- folding a function over an appended list is equivalent to folding over the first part and then the second
Finset.mem_filter- an element is in a filtered finset if and only if it is in the original finset and satisfies the predicate
Finset.mem_univ- every element of a fintype belongs to the universal finset univ
true_and- True ∧ p simplifies to p
dif_pos- dependent if-then-else evaluates to the positive branch when the condition is true
le_antisymm- if a ≤ b and b ≤ a, then a = b
Fin.zero_le- 0 is less than or equal to any element in Fin n
Finset.min'_le- the minimum element of a nonempty finset is less than or equal to any element in the finset
List.nil_append- appending the empty list to a list does not change it
hash_occupied_slots_nil- the occupied slots for an empty list of insertions is the empty set
List.cons_append- consing an element onto an appended list is prepending it to the concatenation
Finset.mem_erase- an element belongs to s.erase b if and only if it is in s and not equal to b
add_left_cancel- in an additive structure, a + b = a + c implies b = c
congrArg- applying a function to equal arguments produces equal results
Fin.val_one'- the natural value of (1 : Fin n) is 1 % n
Fin.val_zero- the natural value of (0 : Fin n) is 0
Nat.mod_eq_of_lt- for natural numbers a < b, the modulo a % b equals a
Finset.min'_eq_iff- the minimum of a nonempty finset is a if and only if a is in the finset and a is less than or equal to every element
Fin.le_def- in Fin n, a ≤ b if and only if the underlying natural numbers satisfy a.val ≤ b.val
Finset.sum_ite_mem- summing an indicator function over s for membership in t equals the sum over s ∩ t
Finset.univ_inter- the intersection of the universal finset with s is s
Finset.sum_pair- the sum of a function over a pair of distinct elements {a, b} equals f a + f b
false_or- False ∨ p simplifies to p
or_false- p ∨ False simplifies to p
if_pos- if c then t else e evaluates to t when c holds
if_neg- if c then t else e evaluates to e when ¬c holds
Fin.ext- two elements of Fin n are equal if their underlying natural values are equal
Fintype.sum_prod_type- a sum over a product type α × β equals the double sum over α and then β
Fintype.sum_equiv- a sum over a type can be rewritten along an equivalence of types
finTwoArrowEquiv- functions Fin 2 → α are equivalent to pairs α × α
hash_occupied_slots_card- for a bijective probe sequence and list length at most n, the number of occupied slots equals the length of the list
List.length_ofFn- the length of List.ofFn f is the domain dimension n
Finset.card_filter- the cardinality of a filtered finset equals the sum of indicator values of the predicate over the finset
List.ofFn_succ- List.ofFn on Fin (n+1) expands to f 0 followed by List.ofFn of the remaining entries
Finset.sum_add_distrib- the sum of a sum of functions over a finset splits into the sum of the two sums
Finset.sum_congr- if two finsets are equal and two functions agree on the set, their sums are equal
Finset.sum_const- summing a constant b over a finset s equals the cardinality of s scalar-multiplied by b
Finset.card_univ- the cardinality of Finset.univ is the cardinality of the ambient finite type
ZMod.card- the cardinality of ZMod n is n
Fintype.card_fun- the cardinality of the function space α → β is (card β) ^ (card α)
Fintype.card_fin- the cardinality of Fin n is n
Finset.card_eq_zero- a finset has cardinality 0 if and only if it is empty
Finset.not_nonempty_iff_eq_empty- a finset is not nonempty if and only if it is empty
Finset.card_insert_of_notMem- inserting an element not in a finset increments its cardinality by 1
Finset.card_singleton- the cardinality of a singleton finset is 1
Finset.card_le_card- if s ⊆ t, then the cardinality of s is at most that of t
NeZero.ne- a type with a NeZero instance has nonzero witness n ≠ 0
hash_probe_tail_prob_zero- the 0-probe tail probability is identically 1
hash_probe_tail_prob- the tail probability for k probes after t insertions is the tail count divided by n^(t+1)
Finset.mem_range- an integer belongs to range m if and only if it is strictly less than m
Finset.sum_subset- the sum over a subset equals the sum over the superset if the summand is zero outside the subset
Finset.sum_insert- the sum over insert a s equals f a plus the sum over s, when a ∉ s
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.
open scoped BigOperatorsprivate lemma hx_occ_append (n : ℕ) (r : Fin n → ZMod n) (A : List (ZMod n)) (a : ZMod n) : hash_occupied_slots n r (A ++ [a]) = hash_insert_step n r (hash_occupied_slots n r A) a := by unfold hash_occupied_slots rw [List.foldl_append] rflprivate lemma hx_insert_not_mem (n : ℕ) [NeZero n] (r : Fin n → ZMod n) (hr0 : r 0 = 0) (T : Finset (ZMod n)) (a : ZMod n) (ha : a ∉ T) : hash_insert_step n r T a = T ∪ {a} := by dsimp only [hash_insert_step] have h0 : (0 : Fin n) ∈ (Finset.univ.filter (fun j : Fin n => a + r j ∉ T)) := by simp only [Finset.mem_filter, Finset.mem_univ, true_and] simpa [hr0] using ha have hne : (Finset.univ.filter (fun j : Fin n => a + r j ∉ T)).Nonempty := ⟨0, h0⟩ rw [dif_pos hne] congr 1 have hmin : (Finset.univ.filter (fun j : Fin n => a + r j ∉ T)).min' hne = 0 := by apply le_antisymm _ (Fin.zero_le _) exact Finset.min'_le _ _ h0 rw [hmin] simp [hr0]private lemma hx_occ_single (n : ℕ) [NeZero n] (r : Fin n → ZMod n) (hr0 : r 0 = 0) (a : ZMod n) : hash_occupied_slots n r [a] = {a} := by have h := hx_occ_append n r ([] : List (ZMod n)) a simp only [List.nil_append] at h rw [h, hash_occupied_slots_nil] rw [hx_insert_not_mem n r hr0 ∅ a (by simp)] simpprivate lemma hx_occ_two (n : ℕ) [NeZero n] (r : Fin n → ZMod n) (hr0 : r 0 = 0) (a b : ZMod n) : hash_occupied_slots n r [a, b] = hash_insert_step n r {a} b := by have h := hx_occ_append n r [a] b simp only [List.cons_append, List.nil_append] at h rw [h, hx_occ_single n r hr0 a]private lemma hx_occ_two_ne (n : ℕ) [NeZero n] (r : Fin n → ZMod n) (hr0 : r 0 = 0) (a b : ZMod n) (hab : a ≠ b) : hash_occupied_slots n r [a, b] = {a, b} := by rw [hx_occ_two n r hr0 a b] rw [hx_insert_not_mem n r hr0 {a} b (by simpa [eq_comm] using hab)] simpprivate lemma hx_occ_two_eq (n : ℕ) [NeZero n] (r : Fin n → ZMod n) (hr : Function.Bijective r) (hr0 : r 0 = 0) (hn : 2 < n) (a : ZMod n) : hash_occupied_slots n r [a, a] = {a, a + r 1} := by rw [hx_occ_two n r hr0 a a] dsimp only [hash_insert_step] have hset : (Finset.univ.filter (fun j : Fin n => a + r j ∉ ({a} : Finset (ZMod n)))) = Finset.univ.erase (0 : Fin n) := by ext j simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_erase] constructor · intro hj refine ⟨?_, trivial⟩ intro hj0 subst hj0 exact hj (by simp [hr0]) · rintro ⟨hj0, -⟩ hmem have hrj : r j = 0 := by have hEq : a + r j = a + 0 := by simpa using hmem exact add_left_cancel hEq exact hj0 (hr.injective (by rw [hrj, hr0])) have h1mem : (1 : Fin n) ∈ Finset.univ.erase (0 : Fin n) := by rw [Finset.mem_erase] refine ⟨?_, Finset.mem_univ _⟩ intro h have h' := congrArg Fin.val h rw [Fin.val_one', Fin.val_zero, Nat.mod_eq_of_lt (by omega)] at h' omega have hne : (Finset.univ.erase (0 : Fin n)).Nonempty := ⟨1, h1mem⟩ rw [hset, dif_pos hne] have hmin : (Finset.univ.erase (0 : Fin n)).min' hne = 1 := by rw [Finset.min'_eq_iff] refine ⟨h1mem, ?_⟩ intro b hb rw [Finset.mem_erase] at hb obtain ⟨hb0, -⟩ := hb rw [Fin.le_def] have hbval : b.val ≠ 0 := by simpa using hb0 have h1 : (1 : Fin n).val = 1 := by rw [Fin.val_one'] exact Nat.mod_eq_of_lt (by omega) omega rw [hmin] simpprivate lemma hx_sum_pair (n : ℕ) [NeZero n] (d a b : ZMod n) (hd : d ≠ 0) (hab : a ≠ b) : (∑ h : ZMod n, if h ∈ ({a, b} : Finset (ZMod n)) ∧ h + d ∈ ({a, b} : Finset (ZMod n)) then (1 : ℕ) else 0) = (if a + d = b then 1 else 0) + (if b + d = a then 1 else 0) := by have hcongr : ∀ h : ZMod n, (if h ∈ ({a, b} : Finset (ZMod n)) ∧ h + d ∈ ({a, b} : Finset (ZMod n)) then (1 : ℕ) else 0) = if h ∈ ({a, b} : Finset (ZMod n)) then (if h + d ∈ ({a, b} : Finset (ZMod n)) then (1 : ℕ) else 0) else 0 := by intro h; by_cases hh : h ∈ ({a, b} : Finset (ZMod n)) <;> simp [hh] simp_rw [hcongr] rw [Finset.sum_ite_mem] simp only [Finset.univ_inter] rw [Finset.sum_pair hab] have had : a + d ≠ a := by intro hh; apply hd have hEq : a + d = a + 0 := by simpa using hh exact add_left_cancel hEq have hbd : b + d ≠ b := by intro hh; apply hd have hEq : b + d = b + 0 := by simpa using hh exact add_left_cancel hEq simp only [Finset.mem_insert, Finset.mem_singleton, had, hbd, false_or, or_false]private lemma hx_sum_single (n : ℕ) [NeZero n] (d a : ZMod n) (hd : d ≠ 0) : (∑ h : ZMod n, if h ∈ ({a, a + d} : Finset (ZMod n)) ∧ h + d ∈ ({a, a + d} : Finset (ZMod n)) then (1 : ℕ) else 0) = 1 + (if d + d = 0 then 1 else 0) := by have hneq : a ≠ a + d := by intro hh; apply hd have hEq : a + d = a + 0 := by simpa [eq_comm] using hh exact add_left_cancel hEq have hcongr : ∀ h : ZMod n, (if h ∈ ({a, a + d} : Finset (ZMod n)) ∧ h + d ∈ ({a, a + d} : Finset (ZMod n)) then (1 : ℕ) else 0) = if h ∈ ({a, a + d} : Finset (ZMod n)) then (if h + d ∈ ({a, a + d} : Finset (ZMod n)) then (1 : ℕ) else 0) else 0 := by intro h; by_cases hh : h ∈ ({a, a + d} : Finset (ZMod n)) <;> simp [hh] simp_rw [hcongr] rw [Finset.sum_ite_mem] simp only [Finset.univ_inter] rw [Finset.sum_pair hneq] have hfirst : (if a + d ∈ ({a, a + d} : Finset (ZMod n)) then (1 : ℕ) else 0) = 1 := by simp rw [hfirst] congr 1 have hiff : ((a + d) + d ∈ ({a, a + d} : Finset (ZMod n))) ↔ (d + d = 0) := by simp only [Finset.mem_insert, Finset.mem_singleton] constructor · rintro (h | h) · have hEq : a + (d + d) = a + 0 := by calc a + (d + d) = (a + d) + d := by abel _ = a := h simpa using hEq exact add_left_cancel hEq · exfalso have hEq : (a + d) + d = (a + d) + 0 := by simpa [eq_comm] using h have hzero : d = 0 := add_left_cancel hEq exact hd hzero · intro hh left calc (a + d) + d = a + (d + d) := by abel _ = a + 0 := by rw [hh] _ = a := by abel by_cases hdd : d + d = 0 · rw [if_pos hdd, if_pos (hiff.mpr hdd)] · rw [if_neg hdd, if_neg (fun h => hdd (hiff.mp h))]private lemma hx_cond (n : ℕ) [NeZero n] (r : Fin n → ZMod n) (hr0 : r 0 = 0) (hn : 2 < n) (A : Fin 2 → ZMod n) (h : ZMod n) : (∀ j : Fin n, j.val < 2 → h + r j ∈ hash_occupied_slots n r (List.ofFn A)) ↔ h ∈ hash_occupied_slots n r (List.ofFn A) ∧ h + r 1 ∈ hash_occupied_slots n r (List.ofFn A) := by constructor · intro hh refine ⟨?_, ?_⟩ · simpa [hr0] using hh 0 (by simp) · exact hh 1 (by rw [Fin.val_one', Nat.mod_eq_of_lt (by omega)] omega) · rintro ⟨h0, h1⟩ j hj have hj' : j.val = 0 ∨ j.val = 1 := by omega rcases hj' with hj0 | hj1 · have hjeq : j = 0 := Fin.ext hj0 subst hjeq simpa [hr0] using h0 · have hjeq : j = 1 := by apply Fin.ext rw [Fin.val_one', Nat.mod_eq_of_lt (by omega)] exact hj1 subst hjeq exact h1private lemma hx_inner (n : ℕ) [NeZero n] (r : Fin n → ZMod n) (hr : Function.Bijective r) (hr0 : r 0 = 0) (hn : 2 < n) (hd : r 1 ≠ 0) (a b : ZMod n) : (∑ h : ZMod n, if h ∈ hash_occupied_slots n r [a, b] ∧ h + r 1 ∈ hash_occupied_slots n r [a, b] then (1 : ℕ) else 0) = (if a = b then 1 else 0) + (if a = b then (if r 1 + r 1 = 0 then 1 else 0) else 0) + (if a + r 1 = b then 1 else 0) + (if b + r 1 = a then 1 else 0) := by by_cases hab : a = b · subst hab rw [hx_occ_two_eq n r hr hr0 hn a] rw [hx_sum_single n (r 1) a hd] have had : a + r 1 ≠ a := by intro hh; apply hd have hEq : a + r 1 = a + 0 := by simpa using hh exact add_left_cancel hEq simp [had] · rw [hx_occ_two_ne n r hr0 a b hab] rw [hx_sum_pair n (r 1) a b hd hab] simp [hab]private lemma hx_sum_arrow (n : ℕ) [NeZero n] (f : ZMod n → ZMod n → ℕ) : (∑ A : Fin 2 → ZMod n, f (A 0) (A 1)) = ∑ a, ∑ b, f a b := by rw [← Fintype.sum_prod_type (fun p : ZMod n × ZMod n => f p.1 p.2)] apply Fintype.sum_equiv (finTwoArrowEquiv (ZMod n)) intro A simp [finTwoArrowEquiv]private lemma hx_occ_card (n : ℕ) [NeZero n] (r : Fin n → ZMod n) (hr : Function.Bijective r) (hn : 2 < n) (A : Fin 2 → ZMod n) : (hash_occupied_slots n r (List.ofFn A)).card = 2 := by rw [hash_occupied_slots_card n r hr (List.ofFn A) (by rw [List.length_ofFn]; omega)] rw [List.length_ofFn]private lemma hx_one_ne_zero (n : ℕ) [NeZero n] (hn : 2 < n) (r : Fin n → ZMod n) (hr : Function.Bijective r) (hr0 : r 0 = 0) : r 1 ≠ 0 := by intro h have h1 : (1 : Fin n) = 0 := hr.injective (by rw [h, hr0]) have h2 := congrArg Fin.val h1 rw [Fin.val_one', Nat.mod_eq_of_lt (by omega), Fin.val_zero] at h2 omegaprivate lemma hx_two_ne_zero (n : ℕ) [NeZero n] (hn : 2 < n) (r : Fin n → ZMod n) (hr : Function.Bijective r) (hr0 : r 0 = 0) : r 2 ≠ 0 := by intro h have h1 : (2 : Fin n) = 0 := hr.injective (by rw [h, hr0]) have h2 := congrArg Fin.val h1 have h2val : (2 : Fin n).val = 2 := by show 2 % n = 2 exact Nat.mod_eq_of_lt (by omega) rw [h2val, Fin.val_zero] at h2 omegaprivate lemma hx_one_ne_two (n : ℕ) [NeZero n] (hn : 2 < n) (r : Fin n → ZMod n) (hr : Function.Bijective r) : r 1 ≠ r 2 := by intro h have h1 : (1 : Fin n) = 2 := hr.injective h have h2 := congrArg Fin.val h1 have h2val : (2 : Fin n).val = 2 := by show 2 % n = 2 exact Nat.mod_eq_of_lt (by omega) rw [Fin.val_one', Nat.mod_eq_of_lt (by omega), h2val] at h2 omegaprivate lemma hx_tail_count_two (n : ℕ) [NeZero n] (r : Fin n → ZMod n) (hr : Function.Bijective r) (hr0 : r 0 = 0) (hn : 2 < n) (hd : r 1 ≠ 0) : hash_probe_tail_count n r 2 2 = n * (3 + (if r 1 + r 1 = 0 then 1 else 0)) := by unfold hash_probe_tail_count rw [Finset.card_filter, Fintype.sum_prod_type] simp only [hx_cond n r hr0 hn] have hofn : ∀ A : Fin 2 → ZMod n, List.ofFn A = [A 0, A 1] := fun A => by simp [List.ofFn_succ] simp only [hofn] rw [hx_sum_arrow n (fun a b => ∑ h : ZMod n, if h ∈ hash_occupied_slots n r [a, b] ∧ h + r 1 ∈ hash_occupied_slots n r [a, b] then (1 : ℕ) else 0)] simp only [hx_inner n r hr hr0 hn hd] have hstep : ∀ a : ZMod n, (Finset.univ.sum (fun b : ZMod n => (((if a = b then (1:ℕ) else 0) + (if a = b then (if r 1 + r 1 = 0 then (1:ℕ) else 0) else 0)) + (if a + r 1 = b then (1:ℕ) else 0)) + (if b + r 1 = a then (1:ℕ) else 0))) = 3 + (if r 1 + r 1 = 0 then (1:ℕ) else 0) := by intro a rw [Finset.sum_add_distrib, Finset.sum_add_distrib, Finset.sum_add_distrib] have h1 : (∑ b : ZMod n, if a = b then (1:ℕ) else 0) = 1 := by simp have h2 : (∑ b : ZMod n, if a = b then (if r 1 + r 1 = 0 then (1:ℕ) else 0) else 0) = (if r 1 + r 1 = 0 then (1:ℕ) else 0) := by simp have h3 : (∑ b : ZMod n, if a + r 1 = b then (1:ℕ) else 0) = 1 := by simp have h4 : (∑ b : ZMod n, if b + r 1 = a then (1:ℕ) else 0) = 1 := by rw [show (∑ b : ZMod n, if b + r 1 = a then (1:ℕ) else 0) = ∑ b : ZMod n, if b = a - r 1 then (1:ℕ) else 0 from by apply Finset.sum_congr rfl intro b _ by_cases h : b + r 1 = a · have hb : b = a - r 1 := by rw [← h]; abel simp [hb] · have hb : b ≠ a - r 1 := by intro hh; exact h (by rw [hh]; abel) simp [h, hb]] simp rw [h1, h2, h3, h4] omega simp only [hstep] rw [Finset.sum_const, Finset.card_univ, ZMod.card] simpprivate lemma hx_tail_count_one (n : ℕ) [NeZero n] (r : Fin n → ZMod n) (hr : Function.Bijective r) (hr0 : r 0 = 0) (hn : 2 < n) : hash_probe_tail_count n r 2 1 = 2 * n ^ 2 := by unfold hash_probe_tail_count rw [Finset.card_filter, Fintype.sum_prod_type] have hcond : ∀ (A : Fin 2 → ZMod n) (h : ZMod n), ((∀ j : Fin n, j.val < 1 → h + r j ∈ hash_occupied_slots n r (List.ofFn A)) ↔ h ∈ hash_occupied_slots n r (List.ofFn A)) := by intro A h constructor · intro hh simpa [hr0] using hh 0 (by simp) · intro hh j hj have hj0 : j.val = 0 := by omega have hjeq : j = 0 := Fin.ext hj0 subst hjeq simpa [hr0] using hh simp only [hcond] have hstep : ∀ A : Fin 2 → ZMod n, (∑ h : ZMod n, if h ∈ hash_occupied_slots n r (List.ofFn A) then (1:ℕ) else 0) = 2 := by intro A rw [← Finset.card_filter] have h2 : Finset.univ.filter (fun h : ZMod n => h ∈ hash_occupied_slots n r (List.ofFn A)) = hash_occupied_slots n r (List.ofFn A) := by ext h; simp rw [h2] exact hx_occ_card n r hr hn A simp only [hstep] rw [Finset.sum_const, Finset.card_univ, Fintype.card_fun, ZMod.card, Fintype.card_fin] simp [mul_comm]private lemma hx_tail_count_three (n : ℕ) [NeZero n] (r : Fin n → ZMod n) (hr : Function.Bijective r) (hr0 : r 0 = 0) (hn : 2 < n) {k : ℕ} (hk : 3 ≤ k) : hash_probe_tail_count n r 2 k = 0 := by unfold hash_probe_tail_count rw [Finset.card_eq_zero, ← Finset.not_nonempty_iff_eq_empty] rintro ⟨⟨A, x⟩, hp⟩ simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hp have hr1 := hx_one_ne_zero n hn r hr hr0 have hr2 := hx_two_ne_zero n hn r hr hr0 have hr12 := hx_one_ne_two n hn r hr have h2val : (2 : Fin n).val = 2 := by show 2 % n = 2 exact Nat.mod_eq_of_lt (by omega) have h0val : (0 : Fin n).val = 0 := by simp have m0 : x + r 0 ∈ hash_occupied_slots n r (List.ofFn A) := hp 0 (by rw [h0val]; omega) have m1 : x + r 1 ∈ hash_occupied_slots n r (List.ofFn A) := hp 1 (by rw [Fin.val_one', Nat.mod_eq_of_lt (by omega)]; omega) have m2 : x + r 2 ∈ hash_occupied_slots n r (List.ofFn A) := hp 2 (by rw [h2val]; omega) have e01 : x + r 0 ≠ x + r 1 := by intro hh have h00 : r 0 = r 1 := add_left_cancel hh rw [hr0] at h00 exact hr1 h00.symm have e02 : x + r 0 ≠ x + r 2 := by intro hh have h00 : r 0 = r 2 := add_left_cancel hh rw [hr0] at h00 exact hr2 h00.symm have e12 : x + r 1 ≠ x + r 2 := fun hh => hr12 (add_left_cancel hh) have hsub : ({x + r 0, x + r 1, x + r 2} : Finset (ZMod n)) ⊆ hash_occupied_slots n r (List.ofFn A) := by intro y hy simp only [Finset.mem_insert, Finset.mem_singleton] at hy rcases hy with h | h | h · subst h; exact m0 · subst h; exact m1 · subst h; exact m2 have hcard3 : ({x + r 0, x + r 1, x + r 2} : Finset (ZMod n)).card = 3 := by rw [Finset.card_insert_of_notMem (by simp [e01, e02]), Finset.card_insert_of_notMem (by simp [e12]), Finset.card_singleton] have hle := Finset.card_le_card hsub rw [hcard3, hx_occ_card n r hr hn A] at hle omegatheorem hash_probe_expected_cost_two (n : ℕ) [NeZero n] (hn : 2 < n) (r : Fin n → ZMod n) (hr : Function.Bijective r) (hr0 : r 0 = 0) : hash_probe_expected_cost n r 2 = 1 + 2 / (n : ℝ) + (3 + (if r 1 + r 1 = 0 then (1 : ℝ) else 0)) / (n : ℝ)^2 := by have hn0 : (n : ℝ) ≠ 0 := by have h : n ≠ 0 := NeZero.ne n positivity have hd : r 1 ≠ 0 := hx_one_ne_zero n hn r hr hr0 have h0 : hash_probe_tail_prob n r 2 0 = 1 := hash_probe_tail_prob_zero n r 2 have h1 : hash_probe_tail_prob n r 2 1 = 2 / (n : ℝ) := by rw [hash_probe_tail_prob, hx_tail_count_one n r hr hr0 hn] push_cast rw [show (n : ℝ) ^ 3 = (n : ℝ) ^ 2 * (n : ℝ) by ring] field_simp have h2 : hash_probe_tail_prob n r 2 2 = (3 + (if r 1 + r 1 = 0 then (1 : ℝ) else 0)) / (n : ℝ)^2 := by rw [hash_probe_tail_prob, hx_tail_count_two n r hr hr0 hn hd] by_cases hh : r 1 + r 1 = 0 · simp only [if_pos hh] have e1 : ((n * (3 + 1) : ℕ) : ℝ) = (n : ℝ) * 4 := by push_cast; ring rw [e1, show (n : ℝ) ^ 3 = (n : ℝ) * (n : ℝ) ^ 2 by ring] field_simp norm_num · simp only [if_neg hh] have e1 : ((n * 3 : ℕ) : ℝ) = (n : ℝ) * 3 := by push_cast; ring rw [e1, show (n : ℝ) ^ 3 = (n : ℝ) * (n : ℝ) ^ 2 by ring] field_simp norm_num unfold hash_probe_expected_cost have hsub : ({0, 1, 2} : Finset ℕ) ⊆ Finset.range (n + 1) := by intro x hx simp only [Finset.mem_insert, Finset.mem_singleton] at hx simp only [Finset.mem_range] rcases hx with h | h | h <;> omega have hzero : ∀ x ∈ Finset.range (n + 1), x ∉ ({0, 1, 2} : Finset ℕ) → hash_probe_tail_prob n r 2 x = 0 := by intro x _ hx2 simp only [Finset.mem_insert, Finset.mem_singleton, not_or] at hx2 have hx3 : 3 ≤ x := by omega rw [hash_probe_tail_prob, hx_tail_count_three n r hr hr0 hn hx3] simp rw [← Finset.sum_subset hsub hzero] rw [Finset.sum_insert (by simp), Finset.sum_insert (by simp), Finset.sum_singleton] rw [h0, h1, h2] ring