Lemma 2: , at most represented cosets, and
ProvedBddExp3SUM.lemma_23sumabelian-groupsp2o-gran-per-chapterp2o-plan-paperp2o-v1randomized-algorithms
For a fixed subinstance and each :
- the number of triples in with sum in satisfies ;
- the number of -cosets represented in is at most .
Moreover
Here is computed from the original list , not from . The first clause controls false positives of every sum order; the second controls the number of hash classes.
Formalization Note The standing assumptions of p.2 are collected in the structure Subinst.
Differences from the source:
- encoding: s_{i,d}, constant on U_i → the supremum of s_{i,d}(x) over x ∈ U_i (sVal); reason: U_i is nonempty and the value is constant on it, so the two agree (proved in the sanity file)
Preamble
import Mathlib import Definitions.Def_BddExp3SUM_Profiles
Formal statement
namespace BddExp3SUM
/-- Lemma 2, p.3 (Zeng, Wang, Cao, Dai, Wang, STOC 2027 submission, manuscript sha256 19546c9a…).
**Formalization Note.** `c` and `s` count in the original lists `S i`; `T_d` and the represented cosets
are in the subinstance `U i`. All divisions are in `ℝ`. -/
theorem lemma_2 {M r n : ℕ} {S U : Fin 3 → Finset (Grp M r)} (h : Subinst M r n S U) :
(∀ d ∈ Dvs M,
((countIn U d : ℝ) < 2 * sMin S U d * (n : ℝ) ^ 2) ∧
∀ i, (cosetsRepresented (U i) d : ℝ) ≤ (n : ℝ) / sVal S U i d ∧
(n : ℝ) / sVal S U i d ≤ (n : ℝ) / sMin S U d) ∧
√(n : ℝ) / 2 < sMin S U M ∧ (n : ℝ) ^ ((1 : ℝ) / 4) ≤ √(n : ℝ) / 2 := 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 2, p.3 (PDF p.4)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.