AFTD Auto-Formalizing Theoretical Domains

hash_probe_expected_cost_two

theoremverified

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

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.

  1. 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.

    lines 1–9

    uses List.foldl_append

    open 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
    
  2. 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}.

    lines 10–25

    uses Finset.mem_filter, Finset.mem_univ, true_and, dif_pos, le_antisymm, Fin.zero_le, Finset.min'_le

    private 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]
    
  3. 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}.

    lines 26–46

    uses List.nil_append, hash_occupied_slots_nil, List.cons_append

    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)]
      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
    
  4. 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}.

    lines 47–90

    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_def

    private 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
    
  5. 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].

    lines 91–158

    uses Finset.sum_ite_mem, Finset.univ_inter, Finset.sum_pair, false_or, or_false, if_pos, if_neg

    private 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))]
    
  6. 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.

    lines 159–204

    uses Fin.ext

    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 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]
    
  7. 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.

    lines 205–247

    uses Fintype.sum_prod_type, Fintype.sum_equiv, finTwoArrowEquiv, hash_occupied_slots_card, List.length_ofFn

    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
      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
    
  8. 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.

    lines 248–288

    uses Finset.card_filter, List.ofFn_succ, Finset.sum_add_distrib, Finset.sum_congr, Finset.sum_const, Finset.card_univ, ZMod.card

    private 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
    
  9. 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.

    lines 289–318

    uses Fintype.card_fun, Fintype.card_fin

    private 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]
    
  10. 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.

    lines 319–362

    uses Finset.card_eq_zero, Finset.not_nonempty_iff_eq_empty, Finset.card_insert_of_notMem, Finset.card_singleton, Finset.card_le_card

    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
      omega
    
  11. 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.

    lines 363–390

    uses NeZero.ne, hash_probe_tail_prob_zero, hash_probe_tail_prob

    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 := 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
  12. 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.

    lines 391–407

    uses Finset.mem_range, Finset.sum_subset, Finset.sum_insert

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

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
See it in the graphDiscuss this resultChallenge it