# Polynomials irreducible over $\mathbb{Q}$ but reducible over $\mathbb{F}_p$ for every prime $p$

Let $f(x) \in \mathbb{Z}[x]$. If we reduce the coefficents of $f(x)$ modulo $p$, where $p$ is prime, we get a polynomial $f^*(x) \in \mathbb{F}_p[x]$. Then if $f^*(x)$ is irreducible and has the same degree as $f(x)$, the polynomial $f(x)$ is irreducible.

This is one way to show that a polynomial in $\mathbb{Z}[x]$ is irreducible, but it does not always work. There are polynomials which are irreducible in $\mathbb{Z}[x]$ yet factor in $\mathbb{F}_p[x]$ for every prime $p$. The only examples I know are $x^4 + 1$ and $x^4 - 10x^2 + 1$.

I'd like to see more examples, in particular an infinite family of polynomials like this would be interesting. How does one go about finding them? Has anyone ever attempted classifying all polynomials in $\mathbb{Z}[x]$ with this property?

-
Your initial claim is false. For example, $f(x)=4x^2-1$ is reducible over $\mathbb{Z}$ but irreducible over $\mathbb{F}_2$. – Chris Eagle Jun 20 '12 at 16:42
Ah, you're right. I meant that unless the leading coefficient is zero modulo $p$. – spin Jun 20 '12 at 16:43

There are two crucial results here.

Dedekind's theorem: Let $f$ be a monic irreducible polynomial over $\mathbb{Z}$ of degree $n$ and let $p$ be a prime such that $f$ has distinct roots $\bmod p$ (this is true for precisely the primes not dividing the discriminant). Suppose that the prime factorization of $f \bmod p$ is $$f \equiv \prod_{i=1}^k f_i \bmod p.$$

Then the Galois group $G$ of $f$ contains an element of cycle type $(\deg f_1, \deg f_2, ...)$. In particular, if $f$ is irreducible $\bmod p$, then $G$ contains an $n$-cycle.

Frobenius density theorem: The density of the primes with respect to which the factorization of $f \bmod p$ has the above form is equal to the density of elements of $G$ with the corresponding cycle type. In particular, for every cycle type there is at least one such prime $p$.

It follows that

$f$ is reducible $\bmod p$ for all $p$ if and only if $G$ does not contain an $n$-cycle.

The smallest value of $n$ for which this is possible is $n = 4$, where the Galois group $V_4 \cong C_2 \times C_2$ has no $4$-cycle. Thus to write down a family of examples it suffices to write down a family of irreducible quartics with Galois group $V_4$. As discussed for example in this math.SE question, if $$f(x) = (x^2 - a)^2 - b$$

is irreducible and $a^2 - b$ is a square, then $f$ has Galois group $V_4$. In particular, taking $b = a^2 - 1$ the problem reduces to finding infinitely many $a$ such that $$f(x) = x^4 - 2ax^2 + 1$$

is irreducible. We get your examples by setting $a = 0, 5$.

By the rational root theorem, the only possible rational roots of $f$ are $\pm 1$, so by taking $a \neq 1$ we already guarantee that $f$ has no rational roots. If $f$ splits into two quadratic factors, then they both have constant term $\pm 1$, so we can write $$x^4 - 2ax + 1 = (x^2 - bx \pm 1)(x^2 + bx \pm 1)$$

for some $b$. This gives $$2a = b^2 \mp 2.$$

Thus $f$ is irreducible if and only if $2a$ cannot be written in the above form (and also $a \neq 1$).

Classifying polynomials $f$ with this property seems quite difficult in general. When $n = 4$, it turns out that $V_4$ is in fact the only transitive subgroup of $S_4$ not containing a $4$-cycle, but for higher values of $n$ there should be lots more, and then one has to tell whether a polynomial has one of these as a Galois group...

(Except if $n = q$ is prime; in this case $q | |G|$ so it must have a $q$-cycle.)

-
I should mention that these theorems together can also be used to compute Galois groups. The idea is that one factors $f \bmod p$ for lots of primes $p$ and builds a table of the observed densities of the cycle types, then compares that table to the densities for all possible Galois groups of $f$. The density of cycle types uniquely characterizes the Galois group up to conjugacy for $n \le 7$ (I didn't check beyond that). – Qiaochu Yuan Jun 20 '12 at 16:59
Could you please explain why $f$ is reducible$\mod p$ in the case that $p$ divides the discriminant of $f$? In that case, the hypotheses for Dedekind's theorem do not hold. – Donkey_2009 Nov 29 '13 at 0:03
OK - got the answer myself. If $f\mod p$ is inseparable, then it has some irreducible factor of the form $g(X^p)$ for some irreducible $g$. But every element of $\mathbb F_p$ is a $p$-th power so, applying the Frobenius automorphism, we can write $g(X^p)$ as $(h(x))^p$, where the coefficients of $h$ are the $p$-th roots of the coefficients of $g$. But this is clearly reducible. – Donkey_2009 Nov 29 '13 at 15:30

The polynomials $p_n(x)=x^{2^n}+1$ form an infinite family of examples of such polynomials. They are irreducible over the rationals, because $p_n(x)$ is also the cyclotomic polynomial of order $2^{n+1}$.

But the polynomial $p_n(x)$ factors in $\mathbb{F}_p[x]$ for any prime $p$. If $p=2$, this is obvious because $$p_n(x)\equiv (x+1)^{2^n}\pmod2.$$ If $p$ is an odd prime, then the reasoning is a little bit more subtle. It follows from the fact that the order $d$ of $p$ in the group $G=\mathbb{Z}/2^{n+1}\mathbb{Z}^*$ is less than $2^n$ (by virtue of non-cyclicity of $G$), and the fact that the field $\mathbb{F}_{p^d}$ then contains a primitive root of unity of order $2^{n+1}$ as $2^{n+1}\mid (p^d-1)$. This implies that the primitive roots of unity of order $p$ have minimal polynomials of degree $d$, and these must be factors of $p_n(x)$.

It is worth observing that for the same reason ($G$ not cyclic) the polynomials $p_n(x)$ pass the test described in Qiaochu's answer. The elements of the Galois group all have orders that are powers of two $<2^n$, so the maximum length of a cycle is $2^{n-1}$.

-
Slightly more obvious: for $n \ge 2$, $p_n(x) = p_2(x^{2^{n-2}})$, so if $p_2$ factors so does $p_n$. – Robert Israel Jun 20 '12 at 16:51