Randomized Integer Word-RAM 3SUM Conjecture

Randomized Integer Word-RAM 3SUM Conjecture

Definitions and mathematical statement

For a set $S\subseteq[-n^3,n^3]\cap{\mathbb{Z}}$ of $n$ distinct integers, define $\mathrm{3SUM}(S)=1$ precisely when distinct $a,b,c\in S$ satisfy $a+b+c=0$. Work on a uniform integer word-RAM with $\Theta(\log n)$-bit words and the operations specified by the source. A Las Vegas algorithm always answers correctly and terminates almost surely; its cost is expected running time over its internal random bits. The conjecture excludes, for every fixed $\varepsilon>0$, an algorithm satisfying \[ \sup_{|S|=n}{\mathbb{E}}[T(S)]=O(n^{2-\varepsilon}). \] There is no real-arithmetic oracle, free preprocessing, or input-specific advice. Logarithmic improvements to $n^2$ are not excluded by this exponent statement.

Formulation and concept references: [S1].

Short English statement

Must exact three-sum testing on bounded integers resist every always-correct randomized algorithm whose worst-case expected exponent is strictly below two?

Research attempt

Current frontier.

The formulation source treats the exponent form of integer 3SUM hardness, not an exact quadratic lower bound [S1], Conjecture 1. The logarithmic savings of Grønlund--Pettie do not refute this selected statement [E1]. A particularly relevant recent result is the $O(n^{3/2}\log n)$ query algorithm of Kasliwal--Polak--Sharma after quadratic preprocessing of three fixed universes [E2]. Its preprocessing is forbidden as a free resource here. The attempt below does not use it. Instead it isolates a streaming witness-reporting statement whose truth would give a genuinely subquadratic algorithm in the exact model of the catalogue.

Attack route.

Dense convolution is fast but the input universe has size $\Theta(n^3)$. Modular hashing reduces that universe while introducing false triples. The usual obstruction is that a convolution coefficient reports a count, not an efficiently accessible list of witnesses. A second obstruction is that even a true instance may have quadratically many valid witnesses, although a decision algorithm needs only one. The proposed attack joins a random modulus with prefix-efficient witness enumeration. Both obstructions are quantified rather than hidden in a subroutine call.

Attempt: the missing algorithmic lemma.

Fix the following precise hypothesis, denoted $\mathsf{StreamConv}$. Given a prime $p$ and a Boolean array $A$ indexed by ${\mathbb{Z}}/p{\mathbb{Z}}$, there is a uniform algorithm in the logarithmic-word RAM model that lists, without repetition, all ordered triples \begin{equation}\label{wsref-0-33-30-30-30-36-37-36-32-3a-72-65-73-69-64-75-65-2d-74-72-69-70-6c-65-73} (r,s,t),\qquad r+s+t=0\pmod p,\qquad A(r)A(s)A(t)=1. \end{equation} If the total number is $K$, the time to produce the first $k$ triples is $\widetilde O(p+k)$ for every $1\le k\le K$, and the time to report exhaustion is $\widetilde O(p+K)$. The algorithm is deterministic and uses only polynomially many $O(\log p)$-bit words. The notation $\widetilde O$ hides fixed powers of logarithms, uniformly over inputs.

This is an unproved reporting hypothesis. Ordinary fast Fourier transform convolution does not supply it. In particular a total-output bound without the prefix guarantee is not enough for the argument below.

Attempt: reduction theorem.

Conditional lemma. If $\mathsf{StreamConv}$ holds, the problem in this section has a uniform Las Vegas algorithm with worst-case expected running time $\widetilde O(n^{3/2})$. Thus this hypothesis would disprove the exact 3SUM conjecture printed above.

Construction. For a valid input $S$ let $m=\lceil n^{3/2}\rceil$. Enumerate the primes in $[m,2m]$ by a sieve and choose one uniformly. The finitely many small $n$ are handled by brute force. For all sufficiently large $m$ the prime number theorem gives \begin{equation}\label{wsref-0-33-30-30-30-36-37-36-32-3a-70-72-69-6d-65-2d-63-6f-75-6e-74} \#\{p\text{ prime}:m\le p\le2m\}\gg m/\log m. \end{equation} The sieve and the explicit list use $\widetilde O(m)$ word operations and space. An exactly uniform random index can be sampled by rejection from a power-of-two range; the acceptance probability exceeds $1/2$.

For each residue $r$, form its bucket $S_r=\{a\in S:a\equiv r\pmod p\}$ and set $A(r)=1$ exactly for nonempty buckets. Invoke $\mathsf{StreamConv}$. For each emitted triple $(r,s,t)$ inspect the Cartesian product $S_r\times S_s\times S_t$, stopping immediately if \[ a+b+c=0\quad\text{as integers},\qquad |\{a,b,c\}|=3. \] If the reporter exhausts its list without finding this, answer no. Every genuine zero triple has residue sum zero for every chosen prime, so no yes instance can be missed. Every yes answer is checked in the integers. The randomness affects only the cost, not correctness.

Attempt: a uniform expected-cost bound.

Call an ordered integer triple false if $a+b+c\ne0$ but $p\mid a+b+c$. For such a triple set $q=a+b+c$; then $0<|q|\le3n^3$. The number of different prime divisors of $q$ in $[m,2m]$ is at most \begin{equation}\label{wsref-0-33-30-30-30-36-37-36-32-3a-64-69-76-69-73-6f-72-2d-63-6f-75-6e-74} \frac{\log(3n^3)}{\log m}\le3 \end{equation} for all sufficiently large $n$. Indeed, the product of $k$ such distinct primes is at least $m^k$ and divides $|q|$. Together with (30006762:prime-count), this gives \begin{equation}\label{wsref-0-33-30-30-30-36-37-36-32-3a-66-61-6c-73-65} {\mathbb{E}} F_p \le \sum_{(a,b,c)\in S^3\, :\,a+b+c\ne0} \Pr(p\mid a+b+c) \ll \frac{n^3\log m}{m}, \end{equation} where $F_p$ is the number of false ordered triples. No independence among these events is used: this is only linearity of expectation.

Repeated-element zero triples need separate treatment. For each of the three equality patterns, such as $a=b$, the equation $2a+c=0$ leaves at most $n$ possibilities because $S$ is a set. Hence at most $3n$ ordered zero triples have a repeated element. Counting the all-equal triple more than once only strengthens this upper bound.

Before termination, therefore, at most \begin{equation}\label{wsref-0-33-30-30-30-36-37-36-32-3a-70-72-65-66-69-78-2d-63-6f-75-6e-74} F_p+3n+1 \end{equation} integer triples are inspected. On a no instance the last $1$ can be omitted; on a yes instance there is only one inspected distinct-element zero triple, because the algorithm stops at the first one. Each emitted residue triple has a nonempty Cartesian product and accounts for at least one inspected integer triple, except that the final product may be only partly inspected. Thus the number of reporter outputs needed is also at most (30006762:prefix-count).

The prefix and exhaustion guarantees now imply cost \[ \widetilde O(m+n+F_p),\qquad \sup_{|S|=n}{\mathbb{E}} T(S) =\widetilde O\left(m+n+\frac{n^3}{m}\right) =\widetilde O(n^{3/2}). \] All integer sums, residues, array indices and sieve indices use $O(\log n)$ bits. The constants in the estimates are independent of the input values. Rejection sampling terminates almost surely, and all remaining loops are finite. These observations check the uniform Las Vegas and worst-case-expectation requirements, rather than replacing them by a high-probability Monte Carlo statement.

Stress test: attempted implementation of the reporter.

Convolution of $A$ with itself gives, for each $u$, the number of pairs $r+s=u$. It does not give the first such pair for every requested target in near-linear total time. Scanning $r$ independently for each occupied $t$ can cost $p\,|\operatorname{supp}A|$; at $p\asymp n^{3/2}$ this loses the claimed exponent. Building all residue pairs explicitly costs $\Theta(|\operatorname{supp}A|^2)$ and also loses the desired bound in the worst case. Hashing by itself therefore does not finish the algorithm.

One might recursively bisect the support and use convolution to prune empty pair rectangles. The unresolved amortization is that many target sums can keep overlapping rectangles alive; I did not prove an $\widetilde O(p+k)$ prefix bound on the total convolution work. Paying for all $K$ outputs before emitting the first is invalid: a symmetric set can have $\Theta(n^2)$ distinct-element zero triples. The quadratic preprocessing in [E2] is an explicit illustration of why a fast query guarantee does not automatically solve the present problem.

The checking script exhausts all $462$ five-element subsets of $[-5,5]$, using each of five small prime moduli. A deliberately slow reporter confirms correctness and the handling of repeated entries. This verifies neither $\mathsf{StreamConv}$ nor the asymptotic running time. It also checks the elementary divisor bound at a finite sample scale. No finite test could certify the required uniform reporting complexity.

Dependency check.

The reduction is not a lower bound against an unrestricted word-RAM and is not a proof of the catalogue's conjecture. Its direction is the opposite: the proposed reporting lemma would violate that conjecture, with a polynomial exponent saving (for example any fixed saving below $1/2$ after absorbing logarithms). Since 3SUM already belongs to polynomial time, this consequence alone does not imply $\mathrm P=\mathrm{NP}$ or its negation. The strong consequence is nevertheless a warning against accepting the reporter as a routine FFT primitive. The connection between integer 3SUM and output-sensitive reporting is also consonant with the reductions in [S1], Section 10.

Outcome.

Outcome: Conditional reduction.

The hashing, false-positive estimate, repeated-element bound, stopping argument, and exact model audit above form a proved conditional reduction. The single missing algorithmic input is $\mathsf{StreamConv}$ with its prefix-time and exhaustion guarantees. No implementation achieving those guarantees has been obtained, and the finite checker is not such an implementation. Thus no unconditional subquadratic algorithm or lower bound is claimed.

Sources

• S1 Abboud and Vassilevska Williams, Popular Conjectures Imply Strong Lower Bounds for Dynamic Problems $2014$, Conjecture 1; KPP $2019$ for Las Vegas convention. https://arxiv.org/pdf/1402.0054. Catalogue formulation source.
• E1 Allan Grønlund and Seth Pettie, "Threesomes, Degenerates, and Love Triangles," arXiv:1404.0799 $2014$. Introduction and 3SUM algorithm bounds. https://arxiv.org/abs/1404.0799. Logarithmic improvements and the distinction from a fixed exponent saving.
• E2 Shashwat Kasliwal, Adam Polak and Pratyush Sharma, "3SUM in Preprocessed Universes: Faster and Simpler," TheoretiCS 4 $2025$, DOI 10.46298/theoretics.25.24; arXiv:2410.16784v3 (15 October 2025). Abstract, introduction and preprocessing/query theorem. https://arxiv.org/html/2410.16784v3. Quadratic preprocessing is counted and is not available for free in the selected model.