hash_potential_of_length_eq
For 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 r S A.
Statement
theorem hash_potential_of_length_eq (n : ℕ) [NeZero n] (r : Fin n → ZMod n)
(S : Finset (ZMod n)) (t : ℕ) (A : List (ZMod n)) (hA : A.length = t) :
hash_potential n r S t A = hash_occupy_count n r S A- Formalizes
- arXiv:2610.31363 Lemma 4.2
- Verified
- 24 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- hash_potentialFor 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…
- 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…
Read back from the Lean
For any positive integer $n$ (given by [NeZero n]), function $r : Fin n \to ZMod n$, subset $S : Finset (ZMod n)$, natural number $t$, and list $A : List (ZMod n)$ such that the length of $A$ equals $t$, the hash potential hash_potential n r S t A equals the hash occupancy count hash_occupy_count n r S A (coerced to a real number).
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 potential `hash_potential n r S t A` is defined as the expected number of slots in `S` occupied after completing `A` to a sequence of length `t`. When `A` already has length `t`, the completion length $t - |A|$ is zero, so the only completion is the empty sequence. Consequently, the sum over completions reduces to the single term for `A`, the normalization factor $n^0$ equals $1$, and the potential simplifies directly to the occupancy count `hash_occupy_count n r S A`.
The potential `hash_potential n r S t A` of a sequence `A` of length `t` equals its actual occupancy count `hash_occupy_count n r S A`. automation
By definition, `hash_potential n r S t A` is the sum of `hash_occupy_count n r S (A ++ List.ofFn B)` over all completions $B : \mathrm{Fin}(t - |A|) \to \mathbb{Z}/n\mathbb{Z}$, divided by $n^{t - |A|}$. The hypothesis `hA` states that $|A| = t$, so the remaining length $t - |A|$ is $0$. There is only one function from $\mathrm{Fin}(0)$ to $\mathbb{Z}/n\mathbb{Z}$ (the empty tuple), whose corresponding list is empty, giving $A ++ [] = A$. The sum thus collapses to the single term `hash_occupy_count n r S A`, and the denominator $n^0$ evaluates to $1$. The simplifier carries out these reductions and closes the goal.
simp [hash_potential, hA]
- The `simp` tactic closes the goal in one step by unfolding the definition of `hash_potential`, substituting `hA`, and evaluating several algebraic and list simplifications: $t - t = 0$, the sum over the unique function `Fin 0 → ZMod n`, the list concatenation $A ++ [] = A$, and the division by $n^0 = 1$.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- Sanity lemma and Lemma 4.2 (1): potential of a full-length sequence is its actual occupancy. -/theorem hash_potential_of_length_eq (n : ℕ) [NeZero n] (r : Fin n → ZMod n) (S : Finset (ZMod n)) (t : ℕ) (A : List (ZMod n)) (hA : A.length = t) : hash_potential n r S t A = hash_occupy_count n r S A := by simp [hash_potential, hA]