# Trick for roots of symmetric polynomials

Given a polynomial such as $X^4 + 4X^3 + 6X^2 + 4X + 1,$ where the coefficients are symmetrical, I know there's a trick to quickly find the zeros. Could someone please refresh my memory?

-

Hint: This particular polynomial is very nice, and factors as $(X+1)^4$.

Take a look at Pascal's Triangle and the Binomial Theorem for more details.

The particular quartic you asked about had a nice solution, but lets find all the roots of the more general $$ax^{4}+bx^{3}+cx^{2}+bx+a.$$ Since $0$ is not a root, we are equivalently finding the zeros of

$$ax^{2}+bx^{1}+c+bx^{-1}+ax^{-2}.$$Let $z=x+\frac{1}{x}$ (as suggested by Aryabhatta) Then $z^{2}=x^{2}+2+x^{-2}$ so that $$ax^{2}+bx^{1}+c+bx^{-1}+ax^{-2}=az^{2}+bz+\left(c-2a\right).$$ The roots of this are given by the quadratic formula: $$\frac{-b+\sqrt{b^{2}-4a\left(c-2a\right)}}{2a},\ \frac{-b-\sqrt{b^{2}-4a\left(c-2a\right)}}{2a}.$$ Now, we then have $$x+\frac{1}{x}=\frac{-b\pm\sqrt{b^{2}-4a\left(c-2a\right)}}{2a}$$

and hence we have the two quadratics $$x^{2}+\frac{b+\sqrt{b^{2}-4a\left(c-2a\right)}}{2a}x+1=0,$$ $$x^{2}+\frac{b-\sqrt{b^{2}-4a\left(c-2a\right)}}{2a}x+1=0.$$ This then gives the four roots:$$\frac{-b+\sqrt{b^{2}-4a\left(c-2a\right)}}{4a}\pm\sqrt{\frac{1}{4}\left(\frac{b-\sqrt{b^{2}-4a\left(c-2a\right)}}{2a}\right)^2-1}$$

$$\frac{-b-\sqrt{b^{2}-4a\left(c-2a\right)}}{4a}\pm\sqrt{\frac{1}{4}\left(\frac{b+\sqrt{b^{2}-4a\left(c-2a\right)}}{2a}\right)^2-1}.$$

If we plug in $a=1$, $b=4$, $c=6$, we find that all four of these are exactly $1$, so our particular case does work out.

-
You've lost a couple of $x$s in the two quadratics just before the roots. – Peter Taylor May 23 '11 at 17:46
Eric, could you please supply a reference for your tantalizing allusion to Aryabhatta ? – Georges Elencwajg May 23 '11 at 17:58
@Elgeorges: Sorry to disappoint, but I meant Aryabhatta, the user on MSE!! (Formely Moron, Who also posted a answer here) – Eric Naslund May 23 '11 at 18:01
+1: For spelling out in detail :-) – Aryabhata May 23 '11 at 18:26
Oops, I can't keep my promise, Eric : I had forgotten that I had already upvoted you and the software won't let me upvote you again.Sorry about that. – Georges Elencwajg May 23 '11 at 23:56

One possibility: Divide by $X^2$ and write it as a polynomial in $Z = X + 1/X$.

-

I'm not sure if this is what you are thinking of, but if $x$ is a root, and $y=1/x$, then by plugging in $1/y$ and multiplying the result by $y^n$ (where $n$ is the degree of the polynomial), we see that $y$ is also a root of the polynomial. This has two consequences. First, every root, except possibly for $X=\pm 1$ comes in pairs, and so if the polynomial is of odd degree, it must have $\pm 1$ as a root. Second, if it is of even degree, then for every root $x$, the polynomial is divisible by $(X-x)(X-1/x)=X^2-X(x+1/x)+1$. This indicates that we should be able to rewrite the polynomial in terms of $X+1/X$. We can do this as follows.

Let the polynomial be $P(X)=\sum_{i=0}^{n} a_i x^i$, where $a_i=a_{n-i}$ If $P(X)$ is of odd degree, we know that $1$ must be a root. Divide out by $X-1$ and $X+1$ until $\pm 1$ are no longer roots, and you will get an even degree polynomial with symmetric coefficients, so from here on we can assume that $n$ is even.

Divide $P(X)$ by $X^{n/2}$ to get $P(X)/X^{n/2}=a_n(X^{n/2}+1/X^{n/2})+a_{n-1}(X^{n/2-1}+1/X^{n/2-1})+\ldots$. We can write $X^k+X^{-k}$ as a polynomial in $(X+1/X)$ with symmetric coefficients, and subtracting off this chunk and repeating with the lower degree terms allows us to eventually rewrite $P(X)/X^{n/2}=Q(Z)$ where $Z=X+1/X$. Thus, we have reduced the problem to one of half the degree.

Note that we can simplify the division step with a little calculus by noting that $1$ is a root of $P(X)$ of multiplicity $k$ if $P(1)=P'(1)=P''(1)=\ldots P^{(k-1)}(1)=0$, but $P^{(k)}(1)\neq 0$, and similarly for $P(-1)$.

Also, it is worth pointing out that this is very similar to how, when you have a real polynomial, all the complex roots have to come in pairs with their conjugates, and so once you get rid of all the real roots, you can write the polynomial as a product of quadratic factors. However, the fact that we can rewrite our polynomial here in terms of $X+1/X$ has no real analogue.

-
How can $X^k + X^{-k}$ be written as a polynomial in $(X+1/X)$ with symmetric coefficients? I would compute $(X+1/X)^k$ and collect terms, but the resulting coefficients are not symmetric. For instance, $X^2 + 1/X^2 = (X+1/X)^2 - 2$. – Ricardo Buring Aug 11 '14 at 11:36
It's been a while since I wrote the statement, but I believe that what I meant was that it is symmetric in $X$ when expanded out, which should be self evident. You are correct that it is not a symmetric polynomial of $(X+1/X)$. – Aaron Aug 11 '14 at 11:48

If you use the Rational Root Theorem, you find that the only possible rational roots are $\pm 1$. You can check if either of those work and if so, divide by the corresponding factor. Then you get a simpler polynomial, and in your specific case you would be able to use the Rational Root Theorem again to get a quadratic.

EDIT: The Rational Root Theorem says that if you have a polynomial with integer coefficients, and that polynomial has a rational root $\frac{a}{b}$ where $\frac{a}{b}$ is in lowest terms, then $a$ divides the constant term and $b$ divides the leading coefficient.

-

You can write $y=x+\frac{1}{x}$ and cut the degree in half. In this case (having checked that $x$ cannot be $0$) $x^2+4x+6+\frac{4}{x}+\frac{1}{x^2}=y^2+4y+4$

-
Is that $y=x+\frac{1}{x}$? and $y^2+4y+6$? – Mitch May 23 '11 at 18:18
Yes there should be a +, but the constant term becomes 4 because you get 2 from squaring y. – Ross Millikan May 23 '11 at 20:05
argh..I was hoping it would be so much easier without having to recompute the constants (which would get that much worse for higher degree. – Mitch May 23 '11 at 21:11
Actually as the degree goes up you need to recalculate other terms as well. If you started with an eighth degree polynomial the (x+1/x)^4 supplies quadratic terms as well. But it is a triangular system. You determine the coefficients on the outer two terms by inspection, then figure out the correction to the next two, and continue. – Ross Millikan May 23 '11 at 21:21

Such a polynomial with symmetric coefficients is called a palindromic polynomial. If $x_0$ is a zero of a palindromic polynomial than $\frac{1}{x_0}$ is a zero , too. If we divide the polynomial $$Ax^4+Bx^3+Cx^2+Bx+A=0$$ by $A$ we get $$x^4+ax^3+bx^2+ax+1=0 \tag{1}$$ $$(x^4+1)+a(x^3+x)+bx^2=0$$ $$x^2(x^2+\frac{1}{x^2})+ax^2(x+\frac{1}{x})+bx^2=0$$ $$x^2\left((x^2+\frac{1}{x^2})+a(x+\frac{1}{x})+b\right)=0$$ because $x \ne0$. For the same reason we can divide the equation by $x^2$ to get

$$(x^2+\frac{1}{x^2})+a(x+\frac{1}{x})+b=0 \tag{2}$$ We set $$y=x+\frac{1}{x} \tag{3}$$ and by squaring we get $$y^2=x^2+\frac{1}{x^2}+2$$ If we substitute this in $(2)$ we get a quadratic equation of $y$ $$(y^2-2)+ay+b=0 \tag{4}$$

So $(1)$ can be solved by first solving the quadratic equation $(4)$ and then the quadratic equation $(3)$

In a similar manner the equation $$x^4+ax^3+bx^2-ax+1=0 \tag{5}$$ can be solved: $$(x^2+\frac{1}{x^2})+a(x-\frac{1}{x})+b=0$$ We set $$y=x-\frac{1}{x} \tag{6}$$ and now get $$y^2=x^2+\frac{1}{x^2}-2$$ and so $$(y^2+2)+ay+b=0 \tag{7}$$ So here we have to solve the quadratic equations $(7)$ and $(6)$ to get the solution of $(5)$.

An palindromic equation of degree $3$ can be solved by a different tick:

We transform $$x^3+ax^2+ax+1=0 \tag{8}$$ to $$(x^3+1)+a(x^2+x)=0$$ $$(x+1)\left((x^2-x+1)+ax\right)=0$$ So one solution is $$x=-1$$ This can also be seen by plugging $-1$ into $(8)$. The two other solutions are the solutions of the quadratic equation $$(x^2-x+1)+ax=0$$ Finally the equation $$x^3+ax^2-ax-1=0$$ can be transformed to $$(x^3-1)+a(x^2-x)=0$$ and therefore to $$(x-1)\left((x^2+x+1)+ax\right)=0$$

An palindromic equation of 6th or 9th degree again can be solved in two steps by solving first an equation of $y$ of degree $3$ or $4$ and then solve the equation $$y=x+\frac{1}{x}$$ The palindromic equation of degree $5$ has the solution $x=-1$ and can be reduced to an equation of degree .

The polynomial equations up to degree $4$ can be solved by radicals, so the palindromic polynomial equations of degree $5,6,8$ can be solved by radicals, too.

-