AFTD Auto-Formalizing Theoretical Domains

mixed_radix_offset_prime

theoremverified

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

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.

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

    line 4

    uses Nat.div_self, NeZero.pos

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

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