AFTD Auto-Formalizing Theoretical Domains

hash_probe_tail_count

def

The number of pairs of an insertion sequence of length t and an additional query slot whose insertion cost under offset sequence r strictly exceeds k, meaning the first k probed slots are all occupied.

Statement

def hash_probe_tail_count (n : ℕ) [NeZero n] (r : Fin n → ZMod n) (t k : ℕ) : ℕ
Defined in
arXiv:2610.31363, Section 2
Verified
01 Nov 2026
Axioms
none listed
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 15

Read back from the Lean

For a positive natural number n (with instance [NeZero n]), a probe offset function r : Fin n → ZMod n, and natural numbers t and k, hash_probe_tail_count n r t k is defined as the cardinality of the set of pairs (seq, x) ∈ (Fin t → ZMod n) × ZMod n such that for every probe index j : Fin n with j.val < k, the slot x + r j belongs to hash_occupied_slots n r (List.ofFn seq).

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

/-- Number of insertion-query pairs requiring strictly more than k probes. -/
def hash_probe_tail_count (n : ℕ) [NeZero n] (r : Fin n → ZMod n) (t k : ℕ) : ℕ :=
  (Finset.univ.filter (fun (p : (Fin t → ZMod n) × ZMod n) =>
    ∀ j : Fin n, j.val < k → p.2 + r j ∈ hash_occupied_slots n r (List.ofFn p.1))).card
See it in the graphDiscuss this resultChallenge it