AFTD Auto-Formalizing Theoretical Domains

prime_fixed_offset_linear_probe_stochastic_maximum_three

theoremverifiedformalization

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.

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

    lines 4–8

    uses Finset.mem_filter, Finset.mem_univ, true_and

      dsimp [hash_probe_tail_count]
      congr 1
      ext p
      simp only [Finset.mem_filter, Finset.mem_univ, true_and]
      constructor
  2. 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.

    lines 9–12

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

    lines 19–20

    uses unit_first_fixed_offset_mean_probe_maximum_three_r_eq_or_eq, le_rfl

      rcases unit_first_fixed_offset_mean_probe_maximum_three_r_eq_or_eq r hr_bij.injective hr0 with rfl | rfl
      · exact le_rfl
  4. 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.

    lines 21–25

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

    lines 26–29

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

    line 30

        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.

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

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