Methods to see if a polynomial is irreducible

Given a polynomial over a field, what are the methods to see it is irreducible? Only two comes to my mind now. First is Eisenstein criterion. Another is that if a polynomial is irreducible mod p then it is irreducible. Are there any others?

-
Well, Eisenstein's criterion is basically a version of reducing modulo a prime. – Akhil Mathew Aug 9 '10 at 18:10

To better understand the Eisenstein and related irreducibility tests you should learn about Newton polygons. It's the master theorem behind all these related results. A good place to start is Filaseta's notes - see the links below. Note: you may need to write to Filaseta to get access to his interesting book [1] on this topic.

[3] Newton Polygon Applet http://www.math.sc.edu/~filaseta/newton/newton.html

[4] Abhyankar, Shreeram S.
Historical ramblings in algebraic geometry and related algebra.
Amer. Math. Monthly 83 (1976), no. 6, 409-448.

-
I'm not able to access the first link you posted – crasic Nov 24 '10 at 11:18
@crasic: Did you try contacting him to obtain access? – Bill Dubuque Nov 24 '10 at 14:08
I would like to read this book too. – quanta May 4 '11 at 11:42
I'm going to contact him and see if he will give me access. I will post my success or failure here. – Holdsworth88 Jun 7 '12 at 9:20
@Holdsworth88: So, ... two years later ... did you succeed or fail? – Eric Towers Jun 29 '14 at 5:23

Here's an elementary trick that I occasionally find useful: Let $y=x+c$ for some fixed integer $c$, and write $f(x)=g(y)$. Then $f$ is irreducible if and only if $g$ is irreducible. You may be able to able to reduce $g$ modulo a prime and/or apply Eisenstein to show that $g$ is irreducible.

-
Also works for $y=ax+c$. – lentic catachresis May 4 '11 at 8:09
...if $a$ is a unit. – lentic catachresis Sep 8 '11 at 23:09

One method for polynomials over $\mathbb{Z}$ is to use complex analysis to say something about the location of the roots. Often Rouche's theorem is useful; this is how Perron's criterion is proven, which says that a monic polynomial $x^n + a_{n-1} x^{n-1} + ... + a_0$ with integer coefficients is irreducible if $|a_{n-1}| > 1 + |a_{n-2}| + ... + |a_0|$ and $a_0 \neq 0$. A basic observation is that knowing a polynomial is reducible places constraints on where its roots can be; for example, if a monic polynomial with prime constant coefficient $p$ is reducible, one of its irreducible factors has constant term $\pm p$ and the rest have constant term $\pm 1$. It follows that the polynomial has at least one root inside the unit circle and at least one root outside.

An important thing to keep in mind here is that there exist irreducible polynomials over $\mathbb{Z}$ which are reducible modulo every prime. For example, $x^4 + 16$ is such a polynomial. So the modular technique is not enough in general.

-
Incidentally, if a polynomial is irreducible in the algebraic closure of every prime field, then it is irreducible. (This is only interesting when one has a polynomial of multiple variables :)). This can be proved via an application of model theory: note that the statement "a given polynomial over $\mathbb{Z}$ is irreducible in some field" can be phrased via first-order logic. So if it is true in algebraically closed fields of arbitrarily high characteristic, it is true over $\mathbb{C}$, even. – Akhil Mathew Aug 9 '10 at 23:16

Below is another method for irreducibility testing - excerpted from one of my old sci.math posts.

In 1918 Stackel published the following simple observation:

THEOREM If $p(x)$ is a composite integer coefficient polynomial

then $p(n)$ is composite for all $|n| > B$, for some bound $B$,

in fact $p(n)$ has at most $2d$ prime values, where $d = {\rm deg}(p)$.

The simple proof can be found online in Mott & Rose [3], p. 8. I highly recommend this delightful and stimulating 27 page paper which discusses prime-producing polynomials and related topics.

Contrapositively, $p(x)$ is prime (irreducible) if it assumes a prime value for large enough $|x|$. Conversely Bouniakowski conjectured (1857) that prime $p(x)$ assume infinitely many prime values (except in trivial cases where the values of $p$ have an obvious common divisor, e.g. $2 | x(x+1)+2$ ).

As an example, Polya-Szego popularized A. Cohn's irreduciblity test, which states that $p(x) \in {\mathbb Z}[x]$ is prime if $p(b)$ yields a prime in radix $b$ representation (so necessarily $0 \le p_i < b$).

For example $f(x) = x^4 + 6 x^2 + 1 \pmod p$ factors for all primes $p$, yet $f(x)$ is prime since $f(8) = 10601$ octal $= 4481$ is prime.

Note: Cohn's test fails if, in radix $b$, negative digits are allowed, e.g. $f(x) = x^3 - 9 x^2 + x-9 = (x-9)(x^2 + 1)$ but $f(10) = 101$ is prime.

For further discussion see my prior post [1], along with Murty's online paper [2].

[1] Dubuque, sci.math 2002-11-12, On prime producing polynomials

[2] Murty, Ram. Prime numbers and irreducible polynomials.
Amer. Math. Monthly, Vol. 109 (2002), no. 5, 452-458.
http://www.mast.queensu.ca/~murty/polya4.dvi

[3] Mott, Joe L.; Rose, Kermit. Prime producing cubic polynomials
Ideal theoretic methods in commutative algebra, 281-317.
Lecture Notes in Pure and Appl. Math., 220, Dekker, New York, 2001.
http://web.math.fsu.edu/~aluffi/archive/paper134.ps

-

Polynomials by Prasolov covers amoung others:

• Eisenstein's criterion
• Duma's criterion
• Irreducibility of polynomials attaining small values
• Hilbert's criterion
• Irreducibility of trinomials and fournomials
• A few algorithms for factorization
-