69
$\begingroup$

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 (Brindza and Pintér, On the irreducibility of some polynomials in two variables, Acta Arith. 1997).

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

$\endgroup$
94
$\begingroup$

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 polygon in $\mathbb{R}^2$ can be written as a Minkowski sum of smaller lattice polygon. Let $P$ be a lattice polytope. Travel around $\partial P$ and write down the vectors pointing from each lattice point to the next lattice point; call this sequence of vectors $v(P)$. For example, if our polynomial is $a y^2 + b y + c xy + d + e x + f x^2 + g x^3$, with $adg \neq 0$, then the lattice points on the boundary are $(0,2)$, $(0,1)$, $(0,0)$, $(1,0)$, $(2,0)$, $(3,0)$ so $v(P) =(\ (0,-1),\ (0,-1),\ (1,0),\ (1,0),\ (1,0),\ (-3,2)\ )$. (Note that $(1,1)$ is not on the boundary of the triangle.)

It turns out that $v(A + B)$ is simply the sequences $v(A)$ and $v(B)$, interleaved by sorting their slopes . 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 y^2 + b y + c xy + d + e x + f x^2 + g x^3$, with $adg \neq 0$ is irreducible.

As an example of a polynomial which could factor, look at $a y^2 + by + c xy + dx + e x^2$. So the boundary is $(0,2)$, $(0,1)$, $(1,0)$, $(2,0)$, $(1,1)$ with $v(P) = (\ (0,-1),\ (1,-1),\ (1,0),\ (-1,1),\ (-1, 1)\ )$. This is the interleaving of $(\ (0,-1),\ (1,0),\ (-1, 1)\ )$ and $(\ (1,-1),\ (-1,1)\ )$, so a polynomial with this Newton polytope could factor.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks, that is probably close to what I want! Do you have a reference? And how to check decomposition of polytopes? $\endgroup$ – Hailong Dao Feb 3 '10 at 23:29
  • $\begingroup$ 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. $\endgroup$ – David E Speyer Feb 3 '10 at 23:58
  • $\begingroup$ I'll edit the above to address your other question. $\endgroup$ – David E Speyer Feb 4 '10 at 0:00
  • 1
    $\begingroup$ Of course. It is a small example. $\endgroup$ – David E Speyer Feb 4 '10 at 12:10
  • 1
    $\begingroup$ Aargh, I made it worse and introduced a polynomial which actually can factor! I think it is right now. $\endgroup$ – David E Speyer Feb 29 at 3:13
86
$\begingroup$

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.]

| cite | improve this answer | |
$\endgroup$
  • 5
    $\begingroup$ Does it really? I think I was assigned this as an exercise in a class once. $\endgroup$ – Qiaochu Yuan Feb 3 '10 at 23:55
  • 6
    $\begingroup$ Amazingly, the sequence is in the OEIS, research.att.com/~njas/sequences/A112090 $\endgroup$ – Mariano Suárez-Álvarez Feb 4 '10 at 0:02
  • $\begingroup$ That sounds pretty awesome! $\endgroup$ – Hailong Dao Feb 4 '10 at 0:02
  • 15
    $\begingroup$ @Qiaochu - Nah, really? Maybe as one of those impossible bonus questions or something. $\endgroup$ – Harry Gindi Feb 4 '10 at 12:23
  • 3
    $\begingroup$ Could you give an example in degree 7 of one of the exceptional cases? $\endgroup$ – Thomas Feb 14 '15 at 6:23
22
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
20
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ Tim B! Welcome! $\endgroup$ – Nick Gill Jan 15 '13 at 10:08
12
$\begingroup$

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 case which fits within 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 Ehrenfeucht 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 criterion for irreducibility of polynomials". Unfortunately, if you have a polynomial with mixed monomials then this criterion does not apply.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Dear Hugo, thanks for this amazing answer, but I don't have access to Tverberg's paper. Would you be so kind as providing a copy ? $\endgroup$ – Georges Elencwajg Dec 17 '15 at 22:17
  • 1
    $\begingroup$ Dear Georges, have a look at the following mat.ulaval.ca/fileadmin/mat/documents/Chapdelaine/Algebre_III/… $\endgroup$ – Hugo Chapdelaine Dec 18 '15 at 4:09
  • $\begingroup$ Have a look at p. 116 of the document above. I only rewrote Ehrenfeucht's proof with a few more details. I can send you the original paper tomorrow, if you like. $\endgroup$ – Hugo Chapdelaine Dec 18 '15 at 4:11
  • $\begingroup$ Thanks a lot for the reprint and your fantastic notes, dear Hugo. You write "Nous aimerions maintenant présenter un critère peu connu qui nous garantit qu’un polynôme à plusieurs variables est irréductible" . "Peu connu" indeed! This must be the only elementary algebra course in the universe mentioning Ehrenfeucht's result :-) Congratulations and thank you very much again for teaching us users such beautiful and completely underappreciated mathematics. $\endgroup$ – Georges Elencwajg Dec 18 '15 at 8:00
11
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
9
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Hailong Dao Feb 3 '10 at 23:23
  • 1
    $\begingroup$ 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...) $\endgroup$ – Pete L. Clark Feb 4 '10 at 2:14
3
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
3
$\begingroup$

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.
| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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