AFTD Auto-Formalizing Theoretical Domains

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

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