hash_count_fully_occupied
def
The 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.
Statement
def hash_count_fully_occupied (n : ℕ) [NeZero n] (r : Fin n → ZMod n) (S : Finset (ZMod n)) (t : ℕ) : ℕ- Defined in
- arXiv:2610.31363 Definition 3.2
- Verified
- 23 Oct 2026
- Axioms
- none listed
- Built on 1
- hash_fully_occupied_seqsThe set of sequences A : Fin t → ZMod n such that hash_occupy_count n r S (List.ofFn A) = S.card, filtering Finset.univ.
- Used by 2
- 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) ≤…
- 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
Given a positive natural number n, a function r : Fin n → ZMod n, a finite subset S : Finset (ZMod n), and a natural number t, hash_count_fully_occupied n r S t is the number of sequences (functions) A : Fin t → ZMod n such that hash_occupy_count n r S (List.ofFn A) = S.card.
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 count F_S(t) of length-t sequences fully occupying target slot set S. -/ def hash_count_fully_occupied (n : ℕ) [NeZero n] (r : Fin n → ZMod n) (S : Finset (ZMod n)) (t : ℕ) : ℕ := (hash_fully_occupied_seqs n r S t).card