linear_probe_offset_zero
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
- 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 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$.
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$.
unfold linear_probe_offsetThe 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.
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
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 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