# Sums of all pairs: possible less than quadratic?

Is there an algorithm to prepare all sums of pairs of a list ($L$, size $n$, max value $m$) in $< O(n^2)$ such that query "does this sum of pairs exist" takes $< O(n)$? In other words, can max value $m$ be used to advantage?

E.g. in $L =\{1, 2, 4, 8\}$ and $m = 8$, all (distinct) sums of pairs are $S = \{2, 3, 4, 5, 6, 8, 9, 10, 12, 16\}$ (not given, calculate).

This may be possible using a divide-and-conquer on both $L$ and on the bits of each item. (N.B. the constraint keeps $S.size$ to $2m$, no need for size $O(n^2)$)

• How large is $m$ compared to $n$? – Chao Xu Jan 5 '15 at 9:41

Yes, it is possible using $O(n \log n)$ preprocessing and $O(\log n)$ query time.

Given the set $S$, construct the polynomial $P(x)=\Sigma_{s\in S}\textrm{ } x^s$. Then use the FFT multiplication algorithm to compute $P^2(x)=P(x)*P(x)$ in $O(n \log n)$.

A value $q$ s a sum-of-pairs of $S$ if and only if the coefficient of $x^q$ in $P^2(x)$ is non-zero. Use binary search to look up the coefficient in $O(\log n)$ time ($P^2(x)$ is a polynomial of degree $2m$).

There are also less complicated (and less efficient, but still better than $O(n^2)$) multiplication algorithms that use divide-and-conquer such as Karatsuba multiplication ($O(n^{1.585})$ preprocessing).

• Given how special is the polynomial (all coefficients are 0 or 1), and that we are interested only in whether the coefficient in the product is non-zero, there probably should be a much simpler, or more efficient, multiplication algorithm than FFT? – jkff Jan 4 '15 at 22:16
• Btw, seems like this problem is called "boolean convolution", though I couldn't yet find fast algorithms for it other than FFT. – jkff Jan 5 '15 at 6:56
• Shouldn't the FFT take $O(m \log m)$ time instead? – Chao Xu Jan 5 '15 at 9:43

The value $m$ can be used to advantage by simply sorting the list, and applying whatever $O(n)$ algorithm you had in mind on the list pruned to exclude items greater than the requested sum (which is $< 2m$). You get $O(m + log(n))$ complexity then.

• But you're not given $S$, you're given $L$ (I have clarified my question above). To get $S$ (brute force) takes $O(n^2)$, so the crux of my question was to find a better way to get $S$. The answer, turns out, is fast-fourier transform. – Derek Illchuk Jan 4 '15 at 22:28
• Sorry for the confusion, by S I meant "the requested sum". It cannot be greater than 2m, and the rest of my answer holds. – jkff Jan 5 '15 at 1:15