not_hash_probe_tail_prob_zero_of_lt
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.
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.
uses
Subsingleton.elimintro 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⟩
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$.
uses
le_rflhave h1 := h 1 (fun _ => 0) hbij 1 2 le_rfl (by norm_num)
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.
uses
hash_probe_tail_count,Finset.filter_true_of_memhave 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 _
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.
uses
hash_occupied_slots_card,Finset.card_pos.mp,Subsingleton.elimhave 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
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$.
uses
Finset.card_univrw [hfilter, Finset.card_univ] simp
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.
uses
hash_probe_tail_probrw [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}$.
- The counterexample succeeds because when $k > n$, the condition $j < k$ for $j : \mathrm{Fin}\ n$ holds for all $j < n$. When the number of inserted elements equals the table size ($t = n$), all $n$ slots are occupied, so every probe position is occupied and the tail probability is $1 \ne 0$. The original pigeonhole argument would require the additional hypothesis $k \le 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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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