# Subquadratic 3SUM when one set is in [n^1.99]

3SUM for three integer sets where only one set is assumed to be in $[n^{2−\delta}]$ can still be solved in subquadratic time (by doing several FFTs, without requiring additive combinatorics - a simple exercise we leave to the reader).

Note, that the other 2 sets can be from $[n^{3+o(1)}]$.

Nevertheless I have no idea how to solve this exercise. Do you have any hints? (probably you can use their paper but it looks like an overkill)

I think one can solve this problem as follows. Assume that we have three sets $A, B, C$ of integers, $|A|=|B|=|C|=n$, and $C\subseteq [n^{2-\delta}]$. We want to check whether there exist $a\in A, b \in B, c \in C$ such that $a+b+c=0$.
First, we partition the set $A$ into $k\leq n$ sets $A_1,\ldots A_k$, where each $A_i$ contains numbers in an interval of length $n^{2-\delta}$. Now from the set $B$, we construct sets $B_1,\ldots, B_k$ as follows. $B_i$ contains numbers from $B$ in the interval $[-n^{2-\delta}-\max_{a \in A_i}{a}, -\min_{a\in A_i}a]$. This way each number from $B$ appears in at most two sets $B_i$. And now we only need to check whether for some $i$ there exists a solution in $A_i + B_i + C$.
Let $a_i=|A_i|$, $b_i=|B_i|$. If $a_i\geq n^{1-\delta/2}$ or $b_i\geq n^{1-\delta/2}$, we solve $A_i+B_i+C$ by FFT in time $O(n^{2-\delta}\log{n})$. (Because numbers in all three sets lie in intervals of length $O(n^{2-\delta})$.) Since $\sum_i a_i=n$ and $\sum_i b_i\leq 2n$, the total number of such $a_i$ and $b_i$ is at most $3n^{\delta/2}$, which means that the running time of this step is $O(n^{2-\delta/2}\log{n})$.
For the remaining values of $i$, we solve the problem by trying all $a\in A_i$ and $b \in B_i$, and looking up their sum in $C$ in logarithmic time. This step takes time $\sum a_i b_i \log{n} \leq O(n^{2-\delta/2}\log{n})$. (I believe one can shave off the $\log{n}$ factor here by using the standard 3-SUM trick.)