AFTD Auto-Formalizing Theoretical Domains

hash_probe_expected_cost_sub_const

theoremverified

Translating an offset sequence by subtracting a constant element c in ZMod n preserves the expected probe cost at any load t, by translation equivariance of uniform open addressing.

Statement

theorem hash_probe_expected_cost_sub_const
    (n : ℕ) [NeZero n] (r : Fin n → ZMod n) (c : ZMod n) (t : ℕ) :
    hash_probe_expected_cost n (fun j => r j - c) t = hash_probe_expected_cost n r t
Source
step towards fixed_offset_hash_worst_mean_mixed_radix
Verified
02 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5
  • hash_probe_expected_costFor a table size n with [NeZero n], an offset sequence r : Fin n → ZMod n, and a number of inserted keys t : ℕ, hash_probe_expected_cost n…
  • 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_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,…
  • 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_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…

The proof, explained

The expected probe cost in open addressing is expressed as the sum of tail probabilities that an insertion requires at least k probes, which are proportional to the number of key sequences and query keys satisfying this condition. Probing with an offset sequence shifted by subtracting a constant c ∈ ZMod n evaluates probe positions as a + (r(j) - c) = (a - c) + r(j), which is identical to probing with the original offsets r on keys shifted by -c. The coordinatewise translation (p₁, p₂) ↦ (p₁ - c, p₂ - c) defines a bijection on the space of insertion sequences and query keys that preserves occupied table slots and probe locations. Because this bijection preserves the probe condition for every history, the tail counts, tail probabilities, and expected probe costs remain unchanged.

  1. A single insertion step with the translated offset sequence j ↦ r(j) - c for key a is identical to an insertion step with offset sequence r for key a - c.

    Unfolding the definition of hash_insert_step, the j-th candidate probe slot for inserting a with offset r(j) - c is a + (r(j) - c). By ring arithmetic in ZMod n, this equals (a - c) + r(j), which is the j-th probe slot for key a - c under the original offset sequence r. Rewriting with this equality shows that the candidate non-occupied slots and the chosen minimum probe index coincide in both cases.

    lines 1–5

    theorem hash_probe_expected_cost_sub_const_insert_step (n : ℕ) (r : Fin n → ZMod n) (c : ZMod n) (T : Finset (ZMod n)) (a : ZMod n) :
        hash_insert_step n (fun j => r j - c) T a = hash_insert_step n r T (a - c) := by
      dsimp [hash_insert_step]
      simp_rw [show ∀ j : Fin n, a + (r j - c) = a - c + r j from fun j => by ring]
    
  2. Inserting a list of keys A with offset sequence r - c produces the same set of occupied slots as inserting the componentwise shifted keys A - c with offset sequence r.

    The result is proved by induction on the list of keys A for an arbitrary initial table T. For the empty list nil, both folds return T by definition. For a cons cell a :: as, unfolding List.foldl and List.map extracts the first insertion step on key a, which rewriting by hash_probe_expected_cost_sub_const_insert_step transforms into an insertion of key a - c using offset r; the induction hypothesis then finishes the remaining insertions. Specializing this fold result to an initially empty table yields hash_probe_expected_cost_sub_const_occupied_slots.

    lines 6–19

    uses List.foldl_cons, List.map_cons, hash_probe_expected_cost_sub_const_insert_step, hash_probe_expected_cost_sub_const_occupied_slots_foldl

    theorem hash_probe_expected_cost_sub_const_occupied_slots_foldl (n : ℕ) (r : Fin n → ZMod n) (c : ZMod n) (A : List (ZMod n)) (T : Finset (ZMod n)) :
        List.foldl (hash_insert_step n (fun j => r j - c)) T A =
        List.foldl (hash_insert_step n r) T (A.map (· - c)) := by
      induction A generalizing T with
      | nil => rfl
      | cons a as ih =>
        simp only [List.foldl_cons, List.map_cons]
        rw [hash_probe_expected_cost_sub_const_insert_step]
        exact ih _
    
    theorem hash_probe_expected_cost_sub_const_occupied_slots (n : ℕ) (r : Fin n → ZMod n) (c : ZMod n) (A : List (ZMod n)) :
        hash_occupied_slots n (fun j => r j - c) A = hash_occupied_slots n r (A.map (· - c)) :=
      hash_probe_expected_cost_sub_const_occupied_slots_foldl n r c A ∅
    
  3. Subtracting c from each element of an insertion sequence and from the query key defines a bijection on the space of table configurations and queries.

    We define an equivalence hash_probe_expected_cost_sub_const_equiv on (Fin t → ZMod n) × ZMod n by sending (p₁, p₂) to (λ i, p₁(i) - c, p₂ - c), with inverse sending (p₁, p₂) to (λ i, p₁(i) + c, p₂ + c). The left and right inverse properties are verified componentwise by cancelling subtraction and addition via sub_add_cancel and add_sub_cancel_right.

    lines 20–26

    uses sub_add_cancel, add_sub_cancel_right

    def hash_probe_expected_cost_sub_const_equiv (t n : ℕ) (c : ZMod n) :
        ((Fin t → ZMod n) × ZMod n) ≃ ((Fin t → ZMod n) × ZMod n) where
      toFun p := (fun i => p.1 i - c, p.2 - c)
      invFun p := (fun i => p.1 i + c, p.2 + c)
      left_inv p := by ext <;> simp only [sub_add_cancel]
      right_inv p := by ext <;> simp only [add_sub_cancel_right]
    
  4. The tail count of probe lengths for offset sequence r - c equals that for r, provided the translation bijection preserves the condition of requiring at least k probes.

    Unfolding hash_probe_tail_count, the tail count is the cardinality of the subset of configuration-query pairs p = (p₁, p₂) whose first k probes hit occupied slots. Applying Finset.card_bijective with the translation equivalence e reduces showing that the sets have the same size to showing that an arbitrary pair p satisfies the condition under r - c if and only if e(p) satisfies the condition under r.

    lines 27–32

    uses Finset.card_bijective

    theorem hash_probe_expected_cost_sub_const_tail_count
        (n : ℕ) [NeZero n] (r : Fin n → ZMod n) (c : ZMod n) (t k : ℕ) :
        hash_probe_tail_count n (fun j => r j - c) t k = hash_probe_tail_count n r t k := by
      dsimp [hash_probe_tail_count]
      let e := hash_probe_expected_cost_sub_const_equiv t n c
      refine Finset.card_bijective e e.bijective ?_
  5. The occupied table slots after inserting key sequence p₁ with offset r - c equal the occupied table slots after inserting (e(p))₁ with offset r.

    After simplifying set membership in the tail count filter using Finset.mem_filter, Finset.mem_univ, and true_and, we establish helper lemma h_occ. By hash_probe_expected_cost_sub_const_occupied_slots, the occupied slots with offset r - c equal those with offset r on the shifted list. Applying List.map_ofFn shows that shifting the list of keys from p₁ by -c matches (e(p))₁ = λ i, p₁(i) - c.

    lines 33–41

    uses Finset.mem_filter, Finset.mem_univ, true_and, hash_probe_expected_cost_sub_const_occupied_slots, List.map_ofFn

      intro p
      simp only [Finset.mem_filter, Finset.mem_univ, true_and]
      have h_occ : hash_occupied_slots n (fun j => r j - c) (List.ofFn p.1) =
          hash_occupied_slots n r (List.ofFn (e p).1) := by
        rw [hash_probe_expected_cost_sub_const_occupied_slots]
        congr 1
        dsimp [e, hash_probe_expected_cost_sub_const_equiv]
        simp only [List.map_ofFn]
        rfl
  6. The j-th probe position for query key p₂ with offset r - c equals that for (e(p))₂ with offset r, completing the proof that tail counts match.

    For each probe index j, helper lemma h_slot proves p₂ + (r(j) - c) = (e(p))₂ + r(j) by ring arithmetic in ZMod n. Rewriting the probe condition with h_slot and h_occ makes the condition for p under r - c identical to the condition for e(p) under r, closing the equivalence.

    lines 42–46

      have h_slot (j : Fin n) : p.2 + (r j - c) = (e p).2 + r j := by
        dsimp [e, hash_probe_expected_cost_sub_const_equiv]
        ring
      simp_rw [h_slot, h_occ]
    
  7. The tail probability that a query requires at least k probes is invariant under translating the offset sequence by -c.

    Unfolding hash_probe_tail_prob, the tail probability is defined as the tail count divided by the total number of histories n^(t+1). Rewriting with hash_probe_expected_cost_sub_const_tail_count replaces the tail count for r - c with that for r.

    lines 47–52

    uses hash_probe_expected_cost_sub_const_tail_count

    theorem hash_probe_expected_cost_sub_const_tail_prob
        (n : ℕ) [NeZero n] (r : Fin n → ZMod n) (c : ZMod n) (t k : ℕ) :
        hash_probe_tail_prob n (fun j => r j - c) t k = hash_probe_tail_prob n r t k := by
      dsimp [hash_probe_tail_prob]
      rw [hash_probe_expected_cost_sub_const_tail_count]
    
  8. The expected probe cost at load t is preserved when translating the offset sequence by subtracting a constant c ∈ ZMod n.

    Unfolding hash_probe_expected_cost, the expected probe cost is expressed as the sum of tail probabilities ∑ k ∈ Finset.range (n + 1), P(probes ≥ k). Rewriting each term in the sum using hash_probe_expected_cost_sub_const_tail_prob yields the expected probe cost for the original offset sequence r.

    lines 53–58

    uses hash_probe_expected_cost_sub_const_tail_prob

    /-- Translating an offset sequence by subtracting a constant element c in ZMod n preserves the expected probe cost at any load t. -/
    theorem hash_probe_expected_cost_sub_const
        (n : ℕ) [NeZero n] (r : Fin n → ZMod n) (c : ZMod n) (t : ℕ) :
        hash_probe_expected_cost n (fun j => r j - c) t = hash_probe_expected_cost n r t := by
      dsimp [hash_probe_expected_cost]
      simp_rw [hash_probe_expected_cost_sub_const_tail_prob]
add_sub_cancel_right
In an additive group, adding b to a and then subtracting b yields a.
Finset.card_bijective
If a function e is bijective and maps elements of a finite set s into a finite set t if and only if they belong to s, then s and t have equal cardinality.
Finset.mem_filter
An element belongs to Finset.filter p s if and only if it belongs to s and satisfies predicate p.
Finset.mem_univ
Every element of a finite type belongs to the universal finite set Finset.univ.
hash_probe_expected_cost_sub_const_insert_step
Inserting a key a with offset sequence translated by -c into a set of occupied slots T results in the same updated table as inserting the translated key a - c with the original offset sequence r.
hash_probe_expected_cost_sub_const_occupied_slots
The set of occupied slots after inserting key list A into an initially empty table with offset sequence r - c equals the set of occupied slots after inserting the translated keys A - c with offset sequence r.
hash_probe_expected_cost_sub_const_occupied_slots_foldl
Folding insertion of a list of keys A starting from table T with offset sequence r - c produces the same table as folding insertion of the translated keys A - c with offset sequence r.
hash_probe_expected_cost_sub_const_tail_count
Translating the offset sequence by subtracting c preserves the number of insertion histories and queries requiring at least k probes.
hash_probe_expected_cost_sub_const_tail_prob
Translating the offset sequence by subtracting c preserves the probability that a query requires at least k probes at load t.
List.foldl_cons
Folding a function over a non-empty list a :: l applies the step function to the accumulator and head element a, then folds over the tail l.
List.map_cons
Mapping a function over a non-empty list a :: l applies the function to a and prepends the result to the mapped tail.
List.map_ofFn
Mapping a function g over a list constructed from a function f on Fin n is equal to constructing the list directly from the composite function g ∘ f.
sub_add_cancel
In an additive group, subtracting b from a and then adding b yields a.
true_and
The conjunction True ∧ p is logically equivalent to p.

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

theorem hash_probe_expected_cost_sub_const_insert_step (n : ℕ) (r : Fin n → ZMod n) (c : ZMod n) (T : Finset (ZMod n)) (a : ZMod n) :    hash_insert_step n (fun j => r j - c) T a = hash_insert_step n r T (a - c) := by  dsimp [hash_insert_step]  simp_rw [show ∀ j : Fin n, a + (r j - c) = a - c + r j from fun j => by ring]theorem hash_probe_expected_cost_sub_const_occupied_slots_foldl (n : ℕ) (r : Fin n → ZMod n) (c : ZMod n) (A : List (ZMod n)) (T : Finset (ZMod n)) :    List.foldl (hash_insert_step n (fun j => r j - c)) T A =    List.foldl (hash_insert_step n r) T (A.map (· - c)) := by  induction A generalizing T with  | nil => rfl  | cons a as ih =>    simp only [List.foldl_cons, List.map_cons]    rw [hash_probe_expected_cost_sub_const_insert_step]    exact ih _theorem hash_probe_expected_cost_sub_const_occupied_slots (n : ℕ) (r : Fin n → ZMod n) (c : ZMod n) (A : List (ZMod n)) :    hash_occupied_slots n (fun j => r j - c) A = hash_occupied_slots n r (A.map (· - c)) :=  hash_probe_expected_cost_sub_const_occupied_slots_foldl n r c A ∅def hash_probe_expected_cost_sub_const_equiv (t n : ℕ) (c : ZMod n) :    ((Fin t → ZMod n) × ZMod n) ≃ ((Fin t → ZMod n) × ZMod n) where  toFun p := (fun i => p.1 i - c, p.2 - c)  invFun p := (fun i => p.1 i + c, p.2 + c)  left_inv p := by ext <;> simp only [sub_add_cancel]  right_inv p := by ext <;> simp only [add_sub_cancel_right]theorem hash_probe_expected_cost_sub_const_tail_count    (n : ℕ) [NeZero n] (r : Fin n → ZMod n) (c : ZMod n) (t k : ℕ) :    hash_probe_tail_count n (fun j => r j - c) t k = hash_probe_tail_count n r t k := by  dsimp [hash_probe_tail_count]  let e := hash_probe_expected_cost_sub_const_equiv t n c  refine Finset.card_bijective e e.bijective ?_  intro p  simp only [Finset.mem_filter, Finset.mem_univ, true_and]  have h_occ : hash_occupied_slots n (fun j => r j - c) (List.ofFn p.1) =      hash_occupied_slots n r (List.ofFn (e p).1) := by    rw [hash_probe_expected_cost_sub_const_occupied_slots]    congr 1    dsimp [e, hash_probe_expected_cost_sub_const_equiv]    simp only [List.map_ofFn]    rfl  have h_slot (j : Fin n) : p.2 + (r j - c) = (e p).2 + r j := by    dsimp [e, hash_probe_expected_cost_sub_const_equiv]    ring  simp_rw [h_slot, h_occ]theorem hash_probe_expected_cost_sub_const_tail_prob    (n : ℕ) [NeZero n] (r : Fin n → ZMod n) (c : ZMod n) (t k : ℕ) :    hash_probe_tail_prob n (fun j => r j - c) t k = hash_probe_tail_prob n r t k := by  dsimp [hash_probe_tail_prob]  rw [hash_probe_expected_cost_sub_const_tail_count]/-- Translating an offset sequence by subtracting a constant element c in ZMod n preserves the expected probe cost at any load t. -/theorem hash_probe_expected_cost_sub_const    (n : ℕ) [NeZero n] (r : Fin n → ZMod n) (c : ZMod n) (t : ℕ) :    hash_probe_expected_cost n (fun j => r j - c) t = hash_probe_expected_cost n r t := by  dsimp [hash_probe_expected_cost]  simp_rw [hash_probe_expected_cost_sub_const_tail_prob]
See it in the graphDiscuss this resultChallenge it