AFTD Auto-Formalizing Theoretical Domains

hash_potential_of_length_eq

theoremverifiedformalization

For any sequence A of length t, the potential hash_potential n r S t A equals the number of slots in S occupied by A, hash_occupy_count n r S A.

Statement

theorem hash_potential_of_length_eq (n : ℕ) [NeZero n] (r : Fin n → ZMod n)
    (S : Finset (ZMod n)) (t : ℕ) (A : List (ZMod n)) (hA : A.length = t) :
    hash_potential n r S t A = hash_occupy_count n r S A
Formalizes
arXiv:2610.31363 Lemma 4.2
Verified
24 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • hash_potentialFor a table of size n, offset sequence r, slot subset S, target sequence length t, and prefix A, the potential hash_potential n r S t A is…
  • 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…

Read back from the Lean

For any positive integer $n$ (given by [NeZero n]), function $r : Fin n \to ZMod n$, subset $S : Finset (ZMod n)$, natural number $t$, and list $A : List (ZMod n)$ such that the length of $A$ equals $t$, the hash potential hash_potential n r S t A equals the hash occupancy count hash_occupy_count n r S A (coerced to a real number).

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 potential `hash_potential n r S t A` is defined as the expected number of slots in `S` occupied after completing `A` to a sequence of length `t`. When `A` already has length `t`, the completion length $t - |A|$ is zero, so the only completion is the empty sequence. Consequently, the sum over completions reduces to the single term for `A`, the normalization factor $n^0$ equals $1$, and the potential simplifies directly to the occupancy count `hash_occupy_count n r S A`.

  1. The potential `hash_potential n r S t A` of a sequence `A` of length `t` equals its actual occupancy count `hash_occupy_count n r S A`. automation

    By definition, `hash_potential n r S t A` is the sum of `hash_occupy_count n r S (A ++ List.ofFn B)` over all completions $B : \mathrm{Fin}(t - |A|) \to \mathbb{Z}/n\mathbb{Z}$, divided by $n^{t - |A|}$. The hypothesis `hA` states that $|A| = t$, so the remaining length $t - |A|$ is $0$. There is only one function from $\mathrm{Fin}(0)$ to $\mathbb{Z}/n\mathbb{Z}$ (the empty tuple), whose corresponding list is empty, giving $A ++ [] = A$. The sum thus collapses to the single term `hash_occupy_count n r S A`, and the denominator $n^0$ evaluates to $1$. The simplifier carries out these reductions and closes the goal.

    line 5

      simp [hash_potential, hA]

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

/-- Sanity lemma and Lemma 4.2 (1): potential of a full-length sequence is its actual occupancy. -/theorem hash_potential_of_length_eq (n : ℕ) [NeZero n] (r : Fin n → ZMod n)    (S : Finset (ZMod n)) (t : ℕ) (A : List (ZMod n)) (hA : A.length = t) :    hash_potential n r S t A = hash_occupy_count n r S A := by  simp [hash_potential, hA]
See it in the graphDiscuss this resultChallenge it