Monic Polynomials — a problem for RMO and INMO


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:


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













Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s