AFTD Auto-Formalizing Theoretical Domains

unit_first_fixed_offset_mean_probe_eq_zero

theoremverified

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.

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

    line 7

    uses hash_probe_expected_cost_zero

      rw [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

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

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