AFTD Auto-Formalizing Theoretical Domains

hash_probe_tail_count_zero_of_lt_strict

theoremverified

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

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.

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

    lines 6–9

    uses Finset.card_eq_zero, Finset.filter_eq_empty_iff

      dsimp [hash_probe_tail_count]
      rw [Finset.card_eq_zero]
      rw [Finset.filter_eq_empty_iff]
      intro p _ hp
  2. 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`.

    lines 10–16

    uses List.length_ofFn, hash_occupied_slots_card

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

    lines 17–25

    uses add_left_cancel, Fin.mk.inj

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

    lines 26–33

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

    lines 34–38

    uses Finset.mem_image

      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
  6. 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`).

    lines 39–43

    uses Finset.card_le_card, Finset.card_image_of_injective, Finset.card_fin

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

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

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