Problem 3

For an integer-coefficient polynomial

P(x)=a_0+a_1x+\cdots+a_kx^k

, let

w(P)

be the number of odd coefficients. Put

Q_i(x)=(1+x)^i

for

i=0,1,2,\ldots

. Prove that if

0\le i_1<i_2<\cdots<i_n

, then

w(Q_{i_1}+Q_{i_2}+\cdots+Q_{i_n})\ge w(Q_{i_1})

Step 3 of 4: Split below and above the power-of-two boundary

Previous step Next step

In plain words

Below degree $m$ and above degree $m$ live in separate shelves. A coefficient can disappear only by pairing two odd contributions, so the two lower-shelf descriptions together must cover every odd coefficient of $A$ .

w(A+B)+w(B)\ge w(A)

Detailed analysis

If $i_1<m$ , choose $r$ so that $i_r<m<i_{r+1}$ , put $A=Q_{i_1}+\cdots+Q_{i_r}$ and write the remaining terms as $(1+x)^mB$ , where $\deg A,\deg B<m$ . Modulo $2$ , the total is $A+B+x^mB$ , and the degree ranges do not overlap, so $w(Q)=w(A+B)+w(B)$ . Since $A=(A+B)+B$ in $\mathbb F_2$ , every odd coefficient of $A$ is odd in at least one of $A+B$ and $B$ ; hence $w(A+B)+w(B)\ge w(A)$ .