fixed_offset_hash_worst_mean_mixed_radix_prime
For any prime p, any bijective offset sequence r : Fin p → ZMod p, and any load t < p, if linear probing achieves expected probe cost at least that of r, then there exists an ordering P of the prime factors of p such that the expected probe cost under r is at most that under the mixed-radix offset for P.
Statement
theorem fixed_offset_hash_worst_mean_mixed_radix_prime
(p : ℕ) [Fact (Nat.Prime p)]
(r : Fin p → ZMod p) (hr_bij : Function.Bijective r)
(t : ℕ) (ht : t < p)
(h_lin : hash_probe_expected_cost p r t ≤ hash_probe_expected_cost p (linear_probe_offset p) t) :
∃ P : List ℕ, P.Perm (Nat.primeFactorsList p) ∧
hash_probe_expected_cost p r t ≤ hash_probe_expected_cost p (mixed_radix_offset p P) t- Source
- arXiv:2610.31363
- Verified
- 01 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- 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…
- mixed_radix_offset_primeFor any positive integer p and any index j in Fin p, the mixed-radix reversed offset with singleton factor list [p] equals the linear…
- 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_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 prime natural number $p$, any function $r : \text{Fin } p \to \mathbb{Z}/p\mathbb{Z}$, if $r$ is bijective, and for any natural number $t < p$, if the expected hash probe cost hash_probe_expected_cost p r t is less than or equal to hash_probe_expected_cost p (linear_probe_offset p) t, then there exists a list of natural numbers $P$ that is a permutation of the prime factors of $p$ (Nat.primeFactorsList p) such that the expected hash probe cost of $r$ with parameter $t$ is less than or equal to the expected hash probe cost of the mixed-radix offset sequence mixed_radix_offset p P with parameter $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 theorem is proved by choosing the singleton list P = [p] as the ordering of the prime factors. Because p is prime, its unique prime factor list is [p], so the permutation condition is immediate. Furthermore, for a single prime factor, the mixed-radix offset coincides pointwise with standard linear probing, so the cost bound follows directly from the assumption that linear probing dominates r.
It suffices to show that [p] is a permutation of the prime factors of p, and that the expected probe cost under r is at most that under the mixed-radix offset for [p].
We choose the singleton list [p] as the witness for the ordering P of the prime factors of p, reducing the existential statement to two subgoals: the permutation condition and the probe cost bound.
use [p] constructor
The singleton list [p] is a permutation of the prime factors of p.
Since p is prime (retrieved from the typeclass assumption using `Fact.out`), its list of prime factors is the singleton list [p] by `Nat.primeFactorsList_prime`. Rewriting with this identity turns the goal into showing that [p] is a permutation of [p], which holds by reflexivity.
uses
Nat.primeFactorsList_prime,Fact.out· rw [Nat.primeFactorsList_prime Fact.out]The mixed-radix offset sequence for [p] is identical to linear probing.
By function extensionality (`ext j`), it suffices to show that both offsets agree at every index j. For a prime table size p with factor list [p], this pointwise equality is established by `mixed_radix_offset_prime`.
uses
mixed_radix_offset_prime· have h_eq : mixed_radix_offset p [p] = linear_probe_offset p := by ext j exact mixed_radix_offset_prime p j
The expected probe cost under r is at most that under the mixed-radix offset for [p].
Rewriting the mixed-radix offset with the equivalence to linear probing turns the goal into the hypothesis `h_lin`, which states that linear probing achieves expected probe cost at least that of r.
rw [h_eq] exact h_lin
Nat.primeFactorsList_prime- For any prime number p, the list of its prime factors is the singleton list [p].
Fact.out- Retrieves the underlying proposition p from a `Fact p` instance.
mixed_radix_offset_prime- For a prime table size p, the mixed-radix offset sequence for [p] is pointwise equal to linear probing.
- In Lean, the primality of p is supplied as a typeclass instance `Fact (Nat.Prime p)`, from which the mathematical proposition `Nat.Prime p` is retrieved via `Fact.out`.
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.
/-- For prime table size, OP-809 reduces to linear probing maximizing the expected probe cost. -/theorem fixed_offset_hash_worst_mean_mixed_radix_prime (p : ℕ) [Fact (Nat.Prime p)] (r : Fin p → ZMod p) (hr_bij : Function.Bijective r) (t : ℕ) (ht : t < p) (h_lin : hash_probe_expected_cost p r t ≤ hash_probe_expected_cost p (linear_probe_offset p) t) : ∃ P : List ℕ, P.Perm (Nat.primeFactorsList p) ∧ hash_probe_expected_cost p r t ≤ hash_probe_expected_cost p (mixed_radix_offset p P) t := by use [p] constructor · rw [Nat.primeFactorsList_prime Fact.out] · have h_eq : mixed_radix_offset p [p] = linear_probe_offset p := by ext j exact mixed_radix_offset_prime p j rw [h_eq] exact h_lin