hash_potential
For a table of size n, offset sequence r, slot subset S, target sequence length t, and prefix A, the potential hash_potential n r S t A is the expected number of slots in S occupied when A is extended by a uniform random suffix of length t - A.length.
Statement
noncomputable def hash_potential (n : ℕ) [NeZero n] (r : Fin n → ZMod n) (S : Finset (ZMod n)) (t : ℕ) (A : List (ZMod n)) : ℝ
- Defined in
- arXiv:2610.31363 Section 4
- Verified
- 23 Oct 2026
- Axioms
- none listed
- Built on 1
- hash_occupy_countThe number of slots in S : Finset (ZMod n) that are occupied after inserting the list A : List (ZMod n) into an initially empty table of…
- Used by 2
- hash_potential_of_length_eqFor any sequence A of length t, the potential hash_potential n r S t A equals the number of slots in S occupied by A, hash_occupy_count n…
- hash_potential_deltaFor a table of size n, offset sequence r, slot subset S, target sequence length t, prefix A, and next element e, the step change…
Read back from the Lean
Given a natural number n with [NeZero n], a function r : Fin n → ZMod n, a finset S ⊆ ZMod n, a natural number t, and a list A of elements of ZMod n, hash_potential n r S t A is defined as the expected value (average) over all uniformly chosen sequences B : Fin (t - A.length) → ZMod n of the number of occupied slots in S after sequentially inserting the elements of A followed by B into an initially empty hash table of size n using probe offsets r. Formally, it is the sum over all B : Fin (t - A.length) → ZMod n of (hash_occupy_count n r S (A ++ List.ofFn B) : ℝ), divided by (n : ℝ) ^ (t - A.length).
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
/-- Potential function phi(A) defined as the average occupancy of S after completing prefix A with a random suffix. -/ noncomputable def hash_potential (n : ℕ) [NeZero n] (r : Fin n → ZMod n) (S : Finset (ZMod n)) (t : ℕ) (A : List (ZMod n)) : ℝ := (∑ B : Fin (t - A.length) → ZMod n, (hash_occupy_count n r S (A ++ List.ofFn B) : ℝ)) / (n : ℝ) ^ (t - A.length)