AFTD Auto-Formalizing Theoretical Domains

prime_fixed_offset_linear_probe_tail_prob_interior_t_pred

theoremverified

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.

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

    lines 7–13

    uses Finset.card_univ, ZMod.card, Finset.card_compl, Nat.pos_of_ne_zero, NeZero.ne, Finset.card_eq_one.mp

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

    lines 14–20

    uses Finset.mem_compl, Finset.mem_singleton

      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)
  3. 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.

    lines 21–40

    uses Finset.mem_filter, Finset.mem_sdiff, Finset.mem_univ, true_and, Finset.mem_image

      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⟩
  4. 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.

    lines 41–51

    uses Finset.card_sdiff, Finset.inter_univ, Finset.card_image_of_injective, Fin.card_filter_val_lt, Nat.min_eq_right, congrArg

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

    lines 57–67

    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_card

      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 hk
  6. 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₂.

    lines 71–75

    uses ZMod.natCast_eq_natCast_iff', Nat.mod_eq_of_lt, Fin.ext

      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'
  7. Linear probing offset function linear_probe_offset p is bijective.

    An injective map between two finite sets of the same cardinality p is bijective.

    lines 79–81

    uses Fintype.bijective_iff_injective_and_card, prime_fixed_offset_linear_probe_tail_prob_interior_t_pred_linear_probe_injective, ZMod.card

      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]⟩
  8. 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).

    lines 89–94

    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_bijective

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

    lines 95–96

      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.

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

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