AFTD Auto-Formalizing Theoretical Domains

prime_fixed_offset_tail_prob_two_two

theoremverified

For any odd prime p and any bijective offset sequence r : Fin p → ZMod p with r 0 = 0, the second tail probability at load t = 2 is exactly 3 / p^2.

Statement

theorem prime_fixed_offset_tail_prob_two_two
    (p : ℕ) [Fact (Nat.Prime p)] (hp : 2 < p)
    (r : Fin p → ZMod p) (hr_bij : Function.Bijective r) (hr0 : r 0 = 0) :
    hash_probe_tail_prob p r 2 2 = 3 / (p : ℝ)^2
Source
step towards prime_fixed_offset_linear_probe_tail_prob_interior_t_two
Verified
04 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 7
  • hash_probe_expected_cost_twoAfter two insertions the expected cost is 1+2/n+(3+[2r₁=0])/n².
  • 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…
  • hash_probe_tail_prob_zero_of_lt_strictFor any table size n with [NeZero n], any bijective offset sequence r, and load t < n, the probe tail probability is 0 whenever k > t.
  • hash_probe_tail_prob_zeroFor 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…
  • hash_probe_tail_prob_oneFor any table size n ≥ 2 with [NeZero n], any bijective offset sequence r with r 0 = 0, and any load t ≤ n, the 1st tail probability…
  • 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…
Used by 1

The proof, explained

The proof computes the second tail probability at load $t = 2$ by equating two expressions for the expected probe cost. First, the general closed-form formula for the expected cost at load 2 simplifies to $1 + 2/p + 3/p^2$ because $p > 2$ is an odd prime, which forces $r(1) + r(1) \neq 0$ by the bijectivity of the offset sequence $r$. Second, the expected cost by definition is the sum of all tail probabilities $\sum_{k=0}^p \mathbb{P}(\text{probes} > k)$, where all terms with $k > 2$ vanish. Substituting the known values $\mathbb{P}(\text{probes} > 0) = 1$ and $\mathbb{P}(\text{probes} > 1) = 2/p$ into this sum and subtracting them from the expected cost directly yields $\mathbb{P}(\text{probes} > 2) = 3/p^2$.

  1. $r(1) + r(1) \neq 0$ in $\mathbb{Z}/p\mathbb{Z}$

    Suppose for contradiction that $r(1) + r(1) = 0$. Since $r(1) + r(1) = 2 \cdot r(1)$ by `two_mul`, this gives $2 \cdot r(1) = 0$. Because $p$ is prime and $p > 2$, $2 \neq 0$ in $\mathbb{Z}/p\mathbb{Z}$ (otherwise $p \mid 2$ by `CharP.cast_eq_zero_iff`, implying $p \le 2$ by `Nat.le_of_dvd`). Since $\mathbb{Z}/p\mathbb{Z}$ has no zero divisors, $2 \cdot r(1) = 0$ implies $r(1) = 0$ via `mul_eq_zero.mp`. But $r$ is bijective and $r(0) = 0$, so injectivity gives $1 = 0$ in $\text{Fin } p$. Applying `congr_arg` to project to natural numbers via `Fin.val_zero` and `Fin.val_one'` gives $1 \pmod p = 0$, but since $1 < p$, `Nat.mod_eq_of_lt` yields $1 \pmod p = 1$, giving $1 = 0$, a contradiction.

    lines 6–24

    uses two_mul, CharP.cast_eq_zero_iff, Nat.le_of_dvd, mul_eq_zero.mp, congr_arg, Fin.val_zero, Fin.val_one', Nat.mod_eq_of_lt

      have hp_ne : r 1 + r 1 ≠ 0 := by
        intro h
        have h_mul : (2 : ZMod p) * r 1 = 0 := by
          calc (2 : ZMod p) * r 1 = r 1 + r 1 := two_mul (r 1)
          _ = 0 := h
        have hp2 : (2 : ZMod p) ≠ 0 := by
          intro h0
          have : (p : ℕ) ∣ 2 := (CharP.cast_eq_zero_iff (ZMod p) p 2).mp h0
          have : p ≤ 2 := Nat.le_of_dvd (by decide) this
          omega
        have hr1 : r 1 = 0 := by
          cases mul_eq_zero.mp h_mul with
          | inl h2 => contradiction
          | inr h1 => exact h1
        have h10 : (1 : Fin p) = 0 := hr_bij.injective (hr1.trans hr0.symm)
        have h' : (1 : Fin p).val = (0 : Fin p).val := congr_arg Fin.val h10
        rw [Fin.val_zero, Fin.val_one'] at h'
        have : 1 % p = 1 := Nat.mod_eq_of_lt (by omega)
        omega
  2. The expected probe cost at load 2 is $1 + 2/p + 3/p^2$

    By `hash_probe_expected_cost_two`, the expected cost at load 2 is $1 + 2/p + (3 + (\text{if } r(1)+r(1)=0 \text{ then } 1 \text{ else } 0))/p^2$. Since $r(1) + r(1) \neq 0$, `if_neg` evaluates the conditional term to 0, and `add_zero` simplifies $3 + 0$ to $3$.

    lines 25–30

    uses hash_probe_expected_cost_two, if_neg, add_zero

      have hec : hash_probe_expected_cost p r 2 =
          1 + 2 / (p : ℝ) + 3 / (p : ℝ)^2 := by
        have h := hash_probe_expected_cost_two p hp r hr_bij hr0
        rw [if_neg hp_ne] at h
        simp only [add_zero] at h
        exact h
  3. The expected probe cost equals the sum of the first three tail probabilities: $\text{tail}(0) + \text{tail}(1) + \text{tail}(2)$

    By definition, the expected probe cost is the sum of the tail probabilities over $k \in \{0, \dots, p\}$. The set $\{0, 1, 2\}$ is contained in $\{0, \dots, p\}$ because $p > 2$ (checked using `Finset.mem_insert`, `Finset.mem_singleton`, and `Finset.mem_range`). For any index $x$ not in $\{0, 1, 2\}$ (rewritten with `not_or`), $x > 2$, so the tail probability at load 2 vanishes by `hash_probe_tail_prob_zero_of_lt_strict`. Hence `Finset.sum_subset` restricts the summation to $\{0, 1, 2\}$, which expands via `Finset.sum_insert` and `Finset.sum_singleton` to $\text{tail}(0) + \text{tail}(1) + \text{tail}(2)$.

    lines 31–47

    uses Finset.mem_insert, Finset.mem_singleton, Finset.mem_range, not_or, hash_probe_tail_prob_zero_of_lt_strict, Finset.sum_subset, Finset.sum_insert, Finset.sum_singleton

      have hsum : hash_probe_expected_cost p r 2 =
          hash_probe_tail_prob p r 2 0 + hash_probe_tail_prob p r 2 1 + hash_probe_tail_prob p r 2 2 := by
        unfold hash_probe_expected_cost
        have hsub : ({0, 1, 2} : Finset ℕ) ⊆ Finset.range (p + 1) := by
          intro x hx
          simp only [Finset.mem_insert, Finset.mem_singleton] at hx
          simp only [Finset.mem_range]
          rcases hx with h | h | h <;> omega
        have hzero : ∀ x ∈ Finset.range (p + 1), x ∉ ({0, 1, 2} : Finset ℕ) →
            hash_probe_tail_prob p r 2 x = 0 := by
          intro x hx hx2
          simp only [Finset.mem_insert, Finset.mem_singleton, not_or] at hx2
          have hx3 : 2 < x := by omega
          exact hash_probe_tail_prob_zero_of_lt_strict p r hr_bij 2 x hp hx3
        rw [← Finset.sum_subset hsub hzero]
        rw [Finset.sum_insert (by simp), Finset.sum_insert (by simp), Finset.sum_singleton]
        ring
  4. The 0-th tail probability at load 2 is 1

    By `hash_probe_tail_prob_zero`, the probability that the probe count exceeds 0 is always 1.

    line 48

    uses hash_probe_tail_prob_zero

      have h0 : hash_probe_tail_prob p r 2 0 = 1 := hash_probe_tail_prob_zero p r 2
  5. The 1st tail probability at load 2 is $2/p$

    Because $2 \le p$, `hash_probe_tail_prob_one` applies at load $t = 2 \le p$, showing that the 1st tail probability equals $t/p = 2/p$.

    lines 49–53

    uses hash_probe_tail_prob_one

      have h1 : hash_probe_tail_prob p r 2 1 = 2 / (p : ℝ) := by
        have hp_ge : 2 ≤ p := by omega
        have ht_le : 2 ≤ p := by omega
        have h := hash_probe_tail_prob_one p hp_ge r hr_bij hr0 2 ht_le
        exact_mod_cast h
  6. The second tail probability at load 2 is $3/p^2$

    Equating the formula for the expected cost ($1 + 2/p + 3/p^2$) with its tail-sum expansion ($\text{tail}(0) + \text{tail}(1) + \text{tail}(2) = 1 + 2/p + \text{tail}(2)$), subtracting $1$ and $2/p$ from both sides by linear arithmetic (`linarith`) isolates $\text{tail}(2) = 3/p^2$.

    line 54

      linarith
two_mul
Multiplication by 2 in a semiring equals adding the element to itself ($2x = x + x$).
CharP.cast_eq_zero_iff
In a ring of characteristic $p$, the natural cast $\uparrow x = 0$ if and only if $p \mid x$.
Nat.le_of_dvd
For positive $n$, if $m \mid n$, then $m \le n$.
mul_eq_zero.mp
In a domain with no zero divisors, $a \cdot b = 0$ implies $a = 0$ or $b = 0$.
congr_arg
Functions preserve equality: if $a = b$, then $f(a) = f(b)$.
Fin.val_zero
The natural number value of $0 \in \text{Fin } n$ is 0.
Fin.val_one'
The natural number value of $1 \in \text{Fin } n$ is $1 \pmod n$.
Nat.mod_eq_of_lt
If $a < b$, then $a \pmod b = a$.
hash_probe_expected_cost_two
For $n > 2$ and a bijective offset sequence $r$ with $r(0) = 0$, the expected probe cost at load $t = 2$ is $1 + 2/n + (3 + (\text{if } r(1)+r(1)=0 \text{ then } 1 \text{ else } 0))/n^2$.
if_neg
An if-then-else evaluates to its 'else' branch when the condition is false.
add_zero
Adding zero to an element leaves it unchanged ($a + 0 = a$).
Finset.mem_insert
An element $x$ is in $\text{insert } a \; s$ if and only if $x = a$ or $x \in s$.
Finset.mem_singleton
An element $x$ is in $\{a\}$ if and only if $x = a$.
Finset.mem_range
A natural number $m$ is in $\text{Finset.range } n$ if and only if $m < n$.
not_or
Negation distributes over disjunction: $\neg(p \lor q) \iff \neg p \land \neg q$.
hash_probe_tail_prob_zero_of_lt_strict
For a bijective offset sequence, the tail probability of requiring strictly more than $k$ probes at load $t < n$ is 0 whenever $t < k$.
Finset.sum_subset
If $s_1 \subseteq s_2$ and the summand is 0 on $s_2 \setminus s_1$, the sum over $s_1$ equals the sum over $s_2$.
Finset.sum_insert
If $a \notin s$, then $\sum_{x \in \text{insert } a \; s} f(x) = f(a) + \sum_{x \in s} f(x)$.
Finset.sum_singleton
The sum of a function over a singleton set $\{a\}$ equals $f(a)$.
hash_probe_tail_prob_zero
The probability of requiring strictly more than 0 probes at any load is 1.
hash_probe_tail_prob_one
For $2 \le n$, load $t \le n$, and a bijective offset sequence with $r(0) = 0$, the probability of requiring strictly more than 1 probe is $t/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

/-- For any odd prime p and any bijective offset sequence r : Fin p → ZMod p with r 0 = 0, the second tail probability at load t = 2 is exactly 3 / p^2. -/theorem prime_fixed_offset_tail_prob_two_two    (p : ℕ) [Fact (Nat.Prime p)] (hp : 2 < p)    (r : Fin p → ZMod p) (hr_bij : Function.Bijective r) (hr0 : r 0 = 0) :    hash_probe_tail_prob p r 2 2 = 3 / (p : ℝ)^2 := by  have hp_ne : r 1 + r 1 ≠ 0 := by    intro h    have h_mul : (2 : ZMod p) * r 1 = 0 := by      calc (2 : ZMod p) * r 1 = r 1 + r 1 := two_mul (r 1)      _ = 0 := h    have hp2 : (2 : ZMod p) ≠ 0 := by      intro h0      have : (p : ℕ) ∣ 2 := (CharP.cast_eq_zero_iff (ZMod p) p 2).mp h0      have : p ≤ 2 := Nat.le_of_dvd (by decide) this      omega    have hr1 : r 1 = 0 := by      cases mul_eq_zero.mp h_mul with      | inl h2 => contradiction      | inr h1 => exact h1    have h10 : (1 : Fin p) = 0 := hr_bij.injective (hr1.trans hr0.symm)    have h' : (1 : Fin p).val = (0 : Fin p).val := congr_arg Fin.val h10    rw [Fin.val_zero, Fin.val_one'] at h'    have : 1 % p = 1 := Nat.mod_eq_of_lt (by omega)    omega  have hec : hash_probe_expected_cost p r 2 =      1 + 2 / (p : ℝ) + 3 / (p : ℝ)^2 := by    have h := hash_probe_expected_cost_two p hp r hr_bij hr0    rw [if_neg hp_ne] at h    simp only [add_zero] at h    exact h  have hsum : hash_probe_expected_cost p r 2 =      hash_probe_tail_prob p r 2 0 + hash_probe_tail_prob p r 2 1 + hash_probe_tail_prob p r 2 2 := by    unfold hash_probe_expected_cost    have hsub : ({0, 1, 2} : Finset ℕ) ⊆ Finset.range (p + 1) := by      intro x hx      simp only [Finset.mem_insert, Finset.mem_singleton] at hx      simp only [Finset.mem_range]      rcases hx with h | h | h <;> omega    have hzero : ∀ x ∈ Finset.range (p + 1), x ∉ ({0, 1, 2} : Finset ℕ) →        hash_probe_tail_prob p r 2 x = 0 := by      intro x hx hx2      simp only [Finset.mem_insert, Finset.mem_singleton, not_or] at hx2      have hx3 : 2 < x := by omega      exact hash_probe_tail_prob_zero_of_lt_strict p r hr_bij 2 x hp hx3    rw [← Finset.sum_subset hsub hzero]    rw [Finset.sum_insert (by simp), Finset.sum_insert (by simp), Finset.sum_singleton]    ring  have h0 : hash_probe_tail_prob p r 2 0 = 1 := hash_probe_tail_prob_zero p r 2  have h1 : hash_probe_tail_prob p r 2 1 = 2 / (p : ℝ) := by    have hp_ge : 2 ≤ p := by omega    have ht_le : 2 ≤ p := by omega    have h := hash_probe_tail_prob_one p hp_ge r hr_bij hr0 2 ht_le    exact_mod_cast h  linarith
See it in the graphDiscuss this resultChallenge it