hash_occupy_count_nil
For any n, r : Fin n → ZMod n, and S : Finset (ZMod n), hash_occupy_count n r S [] = 0.
Statement
theorem hash_occupy_count_nil (n : ℕ) (r : Fin n → ZMod n) (S : Finset (ZMod n)) :
hash_occupy_count n r S [] = 0- Source
- arXiv:2610.31363 Definition 3.1
- Verified
- 23 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- 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…
- hash_occupied_slots_nilFor any n and offset sequence r : Fin n → ZMod n, hash_occupied_slots n r [] = ∅.
- 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…
Read back from the Lean
For every natural number n, probe offset function r : Fin n → ZMod n, and finite subset S ⊆ ZMod n, the count of occupied slots belonging to S after processing an empty list of keys (hash_occupy_count n r S []) is 0.
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 proof proceeds by unfolding the definition of hash_occupy_count and simplifying. By hash_occupied_slots_nil, the set of occupied slots for an empty sequence is the empty set. Its intersection with $S$ is therefore empty, which has cardinality zero.
$\mathrm{hash\_occupy\_count}(n, r, S, []) = 0$
Unfolding $\mathrm{hash\_occupy\_count}$ expresses the count as $| \mathrm{hash\_occupied\_slots}(n, r, []) \cap S |$. Applying $\mathrm{hash\_occupied\_slots\_nil}$ simplifies the occupied set to $\emptyset$. The simplifier then evaluates $|\emptyset \cap S| = |\emptyset| = 0$.
uses
hash_occupy_count,hash_occupied_slots_nilsimp [hash_occupy_count, hash_occupied_slots_nil]
hash_occupy_count- the number of occupied slots in $S$ after inserting list $A$, defined as $| \mathrm{hash\_occupied\_slots}(n, r, A) \cap S |$
hash_occupied_slots_nil- the set of occupied slots after inserting an empty list is the empty set $\emptyset$
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.
/-- Occupy count of an empty sequence is zero. -/theorem hash_occupy_count_nil (n : ℕ) (r : Fin n → ZMod n) (S : Finset (ZMod n)) : hash_occupy_count n r S [] = 0 := by simp [hash_occupy_count, hash_occupied_slots_nil]