AFTD Auto-Formalizing Theoretical Domains

hash_occupied_slots_card

theoremverified

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

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.

  1. 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.

    lines 4–8

    uses AddGroup.addLeft_bijective

      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
  2. 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.

    lines 9–18

    uses Finset.nonempty_iff_ne_empty, not_not, Finset.mem_filter, Finset.mem_univ, Finset.notMem_empty

        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
  3. 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.

    lines 19–27

    uses Finset.mem_image, Finset.card_le_card, Finset.card_image_of_injective, Finset.card_univ, Fintype.card_fin

        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
  4. 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.

    lines 28–34

    uses dif_pos, Finset.union_comm, Finset.singleton_union, Finset.card_insert_of_notMem, Finset.min'_mem, Finset.mem_filter

      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
  5. 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.

    lines 40–42

    uses List.reverseRecOn, hash_occupied_slots_nil, Finset.card_empty, List.length_nil

      induction A using List.reverseRecOn with
      | nil =>
        rw [hash_occupied_slots_nil, Finset.card_empty, List.length_nil]
  6. 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.

    lines 43–46

    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_len
  7. Occupied 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.

    lines 47–51

    uses List.foldl_append

        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
  8. 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].

    lines 52–56

    uses hash_occupied_slots_card_insert_step

        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
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.

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

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
See it in the graphDiscuss this resultChallenge it