AFTD Auto-Formalizing Theoretical Domains

linear_probe_offset_zero

theoremverified

For any table size n with [NeZero n], linear_probe_offset n 0 is 0.

Statement

theorem linear_probe_offset_zero (n : ℕ) [NeZero n] :
    linear_probe_offset n 0 = 0
Source
step towards unit_first_fixed_offset_mean_probe_maximum
Verified
02 Nov 2026
Axioms
Quot.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 proof proceeds by unfolding the definition of `linear_probe_offset`, which maps an index $j \in \mathrm{Fin}\ n$ to $(j : \mathbb{Z}/n\mathbb{Z})$. At index $0$, this yields the coercion of $0 \in \mathrm{Fin}\ n$ into $\mathbb{Z}/n\mathbb{Z}$, which simplifies immediately to $0$.

  1. Expanding the definition reduces the offset to the coercion of $0 \in \mathrm{Fin}\ n$ into $\mathbb{Z}/n\mathbb{Z}$.

    By definition, $\mathrm{linear\_probe\_offset}(n, j)$ is the index $j$ viewed in $\mathbb{Z}/n\mathbb{Z}$. Unfolding this definition specializes $j$ to $0$, transforming the goal into showing that the coercion of $0 \in \mathrm{Fin}\ n$ into $\mathbb{Z}/n\mathbb{Z}$ equals $0$.

    line 4

      unfold linear_probe_offset
  2. The coercion of the zero index into $\mathbb{Z}/n\mathbb{Z}$ is $0$. automation

    The element $0 \in \mathrm{Fin}\ n$ corresponds to the natural number $0$, whose canonical image in $\mathbb{Z}/n\mathbb{Z}$ is $0$. The simplifier resolves these coercions of zero to close the goal.

    line 5

      simp

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 at index 0 is 0 in ZMod n. -/theorem linear_probe_offset_zero (n : ℕ) [NeZero n] :    linear_probe_offset n 0 = 0 := by  unfold linear_probe_offset  simp
See it in the graphDiscuss this resultChallenge it