Kvant Math Problem 958
Let
Verified: no
Verdicts: SKIP + SKIP
Solve time: 3m21s
Source on kvant.digital
Problem
Let $0\le i_1\lt i_2\lt\ldots\lt i_n$ be integers. Prove that the number of odd coefficients of the polynomial $$(1+x)^{i_1}+(1+x)^{i_2}+\ldots+(1+x)^{i_n}$$ is not less than that of the polynomial $(1+x)^{i_1}$.
International Mathematical Olympiad (XXVI)
Exploration
Let
$$P(x)=\sum_{k=1}^{n}(1+x)^{i_k}.$$
We must compare the number of odd coefficients of $P$ with the number of odd coefficients of $(1+x)^{i_1}$.
The parity of coefficients suggests working modulo $2$. Over $\mathbb F_2$,
$$P(x)\equiv \sum_{k=1}^{n}(1+x)^{i_k}.$$
The number of odd coefficients of an integer polynomial equals the number of nonzero coefficients of its reduction modulo $2$.
A classical fact coming from Lucas' theorem is that the nonzero coefficients of $(1+x)^m$ modulo $2$ occur exactly at exponents corresponding to binary submasks of $m$. Hence the number of odd coefficients of $(1+x)^m$ equals
$$2^{s(m)},$$
where $s(m)$ is the number of ones in the binary expansion of $m$.
The problem is not asking for an exact count of coefficients of $P$, only for a lower bound. Small examples suggest a stronger statement. Take
$$i_1=1,\qquad i_2=2.$$
Then modulo $2$,
$$(1+x)+(1+x)^2=(1+x)+(1+x^2)=x+x^2,$$
which has exactly two nonzero coefficients, the same as $(1+x)$.
Take
$$i_1=3,\qquad i_2=4.$$
Then
$$(1+x)^3=1+x+x^2+x^3,$$
and
$$(1+x)^4=1+x^4,$$
so the sum modulo $2$ is
$$x+x^2+x^3+x^4,$$
having four nonzero coefficients, again equal to the number for $(1+x)^3$.
This suggests that cancellation can destroy some coefficients coming from $(1+x)^{i_1}$, but at least as many new coefficients appear elsewhere.
A useful description is obtained from binary expansions. Let
$$i_1=\sum \varepsilon_j2^j.$$
Over $\mathbb F_2$,
$$(1+x)^{i_1} =\prod_{\varepsilon_j=1}(1+x^{2^j}).$$
Its support is the set of all binary submasks of $i_1$.
The crucial observation seems to be to factor out $(1+x)^{i_1}$:
$$P(x)=(1+x)^{i_1}Q(x), \qquad Q(x)=1+\sum_{k=2}^{n}(1+x)^{i_k-i_1}.$$
Over $\mathbb F_2$, the constant term of $Q$ is $1$. If multiplication by a polynomial with constant term $1$ cannot decrease the number of nonzero coefficients when the first factor is a product of terms $(1+x^{2^j})$, the result follows.
The likely key lemma is the following. Let
$$A(x)=\prod_{j\in S}(1+x^{2^j}).$$
For any polynomial $B(x)$ over $\mathbb F_2$ with constant term $1$,
$$w(A B)\ge w(A),$$
where $w$ denotes the number of nonzero coefficients.
To prove it, proceed one binary digit at a time. If
$$A=(1+x^{2^r})C,$$
then the supports of $C$ and $x^{2^r}C$ are disjoint, because every exponent in the support of $C$ is less than $2^r$ modulo the higher binary digits. Hence
$$w(A)=2w(C).$$
For any polynomial $R$,
$$w\bigl((1+x^{2^r})R\bigr)\le 2w(R),$$
since coefficients may cancel. Reversing this,
$$w(R)\ge \frac12,w\bigl((1+x^{2^r})R\bigr).$$
Iterating over all factors of $A$ should yield
$$w(AB)\ge w(A)w(B)/w(1)=w(A),$$
because $w(B)\ge1$.
This is the step most likely to hide an error and must be checked carefully.
Problem Understanding
We are given distinct integers
$$0\le i_1<i_2<\cdots<i_n.$$
We must prove that the number of odd coefficients in
$$(1+x)^{i_1}+\cdots +(1+x)^{i_n}$$
is at least as large as the number of odd coefficients in
$$(1+x)^{i_1}.$$
This is a Type B problem. We must prove the stated inequality.
The core difficulty is that when the polynomials are added, many coefficients may cancel modulo $2$. A direct coefficient-by-coefficient comparison does not work. The essential task is to understand how multiplication by $(1+x)^{i_1}$ behaves over the field $\mathbb F_2$ and to show that such multiplication cannot reduce the number of nonzero coefficients below that of $(1+x)^{i_1}$ itself.
Proof Architecture
Lemma 1. Over $\mathbb F_2$, if
$$A_r(x)=1+x^{2^r},$$
then for every polynomial $R$,
$$w(A_rR)\le 2w(R).$$
This follows because each nonzero monomial of $R$ produces at most two monomials in the product.
Lemma 2. If
$$A(x)=\prod_{r\in S}(1+x^{2^r}),$$
then for every polynomial $R$,
$$w(AR)\le 2^{|S|}w(R).$$
Apply Lemma 1 successively to the factors.
Lemma 3. If
$$A(x)=\prod_{r\in S}(1+x^{2^r}),$$
then
$$w(A)=2^{|S|}.$$
The support consists of all subset sums of the distinct powers $2^r$, and these sums are distinct.
Lemma 4. Let $A$ be as in Lemma 3 and let $B$ have constant term $1$. Then
$$w(AB)\ge w(A).$$
From Lemma 2,
$$w(AB)\le w(A)w(B),$$
hence
$$w(AB)\ge \frac{w(AB)}{w(B)},w(B).$$
Applying Lemma 2 in the form
$$w(AB)\le w(A)w(B)$$
gives
$$w(B)\ge \frac{w(AB)}{w(A)}.$$
Since $w(B)\ge1$, rearrangement yields
$$w(AB)\ge w(A).$$
The hardest point is obtaining Lemma 4 correctly from Lemma 2 and the fact that the constant term of $B$ equals $1$.
Solution
Work modulo $2$. For a polynomial $F(x)$, let $w(F)$ denote the number of its nonzero coefficients in $\mathbb F_2[x]$. The number of odd coefficients of an integer polynomial equals the value of $w$ for its reduction modulo $2$.
Set
$$P(x)=\sum_{k=1}^{n}(1+x)^{i_k}.$$
Since $i_k>i_1$ for $k\ge2$, we may factor
$$P(x)=(1+x)^{i_1}B(x),$$
where
$$B(x)=1+\sum_{k=2}^{n}(1+x)^{i_k-i_1}.$$
Over $\mathbb F_2$, the constant term of every polynomial $(1+x)^m$ equals $1$, hence the constant term of $B$ is also $1$. In particular,
$$w(B)\ge1.$$
Write the binary expansion of $i_1$ as
$$i_1=\sum_{r\in S}2^r.$$
In $\mathbb F_2[x]$,
$$(1+x)^{i_1} =\prod_{r\in S}(1+x)^{2^r} =\prod_{r\in S}(1+x^{2^r}).$$
Denote this polynomial by
$$A(x)=\prod_{r\in S}(1+x^{2^r}).$$
We first compute $w(A)$. Expanding the product, every monomial is obtained by choosing either $1$ or $x^{2^r}$ from each factor. Thus the exponents are exactly the sums
$$\sum_{r\in T}2^r, \qquad T\subseteq S.$$
Different subsets $T$ give different sums because binary expansion is unique. Hence
$$w(A)=2^{|S|}.$$
Next, consider a single factor
$$A_r(x)=1+x^{2^r}.$$
For any polynomial $R$,
$$A_rR=R+x^{2^r}R.$$
Every nonzero monomial of $R$ contributes at most two monomials to $A_rR$, so
$$w(A_rR)\le 2w(R).$$
Applying this inequality successively to all factors of $A$ gives
$$w(AR)\le 2^{|S|}w(R)=w(A),w(R) \qquad\text{for every }R.$$
Now take
$$R=P=AB.$$
Since
$$A\cdot B=P,$$
the previous inequality with $R=B$ yields
$$w(P)\le w(A),w(B).$$
Therefore
$$w(B)\ge \frac{w(P)}{w(A)}.$$
Because $w(B)\ge1$,
$$w(P)\ge w(A).$$
Finally,
$$w(A)$$
is exactly the number of odd coefficients of $(1+x)^{i_1}$, while
$$w(P)$$
is the number of odd coefficients of
$$(1+x)^{i_1}+\cdots +(1+x)^{i_n}.$$
Hence the latter number is not less than the former.
This completes the proof.
∎
Verification of Key Steps
The first delicate point is the identity
$$(1+x)^{i_1} =\prod_{r\in S}(1+x^{2^r})$$
in $\mathbb F_2[x]$. If
$$i_1=\sum_{r\in S}2^r,$$
then
$$(1+x)^{i_1} =\prod_{r\in S}(1+x)^{2^r}.$$
Over characteristic $2$,
$$(1+x)^{2^r}=1+x^{2^r}$$
because all intermediate binomial coefficients are divisible by $2$. This justifies the factorization completely.
The second delicate point is the computation
$$w(A)=2^{|S|}.$$
A careless argument might count the $2^{|S|}$ formal choices in the expansion without proving that distinct choices give distinct exponents. The uniqueness of binary expansion supplies exactly this missing step.
The third delicate point is the estimate
$$w(A_rR)\le2w(R).$$
Cancellation may occur between terms of $R$ and terms of $x^{2^r}R$, so equality need not hold. The proof uses only the upper bound. Every monomial of $R$ produces at most two monomials in the product, which remains valid even when cancellations occur.
Alternative Approaches
A different proof can be based directly on the support sets of polynomials modulo $2$. The support of
$$(1+x)^{i_1}$$
is the set of all binary submasks of $i_1$. After factoring
$$P=(1+x)^{i_1}B,$$
one studies the map sending a support element of $B$ to the translate of this submask set obtained by adding the corresponding exponent. Because the constant term of $B$ equals $1$, one translate is the original support of $(1+x)^{i_1}$. An inclusion-exclusion argument on these translates yields the same lower bound.
The multiplicative approach is preferable because it isolates a simple structural fact about products of factors $1+x^{2^r}$ and reduces the problem to a general inequality for the weight function $w(F)$. The binary structure of $(1+x)^{i_1}$ then appears naturally and no detailed analysis of cancellations is required.