flag_hash_offset_zero
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.
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.
uses
reps.zerosimp [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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- 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]