mixed_radix_offset_prime
For any positive integer p and any index j in Fin p, the mixed-radix reversed offset with singleton factor list [p] equals the linear probing offset j in ZMod p.
Statement
theorem mixed_radix_offset_prime (p : ℕ) [NeZero p] (j : Fin p) :
mixed_radix_offset p [p] j = linear_probe_offset p j- Source
- arXiv:2610.31363
- Verified
- 01 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- 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…
- 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…
- Used by 1
- fixed_offset_hash_worst_mean_mixed_radix_primeFor 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…
Read back from the Lean
For every natural number $p$ with $p \neq 0$ ([NeZero p]) and every $j \in \text{Fin } p$, mixed_radix_offset p [p] j equals linear_probe_offset p j.
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
For a singleton factor list [p], the mixed-radix reversed offset definition reduces to a single-term sum over Fin 1. The simplifier unfolds the definitions of mixed_radix_offset and linear_probe_offset, evaluates the prefix products, and uses p / p = 1 (from p > 0) to reduce the offset directly to j in ZMod p.
The mixed-radix reversed offset for the singleton list [p] equals the linear probing offset j in ZMod p. automation
Unfolding the definitions of mixed_radix_offset and linear_probe_offset, the list [p] has length 1, so the sum over Fin [p].length has only one term (i = 0). For that term, the prefix of length 0 has product 1, yielding (j / 1) % p = j % p = j, while the prefix of length 1 has product p, yielding p / p = 1 by Nat.div_self (justified by p > 0 via NeZero.pos). The product j * 1 in ZMod p simplifies to j, which matches linear_probe_offset p j.
uses
Nat.div_self,NeZero.possimp [mixed_radix_offset, linear_probe_offset, Nat.div_self (NeZero.pos p)]
Nat.div_self- A positive natural number divided by itself equals 1.
NeZero.pos- An element with a NeZero typeclass instance is strictly greater than zero.
- The simplifier silently handles multiple routine evaluations at once: reducing the sum over Fin 1 to its single term i = 0, taking prefix sublists of [p] and evaluating their products, and simplifying the modular arithmetic in ZMod p.
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 a prime size p, the mixed-radix reversed offset with singleton list [p] is linear probing. -/theorem mixed_radix_offset_prime (p : ℕ) [NeZero p] (j : Fin p) : mixed_radix_offset p [p] j = linear_probe_offset p j := by simp [mixed_radix_offset, linear_probe_offset, Nat.div_self (NeZero.pos p)]