prime_fixed_offset_linear_probe_tail_prob_interior_t_two
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.
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.
have hk : k = 2 := by omega subst hk
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.
uses
prime_fixed_offset_tail_prob_two_two,linear_probe_offset_bijective,linear_probe_offset_zerohave 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
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.
/-- 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]