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

  • 1
    $\begingroup$ 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. $\endgroup$ – Michael Zieve May 19 '14 at 19:14
  • $\begingroup$ @Michael: Of course. It is now corrected. Thank you. $\endgroup$ – Roland Bacher May 19 '14 at 20:19
  • 3
    $\begingroup$ This is Exercise 13.5.5 in Dummit and Foote. $\endgroup$ – 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$.

  • $\begingroup$ Thanks. Your proof shows also that all irreducible factors of the generalization are of degree divisible by $p$. $\endgroup$ – Roland Bacher May 19 '14 at 15:52
  • 1
    $\begingroup$ 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$ $\endgroup$ – David E Speyer May 19 '14 at 23:30
  • 1
    $\begingroup$ 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. $\endgroup$ – 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.

  • $\begingroup$ @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. $\endgroup$ – GH from MO May 19 '14 at 20:44
  • $\begingroup$ @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. $\endgroup$ – 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.


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.