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

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$.)

• Regarding the generalization: I think the sum should go up to $n$ rather than to $k$, in which case the generalized polynomial is $a$ plus the $n$-th iterate of $x^p-x$. This suggests that there should be an inductive proof of the generalization, somehow. – Michael Zieve May 19 '14 at 19:14
• @Michael: Of course. It is now corrected. Thank you. – Roland Bacher May 19 '14 at 20:19
• This is Exercise 13.5.5 in Dummit and Foote. – Lucia Jan 30 '15 at 23:50

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$$.

• Thanks. Your proof shows also that all irreducible factors of the generalization are of degree divisible by $p$. – Roland Bacher May 19 '14 at 15:52
• I wonder what the Jordan form of $T$ is on $\mathbb{F}_{p^m}$ when $m$ isn't a power of $p$? I get eigenvalues of $0$ and $-2$ for $m=2$ – David E Speyer May 19 '14 at 23:30
• Oh, it isn't hard. As linear operators, $T = F-1$ where $F$ is the Frobenius. We have $F^m=1$ on $\mathbb{F}_{p^m}$. When $p$ doesn't divide $m$, that's square free, so the characteristic polynomial of $T$ is $(x-1)^m-1$. I do the power of $p$ case above; it should be hard to mix them and do the general case. – David E Speyer May 20 '14 at 2:52

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.

You might be interested in Artin-Schreier theory.

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.

• @Michael: I am thinking about this. At the moment the argument only gives that each irreducible factor of $f_{n,a}$ has a $p$-power degree. – GH from MO May 19 '14 at 20:44
• @Michael: I could not show independence of $s$, so I updated my writeup accordingly. Fortunately, David Speyer came up with an approach that is more to the point. – GH from MO May 20 '14 at 1:10

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.