AFTD Auto-Formalizing Theoretical Domains

mixed_radix_offset_mean_probe_zero

theoremverified

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.

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

    line 6

    uses hash_probe_expected_cost_zero

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

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

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