Solving Diophantine Equations
Projet Polka, Inria Lorraine
December 1st, 1997
[summary by F. Morain]
A properly typeset version of this document is available in postscript
and in pdf
If some fonts do not look right on your screen, this might be
fixed by configuring your browser (see the documentation here).
Solving Diophantine equations, that is finding integer solutions to
polynomial equations, is one of the oldest mathematical problems. The
very name ``Diophantine'' reminds us of the great Greek mathematician
Diophante who solved some of the most basic equations.
At the beginning of the twentieth century, Hilbert asked about
of a universal algorithm that would compute all integer solutions of a
polynomial equation, and it was not until 1970 that Matiyasevich
 showed the inexistence of such an algorithm.
Even before the negative answer to this problem, many mathematicians
have developed algorithms for special cases. For the univariate case,
the problem is related to good rational approximations of a non
rational root a of a polynomial P with integer
coefficients. Let n be the degree of P and
p/q a rational number. Put d(a) =
|a-p/q|. Thue  showed that
with the consequence that there are only a finite number of solutions
of the equation Q(X, Y)=1, where Q is an homogeneous, irreducible
polynomial of degree ³ 3. Siegel  improved the bound to:
which was enough to prove the finiteness of the number of solutions of
yp = f(x) for f a separable polynomial of degree ³ 3 and p ³
2 . Later, in 1955, Roth proved :
a result that is the best possible, due to well known results in
continued fraction theory, namely that if a is irrational, then
there exists an infinite number of rational numbers p/q such that
As is often the case, the constants are ineffective and this does not
help us when we want to find the solutions of a given equation. Around
1966, Baker  (see also ) found a very deep bound:
Let a1,a2,...,an denote algebraic
numbers. Then for every n-tuple of integers (b1, b2, ...,
bn), we have
Unfortunately, the constant C4, though effective, is very huge and
specialists thought it was completely useless. However, Baker and
Davenport  gave the first use of such a bound, for
solving a system of simultaneous Pell equations.
|K=0 or K³ exp(-C4 log
|bi|), where K=|b1 loga1+b2 loga2+
... +bn logan|.
2 Solving Homogeneous Equations
2.1 Statement of the Problem
Let P(X, Y) be a homogeneous polynomial of degree n, monic in Y, and let
ai denote the roots of P(1, Z). In this section, we want to
solve the equation P(X, Y)=1 in integers X and Y, which we
Suppose (X0, Y0) is an integer solution of this equation.
In view of (1), it is obvious that at least one of
the terms Y0 - ai X0 is small. This implies that:
Y0 - aj X0 » (aj - ai) X0
when j ¹ i. Using (1) again, we get that:
or in other words, Y0/X0 is a very good approximation of ai.
2.2 Using the Baker Bound
In algebraic terms, equation (1) tells us that for each
i, the number Y0 - ai X0 is a unit in Q(ai).
One knows that the set of units of a number field Q(a) is a
group of finite type. There exists a set
of units, the so-called fundamental units h1,h2,...,hr such that every unit can be written as:
zb0 Õi=1r hibi
where z denotes a root of unity in Q(a) and the bi's
are integers. Without loss of generality, it can be shown that we can
restrict to the case where z = -1.
Now suppose that a1 is a real root of P(1, Z). If j¹ k
¹ 1, we can write:
From this, we deduce that:
Write Y0 - ak X0 = hk, 1b1 ···
hk, rbr. We can rewrite the last inequality as:
It is not hard to see that log |X0| » B = maxl|bl|, so that the right-hand side of the inequality is bounded by
|| + 2 i k p
C7 exp(-n C8 B).
For the left hand side, we use the Baker bound to finally obtain the
exp(-C9 log B) £ C7 exp(-n C8 B).
This clearly gives a bound B on B.
Unfortunately, this bound is much too large to be useful. For
instance, in the case of the equations
one finds B = 2.32× 1092.
= ± 1, or ± 2,
2.3 Refining the Bound
Once we know that the bi's are bounded, we would like to find a
better bound. The idea is the following. Suppose the bi's are
integers subject to |bi| £ B. We would like to prove
some result on the minimum of the quantity
where the ll's are real numbers. Using the
Lenstra-Lenstra-Lovász theory  as in ,
it is possible to show that this minimum is bounded from below by
Since we also have the Baker bound:
|exp(-C11 B) ³
B £ log ( Br-1/C10) = (r-1) log
B - log C10
or a bound which is logarithmically smaller.
For instance, for our example, we find that B = 29 instead of
2.4 Finishing the Computations
At this point, one can finish the computations by enumerating all
solutions. As easy as it seems, do not forget that there could be a
lot of computations still to be done. In our example, there are 9
values for the bi's, with |bi| £ 29, which amounts to 599
This is enough when n is small, but can be quite
cumbersome when n increases, since the computational determination
of units in a general number field is no easy task at all (see for
example [7, 14, 15]).
3 A Faster Approach
The idea of Bilu and the speaker [4, 5] is the
following: we can rewrite equation (2) as:
that is we have r linear forms in r+1 logarithms. The idea is to
transform these forms so as to obtain a new form of the type
q = |aa + bb +d|
where the integers a and b are bounded. Minimizing such a form can be done
using continued fractions, and therefore is very fast. Once this is
done, and using a bound as C/|X0|n, there are two cases. Either
q < 1/2 and we can easily deduce b from a, or q >
1/2 and since C/|X0|n > 1/2, |X0| is quite small and we are done.
In brief, we have reduced a large enumeration problem in a large
number of unknowns to one in a single unknown.
For our leading example, we get that B = 4 and it takes
12 seconds on a workstation to find all the solutions.
We have shown how to solve some special cases of Diophantine equations
by a clever use of Baker's bound combined with casual ingenuity. It is
possible to use more tricks, for example using units that are not
fundamental, or to work with relative norms. For instance, the speaker
has the world record in the field, with the solution of the equation
using an intermediate field of degree 3. The original Baker bound,
1040, was reduced to 46, yielding a total running time of 8
minutes. More examples are given in  and in
[10, 11], refinements are given when one does not
have the full unit group of the number field under consideration.
|| (Y - cos(2kp/5011) X) = ± 1
The ideas we have described above can be used mutatis mutandis
to solve equations of the type Yp = f(X). The only difference comes
from the construction of the units. We refer to the speaker's thesis
As a final comment, we note that similar techniques can be used to
solve equations on elliptic curves [9, 20].
Baker (A.). --
Linear forms in the logarithms of algebraic numbers I, II, III,
IV. Mathematika, vol. 13, 14, 14, 15, 1966, 1967, 1967,
1968, pp. 204--216, 102--107, 220--228, 204--216.
Baker (A.) and Davenport (H.). --
The equations 3x2 - 2 = y2 and 8x2 - 7 = z2. Quarterly
Journal of Mathematics, Oxford Series, vol. 20, 1969,
Baker (A.) and Wüstholz (G.). --
Logarithmic forms and group varieties. Journal für die reine
und angewandte Mathematik, vol. 442, 1993, pp. 19--62.
Bilu (Yu.) and Hanrot (G.). --
Solving Thue equations of high degree. Journal of Number
Theory, vol. 60, 1996, pp. 373--392.
Bilu (Yu.) and Hanrot (G.). --
Solving superelliptic diophantine equations by Baker's method. --
1998. To appear in Compositio Mathematica.
Bilu (Yu.) and Hanrot (G.). --
Thue equations with composite fields. --
1998. To appear in Acta Arithmetica.
Cohen (Henri). --
A course in computational algebraic number theory. --
Springer-Verlag, Berlin, 1993, Graduate Texts in
Mathematics, vol. 138, xii+534p.
de Weger (B. M. M.). --
Solving exponential diophantine equations using lattice basis
reduction algorithms. Journal of Number Theory, vol. 26,
1987, pp. 325--367.
Gebel (J.), Pethö (A.), and Zimmer (H.). --
Computing S-integral points on elliptic curves. In Cohen (H.)
(editor), Algorithmic Number Theory. --
Springer-Verlag, 1996. Proceedings of the Second
International Symposium ANTS II.
Hanrot (G.). --
Résolution effective d'équations diophantiennes :
algorithmes et applications. --
PhD thesis, Université de Bordeaux I, 1997.
Hanrot (G.). --
Solving Thue equations without the full unit group. --
1998. To appear in Mathematics of Computation.
Lenstra (A. K.), Lenstra (H. W. Jr.), and Lovász (L.). --
Factoring polynomials with rational coefficients. Mathematische
Annalen, vol. 261, 1982, pp. 515--534.
Matiyasevich (Yu.). --
Enumerable sets are diophantine. Soviet Mathematics. Doklady,
vol. 12, 1971, pp. 249--254.
Pohst (M.). --
Computational Algebraic Number Theory. --
Birkhäuser, 1993, DMV Seminar, vol. 21.
Pohst (M.) and Zassenhaus (H.). --
Algorithmic Algebraic Number Theory. --
Cambridge University Press, 1989.
Roth (K. F.). --
Rational approximations to algebraic numbers. Mathematika,
vol. 2, 1955, pp. 1--20.
Siegel (C. L.). --
Approximation algebraischer Zahlen. Mathematische
Zeitschrift, vol. 10, 1921, pp. 173--213.
Siegel (C. L.). --
The integer solutions of the equation y2=axn + bxn-1 + ... +
k (extract from a letter to Prof. L. J. Mordell unter dem
Pseudonym X). Journal of the London Mathematical Society, vol. 1,
1926, pp. 66--68.
Thue (A.). --
Über Annäherungswerte algebraischer Zahlen. Journal
für die reine und angewandte Mathematik, vol. 135, 1909,
Tzanakis (N.). --
Solving elliptic diophantine equations by estimating linear forms in
elliptic logarithms. the case of quartic equations. Acta Arithmetica,
vol. 75, 1996, pp. 165--190.
This document was translated from LATEX by