Irreducible polynomial in $\Bbb{Z}_2[x]$

Question

Suppose $2k + 1 \equiv 3 \mod 4$ in $\Bbb{Z}_{\geq 1}$.

Is the polynomial: $p_k(x) = x^{2k + 1} + x^{2k - 1} \dots + x + 1$ irreducible in $\Bbb{Z}_2[x]$?

I do not know whether it is true or not...

(Side note: I've had a question in a test that is solved immediately if the statement above turns out to be true (a two parted question that would be solved by proving a single statement). The question was much simpler then trying to prove/disprove the above statement but I missed the easy way (very unfortunately and quite disappointingly after so much preparation and work). I decided to go about it my own way, brute forcing instead of trying to think outside the box.)

The idea I had in mind - the statement is true:

Suppose for the sake of contradiction that $p_k$ is reducible and suppose $g, f \in \Bbb{Z}_2[x]$ are such that $gf = p_k$ and $\deg(f), \deg(g) \geq 1$. Also w.l.o.g $\deg f > \deg g$.

Denote $$ f = x^s + b_{s - 1}x^{s - 1} + \dots + b_1 x + 1 \\ g = x^r + a_{r - 1}x^{r - 1} + \dots + a_1 x + 1 $$

Note then, that $r + s = 2k + 1$ so either $r$ is even and $s$ is odd or vice versa. Suppose $r$ is even and $s$ is odd.

We now proceed to equate the coefficients between $fg$ and $p_k$.

Also, $a_1 + b_1 \equiv 1 \mod 2$ because the coefficient of $x$ in $p_k$. Suppose $b_1 \equiv 0 \mod 2 \wedge a_1 \equiv 1 \mod 2$.

Now for the coefficient of $x^2$ we have $a_1b_1 + a_2 + b_2 \equiv a_2 + b_2 \mod 2 \equiv 0 \mod 2$. Yielding yet again two possibilities. Suppose $a_2 \equiv b_2 \mod 2 \equiv 1 \mod 2$.

And in general we can say: $$ a_l + b_l + \sum_{i = 1}^{l - 1}a_i b_{l - i} \equiv \cases{1 \mod 2 & l is odd \\ 0 \mod 2 & l is even} $$ Where $l \in \{1, 2, 3, \dots, r + s - 1\}$. I think maybe I need to prove that all the even powers must reside in $f$ where all the odd powers must reside in $g$ and get a contradiction in some way. But I really don't know what I should do. Maybe induction? But what is the hypothesis?

Thank you for your trouble! And I am sorry if what I've tried above is confusing and unclear. I had no time to think when I tried to solve it and I am kind of stuck now.

Answer 1

The answer is no. The first counterexample is \begin{multline*} x^{23}+x^{21}+x^{19}+x^{17}+x^{15}+x^{13}+x^{11}+x^9+x^7+x^5+x^3+x+1 \\= \left(x^3+x^2+1\right) \left(x^4+x+1\right) \left(x^{16}+x^{15}+x^{12}+x^{10}+x^9+x^8+x^4+x^2+1\right). \end{multline*} Among the odd values of $k$ up to $200$, there are $15$ irreducible polynomials and $85$ reducible polynomials of this form.

Answer 2

Some simple (non-computer) ways of seeing the existence of non-trivial factors. In the end I prove that every primitive polynomial $\in \Bbb{F}_2[x]$ of degree $>2$ is a factor of infinitely many polynomials of this type.

---

I reindex the polynomials and call $P_\ell(x)$ the polynomial with degree $4\ell-1$. The geometric sum formula tells us that $$ P_\ell(x)=1+x\frac{1+x^{4\ell}}{1+x^2}. $$ So an element $\alpha\in K:=\overline{\Bbb{F}_2}$ is a root of $P_\ell(x)$, if $\alpha\neq1$ and $$ \alpha(1+\alpha^{4\ell})=1+\alpha^2.\qquad(*) $$ Because $\alpha\notin \Bbb{F}_2$, it is a root of unity of some order $M$. From equation $(*)$ it thus follows that if $\alpha$ is a root of $P_\ell(x)$, it is also a root of $P_k(x)$ for all $k\equiv \ell\pmod M$. In other words $P_\ell(x)$ has a non-trivial common factor with all the polynomials $P_{\ell+j M}(x)$, $j=1,2,3,\ldots$.

For example the polynomial $P_1(x)=x^3+x+1$ is a well-known irreducible. Its roots have order $M=7$, because $7=2^3-1$ is a Mersenne prime. Consequently $P_1(x)$ is a factor of $P_8(x)$, $P_{15}(x)$ etc. Indeed, (firing up Mathematica) $$ P_8(x)=\left(x^3+x+1\right) \left(x^7+x^6+x^5+x^3+x^2+x+1\right) \left(x^{21}+x^{20}+x^{16}+x^{14}+x^{13}+x^9+x^8+x^7+x^6+x^5+x ^4+x+1\right). $$ Similarly, $P_2(x)=1+x+x^3+x^5+x^7$ is also irreducible (less well known but still doable by paper & pencil). As $2^7-1=127$ is also a Mersenne prime, we can deduce that $P_2(x)\mid P_{129}(x)$.

---

Reverse engineering one of the factors in the example ($\ell=6$) Greg Martin gave as follows. Let $\gamma$ be a root of the primitive polynomial $1+x+x^4$. So $\gamma$ has order $2^4-1=15$. We have $1+\gamma=\gamma^4$, so $1+\gamma^2=\gamma^8$. The element $\gamma^5=\gamma+\gamma^2$ is a third root of unity, so $(\gamma^5)^2=\gamma^{10}=1+\gamma+\gamma^2$. So with $\ell=6$ we see that $$ \gamma^{4\ell}=\gamma^{15+9}=\gamma^9 $$ and consequently $$ \gamma(1+\gamma^{4\ell})=\gamma+\gamma^{10}=1+\gamma^2. $$ The equation $(*)$ thus says that $\gamma$ is a root $P_6(x)$, and hence $1+x+x^4\mid P_6(x)$ as well as $P_{21}(x)$, $P_{36}(x)$ etc.

---

Furthermore, rewriting $(*)$ we also see that $\alpha$ is a root of $P_\ell(x)$, if $$ \alpha^{4\ell}=\frac{1+\alpha+\alpha^2}\alpha.\qquad(**) $$ If $\alpha$ is a primitive element of any finite field $F=\Bbb{F}_{2^m}$, $m>2$, then so is $\alpha^4$. The assumption $m>2$ implies that $1+x+x^2$ is not the minimal polynomial of $\alpha$, so the right hand side of $(**)$ is a non-zero element of $F$. By primitivity of $\alpha^4$, it is thus equal to $(\alpha^4)^\ell$ for some natural number $\ell$, $0<\ell<2^m-1$. So $(**)$ holds for this choice of $\ell$ as well as every other integer in the residue class of $\ell$ modulo $2^m-1$.

Conclusion: If $r(x)\in\Bbb{F}_2[x]$ is a primitive polynomial of degree $m>2$, there exists infinitely many integers $\ell$ (a residue class of $2^m-1$) such that $r(x)\mid P_\ell(x)$.