Computing a polynomial product over roots of unity - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T09:27:45Z http://mathoverflow.net/feeds/question/59859 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/59859/computing-a-polynomial-product-over-roots-of-unity Computing a polynomial product over roots of unity Peter Scholl 2011-03-28T16:30:13Z 2011-03-29T23:08:45Z <p>I'm trying to compute the coefficients of the following polynomial, where $\omega$ is a primitive $p$-th root of unity, for $p$ prime:</p> <p>$$a(x) = \prod_{i=0}^{p-1} f(\omega^ix).$$</p> <p>It turns out that the $i$-th coefficient is always an integer, and non-zero only when $i$ is a multiple of $p$. So it seems to me like there should be an elementary expression for $a$.</p> <p>So far I've got this expression for the $i$-th coefficient: $$a_i = x^i\sum_{k_0 + \ldots + k_{p-1} = i}f_{k_0} \cdots f_{k_{p-1}} \omega^{k_1 + 2k_2 + \ldots + (p-1)k_{p-1}}$$</p> <p>where each $k_i$ is non-negative and bounded by the degree of $f$.</p> <p>Clearly the roots of unity all cancel out somehow, but I can't figure out how to get a 'nice' expression out. Any suggestions?</p> http://mathoverflow.net/questions/59859/computing-a-polynomial-product-over-roots-of-unity/59890#59890 Answer by Abdelmalek Abdesselam for Computing a polynomial product over roots of unity Abdelmalek Abdesselam 2011-03-28T20:05:43Z 2011-03-28T20:05:43Z <p>Notice that $$y^p-x^p=\prod_{i=0}^{p-1} (y-\omega^i x)\ .$$ Therefore $$\prod_{i=0}^{p-1} f(x\omega^i)= Res_y (y^p-x^p, f(y))\ .$$ Where $Res_y$ is the resultant of the polynomials in $y$. The above is just a particular case of the so called Poisson product formula. You can then compute the resultant using for instance Sylvester's determinant formula. See the review <a href="http://mate.dm.uba.ar/~alidick/papers/chapter1cd.pdf" rel="nofollow">http://mate.dm.uba.ar/~alidick/papers/chapter1cd.pdf</a> by Cattani and Dickenstein for a nice introduction to resultants and their properties.</p> http://mathoverflow.net/questions/59859/computing-a-polynomial-product-over-roots-of-unity/59902#59902 Answer by Aaron Meyerowitz for Computing a polynomial product over roots of unity Aaron Meyerowitz 2011-03-28T23:15:21Z 2011-03-29T23:08:45Z <p>I don't think that $p$ being prime makes any difference. The <strong>later thoughts</strong> below suggest a Lagrange interpolation method which is perhaps the same as the resultant method mentioned by Abdelmalek Abdesselam.</p> <p>Let $f(x)=\sum_{j=0}^nc_jx^j.$ One might require $c_n=1$ or $c_0=1$ but it is perhaps nicer not to. Then setting $u=x^n,$ $\prod_{i=0}^{n-1} f(\omega^ix)=F(u)=\sum_{j=0}^nC_j u^j$. One can say that </p> <ul> <li>$C_j$ is a polynomial of degree $n$ in the coefficients $c_0,\cdots,c_n$ where each term has total degree $n$ </li> <li>$C_j$ has a term $\pm(c_j)^n$ and no term $c_j^{n-1}$.</li> <li>$C_{n-j}$ is $C_j$ with $c_k$ replaced by $c_{n-k}$</li> <li>the roots of $F$ are the $n$th powers of the roots of $f$.</li> </ul> <p>Here $c_n$ is a constant and the other $c_i$ are symmetric polynomials of the $n$ roots $\alpha_i$ of $f$. The $\alpha_i$ can be thought of as formal variables. Then $c_0,\cdots,c_{n-1}$ are also a basis for the ring of all symmetric polynomials in those variables ($\frac{1}{c_n}$ times a usual basis) . There are other bases for this ring such as $\sigma_k=\sum_{i=1}^n\alpha_i^k$ and the sum of all the terms $\alpha_1^{m_1}\cdots\alpha_n^{m_n}$ with $m_1+\cdots+m_n=k$. Transforming between these bases (more generally, expressing a given symmetric polynomial in terms of them) is a major topic of invariant theory.</p> <p>In this case, we want to express the $C_i$, which are certain symmetric polynomials in the <code>$\alpha_i^n,$</code> in terms of the values $c_i$. This must be a well known case. At any rate here are some results:</p> <p>For $n=4,$</p> <p>$$C_0=c_0^4$$</p> <p>$$C_1=(4c_0^3c_4-2c_0^2c_2^2)-(4c_0^2c_3)c_1+(4c_0c_2)c_1^2-c_1^4$$</p> <p>$$C_2=(6c_0^2c_4^2-8c_0c_1c_3c_4+2c_1^2c_3^2)+(4c_0c_3^2+4c_1^2c_4)c_2-(4c_0c_4+4c_1c_3)c_2^2+c_2^4$$</p> <p>$$C_3=(4c_4^3c_0-2c_4^2c_2^2)-(4c_4^2c_1)c_3+4(c_4c_2)c_3^2-c_3^4$$</p> <p>$$C_4=c_4^4$$</p> <p>while for $n=5$ we have the following (with the others obtainable by symmetry)</p> <p>$$C_0=c_0^5$$</p> <p>$$C_1=5c_0^4c_5-(5c_0^3c_4-5c_0^2c_2^2)c_1+(5c_0^2c_3)c_1^2-5c_0^3c_2c_3-(5c_0c_2)c_1^3+c_1^5$$</p> <p>$${\small C_2=(10c_0^3c_5^2-15c_0^2c_1c_4c_5+5c_0c_1^2c_4^2+5c_0^2c_3^2c_4+10c_0c_1^2c_3c_5-5c_0c_1c_3^3-5c_1^3c_3c_4)}$$ $${ \small+(5c_0^2c_4^2-15c_0^2c_3c_5+5c_1^2c_3^2-5c_0c_1c_3c_4-5c_1^3c_5)c_2}$$ $${\small +(5c_1^2c_4+10c_0c_1c_5+5c_0c_3^2)c_2^2-(5c_0c_4+5c_1c_3)c_2^3+c_2^5}$$</p> <p><strong>later thoughts</strong> In general one could consider the problem of producing from a polynomial $f(x)=\sum_{j=0}^nc_jx^j$ a polynomial $F(u)=\sum_{j=0}^nC_j u^j$ whose roots are the $m$th powers $\alpha_i^m$ of the $n$ (unknown) roots of $f$. The solution is the polynomial $\prod_{i=0}^{m-1} f(\tau^ix)$ where now $\tau$ is a primitive $m$th root of unity. This process might spread out the roots. In the case $m=2$ one has (with $q$ repeated application) $\alpha_i^{2^q}$ and the <a href="http://en.wikipedia.org/wiki/Graeffe%27s_method" rel="nofollow">Dandelin–Graeffe method</a> for finding the roots of a univariate polynomial. Splitting $f$ into its even and odd parts speeds up the computation. The method was also discovered by <a href="http://www.jstor.org/stable/2304571" rel="nofollow">Nikolai Ivanovich Lobachevsky</a> and the linked article suggests that his book <em>Algebra ili Ichislenie Konechnykh Velichin</em> discussed the general product $\prod_{i=0}^{m-1} f(\omega^ix)$. Perhaps the appropriate manipulations of symmetric polynomials are discussed there.</p> <p>Since a polynomial of degree $n$ is determined by its values at $n$ points (plus its leading coeffcient) one has the following method (which I doubt is new): Let $\zeta$ be a primitive $mn$th root of unity and $\omega$ a primitive $m$th root of unity. Then the desired polynomial $F$ satisfies $F(\zeta^j)=f(\omega^j)$ for $0 \le j \le n-1$. Now Lagrange Interpolation can be used. In this case it might be particularly simple.</p>