Can product of all pairwise sums be computed faster than the naive method?

Question

Let $S$ be a set of integers. $|S|=n$.

Can we find the product $\prod_{a,b\in S} a+b$ faster than naively add all pairs then multiply them one by one? By faster, I mean use less than $O(n^2)$ arithmetic operations.

If it's possible, can that algorithm work for any commutative semiring?

Answer 1

Well, a repeated product is best done by recursively splitting the set of terms in half*, computing the products in each half, then multiplying the result, but only if the products become big enough that fast multiplication algorithms become relevant.

Of course, this is the same number of arithmetic operations either way. But it is still computational work overall.

*: half is best computed by total size of the numbers rather than simply how many

---

We could construct the polynomial

$$ f(x) = \prod_{s \in S} (x + s) $$

(keep in mind my advice about repeated products when computing this product!)

Now, the product you seek to compute is

$$ \prod_{s \in S} f(s) $$

The set of values $\{ f(s) | s \in S \}$ could be computed by a fast "multipoint evaluation" algorithm.

---

Recall that the resultant $\mathop{\text{Res}}(g(x),h(x))$ of two monic polynomials is the product

$$ \prod (\alpha - \beta) $$

where $\alpha$ and $\beta$ range over the roots of $g(x)$ and $h(x)$ respectively. So we could also compute the product by

$$ \mathop{\text{Res}}(f(x), f(-x)) $$

---

I haven't attempted to compute the time complexity of these algorithms. I expect the resultant to be the best of the methods I describe both in terms of time complexity and number of arithmetic operations.

All of these techniques can be adapted directly, I think, to any commutative ring. I know very little about computational algebra in semirings, but I find it very plausible the middle algorithm would only require a little bit of adaptation (although I'd be worried about the existence of fast polynomial multiplication algorithms), and a little bit plausible that there is a variation on resultants that would work.

Answer 2

Couldn't you count the exponents for each of the elements of S? Assuming the different cases where the pairwise sums are symmetric a + b and b + a being counted twice or once, you could calculate the exponents for each of the elements of s, and then using fast exponentiation for each of the elements, and construct the sum of the terms.

You might also get extra mileage out of factoring the elements into powers of generators, if that is possible in the objects you describe.