Maths Olympiad Prep

Library / /49 of 64

Algebra Difficulty 8.1 Shortlist Find the answer

Let P(x)P(x) be a polynomial whose coefficients are all either 00 or 11. Suppose that P(x)P(x) can be written as a product of two nonconstant polynomials with integer coefficients. Does it follow that P(2)P(2) is a composite integer?

A number or a short expression. Spacing and $ signs are ignored.

Solution

Yes, it follows that P(2)P(2) is a composite integer. (Note: 1 is neither prime nor composite.)

Write P(x)=a0+a1x++anxnP(x) = a_0 + a_1 x + \cdots + a_n x^n with ai{0,1}a_i \in \{0,1\} and an=1a_n = 1.
Let α\alpha be an arbitrary root of PP. Since P(α)=0P(\alpha) = 0, α\alpha cannot be a positive real number.
%In addition, if α0\alpha \neq 0 then
%\begin{align*} %1 &< |a_{n-1} \alpha^{-1} + \cdots + a_0 \alpha^{-n}| \\ %&\leq |\alpha|^{-1} + \cdots + |\alpha|^{-n} %\end{align*}
%and so α<2|\alpha| < 2.
%
In addition, if α0\alpha \neq 0 then
1+an1α1=an2α2++a0αnα2++αn.\begin{align*} |1 + a_{n-1} \alpha^{-1}| &= |a_{n-2} \alpha^{-2} + \cdots + a_0 \alpha^{-n}| \\ &\leq |\alpha|^{-2} + \cdots + |\alpha|^{-n}. \end{align*}
If α0\alpha \neq 0 and Re(α)0\mathrm{Re}(\alpha) \geq 0, then Re(1+an1α1)1\mathrm{Re}(1 + a_{n-1} \alpha^{-1}) \geq 1
and
1α2++αn<α21α1; 1 \leq |\alpha|^{-2} + \cdots + |\alpha|^{-n} < \frac{|\alpha|^{-2}}{1 - |\alpha|^{-1}};
this yields α<(1+5)/2|\alpha| < (1 + \sqrt{5})/2.

By the same token, if α0\alpha \neq 0 then
1+an1α1+an2α2α3++αn. |1 + a_{n-1} \alpha^{-1} + a_{n-2} \alpha^{-2}| \leq |\alpha|^{-3} + \cdots + |\alpha|^{-n}.
We deduce from this that Re(α)3/2\mathrm{Re}(\alpha) \leq 3/2 as follows.
\begin{itemize}
\item
There is nothing to check if Re(α)0\mathrm{Re}(\alpha) \leq 0.
\item
If the argument of α\alpha belongs to [π/4,π/4][-\pi/4, \pi/4], then Re(α1),Re(α2)0\mathrm{Re}(\alpha^{-1}), \mathrm{Re}(\alpha^{-2}) \geq 0, so
1α3++αn<α31α1. 1 \leq |\alpha|^{-3} + \cdots + |\alpha|^{-n} < \frac{|\alpha|^{-3}}{1 - |\alpha|^{-1}}.
Hence α1|\alpha|^{-1} is greater than the unique positive root of x3+x1x^3 + x - 1, which
is greater than 2/32/3.
\item
Otherwise, α\alpha has argument in (π/2,π/4)(π/4,π/2)(-\pi/2,\pi/4) \cup (\pi/4,\pi/2),
so the bound α<(1+5)/2|\alpha| < (1 + \sqrt{5})/2 implies that Re(α)<(1+5)/(22)<3/2\mathrm{Re}(\alpha) < (1 + \sqrt{5})/(2 \sqrt{2}) < 3/2.
\end{itemize}

By hypothesis, there exists a factorization P(x)=Q(x)R(x)P(x) = Q(x)R(x) into two nonconstant integer polynomials, which we may assume are monic.
Q(x+3/2)Q(x + 3/2) is a product of polynomials, each of the form xαx - \alpha where α\alpha is a real root of PP
or of the form
(x+32α)(x+32α)=x2+2Re(32α)x+32α2\begin{align*} &\left( x + \frac{3}{2} - \alpha\right) \left(x + \frac{3}{2} - \overline{\alpha} \right) \\ &\quad = x^2 + 2 \mathrm{Re}\left(\frac{3}{2} - \alpha\right) x + \left|\frac{3}{2} - \alpha \right|^2 \end{align*}
where α\alpha is a nonreal root of PP. It follows that Q(x+3/2)Q(x+3/2) has positive coefficients;
comparing its values at x=1/2x=1/2 and x=1/2x=-1/2 yields Q(2)>Q(1)Q(2) > Q(1). We cannot have Q(1)0Q(1) \leq 0, as otherwise the intermediate value theorem would imply that QQ has a real root in [1,)[1, \infty); hence Q(1)1Q(1) \geq 1 and so Q(2)2Q(2) \geq 2.
Similarly R(2)2R(2) \geq 2, so P(2)=Q(2)R(2)P(2) = Q(2) R(2) is composite.

\textbf{Remark.}
A theorem of Brillhart, Filaseta, and Odlyzko from 1981 states that if a prime pp is written as iaibi\sum_i a_i b^i in any base b2b \geq 2, the polynomial iaixi\sum_i a_i x^i is irreducible.
(The case b=10b=10 is an older result of Cohn.)
The solution given above is taken from: Ram Murty, Prime numbers and irreducible polynomials, \textit{Amer. Math. Monthly} \textbf{109} (2002), 452--458). The final step is due to P\'olya and Szeg\H{o}.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.