AFTD Auto-Formalizing Theoretical Domains

flag_hash_offset_zero

theoremverified

For any group G, natural number k, prime quotient orders p : Fin k → ℕ, prime composition series series : GroupPrimeCompositionSeries G k p, and flag representatives reps : FlagRepresentatives series, the offset flag_hash_offset reps ⟨0, Finset.prod_pos fun i _ => (series.prime i).pos⟩ is equal to 1.

Statement

theorem flag_hash_offset_zero {G : Type*} [Group G] {k : ℕ} {p : Fin k → ℕ}
    {series : GroupPrimeCompositionSeries G k p} (reps : FlagRepresentatives series) :
    flag_hash_offset reps ⟨0, Finset.prod_pos fun i _ => (series.prime i).pos⟩ = 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 3
  • GroupPrimeCompositionSeriesA prime composition series of length k for group G with prime quotient orders p : Fin k → ℕ is a chain of subgroups H_0 = ⊥ ≤ ... ≤ H_k =…
  • FlagRepresentativesFor a prime composition series series, FlagRepresentatives bundles a family of group elements g : (i : Fin k) → Fin (p i) → G such that…
  • flag_hash_offsetGiven a group G, a natural number k, prime quotient orders p : Fin k → ℕ, a prime composition series series : GroupPrimeCompositionSeries…

Read back from the Lean

For any group $G$, natural number $k$, sequence of natural numbers $p : \mathrm{Fin}\ k \to \mathbb{N}$, prime composition series series of $G$ with indices $p$, and choice of flag representatives reps for series: the flag hash offset of reps evaluated at $0$ (as an element of $\mathrm{Fin}\left(\prod_{i : \mathrm{Fin}\ k} p\ i\right)$, with $0 < \prod_{i : \mathrm{Fin}\ k} p\ i$ witnessed by the positivity of the primes $p\ i$) is equal to the identity element $1 \in G$.

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 0-th offset in the flag hash sequence corresponds to the index 0 in the mixed-radix representation. Each digit in this expansion is 0, so every factor in the product defining the offset is the representative of 0, which is the group identity by the definition of flag representatives. The product of identity elements evaluates to 1.

  1. The 0-th flag hash offset is the group identity 1. automation

    Unfolding the definition of `flag_hash_offset` at index 0 shows that every mixed-radix digit is (0 / ...) % p i = 0. By `reps.zero`, the representative element for digit 0 at each stage is 1. The total offset is the product of these identity elements, which simplifies to 1.

    line 5

    uses reps.zero

      simp [flag_hash_offset, reps.zero]
reps.zero
The representative element chosen for the index 0 at each level i of the composition series is the group identity 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 0-th offset in a solvable group flag hash sequence is the group identity. -/theorem flag_hash_offset_zero {G : Type*} [Group G] {k : ℕ} {p : Fin k → ℕ}    {series : GroupPrimeCompositionSeries G k p} (reps : FlagRepresentatives series) :    flag_hash_offset reps ⟨0, Finset.prod_pos fun i _ => (series.prime i).pos⟩ = 1 := by  simp [flag_hash_offset, reps.zero]
See it in the graphDiscuss this resultChallenge it