Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Let $k$ be a field. I am interested in sufficient criteria for $f \in k[x,y]$ to be irreducible. An example is Theorem A of this paper.

Does anyone know of similar results in the same vein? How about criterion over fields other than the complex numbers?

share|improve this question
add comment

9 Answers 9

up vote 53 down vote accepted

A trick which works surprisingly often in my experience: If the Newton polytope of $f$ can not be written as a Minkowski sum of two smaller polytopes, then $f$ is irreducible. I think of this as a generalization of Eisenstein's criterion.

It is surprisingly easy to test whether a lattice polytope in $\mathbb{R}^2$ can be written as a Minkowski sum of smaller lattice polytopes. Let $P$ be a lattice polytope. For example, the convex hull of $(2,0)$, $(1,1)$ and $(0,0)$. Travel around $\partial P$ and write down the vectors pointing from each lattice point to the next. So, in this case, we would write $(-1,1)$, $(-1,-1)$, $(1,0)$, $(1,0)$. We'll call this sequence $v(P)$.

It turns out that $v(A + B)$ is simply the sequences $v(A)$ and $v(B)$, interleaved in a certain manner. So, if $P$ can be written as the Minkowski sum $A+B$, we must be able to partition $v(P)$ into two disjoint sub-sequences, each of which sums to zero. In the above example, this can't be done, so any polynomial of the form $a+bx+c x^2 + d xy$, with $a$, $c$ and $d$ nonzero, must be irreducible.

share|improve this answer
    
Thanks, that is probably close to what I want! Do you have a reference? And how to check decomposition of polytopes? –  Hailong Dao Feb 3 '10 at 23:29
    
I don't have a reference, but it is simple enough to see why: the Newton polytope of a product is the Minkowski sum of the convex hulls of the factors. –  David Speyer Feb 3 '10 at 23:58
    
I'll edit the above to address your other question. –  David Speyer Feb 4 '10 at 0:00
    
Brief remark: a+bx+cx2+dxy as above can also be seen to be irreducible in C[x,y] because it's (obviously) irreducible in C(x)[y], right? (and the coefficients, regarded as polys in x, are coprime in C[x], as a,d!=0). –  Kevin Buzzard Feb 4 '10 at 7:46
    
Of course. It is a small example. –  David Speyer Feb 4 '10 at 12:10
show 1 more comment

One of my all-time leading candidates for Most Preposterous Theorem Ever:

Definition: A polynomial $f(x) \in \mathbb{C}[x]$ is indecomposable if whenever $f(x) = g(h(x))$ for polynomials $g$, $h$, one of $g$ or $h$ is linear.

Theorem. Let $f, g$, be nonconstant indecomposable polynomials over $\mathbb C$. Suppose that $f(x)-g(y)$ factors in $\mathbb{C}[x,y]$. Then either $g(x) = f(ax+b)$ for some $a,b \in \mathbb{C}$, or $$\operatorname{deg} f = \operatorname{deg} g = 7, 11, 13, 15, 21, \text{ or } 31,$$ and each of these possibilities does occur.

The proof uses the classification of the finite simple groups [!!!] and is due to Fried [1980, in the proceedings of the 1979 Santa Cruz conference on finite groups], following a the reduction of the problem to a group/Galois-theoretic statement by Cassels [1970]. [W. Feit, "Some consequences of the classification of finite simple groups," 1980.]

share|improve this answer
3  
Does it really? I think I was assigned this as an exercise in a class once. –  Qiaochu Yuan Feb 3 '10 at 23:55
2  
Amazingly, the sequence is in the OEIS, research.att.com/~njas/sequences/A112090 –  Mariano Suárez-Alvarez Feb 4 '10 at 0:02
    
That sounds pretty awesome! –  Hailong Dao Feb 4 '10 at 0:02
4  
@Qiaochu - Nah, really? Maybe as one of those impossible bonus questions or something. –  Harry Gindi Feb 4 '10 at 12:23
add comment

If $k$ is algebraically closed, then any two components of the projective closure of $\text{Spec } k[x, y]/(f(x, y))$ intersect by Bezout's theorem, and one can check for the existence of such points by looking at where the partial derivatives simultaneously vanish (the singular points). For example, $f(x, y) = x^2 + 2xy + y^2 - 1$ has projective closure defined by $F(X, Y, Z) = X^2 + 2XY + Y^2 - Z^2$ and the partial derivatives vanish at $(1 : -1 : 0)$, the intersection of the components $X + Y - Z = 0$ and $X + Y + Z = 0$.

Generically, $k[x]$ is a UFD, so Eisenstein's criterion applies, although I am not sure how practical this is.

share|improve this answer
    
Thanks Qiaochu. Good points! –  Hailong Dao Feb 3 '10 at 23:39
add comment

Quite a useful result can be found in Schmidt's lecture notes on Equations over finite fields (Theorem III.1B in SLNM 536). Suppose that $K$ is any field and let $f(x,y)=c_0y^d+c_1(x)y^{d-1}+ \cdots+c_d(x) \in K[x,y]$, with $c_0 \neq 0$. Let $$ \psi(f)=\sup_{1\leq i\leq d}\frac{\deg c_i}{i}. $$ Then $f$ is absolutely irreducible over $K$ provided that that $\psi(f)=m/d$ with $\gcd(m,d)=1$.

This shows, for example, that the polynomial $f(x,y)=g(x)-h(y)$ is irreducible when $\deg g$ and $\deg h$ are coprime.

share|improve this answer
2  
Tim B! Welcome! –  Nick Gill Jan 15 '13 at 10:08
add comment

I think there must be a lot of work on irreducibility criteria, although I have unfortunately never seen anything like a unified treatment.

The first thing that my MathSciNet search turned up was:


Ayad, Mohamed Sur les polynômes $f(X,Y)$ tels que $K[f]$ est intégralement fermé dans $K[X,Y]$. (French) [Polynomials $f(X,Y)$ such that $K(f)$ is integrally closed in $K[X,Y]$] Acta Arith. 105 (2002), no. 1, 9--28.

MathSciNet review by Maurice Mignotte:

As indicated in the title, the author studies polynomials $f(X,Y)$ such that $K[f]$ is integrally closed in $K[X,Y]$ (then $f$ is said to be closed), where $K$ is of characteristic zero. His main result is the following theorem. Let $f(X,Y)$ be a nonconstant polynomial in $K[X,Y]$. Then $K[f]$ is integrally closed in $K[X,Y]$ if and only if there exists $a\in K$ such that $f(X,Y)+a$ is irreducible over the algebraic closure of $K$.

Indeed, this article contains many other results and also provides a survey of this question. In particular, several examples of families of closed polynomials are given. The case of positive characteristic is studied briefly at the end of the paper.


Explanation for how I found this: I recalled that my colleague Dino Lorenzini has a paper "Reducibility of polynomials in two variables" (J. Algebra, 1993). Upon inspection, this paper didn't seem quite in the spirit of your question -- rather, he gives upper bounds on the number of irreducible components in certain families of polynomials -- but it has several citations on MathSciNet. Ayad's paper is the first.

share|improve this answer
    
Thanks Pete! I a bit confused on how can we apply the above theorem.Let's say I start with a polynomial $f$, and I want to know whether $f$ is irreducible (not whether I can add $a$ to make it irreducible). How does the Theorem help? Am I missing something? –  Hailong Dao Feb 3 '10 at 23:23
1  
So far as I can see, it does not help directly with the irreducibility of $f$; it's just an interesting result about irreducibility of polynomials in two variables. (The other responses are definitely better...) –  Pete L. Clark Feb 4 '10 at 2:14
add comment

I have a reference for the method mentioned by David Speyer above (sorry couldn't find how to add comment to existing answer):

S. Gao, Absolute irreducibility of polynomials via newton polytopes, link

share|improve this answer
    
Dear wishcow: thank you very much. –  Hailong Dao Nov 21 '10 at 5:46
add comment

Let $f\in A[x][y]$ where $A$ is a UFD and assume that $f$ is monic i.e that it can be written as $$ f=a_0+a_1 y+\ldots a_{n-1}y^{n-1}+y^n, $$ with $a_i\in A[x]$. Assume that there exists an irreducible polynomial $g\in A[x]$ such that $g|a_i$ for $i=0\ldots n-1$ and $g^2\nmid a_0$ then by Eisenstein's criterion $f$ is irreducible over $A[x]$ and therefore irreducible in $A[x,y]$. I've used the fact that $A$ was a UFD only to make sure that $gA[x]$ in $A[x]$ is a prime ideal. (Of course Eisenstein criterion is a very special of the method of the Newton polygon).

Using this idea and induction it is easy to see that polynomials like $$ (*)\;\;\;\; x_1^{n_1}+x_2^{n_2}+\ldots x_r^{n_r}\in \mathbf{C}[x_1,x_2,\ldots x_r], $$ are irreducible whenever $n_i\geq 1$ and $r\geq 3$, since the polynomial $x_1^{n_1}+x_2^{n_2}$ has always a multiplicity one irreducible divisor.

More generally there is the so called Eherenfeucht criterion which says that $$ (**) \;\;\;\; f_1(x_1)+f_2(x_2)+\ldots f_r(x_r)\in\mathbf{C}[x_1,\ldots,x_r], $$ is always irreducible if $deg(f_i)\geq 1$ and $r\geq 3$. In the case where $r=2$ it is still irreducible if one has $(deg(f_1),deg(f_2))=1$.

Note that the polynomials in $(\star)$ are a very special case of polynomials in $(\star\star)$. A nice proof of this criterion may be found in a paper of Tverberg entitled "A remark on Ehrenfeucht's crieterion for irreducibility of polynomials". Unfortunately, if you have a polynomial with mixed monomials then this criterion does not apply.

share|improve this answer
add comment

there is a theorem of Ruppert, but I don't know it is useful or not. You can try: pdf - arXiv:math/9808021v1 [math.NT] 5 Aug 1998

share|improve this answer
add comment

What follows is more a series of considerations than a practical algorithm, but could still be of interest. The main idea is that it's easier to work with one-variable polynoms, so we trade a bad problem in two variables for several bad problems in one variable.

The key point is the following lemma (assume $k$ is of characteristic zero!): if $P(X,Y)$ is a two-variable polynom and there are enough distinct values of $a$ such that $P(X,a)$ is a constant polynomial, then $P(X,Y)$ is a polynom in $Y$ only. The proof is by arguing that $P(X,a)$ being a constant polynom means that $a$ is a root for the polynom (in $Y$) coefficient of $X^n$ for all $n>0$. And that can't happen too often in characteristic zero, unless those coefficients are zero polynoms, hence $P(X,Y)$ is reduced to its constant term as a polynom in $X$, hence is only a polynom in $Y$, as was to be proved.

Now, for your question : if you suppose a $P(X,Y)$ isn't irreducible, say factors as $Q(X,Y)R(X,Y)$, but many $P(X,a)$ are irreductible, then that means for each such $a$ either $Q(X,a)$ or $R(X,a)$ is a constant, hence given enough of those $a$, one of $Q$ or $R$ at least is only a polynom in $Y$ by the lemma, say $R$.

Then if you manage to fully factor $P(a,Y)=Q(a,Y)R(Y)$ for some $a$ (again dropping to a one-variable polynom), you get a list with $R$ (and divisors of $R$): check each element for divisibility of $P(X,Y)$. If none is good, $P$ is irreducible.

EDIT:

  1. In fact, after you have found $R$ is a polynom in $Y$, just consider the gcd of the coefficients of the $X^n$ -- if you get $1$, $P$ is irreducible.
  2. The previous considerations mostly prove that a cheating polynom (ie: not irreducible although it appears to be when evaluated along a variable) necessarily has a very precise form, which makes it susceptible to easy factorisation.
share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.