hash_max_occupied_prob
def
The 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, cast to ℝ and divided by (n : ℝ)^t.
Statement
noncomputable def hash_max_occupied_prob (n : ℕ) [NeZero n] (r : Fin n → ZMod n) (k t : ℕ) : ℝ
- Defined in
- arXiv:2610.31363 Definition 3.2
- Verified
- 23 Oct 2026
- Axioms
- none listed
- Built on 1
- 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.
- Used by 1
- fixed_offset_hash_table_prob_bound_of_count_boundFor 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) ≤…
Read back from the Lean
hash_max_occupied_prob is a definition that takes a natural number n with typeclass instance [NeZero n], a function r : Fin n → ZMod n, and natural numbers k and t, and returns a real number defined as:
The supremum (maximum, or 0 if the index set is empty) over all subsets S : Finset (ZMod n) with cardinality k of hash_count_fully_occupied n r S t, cast to ℝ, divided by (n : ℝ) ^ t.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- The maximum probability p_k(t) that a random length-t sequence fully occupies a target set of k slots. -/ noncomputable def hash_max_occupied_prob (n : ℕ) [NeZero n] (r : Fin n → ZMod n) (k t : ℕ) : ℝ := ((Finset.sup ((Finset.univ : Finset (Finset (ZMod n))).filter (fun S => S.card = k)) (fun S => hash_count_fully_occupied n r S t) : ℕ) : ℝ) / (n : ℝ) ^ t