prime_fixed_offset_linear_probe_stochastic_maximum_three
For 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 ≥ 0, the probability hash_probe_tail_prob 3 r t k of requiring strictly more than k probes is at most that under linear probing hash_probe_tail_prob 3 (linear_probe_offset 3) t k.
Statement
theorem prime_fixed_offset_linear_probe_stochastic_maximum_three
(r : Fin 3 → ZMod 3) (hr_bij : Function.Bijective r) (hr0 : r 0 = 0)
(t : ℕ) (ht : t < 3) (k : ℕ) :
hash_probe_tail_prob 3 r t k ≤ hash_probe_tail_prob 3 (linear_probe_offset 3) t k- Formalizes
- arXiv:2610.31363: "A Sharp Analysis of Fixed Offset Hash Tables"
- Verified
- 02 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- hash_probe_tail_probFor a table size n with [NeZero n], an offset sequence r : Fin n → ZMod n, and natural numbers t and k, hash_probe_tail_prob n r t k is…
- 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…
- 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,…
- hash_occupied_slotsThe set of occupied slots in Finset (ZMod n) after sequentially inserting a list A : List (ZMod n) into an initially empty hash table of…
- hash_probe_tail_countThe number of pairs of an insertion sequence of length t and an additional query slot whose insertion cost under offset sequence r…
Read back from the Lean
For every function r : Fin 3 → ZMod 3, assuming that r is bijective and r(0) = 0, for every natural number t such that t < 3, and for every natural number k, the hash probe tail probability hash_probe_tail_prob 3 r t k is less than or equal to hash_probe_tail_prob 3 (linear_probe_offset 3) t k (the tail probability under standard linear probing offsets).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
To bound the probe tail probability for any bijective offset sequence r on 3 slots fixing 0, the proof first classifies r: any such permutation must be either standard linear probing or its reverse. If r is linear probing, the inequality holds trivially by reflexivity. For reversed linear probing, the tail counts are shown to equal those of linear probing for every threshold k: for k < 4 this is an established equality, and for k ≥ 4 both tail counts truncate to their values at k = 3 because probe indices in a 3-slot table are bounded by 3. Consequently, both probing strategies have identical tail probabilities for all k, establishing the upper bound.
Equality of the tail counts for k and n reduces to the equivalence of the probe conditions ∀ (j : Fin n), j < k → ... and ∀ (j : Fin n), j < n → ... for every configuration pair p.
We unfold the definition of hash_probe_tail_count, which counts insertion history and query pairs p whose probe slots at all indices j below the threshold are occupied. Equating the cardinalities of these two filtered finsets reduces by extensionality to proving that a pair p satisfies the condition for threshold k if and only if it satisfies the condition for threshold n.
uses
Finset.mem_filter,Finset.mem_univ,true_anddsimp [hash_probe_tail_count] congr 1 ext p simp only [Finset.mem_filter, Finset.mem_univ, true_and] constructor
For any table size n and threshold k ≥ n, the probe tail count at k equals the tail count at n.
In the forward direction, if j < n, then j < k because n ≤ k (via lt_of_lt_of_le). In the backward direction, any index j : Fin n automatically satisfies j < n by definition (j.is_lt). This establishes the two-way implication and proves the auxiliary lemma.
uses
lt_of_lt_of_le· intro h j hj exact h j (lt_of_lt_of_le j.is_lt hk) · intro h j hj exact h j j.is_lt
Any bijective offset sequence r on Fin 3 with r 0 = 0 is either linear probing or reversed linear probing, and the theorem holds trivially in the linear probing case.
By unit_first_fixed_offset_mean_probe_maximum_three_r_eq_or_eq, an injective map from Fin 3 to ZMod 3 fixing 0 must be either standard linear probing (linear_probe_offset 3) or reversed linear probing (unit_first_fixed_offset_mean_probe_maximum_three_r_rev). If r is linear probing, the inequality is reflexivity (le_rfl).
uses
unit_first_fixed_offset_mean_probe_maximum_three_r_eq_or_eq,le_rflrcases unit_first_fixed_offset_mean_probe_maximum_three_r_eq_or_eq r hr_bij.injective hr0 with rfl | rfl · exact le_rfl
For reversed linear probing, the tail counts agree with linear probing when k < 4.
We unfold hash_probe_tail_prob into counts and assert h_count, which claims that the tail counts of reversed linear probing and linear probing are equal for all k. We split on whether k < 4; when k < 4, equality holds directly by the precomputed lemma unit_first_fixed_offset_mean_probe_maximum_three_r_rev_tail_count.
uses
unit_first_fixed_offset_mean_probe_maximum_three_r_rev_tail_count· dsimp [hash_probe_tail_prob] have h_count : hash_probe_tail_count 3 unit_first_fixed_offset_mean_probe_maximum_three_r_rev t k = hash_probe_tail_count 3 (linear_probe_offset 3) t k := by by_cases hk : k < 4 · exact unit_first_fixed_offset_mean_probe_maximum_three_r_rev_tail_count t ht k hk
For k ≥ 4, both tail counts truncate to their values at k = 3, completing the proof that the counts agree for all k.
When ¬(k < 4), linear arithmetic (omega) gives 3 ≤ k. Applying prime_fixed_offset_linear_probe_stochastic_maximum_three_count_ge to both reversed and standard linear probing, their tail counts at k both equal their counts at 3. Since 3 < 4 (checked by norm_num), unit_first_fixed_offset_mean_probe_maximum_three_r_rev_tail_count equates both counts at 3, thereby establishing h_count.
uses
prime_fixed_offset_linear_probe_stochastic_maximum_three_count_ge,unit_first_fixed_offset_mean_probe_maximum_three_r_rev_tail_count· have hk3 : 3 ≤ k := by omega rw [prime_fixed_offset_linear_probe_stochastic_maximum_three_count_ge 3 _ t k hk3] rw [prime_fixed_offset_linear_probe_stochastic_maximum_three_count_ge 3 (linear_probe_offset 3) t k hk3] exact unit_first_fixed_offset_mean_probe_maximum_three_r_rev_tail_count t ht 3 (by norm_num)
The probe tail probability under reversed linear probing is at most that under linear probing.
Rewriting with the equality of tail counts h_count shows that the probabilities are identical, which immediately satisfies the inequality and completes the proof.
rw [h_count]
Finset.mem_filter- An element belongs to a filtered finset if and only if it belongs to the base finset and satisfies the predicate.
Finset.mem_univ- Every element of a finite type belongs to the universal finset Finset.univ.
true_and- The conjunction True ∧ p is equivalent to p.
lt_of_lt_of_le- In a preorder, if a < b and b ≤ c, then a < c.
unit_first_fixed_offset_mean_probe_maximum_three_r_eq_or_eq- Any injective probe offset sequence on Fin 3 mapping 0 to 0 is either standard linear probing or reversed linear probing.
le_rfl- The less-than-or-equal relation is reflexive: a ≤ a in any preorder.
unit_first_fixed_offset_mean_probe_maximum_three_r_rev_tail_count- For load t < 3 and threshold k < 4 in a 3-slot hash table, the probe tail count under reversed linear probing equals that under linear probing.
prime_fixed_offset_linear_probe_stochastic_maximum_three_count_ge- For a table of size n and any threshold k ≥ n, the probe tail count at k equals the tail count at n.
- The inequality is actually an equality: for a 3-slot hash table, the only non-trivial bijective probe sequence fixing 0 is reversed linear probing, which achieves the exact same probe tail counts and probabilities as forward linear probing.
- The auxiliary lemma prime_fixed_offset_linear_probe_stochastic_maximum_three_count_ge reflects the finite table size: because probe indices are elements j : Fin n, they always satisfy j < n, so requiring all probes j < k to land in occupied slots becomes vacuous beyond k = n, causing the tail count to stabilize at k = n.
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.
lemma prime_fixed_offset_linear_probe_stochastic_maximum_three_count_ge (n : ℕ) [NeZero n] (r : Fin n → ZMod n) (t : ℕ) (k : ℕ) (hk : n ≤ k) : hash_probe_tail_count n r t k = hash_probe_tail_count n r t n := by dsimp [hash_probe_tail_count] congr 1 ext p simp only [Finset.mem_filter, Finset.mem_univ, true_and] constructor · intro h j hj exact h j (lt_of_lt_of_le j.is_lt hk) · intro h j hj exact h j j.is_lt/-- For a 3-slot hash table, every bijective offset sequence with r 0 = 0 has probe-cost tail probabilities bounded by linear probing. -/theorem prime_fixed_offset_linear_probe_stochastic_maximum_three (r : Fin 3 → ZMod 3) (hr_bij : Function.Bijective r) (hr0 : r 0 = 0) (t : ℕ) (ht : t < 3) (k : ℕ) : hash_probe_tail_prob 3 r t k ≤ hash_probe_tail_prob 3 (linear_probe_offset 3) t k := by rcases unit_first_fixed_offset_mean_probe_maximum_three_r_eq_or_eq r hr_bij.injective hr0 with rfl | rfl · exact le_rfl · dsimp [hash_probe_tail_prob] have h_count : hash_probe_tail_count 3 unit_first_fixed_offset_mean_probe_maximum_three_r_rev t k = hash_probe_tail_count 3 (linear_probe_offset 3) t k := by by_cases hk : k < 4 · exact unit_first_fixed_offset_mean_probe_maximum_three_r_rev_tail_count t ht k hk · have hk3 : 3 ≤ k := by omega rw [prime_fixed_offset_linear_probe_stochastic_maximum_three_count_ge 3 _ t k hk3] rw [prime_fixed_offset_linear_probe_stochastic_maximum_three_count_ge 3 (linear_probe_offset 3) t k hk3] exact unit_first_fixed_offset_mean_probe_maximum_three_r_rev_tail_count t ht 3 (by norm_num) rw [h_count]