Fdtxjr

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?

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.

[1] http://www.math.sc.edu/~filaseta/gradcourses/Math788F/latexbook/

[2] http://www.math.sc.edu/~filaseta/gradcourses/Math788F/NewtonPolygonsTalk.pdf

[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.
http://links.jstor.org/sici?sici=0002-9890(197606/07)83:6%3C409:HRIAG...

One method for polynomials over $mathbbZ$ 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 $mathbbZ$ which are reducible modulo every prime. For example, $x^4 + 16$ is such a polynomial. So the modular technique is not enough in general.

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.

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
http://groups.google.com/groups?selm=y8zvg4m9yhm.fsf%40nestle.ai.mit.edu

[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 among 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

Reversing the polynomial. If you have polynomial with degree $geq 2$ and non zero constant coefficients (otherwise it would be reducible so it wouldn't be interesting anyway), then you can reverse the coefficients and check irreducibility on that reciprocal polynomial. For example instead of checking $f(x)=2x^4+2x^3+2x^2+2x+1$, you can instead check $x^4+2x^3+2x^2+2x+2$ (and see it is irreducible by Eisenstein). This corresponds to $x^4f(1/x)$.

Another useful criterion is one provided by Ram's Murty in paper already referenced in the other answer, similar to Cohn's irreducibility criteria, it states:

Murty's irreducibility criterion: Let $f(x)=a_mx^m+a_m-1x^m-1+dots+a_1x+a_0$ be a polynomial of degree $m$ in $mathbbZ[x]$ and set $$H=max_0leq ileq m-1 |a_i/a_m|.$$
If $f(n)$ is prime for some integer $ngeq H+2$, then $f(x)$ is irreducible in $mathbbZ[x]$.

You can see that for example $f(x)=x^3-11x^2+19x-17$ is irreducible because of that, if you try $n=24$.

Osada's criterion. Let $f(x)=x^n+a_1x^n-1+dots+a_n-1xpm p$ be a polynomial with integer coefficients, where $p$ is a prime. If $p>1+|a_1|+dots+|a_n-1|$, then $f(x)$ is irreducible over $mathbbZ$.

Following one is also simple to use, although I found it barely applicable, nvertheless interesting:

Bauer's criterion. Let $a_1 geq a_2 geq dots geq a_n$ be positive integers and $n geq 2$. Then the polynomial $p(x)=x^n-a_1x^n-1-a_2x^n-2-dots-a_n$ is irreducible over $mathbbZ$.

Advanced criteria related to Newton polygons. These criteria are little bit more advanced to use, but the paper below provides plenty of corollaries in terms of prime powers (such as Eisenstein criterion, but in this case with multiple primes). Schönemann–Eisenstein–Dumas-Type Irreducibility Conditions that Use Arbitrarily Many Prime Numbers. An example: try to prove irreducibility of this one $$4x^6+108x^5+108x^4+108x^3+108x^2+108x+27.$$ The article above provides way to do this (it is first example in last section of examples).

Some related questions:

• How to choose correct strategy for irreducibility testing in $mathbbZ[X]$?


• Polynomial is irreducible over $mathbbQ$


• Prove that $f(x)$ is irreducible iff its reciprocal polynomial $f^*(x)$ is irreducible.