# Criteria for irreducibility of polynomial

If $f, g\in \mathbb C[a,b]$ are polynomials in two variables, are there easy criteria that allow to see if $f(x,y)-g(t,z)\in \mathbb C[x,y,t,z]$ is irreducible?

Thank you very much,

best

-
@Thomas, what you say holds only for polynomials in one variable. – KotelKanim Aug 23 '12 at 9:50
I added the tag gr.group-theory since investigations on this problem are intimately linked to group theoretic questions. I thus thought it could be good to give it this extra visibility to the relevant experts. – quid Aug 23 '12 at 14:44
see this related question mathoverflow.net/questions/14076/… and the nice answer provided for it. – Camilo Sarmiento Aug 24 '12 at 7:22

There has been a lot of work on establishing when polynomials of the form $$f(x_1, \dots, x_r) - g(y_1, \dots, y_s)$$ are reducible (over the complex numbers, but also over other fields). (Negating them, or special cases thereof would thus yield criteria, in the sense of conditions, when such a polynomial is irreducible.)

To a considerable extent one can reduce this problem to the case $r=s=1$. Namely, Davenport and Schinzel (Two Problems Concerning Polynomials, J. reine angew. Math., 1964) proved (this is Theorem 2, up to signchange to match the question, of the paper.

The polynomial, over a field of charateristic $0$, $$f(x_1, \dots, x_r) - g(y_1, \dots, y_s)$$ is reducible if and only if $f(x_1, \dots, x_r) = F(R(x_1, \dots, x_r))$ and $g(y_1, \dots, y_s) = G(S(y_1, \dots, y_s))$ with polynomials $F,G,R,S$ over the same field and $$F(u) - G(v)$$ is reducible over the same field.

Note that the main case the authors care about is indeed the complex one.

In particular, it follows that if one cannot write $f,g$ in such a way with nontrivial (that is degree at least 2) $F$ and $G$ then the original polynomial is irreducible [except if one of $f,g$ is constant, but this should not be the case in view of the question]. (I am not sure how to check this most efficiently, but if the polynomials are not too complex, just starting from maximal terms and inferring conditions on the rank and then working ones way down could be a viable, though likely not optimal, strategy.)

If one wishes to have more complete information one is now faced with the question when a polynomial $$F(u)-G(v)$$ is (ir)reducible.

Various interesting results on this problem where obtained (see below for some recent of them), but if one wishes to have an answer for specific polynomials one migt get by via using not these results, but general irreducibilty criteria for polynomials in two variables or easier to apply criteria for this polynomial.

For the former the question pointed out in a comment by Camilo Sarmiento seems like a good resource (I reproduce the link for simplicity Irreducibility of polynomials in two variables ).

For example the Ehrenfeucht criterion mentioned there might allow to directly exclude further cases. Also the Eisenstein (like) criteria could be quite useful. Also the paper by Davenport, Lewis, Schinzel mentioned in my comment below should contain some test, but as I have no access to the paper I do not know what exactly.

Now for more recent results specifically on this problem:

Under the assumption that the $F$ and $G$ are indepecomposable (indepcomposable meaning the polynomial is not the composition of two polynomials) there is a complete answer know (over the complex numbers).

In particular, Pierrette Cassou-Noguès and Jean-Marc Coveignes (Factorisations explicites de $g(y)-h(z)$, Acta Arith. 87 (1999)) based on earlier work by Fried and Feit and others established an explict finite set of pairs of polynomials such that any pair $(F,G)$, with $F,G$ indecomposable and not linearly related (this means $F(x)$ is not of the form $AG(ax+b)+B$ with constants $A,a,B,b$ and $A,a$ non-zero, to avoid corner cases), with $F(u)-G(v)$ reducible is weakly linearly realted (I skip the def, but similar to lin related) to one of them.

This sets is too large to give here (yet the paper is linked anyway) but what can be said briefly (and was already known before) is that the degrees of both polynomials are equal, and equal to one of $7, 11, 13, 15, 21, 31$.

Note that this result uses the Classification of Finite Simple Groups.

There are also other results related to this. For example Yuri Bilu (Acta Arith. 90 (1999)) studied when $F(u)-G(v)$ has a factor of degree at most two (where there is no assumption of indecomposability). Roughly, there can essentially only be a quadratic factor if both are Chebyshev polynolmials of degree a power of two.

-
That's quite surprising! What was the motivation for the Davenport/Schinzel work? – Igor Rivin Aug 23 '12 at 15:23
@Igor Rivin: The direct motivation given in the paper is that this question was raised by one of them (Schinzel) earlier: Some unsolved problems on polynomials, Matematicka Biblioteka 25 (1963), 63-70. Now, for the actual motivation, I think that this derives ultimately mainly from Diophantine Equations/Geometry. For example Davenport, Lewis, Schinzel wrote together somewhat earlier (1961) a paper "Equations of the form f(x)=g(y)" where the f,g are polynomials (with integral coefficients), and while I cannot see the paper the MR review says roughly that if irreducible and genus cond... – quid Aug 23 '12 at 16:00
...then by Siegel's theorem only finitely many solutions; thus the question when reducible; and then they study this; giving a nontrivial case of reducibility and conditions when irreducible. So, I think this how they came to this type of problems (but this is a guess). Several classical Dioph Equ fall into this category f(x)=g(y). – quid Aug 23 '12 at 16:12
"Under the assumption that the F and G are indepecomposable (indecomposable meaning the polynomial is not the composition of two polynomials) there is a complete answer know (over the complex numbers)." Mike Zieve's REU (an incredible group of 6 undergrads) recently announced that they have a classification for all $(F,G)$, without the indecomposable hypothesis. If the indecomposability issue turns out to be crucial for you, you might want to e-mail Zieve. – David Speyer Aug 24 '12 at 11:52
My above comment is not quite right. The question Zieve's group was working on is when $F(x)-G(y)$ has a factor of genus $\leq 1$. I don't know whether they know when there is a factorization with both factors of high genus. – David Speyer Aug 28 '12 at 19:33

David is correct: my REU students have determined the complex polynomials $F(x)$ and $G(y)$ for which $F(x)-G(y)$ has an irreducible factor defining a curve of genus 0 or 1. By Faltings' theorem (a.k.a. Mordell's conjecture), this lets us write down all $F(x)$ and $G(y)$ with algebraic coefficients for which there is a number field $K$ such that $F(K)$ and $G(K)$ have infinite intersection. By one of Picard's theorems, it also means we've solved the functional equation $F\circ A = G \circ B$ in complex polynomials $F,G$ and meromorphic functions $A,B$. This last problem has been studied in the context of finding variants of Nevanlinna's theorem that a nonconstant meromorphic function is uniquely determined by its preimages at each of five points: our equation implies that the preimage under $A$ of the multiset of zeroes of $F(x)$ comprises the same multiset as the preimage under $B$ of the multiset of zeroes of $G(x)$.

We crucially use the genus condition. If one asks for reducibility of $F(x)-G(y)$ without imposing any hypothesis on the genus, then (as noted previously) one can find all examples when $F$ and $G$ are indecomposable: this was the goal of the paper by Cassou-Nogues and Couveignes, although it should be noted that their list of pairs $(F,G)$ is incomplete, so another thing we did this summer was to find the full list of pairs $(F,G)$ in this situation. In the decomposable case, much remains to be discovered about reducibility of $F(x)-G(y)$, although progress has been made. In particular, Mike Fried showed that, if $F$ is indecomposable but $G$ is decomposable, then reducibility of $F(x)-G(y)$ implies that $G=A \circ B$ for some polynomials $A$ and $B$ such that $A$ is indecomposable and $F(x)-A(y)$ is reducible. It follows that the pair $(F,A)$ occurs on the (corrected) Cassou-Nogues--Couveignes list, and in particular, we may assume that either $F = A$ or $\deg(F)=\deg(A)\le 31$. This is shown in [Michael Fried, The field of definition of function fields and a problem in the reducibility of polynomials in two variables], via a novel argument combining Galois theory and representation theory (if you're interested in this, please ask me, since one of my REU students found a very simple proof of Fried's result that I'd love to share). I note that, while the Cassou-Nogues--Couveignes result depends on the classification of finite simple groups (via the classification of finite groups $G$ that have a cyclic subgroup $C$ which acts transitively in two inequivalent doubly transitive permutation representations of $G$). However, Fried's result is elementary.

When both $F$ and $G$ are decomposable, in the same paper Fried proved the following result: if $F(x)-G(y)$ is reducible, then we can write $F = A \circ B$ and $G = C \circ D$ in such a way that $A(x)-C(y)$ is reducible and the splitting field of $A(x)-t$ over $\mathbb{C}(t)$ equals the splitting field of $C(x)-t$ over $\mathbb{C}(t)$ (where $t$ is transcendental over $\mathbb{C}$). The condition on equal splitting fields is extremely restrictive -- for instance, it implies that $\deg(A)=\deg(C)$ (by considering the size of the inertia groups at infinite places), and also that $A$ and $C$ have the same critical values, or more precisely that, for each complex number $\theta$, the least common multiple of the multiplicities of the roots of $A(x)-\theta$ equals the corresponding least common multiples for $C(x)-\theta$. Fried's proof is remarkably simple; a nice exposition of it is Theorem 8.1 in [Yuri Bilu and Robert Tichy, The Diophantine equation $f(x)=g(y)$, Acta Arith. 95 (2000), 261--288].

Surprising phenomena in the decomposable case can be found in Peter M\"uller's papers [Kronecker conjugacy of polynomials, Trans. Amer. Math. Soc. 350 (1998), 1823--1850] and [An infinite series of Kronecker conjugate polynomials, Proc. Amer. Math. Soc. 125 (1997), 1933--1940]. The most recent work on the decomposable case (to my knowledge) is [Michael Fried and Ivica Gusic, Schinzel's problem: Imprimitive covers and the monodromy method, arXiv:1104.1740]. I have not digested everything in these three papers, so I would be thrilled if someone wanted to summarize their main achievements.

-
@Rurik: in practice, even if one only has partial or approximation information about two polynomials $F(x)$ and $G(x)$, one can usually prove that $F(x)-G(y)$ is irreducible. The reason is that one can usually show that both $F$ and $G$ are indecomposable, for instance just by writing $F = A \circ B$ where $A,B$ have undetermined coefficients, and then solving for the coefficients of $A$ and $B$. Once this has been done, then Fried's "same splitting field" result will imply irreducibility. Please feel free to email me about how to do this for your specific polynomials. – Michael Zieve Aug 29 '12 at 12:37
Thank you very much. As a matter of fact I think I managed: infact my 27 polynomials, even if scary-looking in the whole, turned out to be quite simple. For example, for many of them both $F$ and $G$ are of prime degree, and for the others, they have a degree written as the product of just to prime... this allowed me to esclude at once many decompositions... – Rurik Sep 4 '12 at 6:56