AFTD Auto-Formalizing Theoretical Domains

prime_fixed_offset_linear_probe_tail_prob_interior_t_two

theoremverified

At load t = 2 (where k = 2), the probe tail probability under any bijective offset r with r 0 = 0 is bounded by linear probing on any prime table size p > 2.

Statement

theorem prime_fixed_offset_linear_probe_tail_prob_interior_t_two
    (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 ≤ 2) (ht : 2 < p) :
    hash_probe_tail_prob p r 2 k ≤ hash_probe_tail_prob p (linear_probe_offset p) 2 k
Source
step towards prime_fixed_offset_linear_probe_tail_prob_interior_le
Verified
03 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 6
  • 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…
  • linear_probe_offset_bijectiveFor any table size n with [NeZero n], linear_probe_offset n is bijective.
  • linear_probe_offset_zeroFor any table size n with [NeZero n], linear_probe_offset n 0 is 0.
  • 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…
  • 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 inequality is established by showing that both sides are in fact equal. The bounds 2 ≤ k and k ≤ 2 force k = 2. For any prime table size p > 2 and any bijective offset function fixing 0—which includes both the arbitrary offset r and linear probing—the tail probability at load t = 2 and threshold k = 2 evaluates to exactly 3 / p^2. Substituting this value on both sides yields 3 / p^2 ≤ 3 / p^2.

  1. The threshold k must be 2, reducing the claim to comparing the tail probabilities at t = 2 and k = 2.

    The hypotheses 2 ≤ k (hk2) and k ≤ 2 (hkt) squeeze k between 2 and 2, which linear integer arithmetic resolves to k = 2. Substituting 2 for k specializes the goal to showing that the tail probability for r at t = 2, k = 2 is bounded by that of linear probing.

    lines 7–8

      have hk : k = 2 := by omega
      subst hk
  2. Both tail probabilities equal 3 / p^2, so the inequality holds with equality.

    By prime_fixed_offset_tail_prob_two_two, on any prime table size p > 2, every bijective offset function fixing 0 has tail probability exactly 3 / p^2 when t = 2 and k = 2. This applies directly to r by assumption. It also applies to linear probing, since linear_probe_offset_bijective and linear_probe_offset_zero establish that linear probing is bijective and fixes 0. Rewriting both sides of the inequality with 3 / p^2 reduces the goal to 3 / p^2 ≤ 3 / p^2, which holds reflexively.

    lines 9–12

    uses prime_fixed_offset_tail_prob_two_two, linear_probe_offset_bijective, linear_probe_offset_zero

      have h1 := prime_fixed_offset_tail_prob_two_two p ht r hr_bij hr0
      have h2 := prime_fixed_offset_tail_prob_two_two p ht (linear_probe_offset p)
        (linear_probe_offset_bijective p) (linear_probe_offset_zero p)
      rw [h1, h2]
prime_fixed_offset_tail_prob_two_two
For any prime table size p > 2 and any bijective offset function r : Fin p → ZMod p with r(0) = 0, the probe tail probability at load t = 2 and threshold k = 2 equals 3 / p^2.
linear_probe_offset_bijective
The linear probing offset function on a table of size n is bijective.
linear_probe_offset_zero
The linear probing offset function on a table of size n maps 0 to 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

/-- At load t = 2 (where k = 2), the probe tail probability under any bijective offset r with r 0 = 0 is bounded by (in fact equal to) linear probing on any prime table size p > 2. -/theorem prime_fixed_offset_linear_probe_tail_prob_interior_t_two    (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 ≤ 2) (ht : 2 < p) :    hash_probe_tail_prob p r 2 k ≤ hash_probe_tail_prob p (linear_probe_offset p) 2 k := by  have hk : k = 2 := by omega  subst hk  have h1 := prime_fixed_offset_tail_prob_two_two p ht r hr_bij hr0  have h2 := prime_fixed_offset_tail_prob_two_two p ht (linear_probe_offset p)    (linear_probe_offset_bijective p) (linear_probe_offset_zero p)  rw [h1, h2]
See it in the graphDiscuss this resultChallenge it