AFTD Auto-Formalizing Theoretical Domains

group_hash_probe_tail_count_t_zero_succ

theoremverified

For any finite group G with decidable equality, table size n : ℕ with 0 < n, offset sequence r : Fin n → G, and natural number c, the probe tail count when inserting into an empty table group_hash_probe_tail_count G n r 0 (c + 1) is equal to 0.

Statement

theorem group_hash_probe_tail_count_t_zero_succ (G : Type*) [Group G] [Fintype G] [DecidableEq G]
    (n : ℕ) (r : Fin n → G) (c : ℕ) (hn : 0 < n) :
    group_hash_probe_tail_count G n r 0 (c + 1) = 0
Source
arXiv:2610.31363: A Sharp Analysis of Fixed Offset Hash Tables, serving OP-808
Verified
02 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • group_hash_probe_tail_countGiven a finite group G with decidable equality, a table size n : ℕ, an offset sequence r : Fin n → G, and natural numbers t and c,…
  • group_hash_occupied_slotsThe set of occupied slots in Finset G after sequentially inserting a list of keys A : List G into an initially empty hash table on group G…
  • group_hash_insert_stepGiven a group G with decidable equality, table size n, offset sequence r : Fin n → G, a finite set of occupied slots T : Finset G, and key…

Read back from the Lean

For any finite group $G$ with decidable equality, any natural number $n$, any probe sequence $r : \mathrm{Fin}\ n \to G$, and any natural number $c$, if $0 < n$, then group_hash_probe_tail_count G n r 0 (c + 1) = 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 probe tail count for threshold c + 1 counts the number of pairs (A, q) of an insertion sequence of length t and a query element q whose first c + 1 probes all hit occupied slots. When t = 0, no elements have been inserted, so the table has no occupied slots. Because c + 1 > 0, the condition requires the 0-th probe to hit an occupied slot, which is impossible in an empty table; hence no such pairs exist and the count is 0.

  1. The probe tail count is zero if and only if no configuration (A, q) satisfies the condition that its first c + 1 probe slots are occupied.

    Unfolding `group_hash_probe_tail_count`, the tail count is defined as the cardinality of the filtered set of pairs (A, q) whose first c + 1 probes hit occupied slots. A finite set has cardinality zero if and only if it is empty (`Finset.card_eq_zero`), and a filtered set is empty if and only if no element satisfies the filtering condition (`Finset.filter_eq_empty_iff`).

    lines 5–6

    uses Finset.card_eq_zero, Finset.filter_eq_empty_iff

      unfold group_hash_probe_tail_count
      simp only [Finset.card_eq_zero, Finset.filter_eq_empty_iff]
  2. Assuming such a pair (A, q) exists, its initial probe slot q * r(0) must be occupied in the hash table.

    Assume for contradiction that there is a pair x = (A, q) satisfying the probe condition h. Because the table size n is positive (0 < n), index 0 is a valid table slot index ⟨0, hn⟩ ∈ Fin n. Since the probe threshold c + 1 is positive (0 < c + 1 by `Nat.succ_pos`), instantiating h at index 0 implies that the 0-th probe slot q * r(0) must be in the set of occupied slots.

    lines 7–8

    uses Nat.succ_pos

      intro x hx h
      have hmem := h ⟨0, hn⟩ (Nat.succ_pos c)
  3. A contradiction is reached because an empty table has no occupied slots. automation

    The table has length t = 0, so the sequence of inserted elements A : Fin 0 → G forms an empty list List.ofFn A. By definition of `group_hash_occupied_slots`, an empty list leaves the set of occupied slots empty (∅). The derived membership q * r(0) ∈ ∅ simplifies to False, closing the goal.

    line 9

      simp [group_hash_occupied_slots] at hmem
Finset.card_eq_zero
A finite set has cardinality 0 if and only if it is the empty set.
Finset.filter_eq_empty_iff
Filtering a finite set by a predicate yields the empty set if and only if no element of the set satisfies the predicate.
Nat.succ_pos
The successor of any natural number is strictly positive (0 < n + 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

/-- The probe tail count for positive threshold when inserting into an empty table is 0. -/theorem group_hash_probe_tail_count_t_zero_succ (G : Type*) [Group G] [Fintype G] [DecidableEq G]    (n : ℕ) (r : Fin n → G) (c : ℕ) (hn : 0 < n) :    group_hash_probe_tail_count G n r 0 (c + 1) = 0 := by  unfold group_hash_probe_tail_count  simp only [Finset.card_eq_zero, Finset.filter_eq_empty_iff]  intro x hx h  have hmem := h ⟨0, hn⟩ (Nat.succ_pos c)  simp [group_hash_occupied_slots] at hmem
See it in the graphDiscuss this resultChallenge it