AFTD Auto-Formalizing Theoretical Domains

hash_occupied_slots_nil

theoremverified

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.

  1. 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).

    line 3

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