ACTA ARITHMETICA

XCV.3 (2000)
The Diophantine equation f(x) = g(y)
by
Yuri F. Bilu (Basel) and Robert F. Tichy (Graz)
1. Introduction. Let f(x) and g(x) be polynomials with rational
coecients. We study the following question: does the equation
(1) f(x) = g(y)
have nitely or innitely many solutions in rational integers x and y?
Due to the classical theorem of Siegel (see Theorem 10.1 below), the
niteness problem for (1), and even for a more general equation F(x, y) = 0
with F(x, y) Z[x, y], is decidable (
1
). One has to:
decompose the polynomial F(x, y) into Q-irreducible factors;
for those factors which are not Q-reducible, determine the genus g and
the number d of points at innity of the corresponding plane curve;
for the factors with g = 0 and d 2 determine whether the corre-
sponding equation has nitely or innitely many integral solutions (see [4,
Section 1]).
Though this procedure completely solves the problem when the polyno-
mials f(x) and g(x) are given numerically, it is not very helpful when they
depend on unknown parameters, which often happens in applications.
In this paper we obtain a very explicit niteness criterion for the equa-
tion (1). It turns out to be more convenient to study a slightly more gen-
eral question: when does (1) have innitely many rational solutions with a
bounded denominator? We say that the equation F(x, y) = 0 has innitely
2000 Mathematics Subject Classication: Primary 14H45; Secondary 11C08, 11D41,
11G30, 12E05, 12E10, 14H05, 14H25.
Key words and phrases: Ritts second theorem, Dickson polynomials, reducibility,
Diophantine equations.
The rst author supported by the Lise Meitner Fellowship (Austria), grant M00421-
MAT.
(
1
) We mention in passing that the decidability of the existence problem (that is,
whether or not F(x, y) = 0 has at least one solution) is still an open question. The
answer, which is believed to be positive, is known only in particular cases.
[261]
262 Yu. F. Bi l u and R. F. Ti chy
many rational solutions with a bounded denominator if there exists a positive
integer such that F(x, y) = 0 has innitely many solutions (x, y) QQ
with x, y Z.
To formulate our criterion, we have to dene ve types of standard
pairs (f(x), g(x)).
1.1. Standard pairs. In what follows a and b are non-zero elements of
some eld, m and n are positive integers, and p(x) is a non-zero polynomial
(which may be constant).
A standard pair of the rst kind is
(x
m
, ax
r
p(x)
m
)
or switched, (ax
r
p(x)
m
, x
m
), where 0 r < m, (r, m) = 1 and r + deg p(x)
> 0.
A standard pair of the second kind is
(x
2
, (ax
2
+ b)p(x)
2
)
(or switched).
Denote by D
m
(x, a) the mth Dickson polynomial, dened by
D
m
(z + a/z, a) = z
m
+ (a/z)
m
(see Section 3). A standard pair of the third kind is
(D
m
(x, a
n
), D
n
(x, a
m
)),
where gcd(m, n) = 1.
A standard pair of the fourth kind is
(a
m/2
D
m
(x, a), b
n/2
D
n
(x, b)),
where gcd(m, n) = 2.
A standard pair of the fth kind is
((ax
2
1)
3
, 3x
4
4x
3
)
(or switched).
When we want to specify that the parameters a and b and the coecients
of the polynomial p(x) belong to a eld K we say standard pair over K.
If (f(x), g(x)) is a standard pair over Q of the rst or third kind then (1)
has innitely many rational solutions with a bounded denominator. For
the third kind, an innite family of solutions is given by x = D
n
(t, a) and
y = D
m
(t, a), where t Z. For the rst kind, nd positive integers q
and s with qm sr = 1. Then an innite family of solutions is given by
x = a
q
t
r
p(a
s
t
m
) and y = a
s
t
m
, where t Z.
If (f(x), g(x)) is a standard pair over Q of the second, fourth or fth kind
then (1) has innitely many rational solutions with a bounded denominator
for innitely many choices of the parameters a and b.
Diophantine equation f(x) = g(y) 263
For instance, for the second kind let (u, v) satisfy u
2
= av
2
+ b. Then
x = up(v) and y = v is a solution of (1). Hence (1) has innitely many
rational solutions with a bounded denominator whenever u
2
= av
2
+b does,
which happens for innitely many choices of a and b.
For the fourth kind (where we assume, without loss of generality, that
n/2 is odd), let (u, v) be a solution of a
m/2
u
2
+ bv
2
= 4ab. Then x =
a
(2n)/4
D
n/2
(v, a) and y = uE
m/2
(v, a) (where E
n
(t, a) is dened in (8)) is
a solution of (1), as follows from Proposition 3.1.
For the fth kind, let (u, v) be a solution of 3au
2
= v
2
+ 2. Then
x = u(v + 2) and y = ((v + 1)
3
+ 4)/3 is a solution of (1).
1.2. The criterion
Theorem 1.1. Let f(x), g(x) Q[x] be non-constant polynomials. Then
the following two assertions are equivalent.
(1.1.a) The equation (1) has innitely many rational solutions with a
bounded denominator.
(1.1.b) We have f = f
1
and g = g
1
, where (x), (x)
Q[x] are linear polynomials, (x) Q[x], and (f
1
(x), g
1
(x)) is a
standard pair over Q such that the equation f
1
(x) = g
1
(y) has
innitely many rational solutions with a bounded denominator.
We make several comments on this result.
Remark 1.2. (i) The implication (1.1.b)(1.1.a) is trivial. The non-
trivial part is (1.1.a)(1.1.b).
(ii) If gcd(deg f, deg g) = 1 then in (1.1.b) we have deg = 1, and
(f
1
(x), g
1
(x)) is a standard pair of the rst or third kind (over Q). This
reproduces a result of Schinzel [27, Theorem 8].
(iii) Write f = a
p
x
p
+ . . . + a
0
and g = b
q
x
q
+ . . . + b
0
, and assume
that a
p
/b
q
is not a perfect power in Q. Then in (1.1.b) we have deg = 1.
(Indeed, a
p
/b
q
= (a

/b

)
deg
, where a

and b

are the leading coecients

of f
1
and g
1
, respectively.) Using this, one can easily prove, for instance,
that the equation

x
m

= y(y 1) . . . (y n +1) has nitely many solutions

in integers x and y, when m and n are integers greater than 2. This was
originally done by Brindza and Pinter [9].
(iv) One can express the assertion f
1
(x) = g
1
(y) has innitely many
rational solutions with a bounded denominator as an explicit arithmetical
condition on the parameters a and b. For instance, for the second kind
this means that a is positive, not a square, and b = ^
Q(

a)/Q
for some
Q(

a). For the other kinds one can proceed similarly. We do not
go into this because we nd Theorem 1.1 in its present form completely
sucient for applications.
264 Yu. F. Bi l u and R. F. Ti chy
(v) Actually, we obtain a more general result, on solutions of (1) in
S-integers of an arbitrary number eld (see Theorem 10.5). In this case one
more kind of pairs can occur; to distinguish it from the standard pairs just
dened, we call this new kind specic pairs (see Section 9).
(vi) Various applications of Theorem 1.1 will be given in the forthcoming
papers [6, 8]. In particular, we solve the Diophantine problem involving
Meixner polynomials, studied in [22]. (Beukers, Shorey and Tijdeman [3]
considered another type of equations of the form (1), using methods very
similar to ours.)
1.3. Un peu dhistoire. Finiteness conditions for the equation (1) were
studied by many authors. For the equation f(x) = y
n
a niteness theorem
was established by Siegel [29] and LeVeque [24]. Evertse and Silverman [13]
obtained a sharp estimate for the number of solutions. (See also a more
recent paper of Voutier [34].)
Starting from Baker [2], methods for the eective analysis of the equation
f(x) = y
n
were developed by Sprindzuk, Trelina, Brindza, Poulakis, Voutier
and Bugeaud; see [31, 10] for the references. An ecient algorithm for the
numerical solution of this equation was suggested in [7].
Davenport, Lewis and Schinzel [12] obtained a niteness condition for the
general equation (1). However, it was too restrictive for many applications.
Fried investigated the problem from various points of view in a remark-
able series of paper [16, 17, 18]. In particular, he gave in [18, Corollary after
Theorem 3] a new niteness condition, much more general than that of [12],
but still far from explicit.
Schinzel [27, Theorem 8] obtained a completely explicit niteness crite-
rion for the equation (1) under the assumption (deg f, deg g) = 1. His result
is, basically, Remark 1.2(ii) of our paper.
Quite recently, Beukers, Shorey and Tijdeman [3] applied a similar ap-
proach to certain particular types of the equation (1).
1.4. An overview of the paper. The proof of Theorem 1.1 follows the
main lines of the arguments of Fried [18] and Schinzel [27]. However, sev-
eral substantially new ideas were required to drop Schinzels assumption
(deg f, deg g) = 1, retaining the explicit character of his result.
Call an absolutely irreducible polynomial F(x, y) Q[x, y] exceptional
if the corresponding plane curve is of genus 0 and has at most 2 points at
innity. To deduce Theorem 1.1 from Siegels theorem, one has to determine
when the polynomial f(x) g(y) has an exceptional factor.
Our argument consists of two parts. In the rst part (Sections 47) we
show that if the polynomial f(x) g(y) itself is exceptional then (f, g) is a
standard pair up to a linear transformation and linear change of variables.
This generalizes the classical Second theorem of Ritt.
Diophantine equation f(x) = g(y) 265
In the second part (Sections 810) we classify pairs (f, g) such that f(x)
g(y) has an exceptional factor. Due to a clever observation of Fried (see
Theorem 8.1) this reduces to solving two independent problems.
(a) Determine when f(x) g(y) has a factor of degree at most 2.
(b) Given a polynomial q(x, y) of degree at most two, determine for
which f(x) and g(x) the polynomial q(f(x), g(y)) is exceptional.
Problem (a) is completely solved in [5]. The solution of (b) depends
on whether
2
q/xy vanishes or not. If it does, then q(f(x), g(y)) can
be written as f
1
(x) g
1
(y), reducing the problem to the generalized Ritts
second theorem, just proved. If
2
q/xy ,= 0 then the solution of (b) is
remarkably simple (see Proposition 9.2).
After all this work is done, our niteness criterion becomes an (almost)
immediate consequence of Siegels theorem (see Section 10).
Acknowledgments. We are pleased to thank Roberto Maria Avanzi,
Frits Beukers, Michael Fried, Peter M uller, Attila Petho, Andrzej Schinzel,
Robert Tijdeman, Gerhard Turnwald and Umberto Zannier for stimulating
discussions and helpful suggestions. We are especially grateful to Andrzej
Schinzel for detecting a number of inaccuracies in the text.
2. Terminology, notation, conventions
2.1. General. We use (a, b) for the greatest common divisor of a and b,
when a and b are either integers or polynomials (in the latter case (a, b) is
well dened up to a multiplicative constant). When it can be confused with
(a, b) as an ordered pair, we write gcd(a, b).
We denote by x| the maximal integer not exceeding x R.
2.2. Fields. All elds in this paper are of characteristic 0 (although
some of the results are valid in arbitrary characteristic). The capital letter
K (with or without indices) always stands for a eld. We assume that all
elds that occur in the paper are contained in one big algebraically closed
(unnamed) eld. In particular, any eld K has a well dened algebraic
closure K, any two elds K and K

have well dened intersection K K

and composite KK

, etc.
2.3. Polynomials. All polynomials are assumed non-constant, unless the
contrary is stated explicitly. Given a polynomial f(x) having s distinct roots
(in an algebraically closed eld), its root type is the array (
1
, . . . ,
s
) formed
of the multiplicities of its roots. Obviously,
1
+. . .+
s
= deg f. The f-type
of a scalar is the root type of the polynomial f(x) . When it is clear
which polynomial is referred to, we say simply type instead of f-type.
If f(x) has at least one multiple root (in other terms, if the f-type of
is distinct from (1, . . . , 1)) then is called an extremum of f(x).
266 Yu. F. Bi l u and R. F. Ti chy
Given a polynomial f(x) K[x] and K of type (
1
, . . . ,
s
), put

f
() = (
1
1) + . . . + (
s
1) = deg f s
(so that
f
() > 0 if and only if is an extremum of f). Then
(2)

f
() = deg f 1.
To see this, notice that
f
() = deg gcd(f , f

). Hence the sum in (2) is

equal to deg f

= deg f 1, as wanted. Equality (2) will often be used in

the paper, sometimes without special reference.
2.4. Curves and function elds. Let F(x, y) K[x, y] be an absolutely
irreducible polynomial. By points of the plane curve F(x, y) = 0 we always
mean algebraic points, i.e. places of its function eld K(x, y). (With a
standard abuse of notation, we use x, y for both independent variables and
coordinate functions on the plane curve.) The place is innite if it is a pole
of x or y. The corresponding point of the plane curve is called a point at
innity.
Similarly, by the genus of a plane curve we always mean the genus of its
function eld.
3. Dickson polynomials. In this section, we collect miscellaneous
facts about Dickson polynomials.
For a K, the nth Dickson polynomial D
n
(x, a) is dened from the
relation
(3) D
n
(z + a/z, a) = z
n
+ (a/z)
n
.
The following identities will often be used in the paper, sometimes without
special reference:
D
1
(x, a) = x; D
2
(x, a) = x
2
2a; (4)
D
mn
(x, a) = D
m
(D
n
(x, a), a
n
); (5)
b
n
D
n
(x, a) = D
n
(bx, b
2
a); (6)
D
2n
(x, a) 2a
n
= (x
2
4a)E
n
(x, a)
2
, (7)
where the polynomial E
n
(x, a) is dened from the relation
(8) E
n
(z + a/z, a) = (z
n
(a/z)
n
)/(z a/z).
The proofs of (4)(7) are immediate, upon substituting x = z + a/z into
both sides.
An important consequence of (6) is
(9) (a, cos 2 K) (D
n
(xcos , a) K[x]).
Here is a slightly less obvious consequence of (4)(7).
Diophantine equation f(x) = g(y) 267
Proposition 3.1. Let m, n be positive even numbers with n/2 odd. Then
(10)
a
m/2
u
2
+ bv
2
= 4ab

a
m/2
D
m
(a
(2n)/4
D
n/2
(v, a), a) = b
n/2
D
n
(uE
m/2
(v, a), b).
Pr o o f. This is just a calculation:
b
n/2
D
n
(uE
m/2
(v, a), b) = D
n/2
(D
2
(uE
m/2
(v, a)/

b, 1), 1)
= D
n/2
(2 b
1
u
2
E
m/2
(v, a)
2
, 1)
= D
n/2
(2 + a
m/2
(v
2
4a)E
m/2
(v, a)
2
, 1)
= D
n/2
(a
m/2
D
m
(v, a), 1)
= D
mn/2
(v/

a, 1)
= a
m/2
D
m
(a
(2n)/4
D
n/2
(v, a), a),
as wanted.
For further facts about Dickson polynomials, including equivalent de-
nitions, dierential equations, etc., see [25, Chapter 2] and [32].
3.1. Factorization. It is well known that D
n
(x, a) + D
n
(y, a) splits into
factors of degree at most two. More precisely, put
(11)
n
(x, y, a) =

1k<n
k1 mod 2
(x
2
2xy cos(k/n) + y
2
4a sin
2
(k/n)).
Then
(12) D
n
(x, a) + D
n
(y, a) =

n
(x, y, a) if n is even,
(x + y)
n
(x, y, a) if n is odd
(see, for instance, [5, Proposition 3.1]). If a ,= 0 then the factors on the
right-hand side of (11) are absolutely irreducible.
3.2. Semi-denite polynomials. Call a polynomial F(x, y) R[x, y] semi-
denite if there exist positive constants X, C and A such that [F(x, y)[
C max([x[, [y[)
A
as soon as max([x[, [y[) X. The following properties of
semi-denite polynomials are immediate.
Proposition 3.2. (i) A product of semi-denite polynomials is semi-
denite.
(ii) If F(x, y) is semi-denite and f(x), g(x) are non-constant real poly-
nomials then F(f(x), g(y)) is semi-denite.
(iii) If F(x, y) is semi-denite then the level set (x, y) R
2
: F(x, y) =
C is bounded for any C R.
268 Yu. F. Bi l u and R. F. Ti chy
Proposition 3.3. Let a be a real number. If d = gcd(m, n) is even then
the polynomial
(13) D
m
(x, a
n/d
) + D
n
(y, a
m/d
)
is semi-denite. If d = gcd(m, n) is odd and greater than 1 then the poly-
nomial
(14)
D
m
(x, a
n/d
) + D
n
(y, a
m/d
)
D
m/d
(x, a
n/d
) + D
n/d
(y, a
m/d
)
is semi-denite.
Pr o o f. One immediately veries that all the quadratic factors in (11)
are semi-denite, which implies that the polynomial
n
(x, y, a) is semi-
denite for n > 1. Since each of the polynomials (13) and (14) is equal
to
d
(D
m/d
(x, a
n/d
), D
n/d
(x, a
m/d
), a
mn/d
), the result follows.
4. The genus formula. Let f(x), g(x) be polynomials over a eld K
of degrees m, n respectively. Given K of f-type (
1
, . . . ,
s
) and g-type
(
1
, . . . ,
t
), dene the quantities
() =

1is

1jt
(
i
,
j
),
() =

1is

1jt
(
i
(
i
,
j
)) = mt (),
() =

1is

1jt
(
j
(
i
,
j
)) = ns ().
Obviously, mn () = () = () = 0 for all but nitely many K.
Proposition 4.1. Assume that f(x) = g(y) is an absolutely irreducible
plane curve of genus g. Then
2g 2 =

K
() md =

K
() n d (15)
=

K
(mn ()) mn d,
where d = (m, n).
Pr o o f. This is due to Fried [17, Proposition 2 on page 240]. Since our
notation is very dierent from Frieds, we include a proof for the convenience
of the reader.
We use the RiemannHurwitz formula
(16) 2g 2 =

P
(e
P
1) 2n,
Diophantine equation f(x) = g(y) 269
where the sum extends to the places P of the function eld K(x, y) and e
P
is the ramication index of the place P over the eld K(x).
Fix , , K satisfying
(17) f() = g() = .
Let be the order of the root of the polynomial f , and the order
of the root of the polynomial g . Then there are exactly (, ) places
P of K(x, y) with the property
(18) x(P) = and y(P) = ,
and e
P
= /(, ) for every such P. It follows that

P satises (18)
(e
P
1) = (, ).
Dening z K(x, y) by z = f(x) = g(y), we obtain

z(P)=
(e
P
1) =

(,) satis-
es (17)

P satises (18)
(e
P
1) =
s

i=1
t

j=1
(
j
(
i
,
j
)) = ().
Also, there exist d = (m, n) places P with x(P) = y(P) = , and e
P
= n/d
for every such P. Hence

z(P)=
(e
P
1) = n d.
Now
2g 2 =

z(P)=
(e
P
1) +

z(P)=
(e
P
1) 2n =

K
() n d,
which proves the second formula in (15). The rst formula follows by sym-
metry. Finally, using (2), we obtain

K
() n d =

K
((m
f
())n ()) n d
=

K
(mn ()) n

f
() n d
=

K
(mn ()) mn d,
which proves the last formula in (15).
5. Polynomials with a few extrema. It is well known that Dickson
polynomials D
n
(x, a) with a ,= 0 have exactly two extrema. More precisely,
one has the following.
270 Yu. F. Bi l u and R. F. Ti chy
Proposition 5.1. If a ,= 0 and n 3 then D
n
(x, a) has exactly two
extrema 2a
n/2
. If n is odd then both are of type (1, 2, . . . , 2). If n is even
then 2a
n/2
is of type (1, 1, 2, . . . , 2), and 2a
n/2
is of type (2, . . . , 2).
For a proof see, for instance [5, Proposition 3.3].
It is of fundamental importance that, basically, the Dickson polynomials
are characterized by this property. We shall use this classical fact in the
following form.
Theorem 5.2. Let f(x) K[x] be a polynomial of degree m having ex-
actly two extrema in K. Moreover, let its extrema be of one of the following
types:
(19) (2, . . . , 2), (1, 2, . . . , 2), (1, 1, 2, . . . , 2).
Then f(x) = D
m
(x + , a) + , where a, K

and , K.
Pr o o f. We use induction on m. If m is odd then both the extrema are
of the type (1, 2, . . . , 2). In this case the assertion is a particular case of [32,
Lemma 1.11] (reproduced in [25] as Lemma 6.16).
Now assume that m is even, and write m = 2n. Since f(x) has two
extrema, we have m 4. By (2), one of the extrema is of type (2, . . . , 2)
and the other is of type (1, 1, 2, . . . , 2). Since the extrema have distinct types,
they both belong to K. Without loss of generality we may assume that the
polynomial f(x) is monic and that the extremum of type (2, . . . , 2) is 0.
This means that f(x) = g(x)
2
, where g(x) K[x] is a monic polynomial of
degree n.
If n = 2 then g(x) = D
2
(x + , a), where a, K. Moreover, a ,= 0,
because g(x) has simple roots.
Now assume that n = deg g > 2. Let ,= 0 be the other extremum of
f(x). Then (g(x)

)(g(x) +

) has 2 simple roots, all the other roots

being of order 2. It follows that

are extrema of g(x), of one of the

types from (19). Identity (2) applied to the polynomial g(x) certies that
it has no other extrema. By induction, g(x) = D
n
(x + , a) + , where
a, K

and , K. Since g(x) is monic, = 1. Since its extrema

are symmetric with respect to 0, we have = 0.

Thus, in either the case n = 2 or n > 2 we have g(x) = D
n
(x + , a),
where a K

and K. It follows that f(x) = g(x)

2
= D
m
(x+, a)+2a
n
,
as wanted.
Corollary 5.3. Let f(x) K[x] and
1
,
2
K be such that f(x)
i
has at most s
i
simple roots, where s
1
+ s
2
2. (We assume that
1
,=
2
.)
Then f(x) = D
m
(x + , a) + , where a, K

and , K.
Pr o o f. We may assume that m = deg f 3, since otherwise there is
nothing to prove. In particular, both
1
and
2
are extrema of f.
Diophantine equation f(x) = g(y) 271
We have
(20)
f
(
i
) (ms
i
)/2 (i = 1, 2),
the equality being attained when f(x)
i
has s
i
simple and (m s
i
)/2
double roots. On the other hand, (2) implies that
(ms
1
)/2 + (ms
2
)/2 = m1
f
(
1
) +
f
(
2
).
Hence we have equalities in (20), and f has no extrema other than
i
. We
have shown that f satises the assumptions of Theorem 5.2.
Corollary 5.4. Let f(x) K[x] be a polynomial of degree m such that
for some b K

, the polynomial f(x)

2
4b has at most 2 roots of odd order.
Then for some linear polynomial (x) K[x] one of the following options
takes place.
(5.4.a) The degree m is even, b is a perfect square in K, and f(x) =

bD
m
((x)

a, 1), for some a K and a suitable choice of the

sign of

b.
(5.4.b) The degree m is odd, and f(x) =

bD
m
((x)

b, 1).
Pr o o f. As b ,= 0, the polynomial f(x) satises the assumption of Corol-
lary 5.3. Hence f(x) = D
m
(x + , a) + , where a, K

and , K.
The extrema of f(x) are 2

b, which implies = 0 and b =

2
a
m
. If m
is even then f(x) = a
m/2
D
m
((x)

a, 1), where (x) = (x + )/a. If m is

odd then f(x) =

bD
m
((x)

b, 1), where (x) = (x + )

1
a
(m+1)/2
.
Proposition 5.5. If f(x) K[x] has only one extremum then f(x) =
a(x )
m
+ , where a, , K and a ,= 0.
Pr o o f. If is the extremum then (2) implies that its f-type is (n), and
the result follows.
6. Ritts second theorem. Let f
1
(x), g
1
(x), f
2
(x), g
2
(x) be polyno-
mials over K. We say that pairs (f
1
, g
1
) and (f
2
, g
2
) are equivalent over K
(notation: (f
1
, g
1
)
K
(f
2
, g
2
)) if there exist (non-constant) linear polynomi-
als (x), (x), (x) K[x] such that f
1
= f
2
and g
1
= g
2
.
Theorem 6.1. Let f(x), g(x) K[x] be polynomials of degree m and n
respectively. Assume that d = gcd(m, n) 2, and that
(21) f(x) = g(y)
is an absolutely irreducible plane curve of genus 0. Then (f, g)
K
(f
1
, g
1
),
where (f
1
, g
1
) is a standard pair over K.
The case d = 1 of this theorem follows from the classical second theorem
of Ritt [26], as presented, for instance, in [27, Section 5]. The case d = 2
272 Yu. F. Bi l u and R. F. Ti chy
was examined by Fried [18, Theorem 3]. We give, however, a much more
explicit classication of the possible pairs (f, g).
Recently, Avanzi and Zannier [1] classied the pairs (f, g) over an al-
gebraically closed eld and over Q such that gcd(deg f, deg g) = 1 and the
genus of f(x) = g(y) is 1. Extending their result to number elds leads to
interesting problems in the arithmetic of elliptic curves.
Theorem 6.1 will be proved in the next section. We conclude this section
with several auxiliary statements required for the proof.
As the genus formula suggests, we have to deal with sums of the form

(
i
,
j
). Some simple properties of such sums are listed in the following
lemma.
Lemma 6.2. Let
1
, . . . ,
s
and
1
, . . . ,
t
be positive integers, and put
(22) m =
1
+ . . . +
s
, n =
1
+ . . . +
t
, =

1is

1jt
(
i
,
j
).
Then
(i) We have sn, the equality being attained when every
j
divides
every
i
.
(ii) If min(
1
, . . . ,
s
) = 1, then n(s 1) + t.
(iii) (Schinzel) If gcd(
1
, . . . ,
s
,
1
, . . . ,
t
) = 1, then
max(m(t 1) + s, n(s 1) + n/2).
Pr o o f. (i) For every i we have (
i
,
1
)+. . . +(
i
,
t
)
1
+. . . +
t
= n,
the equality being attained when every
j
divides this
i
. Summing up over
i, we complete the proof.
(ii) Say, let
1
= 1. Then
(
i
,
1
) + . . . + (
i
,
t
)

= t if i = 1,
n if i 2.
We again complete the proof, summing up over i.
(iii) We consider two cases.
Case 1: For every i either
there exists a j with (
i
,
j
) = 1, or (23)
there exist distinct j
1
and j
2
such that
i
does not divide
j
1
and
j
2
. (24)
If for a given i we have (23) then
(
i
,
1
) + . . . + (
i
,
t
) (t 1)
i
+ 1.
If we have (24) then (
i
,
j
1
) and (
i
,
j
2
) do not exceed
i
/2, and
(
i
,
1
) + . . . + (
i
,
t
) (t 1)
i
< (t 1)
i
+ 1.
Summing up over i, we obtain (t 1)(
1
+. . . +
s
) +s = (t 1)m+s.
Diophantine equation f(x) = g(y) 273
Case 2: There exist i
0
and j
0
such that
(25) j ,= j
0

i
0
[
j
and d := (
i
0
,
j
0
) > 1.
It follows from (25) that d divides
1
, . . . ,
t
. But
gcd(
1
, . . . ,
s
,
1
, . . . ,
t
) = 1,
whence d does not divide at least one of the numbers
i
, say,
1
. It follows
that none of the
j
divides
1
, which implies that (
1
,
j
)
j
/2 for all j.
Therefore
(
i
,
1
) + . . . + (
i
,
t
)

n/2 if i = 1,
n if i 2.
Summing up over i, we obtain (s1)n+n/2. The proof is complete.
The following trivial observation will often be used.
Proposition 6.3. If f(x) has at least r simple roots then ()
r
g
() (we use the notation of Section 4).
Pr o o f. At least r of the numbers
1
, . . . ,
s
are equal to 1, say,
1
=
. . . =
r
= 1. Hence
()
r

i=1
t

j=1
(
j
(
i
,
j
)) =
r

i=1
t

j=1
(
j
1) = r
g
(),
as wanted.
Finally, we consider three simple particular cases of Theorem 6.1.
Proposition 6.4. In the set-up of Theorem 6.1 assume that m 3,
n 2 and f(x) = a(x)
m
+. Then d = 1 and g(x) = b(x)
r
g
1
(x)
m
+,
where 0 < r < m, b K

, K and the polynomial g

1
(x) K[x] may be
constant.
Pr o o f. Plainly, K. Hence we may write g(x) = g
2
(x)g
1
(x)
m
+ ,
where g
1
, g
2
K[x] and the root type of g
1
is (
1
, . . . ,
t
) with
i
< m. We
have
(26) gcd(m,
1
, . . . ,
t
) = 1,
since otherwise the curve (21) would have been reducible.
The second formula in (15) implies that 2 = 2g 2 = () m d
(because (

) = 0 for

,= ). Further,
() =
t

j=1
(m(m,
j
)) > tm/2,
because (m,
j
) m/2 for all j, and (m,
j
) < m/2 for at least one j
(otherwise we violate (26)).
274 Yu. F. Bi l u and R. F. Ti chy
If t 2 then 2 > (t 2)m/2 d, a contradiction. Thus, t = 1, which
completes the proof.
Proposition 6.5. In the set-up of Theorem 6.1 assume that m = 2 and
f(x) = a(x )
2
+ . Then g(x) = g
1
(x)
2
g
2
(x) + , where g
2
(x) K[x] is
a separable polynomial of degree at most 2, and the polynomial g
1
(x) K[x]
may be constant.
Pr o o f (similar to the proof of Proposition 6.4 and simpler). Now we
have
1
= . . . =
t
= 1 and () = t. The genus formula reads 2 = t2d,
which yields t = deg g
2
= d 2, as desired.
Proposition 6.6. In the set-up of Theorem 6.1 assume that n is odd,
m, n 3 and g(x) = D
n
(x, b), where b K

. Then for some linear polyno-

mial (x) K[x] we have the following.
(i) If m is odd then f(x) = b
(nm)/2
D
m
((x), b).
(ii) If m is even then b is a perfect square in K, and we have f(x) =
a
m/2
b
n/2
D
n
((x), a) for some a K

and for a suitable choice of the sign

of b
n/2
.
Pr o o f. By Proposition 5.1, g(x) has two extrema b
n/2
, both of type
(1, 2, . . . , 2). Let s
+
(respectively, s

) be the number of odd entries in the

f-type of b
n/2
(respectively, b
n/2
). Then (b
n/2
) = s

(n1)/2, and the

second formula in (15) implies that 2 (s
+
+s

)(n1)/2n1. It follows
that s
+
+s

= 2, and Corollary 5.3 implies that f(x) = D

m
(x+, a) +,
where , a K

and , K.
The extrema of f are a
m/2
+ . On the other hand, they are b
n/2
.
It follows that = 0 and
(27) = a
m/2
b
n/2
,
where 1, 1 depends on the signs of a
m/2
and b
n/2
.
Now recall that K. If m is even, then (27) implies that b is a
perfect square in K, say, b = b
2
1
. The sign of b
1
can be dened to have
f(x) = a
m/2
b
n
1
D
n
((x), a), which completes the proof in this case.
If m is odd then (27) implies that a/b is a perfect square in K, say, b =
ac
2
. We dene that sign of c so that (27) turns to f(x)= b
(nm)/2
D
n
((x), b)
with (x) = c(x + ). This completes the proof also in this case.
7. Proof of Theorem 6.1. Everywhere in this section equivalent
means equivalent over K, and standard pair means standard pair over
K.
If min(m, n) = 1 then (f, g) is equivalent to a standard pair of the rst
kind. If min(m, n) = 2 then (f, g) is equivalent to a standard pair of the
Diophantine equation f(x) = g(y) 275
rst or second kind by Proposition 6.5. Hence we may assume that
min(m, n) 3.
We use the quantities (), etc., dened at the beginning of Section 4. We
start with the following observation.
Assertion 1. Let K have f-type (
1
, . . . ,
s
) and g-type (
1
, . . . ,
t
).
Then
(28) gcd(
1
, . . . ,
s
,
1
, . . . ,
t
) = 1.
Indeed, assume that for some we have q = gcd(
1
, . . . ,
s
,
1
, . . . ,
t
)
> 1. Then both f(x) and g(x) are qth powers in the ring K[x],
which contradicts the irreducibility of the curve (21).
The following assertion is just a reformulation of Lemma 6.2(iii).
Assertion 2. For any K either ()
f
(), or () n/2.
We say that K is a -point (respectively, -point) (
2
) if
f
() > ()
(respectively,
g
() > ()). Reformulating item (ii) of Lemma 6.2, we
obtain the following.
Assertion 3. If is a -point then f(x) has no simple roots. In
particular,
f
() m/2.
It follows that there can be at most one -point and at most one -point.
Case 1: There exist a -point
1
and a -point
2
.
Subcase 1.1:
1
=
2
. We follow [27, pp. 3738] with some changes.
Assertion 2 implies that

f
(
1
) > (
1
) m/2,
g
(
1
) > (
1
) n/2.
Write
f
(
1
) = m/2 + and
g
(
1
) = n/2 + . Without loss of generality
. Assume that g(x) has an extremum
3
,=
1
. Since

f
(
3
) m1
f
(
1
) = m/2 1,
the polynomial f(x)
3
has at least 2+2 simple roots. By Proposition 6.3
(
3
) (2 + 2)
g
(
3
)
g
(
3
) + 2 + 1.
We also have
(
1
)
g
(
1
)
g
(
1
) ,
and ()
g
() for ,=
1
,
3
. By the genus formula (15),
2 =

K
() n d

g
() + + 1 n d = d > d,
a contradiction.
(
2
) In Ritts [26] terminology, extra point of f (respectively, g).
276 Yu. F. Bi l u and R. F. Ti chy
Thus, g(x) cannot have an extremum distinct from
1
. Proposition 5.5
implies that g(x) = a(x )
n
+
1
, and Proposition 6.4 implies that (f, g)
is equivalent to a standard pair of the rst kind.
Subcase 1.2:
1
,=
2
. By Assertion 3,
(29)
f
(
1
) m/2,
g
(
2
) n/2,
and by Lemma 6.2,
(30) (
1
) n(m
f
(
1
)), (
2
) m(n
g
(
2
)).
Using (29), (30) and Proposition 4.1, we obtain
2 =

K
(mn ()) mn d
(mn (
1
)) + (mn (
2
)) mn d (31)

f
(
1
)n +
g
(
2
)mmn d
d. (32)
Thus, d = 2, and inequalities (31) and (32) are equalities. This has the
following consequences:
() = mn for any ,=
1
,
2
. This implies that f and g have no
extrema distinct from
1
and
2
.
Inequalities (29) are equalities, which implies that the f-type of
1
and
the g-type of
2
are (2, . . . , 2).
Inequalities (30) are equalities. Hence Lemma 6.2(i) together with (2)
implies that the f-type of
2
and the g-type of
1
are (1, 1, 2, . . . , 2).
Now Theorem 5.2 implies
f(x) = D
n
(x + , a) + , g(x) =

D
n
(x +

, b) +

.
Since

1
= a
m/2
+ =

b
n/2
+

,
2
= a
m/2
+ =

b
n/2
+

,
we have =

and a
m/2
=

b
n/2
, which shows that (f, g) is equivalent
to a standard pair of the fourth kind. This completes the proof in Case 1.
Case 2: There exist no -point. If f has a single extremum, then
f(x) = a(x )
m
+ by Proposition 5.5, which reduces the theorem to
Proposition 6.4.
From now on assume that
(33) f has at least two distinct extrema.
Subcase 2.1: For every extremum of f, the polynomial g has at
most one simple root. Let
1
and
2
be two distinct extrema of f (which
exist by (33)). Since g
1
and g
2
have at most one simple root, we
Diophantine equation f(x) = g(y) 277
have
g
(
1
),
g
(
2
) (n 1)/2. Since
g
(
1
) +
g
(
2
) n 1, we have

g
(
1
) = (
2
) = (n1)/2 and the polynomial g has no extrema other than

1
and
2
. Also, both
1
and
2
have g-type (1, 2, . . . , 2). In particular, n
is odd and d = 1.
It follows from Theorem 5.2 that g(x) = D
n
(x+, b) +, where , b
K

and , K. If m is even then Proposition 6.6 implies that b = b

2
1
,
where b
1
K

, and f(x) = a
m/2
b
n
1
D
m
((x), a) + . Writing
f(x) = a
mn/2
b
n
1
D
m
(a
(n1)/2
(x), a
n
) + ,
g(x) = a
mn/2
b
n
1
D
n
(a
(m1)/2
b
1
1
(x + ), a
m
) + ,
we conclude that (f, g) is equivalent to a standard pair of the third kind.
If m is odd then Proposition 6.6 implies that
f(x) = b
(nm)/2
D
n
((x), b) + .
Writing
f(x) = b
n(m+1)/2
D
n
(b
(n1)/2
(x), b
n
) + ,
g(x) = b
n(m+1)/2
D
n
(b
(m1)/2
(x + ), b
m
) + ,
we again see that (f, g) is equivalent to a standard pair of the third kind.
Subcase 2.2: For some extremum
1
of f, the polynomial g
1
has at
least two simple roots. Since the argument in this subcase is rather lengthy,
we divide it into short logically complete steps.
Step 1: The f-type and further properties of
1
. By Proposition 6.3 we
have (
1
) 2
f
(
1
). Since there is no -point, ()
f
() for all K.
By the genus formula,
2 = (
1
)+

=
1
()nd 2
f
(
1
)+

=
1

f
()nd =
f
(
1
)1d.
Since
1
is an extremum of f, we have
f
(
1
) 1. Hence
d = 2,
f
(
1
) = 1, (
1
) = 2, (34)
() =
f
() ( ,=
1
). (35)
It follows from (34) that the f-type of
1
is (2, 1, . . . , 1).
Step 2: The denition of
2
. Equality (35) together with Proposition 6.3
implies that for any extremum of f(x), distinct from
1
, the polynomial
g(x) has at most one simple root. Since n is even,
g
() n/2 for any
such . Also, (34) and Proposition 6.3 imply that g(x)
1
has exactly two
simple roots, whence
g
(
1
) (n 2)/2. It follows that f has exactly two
extrema, one of which is
1
; denote the other by
2
. Since
g
(
1
) +
g
(
2
)
(n 2)/2 + n/2 = n 1, these
1
and
2
are the only extrema of g as well,
278 Yu. F. Bi l u and R. F. Ti chy
and
(36)
g
(
1
) = (n 2)/2,
g
(
2
) = n/2.
Step 3: Possible g-types of
1
and
2
. As we have seen in the previous
step, g(x)
2
has at most one simple root, and g(x)
1
has exactly two
simple roots. Comparing this with (36), we conclude that the g-type of
1
is (1, 1, 2, . . . , 2), and the g-type of
2
is either (1, 3, 2, . . . , 2) or (2, . . . , 2).
Step 4: Possible m and n. The third genus formula (15) implies that
2 = mn (
1
) (
2
) 2. The f- and g-types of
1
being known, one
nds (
1
) = mn/2 + m2. Hence
(37) (
2
) = mn/2 m + 2.
On the other hand, by Lemma 6.2(i),
(38) (
2
) n(m
f
(
2
)) = n(
f
(
1
) + 1) = 2n.
Comparing (37) and (38), we obtain
(39) m (2n 2)/(n/2 1),
which implies one of the following options:
m = 6, n = 4, (40)
m = 4, n 2 (mod 4). (41)
Step 5: Impossibility of (41). In case (41) we have
f
(
2
) = 3
f
(
1
) =
2, and the f-type of
2
can be either (2, 2) or (1, 3).
Notice that the f-type (2, 2) and the g-type (2, . . . , 2) together vio-
late (28). There remain three possibilities for the f- and g-types of
2
,
respectively:
(1, 3) and (1, 3, 2, . . . , 2); (2, 2) and (1, 3, 2, . . . , 2); (1, 3) and (2, . . . , 2).
In the rst case (
2
) = n + 2, in the second case (
2
) = 2n 4, and in
the third case (
2
) = n. In any case, this contradicts (37), which shows
that (41) is impossible.
Step 6: The f- and g-types of
2
. Thus, we have (40). Moreover, we
have equality in (38), which means, by Lemma 6.2(i), that
(42) every entry of the g-type of
2
divides every entry of its f-type.
This shows that the g-type (2, 2) is impossible (it violates (28)), and the
single possibility for the g-type of
2
is (1, 3). By (42), the only possible
f-type for
2
is (3, 3).
Step 7: Normalizing
1
and
2
. Since f has no extrema of type (3, 3)
other than
2
, we have
2
K. Similarly,
1
K. Replacing f and g by
(f
2
)/(
2

1
) and (g
2
)/(
2

1
), we may assume that
1
= 1 and

2
= 0.
Diophantine equation f(x) = g(y) 279
Step 8: The polynomial f. Since
2
= 0 is an extremum of f of type
(3, 3), we have f(x) = f
1
(x)
3
, where K

and f
1
(x) K[x] is a
separable quadratic polynomial. After a linear change of the variable we
may write f
1
(x) = a
1
x
2
a
2
, where a
1
, a
2
K

. The second extremum

of f is a
3
2
=
1
= 1. Thus, = a
3
2
and f(x) = (ax
2
1)
3
, where
a = a
1
/a
2
.
Step 9: The polynomial g. Since
2
= 0 has g-type (1, 3), we may write,
after a linear change of variable, that g(x) = (px q)x
3
, where p, q K

.
The second extremum of g is 27q
4
/(256p
3
) = 1. Hence (q/4)
4
= (p/3)
3
=

12
1
, where
1
K

. Thus, q/4 =
3
1

4
and p/3 =
4
1

3
, where
3
and
4
are third and fourth root of unity, respectively (not necessarily primitive).
Notice that
3
,
4
K. Putting =
1

1
3

4
, we obtain q = 4
3
and p = 3
4
.
Thus, g(x) = 3(x)
4
4(x)
3
.
We have shown that (f, g) is equivalent to a standard pair of the fth
kind. The theorem is proved.
8. Irreducible factors of f(x) g(y). Everywhere in this section
irreducible means irreducible over K, and factor means K-factor,
unless the contrary is stated explicitly.
Given f(x) K[x], denote by
f
the splitting eld of f(x) t over K(t)
(where t is a new indeterminate). Two polynomials f(x) and g(x) are called
similar if
f
=
g
.
A place of
f
is called innite if it lies over the innite place of K(t).
The ramication index (over K(t)) of any innite place of
f
is equal to
deg f. It follows that
(43) similar polynomials have equal degrees.
Fried [16, Proposition 2] observed that the problem of factoring polyno-
mials of the form f(x) g(y) reduces to the case of similar f and g.
Theorem 8.1 (Fried). Given f(x), g(x) K[x], there exist similar poly-
nomials f
1
(x), g
1
(x) K[x], and polynomials f
2
(x), g
2
(x) K[x] such that
f = f
1
f
2
, g = g
1
g
2
,
and
for every irreducible factor F
1
(x, y) of f
1
(x) g
1
(y), the polynomial
F(x, y) := F
1
(f
2
(x), g
2
(y)) is irreducible;
every irreducible factor of f(x) g(y) is of the form F
1
(f
2
(x), g
2
(y)),
where F
1
(x, y) is an irreducible factor of f
1
(x) g
1
(y).
Thereby,
(44) F
1
(x, y) F(x, y) := F
1
(f
2
(x), g
2
(y))
gives a one-to-one correspondence between the irreducible factors of f
1
(x)
g
1
(y) and of f(x) g(y).
280 Yu. F. Bi l u and R. F. Ti chy
Pr o o f. We give a proof for the convenience of the reader. We use
induction on deg f + deg g. If f(x) t has a root in
g
and g(x) t has a
root in
f
then
f
=
g
and there is nothing to prove. Therefore we may
assume that, say, g(x) t has no root in
f
.
Let y
1
be a root of g(x) t. By assumption, y
1
,
f
. We have a tower
of rational elds:
K(t)
f
K(y
1
) K(y
1
).
The innite place of the eld K(t) totally ramies in K(y
1
). Hence it totally
ramies in the intermediate eld
f
K(y
1
). Therefore
f
K(y
1
) = K(y
2
),
where y
2
is integral over the ring K[t]. We have t = g(y
2
) K[y
2
] and
y
2
= g(y
1
) K[y
1
]. It is important to notice that deg g < deg g, because
K(y
2
) is a proper subeld of K(y
1
).
Now let F(x, y) = a
q
(y)x
q
+. . . +a
0
(y) be a factor of f(x) g(y). Then
a
0
(y
1
), . . . , a
q
(y
1
) are polynomials in the roots of f(x) g(y
1
) = f(x) t.
Hence a
0
(y
1
), . . . , a
q
(y
1
)
f
. It follows that
a
0
(y
1
), . . . , a
q
(y
1
)
f
K(y
1
) = K(y
2
).
Therefore a
i
(y) = a
i
( g(y)), where a
0
(y), . . . , a
q
(y) K[y].
Obviously,

F(x, y) := a
q
(y)x
q
+. . . +a
0
(y) is a factor of f(x) g(y). We
have proved that every factor of f(x) g(y) is of the form

F(x, g(y)), where

F(x, y) is a factor of f(x) g(y).

Conversely, for any factor

F(x, y) of f(x) g(y), the polynomial F(x, y)=

F(x, g(y)) is a factor of f(x) g(y), distinct

F giving rise to distinct F.
Hence

F(x, y) F(x, y) :=

F(x, g(y))
is a one-to-one correspondence between the factors of f(x) g(y) and of
f(x) g(y). Moreover, since this correspondence preserves the divisibility
relation, it restricts to a one-to-one correspondence between the irreducible
factors of f(x) g(y) and of f(x) g(y).
Since deg g < deg g, there exist, by induction, similar polynomials f
1
(x),
g
1
(x) K[x], and polynomials f
2
(x), g
2
(x) K[x] such that f = f
1
f
2
,
g = g
1
g
2
and F
1
(x, y)

F(x, y) := F
1
(f
2
(x), g
2
(y)) is a one-to-one
correspondence between the irreducible factors of f
1
(x)g
1
(y) and of f(x)
g(y). Putting g
2
= g
2
g, we complete the proof.
As Fried indicated in [18], the study of the Diophantine equation
f(x) = g(y) requires classication of polynomials of the form f(x) g(y)
having quadratic factors. This problem is solved in [5].
Theorem 8.2. Let f(x) and g(x) be polynomials over K, and let q(x, y)
K[x, y] be an irreducible (over K) factor of f(x) g(y) of degree at most 2.
Diophantine equation f(x) = g(y) 281
Then there exist polynomials (x), f
1
(x), g
1
(x) K[x] such that f = f
1
,
g = g
1
and one of the following two options takes place.
(8.2.a) We have max(deg f
1
, deg g
1
) = 2 and q(x, y) = f
1
(x) g
1
(y).
(8.2.b) There exists an integer n > 2 with cos(2/n) K such that for
some K

and a, , K we have
f
1
(x) = D
n
(x + , a), g
1
(x) = D
n
((x + ) cos(/n), a),
and q(x, y) is a quadratic factor of f
1
(x) g
1
(y). If q(x, y) is
absolutely irreducible then a ,= 0.
Pr o o f. See [5, Theorem 1.3].
Note in conclusion that the problem of factorization of f(x) g(y) has a
long history, which cannot be presented here. We just mention that among
the contributors were Cassels, Davenport, Feit, Fried, Lewis, Schinzel, Tver-
berg, and many others. In particular, Tverberg [33, Chapter 2] obtained
some results complementary to Theorem 8.2. Fried [16, Theorem 1 on
pp. 141142] proved that if f is an indecomposable (
3
) polynomial of degree
n and K contains no complex subeld of Q(e
2i/n
) (in particular, if K = Q),
then f(x) g(y) is reducible (over Q) only in trivial cases. He also showed
that the problem with indecomposable f and general K reduces to a certain
problem in group theory, studied by Feit [14]. For further advances see [15,
19, 20]. Quite recently, Cassou-Nogu`es and Couveignes [11], essentially us-
ing the previous work of Fried and Feit, and assuming the classication of
nite simple groups, completely classied the pairs of polynomials f, g with
indecomposable f such that f(x) g(y) is reducible (
4
).
9. Exceptional factors of f(x) g(y) and specic pairs. An ab-
solutely irreducible polynomial F(x, y) K[x, y] is called exceptional if the
plane curve F(x, y) = 0 is of genus 0 and has at most two points at innity.
In this section we use Theorems 8.1 and 8.2 to classify polynomials of
the form f(x) g(y) having exceptional factors.
Proposition 9.1. Let (x, y), f(x, y), g(x, y) K[x, y] be non-constant
polynomials such that (f(x, y), g(x, y)) is an exceptional polynomial. As-
sume that f and g are algebraically independent over K. Then (x, y) itself
is an exceptional polynomial.
Pr o o f. First, since (x, y)= (f(x, y), g(x, y)) is absolutely irreducible,
so is (x, y).
(
3
) A polynomial is indecomposable if it is not a composition of two polynomials of
smaller degree.
(
4
) Cassou-Nogu`es and Couveignes assume that both f and g are indecomposable.
But [16, assertion (2.38) on p. 142] implies that the assumption about g can be dropped.
282 Yu. F. Bi l u and R. F. Ti chy
Second, the eld K(u, v) of rational functions on the curve (u, v) = 0 is
contained in the eld K(x, y) of rational functions on the curve (x, y) = 0,
the embedding being dened by u f(x, y) and v g(x, y). By the L uroth
theorem, the curve (x, y) = 0 is of genus 0.
Third, since f(x, y) and g(x, y) are polynomials, the innite places of
the eld K(x, y) restrict to the innite places of the eld K(u, v). Since the
former eld has at most 2 innite places, so does the latter.
Proposition 9.2. Let q(x, y) = x
2
+ 2xy + y
2
+ K[x, y] be a
quadratic polynomial with (
2
) ,= 0. Let f(x), g(x) K[x] be non-
constant polynomials of degrees m and n, respectively, such that q(f(x), g(y))
is an exceptional polynomial. Then (m, n) = 1. Furthermore, dene b =
/(4(
2
)). Then for some linear polynomial (x) K[x] one of the
following options takes place.
(9.2.a) The degree m is even, b is a perfect square in K, and f(x) =

bD
m
((x)

a, 1) for some a K and a suitable choice of the

sign of

b.
(9.2.b) The degree m is odd and f(x) =

bD
m
((x)

b, 1).
We have similar options for g(x) with c = /(4(
2
)) instead of b,
and with another linear polynomial (x) instead of (x).
Pr o o f. The plane curve q(f(x), g(y)) = 0 has 2 gcd(m, n) points at
innity, which implies that gcd(m, n) = 1.
Further, since q(f(x), g(y)) is exceptional, so is
q(f(x), y) = (y yf(x))
2
(
2
)(f(x)
2
4b),
as well as y
2
(
2
)(f(x)
2
4b). By Proposition 6.5, the polynomial
f(x)
2
4b has at most two roots of odd order. We complete the proof using
Corollary 5.4.
To formulate the main result of this section, we need to dene one more
kind of pairs, which we call specic (
5
). A specic pair over K is
(D
m
(x, a
m/d
), D
n
(xcos(/d), a
n/d
))
(or switched), where d = gcd(m, n) 3 and a, cos(2/d) K. Notice that
D
n
(xcos(/d), a
n/d
) K[x] by (9).
Theorem 9.3. Let f(x), g(x) K[x] be such that f(x) g(y) has an ex-
ceptional factor E(x, y). Then there exist a standard or specic pair (f
1
, g
1
)
over K, linear polynomials (x), (x) K[x], and a polynomial (x) K[x]
such that f = f
1
and g = g
1
. Also, E(x, y) is equal to
f
1
(x) g
1
(y) times a constant if (f
1
, g
1
) is standard, and E(x, y)
divides f
1
(x) g
1
(y) if (f
1
, g
1
) is specic.
(
5
) This term has no intuitive meaning: specic pairs are neither less standard nor
more specic than standard pairs.
Diophantine equation f(x) = g(y) 283
Pr o o f. All polynomials that occur in the proof have coecients in K
unless the contrary is stated explicitly.
Let f = f
3
f
2
and g = g
3
g
2
be the decompositions from Theorem 8.1
(we write f
3
and g
3
instead of f
1
and g
1
). In particular,
(45) deg f
3
= deg g
3
.
Then E(x, y) = q(f
2
(x), g
2
(y)), where q(x, y) is an absolutely irreducible
factor of f
3
(x) g
3
(y).
It follows from (45) that the curve q(x, y) = 0 has exactly deg q points
at innity. Since q is exceptional (by Proposition 9.1), we have deg q 2.
Theorem 8.2 implies that f
3
=
1
f
4
and g
3
=
1
g
4
, where either
(46) q(x, y) = f
4
(x) g
4
(y),
or for some integer > 2 we have
(47)
f
4
(x) = D

(x + , a), g
4
(x) = D

((x + ) cos(/), a),

> 2, cos(2/) K, q(x, y) [ (f
4
(x) g
4
(y)),
where a, K

and , K. Put f
5
= f
4
f
2
and g
5
= g
4
g
2
.
In the case (46) we have E(x, y) = f
5
(x) g
5
(y). Since E(x, y) has d =
gcd(deg f
5
, deg g
5
) points at innity, we have d 2. Applying Theorem 6.1,
we conclude that f
5
= f
1
and g
5
= g
1
, where (x), (x), (x)
are linear polynomials and (f
1
, g
1
) is a standard pair over K.
Obviously, E(x, y) is equal to f
1
((x)) g
1
((y)) times a constant.
Putting =
1
, we complete the proof in the case (46).
Now assume (47). By (11), for some positive integer k we have q(x, y) =
q
k
(x + , y + ), where
q
k
(x, y) = x
2
2xy cos(k/) cos(/) + y
2
cos
2
(/) 4a sin
2
(k/).
Put f
6
= f
2
+ and g
6
= g
2
+ . Then E(x, y) = q
k
(f
6
(x), g
6
(y)) is an
exceptional polynomial, which, by Proposition 9.2, implies that
(48) gcd(m

, n

) = 1,
where m

= deg f
6
and n

= deg g
6
. Without loss of generality, n

is odd.
Furthermore, Proposition 9.2 implies that
g
6
(x) = (cos(/))
1

aD
n
(
1
(x) cos(/)

a, 1),
and that either m

is odd and
f
6
(x) =

aD
m
(
1
(x)

a, 1),
or m

is even, a is a perfect square in K, and for some a

and a suitable
choice of the sign of

a we have
f
6
(x) =

aD
m
(
1
(x)

, 1).
Here
1
(x) and
1
(x) are linear polynomials.
284 Yu. F. Bi l u and R. F. Ti chy
Putting m = m

and n = n

, we obtain
g
5
(x) = D

(g
6
(x) cos(/), a)
= (

a)

((

a)
1
g
6
(x) cos(/), 1)
= (

a)

(D
n
(
1
(x)

a cos(/), 1), 1)
= (

a)

D
n
(
1
(x)

a cos(/), 1)
=

a
(+mn/)/2
D
n
((x) cos(/), a
m/
) if m

is odd,
(

a)

(a

)
mn/(2)
D
n
((x) cos(/), (a

)
m/
) if m

is even.
(Recall that

a K when m

is even.) Here
(x) =

1
(x)a
(1+m/)/2
if m

is odd,

1
(x)(a

)
m/(2)

a if m

is even.
A similar calculation shows that
f
5
(x) =

a
(+mn/)/2
D
m
((x), a
n/
) if m

is odd,
(

a)

(a

)
mn/(2)
D
n
((x), (a

)
n/
) if m

is even,
where
(x) =

1
(x)a
(1+n/)/2
if m

is odd,

1
(x)(a

)
(1+n/)/2
if m

is even.
Further, = d = gcd(m, n) by (48), which implies that d > 2 and cos(2/d)
K by (47). Thus, f
5
= Af
1
and g
5
= Ag
1
, where
A =

a
(+mn/)/2
if m

is odd,
(

a)

(a

)
mn/(2)
if m

is even,
and (f
1
, g
1
) is a specic pair over K.
Finally, since q(x, y) [ (f
4
(x) g
4
(y)), the polynomial E(x, y) =
q(f
2
(x), g
2
(y)) divides f
5
(x) g
5
(y) = A(f
1
((x)) g
1
((y))). Putting
(x) =
1
(x/A), we complete the proof in the case (47) as well.
10. The Diophantine equation. Let R be a commutative integral do-
main with quotient eld K, and F(x, y) K[x, y]. We say that the equation
F(x, y) = 0 has innitely many solutions with a bounded R-denominator if
there exists a non-zero R such that F(x, y) = 0 has innitely many
solutions (x, y) K K with x, y R.
In this section K is a number eld, and S a nite set of places of K
containing all Archimedean places. We denote by O
S
the ring of S-integers
of the eld K.
Recall the classical theorem of Siegel [30] (see also [23, 28]).
Theorem 10.1 (Siegel). Let F(x, y) K[x, y] be an absolutely irreducible
polynomial. If the equation F(x, y) = 0 has innitely many solutions with
a bounded O
S
-denominator, then the polynomial F(x, y) is exceptional , as
dened at the beginning of Section 9.
Diophantine equation f(x) = g(y) 285
We need several simple auxiliary results.
Proposition 10.2. Let F(x, y) K[x, y] be irreducible over K but re-
ducible over K. Then the equation F(x, y) = 0 has at most nitely many
solutions (x, y) K K.
Pr o o f. This is well known (and very simple); see, for instance, [31,
beginning of Section 9.6].
Proposition 10.3. Let K be a totally real number eld, O its ring of
integers, and let F(x, y) K(x, y) have the following property: for any
embedding : K R, the polynomial F is semi-denite (see Subsec-
tion 3.2). Then the equation F(x, y) = 0 has only nitely many solutions
with a bounded O-denominator.
Pr o o f. By Proposition 3.2(iii), there is a constant c = c(F) such that
max([(x)[, [(y)[) c(F) for any (x, y) K
2
satisfying F(x, y) = 0 and
for any embedding : K R.
Fix O. Let (x, y) K
2
be a solution of F(x, y) = 0 with x, y
O. Then x, y are algebraic integers with all conjugates bounded. Hence
there are only nitely many possibilities for x and y. This completes the
proof.
Corollary 10.4. Let K be a totally real number eld, O its ring of
integers and a K

. Then we have the following.

(i) If d = gcd(m, n) is even then the equation
D
m
(x, a
n/d
) + D
n
(y cos(/d), a
m/d
) = 0
has only nitely many solutions with a bounded O-denominator.
(ii) If d = gcd(m, n) is odd and the equation
D
m
(x, a
n/d
) + D
n
(y, a
m/d
) = 0
has innitely many solutions with a bounded O-denominator, then all of
them with nitely many exceptions satisfy
D
m/d
(x, a
n/d
) + D
n/d
(y, a
m/d
) = 0.
Pr o o f. This follows from Propositions 3.3 and 10.3.
Now we are ready to prove the main result of this paper.
Theorem 10.5. Let K be number eld, S a nite set of places of K con-
taining all Archimedean places, and f(x), g(x) K[x]. Then the following
two assertions are equivalent.
(10.5.a) The equation f(x) = g(y) has innitely many solutions with a
bounded O
S
-denominator.
286 Yu. F. Bi l u and R. F. Ti chy
(10.5.b) We have f = f
1
and g = g
1
, where (x), (x) K[x]
are linear polynomials, (x) K[x], and (f
1
(x), g
1
(x)) is a stan-
dard or specic pair over K such that the equation f
1
(x) = g
1
(y)
has innitely many solutions with a bounded O
S
-denominator.
If K is totally real and S is the set of Archimedean places (in particular, if
K = Q and O
S
= Z) then the word specic in (10.5.b) may be skipped.
Pr o o f. Only (10.5.a)(10.5.b) is to be proved (the converse is obvious).
Thus, assume (10.5.a). Then there exists a K-irreducible factor E(x, y)
of f(x) g(y) such that the equation E(x, y) = 0 has innitely many solu-
tions with a bounded O
S
-denominator. By Proposition 10.2, the polynomial
E(x, y) is absolutely irreducible. By Siegels theorem, E(x, y) is exceptional.
Now Theorem 9.3 implies that f = f
1
and g = g
1
, where ,
f
1
, g
1
, and are as required.
Further, since E(x, y) divides f
1
(x)g
1
(y), the equation f
1
(x) =
g
1
(y) has innitely many solutions with a bounded O
S
-denominator.
Hence so does the equation f
1
(x) = g
1
(y).
Now assume that K is totally real, S the set of its Archimedean places,
and (f
1
, g
1
) a specic pair. That is,
f
1
(x) = D
m
(x, a
n/d
) and g
1
(x) = D
n
(xcos(/d), a
m/d
),
where d = gcd(m, n) 3 and a, cos(2/d) K.
Since f
1
(x) = g
1
(y) has innitely many solutions with a bounded O
S
-
denominator, Corollary 10.4(i) implies that d is odd. Therefore cos(/d)
K. Now, f =

f
1

and g = g
1
with
(x) = (D
d
(x, a
mn/d
2
)),

f
1
(x) = D
m/d
(x, a
n/d
), g
1
(x) = D
n/d
(x, a
m/d
),

(x) = (x), (x) = (x) cos(/d),

where = (1)
m
. Notice that (

f
1
, g
1
) is a standard pair (of the third kind).
It remains to show that

f
1
(x) = g
1
(y) has innitely many solutions with
a bounded O
S
-denominator. Since cos(/d) K, the equation
f
1
(x) g
1
(y/ cos(/d)) = D
m
(x, a
n/d
) + D
n
(x, a
m/d
) = 0
has innitely many solutions with a bounded O
S
-denominator. By Corol-
lary 10.4(ii), so does the equation D
m/d
(x, a
n/d
) = D
n/d
(x, a
m/d
). Since
either m/d or n/d is odd, the equation

f
1
(x) = g
1
(y) has the same property.
The theorem is proved.
Theorem 1.1 is a particular case of Theorem 10.5.
Diophantine equation f(x) = g(y) 287
References
[1] R. M. Avanzi and U. Zanni er, Genus one curves dened by separated variable
polynomials, Acta Arith., to appear.
[2] A. Baker, Bounds for solutions of superelliptic equations, Proc. Cambridge Philos.
Soc. 65 (1969), 439444.
[3] F. Beuker s, T. N. Shor ey and R. Ti j deman, Irreducibility of polynomials and
arithmetic progressions with equal product of terms, in: [21], pp. 1126.
[4] Yu. Bi l u, Integral points and Galois covers, Mat. Contemp. 14 (1998), 111.
[5] , Quadratic factors of f(x) g(y), Acta Arith. 90 (1999), 341355.
[6] Yu. F. Bi l u, B. Br i ndza,

A. Pi nter and R. F. Ti chy, On some diophantine
problems related to power sums and binomial coecients, in preparation.
[7] Yu. Bi l u and G. Hanr ot, Solving superelliptic Diophantine equations by Bakers
method, Compositio Math. 112 (1998), 273312.
[8] Yu. F. Bi l u, T. St ol l and R. F. Ti chy, Diophantine equations for the Meixner
polynomials, in preparation.
[9] B. Br i ndza and

A. Pi nter, On the irreducibility of some polynomials in two
variables, Acta Arith. 82 (1997), 303307.
[10] Y. Bugeaud, Bounds for the solutions of superelliptic equations, Compositio Math.
107 (1997), 187219.
[11] P. Cas s ou- Nogu`es et J.-M. Couvei gnes, Factorisations explicites de g(y)h(z),
Acta Arith. 87 (1999), 291317.
[12] H. Davenpor t, D. J. Lewi s and A. Schi nzel, Equations of the form f(x) = g(y),
Quart. J. Math. Oxford Ser. (2) 12 (1961), 304312.
[13] J.-H. Ever t s e and J. H. Si l ver man, Uniform bounds for the number of solutions
to Y
n
= f(X), Math. Proc. Cambridge Philos. Soc. 100 (1986), 237248.
[14] W. Fei t, On symmetric balanced incomplete block designs with doubly transitive
automorphism groups, J. Combin. Theory Ser. A 14 (1973), 221247.
[15] , Some consequences of the classication of nite simple groups, in: Proc. Sym-
pos. Pure Math. 37, Amer. Math. Soc., 1980, 175181.
[16] M. Fr i ed, The eld of denition of function elds and a problem in the reducibility
of polynomials in two variables, Illinois J. Math. 17 (1973), 128146.
[17] , Arithmetical properties of function elds (II). The generalized Schur problem,
Acta Arith. 25 (1973/74), 225258.
[18] , On a theorem of Ritt and related Diophantine problems, J. Reine Angew. Math.
264 (1974), 4055.
[19] , Exposition on an arithmetic-group theoretic connection via Riemanns existence
theorem, in: Proc. Sympos. Pure Math. 37, Amer. Math. Soc., 1980, 571601.
[20] , Variables separated polynomials, the genus 0 problem, and moduli spaces, in:
[21], pp. 169228.
[21] K. Gyor y, H. I wani ec and J. Ur banowi cz (eds.), Number Theory in Progress
(Proc. Internat. Conf. in Number Theory in Honor of A. Schinzel, Zakopane,
1997), de Gruyter, 1999.
[22] P. Ki r s chenhof er, A. Pet ho and R. F. Ti chy, On analytical and Diophantine
properties of a family of counting polynomials, Acta Sci. Math. (Szeged) 65 (1999),
4759.
[23] S. Lang, Fundamentals of Diophantine Geometry, Springer, 1983.
[24] W. J. LeVeque, On the equation y
m
= f(x), Acta Arith. 9 (1964), 209219.
[25] R. Li dl, G. L. Mul l en and G. Tur nwal d, Dickson Polynomials, Pitman Mono-
graphs Surveys Pure Appl. Math. 65, Longman Sci. Tech., 1993.
288 Yu. F. Bi l u and R. F. Ti chy
[26] J. F. Ri t t, Prime and composite polynomials, Trans. Amer. Math. Soc. 23 (1922),
5166.
[27] A. Schi nzel, Selected Topics on Polynomials, The Univ. of Michigan Press, Ann
Arbor, 1982.
[28] J.-P. Ser r e, Lectures on the MordellWeil Theorem, Aspects Math. E15, Vieweg,
Braunschweig, 1989.
[29] C. L. Si egel, The integer solutions of the equation y
2
= ax
n
+ bx
n1
+ . . . + k,
J. London Math. Soc. 1 (1926), 6668; also: Gesammelte Abhandlungen, Band 1,
207208.
[30] ,

Uber einige Anwendungen Diophantischer Approximationen, Abh. Preuss. Akad.
Wiss. Phys.-Math. Kl., 1929, Nr. 1; also: Gesammelte Abhandlungen, Band 1,
209266.
[31] V. G. Spr i ndzuk, Classical Diophantine Equations in Two Unknowns, Nauka,
Moscow, 1982 (in Russian); English transl.: Lecture Notes in Math. 1559, Springer,
1994.
[32] G. Tur nwal d, On Schurs conjecture, J. Austral. Math. Soc. 58 (1995), 312357.
[33] H. A. Tver ber g, A study in irreducibility of polynomials, Ph.D. thesis, Dept. of
Math., Univ. of Bergen, 1968.
[34] P. M. Vout i er, On the number of S-integral solutions to Y
m
= f(X), Monatsh.
Math. 119 (1995), 125139.
Mathematisches Institut
Universitat Basel
Rheinsprung 21
4051 Basel, Switzerland
E-mail: [email protected]
Institut f ur Mathematik (A)
Technische Universitat Graz
Steyrergasse 30
8010 Graz, Austria
E-mail: [email protected]
Received on 17.12.1999 (3730)