How to choose correct strategy for irreducibility testing in $\mathbb{Z}[X]$?

Solution 1:

This seems to be a good question to summarize different possible irreducibility criteria/methods since you already mentioned many. @QiaochuYuan already mentioned Newton's polygons and Perron's criterion, I would add:

Cohn's irreducibility criterion: Assume that $b\geq 2$ is a natural number and $p(x)=a_k x^k+a_{k-1}x^{k-1}+\dots+a_1 x+a_0$ is a polynomial such that $0 \leq a_i \leq b-1$. If $p(b)$ is a prime number, then $p(x)$ is irreducible in $\mathbb{Z}[x]$.

Example: The $f(x)=x^4+8$ is irreducible by Cohn for $b=9$ since $f(9)=6569$ is a prime.

Murty's irreducibility criterion: Let $f(x)=a_mx^m+a_{m-1}x^{m-1}+\dots+a_1x+a_0$ be a polynomial of degree $m$ in $\mathbb{Z}[x]$ and set $$H=\max_{0\leq i\leq m-1} |a_i/a_m|.$$ If $f(n)$ is prime for some integer $n\geq H+2$, then $f(x)$ is irreducible in $\mathbb{Z}[x]$.

See Theorem 1 in Prime Numbers and Irreducible Polynomials.

Example: The $f(x)=x^3-11x^2+19x-17$ can be easily checked to be irreducible by rational roots theorem. But if you try to apply Eisenstein, Perron, Newton Polygons or Cohn, it won't help. On the other hand it is irreducible by Murty's criterion because $f(24)=7927$ is a prime.

Maybe it is worth mentioning that both criteria above are good for proving certain polynomials are irreducible giving you have a good mechanism for checking primality of often large numbers, but usually they are less useful when you want to prove it by hand.

Solution 2:

None of these methods work in general. You can write down irreducible polynomials, starting I think at degree $4$, which are reducible $\bmod n$ for every positive integer $n \ge 2$, and hence on which both Eisenstein's criterion and reducing $\bmod p$ necessarily fail. There is some theory of Newton polygons over the $p$-adics which is supposed to generalize both of these but I never learned it.

Checking for irreducibility is quite hard in general, and honestly I still don't have great intuitions about what method to use when, I just throw everything I know at a polynomial until something sticks. Here's a great example: on MO someone asked whether or not the polynomial

$$x^n + p_1 x^{n-1} + p_2 x^{n-2} + \dots + p_n$$

is always irreducible, where $p_i$ is the $i^{th}$ prime. I observed in the comments that the constant coefficient being prime means that, if the polynomial were reducible, its irreducible factors must have constant term $\pm 1$ or $\pm p_n$, and the latter case occurs exactly once; in particular you can deduce that at least one complex root must be inside (or on) the unit circle and at least one complex root must be outside (or on) the unit circle. So if it were possible to rule that out, the polynomial is irreducible. And then Bjorn Poonen was able to rule this out, by showing that all of the roots of this polynomial lie outside the unit circle.

The reason it occurred to me to think about the location of the complex roots is by an analogy to the proof of Perron's criterion, which says the following.

Perron's criterion: Let $P(x) = x^n + a_{n-1} x^{n-1} + \dots + a_0 \in \mathbb{Z}[x]$. If $|a_{n-1}| > 1 + |a_{n-2}| + \dots + |a_0|$, then $P(x)$ is irreducible.

This can be proven using Rouche's theorem to show that the above condition implies that exactly one of the roots of $P$ lies outside the unit circle, and the rest must lie strictly inside. It doesn't come up all that often in practice, though.