AFTD Auto-Formalizing Theoretical Domains

unit_first_fixed_offset_mean_probe_maximum_three

theoremverified

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

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.

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

    lines 5–8

      fin_cases x
      · left; rfl
      · right; left; rfl
      · right; right; rfl
  2. 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.

    lines 12–16

      ext ⟨i, hi⟩
      interval_cases i
      · exact h0
      · exact h1
      · exact h2
  3. 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.

    lines 21–29

      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
  4. 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).

    lines 30–43

    uses unit_first_fixed_offset_mean_probe_maximum_three_zmod3_cases, False.elim, unit_first_fixed_offset_mean_probe_maximum_three_fun_ext

      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)
  5. 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.

    line 49

      interval_cases t <;> interval_cases k <;> decide
  6. For 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.

    lines 55–59

    uses Finset.sum_congr, Finset.mem_range, unit_first_fixed_offset_mean_probe_maximum_three_r_rev_tail_count

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

    lines 67–69

    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_cost

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

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

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