hash_probe_tail_count_zero_of_lt_strict
For any table size n with [NeZero n], any bijective offset sequence r, and load t < n, the probe tail count is 0 whenever k > t.
Statement
theorem hash_probe_tail_count_zero_of_lt_strict
(n : ℕ) [NeZero n] (r : Fin n → ZMod n) (hr : Function.Bijective r)
(t k : ℕ) (ht : t < n) (hkt : t < k) :
hash_probe_tail_count n r t k = 0- Source
- step towards prime_fixed_offset_linear_probe_stochastic_maximum
- Verified
- 02 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- 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_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_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 1
- 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.
The proof, explained
The theorem shows that when a hash table contains t < n elements, it is impossible for the first k probe positions to all be occupied if k > t. The proof proceeds by contradiction: inserting t keys into an empty table occupies exactly t slots when the offset sequence r is bijective. If k > t, the first t + 1 probe positions are distinct by injectivity and would all have to be occupied, requiring at least t + 1 occupied slots, which contradicts the table having only t occupied slots.
It suffices to show that no table configuration can have all its first k probe locations occupied.
Unfolding the definition of `hash_probe_tail_count`, the goal is to show that a filtered finite set has cardinality 0. By `Finset.card_eq_zero` and `Finset.filter_eq_empty_iff`, this is equivalent to showing that no pair `p` (consisting of `t` inserted keys and a search key) satisfies the tail condition `hp` that all probe slots for `j < k` are occupied. We assume such a pair `p` exists for contradiction.
uses
Finset.card_eq_zero,Finset.filter_eq_empty_iffdsimp [hash_probe_tail_count] rw [Finset.card_eq_zero] rw [Finset.filter_eq_empty_iff] intro p _ hp
The number of occupied slots in the hash table after inserting the t keys is exactly t.
The list of inserted keys has length `t`, which is at most `n` since `t < n` (verified by `List.length_ofFn` and linear arithmetic). Applying `hash_occupied_slots_card` with the bijectivity of `r` establishes that the set of occupied slots has cardinality `t`.
uses
List.length_ofFn,hash_occupied_slots_cardhave hS_card : (hash_occupied_slots n r (List.ofFn p.1)).card = t := by have hlen : (List.ofFn p.1).length ≤ n := by rw [List.length_ofFn] omega have h := hash_occupied_slots_card n r hr (List.ofFn p.1) hlen rw [List.length_ofFn] at h exact h
The probe sequence f(j) = p.2 + r(j) restricted to j ∈ Fin (t + 1) is injective.
For any `a, b : Fin (t + 1)`, equality `f(a) = f(b)` means `p.2 + r(a) = p.2 + r(b)`. Cancelling the search key `p.2` on the left using `add_left_cancel` gives `r(a) = r(b)`. Since `r` is bijective, it is injective, so `a = b` as indices in `Fin n`, and thus `a = b` in `Fin (t + 1)` by `Fin.mk.inj`.
uses
add_left_cancel,Fin.mk.injlet f : Fin (t + 1) → ZMod n := fun j => p.2 + r ⟨j.val, by omega⟩ have hf_inj : Function.Injective f := by intro a b hab dsimp [f] at hab have h1 : r ⟨a.val, by omega⟩ = r ⟨b.val, by omega⟩ := add_left_cancel hab have h2 : (⟨a.val, by omega⟩ : Fin n) = ⟨b.val, by omega⟩ := hr.1 h1 ext exact Fin.mk.inj h2
Every probe slot f(j) for j ∈ Fin (t + 1) is occupied.
Any index `j : Fin (t + 1)` satisfies `j.val < t + 1 ≤ k` because `t < k`. By the hypothesis `hp`, all probe locations with index less than `k` must be occupied, so `f(j)` is in the set of occupied slots.
have hf_sub : ∀ j : Fin (t + 1), f j ∈ hash_occupied_slots n r (List.ofFn p.1) := by intro j dsimp [f] have hj : (⟨j.val, by omega⟩ : Fin n).val < k := by have := j.isLt dsimp omega exact hp ⟨j.val, by omega⟩ hj
The image of f is a subset of the occupied slots.
By definition of the image (`Finset.mem_image`), every element of `Finset.image f Finset.univ` has the form `f(j)` for some `j : Fin (t + 1)`, and each such element was shown to be an occupied slot.
uses
Finset.mem_imagehave h_image : Finset.image f Finset.univ ⊆ hash_occupied_slots n r (List.ofFn p.1) := by intro x hx rw [Finset.mem_image] at hx rcases hx with ⟨j, _, rfl⟩ exact hf_sub j
The cardinality inequality leads to a contradiction.
By `Finset.card_le_card`, the image of `f` has cardinality at most the number of occupied slots. Since `f` is injective, `Finset.card_image_of_injective` and `Finset.card_fin` show that the image has cardinality `t + 1`. Since the occupied slots set has cardinality `t`, this implies `t + 1 ≤ t`, an impossibility closed by linear arithmetic (`omega`).
uses
Finset.card_le_card,Finset.card_image_of_injective,Finset.card_finhave h_card_le := Finset.card_le_card h_image rw [Finset.card_image_of_injective Finset.univ hf_inj] at h_card_le rw [Finset.card_fin] at h_card_le rw [hS_card] at h_card_le omega
Finset.card_eq_zero- A finite set has cardinality zero if and only if it is empty.
Finset.filter_eq_empty_iff- Filtering a finite set by a predicate produces the empty set if and only if no element satisfies the predicate.
List.length_ofFn- The length of a list created from a function on `Fin n` is `n`.
hash_occupied_slots_card- For a bijective offset sequence and any list of at most `n` keys, the number of occupied slots equals the length of the list.
add_left_cancel- In an additive group or cancellative structure, `a + b = a + c` implies `b = c`.
Fin.mk.inj- Two elements of `Fin n` are equal if and only if their underlying natural values are equal.
Finset.mem_image- An element belongs to the image of a set under `f` if and only if it is the image of some element in that set.
Finset.card_le_card- A subset of a finite set has cardinality less than or equal to the superset.
Finset.card_image_of_injective- The image of a finite set under an injective function has the same cardinality as the domain set.
Finset.card_fin- The cardinality of `Fin n` as a finite set is `n`.
- Inline proofs that indices lie within bounds (e.g., `j.val < n`) are discharged silently by `omega` without paper counterparts.
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.
/-- For any table size n with [NeZero n], any bijective offset sequence r, and load t < n, the probe tail count is 0 whenever k exceeds t. -/theorem hash_probe_tail_count_zero_of_lt_strict (n : ℕ) [NeZero n] (r : Fin n → ZMod n) (hr : Function.Bijective r) (t k : ℕ) (ht : t < n) (hkt : t < k) : hash_probe_tail_count n r t k = 0 := by dsimp [hash_probe_tail_count] rw [Finset.card_eq_zero] rw [Finset.filter_eq_empty_iff] intro p _ hp have hS_card : (hash_occupied_slots n r (List.ofFn p.1)).card = t := by have hlen : (List.ofFn p.1).length ≤ n := by rw [List.length_ofFn] omega have h := hash_occupied_slots_card n r hr (List.ofFn p.1) hlen rw [List.length_ofFn] at h exact h let f : Fin (t + 1) → ZMod n := fun j => p.2 + r ⟨j.val, by omega⟩ have hf_inj : Function.Injective f := by intro a b hab dsimp [f] at hab have h1 : r ⟨a.val, by omega⟩ = r ⟨b.val, by omega⟩ := add_left_cancel hab have h2 : (⟨a.val, by omega⟩ : Fin n) = ⟨b.val, by omega⟩ := hr.1 h1 ext exact Fin.mk.inj h2 have hf_sub : ∀ j : Fin (t + 1), f j ∈ hash_occupied_slots n r (List.ofFn p.1) := by intro j dsimp [f] have hj : (⟨j.val, by omega⟩ : Fin n).val < k := by have := j.isLt dsimp omega exact hp ⟨j.val, by omega⟩ hj have h_image : Finset.image f Finset.univ ⊆ hash_occupied_slots n r (List.ofFn p.1) := by intro x hx rw [Finset.mem_image] at hx rcases hx with ⟨j, _, rfl⟩ exact hf_sub j have h_card_le := Finset.card_le_card h_image rw [Finset.card_image_of_injective Finset.univ hf_inj] at h_card_le rw [Finset.card_fin] at h_card_le rw [hS_card] at h_card_le omega