<p>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$. </p>

<p>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$. </p>

<p>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})$. </p>

<p>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.)</p>

CC BY-SA 4.0
2018-06-19T19:53:47.647Z
2018-06-25T03:26:21.343Z
2018-06-25T03:26:21.343Z
Alex Golovnev
<p><a href="https://arxiv.org/abs/1502.05204" rel="noreferrer">Chan and Lewenstein (STOC 2015)</a> said:</p>

<blockquote>
  <p>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).</p>
</blockquote>

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

<p>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)</p>

<fft><convolution>
Subquadratic 3SUM when one set is in [n^1.99]
Alexandr Pietriev
# Subquadratic 3SUM when one set is in [n^1.99]

(Asked by: username_0 on 2018-06-18)

[Chan and Lewenstein (STOC 2015)](https://arxiv.org/abs/1502.05204) said:

> 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)

**Tags:** fft, convolution

---

## 1 answers

### Answer by username_1 on 2018-06-19. Score: 3 | Accepted answer

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.)


---

