unit_first_fixed_offset_mean_probe_maximum_three
For 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, the expected probe cost hash_probe_expected_cost 3 r t is at most hash_probe_expected_cost 3 (linear_probe_offset 3) t.
Statement
theorem unit_first_fixed_offset_mean_probe_maximum_three
(r : Fin 3 → ZMod 3) (hr_bij : Function.Bijective r)
(hr0 : r 0 = 0) (hr1 : IsUnit (r 1))
(t : ℕ) (ht : t < 3) :
hash_probe_expected_cost 3 r t ≤ hash_probe_expected_cost 3 (linear_probe_offset 3) t- Source
- scout/2610-31363-a-sharp-analysis-of-fixed-offset-hash-tables.md
- Verified
- 01 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- hash_probe_expected_costFor a table size n with [NeZero n], an offset sequence r : Fin n → ZMod n, and a number of inserted keys t : ℕ, hash_probe_expected_cost n…
- 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…
- 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…
- 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…
- Used by 1
- prime_fixed_offset_linear_probe_stochastic_maximum_threeFor 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 ≥…
Read back from the Lean
For any function $r : \text{Fin } 3 \to \mathbb{Z}/3\mathbb{Z}$, if $r$ is bijective, $r(0) = 0$, and $r(1)$ is a unit in $\mathbb{Z}/3\mathbb{Z}$, then for any natural number $t < 3$, the expected hash probe cost with offset sequence $r$ after inserting $t$ elements, hash_probe_expected_cost 3 r t, is less than or equal to the expected probe cost with linear probing offsets linear_probe_offset 3 (which is $j \mapsto j \pmod 3$) after inserting $t$ elements.
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
On a 3-slot hash table, any injective probe sequence starting at 0 must be either standard linear probing [0, 1, 2] or its reversal [0, 2, 1]. The proof reduces the inequality to these two sequences. By exhaustive computation across all loads t < 3 and cutoffs k < 4, the reversed sequence is shown to have identical probe tail counts—and therefore identical expected probe cost—to linear probing, so the inequality holds (in fact with equality) in both cases.
Every element of ZMod 3 is 0, 1, or 2.
We exhaust all elements of the finite type ZMod 3 using `fin_cases`. In each of the three cases (x = 0, x = 1, and x = 2), the disjunction is satisfied by definition.
fin_cases x · left; rfl · right; left; rfl · right; right; rfl
Two functions from Fin 3 to ZMod 3 that agree at 0, 1, and 2 are identical.
By function extensionality, it suffices to show that f(i) = g(i) for all i : Fin 3. Exhausting the possible values of the index i < 3 leaves the cases i = 0, 1, and 2, which match the three equality hypotheses h0, h1, and h2.
ext ⟨i, hi⟩ interval_cases i · exact h0 · exact h1 · exact h2
For any injective probe sequence r : Fin 3 → ZMod 3 with r 0 = 0, the values r 1 and r 2 are nonzero and distinct from each other.
If r 1 = 0 = r 0, injectivity forces 1 = 0 in Fin 3, which is absurd. Similarly, r 2 = 0 would force 2 = 0, and r 2 = r 1 would force 2 = 1. Each contradiction is decided by computation on Fin 3.
have h1_ne_0 : r 1 ≠ 0 := fun h => by have : (1 : Fin 3) = 0 := hr_inj (h.trans hr0.symm) revert this; decide have h2_ne_0 : r 2 ≠ 0 := fun h => by have : (2 : Fin 3) = 0 := hr_inj (h.trans hr0.symm) revert this; decide have h2_ne_1 : r 2 ≠ r 1 := fun h => by have : (2 : Fin 3) = 1 := hr_inj h revert this; decide
Every injective probe sequence r fixing 0 is either linear probing [0, 1, 2] or its reversal [0, 2, 1].
Case analysis on the possible values of r 1 and r 2 in ZMod 3 produces 9 branches. The cases where r 1 = 0, r 2 = 0, or r 2 = r 1 are ruled out as contradictions by the injectivity facts just proved. The only surviving cases are r 1 = 1, r 2 = 2 (which equals linear probing by function extensionality) and r 1 = 2, r 2 = 1 (which equals the reversed sequence r_rev).
uses
unit_first_fixed_offset_mean_probe_maximum_three_zmod3_cases,False.elim,unit_first_fixed_offset_mean_probe_maximum_three_fun_extrcases unit_first_fixed_offset_mean_probe_maximum_three_zmod3_cases (r 1) with hr1 | hr1 | hr1 · exact False.elim (h1_ne_0 hr1) · rcases unit_first_fixed_offset_mean_probe_maximum_three_zmod3_cases (r 2) with hr2 | hr2 | hr2 · exact False.elim (h2_ne_0 hr2) · rw [hr1] at h2_ne_1 exact False.elim (h2_ne_1 hr2) · left exact unit_first_fixed_offset_mean_probe_maximum_three_fun_ext hr0 hr1 hr2 · rcases unit_first_fixed_offset_mean_probe_maximum_three_zmod3_cases (r 2) with hr2 | hr2 | hr2 · exact False.elim (h2_ne_0 hr2) · right exact unit_first_fixed_offset_mean_probe_maximum_three_fun_ext hr0 hr1 hr2 · rw [hr1] at h2_ne_1 exact False.elim (h2_ne_1 hr2)
For all loads t < 3 and thresholds k < 4, the tail count under the reversed probe sequence equals that under linear probing. automation
Exhaustive case splitting on t ∈ {0, 1, 2} and k ∈ {0, 1, 2, 3} produces 12 concrete goals, each closed by computational evaluation (`decide`) of the hash table insertion counts.
interval_cases t <;> interval_cases k <;> decideFor every load t < 3, the expected probe cost under the reversed sequence equals that under linear probing.
Unfolding expected cost and tail probability expresses both sides as sums of tail counts divided by 3^(t+1) over k ∈ {0, 1, 2, 3}. By sum congruence, since each index k satisfies k < 4, the terms are equal by the equality of tail counts established in the previous lemma.
uses
Finset.sum_congr,Finset.mem_range,unit_first_fixed_offset_mean_probe_maximum_three_r_rev_tail_countunfold hash_probe_expected_cost hash_probe_tail_prob apply Finset.sum_congr rfl intro k hk rw [Finset.mem_range] at hk rw [unit_first_fixed_offset_mean_probe_maximum_three_r_rev_tail_count t ht k hk]
For every load t < 3, the expected probe cost under r is at most that under linear probing.
By the classification lemma, r is either linear probing or the reversed sequence r_rev. If r is linear probing, the inequality holds reflexively. If r is r_rev, rewriting with the equality of their expected costs closes the goal.
uses
unit_first_fixed_offset_mean_probe_maximum_three_r_eq_or_eq,le_rfl,unit_first_fixed_offset_mean_probe_maximum_three_r_rev_expected_costrcases unit_first_fixed_offset_mean_probe_maximum_three_r_eq_or_eq r hr_bij.injective hr0 with rfl | rfl · exact le_rfl · rw [unit_first_fixed_offset_mean_probe_maximum_three_r_rev_expected_cost t ht]
False.elim- From a contradiction (a proof of False), any proposition follows.
Finset.mem_range- A natural number m belongs to the range of n if and only if m < n.
Finset.sum_congr- Two finite sums are equal if their index sets are equal and their summands agree on every index in the set.
le_rfl- The preorder relation ≤ is reflexive (a ≤ a).
unit_first_fixed_offset_mean_probe_maximum_three_fun_ext- Two functions from Fin 3 to ZMod 3 are equal if they agree at inputs 0, 1, and 2.
unit_first_fixed_offset_mean_probe_maximum_three_r_eq_or_eq- Any injective probe sequence from Fin 3 to ZMod 3 starting at 0 must be either linear probing [0, 1, 2] or the reversed sequence [0, 2, 1].
unit_first_fixed_offset_mean_probe_maximum_three_r_rev_expected_cost- For any load t < 3 on a 3-slot table, the expected probe cost under the reversed sequence r_rev equals that under linear probing.
unit_first_fixed_offset_mean_probe_maximum_three_r_rev_tail_count- For any load t < 3 and cutoff k < 4 on a 3-slot table, the tail counts for r_rev and linear probing are equal.
unit_first_fixed_offset_mean_probe_maximum_three_zmod3_cases- Every element of ZMod 3 is equal to 0, 1, or 2.
- The theorem assumes `hr1 : IsUnit (r 1)`, but this hypothesis is unused in the proof because any injective function from `Fin 3` to `ZMod 3` fixing 0 automatically maps 1 to either 1 or 2, both of which are units in `ZMod 3`.
- Lemma `unit_first_fixed_offset_mean_probe_maximum_three_r_rev_tail_count` is verified entirely by automation (`decide`), which computes and compares hash table insertion tail counts across all 3 × 4 = 12 combinations of load `t` and tail cutoff `k`.
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.
def unit_first_fixed_offset_mean_probe_maximum_three_r_rev : Fin 3 → ZMod 3 := ![0, 2, 1]lemma unit_first_fixed_offset_mean_probe_maximum_three_zmod3_cases (x : ZMod 3) : x = 0 ∨ x = 1 ∨ x = 2 := by fin_cases x · left; rfl · right; left; rfl · right; right; rfllemma unit_first_fixed_offset_mean_probe_maximum_three_fun_ext {f g : Fin 3 → ZMod 3} (h0 : f 0 = g 0) (h1 : f 1 = g 1) (h2 : f 2 = g 2) : f = g := by ext ⟨i, hi⟩ interval_cases i · exact h0 · exact h1 · exact h2lemma unit_first_fixed_offset_mean_probe_maximum_three_r_eq_or_eq (r : Fin 3 → ZMod 3) (hr_inj : Function.Injective r) (hr0 : r 0 = 0) : r = linear_probe_offset 3 ∨ r = unit_first_fixed_offset_mean_probe_maximum_three_r_rev := by have h1_ne_0 : r 1 ≠ 0 := fun h => by have : (1 : Fin 3) = 0 := hr_inj (h.trans hr0.symm) revert this; decide have h2_ne_0 : r 2 ≠ 0 := fun h => by have : (2 : Fin 3) = 0 := hr_inj (h.trans hr0.symm) revert this; decide have h2_ne_1 : r 2 ≠ r 1 := fun h => by have : (2 : Fin 3) = 1 := hr_inj h revert this; decide rcases unit_first_fixed_offset_mean_probe_maximum_three_zmod3_cases (r 1) with hr1 | hr1 | hr1 · exact False.elim (h1_ne_0 hr1) · rcases unit_first_fixed_offset_mean_probe_maximum_three_zmod3_cases (r 2) with hr2 | hr2 | hr2 · exact False.elim (h2_ne_0 hr2) · rw [hr1] at h2_ne_1 exact False.elim (h2_ne_1 hr2) · left exact unit_first_fixed_offset_mean_probe_maximum_three_fun_ext hr0 hr1 hr2 · rcases unit_first_fixed_offset_mean_probe_maximum_three_zmod3_cases (r 2) with hr2 | hr2 | hr2 · exact False.elim (h2_ne_0 hr2) · right exact unit_first_fixed_offset_mean_probe_maximum_three_fun_ext hr0 hr1 hr2 · rw [hr1] at h2_ne_1 exact False.elim (h2_ne_1 hr2)lemma unit_first_fixed_offset_mean_probe_maximum_three_r_rev_tail_count (t : ℕ) (ht : t < 3) (k : ℕ) (hk : k < 4) : 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 interval_cases t <;> interval_cases k <;> decidelemma unit_first_fixed_offset_mean_probe_maximum_three_r_rev_expected_cost (t : ℕ) (ht : t < 3) : hash_probe_expected_cost 3 unit_first_fixed_offset_mean_probe_maximum_three_r_rev t = hash_probe_expected_cost 3 (linear_probe_offset 3) t := by unfold hash_probe_expected_cost hash_probe_tail_prob apply Finset.sum_congr rfl intro k hk rw [Finset.mem_range] at hk rw [unit_first_fixed_offset_mean_probe_maximum_three_r_rev_tail_count t ht k hk]/-- OP-805 holds for all loads t < 3 on a table of size 3. -/theorem unit_first_fixed_offset_mean_probe_maximum_three (r : Fin 3 → ZMod 3) (hr_bij : Function.Bijective r) (hr0 : r 0 = 0) (hr1 : IsUnit (r 1)) (t : ℕ) (ht : t < 3) : hash_probe_expected_cost 3 r t ≤ hash_probe_expected_cost 3 (linear_probe_offset 3) t := 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 · rw [unit_first_fixed_offset_mean_probe_maximum_three_r_rev_expected_cost t ht]