# Even polynomial having multiple with odd coefficients

Let $$Q \in \mathbb{Z}/2\mathbb{Z}[X]$$ be a non constant polynomial such that all coefficients of odd order are $$0$$, i.e. $$Q = \sum a_k X^{2k}$$. Show that if $$P \in \mathbb{Z}/2\mathbb{Z}[X]$$ is such that all the coefficients of $$PQ$$ are odd, then the degree of $$P$$ is odd.

This is a conjecture that I made. I believe it is true but have no proof for it.

At first I thought that no multiples of $$Q$$ could have all coefficients odd. I quickly found counterexamples : $$(1+X^2)*(1+X) = 1+X+X^2+X^3$$

and more generally, for any even $$n$$, $$\Big(\sum \limits_{k=0}^m X^{kn}\Big)\cdot \Big(\sum\limits_{k=0}^{m-1} X^k\Big) = \sum \limits_{k=0}^{(m+1)n-1} X^k$$

I also found weirder counterexamples, like $$(1+X^4+X^6)(1+X+X^2+X^3+X^6+X^7)=\sum\limits_{k=0}^{13} X^k + 2X^7+2X^6$$

I could not find polynomials with odd degree. I tried to work in $$\mathbb{Z}/2\mathbb{Z}$$ and get information on the coefficients but it was not really conclusive. If $$Q$$ can be written $$\sum\limits_{k=0}^m X^{kn}$$ for some even $$n$$, then I have a proof, but in the general case, the coefficients of $$Q$$ can be quite random (see my last example).



*Note: this problem arose during a math contest, which ended on 04/11/2018

• $P$ is non constant also (it is clear that it is understood but......). – Piquito Nov 5 '18 at 13:21
• @Piquito Actually $P$ cannot be constant : $Q$ is not constant, so it has at least one zero coefficient (the coeff with $X$). $P$ can be either odd or even, the $X$ coefficient of $PQ$ will always be zero. Which is not odd – Charles Madeline Nov 5 '18 at 13:40
• I don't see any reason why this conjecture or anything similar would be true. There's no link between the parity of the polynomial function $P$ and the parity of the coefficients of $P$. The polynomial $P(x) = 1+x^2$ is even, and yet all its coefficients are odd... What do you base this conjecture on? – Najib Idrissi Nov 5 '18 at 13:49
• @NajibIdrissi $P = 1 + 0\cdot X + X^2$ does not have only odd coefficients. All the coefficients before the terms $X^{2k+1}$ are zero (and thus even) for an even polynomial – Charles Madeline Nov 5 '18 at 13:59
• Right. But it still has two odd coefficients. There's no connection... – Najib Idrissi Nov 5 '18 at 14:01

It's true in general. It suffices to show that $$PQ$$ has odd degree. Suppose to the contrary that there exist some $$P,Q\in\mathbb F_2[x]$$ subject to the constraints outlined in the OP for which $$PQ=1+x+\cdots+x^{2n}=\frac{x^{2n+1}-1}{x-1}$$. Observe by Frobenius that $$\sum a_kx^{2k}=\left(\sum a_kx^k\right)^2$$ in $$\mathbb F_2[x]$$. We shall prove that $$1+x+\cdots+x^{2n}$$ is squarefree; this clearly implies the result. Indeed, \begin{align*}\gcd\left(1+x+\cdots+x^{2n},\left(1+x+\cdots+x^{2n}\right)'\right)&=\gcd\left(1+x+\cdots+x^{2n},1+x^2+\cdots+x^{2n-2}\right)\\&=\gcd\left(1+x+\cdots+x^{2n},\left(1+x+\cdots+x^{n-1}\right)^2\right)\\&=\gcd\left(\tfrac{x^{2n+1}-1}{x-1},\left(\tfrac{x^{n}-1}{x-1}\right)^2\right)=1\end{align*} Where the last equality follows from the identity $$\gcd(x^m-1,x^n-1)=x^{\gcd(m,n)}-1$$ $$\blacksquare$$