hash_probe_expected_cost_sub_const
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.
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.
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]
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.
uses
List.foldl_cons,List.map_cons,hash_probe_expected_cost_sub_const_insert_step,hash_probe_expected_cost_sub_const_occupied_slots_foldltheorem 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 ∅
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.
uses
sub_add_cancel,add_sub_cancel_rightdef 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]
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.
uses
Finset.card_bijectivetheorem 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 ?_
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.
uses
Finset.mem_filter,Finset.mem_univ,true_and,hash_probe_expected_cost_sub_const_occupied_slots,List.map_ofFnintro 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
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.
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]
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.
uses
hash_probe_expected_cost_sub_const_tail_counttheorem 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]
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.
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.
- The expected probe cost is formalized via the tail-sum formula ∑ k ∈ Finset.range (n + 1), P(probes ≥ k), where probabilities are computed by counting favorable histories in the uniform product space (Fin t → ZMod n) × ZMod n of prior insertions and query keys.
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.
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]