AFTD Auto-Formalizing Theoretical Domains

hash_probe_tail_prob_zero

theoremverified

For any table size n with [NeZero n], offset sequence r : Fin n → ZMod n, and number of inserted keys t, the 0-th tail probability of probe cost hash_probe_tail_prob n r t 0 is 1.

Statement

theorem hash_probe_tail_prob_zero (n : ℕ) [NeZero n] (r : Fin n → ZMod n) (t : ℕ) :
    hash_probe_tail_prob n r t 0 = 1
Source
step towards unit_first_fixed_offset_mean_probe_maximum
Verified
01 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • 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…
  • 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_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…
Used by 3

The proof, explained

The 0-th tail probability of probe cost is defined as the fraction of configuration pairs in `(Fin t → ZMod n) × ZMod n` whose first 0 probe slots are occupied. Because the index condition `j < 0` is vacuously false for all natural numbers, every configuration pair satisfies this requirement, making the event set the entire universe of configurations. Counting the product space yields `n^t * n = n^(t+1)` outcomes, which matches the denominator and evaluates to 1.

  1. The set of configuration pairs satisfying the 0-th probe condition is the entire universe `Finset.univ`.

    Unfolding `hash_probe_tail_prob` and `hash_probe_tail_count`, the condition for probe cost being at least 0 requires that all probe indices `j` satisfying `(j : ℕ) < 0` correspond to occupied slots. Since no natural number is less than zero (`Nat.not_lt_zero`), this implication is vacuously true for every configuration. Therefore, filtering `Finset.univ` by this condition keeps every element (`Finset.filter_true_of_mem`).

    lines 4–10

    uses Finset.filter_true_of_mem, Nat.not_lt_zero

      unfold hash_probe_tail_prob hash_probe_tail_count
      have h : (Finset.univ.filter (fun p : (Fin t → ZMod n) × ZMod n =>
          ∀ j : Fin n, (j : ℕ) < 0 → p.2 + r j ∈ hash_occupied_slots n r (List.ofFn p.1)))
          = Finset.univ := by
        rw [Finset.filter_true_of_mem]
        intro p _ j hj
        exact absurd hj (Nat.not_lt_zero _)
  2. The cardinality of the event set is `n ^ t * n`.

    Replacing the filtered set with `Finset.univ`, its cardinality is given by `Fintype.card ((Fin t → ZMod n) × ZMod n)` (`Finset.card_univ`). Applying the cardinality formulas for product types (`Fintype.card_prod`) and function spaces (`Fintype.card_fun`), together with the cardinalities `|ZMod n| = n` (`ZMod.card`) and `|Fin t| = t` (`Fintype.card_fin`), the total number of configurations is `n ^ t * n`.

    lines 11–14

    uses Finset.card_univ, Fintype.card_prod, Fintype.card_fun, ZMod.card, Fintype.card_fin

      rw [h, Finset.card_univ]
      have hcard : Fintype.card ((Fin t → ZMod n) × ZMod n) = n ^ t * n := by
        rw [Fintype.card_prod, Fintype.card_fun, ZMod.card, Fintype.card_fin]
      rw [hcard]
  3. The quotient simplifies to 1.

    Since `n ≠ 0` (`NeZero.ne`), the real number `n` is nonzero, implying `(n : ℝ) ^ t * n ≠ 0` by `pow_ne_zero` and `mul_ne_zero`. Rewriting the denominator `n ^ (t + 1)` as `n ^ t * n` using `pow_succ`, the numerator and denominator are identical and nonzero, so their division evaluates to 1 (`div_self`).

    lines 15–18

    uses NeZero.ne, pow_succ, div_self, mul_ne_zero, pow_ne_zero

      have hn : (n : ℝ) ≠ 0 := by exact_mod_cast NeZero.ne n
      have hpow : (n : ℝ) ^ (t + 1) = (n : ℝ) ^ t * n := by rw [pow_succ]
      push_cast
      rw [hpow, div_self (mul_ne_zero (pow_ne_zero _ hn) hn)]
Finset.filter_true_of_mem
Filtering a finite set by a predicate that holds for all of its elements yields the original finite set.
Nat.not_lt_zero
No natural number is strictly less than zero.
Finset.card_univ
The cardinality of the universal finset `Finset.univ` on a finite type is the cardinality of the type itself.
Fintype.card_prod
The cardinality of a Cartesian product of two finite types is the product of their cardinalities.
Fintype.card_fun
The cardinality of the function type `α → β` between finite types is the cardinality of `β` raised to the power of the cardinality of `α`.
ZMod.card
The cardinality of `ZMod n` is `n`.
Fintype.card_fin
The cardinality of `Fin n` is `n`.
NeZero.ne
An element with an instance of `NeZero` is nonzero.
pow_succ
In any monoid, a power satisfies `a ^ (n + 1) = a ^ n * a`.
div_self
Any nonzero element divided by itself equals 1.
mul_ne_zero
The product of two nonzero elements in a structure with no zero divisors is nonzero.
pow_ne_zero
Any natural power of a nonzero element in a structure without zero divisors is nonzero.

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

/-- For any table size n, offset sequence r, and load t, the 0-th tail probability of probe cost is 1. -/theorem hash_probe_tail_prob_zero (n : ℕ) [NeZero n] (r : Fin n → ZMod n) (t : ℕ) :    hash_probe_tail_prob n r t 0 = 1 := by  unfold hash_probe_tail_prob hash_probe_tail_count  have h : (Finset.univ.filter (fun p : (Fin t → ZMod n) × ZMod n =>      ∀ j : Fin n, (j : ℕ) < 0 → p.2 + r j ∈ hash_occupied_slots n r (List.ofFn p.1)))      = Finset.univ := by    rw [Finset.filter_true_of_mem]    intro p _ j hj    exact absurd hj (Nat.not_lt_zero _)  rw [h, Finset.card_univ]  have hcard : Fintype.card ((Fin t → ZMod n) × ZMod n) = n ^ t * n := by    rw [Fintype.card_prod, Fintype.card_fun, ZMod.card, Fintype.card_fin]  rw [hcard]  have hn : (n : ℝ) ≠ 0 := by exact_mod_cast NeZero.ne n  have hpow : (n : ℝ) ^ (t + 1) = (n : ℝ) ^ t * n := by rw [pow_succ]  push_cast  rw [hpow, div_self (mul_ne_zero (pow_ne_zero _ hn) hn)]
See it in the graphDiscuss this resultChallenge it