Is $x^p-x+1$ always irreducible in $\mathbb F_p[x]$?

Question

It seems that for any prime number $p$ and for any non-zero element $a$ in the finite field $\mathbb F_p$, the polynomial $x^p-x+a$ is irreducible over $\mathbb F_p$. (It is of course obvious that there are no linear factors.)

Are there any general irreducibility criteria which can help to prove such a result?

(More generally, it seems that all irreducible factors over $\mathbb F_p$ of $$a+\sum_{j=0}^n{n\choose j}(-1)^jx^{p^j}$$ (where $a$ is of course a non-zero element of $\mathbb F_p$) have a common degree given by a non-trivial power of $p$.)

Answer 1

This is true. Pass to an extension field where the polynomial has a root $r$, notice that the other roots are of the form $r+1$, $r+2$, ..., $r+p-1$. Suppose that $x^p - x +1 = f(x) g(x)$, with $f, g \in \mathbb{F}_p\left[x\right]$ and $\deg f = d$. Then $f(x) = (x-r-c_1) (x-r-c_2) \cdots (x-r-c_d)$ for some subset $\{ c_1, c_2, \ldots, c_d \}$ of $\mathbb{F}_p$. So the coefficient of $x^{d-1}$ in $f$ is $-\sum (r+c_i) = - (dr + \sum c_i)$; we deduce that $dr \in \mathbb{F}_p$. If $d \neq 0 \bmod p$, then $r \in \mathbb{F}_p$ which is plainly false, so $d=0$ or $p$ and the factorization is trivial.

If I were to try to turn this proof into a general technique, I suppose I would frame it as "prove that the Galois group is contained in a cyclic group of order $p$, and observe that it can't be the trivial group, so it must be the whole group."

---

I can also prove the generalization. Define a $\mathbb{F}_p$-module endomorphism $T$ of any commutative $\mathbb{F}_p$-algebra by $T(u) = u^p-u$. Set $F(n) = \mathbb{F}_{p^{p^n}}$. Observe that $$T^r(x) = \sum_{k=0}^r (-1)^{r-k} x^{p^k} \binom{r}{k}.$$

Lemma $T$ is an $\mathbb{F}_p$-linear endomorphism of $F(n)$ whose Jordan-normal form is a single nilpotent block (of size $p^n$).

Proof Obviously, $T$ is $\mathbb{F}_p$-linear. Observe that $$T^{p^n}(x) = \sum_{k=0}^{p^n} (-1)^{p^n-k} x^{p^k} \binom{p^n}{k} = x^{p^{p^n}} - x$$ so $T^{p^n}$ is zero on $F(n)$ and we know that $T$ is nilpotent. Finally, $T(x) = x^p-x$ so the kernel of $T$ is one dimensional, and we see that there is only one Jordan block. $\square$

Now, let $p^{n-1} \leq r < p^n$. Roland's polynomial is $T^r(x) = a$ for $a$ a nonzero element of $\mathbb{F}_p$. Using the Lemma, the image of $T^r: F(n) \to F(n)$ is the same as the kernel of $T^{p^n-r}$. In particular, since $a \in \mathrm{Ker}(T)$, we see that $a$ is in the image of $T^r: F(n) \to F(n)$. Using the Lemma again, all nonzero fibers of $T^r$ are of size $p^r$, so there are $p^r$ roots of $T^r(x)=a$ in $F(n)$. Since Roland's polynomial only has degree $p^r$, we see that all roots of $T^r(x)=a$ are in $F(n)$.

All proper subfields of $F(n)$ are contained in $F(n-1)$. But, since $r \geq p^{n-1}$, the Lemma shows that $T^r(x)=0$ on $F(n-1)$. So none of the roots of $T^r(x)=a$ are in $F(n-1)$.

We conclude that all the factors of Roland's polynomial are of degree $p^n$.

Answer 2

Here is an alternate proof of the OP's first conclusion, based on the same idea as David's, but which avoids consideration of coefficients. Let $r$ be a root of $h(x):=x^p-x+1$, so that $r\notin\mathbf{F}_p$. Since $h(x+c)=h(x)$ for every $c\in\mathbf{F}_p$, the other roots of $h(x)$ are $r+1,r+2,\dots,r+p-1$. Let $f(x)$ be the minimal polynomial of $r$ over $\mathbf{F}_p$, and let $r+c$ be a root of $f(x)$ with $c\ne 0$. Write $h(x)=f(x)g(x)$, so that $$ f(x+c)g(x+c)=h(x+c)=h(x)=f(x)g(x). $$ Since $f(x)$ and $f(x+c)$ are monic irreducible polynomials in $\mathbf{F}_p$ which both have $r$ as a root, they must be the same polynomial. Therefore the set of roots of $f(x)$ is preserved by the map $s\mapsto s+c$, so this set must include all the roots of $h(x)$.

I mention this variant of David's proof mostly in case this version might suggest generalizations to different types of settings.

---

Here is a proof of the OP's more general conclusion. Write $L(x)^{\circ n}$ for the $n$-th iterate of $L(x):=x^p-x$. We compute $$ L(x)^{\circ n} = (L(x)^{\circ (n-1)})^p-L(x)^{\circ (n-1)}=L(x)^{\circ (n-1)}\prod_{a=1}^{p-1} (L(x)^{\circ (n-1)}+a) $$ $$= L(x)^{\circ (n-1)}\prod_{a=1}^{p-1}\Bigl( a + \sum_{j=0}^n {n\choose j}(-1)^jx^{p^j}\Bigr). $$ It follows that $L(x)^{\circ n}$ is divisible by $L(x)^{\circ (n-1)}$, and the goal is to prove that for every $n$ there exists $k$ so that every irreducible factor of $f_n(x):=L(x)^{\circ n}/L(x)^{\circ (n-1)}$ in $\mathbf{F}_p[x]$ has degree $p^k$.

The key step in the proof is the following claim: if $u$ is a root of $f_n(x)$, then all roots of $f_n(x)$ have the form $iu+L(w)$ where $i\in\mathbf{F}_p$ and $L^{\circ n}(w)=0$. To prove this, first note that $L(x+dy)=L(x)+dL(y)$ for any $d\in\mathbf{F}_p$, so that $L^{\circ n}(iu+j)=0$ for every $i\in\mathbf{F}_p$ and every root $j$ of $L^{\circ (n-1)}(x)$. But the polynomial $L^{\circ (n-1)}(x)$ is squarefree (since its derivative is $1$), so its roots form an $(n-1)$-dimensional $\mathbf{F}_p$-vector space, and since $L^{\circ (n-1)}(u)\ne 0$ it follows that the above values $iu+j$ comprise $p^n$ distinct roots of $L^{\circ n}(x)$, so every root has this form. Since $L^{\circ (n-1)}(j)=0$, we can write $j=L(w)$ for some root $w$ of $L^{\circ n}(x)$, which proves the claim.

Now we prove by induction on $n$ that for every $n$ there exists $k$ so that every irreducible factor of $f_n(x)$ in $\mathbf{F}_p[x]$ has degree $p^k$. The base case $n=1$ is trivial (where $L(x)^{\circ 0}=x$ by definition). Inductively, suppose that all irreducible factors of $f_n(x)$ have degree $p^k$.
Let $r,s$ be roots of $f_{n+1}(x)$. Then $u:=L(r)$ and $v:=L(s)$ are roots of $f_n(x)$, so that $\mathbf{F}_p(u)=\mathbf{F}_{p^k}=\mathbf{F}_p(v)$, and by the above claim we have $v=iu+L(w)$ with $i\in\mathbf{F}_p$ and $L^{\circ n}(w)=0$. Note that $i\ne 0$ since $L^{\circ (n-1)}(v)\ne 0$. Also $w\in\mathbf{F}_{p^k}$, since if $w\ne 0$ then $w$ is a root of $f_{\ell}(x)$ for some $\ell\le n$, so that $w=L^{\circ (n-\ell)}(z)$ for some root $z$ of $f_n(x)$, where $z\in\mathbf{F}_{p^k}$ by inductive hypothesis. By the Artin-Schreier theorem, $[\mathbf{F}_p(r):\mathbf{F}_{p^k}]$ is either $1$ or $p$, and is $1$ if and only if $L(x)-u$ has a root in $\mathbf{F}_{p^k}$. This is equivalent to saying that $iL(x-w/i)-iu$ has a root in $\mathbf{F}_{p^k}$, or in other words (with $y=ix$) that $L(y)-(iu+j)$ has such a root, which in turn says that $[\mathbf{F}_p(s):\mathbf{F}_{p^k}]=1$. Therefore $\mathbf{F}_{p}(r)=\mathbf{F}_{p}(s)$, and this field is either $\mathbf{F}_{p^k}$ or $\mathbf{F}_{p^{k+1}}$, as desired.

Answer 3

You might be interested in Artin-Schreier theory.

Answer 4

Here is a quick proof using Galois theory.

Let $r$ be any of the roots in an algebraic closure of $\mathbb{F}_p$. Then $r^p=r-a$, hence by induction $r^{p^k}=r-ka$. Therefore the elements $r^{p^k}$ ($0\leq k\leq p-1$) are all different, hence $r$ is of degree $p$.

Added. More generally, it follows by Artin-Schreier theory that the polynomial $$ f_{n,a}(x):=a+\sum_{j=0}^n{n\choose j}(-1)^jx^{p^j} $$ decomposes over $\mathbb{F}_p$ into irreducible factors of $p$-power degree. We proceed by induction on $n$. Let $n\geq 1$, and assume the statement for $n-1$ in place of $n$. Let us work in a fixed algebraic closure $\overline{\mathbb{F}_p}$. Let $r\in\overline{\mathbb{F}_p}$ be a root of $f_{n,a}$. Then $s:=r-r^p$ is a root of $f_{n-1,a}$, so $(\mathbb{F}_p(s):\mathbb{F}_p)$ is a power of $p$. Clearly, $\mathbb{F}_p(r)$ is an extension of $\mathbb{F}_p(s)$, because $s\in\mathbb{F}_p(r)$. This extension is of Artin-Schreier type, because $r$ is the root of the polynomial $x^p-x+s$ over $\mathbb{F}_p(s)$. Hence $(\mathbb{F}_p(r):\mathbb{F}_p(s))$ is equal to $1$ or $p$, and so $(\mathbb{F}_p(r):\mathbb{F}_p)$ is a power of $p$.

Remark. The degree of $(\mathbb{F}_p(r):\mathbb{F}_p(s))$ equals $p$ if and only if the trace of $s$ is nonzero. However, it seems difficult to show in this way that $(\mathbb{F}_p(r):\mathbb{F}_p)$ only depends on $n$ and $a$, let alone calculate it explicitly. David Speyer's elegant solution based on linear algebra seems to be the right approach here.

Answer 5

There is kind of an easy proof given that Berlekamp's algorithm works?

In the notation of https://en.wikipedia.org/wiki/Berlekamp%27s_algorithm, the point is that the space of polynomials g congruent to their p-th power is not going to contain anything but constants, because the p-th power map is a translation of the argument.