hash_occupied_slots_nil
For any n and offset sequence r : Fin n → ZMod n, hash_occupied_slots n r [] = ∅.
Statement
theorem hash_occupied_slots_nil (n : ℕ) (r : Fin n → ZMod n) :
hash_occupied_slots n r [] = ∅- Source
- arXiv:2610.31363 Section 2
- Verified
- 23 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- hash_occupied_slotsThe set of occupied slots in Finset (ZMod n) after sequentially inserting a list A : List (ZMod n) into an initially empty hash table of…
- Used by 4
- hash_occupy_count_nilFor any n, r : Fin n → ZMod n, and S : Finset (ZMod n), hash_occupy_count n r S [] = 0.
- hash_occupied_slots_cardFor any table size n with [NeZero n], any bijective offset sequence r : Fin n → ZMod n, and any list of keys A with length at most n, the…
- hash_probe_expected_cost_zeroFor any table size n with [NeZero n] and any offset sequence r : Fin n → ZMod n, the expected probe cost hash_probe_expected_cost n r 0…
- hash_probe_expected_cost_twoAfter two insertions the expected cost is 1+2/n+(3+[2r₁=0])/n².
Read back from the Lean
For every natural number $n$ and every function $r : \text{Fin } n \to \mathbb{Z}/n\mathbb{Z}$, the set of occupied slots resulting from hashing the empty list of elements, $\mathrm{hash\_occupied\_slots}(n, r, [])$, is the empty set $\emptyset$.
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 claim holds directly by definition: folding over an empty list leaves the initial empty set `∅` unchanged, so the result is true by reflexivity.
The set of occupied slots after inserting an empty list of elements is the empty set.
By definition, `hash_occupied_slots n r []` evaluates to `[].foldl (hash_insert_step n r) ∅`, which reduces immediately to `∅` by the definition of `List.foldl` on an empty list. Hence the equality holds definitionally (by reflexivity).
hash_occupied_slots n r [] = ∅ := rfl
Written by a model (gemini-3.8-flash) from the Lean source alone (no goal states were available). Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
/-- Inserting an empty sequence results in no occupied slots. -/theorem hash_occupied_slots_nil (n : ℕ) (r : Fin n → ZMod n) : hash_occupied_slots n r [] = ∅ := rfl