Criteria for irreducibility of polynomial - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T01:48:46Z http://mathoverflow.net/feeds/question/105304 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/105304/criteria-for-irreducibility-of-polynomial Criteria for irreducibility of polynomial Rurik 2012-08-23T07:09:31Z 2012-08-29T12:23:25Z <p>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? </p> <p>Thank you very much,</p> <p>best</p> http://mathoverflow.net/questions/105304/criteria-for-irreducibility-of-polynomial/105323#105323 Answer by quid for Criteria for irreducibility of polynomial quid 2012-08-23T14:38:17Z 2012-08-24T11:09:14Z <p>There has been a lot of work on establishing when polynomials of the form <code>$$f(x_1, \dots, x_r) - g(y_1, \dots, y_s)$$</code> 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.)</p> <p>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. </p> <blockquote> <p>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 <code>$f(x_1, \dots, x_r) = F(R(x_1, \dots, x_r))$</code> and <code>$g(y_1, \dots, y_s) = G(S(y_1, \dots, y_s))$</code> with polynomials $F,G,R,S$ over the same field and $$F(u) - G(v)$$ is reducible over the same field.</p> </blockquote> <p>Note that the main case the authors care about is indeed the complex one. </p> <p>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.)</p> <p>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. </p> <p>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. </p> <p>For the former the question pointed out in a comment by Camilo Sarmiento seems like a good resource (I reproduce the link for simplicity <a href="http://mathoverflow.net/questions/14076/irreducibility-of-polynomials-in-two-variables" rel="nofollow">http://mathoverflow.net/questions/14076/irreducibility-of-polynomials-in-two-variables</a> ).</p> <p>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.</p> <p>Now for more recent results specifically on this problem: </p> <p>Under the assumption that the $F$ and $G$ are indepecomposable (indepcomposable meaning the polynomial is not the <em>composition</em> of two polynomials) there is a complete answer know (over the complex numbers).</p> <p>In particular, Pierrette Cassou-Noguès and Jean-Marc Coveignes (<a href="http://www.math.u-bordeaux1.fr/~jcouveig/publi/CaCou.pdf" rel="nofollow">Factorisations explicites de $g(y)-h(z)$</a>, Acta Arith. 87 (1999)) based on earlier work by Fried and Feit and others established an explict <em>finite set</em> 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. </p> <p>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$. </p> <p>Note that this result uses the Classification of Finite Simple Groups.</p> <p>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. </p> http://mathoverflow.net/questions/105304/criteria-for-irreducibility-of-polynomial/105823#105823 Answer by Michael Zieve for Criteria for irreducibility of polynomial Michael Zieve 2012-08-29T12:23:25Z 2012-08-29T12:23:25Z <p>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)$.</p> <p>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.</p> <p>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].</p> <p>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.</p>