# Monic Polynomials — a problem for RMO and INMO

Problem:

Prove that if the polynomial $X^{n}+X^{n-1}+ \ldots + X +1$ can be written as the product of two monic polynomials with real non-negative coefficients, then those coefficients are all 0 or 1.

Proof by Andrei Stefanescu:

Definition:

We call any polynomial $P(X)=a_{n}X^{n}+\ldots+a_{0}$ symmetrical if and only if $a_{i}=a_{n-i}$ for all i. We will use the following lemma:

LEMMA: If P is a polynomial which can be written as $P=Q.R$, where Q and R are symmetrical polynomials, then P is symmetrical too.

Let $Q(X)=b_{s}X^{s}+ \ldots + b_{0}$ and $R(X)=c_{t}X^{t}+\ldots+c_{0}$. We have that $a_{i}=\sum_{j=0}^{i}b_{j}c_{i-j}$ and $a_{n-i}=\sum_{j=0}^{i}b_{s-j}c_{t-(i-j)}$. Since Q and R are symmetrical, it follows that $b_{j}=b_{s-j}$ and $c_{i-j}=c_{t-(i-j)}$. Hence, $a_{i}=a_{n-i}$ for any i, and thus P is symmetrical.

Let $f(X)=X^{n}+X^{n-1}+ \ldots+1$ and assume that $f=g.h$, where g and h are nonconstant polynomials with non-negative coefficients. Let $g(X)=b_{s}X^{s}+\ldots + b_{0}$ and $h(X)=c_{t}X^{t}+\ldots + c_{0}$. Since $f=g.h$, all the complex roots of  g and h have absolute value 1. Also, if $g(\in)=0$, then $g(\overline{\in}) = g(\frac{1}{\in})=0$. It follows that both g and h are a product of symmetric terms of the form $(X-\in)(X-\frac{1}{\in}) = X^{2}-2\Re (\in)+1$ or $X+1$, hence by lemma, g and h are symmetrical.

If all the coefficients of g and h are in $\{0,1\}$ we are done. Otherwise, let k be the least number such that $\{ b_{k},c_{k} \}$ is not a subset of $\{ 0,1\}$. Since $b_{s}=c_{t}=1$, it follows that $b_{0}=c_{0}=1$, thus $k \geq 1$. As g is symmetrical, $b_{k}=b_{s-k}$. Computing the coefficient of $X^{s}$ gives us $1=b_{s}c_{0}+\ldots+b_{s-k}c_{k}+\ldots+b_{0}c_{s}$. Since $b_{s}=c_{0}=1$ and all the terms of the sum are non-negative, we obtain $b_{s-k}c_{k}=b_{k}c_{k}=0$, thus one of $b_{k}$ and $c_{k}$ (say, $c_{k}$)is 0. Computing the coefficient of $X^{k}$, we have $1=b_{k}c_{0}+\ldots + b_{0}c_{k}$. As $\{ b_{i},c_{i}\} \subset \{ 0,1\}$ for $i < k$ and $c_{k}=0$, all the terms but $b_{k}c_{0}$ must be in $\{ 0,1\}$. It follows that $b_{k}c_{0}=b_{k}$ must be in $\{ 0,1\}$, which leads to a contradiction with the definition of k.

More later,

Nalin Pithwa