AFTD Auto-Formalizing Theoretical Domains

group_hash_probe_tail_count_zero_tail

theoremverified

For any finite group G with decidable equality, table size n : ℕ, offset sequence r : Fin n → G, and insertion length t : ℕ, the probe tail count group_hash_probe_tail_count G n r t 0 is equal to (Fintype.card G) ^ (t + 1).

Statement

theorem group_hash_probe_tail_count_zero_tail (G : Type*) [Group G] [Fintype G] [DecidableEq G]
    (n : ℕ) (r : Fin n → G) (t : ℕ) :
    group_hash_probe_tail_count G n r t 0 = (Fintype.card G) ^ (t + 1)
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 2
  • 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…

Read back from the Lean

For any finite group G with decidable equality, any natural number n, any function r : Fin n → G, and any natural number t, the quantity group_hash_probe_tail_count G n r t 0 is equal to (Fintype.card G) ^ (t + 1).

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 0 measures the number of insertion histories and query keys for which the first 0 probe positions are occupied. Because the requirement for indices j < 0 has an impossible premise, it holds vacuously for all keys and insertion sequences. The filtered set is therefore the entire universal set of pairs in (Fin t → G) × G, whose cardinality is |G|^t · |G| = |G|^(t + 1).

  1. The condition defining the probe tail count simplifies to a vacuously true statement for all pairs of insertion histories and query keys.

    Unfolding `group_hash_probe_tail_count` expresses the quantity as the cardinality of a filtered subset of pairs (A, q) ∈ (Fin t → G) × G. The filtering condition specifies that for every probe index j : Fin n, if j < 0 then the j-th probe is occupied. Since no natural number is strictly less than 0 (`Nat.not_lt_zero`), the premise is false, so the implication is vacuously true (`false_implies`), reducing the filter condition to `∀ j, True`.

    lines 5–6

    uses Nat.not_lt_zero, false_implies

      unfold group_hash_probe_tail_count
      simp only [Nat.not_lt_zero, false_implies]
  2. Filtering by a universally true condition reduces the set to the full universal set, leaving the cardinality computation and the universal validity as subgoals.

    By `Finset.filter_true_of_mem`, filtering a finite set by a predicate that holds everywhere returns the set itself. Here, this replaces the filtered set with `Finset.univ`, leaving two subgoals: computing the cardinality of `Finset.univ` and verifying that the condition `∀ j, True` holds for every element.

    line 7

    uses Finset.filter_true_of_mem

      rw [Finset.filter_true_of_mem]
  3. The cardinality of the universal set of pairs in (Fin t → G) × G is |G|^(t + 1).

    By `Finset.card_univ`, the size of `Finset.univ` is the cardinality of the product type (Fin t → G) × G. Using `Fintype.card_prod` and `Fintype.card_fun`, this factors as |G|^|Fin t| * |G| = |G|^t * |G|. Rewriting with `pow_succ` and commutativity of multiplication (`mul_comm`) simplifies this to |G|^(t + 1), completing the main equality.

    lines 8–9

    uses Finset.card_univ, Fintype.card_prod, Fintype.card_fun, pow_succ, mul_comm

      · rw [Finset.card_univ, Fintype.card_prod, Fintype.card_fun]
        simp [pow_succ, mul_comm]
  4. The filter condition holds for every element of the universal set.

    For any element x in the universal set and any index j : Fin n, the statement to check is simply `True`, which holds trivially.

    line 10

      · intro x _; simp
Nat.not_lt_zero
No natural number is strictly less than 0.
false_implies
An implication whose premise is false is logically equivalent to true.
Finset.filter_true_of_mem
Filtering a finite set by a predicate that holds for all of its members leaves the set unchanged.
Finset.card_univ
The cardinality of the universal finset of a finite type is the cardinality of the type itself.
Fintype.card_prod
The cardinality of a product type α × β is the product of the cardinalities of α and β.
Fintype.card_fun
The cardinality of the function type α → β is the cardinality of β raised to the cardinality of α.
pow_succ
For any element a and natural number n, a^(n + 1) = a^n * a.
mul_comm
Multiplication is commutative: a * b = b * a.

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 threshold 0 equals the total number of insertion histories and query keys. -/theorem group_hash_probe_tail_count_zero_tail (G : Type*) [Group G] [Fintype G] [DecidableEq G]    (n : ℕ) (r : Fin n → G) (t : ℕ) :    group_hash_probe_tail_count G n r t 0 = (Fintype.card G) ^ (t + 1) := by  unfold group_hash_probe_tail_count  simp only [Nat.not_lt_zero, false_implies]  rw [Finset.filter_true_of_mem]  · rw [Finset.card_univ, Fintype.card_prod, Fintype.card_fun]    simp [pow_succ, mul_comm]  · intro x _; simp
See it in the graphDiscuss this resultChallenge it