Putnam 2021, Problem A-6

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

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

Write $P(x) = a_0 + a_1x + \cdots + a_nx^n$ with $a_i \in \{0,1\}$ and $a_n = 1$. Let $\alpha$ be an arbitrary root of $P$. Since $P(\alpha) = 0$, $\alpha$ cannot be a positive real number. In addition, if $\alpha \neq 0$ then
$$|1 + a_{n-1}\alpha^{-1}| = |a_{n-2}\alpha^{-2} + \cdots + a_0\alpha^{-n}|$$
$$\leq |\alpha|^{-2} + \cdots + |\alpha|^{-n}.$$

If $\alpha \neq 0$ and $\text{Re}(\alpha) \geq 0$, then $\text{Re}(1 + a_{n-1}\alpha^{-1}) \geq 1$ and
$$1 \leq |\alpha|^{-2} + \cdots + |\alpha|^{-n} < \frac{|\alpha|^{-2}}{1 - |\alpha|^{-1}};$$
this yields $|\alpha| < (1 + \sqrt{5})/2$.

By the same token, if $\alpha \neq 0$ then
$$|1 + a_{n-1}\alpha^{-1} + a_{n-2}\alpha^{-2}| \leq |\alpha|^{-3} + \cdots + |\alpha|^{-n}.$$

We deduce from this that $\text{Re}(\alpha) \leq 3/2$ as follows.
- There is nothing to check if $\text{Re}(\alpha) \leq 0$.
- If the argument of $\alpha$ belongs to $[-\pi/4, \pi/4]$, then $\text{Re}(\alpha^{-1}), \text{Re}(\alpha^{-2}) \geq 0$, so
$$1 \leq |\alpha|^{-3} + \cdots + |\alpha|^{-n} < \frac{|\alpha|^{-3}}{1 - |\alpha|^{-1}}.$$
Hence $|\alpha|^{-1}$ is greater than the unique positive root of $x^3 + x - 1$, which is greater than $2/3$.
- Otherwise, $\alpha$ has argument in $(-\pi/2, \pi/4) \cup (\pi/4, \pi/2)$, so the bound $|\alpha| < (1 + \sqrt{5})/2$ implies that $\text{Re}(\alpha) < (1 + \sqrt{5})/(2\sqrt{2}) < 3/2$.

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

**Remark.** A theorem of Brillhart, Filaseta, and Odlyzko from 1981 states that if a prime $p$ is written as $\sum_i a_ib^i$ in any base $b \geq 2$, the polynomial $\sum_i a_ix^i$ is irreducible. (The case $b = 10$ is an older result of Cohn.) The solution given above is taken from: Ram Murty, Prime numbers and irreducible polynomials, Amer. Math. Monthly 109 (2002), 452-458). The final step is due to Pólya and Szegö.