Maths Olympiad Prep

Library / Putnam /46 of 60

Putnam

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. Fractions can be typed as 3/2, and spacing doesn't matter.

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
%1 < |a n-1 -1 + + a 0 -n | | | -1 + + | | -n\text{1 < |a n-1 -1 + + a 0 -n | | | -1 + + | | -n}
%and so ∣α∣<2|\alpha| < 2.
%
In addition, if α≠0\alpha \neq 0 then
∣1+an−1α−1∣=∣an−2α−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+an−1α−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+an−1α−1+an−2α−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.
\text{}
There is nothing to check if Re(α)≤0\mathrm{Re}(\alpha) \leq 0.
\text{}
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+x−1x^3 + x - 1, which
is greater than 2/32/3.
\text{}
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.
\text{}

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.

Remark.\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 b≥2b \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, Amer.\textit{Amer.} Math. Monthly} 109\textbf{109} (2002), 452--458). The final step is due to P\'olya and Szego˝.Szeg\H{o}.

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

Source: Omni-MATH, licensed Apache-2.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.