prime_fixed_offset_mean_le_of_tail_le
For any prime table size p, offset sequence r : Fin p → ZMod p, and load t, if every probe-cost tail probability under r is bounded by the corresponding tail probability under linear probing, then the expected probe cost under r is at most the expected probe cost under linear probing.
Statement
theorem prime_fixed_offset_mean_le_of_tail_le
(p : ℕ) [Fact (Nat.Prime p)] (r : Fin p → ZMod p) (t : ℕ)
(h_tail : ∀ k : ℕ, hash_probe_tail_prob p r t k ≤ hash_probe_tail_prob p (linear_probe_offset p) t k) :
hash_probe_expected_cost p r t ≤ hash_probe_expected_cost p (linear_probe_offset p) t- Source
- arXiv:2610.31363: "A Sharp Analysis of Fixed Offset Hash Tables"
- Verified
- 02 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- 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_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…
- 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…
Read back from the Lean
For any prime natural number $p$ (assumed via [Fact (Nat.Prime p)]), any probe offset function $r : \mathrm{Fin}\; p \to \mathbb{Z}/p\mathbb{Z}$, and any natural number $t$ (representing the number of inserted elements):
If for all $k \in \mathbb{N}$, the tail probability of requiring at least $k$ probes under offset sequence $r$ is at most the tail probability under the standard linear probe offset function $j \mapsto (j : \mathbb{Z}/p\mathbb{Z})$ (that is, hash_probe_tail_prob p r t k ≤ hash_probe_tail_prob p (linear_probe_offset p) t k),
then the expected probe cost under $r$ is at most the expected probe cost under the standard linear probe offset function (that is, hash_probe_expected_cost p r t ≤ hash_probe_expected_cost p (linear_probe_offset p) t).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The expected probe cost is defined directly as the finite sum of probe-cost tail probabilities over k ∈ {0, …, p}. Because each tail probability under r is assumed to be at most that under linear probing, the inequality on expected costs follows immediately by termwise inequality of finite sums.
The expected probe cost under offset sequence r is at most that under linear probing.
By definition, hash_probe_expected_cost is the sum of the tail probabilities hash_probe_tail_prob over k ∈ Finset.range (p + 1). Applying Finset.sum_le_sum to the hypothesis h_tail—which states that each tail probability under r is bounded by the corresponding tail probability under linear probing—shows that the sum for r is at most the sum for linear probing.
uses
Finset.sum_le_sumhash_probe_expected_cost p r t ≤ hash_probe_expected_cost p (linear_probe_offset p) t := Finset.sum_le_sum fun k _ => h_tail k
Finset.sum_le_sum- If f(i) ≤ g(i) for all elements i of a finite set s, then ∑ i ∈ s, f(i) ≤ ∑ i ∈ s, g(i).
- The expected cost is definitionally equal to the finite sum of tail probabilities for k from 0 to p (the tail-sum formula for the expectation of a bounded variable), so no unfolding or expansion step is needed.
- The hypothesis that p is prime ([Fact (Nat.Prime p)]) is not used in this proof; the claim is a direct consequence of the definition of expected cost as a sum of tail probabilities and the monotonicity of summation.
Written by a model (gemini-3.8-flash) from the Lean source alone (no goal states were available). Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
/-- Pointwise tail probability dominance on a prime-size table implies expected probe cost dominance by linear probing. -/theorem prime_fixed_offset_mean_le_of_tail_le (p : ℕ) [Fact (Nat.Prime p)] (r : Fin p → ZMod p) (t : ℕ) (h_tail : ∀ k : ℕ, hash_probe_tail_prob p r t k ≤ hash_probe_tail_prob p (linear_probe_offset p) t k) : hash_probe_expected_cost p r t ≤ hash_probe_expected_cost p (linear_probe_offset p) t := Finset.sum_le_sum fun k _ => h_tail k