Polynomials, Degrees, and Other Things that Rhyme With That

There are (at least) two solutions. Let me call them "Factoring" and "Brute force". In both case we need to assume that the coefficients of the polynomial are reals (see PS at the end). Also both solutions do require (in my opinion, tedious) case checking. The "factoring" solution can [probably] be improved to a case-checking-free solution.

"Factoring" solution

This property is conserved by factoring the polynomials, i.e. if two polynomials have this property, then so do their product. In fact, it is more convenient to look at the property $(*): P(x^2) = P(x) \cdot P(-x) \cdot (-1)^{\deg P}$ (otherwise there are no degree 1 solutions).

Next, note that if $a$ is a root of $P$ , then $a^2$ is also a root of $P$ . This means $a^4, a^8, a^{16},\ldots$ are also roots of $P$ . Since $P$ has finite degree, this implies that all roots are either 0 or a root of unity. Also the leading coefficient of the polynomial has to be 1. Note that roots of unity are solutions to the cyclotomic polynomials, so if we assume the coefficients of $P$ to be integers, this would reduce the case checking a lot.

So let's start by looking at degree 1 polynomials with property $(*)$ . The only possible roots here are $-1,0$ and $1$ . The actual polynomials satisfying property $(*)$ are $x$ and $x-1$ (the only excluded member here is $x+1$ ).

For degree 2, we only need to look at roots which do not occur from a degree 1 polynomial. This would mean any root of unity might pop up (because $(x-\zeta)(x-\bar{\zeta})$ has real coefficients and degree 2). Let $a$ be a $n^{\textrm{th}}$ root of unity (which is not a first, second, or third root of unity) and a root of $P$ , then $a^2$ as well as the complex conjugate of $a$ should also be roots of $P$ . [Complex conjugates need to be there since $P$ has real coefficients.] This makes $P$ of degree at least 3. And implies only the cyclotomic polynomial for the third root $x^2+x+1$ may satisty $(*)$ . And then you may check it does indeed have the property.

For degree 3, we need to check that the fourth root does not satisfy the property. Indeed, I did not show that two polynomials which do not have the property may not result in a polynomial which does (exercise?). The fourth root has a degree two polynomial ( $x^2+1$ ), which can be pumped up to degree 3 as $(x^2+1)(x+1)$ . You may check it does not have the property. The next candidate is the fifth root of unity. But the same argument as above shows that a polynomial which has property $(*)$ and has a $n^{\textrm{th}}$ root of unity as a solution has degree at least 4.

In degree 4, it is also clear that a polynomial which has property $(*)$ and admits a $n^{\textrm{th}}$ root of unity with $n \geq 7$ as a solution won't work: $a , a^2$ and $a^4$ as well as their conjugates form at least 5 distinct elements; so it cannot have degree 4. So there only remains the fifth and sixth root of unity. The 5th root of unity: $x^4+x^3+x^2+x+1$ has the property $(*)$ .
For the sixth root, we need to check that $x^2-x+1$ times some other polynomial do not have the property. The possible choices to multiply with are: $(x^2-x+1)(x^2+1)$ and $(x^2-x+1)(x+1)^2$ . It turns out the property fails for these two.

So all in all we need to build product of all the polynomials with property $(*)$ so that the result has degree 4. Our list of primitive polynomials is $x, x-1, x^2+x+1, x^4+x^3+x^2+x+1$ . So we have: $\begin{array}{c} x^4, x^3 (x-1) , x^2(x-1)^2, x(x-1)^3, (x-1)^4, \\ (x^2+x+1)^2, (x^2+x+1)x^2 , (x^2+x+1)x(x-1), (x^2+x+1)(x-1)^2,\\ \textrm{and} \qquad x^4+x^3+x^2+x+1 \end{array}$ So we have in total $\fbox{10}$ solutions.

Side note: If we knew that $P$ has integer coefficients, then we could focus on the cyclotomic polynomials (there is a list of cyclotomic polynomials on Wikipedia). For example, in degree two, we need only to check the polynomials $x^2-x+1$ , $x^2+1$ and $x^2+x+1$ . In degree 4, we need only to check $x^4+x^3+x^2+x+1$ , $x^4+1$ , $x^4-x^3+x^2-x+1$ and $x^4-x^2+1$ . This would make the case checking easier.

Alternatively, here are two improvements which would make the case checking disappear:

Improvement 1: Show that a polynomial has property $(*)$ if and only each of its factors has it.

Improvement 2: Show that the cyclotomic polynomials with property $(*)$ are exactly the odd ones (those of the third, 5th, 7th, 9th, 11th, ... roots of unity)!

Number of polynomials with property $(*)$ : if the improvements above are correct, then the number of polynomials of degree $n$ with this property is given by the power of $x^n$ in the power series expansion of $\frac{1}{1-x} \prod_{i=1}^\infty \frac{1}{1-x^{\phi(2i+1)}}$ (you probably need to truncate the product before making the expansion). This gives the sequence 1,2,4,6,10,14,22,30,44,58,... which is not in the OEIS.

"Brute force" solution

Write $P(x) = a x^{4} + b x^{3} + c x^{2} + d x + e$ . Then $P(x^2) = a x^{8} + b x^{6} + c x^{4} + d x^2 + e$ while $P(x) \cdot P(-x) = a^{2} x^{8} + (- b^{2} + 2 \, a c ) x^{6} + (c^{2} - 2 \, b d + 2 \, a e ) x^{4} + (- d^{2} + 2 \, c e ) x^{2} + e^{2}$ This yields five equations: $\begin{array}{rl} a &= a^{2} \\ b &=- b^{2} + 2 \, a c \\ c &=c^{2} - 2 \, b d + 2 \, a e \\ d &= - d^{2} + 2 \, c e \\ e &= e^2 \\ \end{array}$ The first equation $a = a^2$ has possible solutions $a=0$ and $a=1$ . But $a =0$ would mean the polynomial does not have degree 4. So $a=1$ .

The last equation $e = e^2$ has two possible solutions $e=0$ and $e=1$ . This splits the problem in two cases:

• Case $e=0$ : The remaining equations are $\begin{array}{rl} b &=- b^{2} + 2 \, c \\ c &=c^{2} - 2 \, b d \\ d &= - d^{2} \\ \end{array}$ The solutions may be found by further case checking (the next two sub-cases are $d=0$ or $d=-1$ , coming from the last equation). The solution list reads: $\begin{array}{cccc} b = 0, &c = 0, &d = 0, &e = 0 \\ b = 0, &c = 0, &d = -1, &e = 0 \\ b = 1, &c = 1, &d = 0, &e = 0 \\ b = -1, &c = 0, &d = 0, &e = 0 \\ b = -2, &c = 1, &d = 0, &e = 0 \\ b = -3, &c = 3, &d = -1, &e = 0 \\ \end{array}$
• Case $e=1$ : The remaining equations are $\begin{array}{rl} b &=- b^{2} + 2 \, c \\ c &=c^{2} - 2 \, b d + 2 \\ d &= - d^{2} + 2 \, c \\ \end{array}$ Here one can [needs to?] be more careful. From the first and the third equation one gets: $b+b^2 = d+ d^2$ . Looking at the graph of the function $x^2+x$ , one sees that there are two possibilities: $b=d$ or $b = -1 -d$ . If there are not equal then they have either opposite sign (in which case the middle equation has no real solution) or they are both negative and in the interval $[-1,0]$ (and again the middle equation has no solution, since their product is at most $\frac{1}{4}$ ). So $b=d$ . And we are left with the equations: $\begin{array}{rl} b &=- b^{2} + 2 \, c \\ c &=c^{2} - 2 \, b^2 + 2 \\ \end{array}$ Now you can use the first equation to get $c = \frac{1}{2} (b+b^2)$ . Using this in the second equation gives you a degree 4 equation for $b$ : $b^{4} + 2 \, b^{3} - 9 \, b^{2} - 2 \, b + 8 =0$ You can solve this by hand (because it turns out the solutions are all integers). The first obvious solution is $b=1$ (because the coefficients add to 0). After factoring out there remains a degree 3 polynomial: $b^{3} + 3 \, b^{2} - 6 \, b - 8 =0$ This time there is another "easy" solution $b = -1$ (since the alternate sum of the coefficients is 0). So we are left with a degree 2 polynomial: $b^{2} + 2 \, b - 8 =0$ And now the other two solutions are easy to find: $b=-4$ and $b=2$ . So the list of solutions (when $e=1$ ) is: $\begin{array}{cccc} b = 2,& c = 3, &d = 2, &e = 1\\ b = 1, & c = 1, &d = 1, &e = 1 \\ b = -1, &c = 0, &d = -1, &e = 1\\ b = -4, &c = 6, &d = -4, &e = 1 \\ \end{array}$ We now have in total $\fbox{10}$ solutions.

PS: there are also 6 extra complex solutions $\begin{array}{cccc} b = (-\imath \cdot\sqrt{7} + 1)/2,& c = -(\imath \cdot\sqrt{7} +1)/2,& d = -1,& e = 0 \\ b = (\imath \cdot\sqrt{7} + 1)/2,& c = (\imath \cdot\sqrt{7} - 1)/2,& d = -1,& e = 0 \\ b = -(\imath \cdot\sqrt{15} + 1)/2,& c = -2,& d = -8/(\imath \cdot\sqrt{15} + 1),& e = 1 \\ b = (\imath \cdot\sqrt{15} - 1)/2,& c = -2,& d = 8/(\imath \cdot\sqrt{15} - 1),& e = 1 \\ b = -(\imath \cdot\sqrt{7} + 1)/2,& c = -1,& d = -4/(\imath \cdot\sqrt{7} + 1),& e = 1 \\ b = (\imath \cdot\sqrt{7} - 1)/2,& c = -1,& d = 4/(\imath \cdot\sqrt{7} - 1),& e = 1 \\ \end{array}$