hash_occupied_slots_card
For 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 set of occupied slots hash_occupied_slots n r A has cardinality equal to A.length.
Statement
theorem hash_occupied_slots_card (n : ℕ) [NeZero n] (r : Fin n → ZMod n)
(hr : Function.Bijective r) (A : List (ZMod n)) (hA : A.length ≤ n) :
(hash_occupied_slots n r A).card = A.length- Source
- step towards unit_first_fixed_offset_mean_probe_maximum
- Verified
- 05 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- 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…
- hash_occupied_slots_nilFor any n and offset sequence r : Fin n → ZMod n, hash_occupied_slots n r [] = ∅.
- hash_insert_stepGiven table size n, an offset sequence r : Fin n → ZMod n, a set of occupied slots T : Finset (ZMod n), and an element a : ZMod n,…
- Used by 5
- hash_probe_tail_count_zero_of_lt_strictFor 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.
- hash_probe_expected_cost_twoAfter two insertions the expected cost is 1+2/n+(3+[2r₁=0])/n².
- not_hash_probe_tail_prob_zero_of_ltThe statement
hash_probe_tail_prob_zero_of_ltis false: Take n = 1, r = (fun _ => 0 : Fin 1 → ZMod 1), t = 1, k = 2. Hypotheses hold:… - 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…
- prime_fixed_offset_linear_probe_tail_prob_interior_t_predAt load t = p - 1 (one empty slot), every bijective offset sequence has identical probe tail probabilities, matching linear probing.
The proof, explained
The theorem is proved by induction on the list of keys A from the right using List.reverseRecOn. The empty list occupies 0 slots, matching length 0. For the step A = xs ++ [x], the prefix satisfies |xs| < n, so by the induction hypothesis the table occupies fewer than n slots. The helper lemma hash_occupied_slots_card_insert_step then ensures that inserting x occupies a new slot, because the probe sequence j ↦ x + r j is injective on Fin n and cannot be entirely contained in a table of size strictly less than n.
The probe function j ↦ a + r j from Fin n to ZMod n is injective.
The probe map is the composition of the offset bijection r with left addition by a in ZMod n. Left addition in an additive group is bijective (and thus injective) by AddGroup.addLeft_bijective, and the composition of injective maps is injective.
uses
AddGroup.addLeft_bijectivehave h_cand : (Finset.univ.filter (fun j : Fin n => a + r j ∉ T)).Nonempty := by have h_inj : Function.Injective (fun j : Fin n => a + r j) := by have : (fun j : Fin n => a + r j) = (fun x : ZMod n => a + x) ∘ r := rfl rw [this] exact (AddGroup.addLeft_bijective a).injective.comp hr.injective
If no candidate unoccupied probe slot existed, then every probed position a + r j would belong to T.
Suppose for contradiction that the candidate set {j | a + r j ∉ T} is empty. If any index j had a + r j ∉ T, then j would belong to the candidate set by Finset.mem_filter and Finset.mem_univ, contradicting Finset.notMem_empty. Hence a + r j ∈ T for all j.
uses
Finset.nonempty_iff_ne_empty,not_not,Finset.mem_filter,Finset.mem_univ,Finset.notMem_emptyby_contra h_empty rw [Finset.nonempty_iff_ne_empty, not_not] at h_empty have h_all : ∀ j : Fin n, a + r j ∈ T := by intro j by_contra hj have : j ∈ Finset.univ.filter (fun j : Fin n => a + r j ∉ T) := by rw [Finset.mem_filter] exact ⟨Finset.mem_univ _, hj⟩ rw [h_empty] at this exact Finset.notMem_empty j this
The set of candidate indices whose probed slots are unoccupied is nonempty.
Since all probed positions belong to T, the image of the probe map is a subset of T by Finset.mem_image. By Finset.card_le_card, the image has cardinality at most |T|. However, because the probe map is injective, Finset.card_image_of_injective, Finset.card_univ, and Fintype.card_fin show its image has size n, so n ≤ |T|. This contradicts the assumption |T| < n, and omega derives False.
uses
Finset.mem_image,Finset.card_le_card,Finset.card_image_of_injective,Finset.card_univ,Fintype.card_finhave h_sub : (Finset.univ.image (fun j : Fin n => a + r j)) ⊆ T := by intro x hx rw [Finset.mem_image] at hx rcases hx with ⟨j, _, rfl⟩ exact h_all j have h_card_le : (Finset.univ.image (fun j : Fin n => a + r j)).card ≤ T.card := Finset.card_le_card h_sub rw [Finset.card_image_of_injective _ h_inj, Finset.card_univ, Fintype.card_fin] at h_card_le omega
Inserting a key into a table with |T| < n increases the cardinality of occupied slots by 1.
Unfolding hash_insert_step, the candidate set is nonempty by the previous step, so dif_pos selects the branch that inserts a + r(j*) into T, where j* is the minimal candidate index. Rewriting the union as insert(a + r(j*), T) using Finset.union_comm and Finset.singleton_union, its cardinality is |T| + 1 by Finset.card_insert_of_notMem, since a + r(j*) ∉ T by Finset.min'_mem and Finset.mem_filter.
uses
dif_pos,Finset.union_comm,Finset.singleton_union,Finset.card_insert_of_notMem,Finset.min'_mem,Finset.mem_filterunfold hash_insert_step dsimp rw [dif_pos h_cand] rw [Finset.union_comm, Finset.singleton_union, Finset.card_insert_of_notMem] have h_min := Finset.min'_mem (Finset.univ.filter fun j => a + r j ∉ T) h_cand rw [Finset.mem_filter] at h_min exact h_min.2
For the empty list of keys, the number of occupied slots is 0, which equals the list length.
We induct on the list A from the right using List.reverseRecOn. In the base case A = [], hash_occupied_slots n r [] is empty by hash_occupied_slots_nil, so its cardinality is 0 by Finset.card_empty, which matches [].length = 0 by List.length_nil.
uses
List.reverseRecOn,hash_occupied_slots_nil,Finset.card_empty,List.length_nilinduction A using List.reverseRecOn with | nil => rw [hash_occupied_slots_nil, Finset.card_empty, List.length_nil]
In the inductive step for A = xs ++ [x], the prefix xs has length at most n, enabling the induction hypothesis.
Expanding the length with List.length_append and List.length_singleton, the hypothesis |xs| + 1 ≤ n implies |xs| ≤ n by linear integer arithmetic (omega), which allows instantiating the induction hypothesis for xs.
uses
List.length_append,List.length_singleton| append_singleton xs x ih => rw [List.length_append, List.length_singleton] at hA ⊢ have h_xs_len : xs.length ≤ n := by omega have ih_val := ih h_xs_lenOccupied slots after inserting xs ++ [x] equals one insertion step of x into the slots occupied by xs.
By definition, hash_occupied_slots is a left fold of hash_insert_step starting from ∅. By List.foldl_append, folding over xs ++ [x] splits into folding over xs followed by a single insertion step with key x.
uses
List.foldl_appendhave h_fold : hash_occupied_slots n r (xs ++ [x]) = hash_insert_step n r (hash_occupied_slots n r xs) x := by dsimp [hash_occupied_slots] rw [List.foldl_append] rfl
The number of occupied slots after inserting xs ++ [x] is |xs| + 1.
Rewriting with the fold identity, we apply hash_occupied_slots_card_insert_step to the table T = hash_occupied_slots n r xs and key x. The prerequisite |T| < n holds because |T| = |xs| by the induction hypothesis and |xs| < n follows from |xs| + 1 ≤ n by omega. The lemma evaluates the cardinality to |xs| + 1, matching the length of xs ++ [x].
uses
hash_occupied_slots_card_insert_steprw [h_fold] rw [hash_occupied_slots_card_insert_step n r hr (hash_occupied_slots n r xs)] · rw [ih_val] · rw [ih_val] omega
AddGroup.addLeft_bijective- In an additive group, left addition by a fixed element is a bijective map.
Finset.nonempty_iff_ne_empty- A finite set is nonempty if and only if it is not equal to the empty set.
not_not- Double negation elimination: ¬¬P ↔ P.
Finset.mem_filter- An element belongs to a filtered set if and only if it belongs to the base set and satisfies the predicate.
Finset.mem_univ- Every element of a finite type belongs to its universal set Finset.univ.
Finset.notMem_empty- No element belongs to the empty set.
Finset.mem_image- An element b belongs to the image f(s) if and only if b = f(a) for some a in s.
Finset.card_le_card- If s ⊆ t for finite sets s and t, then |s| ≤ |t|.
Finset.card_image_of_injective- The image of a finite set under an injective map has the same cardinality as the set.
Finset.card_univ- The cardinality of the universal set Finset.univ is equal to the cardinality of the underlying finite type.
Fintype.card_fin- The cardinality of Fin n is n.
dif_pos- A dependent if-then-else expression evaluates to its then-branch when the condition is true.
Finset.union_comm- Union of finite sets is commutative: s₁ ∪ s₂ = s₂ ∪ s₁.
Finset.singleton_union- The union of a singleton {x} and a set s equals insert x s.
Finset.card_insert_of_notMem- Inserting an element a into a finite set s that does not contain a increases the cardinality by 1.
Finset.min'_mem- The minimum element min' of a nonempty finite linearly ordered set belongs to the set.
List.reverseRecOn- Principle of induction on lists from the right: to prove a property of lists, show it for the empty list and show it is preserved when appending a single element.
hash_occupied_slots_nil- The set of occupied slots after inserting the empty list of keys into a hash table is empty.
Finset.card_empty- The cardinality of the empty set is 0.
List.length_nil- The length of the empty list is 0.
List.length_append- The length of the concatenation of two lists is the sum of their lengths.
List.length_singleton- The length of a single-element list is 1.
List.foldl_append- A left fold over concatenated lists l ++ l' equals the fold over l' starting from the fold over l.
hash_occupied_slots_card_insert_step- If the probe sequence r is bijective and fewer than n slots are occupied, a single insertion step increases the number of occupied slots by exactly 1.
- The file contains both the helper lemma hash_occupied_slots_card_insert_step (lines 1–34) and the main theorem hash_occupied_slots_card (lines 37–56).
- The omega tactic is used in lines 27, 45, and 56 to discharge linear integer arithmetic inequalities over ℕ.
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.
lemma hash_occupied_slots_card_insert_step (n : ℕ) [NeZero n] (r : Fin n → ZMod n) (hr : Function.Bijective r) (T : Finset (ZMod n)) (hT : T.card < n) (a : ZMod n) : (hash_insert_step n r T a).card = T.card + 1 := by have h_cand : (Finset.univ.filter (fun j : Fin n => a + r j ∉ T)).Nonempty := by have h_inj : Function.Injective (fun j : Fin n => a + r j) := by have : (fun j : Fin n => a + r j) = (fun x : ZMod n => a + x) ∘ r := rfl rw [this] exact (AddGroup.addLeft_bijective a).injective.comp hr.injective by_contra h_empty rw [Finset.nonempty_iff_ne_empty, not_not] at h_empty have h_all : ∀ j : Fin n, a + r j ∈ T := by intro j by_contra hj have : j ∈ Finset.univ.filter (fun j : Fin n => a + r j ∉ T) := by rw [Finset.mem_filter] exact ⟨Finset.mem_univ _, hj⟩ rw [h_empty] at this exact Finset.notMem_empty j this have h_sub : (Finset.univ.image (fun j : Fin n => a + r j)) ⊆ T := by intro x hx rw [Finset.mem_image] at hx rcases hx with ⟨j, _, rfl⟩ exact h_all j have h_card_le : (Finset.univ.image (fun j : Fin n => a + r j)).card ≤ T.card := Finset.card_le_card h_sub rw [Finset.card_image_of_injective _ h_inj, Finset.card_univ, Fintype.card_fin] at h_card_le omega unfold hash_insert_step dsimp rw [dif_pos h_cand] rw [Finset.union_comm, Finset.singleton_union, Finset.card_insert_of_notMem] have h_min := Finset.min'_mem (Finset.univ.filter fun j => a + r j ∉ T) h_cand rw [Finset.mem_filter] at h_min exact h_min.2/-- Inserting a sequence of length at most n into an initially empty table always occupies exactly as many slots as inserted keys. -/theorem hash_occupied_slots_card (n : ℕ) [NeZero n] (r : Fin n → ZMod n) (hr : Function.Bijective r) (A : List (ZMod n)) (hA : A.length ≤ n) : (hash_occupied_slots n r A).card = A.length := by induction A using List.reverseRecOn with | nil => rw [hash_occupied_slots_nil, Finset.card_empty, List.length_nil] | append_singleton xs x ih => rw [List.length_append, List.length_singleton] at hA ⊢ have h_xs_len : xs.length ≤ n := by omega have ih_val := ih h_xs_len have h_fold : hash_occupied_slots n r (xs ++ [x]) = hash_insert_step n r (hash_occupied_slots n r xs) x := by dsimp [hash_occupied_slots] rw [List.foldl_append] rfl rw [h_fold] rw [hash_occupied_slots_card_insert_step n r hr (hash_occupied_slots n r xs)] · rw [ih_val] · rw [ih_val] omega