Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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}^{i=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?)

share|improve this question
3  
Well, a generalization to arbitrary powers is given by the multinomial theorem. –  Calle Feb 18 '11 at 5:16
3  
@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$. –  Arturo Magidin Feb 18 '11 at 5:39
    
@Arturo, ah, yes. That's true. –  Calle Feb 18 '11 at 5:43
add comment

2 Answers 2

up vote 1 down vote accepted

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: p'th power of a power series 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)

share|improve this answer
add comment

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.

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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.