AFTD Auto-Formalizing Theoretical Domains

prime_fixed_offset_mean_le_of_tail_le

theoremverified

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.

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

    line 5

    uses Finset.sum_le_sum

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

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