Calculating “Small” Solutions of Relative Thue Equations

Abstract

Diophantine equations can often be reduced to various types of classical Thue equations. These equations usually have only very small solutions. On the other hand, to compute all solutions (i.e., to prove the nonexistence of large solutions) is a time-consuming procedure. Therefore, it is useful to have a fast algorithm to calculate the “small” solutions, especially if “small” means less than, e.g., 10¹⁰⁰. Such an algorithm was constructed by A. Pethö in 1987 based on continued fractions.

In the present paper, we construct a similar type of fast algorithm to calculate “small” solutions of relative Thue equations. Our method is based on the LLL reduction algorithm. We illustrate the method with explicit examples. The algorithm has several applications.

Keywords:

• relative Thue equations
• algorithms for the resolution
• LLL reduction
• supercomputers

2000 AMS Subject Classification::

• Primary 11D59, 11Y50
• Secondary 11R2