AFTD Auto-Formalizing Theoretical Domains

linear_probe_offset_bijective

theoremverified

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

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.

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

    lines 4–6

    uses Fintype.bijective_iff_injective_and_card

      unfold linear_probe_offset
      rw [Fintype.bijective_iff_injective_and_card]
      constructor
  2. 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.

    lines 7–10

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

    line 11

      · 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

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