Lemma 3: fewer than nonempty -classes, and at most blocks
ProvedBddExp3SUM.lemma_33sumabelian-groupsp2o-gran-per-chapterp2o-plan-paperp2o-v1randomized-algorithms
For a fixed subinstance with its certificate and for every choice of rows, each has fewer than
nonempty -classes. Cutting each class into blocks of size at most gives at most blocks.
The first bound is the class bound supplied by the single divisor ; it is independent of the rows.
Differences from the source:
- reading: "Cutting each such class into blocks of size at most σ" → a class of size a is cut into exactly ⌈a/σ⌉ blocks (IsBlockCut); reason: the bound is false for an arbitrary partition into small pieces (singletons give |U_i| blocks); the proof bounds the number of blocks by "the number of classes plus |U_i|/σ", which is this cut
Preamble
import Mathlib import Definitions.Def_BddExp3SUM_Blocks
Formal statement
namespace BddExp3SUM
/-- Lemma 3, p.4 (Zeng, Wang, Cao, Dai, Wang, STOC 2027 submission, manuscript sha256 19546c9a…).
**Formalization Note.** "Cutting each such class into blocks of size at most σ" is `IsBlockCut`: a
class of size `a` is cut into exactly `⌈a/σ⌉` blocks. -/
theorem lemma_3 {M r n k q e p : ℕ} {S U : Fin 3 → Finset (Grp M r)}
(h : Cert M r n S U k q e p) (u : Fin (k + q) → Grp M r) (i : Fin 3) :
(classCount (U i) (piHash h.p_dvd e u) : ℝ) < (M : ℝ) ^ 2 * n / σ M n ∧
∀ parts : Finset (Finset (Grp M r)), IsBlockCut (piHash h.p_dvd e u) (U i) (σ M n) parts →
(parts.card : ℝ) ≤ ((M : ℝ) ^ 2 + 1) * n / σ M n := by sorry
end BddExp3SUM
Source
Zeng, Wang, Cao, Dai, Wang, Truly Subquadratic 3SUM over Every Bounded-Exponent Abelian Group, STOC 2027 submission (manuscript sha256 19546c9a…), Lemma 3, p.4 (PDF p.5)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.