(6): , , and the split
ProvedBddExp3SUM.eq_63sumabelian-groupsp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1randomized-algorithms
For every choice of rows, if then lies in
Moreover as groups, , and splits as with and : every element of is uniquely .
This fixes the explicit middle group over which the support matrices are built.
Differences from the source:
- generalization: k, q, e, p from the certificate of a fixed subinstance → any k, q, e and any prime p ∣ M; reason: the claim is algebra about rows; the source’s parameters are a special case
- encoding: B = B₁ × B₂ → two subgroups of B with the given cardinalities and unique decomposition; reason: makes (µ₁, 0) and (0, µ₂) plain elements of the target of K
Preamble
import Mathlib import Definitions.Def_BddExp3SUM_Hash
Formal statement
namespace BddExp3SUM
/-- (6), p.4 (Zeng, Wang, Cao, Dai, Wang, STOC 2027 submission, manuscript sha256 19546c9a…):
`K(ker π) ⊆ B ≅ F_p^q`, `|B| = D = p^q`, and the split `B = B₁ × B₂` with dimensions `⌈q/2⌉`, `⌊q/2⌋`.
**Formalization Note.** `M/p` may be `1`, in which case `ZMod (M/p)` is the trivial ring. The split is
stated as: `B₁`, `B₂` have the right cardinalities, and each element of `B` is uniquely `μ₁ + μ₂`. -/
theorem eq_6 {M r e k q p : ℕ} [NeZero M] (hp : p.Prime) (hpM : p ∣ M)
(u : Fin (k + q) → Grp M r) :
(∀ x : Grp M r, piHash hpM e u x = 0 → KHash e u x ∈ B M r e k q p) ∧
Nonempty (B M r e k q p ≃+ (Fin q → ZMod p)) ∧
Nat.card (B M r e k q p) = p ^ q ∧
Nat.card (B₁ M r e k q p) = p ^ ((q + 1) / 2) ∧
Nat.card (B₂ M r e k q p) = p ^ (q / 2) ∧
∀ w ∈ B M r e k q p, ∃! v : (B₁ M r e k q p) × (B₂ M r e k q p), (v.1 : KTarget M r e k q) + v.2 = w := 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…), (6), p.4 (PDF p.5; the sentence starts on PDF p.4)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.