AFTD Auto-Formalizing Theoretical Domains

hash_probe_tail_two_eq_adjacent_mean

theoremverified

The second probe-cost tail equals the expected number of occupied adjacent pairs, divided by the table size.

Statement

theorem hash_probe_tail_two_eq_adjacent_mean (n : ℕ) [NeZero n] (hn : 2 ≤ n)
  (r : Fin n → ZMod n) (hr0 : r 0 = 0) (t : ℕ) :
  (n : ℝ) * hash_probe_tail_prob n r t 2 =
    (∑ A : Fin t → ZMod n,
      (hash_adjacent_count n (r 1) (hash_occupied_slots n r (List.ofFn A)) : ℝ)) / (n : ℝ)^t
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 5
  • hash_adjacent_countThe number of occupied slots whose d-successor is also occupied.
  • 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…
  • OrderAn order of dimension d is a permutation of the attribute set {0, ..., d-1}, represented as a list without duplicates containing all…

The proof, explained

A probe sequence takes at least two steps if and only if both the initial slot and the second probe slot are occupied; because r 0 = 0, this means both x and x + r 1 are in the table, identifying such starting locations with occupied adjacent pairs. Summing over all t-step hash sequences equates the total probe tail count to the sum of adjacent pair counts across all tables. Dividing by the sample space size n^(t + 1) and multiplying by n cancels one factor of n, showing that n times the tail probability equals the expected number of adjacent occupied pairs divided by n^t.

  1. Membership in {x | ∀ j < 2, x + r j ∈ T} reduces to (∀ j ≤ 1, x + r j ∈ T) ↔ (x ∈ T ∧ x + r 1 ∈ T), with the values of the indices 0 and 1 in Fin n known to be 0 and 1.

    By set extensionality, an element x belongs to the filtered set if and only if x + r j ∈ T for all indices j with j < 2. Because j < 2 is equivalent to j ≤ 1 on natural numbers, and n ≥ 2 ensures that the elements 0 and 1 of Fin n have numerical values 0 and 1, the condition becomes (∀ j ≤ 1, x + r j ∈ T).

    lines 8–13

    uses mem_filter, mem_univ, true_and, Order.lt_two_iff, Fin.val_one', Nat.mod_eq_of_lt, Fin.val_zero

      ext x
      simp only [mem_filter, mem_univ, true_and, Order.lt_two_iff]
      have h1_val : (1 : Fin n).val = 1 := by
        rw [Fin.val_one']
        exact Nat.mod_eq_of_lt (by omega)
      have h0_val : (0 : Fin n).val = 0 := Fin.val_zero n
  2. If x + r j ∈ T for all j ≤ 1, then x ∈ T and x + r 1 ∈ T.

    Specializing the hypothesis to j = 0 (since 0 ≤ 1) and using r 0 = 0 gives x + 0 = x ∈ T. Specializing to j = 1 (since 1 ≤ 1) gives x + r 1 ∈ T.

    lines 14–23

    uses add_zero

      constructor
      · intro h
        have h0 : x ∈ T := by
          have hj : (0 : Fin n).val ≤ 1 := by rw [h0_val]; decide
          have h' := h 0 hj
          rwa [hr0, add_zero] at h'
        have h1 : x + r 1 ∈ T := by
          have hj : (1 : Fin n).val ≤ 1 := by rw [h1_val]
          exact h 1 hj
        exact ⟨h0, h1⟩
  3. Conversely, if x ∈ T and x + r 1 ∈ T, then x + r j ∈ T for every j ≤ 1, completing the set equality.

    For any index j with j ≤ 1, either j.val = 0 or j.val = 1. In the first case, j = 0, so x + r j = x + r 0 = x ∈ T. In the second case, j = 1, so x + r j = x + r 1 ∈ T. Hence the two sets of slots coincide.

    lines 24–31

    uses Nat.le_one_iff_eq_zero_or_eq_one.mp, add_zero

      · intro ⟨h0, h1⟩ j hj
        rcases Nat.le_one_iff_eq_zero_or_eq_one.mp hj with hj0 | hj1
        · have : j = 0 := by ext; rw [hj0, h0_val]
          rw [this, hr0, add_zero]
          exact h0
        · have : j = 1 := by ext; rw [hj1, h1_val]
          rw [this]
          exact h1
  4. The total probe tail count for k = 2 equals the sum over all hash sequences A of the number of occupied adjacent pairs in the resulting table.

    Unfolding the definition of tail count gives the cardinality of pairs (A, x) where probing at x takes at least 2 steps in table T(A). Rewriting this cardinality as a sum of indicators and splitting over the product type turns it into an outer sum over hash sequences A and an inner sum over starting positions x. For each fixed table, the inner sum counts elements whose first two probe steps lie in T(A), which the set equality lemma equates to the adjacent count {x ∈ T(A) | x + r 1 ∈ T(A)}.

    lines 38–43

    uses card_filter, Fintype.sum_prod_type, hash_probe_tail_two_eq_adjacent_mean_filter_finset

      unfold hash_probe_tail_count
      simp_rw [card_filter, Fintype.sum_prod_type]
      congr 1 with A
      rw [← card_filter]
      unfold hash_adjacent_count
      rw [hash_probe_tail_two_eq_adjacent_mean_filter_finset n hn r hr0]
  5. Unfolding the probe tail probability expresses n * ℙ(probe cost ≥ 2) as n * (∑_A adjacent_count(T(A))) / n^(t + 1).

    The tail probability is defined as the tail count divided by the total number of choices n^(t + 1). Substituting the tail count formula from the previous lemma and distributing the real coercion over the sum yields n times the sum of adjacent counts divided by n^(t + 1).

    lines 50–52

    uses hash_probe_tail_two_eq_adjacent_mean_tail_count_eq

      unfold hash_probe_tail_prob
      rw [hash_probe_tail_two_eq_adjacent_mean_tail_count_eq n hn r hr0 t]
      push_cast
  6. Cancelling the factor of n in the numerator against one power of n in the denominator leaves the adjacent count sum divided by n^t.

    Because n ≠ 0 in ℝ, the denominator factors as n^(t + 1) = n^t * n. Rewriting division by a product as iterated division allows cancelling n with the denominator's n factor via mul_div_cancel₀.

    lines 53–56

    uses NeZero.ne, pow_succ, div_mul_eq_div_div, mul_div_cancel₀

      have hn_ne : (n : ℝ) ≠ 0 := by exact_mod_cast NeZero.ne n
      have hpow : (n : ℝ) ^ (t + 1) = (n : ℝ) ^ t * (n : ℝ) := by rw [pow_succ]
      rw [hpow]
      rw [div_mul_eq_div_div, mul_div_cancel₀ _ hn_ne]
mem_filter
An element belongs to the filtered finset {x ∈ s | p x} if and only if it belongs to s and satisfies p.
mem_univ
Every element of a finite type belongs to the universal finset univ.
true_and
The conjunction True ∧ p simplifies to p.
Order.lt_two_iff
In a discrete linear order, x < 2 is equivalent to x ≤ 1.
Fin.val_one'
The numerical value of 1 in Fin n is 1 mod n.
Nat.mod_eq_of_lt
If a < b, then a mod b = a.
Fin.val_zero
The numerical value of 0 in Fin n is 0.
add_zero
Adding zero to an element leaves it unchanged (a + 0 = a).
Nat.le_one_iff_eq_zero_or_eq_one.mp
If a natural number is at most 1, it is either 0 or 1.
card_filter
The size of a filtered finset equals the sum of indicator values (1 if the predicate holds, 0 otherwise) over the ambient finset.
Fintype.sum_prod_type
A sum over a product type α₁ × α₂ equals the iterated sum over α₁ and α₂.
hash_probe_tail_two_eq_adjacent_mean_filter_finset
For any set of occupied slots T with table size n ≥ 2 and probe base r 0 = 0, the set of starting locations whose first two probe steps lie in T equals {x ∈ T | x + r 1 ∈ T}.
hash_probe_tail_two_eq_adjacent_mean_tail_count_eq
The total count of probe sequences taking at least 2 steps across all hash sequences of length t equals the sum over all hash sequences of the number of occupied adjacent pairs in the resulting table.
NeZero.ne
An element with a NeZero instance is not equal to zero.
pow_succ
In a monoid, a^(n + 1) = a^n * a.
div_mul_eq_div_div
In division monoids, a / (b * c) = (a / b) / c.
mul_div_cancel₀
In a group with zero, multiplying b by a / b yields a when b ≠ 0.

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 Finsetprivate lemma hash_probe_tail_two_eq_adjacent_mean_filter_finset    (n : ℕ) [NeZero n] (hn : 2 ≤ n) (r : Fin n → ZMod n) (hr0 : r 0 = 0)    (T : Finset (ZMod n)) :    univ.filter (fun x : ZMod n => ∀ j : Fin n, j.val < 2 → x + r j ∈ T) =      {x ∈ T | x + r 1 ∈ T} := by  ext x  simp only [mem_filter, mem_univ, true_and, Order.lt_two_iff]  have h1_val : (1 : Fin n).val = 1 := by    rw [Fin.val_one']    exact Nat.mod_eq_of_lt (by omega)  have h0_val : (0 : Fin n).val = 0 := Fin.val_zero n  constructor  · intro h    have h0 : x ∈ T := by      have hj : (0 : Fin n).val ≤ 1 := by rw [h0_val]; decide      have h' := h 0 hj      rwa [hr0, add_zero] at h'    have h1 : x + r 1 ∈ T := by      have hj : (1 : Fin n).val ≤ 1 := by rw [h1_val]      exact h 1 hj    exact ⟨h0, h1⟩  · intro ⟨h0, h1⟩ j hj    rcases Nat.le_one_iff_eq_zero_or_eq_one.mp hj with hj0 | hj1    · have : j = 0 := by ext; rw [hj0, h0_val]      rw [this, hr0, add_zero]      exact h0    · have : j = 1 := by ext; rw [hj1, h1_val]      rw [this]      exact h1private lemma hash_probe_tail_two_eq_adjacent_mean_tail_count_eq    (n : ℕ) [NeZero n] (hn : 2 ≤ n)    (r : Fin n → ZMod n) (hr0 : r 0 = 0) (t : ℕ) :    hash_probe_tail_count n r t 2 =      ∑ A : Fin t → ZMod n, hash_adjacent_count n (r 1) (hash_occupied_slots n r (List.ofFn A)) := by  unfold hash_probe_tail_count  simp_rw [card_filter, Fintype.sum_prod_type]  congr 1 with A  rw [← card_filter]  unfold hash_adjacent_count  rw [hash_probe_tail_two_eq_adjacent_mean_filter_finset n hn r hr0]theorem hash_probe_tail_two_eq_adjacent_mean (n : ℕ) [NeZero n] (hn : 2 ≤ n)  (r : Fin n → ZMod n) (hr0 : r 0 = 0) (t : ℕ) :  (n : ℝ) * hash_probe_tail_prob n r t 2 =    (∑ A : Fin t → ZMod n,      (hash_adjacent_count n (r 1) (hash_occupied_slots n r (List.ofFn A)) : ℝ)) / (n : ℝ)^t := by  unfold hash_probe_tail_prob  rw [hash_probe_tail_two_eq_adjacent_mean_tail_count_eq n hn r hr0 t]  push_cast  have hn_ne : (n : ℝ) ≠ 0 := by exact_mod_cast NeZero.ne n  have hpow : (n : ℝ) ^ (t + 1) = (n : ℝ) ^ t * (n : ℝ) := by rw [pow_succ]  rw [hpow]  rw [div_mul_eq_div_div, mul_div_cancel₀ _ hn_ne]
See it in the graphDiscuss this resultChallenge it