linear_probe_offset
def
Given 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 coercion (j : ZMod n) in ZMod n.
Statement
def linear_probe_offset (n : ℕ) : Fin n → ZMod n- Defined in
- arXiv:2610.31363, Section 1
- Verified
- 01 Nov 2026
- Axioms
- none listed
- Used by 12
- linear_probe_offset_zeroFor any table size n with [NeZero n], linear_probe_offset n 0 is 0.
- 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…
- linear_probing_displacementsGiven a table size n and a sequence of n home slots h in Fin n -> ZMod n, linear_probing_displacements n h i is the number of occupied…
- unit_first_fixed_offset_mean_probe_eq_zeroFor every table size n ≥ 2 with [NeZero n] and every bijective probe sequence r : Fin n → ZMod n with r 0 = 0 and IsUnit (r 1), the…
- prime_fixed_offset_linear_probe_tail_prob_interior_t_twoAt load t = 2 (where k = 2), the probe tail probability under any bijective offset r with r 0 = 0 is bounded by linear probing on any…
- 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…
- prime_fixed_offset_mean_le_of_tail_leFor any prime table size p, offset sequence r : Fin p → ZMod p, and load t, if every probe-cost tail probability under r is bounded by the…
- prime_fixed_offset_linear_probe_stochastic_maximum_threeFor a 3-slot hash table (p = 3), every bijective probe sequence r : Fin 3 → ZMod 3 with r 0 = 0, every load t < 3, and every integer k ≥…
- unit_first_fixed_offset_mean_probe_maximum_threeFor a 3-slot hash table (n = 3), every bijective probe sequence r : Fin 3 → ZMod 3 with r 0 = 0 and IsUnit (r 1), and every load t < 3,…
- linear_probe_offset_bijectiveFor any table size n with [NeZero n], linear_probe_offset n is bijective.
- prime_fixed_offset_linear_probe_tail_prob_interior_t_predAt load t = p - 1 (one empty slot), every bijective offset sequence has identical probe tail probabilities, matching linear probing.
- hash_adjacent_step_counterexampleOn a fixed occupied set, a unit-first order can create more adjacent pairs on average in the next step than linear probing.
Read back from the Lean
For any natural number n, linear_probe_offset n is defined as the function from Fin n to ZMod n that maps each index j : Fin n to its coercion in ZMod n (i.e., j considered as an element of the integers modulo n).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- The linear probing offset sequence r(j) = j on a hash table of size n. -/ def linear_probe_offset (n : ℕ) : Fin n → ZMod n := fun j => (j : ZMod n)