How can I show that if $m ≥ 2^k $(with k ≥ 2 integer), then $n ≥ 2^{k + 1} -1$?

Question

Let $m, n$ be positive integers and $P ∈ Z [X] $ a polynomial of degree $n$ such that all its coefficients are odd. Assume that $(x - 1)^m$ divides $P$. How can I show that if $m ≥ 2^k $(with k ≥ 2 integer), then $n ≥ 2^{k + 1} -1$?

Answer 1

Given a polynomial $P$ which verifies your problem, we will work in $\mathbb{F_2}[X]$ the ring of polynomials over the field $\mathbb{Z_2}$, so let us write the condition of divisibility : $$P(X)=(X-1)^{m}Q(X)$$ it's clear that we have to shox the inequality only for $m=2^k$ the rest follows easily, so let's suppose that $m=2^k$. if we reduce this equality in $\mathbb{F_2}[X]$ we obtain (because the coefficients are all odd): $X^n + X^{n - 1} + \cdots + X + 1 =\left( X - 1 \right)^{2^k}\overline{R}\left(X\right) =\left(X^{2^k} - 1\right)\overline{R}\left(X\right)$

I think the equality $\left(X - 1\right)^{2^k}=(X^{2^k} - 1) $ is clear. This can also be written in the form : $X^n + X^{n - 1} + \cdots + X + 1 =X^{2^k}\overline{R}(X)+\overline{R}(x)$

now if we look to the coefficient of $X^{2^k-1}$ in this equality, this coefficient must be $1$ according to the first term, hence this coefficient must be $1$ also in $\overline{R}$ so: $deg(\overline{R})\geq 2^k-1$ which implies that $n=2^k+deg(\overline{R})\geq 2^{k+1}-1$.