MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

When is P(x)-Q(y) irreducible?

Let $k$ be an algebraically closed field (in my application, it is characteristic zero, but this probably doesn't matter so much), and let $P: k \to k$, $Q: k \to k$ be polynomials of one variable. Then $P(x)-Q(y)$ is a polynomial of two variables $x,y$. Generically, one expects this polynomial to be irreducible, but there are some exceptional cases where it becomes reducible. For instance, if $P=Q$ and $P,Q$ have degree greater than $1$, then $P(x)-Q(y)$ contains $x-y$ as a nontrivial factor. More generally, if $P = R \circ \tilde P$ and $Q = R \circ \tilde Q$ for some polynomials $\tilde P, \tilde Q, R$ with $R$ having degree greater than $1$, then $P(x)-Q(y)$ contains $\tilde P(x)-\tilde Q(y)$ as a nontrivial factor.

My (somewhat vague) question is whether there is a way to classify all the pairs of polynomials $P, Q$ in which $P(x)-Q(y)$ becomes reducible. Of course, this has a tautological answer - it is those $P, Q$ for which one can factorise $P(x)-Q(y) = R(x,y) S(x,y)$ for some polynomials $R,S$ - but I am looking for a criterion which is somehow simpler to verify than the general problem of determining whether an arbitrary polynomial of two variables is irreducible. Ideally it should have the flavour of "the only obstructions to irreducibility are the obvious ones". One could naively conjecture that the above examples are in fact the only reducible examples; indeed I could not produce any other examples, but this is likely a failure of my own imagination.

I have this vague picture of viewing the curve $\{ (x,y): P(x)=Q(y)\}$ as a relative product of the curves $\{ (x,z): z = P(x) \}$ and $\{ (y,z): z = Q(y) \}$ over the $z$-axis, so that the irreducibility of the former should somehow relate to the structure of the latter two factors (and in particular, in the location and nature of the singular points of the projection maps to the $z$-axis), but I don't know how to make this precise. (Maybe I should have paid more attention to Riemann surfaces as a student...)

Actually, I'm ultimately interested in the multidimensional version of this question, namely to give a criterion for when the algebraic set $\{ (x,y) \in k^d \times k^d: P(x)=Q(y) \}$ is an irreducible variety, where $P, Q: k^d \to k^m$ are polynomial maps, but given that even the $d=m=1$ case seems to be non-trivial, I thought I should focus on that first.

-
The expert on this is Mike Zieve, here at U Michigan. I don't know that there is a complete answer, but e-mail him and he'll have a lot to say. – David Speyer Aug 28 at 18:35
Wasn't there a similar question asked a few days ago? Gerhard "Currently Not Trusting His Memory" Paseman, 2012.08.28 – Gerhard Paseman Aug 28 at 18:49
Have a look at ams.org/mathscinet-getitem?mr=137703 – Boris Bukh Aug 28 at 18:49
I remember reading an answer elsewhere on mathoverflow that said "A polynomial $P(x)$ is indecomposable if there do not exist nonlinear polynomials $Q, R$ such that $P(x) = Q(R(x)).$ If $P,Q$ are nonconstant and indecomposable polynomials such that $P(x) - Q(y)$ is not irreducible, then either $Q(x) = P(ax+b)$ for some complex numbers $a,b$, or deg $P$ = deg $Q$ = 7,11,13,15,21, or 31." Unfortunately, I don't remember where I read it. – David Aug 28 at 18:52
Nevermind, I found the answer: mathoverflow.net/questions/14076/…, Graham's answer. – David Aug 28 at 18:53
show 1 more comment

THis is answered in great detail by @quid in this question.

-
That might be what I was not quite remembering. Gerhard "Back To Bounding Jacobsthal's Function" Paseman, 2012.08.28 – Gerhard Paseman Aug 28 at 19:21
Thank you for mentioning my answer! Meanwhile, Michael Zieve gave an additional answer to that question. – quid Aug 29 at 15:17

An interesting example perhaps is \eqalign{4 x^4 &- 4 x^2 + y^4 + 4 y^3 + 4 y^2\cr &= \left( 2{x}^{2}+2x+2xy+2y+{y}^{2} \right) \left( 2{x}^{2}-2x-2xy+2y+{y}^{2} \right)}

-
If you multiply this by 2, and note that $8x^4-8x^2+1=2(2x^2-1)^2-1$ is the Chebyshev polynomial $T_4(x)$, and $2y^4+8y^3+8y^2-1=2((y+1)^2-1)^2-1$ is $T_4(\frac{y+1}{\sqrt{2}})$, this example falls into the pattern mentioned in the answer of quid linked in the other answer here, due to Yuri Bilu (Acta Arith. 90 (1999), matwbn.icm.edu.pl/ksiazki/aa/aa90/aa9043.pdf). – Vladimir Dotsenko Aug 29 at 5:18