linear_probe_offset_bijective
For any table size n with [NeZero n], linear_probe_offset n is bijective.
Statement
theorem linear_probe_offset_bijective (n : ℕ) [NeZero n] :
Function.Bijective (linear_probe_offset n)- Source
- step towards unit_first_fixed_offset_mean_probe_maximum
- Verified
- 02 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- 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
- 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…
The proof, explained
The linear probe offset is defined as the canonical coercion from Fin n to ZMod n. For finite types of the same size, bijectivity is equivalent to injectivity. Injectivity follows because every element of Fin n is strictly less than n, so taking the integer representative of its residue modulo n recovers the original index.
Bijectivity reduces to showing that the canonical coercion Fin n → ZMod n is injective and that Fin n and ZMod n have the same cardinality.
Unfolding the definition of `linear_probe_offset`, the map simply sends each index j to its canonical coercion in ℤ/nℤ. For maps between finite types, `Fintype.bijective_iff_injective_and_card` reduces bijectivity to injectivity together with equal cardinality of the domain and codomain. Splitting the conjunction (`constructor`) yields two separate subgoals.
uses
Fintype.bijective_iff_injective_and_cardunfold linear_probe_offset rw [Fintype.bijective_iff_injective_and_card] constructor
The map is injective: if two indices in Fin n have the same image in ZMod n, they are equal.
Let a and b in Fin n have identical images in ℤ/nℤ (assumption `hab`). By extensionality on Fin n (`ext`), it suffices to show that their underlying natural numbers are equal. Since both a and b are strictly less than n, `ZMod.val_cast_of_lt` rewrites each underlying natural number as the standard representative `ZMod.val` of its cast into ℤ/nℤ. Applying `ZMod.val` to both sides of the hypothesis `hab` via `congrArg` completes the equality.
uses
ZMod.val_cast_of_lt,congrArg· intro a b hab ext rw [← ZMod.val_cast_of_lt a.isLt, ← ZMod.val_cast_of_lt b.isLt] exact congrArg ZMod.val hab
The cardinalities of Fin n and ZMod n are equal.
Both Fin n and ZMod n have cardinality n, so `simp` computes both sides and discharges the equality immediately.
· simp
Fintype.bijective_iff_injective_and_card- A map between finite types is bijective if and only if it is injective and the domain and codomain have the same cardinality.
ZMod.val_cast_of_lt- For any natural number a < n, the standard representative of a modulo n is a itself.
congrArg- If two elements are equal, applying any function to both produces equal values.
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.
/-- The linear probe offset sequence is a bijection from Fin n to ZMod n. -/theorem linear_probe_offset_bijective (n : ℕ) [NeZero n] : Function.Bijective (linear_probe_offset n) := by unfold linear_probe_offset rw [Fintype.bijective_iff_injective_and_card] constructor · intro a b hab ext rw [← ZMod.val_cast_of_lt a.isLt, ← ZMod.val_cast_of_lt b.isLt] exact congrArg ZMod.val hab · simp