AFTD Auto-Formalizing Theoretical Domains

fixed_offset_hash_table_prob_bound_of_count_bound

theoremverified

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.

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

    lines 10–15

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

    lines 16–28

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

    lines 29–54

    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_refl

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

    lines 56–63

    uses NeZero.pos, Nat.sub_add_cancel, Nat.succ_le_of_lt, pow_succ

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

    lines 64–74

    uses mul_pos, mul_div_mul_right, ne_of_gt, mul_comm, div_le_div_of_nonneg_right, le_of_lt

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

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

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