fixed_offset_hash_table_prob_bound_of_count_bound
For any n : ℕ with NeZero n, r : Fin n → ZMod n, and k < t ≤ n, if (n : ℝ) * hash_count_fully_occupied n r S (t - 1) ≤ hash_count_fully_occupied n r S t * (1 - (k : ℝ) / t + (k : ℝ) / n) holds for all S : Finset (ZMod n) with S.card = k, then hash_max_occupied_prob n r k (t - 1) ≤ hash_max_occupied_prob n r k t * (1 - (k : ℝ) / t + (k : ℝ) / n).
Statement
theorem fixed_offset_hash_table_prob_bound_of_count_bound
(n : ℕ) [NeZero n] (r : Fin n → ZMod n) (k t : ℕ)
(hkt : k < t) (htn : t ≤ n)
(hF : ∀ S : Finset (ZMod n), S.card = k →
(n : ℝ) * hash_count_fully_occupied n r S (t - 1) ≤
hash_count_fully_occupied n r S t * (1 - (k : ℝ) / t + (k : ℝ) / n)) :
hash_max_occupied_prob n r k (t - 1) ≤
hash_max_occupied_prob n r k t * (1 - (k : ℝ) / t + (k : ℝ) / n)- Source
- arXiv:2610.31363 Theorem 4.1
- Verified
- 23 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- hash_count_fully_occupiedThe cardinality of hash_fully_occupied_seqs n r S t, giving the number of length-t sequences in Fin t → ZMod n that fully occupy S.
- hash_max_occupied_probThe maximum probability p_k(t) defined as the supremum of hash_count_fully_occupied n r S t over all S : Finset (ZMod n) with S.card = k,…
Read back from the Lean
Let $n$ be a positive natural number (n : ℕ with [NeZero n]), $r : \text{Fin } n \to \mathbb{Z}/n\mathbb{Z}$, and $k, t \in \mathbb{N}$ such that $k < t$ and $t \le n$.
Assume that for every subset $S \subseteq \mathbb{Z}/n\mathbb{Z}$ of size $k$ (S.card = k), the number of length-$(t-1)$ probe sequences fully occupying $S$, scaled by $n$, satisfies:
$$n \cdot \text{hash\_count\_fully\_occupied}(n, r, S, t - 1) \le \text{hash\_count\_fully\_occupied}(n, r, S, t) \cdot \left(1 - \frac{k}{t} + \frac{k}{n}\right)$$
(evaluated in $\mathbb{R}$).
Then the maximum occupancy probability for size-$k$ sets at step $t - 1$ is bounded by that at step $t$:
$$\text{hash\_max\_occupied\_prob}(n, r, k, t - 1) \le \text{hash\_max\_occupied\_prob}(n, r, k, t) \cdot \left(1 - \frac{k}{t} + \frac{k}{n}\right).$$
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The proof derives the recurrence bound on the maximum occupied probability p_k(t) from the recurrence bound on individual subset counts F_S(t). Choosing a subset S_max that achieves the maximal count M1 at time t - 1, the assumption hF yields n * M1 ≤ F_{S_max}(t) * c ≤ M2 * c, where M2 is the maximal count at time t and c = 1 - k/t + k/n ≥ 0. Dividing both sides of n * M1 ≤ M2 * c by the positive denominator n^t = n^(t - 1) * n completes the derivation.
Unfold the definition of hash_max_occupied_prob and introduce abbreviations for the collection of subsets K, the factor c, and the maxima M1 and M2.
We unfold hash_max_occupied_prob, which expresses the maximum occupancy probability at time t as the supremum over k-element subsets divided by n^t. We then set K to be the set of k-element subsets of ZMod n, c to be the multiplier 1 - k/t + k/n, and M1, M2 to be the suprema of the fully occupied counts at times t - 1 and t, respectively.
have _ := htn dsimp only [hash_max_occupied_prob] set K : Finset (Finset (ZMod n)) := (Finset.univ : Finset (Finset (ZMod n))).filter (fun S => S.card = k) set c : ℝ := 1 - (k : ℝ) / t + (k : ℝ) / n set M1 : ℕ := K.sup (fun S => hash_count_fully_occupied n r S (t - 1)) set M2 : ℕ := K.sup (fun S => hash_count_fully_occupied n r S t)
t is strictly positive, and the multiplier c is non-negative (0 ≤ c).
From k < t we have 0 < t. In ℝ, since 0 < t and k < t, dividing gives k / t < 1, so 1 - k / t > 0. Since n is positive, k / n ≥ 0. Summing these inequalities shows c = 1 - k / t + k / n ≥ 0.
uses
NeZero.pos,div_lt_iff₀have ht_pos : 0 < t := by omega have hc_nonneg : 0 ≤ c := by have ht_pos_real : (0 : ℝ) < (t : ℝ) := by positivity have hn_pos_real : (0 : ℝ) < (n : ℝ) := by have : 0 < n := NeZero.pos n positivity have hkt_real : (k : ℝ) < (t : ℝ) := by exact_mod_cast hkt have h1 : (k : ℝ) / t < 1 := by rw [div_lt_iff₀ ht_pos_real] linarith have h2 : 0 ≤ (k : ℝ) / n := by positivity change 0 ≤ 1 - (k : ℝ) / t + (k : ℝ) / n linarith
The inequality n * M1 ≤ M2 * c holds in ℝ.
We consider whether K is non-empty. If K is non-empty, the supremum M1 is attained at some subset S_max with |S_max| = k. The hypothesis hF applied to S_max gives n * M1 ≤ count(S_max, t) * c. Since S_max ∈ K, count(S_max, t) ≤ M2, and since c ≥ 0, this product is bounded by M2 * c. If K is empty, both M1 and M2 vanish, so both sides are zero and the inequality holds trivially.
uses
Finset.exists_mem_eq_sup,Finset.mem_filter.mp,Finset.le_sup,mul_le_mul_of_nonneg_right,le_trans,Finset.not_nonempty_iff_eq_empty.mp,Nat.cast_zero,mul_zero,zero_mul,le_reflhave h_bound : (n : ℝ) * (M1 : ℝ) ≤ (M2 : ℝ) * c := by by_cases hK : K.Nonempty · obtain ⟨S_max, hS_max_mem, hS_max_eq⟩ := Finset.exists_mem_eq_sup K hK (fun S => hash_count_fully_occupied n r S (t - 1)) have hS_card : S_max.card = k := (Finset.mem_filter.mp hS_max_mem).2 have hF_max := hF S_max hS_card have hS_le : hash_count_fully_occupied n r S_max t ≤ M2 := Finset.le_sup (f := fun S => hash_count_fully_occupied n r S t) hS_max_mem have hS_le_real : (hash_count_fully_occupied n r S_max t : ℝ) ≤ (M2 : ℝ) := by exact_mod_cast hS_le have h_mul_le : (hash_count_fully_occupied n r S_max t : ℝ) * c ≤ (M2 : ℝ) * c := mul_le_mul_of_nonneg_right hS_le_real hc_nonneg have hM1_eq : M1 = hash_count_fully_occupied n r S_max (t - 1) := hS_max_eq rw [hM1_eq] exact le_trans hF_max h_mul_le · have hK_empty : K = ∅ := Finset.not_nonempty_iff_eq_empty.mp hK have hM1_zero : M1 = 0 := by change (K.sup (fun S => hash_count_fully_occupied n r S (t - 1))) = 0 rw [hK_empty] rfl have hM2_zero : M2 = 0 := by change (K.sup (fun S => hash_count_fully_occupied n r S t)) = 0 rw [hK_empty] rfl rw [hM1_zero, hM2_zero] simp only [Nat.cast_zero, mul_zero, zero_mul, le_refl]
n > 0, n^(t - 1) > 0, and n^t = n^(t - 1) * n in ℝ.
Since n is non-zero, n > 0 in ℝ, which also implies n^(t - 1) > 0. Because t > 0, we can write t = (t - 1) + 1, so n^t = n^(t - 1) * n by the successor property of powers.
uses
NeZero.pos,Nat.sub_add_cancel,Nat.succ_le_of_lt,pow_succhave hn_pos : (0 : ℝ) < (n : ℝ) := by have : 0 < n := NeZero.pos n positivity have hnt_pos : (0 : ℝ) < (n : ℝ) ^ (t - 1) := by positivity have ht_eq : (n : ℝ) ^ t = (n : ℝ) ^ (t - 1) * (n : ℝ) := by have : t = (t - 1) + 1 := (Nat.sub_add_cancel (Nat.succ_le_of_lt ht_pos)).symm nth_rw 1 [this] rw [pow_succ]
hash_max_occupied_prob n r k (t - 1) ≤ hash_max_occupied_prob n r k t * c holds.
In terms of M1 and M2, the goal is M1 / n^(t - 1) ≤ (M2 / n^t) * c. Substituting n^t = n^(t - 1) * n, we rewrite the left-hand side as (n * M1) / (n^(t - 1) * n) by scaling numerator and denominator by n, and the right-hand side as (M2 * c) / (n^(t - 1) * n). Since the denominator n^(t - 1) * n is strictly positive and n * M1 ≤ M2 * c, dividing both sides by this denominator yields the claim.
uses
mul_pos,mul_div_mul_right,ne_of_gt,mul_comm,div_le_div_of_nonneg_right,le_of_ltchange (M1 : ℝ) / (n : ℝ) ^ (t - 1) ≤ ((M2 : ℝ) / (n : ℝ) ^ t) * c rw [ht_eq] have h_prod_pos : 0 < (n : ℝ) ^ (t - 1) * (n : ℝ) := mul_pos hnt_pos hn_pos have h_rw1 : (M1 : ℝ) / (n : ℝ) ^ (t - 1) = ((n : ℝ) * (M1 : ℝ)) / ((n : ℝ) ^ (t - 1) * (n : ℝ)) := by have h_cancel := (mul_div_mul_right (M1 : ℝ) ((n : ℝ) ^ (t - 1)) (ne_of_gt hn_pos)).symm rw [mul_comm (M1 : ℝ) (n : ℝ)] at h_cancel exact h_cancel have h_rw2 : ((M2 : ℝ) / ((n : ℝ) ^ (t - 1) * (n : ℝ))) * c = ((M2 : ℝ) * c) / ((n : ℝ) ^ (t - 1) * (n : ℝ)) := by ring rw [h_rw1, h_rw2] exact div_le_div_of_nonneg_right h_bound (le_of_lt h_prod_pos)
NeZero.pos- A nonzero element in a partially ordered type with zero as a bottom element is strictly positive.
div_lt_iff₀- For c > 0 in a group with zero, b / c < a if and only if b < a * c.
Finset.exists_mem_eq_sup- On a nonempty finite set, a function into a linear order with a bottom element attains its supremum.
Finset.mem_filter.mp- An element in a filtered finset belongs to the base set and satisfies the predicate.
Finset.le_sup- The value of a function at any element of a finset is bounded by its supremum over that finset.
mul_le_mul_of_nonneg_right- Multiplying both sides of an inequality by a nonnegative element on the right preserves the inequality.
le_trans- Inequality is transitive: if a ≤ b and b ≤ c, then a ≤ c.
Finset.not_nonempty_iff_eq_empty.mp- A finset that is not nonempty is the empty set.
Nat.cast_zero- The coercion of the natural number 0 to a ring is 0.
mul_zero- Multiplying by zero on the right gives zero.
zero_mul- Multiplying by zero on the left gives zero.
le_refl- Every element in a preorder is less than or equal to itself.
Nat.sub_add_cancel- For natural numbers with m ≤ n, (n - m) + m = n.
Nat.succ_le_of_lt- If n < m for natural numbers, then n + 1 ≤ m.
pow_succ- In a monoid, a^(n + 1) = a^n * a.
mul_pos- The product of two strictly positive elements is strictly positive.
mul_div_mul_right- In a group with zero, cancelling a nonzero factor c on the right yields (a * c) / (b * c) = a / b.
ne_of_gt- If b < a, then a ≠ b.
mul_comm- Multiplication in a commutative magma is commutative: a * b = b * a.
div_le_div_of_nonneg_right- Dividing both sides of an inequality by a nonnegative element preserves the inequality.
le_of_lt- A strict inequality a < b implies the weak inequality a ≤ b.
- The proof includes an explicit case analysis on whether K is empty (i.e. whether there exist subsets of size k), though mathematically this is an edge case where both suprema default to zero.
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.
/-- Derivation of the recurrence on p_k(t) from the recurrence on F_S(t). -/theorem fixed_offset_hash_table_prob_bound_of_count_bound (n : ℕ) [NeZero n] (r : Fin n → ZMod n) (k t : ℕ) (hkt : k < t) (htn : t ≤ n) (hF : ∀ S : Finset (ZMod n), S.card = k → (n : ℝ) * hash_count_fully_occupied n r S (t - 1) ≤ hash_count_fully_occupied n r S t * (1 - (k : ℝ) / t + (k : ℝ) / n)) : hash_max_occupied_prob n r k (t - 1) ≤ hash_max_occupied_prob n r k t * (1 - (k : ℝ) / t + (k : ℝ) / n) := by have _ := htn dsimp only [hash_max_occupied_prob] set K : Finset (Finset (ZMod n)) := (Finset.univ : Finset (Finset (ZMod n))).filter (fun S => S.card = k) set c : ℝ := 1 - (k : ℝ) / t + (k : ℝ) / n set M1 : ℕ := K.sup (fun S => hash_count_fully_occupied n r S (t - 1)) set M2 : ℕ := K.sup (fun S => hash_count_fully_occupied n r S t) have ht_pos : 0 < t := by omega have hc_nonneg : 0 ≤ c := by have ht_pos_real : (0 : ℝ) < (t : ℝ) := by positivity have hn_pos_real : (0 : ℝ) < (n : ℝ) := by have : 0 < n := NeZero.pos n positivity have hkt_real : (k : ℝ) < (t : ℝ) := by exact_mod_cast hkt have h1 : (k : ℝ) / t < 1 := by rw [div_lt_iff₀ ht_pos_real] linarith have h2 : 0 ≤ (k : ℝ) / n := by positivity change 0 ≤ 1 - (k : ℝ) / t + (k : ℝ) / n linarith have h_bound : (n : ℝ) * (M1 : ℝ) ≤ (M2 : ℝ) * c := by by_cases hK : K.Nonempty · obtain ⟨S_max, hS_max_mem, hS_max_eq⟩ := Finset.exists_mem_eq_sup K hK (fun S => hash_count_fully_occupied n r S (t - 1)) have hS_card : S_max.card = k := (Finset.mem_filter.mp hS_max_mem).2 have hF_max := hF S_max hS_card have hS_le : hash_count_fully_occupied n r S_max t ≤ M2 := Finset.le_sup (f := fun S => hash_count_fully_occupied n r S t) hS_max_mem have hS_le_real : (hash_count_fully_occupied n r S_max t : ℝ) ≤ (M2 : ℝ) := by exact_mod_cast hS_le have h_mul_le : (hash_count_fully_occupied n r S_max t : ℝ) * c ≤ (M2 : ℝ) * c := mul_le_mul_of_nonneg_right hS_le_real hc_nonneg have hM1_eq : M1 = hash_count_fully_occupied n r S_max (t - 1) := hS_max_eq rw [hM1_eq] exact le_trans hF_max h_mul_le · have hK_empty : K = ∅ := Finset.not_nonempty_iff_eq_empty.mp hK have hM1_zero : M1 = 0 := by change (K.sup (fun S => hash_count_fully_occupied n r S (t - 1))) = 0 rw [hK_empty] rfl have hM2_zero : M2 = 0 := by change (K.sup (fun S => hash_count_fully_occupied n r S t)) = 0 rw [hK_empty] rfl rw [hM1_zero, hM2_zero] simp only [Nat.cast_zero, mul_zero, zero_mul, le_refl] -- Now algebraic deduction have hn_pos : (0 : ℝ) < (n : ℝ) := by have : 0 < n := NeZero.pos n positivity have hnt_pos : (0 : ℝ) < (n : ℝ) ^ (t - 1) := by positivity have ht_eq : (n : ℝ) ^ t = (n : ℝ) ^ (t - 1) * (n : ℝ) := by have : t = (t - 1) + 1 := (Nat.sub_add_cancel (Nat.succ_le_of_lt ht_pos)).symm nth_rw 1 [this] rw [pow_succ] change (M1 : ℝ) / (n : ℝ) ^ (t - 1) ≤ ((M2 : ℝ) / (n : ℝ) ^ t) * c rw [ht_eq] have h_prod_pos : 0 < (n : ℝ) ^ (t - 1) * (n : ℝ) := mul_pos hnt_pos hn_pos have h_rw1 : (M1 : ℝ) / (n : ℝ) ^ (t - 1) = ((n : ℝ) * (M1 : ℝ)) / ((n : ℝ) ^ (t - 1) * (n : ℝ)) := by have h_cancel := (mul_div_mul_right (M1 : ℝ) ((n : ℝ) ^ (t - 1)) (ne_of_gt hn_pos)).symm rw [mul_comm (M1 : ℝ) (n : ℝ)] at h_cancel exact h_cancel have h_rw2 : ((M2 : ℝ) / ((n : ℝ) ^ (t - 1) * (n : ℝ))) * c = ((M2 : ℝ) * c) / ((n : ℝ) ^ (t - 1) * (n : ℝ)) := by ring rw [h_rw1, h_rw2] exact div_le_div_of_nonneg_right h_bound (le_of_lt h_prod_pos)