unit_first_fixed_offset_mean_probe_eq_zero
For every table size n ≥ 2 with [NeZero n] and every bijective probe sequence r : Fin n → ZMod n with r 0 = 0 and IsUnit (r 1), the expected insertion cost into an empty table (t = 0) under r equals that under linear probing, hash_probe_expected_cost n r 0 = hash_probe_expected_cost n (linear_probe_offset n) 0.
Statement
theorem unit_first_fixed_offset_mean_probe_eq_zero
(n : ℕ) [NeZero n] (hn : 2 ≤ n)
(r : Fin n → ZMod n) (hr_bij : Function.Bijective r)
(hr0 : r 0 = 0) (hr1 : IsUnit (r 1)) :
hash_probe_expected_cost n r 0 = hash_probe_expected_cost n (linear_probe_offset n) 0- Source
- folklore
- Verified
- 01 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- 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…
- 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…
Read back from the Lean
For any natural number n with n ≠ 0 and 2 ≤ n, and any function r : Fin n → ZMod n such that:
1. r is bijective (Function.Bijective r),
2. r 0 = 0, and
3. r 1 is a unit in ZMod n (IsUnit (r 1), i.e., coprime to n),
the expected hash probe cost hash_probe_expected_cost n r 0 with offset function r at insertion count t = 0 is equal to the expected hash probe cost hash_probe_expected_cost n (linear_probe_offset n) 0 with the canonical linear probing offset function linear_probe_offset n at insertion count 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
The expected cost of inserting a key into an empty hash table (load t = 0) is always 1, regardless of the probe sequence, because the very first probed slot is necessarily empty. Applying this identity to both the given probe sequence r and linear probing evaluates both sides to 1, immediately completing the proof.
Both expected costs equal 1, making them equal to each other.
Rewrite both sides using `hash_probe_expected_cost_zero`. Since an empty table contains no occupied slots, the initial probe always succeeds, so the expected insertion cost at load t = 0 is 1 for any probe sequence r as well as for linear probing. Both sides simplify to 1, leaving 1 = 1.
uses
hash_probe_expected_cost_zerorw [hash_probe_expected_cost_zero, hash_probe_expected_cost_zero]
hash_probe_expected_cost_zero- for any hash table of size n and any probe sequence r, the expected probe cost when the table is empty (t = 0) is 1
- The assumptions that n ≥ 2, that r is bijective, that r 0 = 0, and that r 1 is a unit are not used; the expected probe cost at load t = 0 equals 1 for any probe sequence.
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.
/-- OP-805 holds with equality at load t = 0 for any probe sequence with r 0 = 0 and unit first offset. -/theorem unit_first_fixed_offset_mean_probe_eq_zero (n : ℕ) [NeZero n] (hn : 2 ≤ n) (r : Fin n → ZMod n) (hr_bij : Function.Bijective r) (hr0 : r 0 = 0) (hr1 : IsUnit (r 1)) : hash_probe_expected_cost n r 0 = hash_probe_expected_cost n (linear_probe_offset n) 0 := by rw [hash_probe_expected_cost_zero, hash_probe_expected_cost_zero]