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

  • $\begingroup$ $P$ is non constant also (it is clear that it is understood but......). $\endgroup$ – Piquito Nov 5 '18 at 13:21
  • $\begingroup$ @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 $\endgroup$ – Charles Madeline Nov 5 '18 at 13:40
  • $\begingroup$ 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? $\endgroup$ – Najib Idrissi Nov 5 '18 at 13:49
  • $\begingroup$ @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 $\endgroup$ – Charles Madeline Nov 5 '18 at 13:59
  • $\begingroup$ Right. But it still has two odd coefficients. There's no connection... $\endgroup$ – 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$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.