AFTD Auto-Formalizing Theoretical Domains

fixed_offset_hash_worst_mean_mixed_radix_prime

theoremverified

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.

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

    lines 9–10

      use [p]
      constructor
  2. 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.

    line 11

    uses Nat.primeFactorsList_prime, Fact.out

      · rw [Nat.primeFactorsList_prime Fact.out]
  3. 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`.

    lines 12–14

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

    lines 15–16

        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.

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

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