<p>Warning: This is not yet a complete answer. If plausibility arguments make you uncomfortable, stop reading.</p>
<p>I will consider a variant where we want to multiply <span class="math-container">$(x - a_1) \cdot ... \cdot (x - a_n)$</span> over the complex numbers.</p>
<p>The problem is dual to evaluating a polynomial at n points. We know this can be done cleverly in <span class="math-container">$O(n \log n)$</span> time when the points happen to be <span class="math-container">$n$</span>-th roots of unity. This takes essential advantage of the symmetries of regular polygons that underlie the Fast Fourier Transform. That transform comes in two forms, conventionally called decimation-in-time and decimation-in-frequency. In radix two they rely on a dual pair of symmetries of even-sided regular polygons: the interlocking symmetry (a regular hexagon consists of two interlocking equilateral triangles) and the fan unfolding symmetry (cut a regular hexagon in half and unfold the pieces like fans into equilateral triangles).</p>
<p>From this perspective, it seems highly implausible that an <span class="math-container">$O(n \log n)$</span> algorithm would exist for an arbitrary set of <span class="math-container">$n$</span> points without special symmetries. It would imply that there is nothing algorithmically exceptional about regular polygons as compared to random sets of points in the complex plane.</p>

CC BY-SA 3.0
2012-02-21T04:58:04.287Z
@PerVognsen: Can you give a reference for this point of view re: symmetries of polygons / interlocking symmetry? Or if this is an observation of your own, could you expand on it a bit more?
Joshua Grochow
CC BY-SA 2.5
2010-09-27T06:46:01.023Z
On the other hand, an $\Omega(n\log^2 n)$ lower bound for such a natural problem seems equally implausible!
Jeffε
CC BY-SA 2.5
2010-09-27T06:51:21.940Z
True! I wish I had a more definitive answer. It's very interesting.
Per Vognsen
CC BY-SA 2.5
2010-09-28T01:36:22.460Z
Bounty awarded!
Jeffε
CC BY-SA 4.0
2010-09-24T06:31:37.537Z
2021-10-20T07:50:40.300Z
2021-10-20T07:50:40.300Z
Per Vognsen
<p>In computer algebra, this computation is usually referred as computing the <em>subproduct tree</em> and is a subroutine of multipoint evaluation and interpolation. See for instance: von zur Gathen, Gerhard. <a href="https://www.cambridge.org/core/books/modern-computer-algebra/DB3563D4013401734851CF683D2F03F0" rel="nofollow noreferrer">Modern Computer Algebra</a>, 3rd edition, 2013 [chapter 10]. As far as I know, the best known complexity is <span class="math-container">$O(\mathsf{M}(n)\log n)$</span> where <span class="math-container">$\mathsf M(n)$</span> denotes the cost of multiplying two degree-<span class="math-container">$n$</span> polynomials. (This applies over any ring.)</p>

CC BY-SA 4.0
2021-10-18T07:11:31.490Z
Is there a matching lower bound or is the lower bound $\Omega(\mathsf{M}(n))$?
Turbo
CC BY-SA 4.0
2021-10-18T08:16:28.557Z
For the original problem, I do not think so. For the subproduct tree used in multipoint evaluation, the output size is $O(n\log n)$ so this gives a lower bound independent from $\mathsf{M}(n)$ (though not larger).
Bruno
CC BY-SA 4.0
2021-10-19T23:50:46.830Z
Believe me when I say that Mihai knew this... but it is good to name the problem, and give references.
Ryan Williams
CC BY-SA 4.0
2021-10-20T16:04:59.380Z
I had not made the connection between the first name and the author of the question...
Bruno
CC BY-SA 4.0
2021-10-18T07:06:28.463Z
2021-10-18T07:06:28.463Z
Bruno
<p>The problem is to compute the polynomial $(a_1 x + b_1) \times \cdots \times (a_n x + b_n)$. Assume that all coefficients fit in a machine word, i.e. can be manipulated in unit time.</p>

<p>You can do $O(n \log^2 n)$ time by applying FFT in a tree fashion. Can you do $O(n \log n)$?</p>

CC BY-SA 2.5
2010-08-27T19:51:10.663Z
Nice question, seems like I've seen something similar in someone's  blog, but I can't remember where it was.
Grigory Yaroslavtsev
CC BY-SA 2.5
2010-08-28T02:43:32.423Z
Minor observation: we know (working over Q, say) the n roots $\alpha_i = -b_i/a_i$, so the problem is equivalent to: Given $\alpha_1, \dots , \alpha_n$, compute the polynomial $(x-\alpha_1)\dots(x-\alpha_n)$. (I guess.)
ShreevatsaR
CC BY-SA 2.5
2010-09-10T02:14:14.600Z
Can you give a reference to the $O(n\log^2 n)$ result?
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-09-10T04:15:32.257Z
@turkistany: do divide and conquer. the merge step is a single multiplication on two polys of degree n/2, which can be done in n log n time via FFT. so the overall recurrence is 2T(n/2) + n log n.
Suresh Venkat
CC BY-SA 2.5
2010-09-10T04:47:38.870Z
As @Suresh mentioned, it is a simple divide-and-conquer approach. It can be generalized so that n polys may have different degrees $d_i$, in which case you can divide in a Huffman tree fashion. See Strassen: The computational complexity of continued fractions.
Zeyu
CC BY-SA 2.5
2010-09-10T05:55:49.497Z
You're talking about computing the coefficients of the polynomial, right?  Is this equivalent to computing the product of $\sqrt{n}$ $\sqrt{n}$-bit integers in time $\tilde O(n \log n)$ (where $\tilde O$ hides sub-logarithmic factors)?
Joshua Grochow
CC BY-SA 2.5
2010-09-10T07:50:29.470Z
@Joshua not sure I see the connection
Suresh Venkat
CC BY-SA 2.5
2010-09-10T13:19:37.387Z
@Suresh: as far as I can see, the two questions are not *obviously* equivalent.  The connection is that they both can use divide-and-conquer and then the FFT to get time $\tilde O(n \log^2(n))$.  In a sense both questions are asking whether $n$ FFT-based multiplications can be done in the same asymptotic running time as a single such multiplication; I wouldn't be surprised if a positive answer to one implied a positive answer to the other, but again, it's not obvious.
Joshua Grochow
CC BY-SA 2.5
2010-09-10T13:55:13.773Z
@Joshua, I'm confused, What does $n$ represent here? Is it the number of bits or is it the number of polynomials?
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-09-10T14:14:48.943Z
Can we compute the convolution of $n$ vectors of constant dimension 2 in time $O(n \log n)$?
Kaveh
CC BY-SA 2.5
2010-09-12T04:58:20.663Z
@turkistany, in both cases it is the number of bits.  In the original question, Mihai stipulated that the coefficients fit into a single word, so the number of bits is O(n).  In my question I stipulated $\sqrt{n}$ numbers of $\sqrt{n}$ bits each, for a total of $n$ bits.
Joshua Grochow
CC BY-SA 2.5
2010-09-23T11:56:16.533Z
@Joshua: You're correct, but (and I'm about to say something that's nigh-heresy in a theoretical discussion) machine word size probably grows slower than anything else in all of computer science. For any actual machine a $\sqrt(n)$-bit machine word is just a byte. A "don't care" assumption, as in the question, makes plenty of sense; but taking the further step of treating machine words as a "true" $O(n)$-size object seems too impractical to make much sense to me..
Daniel Apon
CC BY-SA 2.5
2010-09-25T05:21:46.490Z
@Daniel: The standard assumption is that a word is O(log n) bits long. This is sometimes generalized to allow words of length w ≥ log n, but even then, the word size w is typically assumed to be O(polylog n).  Word sizes around √n would make a number of things unreasonably easy, thanks to massive bit-level parallelism.  But yes, O(n)-bit words are right out.
Jeffε
<ds.algorithms><reference-request><open-problem><polynomials>
Multiplying n polynomials of degree 1
Mihai
# Multiplying n polynomials of degree 1

(Asked by: username_0 on 2010-08-27)

The problem is to compute the polynomial $(a\_1 x + b\_1) \times \cdots \times (a\_n x + b\_n)$. Assume that all coefficients fit in a machine word, i.e. can be manipulated in unit time.

You can do $O(n \log^2 n)$ time by applying FFT in a tree fashion. Can you do $O(n \log n)$?

**Tags:** ds.algorithms, reference-request, open-problem, polynomials

> **Comments:**
> **username_1**: Nice question, seems like I've seen something similar in someone's  blog, but I can't remember where it was.  
> **username_2**: Minor observation: we know (working over Q, say) the n roots $\alpha_i = -b_i/a_i$, so the problem is equivalent to: Given $\alpha_1, \dots , \alpha_n$, compute the polynomial $(x-\alpha_1)\dots(x-\alpha_n)$. (I guess.)  
> **username_3**: Can you give a reference to the $O(n\log^2 n)$ result?  
> **username_4**: @turkistany: do divide and conquer. the merge step is a single multiplication on two polys of degree n/2, which can be done in n log n time via FFT. so the overall recurrence is 2T(n/2) + n log n.  
> **username_5**: As @Suresh mentioned, it is a simple divide-and-conquer approach. It can be generalized so that n polys may have different degrees $d_i$, in which case you can divide in a Huffman tree fashion. See Strassen: The computational complexity of continued fractions.  
> **username_6**: You're talking about computing the coefficients of the polynomial, right?  Is this equivalent to computing the product of $\sqrt{n}$ $\sqrt{n}$-bit integers in time $\tilde O(n \log n)$ (where $\tilde O$ hides sub-logarithmic factors)?  
> **username_4**: @Joshua not sure I see the connection  
> **username_6**: @Suresh: as far as I can see, the two questions are not *obviously* equivalent.  The connection is that they both can use divide-and-conquer and then the FFT to get time $\tilde O(n \log^2(n))$.  In a sense both questions are asking whether $n$ FFT-based multiplications can be done in the same asymptotic running time as a single such multiplication; I wouldn't be surprised if a positive answer to one implied a positive answer to the other, but again, it's not obvious.  
> **username_3**: @Joshua, I'm confused, What does $n$ represent here? Is it the number of bits or is it the number of polynomials?  
> **username_7**: Can we compute the convolution of $n$ vectors of constant dimension 2 in time $O(n \log n)$?  
> **username_6**: @turkistany, in both cases it is the number of bits.  In the original question, username_0 stipulated that the coefficients fit into a single word, so the number of bits is O(n).  In my question I stipulated $\sqrt{n}$ numbers of $\sqrt{n}$ bits each, for a total of $n$ bits.  
> **username_8**: @Joshua: You're correct, but (and I'm about to say something that's nigh-heresy in a theoretical discussion) machine word size probably grows slower than anything else in all of computer science. For any actual machine a $\sqrt(n)$-bit machine word is just a byte. A "don't care" assumption, as in the question, makes plenty of sense; but taking the further step of treating machine words as a "true" $O(n)$-size object seems too impractical to make much sense to me..  
> **username_9**: @Daniel: The standard assumption is that a word is O(log n) bits long. This is sometimes generalized to allow words of length w ≥ log n, but even then, the word size w is typically assumed to be O(polylog n).  Word sizes around √n would make a number of things unreasonably easy, thanks to massive bit-level parallelism.  But yes, O(n)-bit words are right out.  

---

## 2 answers

### Answer by username_10 on 2010-09-24. Score: 7

Warning: This is not yet a complete answer. If plausibility arguments make you uncomfortable, stop reading.

I will consider a variant where we want to multiply $(x - a\_1) \cdot ... \cdot (x - a\_n)$ over the complex numbers.

The problem is dual to evaluating a polynomial at n points. We know this can be done cleverly in $O(n \log n)$ time when the points happen to be $n$-th roots of unity. This takes essential advantage of the symmetries of regular polygons that underlie the Fast Fourier Transform. That transform comes in two forms, conventionally called decimation-in-time and decimation-in-frequency. In radix two they rely on a dual pair of symmetries of even-sided regular polygons: the interlocking symmetry (a regular hexagon consists of two interlocking equilateral triangles) and the fan unfolding symmetry (cut a regular hexagon in half and unfold the pieces like fans into equilateral triangles).

From this perspective, it seems highly implausible that an $O(n \log n)$ algorithm would exist for an arbitrary set of $n$ points without special symmetries. It would imply that there is nothing algorithmically exceptional about regular polygons as compared to random sets of points in the complex plane.

> **Comments:**
> **username_9**: On the other hand, an $\Omega(n\log^2 n)$ lower bound for such a natural problem seems equally implausible!  
> **username_10**: True! I wish I had a more definitive answer. It's very interesting.  
> **username_9**: Bounty awarded!  
> **username_6**: @PerVognsen: Can you give a reference for this point of view re: symmetries of polygons / interlocking symmetry? Or if this is an observation of your own, could you expand on it a bit more?  

---

### Answer by username_11 on 2021-10-18. Score: 2

In computer algebra, this computation is usually referred as computing the *subproduct tree* and is a subroutine of multipoint evaluation and interpolation. See for instance: von zur Gathen, Gerhard. [Modern Computer Algebra](https://www.cambridge.org/core/books/modern-computer-algebra/DB3563D4013401734851CF683D2F03F0), 3rd edition, 2013 [chapter 10]. As far as I know, the best known complexity is $O(\mathsf{M}(n)\log n)$ where $\mathsf M(n)$ denotes the cost of multiplying two degree-$n$ polynomials. (This applies over any ring.)

> **Comments:**
> **username_12**: Is there a matching lower bound or is the lower bound $\Omega(\mathsf{M}(n))$?  
> **username_11**: For the original problem, I do not think so. For the subproduct tree used in multipoint evaluation, the output size is $O(n\log n)$ so this gives a lower bound independent from $\mathsf{M}(n)$ (though not larger).  
> **username_13**: Believe me when I say that username_0 knew this... but it is good to name the problem, and give references.  
> **username_11**: I had not made the connection between the first name and the author of the question...  

---

