# Raising a polynomial to a power

Let $$f$$ be a degree $$n$$ univariate polynomial in $$Z[x]$$, defined as $$f = \sum\limits_{i=0}^{i=n} f_i x^i$$. Let $$g = f^2 = f \cdot f = \sum\limits_{k=0}^{k=2n} g_k x^k$$ be the square of $$f$$. I am trying to find an expression for the coefficients $$g_k$$. So far, I have the standard expression: $$g_k = \sum\limits_{i+j=k,0 \le i,j \le n} f_i f_j.$$ But while playing with polynomials in Maple, I noticed that there is (seemingly) more structure in the coefficients. Is there a nicer formula for raising a polynomial to arbitrary powers? (and more specifically to power 2?)

• Well, a generalization to arbitrary powers is given by the multinomial theorem. Feb 18, 2011 at 5:16
• @Calle: Only sort of; the multinomial theorem gives you the coefficients of the monomials in $(a_0+\cdots+a_m)^k$, but to get the coefficient of $x^r$ you would need to add over all monomials whose "index sum" equals $r$. Feb 18, 2011 at 5:39
• @Arturo, ah, yes. That's true. Feb 18, 2011 at 5:43

At least you can do it faster, using discrete Fourier transform.

Let $a$ be a vector with $2n$ elements whose first $n$ elements are the coefficients of the polynomial $f$, the rest zero. Let $c$ be the vector with the coefficients for $g$. Then $c$ is the cyclic convolution of $a$ with itself:

$$c = a * a$$

But convolution turns to multiplication under the Fourier transform $\mathcal F$:

$$\mathcal F (c) = \mathcal F(a) \mathcal F(a)$$

using the inverse Fourier transform you get:

$$c = \mathcal F^{-1} \left( \mathcal F(a) \mathcal F(a) \right)$$

This can of course be generalized to arbitrary powers and polynomials which are not equal.

• Would FFT work over $\mathbb{Z}$? What would be the $n^{th}$-PRU?
– user2468
Feb 18, 2011 at 5:40
• Just do as you would when you work over $\mathbb C$. Now you just happen to have integers. Feb 18, 2011 at 5:56
• See everything2.com/title/…. Time complexity is $O(n\log n)$.
– Did
Feb 18, 2011 at 9:24

I've written this for the more general case of the p'th power of a powerseries $$f(x)=1+ax+bx^2+...$$ You can just set all non-wanted coefficients to zero. Here is a screenshot: The numerical coefficients at some term $$a^{e_1}*b^{e_2}*c^{e_3}$$depends on the occurences of the exponents and the number of factors (multinomials)

Since you say you are mostly interested in squaring a polynomial, have you ever tried using the "box method"? It's often used for small polynomials, but can be used for any number of terms (that can be written on a piece of paper). See, for example, YouTube

On a grid, write the terms across the top of each column and write the same terms to the left of each row. At the intersection of a row and column write the product of the term at the left of that row and the top of the column. You will end up with a symmetric box (so you can simply copy the result in row i column j into row j col i) with squares down the diagonal and cross terms everywhere else. Now collect terms in "boxes" that have the same power of $$x$$ by adding those terms and cross them off as you go. When you are done you will have the terms of the squared polynomial. Seeing all the terms layed out and how they came together in the result might help you see the source of the structure that you are seeing.

Here is a small example. The bold cells were copied from the corresponding cells above the diagonal.