Solving Diophantine Equations

Guillaume Hanrot

Projet Polka, Inria Lorraine

Algorithms Seminar

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).

1 Introduction

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 the existence of a universal algorithm that would compute all integer solutions of a polynomial equation, and it was not until 1970 that Matiyasevich [13] 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 [19] showed that

d(a) ³

C₁

n/2+e

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 [17] improved the bound to:

d(a) ³

C₂(e)

2(n)^1/2+1+e

which was enough to prove the finiteness of the number of solutions of y^p = f(x) for f a separable polynomial of degree ³ 3 and p ³ 2 [18]. Later, in 1955, Roth proved [16]:

d(a) ³

C₃(e)

2+e

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

d(a) £

2 q²

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 [1] (see also [3]) found a very deep bound:

Theorem 1 Let a₁,a₂,...,a_n denote algebraic numbers. Then for every n-tuple of integers (b₁, b₂, ..., b_n), we have

K=0 or K³ exp(-C₄ log

max

|b_i|), where K=|b₁ loga₁+b₂ loga₂+ ... +b_n loga_n|.

Unfortunately, the constant C₄, though effective, is very huge and specialists thought it was completely useless. However, Baker and Davenport [2] gave the first use of such a bound, for solving a system of simultaneous Pell equations.

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 a_i 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 rewrite as:

i=1

(Y - a_i X) = 1. (1)

Suppose (X₀, Y₀) is an integer solution of this equation. In view of (1), it is obvious that at least one of the terms Y₀ - a_i X₀ is small. This implies that:

Y₀ - a_j X₀ » (a_j - a_i) X₀

when j ¹ i. Using (1) again, we get that:

½
½
½
½

a_i -

Y₀

X₀

½
½
½
½

|X₀|ⁿ

j ¹ i

|a_j - a_i|

or in other words, Y₀/X₀ is a very good approximation of a_i.

2.2 Using the Baker Bound

In algebraic terms, equation (1) tells us that for each i, the number Y₀ - a_i X₀ is a unit in Q(a_i).

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 h₁,h₂,...,h_r such that every unit can be written as: z^b_⁰ Õ_i=1^r h_i^b_ⁱ where z denotes a root of unity in Q(a) and the b_i's are integers. Without loss of generality, it can be shown that we can restrict to the case where z = -1.

Now suppose that a₁ is a real root of P(1, Z). If j¹ k ¹ 1, we can write:

½
½
½
½

Y₀ - a_j X₀

Y₀-a_k X₀

a_k-a₁

a_j-a₁

- 1

½
½
½
½

C₅(P)

|X₀|ⁿ

From this, we deduce that:

½
½
½
½

log

Y₀ - a_j X₀

Y₀-a_k X₀

a_k-a₁

a_j-a₁

½
½
½
½

C₆(P)

|X₀|ⁿ

Write Y₀ - a_k X₀ = h_{k, 1}^b_¹ ··· h_{k, r}^b_^r. We can rewrite the last inequality as:

½
½
½
½
½

-log

a_k-a₁

a_j-a₁

l=1

log

k, l

j, l

+ 2 i k p

½
½
½
½
½

C₇

|X₀|ⁿ

. (2)

It is not hard to see that log |X₀| » B = max_l|b_l|, so that the right-hand side of the inequality is bounded by

C₇ exp(-n C₈ B).

For the left hand side, we use the Baker bound to finally obtain the lower bound

exp(-C₉ log B) £ C₇ exp(-n C₈ 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

X¹⁹+2 Y¹⁹ = ± 1, or ± 2, (3)

one finds B = 2.32× 10⁹².

2.3 Refining the Bound

Once we know that the b_i's are bounded, we would like to find a better bound. The idea is the following. Suppose the b_i's are integers subject to |b_i| £ B. We would like to prove some result on the minimum of the quantity |å_l=1^r b_ll_l| where the l_l's are real numbers. Using the Lenstra-Lenstra-Lovász theory [12] as in [8], it is possible to show that this minimum is bounded from below by C₁₀/ B^r-1. Since we also have the Baker bound:

exp(-C₁₁ B) ³

½
½
½
½

l=1

½
½
½
½

we get

B £ log ( B^r-1/C₁₀) = (r-1) log B - log C₁₀

or a bound which is logarithmically smaller.

For instance, for our example, we find that B = 29 instead of 2.32× 10⁹².

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 b_i's, with |b_i| £ 29, which amounts to 59⁹ combinations.

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:

_{0, j} +

l=1

l, j

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/|X₀|ⁿ, there are two cases. Either q < 1/2 and we can easily deduce b from a, or q > 1/2 and since C/|X₀|ⁿ > 1/2, |X₀| 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.

4 Conclusions

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

2505

k=1

(Y - cos(2kp/5011) X) = ± 1

using an intermediate field of degree 3. The original Baker bound, 10⁴⁰, was reduced to 46, yielding a total running time of 8 minutes. More examples are given in [6] and in [10, 11], refinements are given when one does not have the full unit group of the number field under consideration.

The ideas we have described above can be used mutatis mutandis to solve equations of the type Y^p = f(X). The only difference comes from the construction of the units. We refer to the speaker's thesis for this.

As a final comment, we note that similar techniques can be used to solve equations on elliptic curves [9, 20].

References

[1]: 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.
[2]: Baker (A.) and Davenport (H.). -- The equations 3x² - 2 = y² and 8x² - 7 = z². Quarterly Journal of Mathematics, Oxford Series, vol. 20, 1969, pp. 129--137.
[3]: 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.
[4]: Bilu (Yu.) and Hanrot (G.). -- Solving Thue equations of high degree. Journal of Number Theory, vol. 60, 1996, pp. 373--392.
[5]: Bilu (Yu.) and Hanrot (G.). -- Solving superelliptic diophantine equations by Baker's method. -- 1998. To appear in Compositio Mathematica.
[6]: Bilu (Yu.) and Hanrot (G.). -- Thue equations with composite fields. -- 1998. To appear in Acta Arithmetica.
[7]: Cohen (Henri). -- A course in computational algebraic number theory. -- Springer-Verlag, Berlin, 1993, Graduate Texts in Mathematics, vol. 138, xii+534p.
[8]: de Weger (B. M. M.). -- Solving exponential diophantine equations using lattice basis reduction algorithms. Journal of Number Theory, vol. 26, 1987, pp. 325--367.
[9]: 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.
[10]: Hanrot (G.). -- Résolution effective d'équations diophantiennes : algorithmes et applications. -- PhD thesis, Université de Bordeaux I, 1997.
[11]: Hanrot (G.). -- Solving Thue equations without the full unit group. -- 1998. To appear in Mathematics of Computation.
[12]: Lenstra (A. K.), Lenstra (H. W. Jr.), and Lovász (L.). -- Factoring polynomials with rational coefficients. Mathematische Annalen, vol. 261, 1982, pp. 515--534.
[13]: Matiyasevich (Yu.). -- Enumerable sets are diophantine. Soviet Mathematics. Doklady, vol. 12, 1971, pp. 249--254.
[14]: Pohst (M.). -- Computational Algebraic Number Theory. -- Birkhäuser, 1993, DMV Seminar, vol. 21.
[15]: Pohst (M.) and Zassenhaus (H.). -- Algorithmic Algebraic Number Theory. -- Cambridge University Press, 1989.
[16]: Roth (K. F.). -- Rational approximations to algebraic numbers. Mathematika, vol. 2, 1955, pp. 1--20.
[17]: Siegel (C. L.). -- Approximation algebraischer Zahlen. Mathematische Zeitschrift, vol. 10, 1921, pp. 173--213.
[18]: Siegel (C. L.). -- The integer solutions of the equation y²=axⁿ + bx^n-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.
[19]: Thue (A.). -- Über Annäherungswerte algebraischer Zahlen. Journal für die reine und angewandte Mathematik, vol. 135, 1909, pp. 284--305.
[20]: 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 L^AT_EX by H^EV^EA.