mixed_radix_offset_mean_probe_zero
For every table size n ≥ 2, every probe sequence r : Fin n → ZMod n, and every factor list P, the expected probe cost into an empty table (t = 0) under r is at most the expected probe cost under the mixed-radix offset sequence for P.
Statement
theorem mixed_radix_offset_mean_probe_zero
(n : ℕ) [NeZero n] (hn : 2 ≤ n)
(r : Fin n → ZMod n) (P : List ℕ) :
hash_probe_expected_cost n r 0 ≤ hash_probe_expected_cost n (mixed_radix_offset n P) 0- Source
- arXiv:2610.31363
- Verified
- 01 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- mixed_radix_offsetGiven a table size n, an ordered list of factors P, and an index j in Fin n, mixed_radix_offset n P j is the element of ZMod n given by…
- hash_probe_expected_cost_zeroFor any table size n with [NeZero n] and any offset sequence r : Fin n → ZMod n, the expected probe cost hash_probe_expected_cost n r 0…
- 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…
Read back from the Lean
For any natural number n ≥ 2 (with n ≠ 0), any probe offset function r : Fin n → ZMod n, and any list of natural numbers P, the expected probe cost of r at t = 0 (after 0 keys have been inserted) is less than or equal to the expected probe cost of the mixed radix offset probe sequence defined by P at t = 0.
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
When a hash table is empty ($t = 0$), the first probed slot is always free regardless of the probe sequence chosen, so every probe sequence achieves an expected cost of exactly 1. By rewriting both sides of the inequality using this fact, the claim reduces to $1 \le 1$, which holds trivially.
Both expected costs equal 1, reducing the inequality to $1 \le 1$.
By `hash_probe_expected_cost_zero`, the expected probe cost when the table is empty ($t = 0$) is identically 1 regardless of the probe sequence. Rewriting both the left-hand side (for $r$) and the right-hand side (for the mixed-radix offset) with this lemma simplifies the goal to $1 \le 1$, which holds by reflexivity.
uses
hash_probe_expected_cost_zerorw [hash_probe_expected_cost_zero, hash_probe_expected_cost_zero]
hash_probe_expected_cost_zero- For any table size $n \ge 1$ and any probe sequence $r$, the expected probe cost into an empty table ($t = 0$) equals 1.
- The `rw` tactic automatically closes the reflexive inequality $1 \le 1$ after substitution.
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 = 0, any offset sequence achieves expected cost at most the mixed-radix offset cost. -/theorem mixed_radix_offset_mean_probe_zero (n : ℕ) [NeZero n] (hn : 2 ≤ n) (r : Fin n → ZMod n) (P : List ℕ) : hash_probe_expected_cost n r 0 ≤ hash_probe_expected_cost n (mixed_radix_offset n P) 0 := by rw [hash_probe_expected_cost_zero, hash_probe_expected_cost_zero]