Every structure we found yielded a subquadratic algorithm. What survived was pseudorandomness itself.
Bottom Line Up Front
3SUM — given n integers, do any three sum to zero? — has a textbook O(n²) solution and a famous conjecture that you cannot do meaningfully better. Over one long evening we ran five experiments in TypeScript trying to beat that wall from every angle we could think of: convolution, randomization, spectral tricks, lattice structure, and finally the Hardy–Littlewood circle method.
We beat n² in every structured regime we tested, sometimes by 40×. And every win traced back to the same object: a large Fourier coefficient. What remained at the end — the instances no trick could touch — were exactly the Fourier-flat ones, where a rigorous certificate proves the answer is already forced to its random-model value. The wall is real, but it is not a wall around a puzzle about triples. It is a wall around pseudorandomness.
Everything below is implemented, verified against brute force, and benchmarked. All numbers are real measured results. A note on novelty up front: the mathematical ingredients — FFT counting, Freiman-type structure, Parseval bounds, the circle method — are known to their respective fields. What we have not seen elsewhere is the end-to-end executable synthesis: a router that walks the structure hierarchy, and a certificate that reports, with proof, when it has run out of structure.
The Convolution Baseline, and the First Wall
For values bounded by u, 3SUM is a convolution. Build a histogram polynomial f(x); the coefficient of x^(3u) in f³ counts solutions, after an inclusion–exclusion step (C₃ − 3C₂ + 2C₁, then ÷6) strips out triples that reuse an index. FFT computes this in O(u log u), independent of n. On worst-case no-solution instances, with four algorithms all verified against brute force first, the crossovers were sharp: FFT wins when the value range is small (4.4ms vs 6.5ms at u = 10³), and loses badly when it is not (514ms vs 8.2ms at u = 10⁵).
The most instructive result was a negative one. Randomized universe reduction — hash every value mod a random prime p ≈ 4n², solve in the compressed universe, verify candidates — works correctly, and makes u = 10⁹ tractable where a dense FFT would need two billion bins. But it lands at Θ(n² log n): slower than the wall it was built to break, 12.6 seconds against two-pointer's 8ms at n = 2000.
The lesson generalizes. Hashing can compress the universe, but never below ~n² — below that, residue pair-sums saturate and every element becomes a candidate. And convolving an n²-sized universe already costs n². Randomization removed the dependence on u and slammed into the convolution wall from the other side. You beat n² exactly when n² ≫ u, and never otherwise by this route.
The Spectral Reframe: Nine Transforms Become Two, Then One
The first real gain came from a reframing. 3SUM-to-zero is a sumset overlap — does (A+A) intersect −A? — and the count is a correlation at lag zero. Two consequences fall out. First, we never need the full cubed polynomial, only one coefficient, and one coefficient of a product is one bin of an inverse transform. Second, the index-reuse correction polynomial g(x) = f(x²) has spectrum G[k] = F[2k mod N], readable directly off the forward transform. One forward FFT, a pointwise combination K = F³ − 3GF, one inverse, one bin: two transforms instead of nine. Measured: 4–9× across every universe size.
Symmetry then halved it again. The histogram is real, so the spectrum is conjugate-symmetric; packing even and odd samples into a half-size complex FFT (the classic rfft trick) computes the forward transform at half cost, and since only one output bin is wanted, the inverse FFT can be replaced entirely by an O(N/2) dot product. One half-size transform, total. Another 2.9×, compounding to roughly 13× over the original pipeline — 1,636ms down to 123ms at u = 3×10⁵. That is the floor for this approach; there is nothing left to remove.
Affine Structure: The Certificate and the Lattice
Generalizing gcd produced the evening's first genuine surprise. If the input sits on a lattice, A ⊂ {v₀ + d·m}, then a+b+c = 0 forces Σm = −3v₀/d — and if d does not divide 3v₀, that is not an integer, so the answer is NO, certified in O(n) with no search at all. Otherwise the effective universe is the lattice length, not the magnitude: values near 10⁹ on a d = 21,000 lattice collapsed to L ≈ 80K, and the router counted 6.3 million triples in 12ms against two-pointer's 555ms at n = 16,000 — 44×, with the gap doubling every time n does.
Two things fell out of this that we did not plan. Target 0 is special: because zero is scale-invariant, a lattice offset almost always certifies infeasibility, so feasible structured instances are essentially gcd-lattices up to a factor of three. And our own worst-case generator from the first experiment — values ≡ 1 mod 4, chosen to force full execution — turned out to be affinely trivial. The certificate kills it in 0.03ms while the oblivious FFT burns 57ms. The benchmark we had trusted was soft, and the next tool we built is what told us so.
Rank Two: Generalized Arithmetic Progressions
Freiman's theorem says sets with small doubling |A+A|/|A| live inside generalized APs: {v₀ + d₁m₁ + d₂m₂ + ...}. Rank one was a gcd pass. Rank two is where detection becomes a real problem — and where the solver picked up a trick worth stating on its own.
Write each value as v = v₀ + a + D·b. Triple sums then satisfy a single linear Diophantine equation, Σa + D·Σb = T, with O(1) valid coordinate pairs when D > 3A. Embed (a, b) ↦ a + (3A+1)·b — a positional number system in which three-element sums cannot carry between digits — and the two-dimensional problem collapses back into the one-dimensional spectral engine, over a universe of ~9AB cells, regardless of how large the raw values are.
The detector, and an instructive bug
Detection used a planted-regime heuristic: cluster sorted residuals by a gap-size elbow, regress cluster starts for D, refine by scoring the bounding-box area. The first version had a bug worth reporting: centered data wraps around the residue circle mod D, so linear min/max scoring saw a spread of ~D and rejected the true lattice — while, remarkably, the counts stayed correct, because the Diophantine solver is exact for any D, right or wrong. The fix, scoring residues as the smallest covering arc on the circle, is a miniature of what makes real GAP recovery hard.
Final numbers: on values spanning 249 million hiding a 250×250 box (a ~4,000× compression), the detector recovered D = 1,000,003 exactly at every n; at n = 32,000 the router counted 49.1 million triples in 142ms against two-pointer's 1,844ms — 13×, scaling flat while the wall scales quadratically. The control, genuinely random instances, never triggered a false detection. All the difficulty of the Freiman world concentrates in detection, exactly as the theory predicts: constructive Freiman theorems exist with terrible bounds, and practical recovery wants LLL-flavored lattice reduction.
The Circle Method: Everything Unifies
The final reframe is the one that ties the evening together. The DFT of the value histogram is an exponential sum, F̂(k) = Σⱼ e^(2πik·vⱼ/N), and Hardy–Littlewood's circle method splits the frequency circle in two. Major arcs — frequencies near rationals a/q with small q — are where residue-structured sets are loud. Minor arcs are everywhere else, where pseudorandom sets live. Roth's structure-versus-randomness dichotomy, running as code.
Major arcs: detection with no big transform
For each modulus q up to Q, fold the values mod q and take a length-q DFT of the class histogram — O(n + q²) per modulus, with the value range completely irrelevant. Walking every rational with q ≤ 300 took about 100ms at a range of 7.5×10⁷, where the dense FFT, the gcd pass, and the gap-elbow detector are all blind. The scanner found the planted q = 251; a class-decomposed solver (Diophantine class-triples crossed with quotient convolutions) then beat two-pointer at n = 32,000 — 1,269ms against 2,048ms — while staying flat in n. Random control instances scanned clean every time.
Minor arcs: a certificate with teeth
Parseval gives a provable bound: the exact triple count differs from a computable main term by at most Λ′·(P₂ + n√(P₂/W) + n²/W), where Λ′ is the largest Fourier coefficient after subtracting the smooth interval model. That subtraction is the crux, and it taught us something on the way in. An interval is itself an arithmetic progression, so the raw spectrum of any interval-supported set is dominated by its own Dirichlet kernel — the first version's structure meter read 0.94 for random sets, valid but useless. Comparing against the smooth model — precisely the circle method's split into singular integral and singular series — fixed it.
The result is one number, Λ′/n, that separates two worlds. Uniform random: 0.081, and the singular integral predicted the true count of 29,151 as 30,024 — within 3%, without computing it, with a rigorous error bar. Quadratic residues, number theory's canonical pseudorandom set: 0.152, certified clean, exactly as Weil-type character-sum bounds say. The structured set: 0.998, correctly routed to the major arcs. The bound held on every adversarial spot-check, as the mathematics requires.
The Synthesis: What the Wall Is Made Of
Stacking five experiments yields a decision tree. An O(n) divisibility certificate. A rank-one lattice solve at the cost of the AP length. A range-independent major-arc scan with a class-decomposed solver. A rank-two GAP solve through the carry-free embedding. A one-FFT flatness certificate proving the count is near its random-model value. And only then, for instances that failed every test, the n² wall.
The point the whole tour was secretly building toward: every structure we exploited corresponds to a large Fourier coefficient somewhere, and every large Fourier coefficient yielded a subquadratic algorithm. The instances that reach the wall are precisely the Fourier-flat ones — where the certificate says the count is forced, so there is nothing left to exploit, only to verify. The 3SUM conjecture is a statement about pseudorandom sets specifically. Additive combinatorics, analytic number theory, and fine-grained complexity turn out to be describing the same object from three sides, and you can watch them converge in a benchmark table.
Open Doors
Sparse spike detection at huge range: the minor-arc certificate needs an FFT over the range, and the scanner only covers small moduli, so detecting a large Fourier coefficient at arbitrary frequency in a 10⁹-range set is sparse-FFT / Goldreich–Levin territory — implementable, and it would close the last detection gap. General GAP recovery wants LLL on the values, the same machinery as approximate-common-divisor attacks in cryptography — a suggestive connection, since instances hard for our detector are ACD-hard instances. The carry-free embedding iterates to higher rank at cost ~3ʳ·∏Lᵢ, climbing until the box outgrows n² — a constructive restatement of where hardness must live. And the bitset path still has 8–32× of SIMD constant factor available, which moves crossovers but never exponents: a clean illustration of the difference.
The code is six self-contained TypeScript files with brute-force verification built in, runnable with npx tsx and zero dependencies. The experiments are honest: the negative results — the mod-p dead end, the detection failures, our own soft benchmark — are reported alongside the wins, because they turned out to be where most of the insight lived.