AFTD Auto-Formalizing Theoretical Domains

not_hash_probe_tail_prob_zero_of_lt

theoremverifiedoriginal

The statement hash_probe_tail_prob_zero_of_lt is false: Take n = 1, r = (fun _ => 0 : Fin 1 → ZMod 1), t = 1, k = 2. Hypotheses hold: htn : 1 ≤ 1 and hkt : 1 < 2. But hash_probe_tail_count 1 r 1 2 = 1 (kernel-checked by unfolding the definition), so hash_probe_tail_prob 1 r 1 2 = 1 / 1^2 = 1 ≠ 0. Reason: with t = n the occupied set hash_occupied_slots has cardinality n = |ZMod n|, hence is all of ZMod n, so the condition "p.2 + r j is occupied for all j < k" holds for every pair p whenever k > n; the count is n^(n+1) ≠ 0. The claimed pigeonhole (at most t occupied slots, so fewer than k probes) is only valid when additionally k ≤ n, since the k probe positions p.2 + r 0, …, p.2 + r(k-1) are distinct only if k ≤ n.

Statement

theorem not_hash_probe_tail_prob_zero_of_lt : ¬ (∀ (n : ℕ) [NeZero n]
    (r : Fin n → ZMod n) (hr_bij : Function.Bijective r)
    (t k : ℕ) (htn : t ≤ n) (hkt : t < k), hash_probe_tail_prob n r t k = 0)
Related work
refutes `hash_probe_tail_prob_zero_of_lt`
Verified
02 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • 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_occupied_slots_cardFor any table size n with [NeZero n], any bijective offset sequence r : Fin n → ZMod n, and any list of keys A with length at most n, the…
  • 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…

The proof, explained

The theorem is refuted by providing an explicit counterexample: $n = 1$, $t = 1$, $k = 2$, and the trivial probe function $r(0) = 0$. The preconditions $t \le n$ and $t < k$ hold, and $r$ is bijective because both $\mathrm{Fin}\ 1$ and $\mathbb{Z}/1\mathbb{Z}$ are singletons. However, inserting $t = 1$ item into a table of size $1$ fills all available slots, so every probe position is occupied; this forces the tail count to be $1$ and the tail probability to be $1 / 1^2 = 1 \ne 0$, contradicting the claim.

  1. Assuming the universal statement for contradiction, the unique function from Fin 1 to ZMod 1 is bijective.

    We assume the universally quantified statement for contradiction. We then define our candidate probe sequence $r : \mathrm{Fin}\ 1 \to \mathbb{Z}/1\mathbb{Z}$ by $r(0) = 0$. Because both domain $\mathrm{Fin}\ 1$ and codomain $\mathbb{Z}/1\mathbb{Z}$ have cardinality 1 (they are subsingletons), injectivity and surjectivity hold immediately by Subsingleton.elim.

    lines 4–8

    uses Subsingleton.elim

      intro h
      have hbij : Function.Bijective (fun _ : Fin 1 => (0 : ZMod 1)) := by
        constructor
        · intro a b _; exact Subsingleton.elim a b
        · intro b; exact ⟨0, Subsingleton.elim _ b⟩
  2. The universal assumption implies that the tail probability for n = 1, t = 1, and k = 2 is zero.

    We specialize the assumed universal claim to the table size $n = 1$, probe function $r$, $t = 1$, and $k = 2$. Both preconditions $t \le n$ (as $1 \le 1$ by reflexivity) and $t < k$ (as $1 < 2$ by numerical calculation) are satisfied, yielding $\mathrm{hash\_probe\_tail\_prob}\ 1\ r\ 1\ 2 = 0$.

    line 9

    uses le_rfl

      have h1 := h 1 (fun _ => 0) hbij 1 2 le_rfl (by norm_num)
  3. To show hash_probe_tail_count 1 r 1 2 = 1, it suffices to show that every candidate pair satisfies the probe condition.

    We unfold the definition of hash_probe_tail_count. The count is the size of the subset of pairs $p = (A, p.2) \in (\mathrm{Fin}\ 1 \to \mathbb{Z}/1\mathbb{Z}) \times \mathbb{Z}/1\mathbb{Z}$ such that the probe $p.2 + r(j)$ is occupied for all $j : \mathrm{Fin}\ 1$ with $j < 2$. By Finset.filter_true_of_mem, if this condition holds for every pair, the filtered set is equal to the full universe Finset.univ.

    lines 10–15

    uses hash_probe_tail_count, Finset.filter_true_of_mem

      have hc : hash_probe_tail_count 1 (fun _ => 0) 1 2 = 1 := by
        simp only [hash_probe_tail_count]
        have hfilter : (Finset.univ.filter (fun p : (Fin 1 → ZMod 1) × ZMod 1 =>
            ∀ (j : Fin 1), (j:ℕ) < 2 → p.2 + (fun _ => 0) j ∈ hash_occupied_slots 1 (fun _ => 0) (List.ofFn p.1))) = Finset.univ := by
          apply Finset.filter_true_of_mem
          intro p _ j _
  4. For every pair p and probe index j, the probe position p.2 + r(j) lies in the occupied slots.

    The inserted sequence has length 1, so by hash_occupied_slots_card the set of occupied slots has cardinality 1. Because this cardinality is positive, there exists at least one element $x$ in the occupied slots by Finset.card_pos.mp. Since the ambient space $\mathbb{Z}/1\mathbb{Z}$ has only one element, $p.2 + r(j) = x$ by Subsingleton.elim, and thus $p.2 + r(j)$ is occupied.

    lines 16–21

    uses hash_occupied_slots_card, Finset.card_pos.mp, Subsingleton.elim

          have hc' : (hash_occupied_slots 1 (fun _ => 0) (List.ofFn p.1)).card = 1 := by
            rw [hash_occupied_slots_card (n := 1) (r := fun _ => 0) (hr := hbij) (A := List.ofFn p.1) (hA := by simp)]
            simp
          obtain ⟨x, hx⟩ := Finset.card_pos.mp (by omega : 0 < (hash_occupied_slots 1 (fun _ => 0) (List.ofFn p.1)).card)
          rw [show p.2 + (fun _ => (0:ZMod 1)) j = x from Subsingleton.elim _ _]
          exact hx
  5. The tail probe count hash_probe_tail_count 1 r 1 2 equals 1.

    Since the filtered set is the entire universal set, its cardinality is the size of the product type $(\mathrm{Fin}\ 1 \to \mathbb{Z}/1\mathbb{Z}) \times \mathbb{Z}/1\mathbb{Z}$ by Finset.card_univ. Because both types are singletons, the product has size $1^1 \times 1 = 1$.

    lines 22–23

    uses Finset.card_univ

        rw [hfilter, Finset.card_univ]
        simp
  6. The derived tail probability equality 1 / 1^2 = 0 is a numerical contradiction.

    Rewriting the tail probability in our instantiated hypothesis using the definition of hash_probe_tail_prob and substituting the computed count $1$ gives $1 / 1^2 = 0$. Normalizing arithmetic reveals that $1 = 0$, producing False and concluding the proof.

    lines 24–25

    uses hash_probe_tail_prob

      rw [hash_probe_tail_prob, hc] at h1
      norm_num at h1
Subsingleton.elim
In any type with at most one element, any two elements are equal.
le_rfl
The preorder relation ≤ is reflexive ($a \le a$ for any $a$).
hash_probe_tail_count
The number of pairs consisting of an insertion sequence of length $t$ and an initial slot whose probe positions are all occupied for indices $j < k$.
Finset.filter_true_of_mem
Filtering a finite set by a predicate that holds for all members of the set leaves the set unchanged.
hash_occupied_slots_card
When inserting a list of keys of length at most $n$ with a bijective probe sequence, the number of occupied slots equals the length of the list.
Finset.card_pos.mp
A finite set with strictly positive cardinality is nonempty, so it contains at least one element.
Finset.card_univ
The cardinality of the universal finset of a finite type equals the cardinality of the type itself.
hash_probe_tail_prob
The tail probe probability, defined as $\mathrm{hash\_probe\_tail\_count}(n, r, t, k) / n^{t+1}$.

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

theorem not_hash_probe_tail_prob_zero_of_lt : ¬ (∀ (n : ℕ) [NeZero n]    (r : Fin n → ZMod n) (hr_bij : Function.Bijective r)    (t k : ℕ) (htn : t ≤ n) (hkt : t < k), hash_probe_tail_prob n r t k = 0) := by  intro h  have hbij : Function.Bijective (fun _ : Fin 1 => (0 : ZMod 1)) := by    constructor    · intro a b _; exact Subsingleton.elim a b    · intro b; exact ⟨0, Subsingleton.elim _ b⟩  have h1 := h 1 (fun _ => 0) hbij 1 2 le_rfl (by norm_num)  have hc : hash_probe_tail_count 1 (fun _ => 0) 1 2 = 1 := by    simp only [hash_probe_tail_count]    have hfilter : (Finset.univ.filter (fun p : (Fin 1 → ZMod 1) × ZMod 1 =>        ∀ (j : Fin 1), (j:ℕ) < 2 → p.2 + (fun _ => 0) j ∈ hash_occupied_slots 1 (fun _ => 0) (List.ofFn p.1))) = Finset.univ := by      apply Finset.filter_true_of_mem      intro p _ j _      have hc' : (hash_occupied_slots 1 (fun _ => 0) (List.ofFn p.1)).card = 1 := by        rw [hash_occupied_slots_card (n := 1) (r := fun _ => 0) (hr := hbij) (A := List.ofFn p.1) (hA := by simp)]        simp      obtain ⟨x, hx⟩ := Finset.card_pos.mp (by omega : 0 < (hash_occupied_slots 1 (fun _ => 0) (List.ofFn p.1)).card)      rw [show p.2 + (fun _ => (0:ZMod 1)) j = x from Subsingleton.elim _ _]      exact hx    rw [hfilter, Finset.card_univ]    simp  rw [hash_probe_tail_prob, hc] at h1  norm_num at h1
See it in the graphDiscuss this resultChallenge it