Solving superelliptic Diophantine equations by Baker’s method

Yuri F. Bilu^{∗}

Max-Planck-Institut für Mathematik Gottfried-Claren-Strasse 26 53225 Bonn GERMANY

Guillaume Hanrot

Algorithmique Arithmétique Expérimentale (A2X) UMR CNRS 9936 Université Bordeaux 1 351, cours de la Libération F-33405 Talence Cedex, FRANCE

e-mail: hanrot@math.u-bordeaux.fr

April 20, 1997

Abbreviated title: Superelliptic equations

Abstract. We describe a method for complete solution of the superelliptic Diophantine equation ay^{p} = f(x). The method is based on Baker’s theory of linear forms in the logarithms. The characteristic feature of our approach (as compared with the classical method) is that we reduce the equation directly to the linear forms in logarithms, without intermediate use of Thue and linear unit equations.

We show that the reduction method of Baker and Davenport [3] is applicable for superelliptic equations, and develop a very efficient method for enumerating the solutions below the reduced bound.

The method requires computing the algebraic data in number fields of degree pn(n − 1)/2 at most; in many cases this number can be reduced.

Two examples with p = 3 and n = 4 are given.

Key words: Diophantine equations, linear forms in logarithms

AMS Subject Classification: Primary : 11Y50. Secondary : 11D25, 11D41.

1. Introduction

In this paper we propose a method for complete solution of the superelliptic Diophantine equation

ay^{p} = f(x),  (1)

where a is a non-zero integer, p ≥ 3 and f(x) ∈ ℤ[x] a separable polynomial of degree n ≥ 2. Recall that the first effective bound for the integral solutions of this equation was obtained by A. Baker [2] as

∗ Current address: Forschungsinstitut für Mathematik, ETH-Zentrum, CH-8092

Zurich, SWITZERLAND, e-mail: yuri@math.ethz.ch

an application of his theory of linear forms in logarithms [1]. For further advance and bibliography see [24, 26, 25, 9, 22, 21, 29]. In these papers the equation (1) is reduced to finitely many Thue equations over certain number fields, each of the latter being then reduced to finitely many linear unit equations, which can be analyzed using Baker’s theory. (Voutier [29] reduces (1) directly to linear unit equations, without intermediate use of Thue equations.) However, this method (call it “Thue descent”) does not seem to be suitable for practical solution of the superelliptic equation, because the number of Thue (or linear unit) equations to be solved turns out to be very large, even when the equation has very moderate coefficients.

In the present paper we develop a different method, reducing the superelliptic equation directly to the linear forms in logarithms, without intermediate use of Thue and linear unit equations (as it is done in [6]). For simplicity, we deal with case when p is an odd prime. Since the case of an arbitrary p ≠ 2^{k} can be reduced to the case of an odd prime p, we almost preserve the generality. With a few changes, our method extends to the hyperelliptic equation ay^{2} = f(x), where f(x) is a separable polynomial of degree at least 3 (see Appendix E).

In accordance with the general ideology of [5], our method can be described as follows.

(i) Construct functional units in an unramified extension of the field ℚ (x, (a^{−1}f(x))^{1/p});

(ii) Using the fact that the specialization of a functional unit at an integral point is “almost a unit” of a certain number field, reduce the equation to finitely many inequalities of the type

0 < |α_{0}α_{1}^{b_{1}} ⋯ α_{n}^{b_{n}} − 1| < exp(−cB),  (2)

where B = max(|b_{1}|, …, |b_{n}|) and c is an effectively computable constant.

(iii) Obtain from (2) an upper bound for B by means of the theory of linear forms in logarithms.

Successful choice of functional units allowed us to reduce the degrees of number fields, occurring in the process of solution, from pn(n−1), as required for the Thue descent, to \frac{1}{2}pn(n − 1), which is very important from the computational point of view. (See Subsection 5.5.)

The theoretical bound for B, obtained from the theory of linear forms in logarithms, is very large. As explained in [17, 27], in practical cases the bound for B can be significantly reduced with the help of the Lenstra–Lenstra–Lovász (further LLL) algorithm [13]. In [8] we showed that in the case of the Diophantine equations of Thue, one can replace the LLL by the simple continued fraction algorithm, as Baker and Davenport [3] did already in 1969. It turns out that the same idea works for the superelliptic equation, see Subsection 4.6.

Another difficult point in the numerical solution of Diophantine equations is enumerating all solutions below the reduced bound. Various approaches to this problem are suggested in [30, 28, 23] and other papers. Here we use the method of [6, 8], in a somewhat modified form.

We refer to [17, 27] for the history of the numerical solution of Diophantine equations and extensive bibliography up to 1989. Some of later references most close to the subject of the present paper are [14, 15, 16, 31, 32].

Acknowledgements

The main part of this paper was written during the first named author’s postdoctoral stage at the Max-Planck-Institut für Mathematik, Bonn. At different stages of preparation of this paper he was also supported by the Bourse Chateaubriand du Gouvernement Français, Karl-Franzens-Universität Graz, and Instituto de Matemática Pura e Aplicada. He is grateful to Professor J.-M. Deshouillers at Bordeaux, Professor F. Hirzebruch at Bonn, Professor F. Halter-Koch at Graz, and Professor J. Palis at Rio de Janeiro for their generous hospitality.

We would like to thank Henri Cohen, Xavier Roblot, Nikos Tzanakis, Benne de Weger, and Don Zagier for interesting discussions and suggestions.

The last but not least, we are pleased to thank the referee for a number of very valuable comments, in particular concerning Proposition 3.1.

2. Notation and conventions

Throughout the paper p is a fixed prime number, and f(x) ∈ ℤ[x] a fixed separable polynomial of degree n ≥ 2. For the sake of further applications, we do not exclude the case p = 2 wherever possible. In all cases where we had to assume that p ≠ 2, this is explicitly specified. We fix a primitive root of unity ζ of degree p and put

P = {0, …, p − 1}.

Given b ∈ ℤ, we denote by b_{mod p} the uniquely defined b′ ∈ P such that b ≡ b′ (mod p).

We fix once and for all an embedding \overline{ℚ} → ℂ, so that any algebraic number has a well defined complex value. We use the branches of the functions z^{1/p} and log z defined by −π/p < arg z^{1/p} ≤ π/p and −π <

Im log z ≤ π. We write z^{−1/p} instead of (z^{1/p})^{−1}. Note that

Re z_{1}, Re z_{2} > 0 ⟹ (z_{1}z_{2}^{±1})^{1/p} = z_{1}^{1/p}z_{2}^{±1/p}.  (3)

Put

Sol = {x ∈ ℤ : (a^{−1}f(x))^{1/p} ∈ ℤ} .

Elements of the set Sol are referred to as “solutions”.

For a vector b = (b_{1}, …, b_{μ}) ∈ ℂ^{μ} put |b|_{∞} = max(|b_{1}|, …, |b_{μ}|). We use O_{1}(…) as a quantitative version of the standard notation

O(…):

A = O_{1}(B)

means |A| ≤ B.

We fix two distinct roots α and β of f(x) and put

c_{1} = max (\overline{|α|}, \overline{|β|}) , X_{1} = 3c_{1},

where \overline{|α|} is the maximum of the absolute values of the conjugates of α over ℚ, and \overline{|β|} is defined similarly.

Solutions satisfying |x| ≤ X_{1} can be quickly found by direct enumeration. In the sequel we restrict ourselves on the solutions satisfying |x| > X_{1}. In particular, we say simply “solution” instead of “solution with |x| > X_{1}” and write “x ∈ Sol instead of “x ∈ Sol and |x| > X_{1}”.

The assumption |x| > X_{1} allows us to avoid certain pathologies that occur for small solutions. In particular,

x ≠ 0, α, β and arg \frac{x − α}{x − β} ≠ π.  (4)

We shall use properties (4) of the solutions without special reference.

More specific notations are introduced in the course of the paper. For the reader’s convenience, we give a glossary of the most important notations in Table 2.

For the practical implementation of our method one should be able to perform various operations in certain number fields. We distinguish here four operations:

(PD) find the prime ideal decomposition of a given fractional ideal;

(U) find the group of roots of unity and a system of fundamental units;

Superelliptic equations 5

Table I. Specific notations

Notation  Where introduced  Notation  Where introduced
𝕂_{0}  Beginning of Subsection 4.1^{∗}  Ξ(α)  Lemma 3.2
M_{0}  Equations (15) and (16)  M  Equation (17)
𝕂, m, s, t, σ_{i}, α_{i}, β_{i}  Beginning of Subsection 4.2  s_{0}, t_{0}  Proposition 4.2.1
Sol(𝕂), k(x), k_{i}(x), k(x)  After Proposition 4.2.1  φ(x)  Subsection 4.3
η_{j} , Θ, θ(x), b_{j} (x), b(x)  End of Subsection 4.3  φ_{i}(x)  Equation (39)
θ, k, Sol(𝕂, k, θ)  Beginning of Subsection 4.4  ζ_{i}  After equation (39)
θ_{i}, η_{ij} , ρ_{i}, γ_{i}  Equation (40)  A, a_{ij}  After equation (40)
Δ_{i}, λ_{i}  Equation (41)  X_{4}  Corollary 4.4.2
c_{2}–c_{10}, X_{2}, X_{3}  Equation (42)  c_{11}  Theorem 4.5.1
i_{1}, i_{2}  Equations (60), (61) and (62)  Φ(x)  Equation (63)
c_{13}–c_{16}, B_{0}  End of Subsection 4.5  c_{12}  After equation (66)
j_{1}, j_{2}, Δ, λ  Subsection 4.6.1  ∥ … ∥  After equation (79)
c_{18}, c_{19}  After equation (78)  B′_{0}  Subsection 4.7
ω_{i}, γ′_{i}, c_{19}–c_{23}, X_{5}  Before Lemma 4.7.1  b′_{j} (x)  Equation (87)
𝕂′_{0}, τ : 𝕂′_{0}→𝕂′_{0}  Beginning of Subsection 5.2  s′, s′_{0}  Proposition 5.3.1
𝕂′, τ : 𝕂′→𝕂′  Beginning of Subsection 5.3  X_{7}, X_{8}  Appendix D

∗ In the case of (α, β)-symmetry 𝕂_{0} is defined in the beginning of Subsection 5.2.

(PI) decide whether a given fractional ideal is principal and find its generator if it is;

(CG) compute the class group, construct a system of representatives of the ideal classes and find the representative of a given fractional ideal.

(Note that (CG) partially covers (PI).) Fulfilling these operations (which will be referred to as “multiplicative”) in the occurring fields seems to be the main difficulty of our method.

We do not mention here “additive” operations (finding integral bases, etc.). Though these operations should also be performed, they are much easier algorithmically than the “multiplicative” ones. See, for example, [10, 20, 19].

3. Classical background

In this section we review some classical facts [2, 25, 22, 21, 29], but in a very explicit setting. The results of this section do not require the assumption |x| > X_{1}.

Fix a root α of f(x). A prime ideal 𝔭 of the field ℚ(α) is exclusive if

either Ord_{𝔭}(a) > 0 or Ord_{𝔭}(α) < 0 or Ord_{𝔭} (f′(α)) > 0,

where a is from (1). (Recall that Ord_{𝔭}(γ) is the largest integer m such that γ ∈ 𝔭^{m}.)

PROPOSITION 3.1. Let 𝔭 be a prime ideal of ℚ(α) with Ord_{𝔭}(α) ≥ 0. Then for any x ∈ Sol one has either

0 ≤ Ord_{𝔭}(x − α) ≤ Ord_{𝔭}(f′(α)),  (5)

or^{1}

0 ≤ (Ord_{𝔭}(a) − Ord_{𝔭}(x − α))_{mod p} ≤ Ord_{𝔭}(f′(α)).  (6)

In particular, if 𝔭 is non-exclusive then p|Ord_{𝔭}(x − α).

Proof. We write Ord instead of Ord_{𝔭}. Denote by O_{𝔭} the local ring of the ideal 𝔭 (recall that O_{𝔭} = {γ ∈ ℚ(α) : Ord(γ) ≥ 0}) and put f_{α}(x) = f(x)/(x − α). Since f′(α) is the resultant of the polynomials x − α and f_{α}(x), both having coefficients in O_{𝔭}, we have

A(x)(x − α) + B(x)f_{α}(x) = f′(α)  (7)

for some A(x), B(x) ∈ O_{𝔭}[x].

Now let (x, y) be a solution of (1) with Ord(x − α) > Ord(f′(α)). Then Ord (f_{α}(x)) ≤ Ord(f′(α)) by (7). Since

Ord(x − α) = Ord (f(x)) − Ord (f_{α}(x))
= Ord (ay^{p}) − Ord (f_{α}(x))
≡ Ord(a) − Ord (f_{α}(x)) (mod p),

we have (6). The proposition is proved.

The following lemma is crucial for the effective study of superelliptic equations.

LEMMA 3.2. There exists a finite effectively constructible set Ξ = Ξ(α) ⊂ ℚ(α) with the following property. For any x ∈ Sol

x − α = ξλ^{p}  (8)

with ξ ∈ Ξ and λ ∈ ℚ(α).

Proof. We construct the set Ξ as follows. Write the principal ideal (α) as (α)_{0}/(α)_{∞}, where (α)_{0} and (α)_{∞} are coprime integral ideals of the field ℚ(α). Let 𝔭_{1}, …, 𝔭_{k} be all exclusive ideals satisfying Ord_{𝔭}(α) ≥ 0. Consider ideals of the type

𝔞 = 𝔞(b_{1}, …, b_{k}) = (α)_{∞}^{−1}𝔭_{1}^{b_{1}} ⋯ 𝔭_{k}^{b_{k}},  (9)

1 Recall that for any b ∈ ℤ we denote by b_{mod p} the unique b′ ∈ P such that b ≡ b′ (mod p).

where every b_{i} ∈ P satisfies either

b_{i} ≤ Ord_{𝔭_{i}}(f′(α)),  (10)

or

0 ≤ (Ord_{𝔭_{i}}(a) − b_{i})_{mod p} ≤ Ord_{𝔭_{i}}(f′(α)).  (11)

For any such 𝔞 let Δ = Δ(𝔞) be a maximal set of pairwise nonequivalent^{2} ideals 𝔟 of the field ℚ(α) such that 𝔞𝔟^{p} is principal for any 𝔟 ∈ Δ. (The set Δ can happen to be empty.) Constructing the set Δ requires the operation (CG) in the field ℚ(α). If this field has class number 1, then we can put Δ(𝔞) = {(1)} for any 𝔞.

Fix a generator ξ_{0} for any principal ideal 𝔞𝔟^{p}, where 𝔞 is of the type (9) and 𝔟 ∈ Δ(𝔞). (Here the operation (PI) is needed.) Let Ξ_{0} be the set of all numbers ξ_{0} obtained this way. Also, let ω generate the group of roots of unity of the field ℚ(α) and η_{1}, …, η_{r} be a system of basic units (here (U) is needed). We put

Ξ = {ξ_{0}ω^{b_{0}}η_{1}^{b_{1}} ⋯ η_{r}^{b_{r}} : ξ_{0} ∈ Ξ_{0}, b_{0}, …, b_{r} ∈ P} .

It is easy to see that the set Ξ is as desired. Let x ∈ Sol. By Proposition 3.1 the principal ideal (x − α) can be presented in the form 𝔞𝔟_{1}^{p} where 𝔞 is an ideal of the type (9). Let 𝔟 ∈ Δ(𝔞) be equivalent to 𝔟_{1} and ξ_{0} ∈ Ξ_{0} generate 𝔞𝔟^{p}. Then (x − α) = (ξ_{0})(λ_{0})^{p} with λ_{0} ∈ ℚ(α). Therefore we have (8) with ξ ∈ Ξ and λ ∈ ℚ(α). The lemma is proved.

The most important case of equation (1) is when the polynomial f(x) is irreducible. Under this assumption one has further (severe) restrictions for Ord_{𝔭}(x − α), which considerably reduces the set Ξ.

Indeed, denote by f_{n} the leading coefficient of f(x), that is

f(x) = f_{n}x^{n} + terms of lower degree.  (12)

Let 𝔭 be a prime ideal of ℚ(α) and f = f_{𝔭} the residue degree of 𝔭 over ℚ. That is, N_{ℚ(α)/ℚ}(𝔭) = P^{f}, where P = P (𝔭) is the underlying prime. Since N_{ℚ(α)/ℚ}(x − α) = (a/f_{n})y^{p}, we have

f_{𝔭}Ord_{𝔭}(x − α) ≡ Ord_{P} (a/f_{n}) (mod p)  (13)

for any solution^{3} x. This defines Ord_{𝔭}(x−α) uniquely modulo p as soon as f_{𝔭} ≢ 0 (mod p).

2 Recall that ideals 𝔟_{1} and 𝔟_{2} are equivalent if the fractional ideal 𝔟_{1}𝔟_{2}^{−1} is principal.

3 Sometimes (13) even provides a local obstruction for solubility of equation (1): if f_{𝔭} ≡ 0 (mod p) but Ord_{P} (a/f_{n}) ≢ 0 (mod p) then (1) has no solutions at all.

Hence, when f(x) is irreducible, one can, for every 𝔭_{i} with f_{i} := f_{𝔭_{i}} ≢ 0 (mod p), define the corresponding b_{i} ∈ P uniquely from f_{i}b_{i} ≡ Ord_{P_{i}}(a/f_{n}) (mod p), rather than consider all possible b_{i} satisfying (10) or (11). (Here P_{i} = P (𝔭_{i}).) In particular, b_{i} = 0 whenever

f_{i} ≢ 0 (mod p) and Ord_{P_{i}}(a/f_{n}) ≡ 0 (mod p).  (14)

Therefore the ideals 𝔭_{i} which satisfy (14) can be excluded from consideration.

4. The general method

4.1. Admissible fields

Put 𝕂_{0} = ℚ(α, β).

DEFINITION 4.1.1. A number field 𝕂 is admissible for a solution x if 𝕂 = 𝕂_{0} (ζ^{k}(\frac{x−α}{x−β})^{1/p}) for some k ∈ P. A system of number fields \{𝕂\}

is a complete system of admissible fields if it contains an admissible field for any solution x.

All conjugates of (\frac{x−α}{x−β})^{1/p} over 𝕂_{0} are among the numbers ζ^{k}(\frac{x−α}{x−β})^{1/p}, where k ∈ P. Hence any field isomorphic to 𝕂 over 𝕂_{0} is admissible for x as soon as 𝕂 is admissible for x. A complete system is minimal if it consists of fields pairwise non-isomorphic over 𝕂_{0}.

By Kummer’s theory [12, Ch. 6, Th. 8.1], either ζ^{k}(\frac{x−α}{x−β})^{1/p} ∈ 𝕂_{0}

for some k ∈ P, or [𝕂_{0} (ζ^{k}(\frac{x−α}{x−β})^{1/p}) : 𝕂_{0}] = p for all k ∈ P, and the

p fields 𝕂_{0} (ζ^{k}(\frac{x−α}{x−β})^{1/p}) are isomorphic over 𝕂_{0}. This prompts the

following procedure for constructing a complete system of admissible fields. Let Ξ(α) be the set constructed in Lemma 3.2 and Ξ(β) a similar set for the root β. Put

M_{0} = {ξ′/ξ′′: ξ′ ∈ Ξ(α), ξ′′ ∈ Ξ(β)} ⊂ ℚ(α, β).  (15)

If α and β are conjugate over ℚ and τ: ℚ(α) → ℚ(β) is the automorphism taking α to β, then we can define M_{0} alternatively as

M_{0} = {ξ/τ(ξ): ξ ∈ Ξ(α)} .  (16)

Further, put

M = {μ ∈ M_{0} : μ is not a p-th power in 𝕂_{0}} .  (17)

Then the fields 𝕂_{0} and all 𝕂_{0} (μ^{1/p}), where μ runs the set M, form a complete system of admissible fields. Testing them for isomorphism, we obtain a minimal complete system.

It is worth mentioning here that, though the set M can be large, we expect that the size of the minimal complete system obtained this way would be reasonable, because distinct μ ∈ M often give rise to 𝕂_{0}-isomorphic fields 𝕂_{0} (μ^{1/p}). This expectation was confirmed in all examples we considered. For instance, in the second of the examples discussed in Section 6, we had |M| = 18, while the minimal complete system included only 4 fields (together with 𝕂_{0}).

4.2. A fixed admissible field

Starting from this subsection we fix an admissible field 𝕂 from the complete system constructed in the previous subsection. Let m = [𝕂: ℚ] = s + 2t, where σ_{1}, …, σ_{s}: 𝕂 → ℝ are the real embeddings of 𝕂, and σ_{s+1}, …, σ_{s+2t}: 𝕂 → ℂ are the complex ones, σ_{s+i} and σ_{s+i+t} being complex conjugate. We write α_{i} and β_{i} instead of σ_{i}(α) and σ_{i}(β), respectively.

The following observation is immediate.

PROPOSITION 4.2.1. If [𝕂: 𝕂_{0}] = p ≥ 3, then each real embedding of 𝕂_{0} has exactly one real prolongation to 𝕂, and \frac{p−1}{2} pairs of complex conjugate prolongations. In particular, in this case s = s_{0} and t = pt_{0} + \frac{p−1}{2}s_{0}, where s_{0} and 2t_{0} are the numbers of real and complex embeddings of 𝕂_{0}, respectively.

We denote by Sol(𝕂) the set of solutions x such that 𝕂 is admissible for x. For any x ∈ Sol(𝕂) there exists k(x) ∈ P such that

ζ^{k(x)}(\frac{x−α}{x−β})^{1/p} ∈ 𝕂. Of course, k(x) is not well-defined in the case ζ ∈ 𝕂_{0}.

Given x ∈ Sol(𝕂) and i ∈ {1, …, m}, define k_{i}(x) ∈ P from

σ_{i} (ζ^{k(x)}(\frac{x−α}{x−β})^{1/p}) = ζ^{k_{i}(x)}(\frac{x−α_{i}}{x−β_{i}} )^{1/p}.  (18)

Then

k_{1}(x) = ⋯ = k_{s}(x) = 0,  (19)
k_{i}(x) + k_{i+t}(x) ≡ 0 (mod p) (s < i ≤ s + t).  (20)

Therefore there are at most p^{t} possibilities for the vector k(x) = (k_{1}(x), …, k_{m}(x)).

Now assume that [𝕂: 𝕂_{0}] = p. Then any embedding of 𝕂_{0} has p distinct prolongations to 𝕂. If σ_{i_{1}} and σ_{i_{2}} are distinct embeddings of 𝕂 coinciding on 𝕂_{0} then k_{i_{1}} ≠ k_{i_{2}}. Therefore, in addition to (19)–(20), we have the following:

if σ_{i_{1}}, …, σ_{i_{p}} are the p distinct prolongations of a fixed embedding of 𝕂_{0}, then {k_{i_{1}}(x), …, k_{i_{p}}(x)} = P.

(21)

It follows from Proposition 4.2.1 and (19)–(21) that in the case [𝕂: 𝕂_{0}] = p ≥ 3 there at most (2^{\frac{p−1}{2}} (\frac{p−1}{2})!)^{s_{0}} (p!)^{t_{0}} possibilities for k(x). See Appendix B for further ideas how to reduce the number of possibilities for k(x).

4.3. Function φ(x) and set Θ

For any x ∈ Sol(𝕂) put

φ(x) = (x − β) (ζ^{k(x)}(\frac{x−α}{x−β})^{1/p} − 1)^{p} .  (22)

PROPOSITION 4.3.1. There exists a finite effectively constructible set Θ_{0} ⊂ 𝕂 with the following property: for any x ∈ Sol(𝕂) there are θ_{0} ∈ Θ_{0} and a unit η of the field 𝕂 such that

φ(x) = θ_{0}η.  (23)

Proof. For any prime ideal 𝔭 of 𝕂 put

u_{1}(𝔭) = max (0, −Ord_{𝔭}(α), −Ord_{𝔭}(β)) ,  (24)
u_{2}(𝔭) = max (0, Ord_{𝔭}(α − β)) .  (25)

Then u_{1} and u_{2} are non-negative integers both equal to 0 for all but finitely many 𝔭. If the polynomial f(x) is monic then u_{1}(𝔭) = 0 for all 𝔭.

Let Θ_{0} be a maximal set of pairwise non-associate θ_{0} ∈ 𝕂 satisfying

−u_{1}(𝔭) ≤ Ord_{𝔭}(θ_{0}) ≤ pu_{2}(𝔭) + (p − 1)u_{1}(𝔭)  (26)

for all 𝔭. (Recall that two algebraic numbers are associate if their ratio is a unit.) Note that, in order to construct Θ_{0}, one should be able to perform the operations (PD) and (PI) in the field 𝕂.

Now let x be a solution. Then

φ(x)φ̃(x) = (β − α)^{p}  (27)

Superelliptic equations 11

where

φ̃(x) = ∏_{{k′∈P \atop k′≠k(x)}}(x − β) (ζ^{k′}(\frac{x−α}{x−β})^{1/p} − 1)^{p}

For some k′′ ∈ P we have

φ(x)  =  ((x − α)^{1/p} − ζ^{k′′} (x − β)^{1/p})^{p}  (28)
φ̃(x) = ∏_{{k′∈P \atop k′≠k′′}} ((x − α)^{1/p} − ζ^{k′} (x − β)^{1/p})^{p}  (29)

Fix a prime ideal 𝔭 of the field 𝕂. Let | … |_{𝔭} be the 𝔭-adic valuation on 𝕂, extended somehow to the field 𝕂 (ζ, (x − α)^{1/p}, (x − β)^{1/p}). As follows from (28) and (29), we have

|φ(x)|_{𝔭} ≤ max (1, |α|_{𝔭}, |β|_{𝔭}) ,
|φ̃(x)|_{𝔭} ≤ (max (1, |α|_{𝔭}, |β|_{𝔭}))^{p−1} .

Together with (27) this yields

−u_{1}(𝔭) ≤ Ord_{𝔭} (φ(x)) ≤ pu_{2}(𝔭) + (p − 1)u_{1}(𝔭).  (30)

Thus,

φ(x) is associate to some θ_{0} ∈ Θ_{0}.  (31)

The proposition is proved.

Remark 4.3.2. In the case [𝕂: 𝕂_{0}] = p the set Θ_{0} can be made smaller. Indeed, in this case

N_{𝕂/𝕂_{0}} (φ(x)) = (β − α)^{p}.  (32)

Hence all θ_{0} such that the principal ideals

(N_{𝕂/𝕂_{0}} (θ_{0})) and ((β − α)^{p})  (33)

are distinct, can be excluded from the set Θ_{0}. Let Ω be the group of roots of unity of the field 𝕂, and η_{1}, …, η_{r} a system of fundamental units. (Of course r = s + t − 1.) Put

Θ = {θ_{0}ω: θ_{0} ∈ Θ_{0}, ω ∈ Ω}.

Then for any x ∈ Sol(𝕂) there exists θ(x) ∈ Θ such that

φ(x) = θ(x)η_{1}^{b_{1}(x)} ⋯ η_{r}^{b_{r}(x)}  (34)

with b(x) = (b_{1}(x), …, b_{r}(x)) ∈ ℤ^{r}.

4.4. Fixed admissible field, θ and k

Starting from this point, we fix θ ∈ Θ and k = (k_{1}, …, k_{m}) ∈ P^{m} and consider the set

Sol(𝕂, k, θ) = {x ∈ Sol(𝕂): k(x) = k, θ(x) = θ}.  (35)

As we have seen in the Subsection 4.2, we have to consider only vectors k satisfying

k_{1} = ⋯ = k_{s} = 0,  (36)
k_{i} + k_{i+t} ≡ 0 (mod p) (s < i ≤ s + t).  (37)

In the case [𝕂: 𝕂_{0}] = p we also require that

if σ_{i_{1}}, …, σ_{i_{p}} are the p distinct prolongations of a fixed embedding of 𝕂_{0}, then {k_{i_{1}}, …, k_{i_{p}}} = P.

(38)

For any x ∈ Sol(𝕂, k, θ) put

φ_{i}(x) = (x − β_{i}) (ζ_{i}(\frac{x−α_{i}}{x−β_{i}} )^{1/p} − 1)^{p} = σ_{i}(φ(x)),  (39)

where ζ_{i} = ζ^{k_{i}}. We also write

\begin{matrix}θ_{i} = σ_{i}(θ), & η_{ij} = σ_{i}(η_{j}), \\ ρ_{i} = \{ \begin{matrix}1 − p, & k_{i} = 0, \\ 1, & k_{i} ≠ 0, \end{matrix} & γ_{i} = \{ \begin{matrix}(\frac{β_{i}−α_{i}}{p} )^{p} , & k_{i} = 0, \\ (ζ_{i} − 1)^{p} , & k_{i} ≠ 0, \end{matrix} \end{matrix}  (40)

where 1 ≤ i ≤ m. Let A = [a_{ij}]_{1≤j,i≤r} be the inverse for the matrix [log |η_{ij}|]_{1≤i,j≤r}. For 1 ≤ j ≤ r put

δ_{i} = ∑_{j=1}^{r} a_{ij}ρ_{j}, λ_{i} = ∑_{j=1}^{r} (a_{ij} log |γ_{j}θ_{j}^{−1}|) .  (41)

Also, we need some constants:

c_{2} = 4 |2^{−1/p} + (2p)^{−1} − 1| , c_{3} = 2 (1 − 2^{−1/p}) ,
c_{4} = 2 sin(π/p),  c_{5} = max_{1≤i≤m} (|α_{i}| + |β_{i}|) ,
c_{6} = max_{1≤i≤m} \frac{|α_{i}|^{2}+|β_{i}|^{2}}{|α_{i}−β_{i}|} ,  c_{7} = 1.39p max (c_{3}c_{4}^{−1}c_{5}, pc_{2}c_{6}) ,
c_{8} = max_{1≤j≤r}|δ_{j}|,  X_{2} = max (X_{1}, 2c_{3}c_{4}^{−1}c_{5}, 2pc_{2}c_{6}) ,
c_{9} = \frac{1}{20} + max_{1≤j≤r}|λ_{j}|,  c_{10} = c_{7} max_{1≤i≤r} ∑_{j=1}^{r}|a_{ij}|,

X_{3} = max(X_{2}, 20c_{10}).

(42)

PROPOSITION 4.4.1. Suppose that x ∈ Sol(𝕂, k, θ) and |x| > X_{2}. Then

φ_{i}(x) = γ_{i}x^{ρ_{i}}e^{O_{1}(c_{7}|x|^{−1})} (1 ≤ i ≤ m),  (43)
b_{i}(x) = δ_{i} log |x| + λ_{i} + O_{1} (c_{10}|x|^{−1}) (1 ≤ j ≤ r),  (44)

Also, if |x| > X_{3} then

|b(x)|_{∞} ≤ c_{8} log |x| + c_{9}.  (45)

(Recall that b_{j}(x) were defined in the previous section, and b(x) = (b_{1}(x), …, b_{r}(x).)

Proof. Let z be a complex number with the condition |z| ≤ 1/2. Then

(1 + z)^{1/p} = 1 + p^{−1}z + O_{1}(c_{2}|z|^{2}) = 1 + O_{1}(c_{3}|z|), (46)
1 + z = e^{O_{1}(1.39|z|)}.  (47)

For (47) see [27, p. 106]. For (46), put

ψ(z) = z^{−2} ((1 + z)^{1/p} − 1 − p^{−1}z) .

Then

|ψ(z)| = |∑_{ν=2}^{∞} \binom{1/p}{ν} z^{ν−2}| ≤ ∑_{ν=2}^{∞} |\binom{1/p}{ν}| (1/2)^{ν−2} = |ψ(−1/2)| = c_{2},

which proves the first equality in (46). The second one can be obtained in the same manner.

As follows from (3), for |x| ≥ X_{1} we have

φ_{i}(x) = x (ζ_{i} (1 − α_{i}x^{−1})^{1/p} − (1 − β_{i}x^{−1})^{1/p})^{p} .  (48)

When k_{i} ≠ 0 we have ζ_{i} ≠ 1 and, moreover, |ζ_{i} − 1| ≥ c_{4}. Therefore

φ_{i}(x) = (ζ_{i} − 1)^{p} x (1 + O_{1} (c_{3}c_{4}^{−1}c_{5}|x|^{−1}))^{p} .

Since |x| ≥ X_{2}, the O_{1}-term is bounded by 1/2, and we obtain

φ_{i}(x) = γ_{i}xe^{O_{1}(1.39pc_{3}c_{4}^{−1}c_{5}|x|^{−1})},

which proves (43) in the case k_{i} ≠ 0.

When k_{i} = 0 we have

φ_{i}(x) = (\frac{β_{i}−α_{i}}{p} )^{p} x^{1−p} (1 + O_{1} (pc_{2}c_{6}|x|^{−1}))^{p} .

Again the O_{1}-term is bounded by 1/2, and we obtain

φ_{i}(x) = γ_{i}x^{1−p}e^{O_{1}(1.39p^{2}c_{2}c_{6}|x|^{−1})},

and (43) is established in the case k_{i} = 0 as well.

Now prove (44). Since

log |θ_{i}^{−1}φ_{i}(x)| = b_{1}(x) log |η_{i1}| + ⋯ + b_{r}(x) log |η_{ir}| (1 ≤ i ≤ r), (49)

we have

b_{i}(x) = ∑_{j=1}^{r} a_{ij} log |θ_{j}^{−1}φ_{j}(x)|  (50)

= (∑_{j=1}^{r} a_{ij}ρ_{j}) log |x| + ∑_{j=1}^{r} (a_{ij} log |γ_{j}θ_{j}^{−1}|) +

O_{1} (c_{7}|x|^{−1} ∑_{j=1}^{r} |a_{ij}|) ,  (51)

which is (44). Finally, (45) is a direct consequence of (44). The proposition is proved.

We conclude this subsection observing that in the case

|{i: k_{i}(x) = 0}| ≠ m/p  (52)

an upper bound for the solutions follows already from Proposition 4.4.1. Note that, in view of (38), the inequality (52) can take place only for 𝕂 = 𝕂_{0}, and that (52) is always the case when m ≢ 0 (mod p).

COROLLARY 4.4.2. Suppose that (52) holds, and put ρ′ = m − p |{i: k_{i}(x) = 0}|. Then any x ∈ Sol (𝕂, k, θ) satisfies

|x| ≤ X_{4} := max (X_{2}, 3mc_{7}, e^{1/(3|ρ′|)} |γ_{1} ⋯ γ_{m}|^{−1/ρ′} |θ_{1} ⋯ θ_{m}|^{1/ρ′}) .

(53)

Proof. On the one hand,

φ_{1}(x) ⋯ φ_{m}(x) = N_{𝕂/ℚ}(φ(x)) = ±θ_{1} ⋯ θ_{m}.  (54)

On the other hand,

φ_{1}(x) ⋯ φ_{m}(x) = γ_{1} ⋯ γ_{m}x^{ρ_{1}+···+ρ_{m}}e^{O_{1}(mc_{7}|x|^{−1})}.

Since ρ_{1} + ⋯ + ρ_{m} = ρ′, the result follows.

4.5. A large upper bound for |b(x)|_{∞}

In this subsection, assuming that p ≥ 3, [𝕂: ℚ] ≥ 3 and |x| ≥ X_{3}, we obtain a large upper bound for |b(x)| as a consequence of Baker’s theory of linear forms in logarithms. We apply a result of Baker and Wüstholz [4].

THEOREM 4.5.1. [4, p. 20] Let ϑ_{0}, …, ϑ_{r} be complex algebraic numbers distinct from 0 and 1, and b = (b_{1}, …, b_{r+1}) ∈ ℤ^{r+1}. Also, let

d ≥ [ℚ(ϑ_{0}, …, ϑ_{r}) : ℚ],  (55)
h_{i} ≥ max (h(ϑ_{i}), d^{−1}| log ϑ_{i}|, d^{−1}) (0 ≤ i ≤ r),  (56)

where h(…) is the absolute logarithmic height. Then either

Λ = log ϑ_{0} + b_{1} log ϑ_{1} + ⋯ + b_{r} log ϑ_{r} + b_{r+1}πi = 0,  (57)

or

|Λ| ≥ exp(−c_{11} log B).  (58)

Here B = max(|b_{1}| , …, |b_{r+1}| , e) and

c_{11} = 18π · 32^{r+4}(r + 3)!(r + 2)^{r+3}d^{r+3} log(2d(r + 2))h_{0} ⋯ h_{r}.

Remark 4.5.2. The parameters n, h′(α_{1}), …, h′(α_{n}), h′(L) of the original theorem in [4] correspond in Theorem 4.5.1 to r + 2, h_{0}, …, h_{r}, π/d, log B, respectively.

We have slightly modified the statement in [4], to allow inequalities in (55) and (56). It is often much easier (and quicker) to find an upper bound for the degree of a number field or for the height of an algebraic number, than to compute any of them exactly.

LEMMA 4.5.3. Let z and C_{1} be positive real numbers and C_{2} an arbitrary real number. Suppose that

z ≤ C_{1} log z + C_{2}.  (59)

Then

z ≤ 2(C_{1} log C_{1} + C_{2}).

Proof. This is the case h = 1 of Lemma 2.2 from [18].

Now we can obtain an upper bound for |b(x)|_{∞}. By (21), in the case [𝕂: 𝕂_{0}] = p there exist i_{1}, i_{2} ∈ {1, …, m} such that

σ_{i_{1}} |_{𝕂_{0}} = σ_{i_{2}} |_{𝕂_{0}} ,  (60)
k_{i_{1}} ≠ 0, k_{i_{2}} ≠ 0, k_{i_{1}} ≠ k_{i_{2}}.  (61)

It follows from (60) that

α_{i_{1}} = α_{i_{2}}, β_{i_{1}} = β_{i_{2}}.

In the case 𝕂 = 𝕂_{0} choose i_{1} and i_{2} such that among the numbers

α_{i_{1}}, α_{i_{2}}, β_{i_{1}}, β_{i_{2}}  (62)

there are at least three distinct. The required choice of i_{1} and i_{2} is possible by the condition [𝕂: ℚ] ≥ 3.

Let i_{1} and i_{2} be as defined above. Put

Φ(x) = \frac{γ_{i_{2}}^{ρ_{i_{1}}} φ_{i_{1}}(x)^{ρ_{i_{2}}}}{γ_{i_{1}}^{ρ_{i_{2}}} φ_{i_{2}}(x)^{ρ_{i_{1}}}} .  (63)

By the choice of i_{1} and i_{2}, the equation

Φ(x) = 1  (64)

has finitely many solutions, which can be easily found in practice (see Appendix C for the details). Now suppose that

Φ(x) ≠ 1.  (65)

By (43) we have (assuming |x| ≥ X_{2}):

Φ(x) = e^{O_{1}(c_{12}|x|^{−1})},  (66)

with c_{12} = 2pc_{7}. On the other hand,

Φ(x) = ϑ_{0}ϑ_{1}^{b_{1}(x)} ⋯ ϑ_{r}^{b_{r}(x)},  (67)

where

ϑ_{0} = \frac{γ_{i_{2}}^{ρ_{i_{1}}} θ_{i_{1}}^{ρ_{i_{2}}}}{γ_{i_{1}}^{ρ_{i_{2}}} θ_{i_{2}}^{ρ_{i_{1}}}} , ϑ_{j} = \frac{η_{i_{1}j}^{ρ_{i_{2}}}}{η_{i_{2}j}^{ρ_{i_{1}}}} .  (68)

Taking the logarithm, we obtain

log Φ(x) = log ϑ_{0} + b_{1}(x) log ϑ_{1} + ⋯ + b_{r}(x) log ϑ_{r} + b_{r+1}(x)πi, (69)

for some b_{r+1}(x) ∈ ℤ. Comparing the imaginary parts in (69), and using (66), we get

|b_{r+1}(x)| ≤ 1 + |b_{1}(x)| + ⋯ + |b_{r}(x)| + π^{−1}c_{12}|x|^{−1}  (70)
≤ 1 + π^{−1}c_{12} + r |b(x)|_{∞} .  (71)

Apply Theorem 4.5.1 to the right-hand side of (69). Since log Φ(x) ≠ 0, we obtain

|log Φ(x)| ≥ exp (−c_{11} log B(x)) ,  (72)

where

B(x) := max (b_{1}(x), …, b_{r}(x), b_{r+1}(x), e)
≤ 1 + π^{−1}c_{12} + r |b(x)|_{∞}  (73)
≤ c_{13} log |x| + c_{14}  (74)

with c_{13} = rc_{8} and c_{14} = max (1 + π^{−1}c_{12} + rc_{9}, e).

Combining (66) and (72), we obtain

log |x| ≤ c_{11} log B(x) + log c_{12}.  (75)

Assuming |x| ≥ X_{3}, we deduce from here that B(x) ≤ c_{15} log B(x)+c_{16} with c_{15} = c_{11}c_{13} and c_{16} = c_{13}c_{12} + c_{14}. By Lemma 4.5.3 we have

|b(x)|_{∞} ≤ B(x) ≤ B_{0} := 2(c_{15} log c_{15} + c_{16}).

4.6. Reduction of Baker’s bound

4.6.1. Preliminaries In practice, the value of B_{0} is too large for directly enumerating all possibilities for b(x). However, B_{0} may be significantly reduced by applying an appropriate version of the LLL-reduction algorithm, as described in [27]. We use here (see also [8]) a modification making the reduction process much more efficient; in particular, LLL can be replaced by the classical continued fractions algorithm, as in [3] (see also [33]).

Let j_{1} be defined by the condition

|δ_{j_{1}}| = max_{1≤j≤r} |δ_{j}| = c_{8}.  (76)

(Recall that the numbers δ_{j} are defined in (41).) We have δ_{j_{1}} ≠ 0, because the matrix A is non-degenerated.

The method of reduction we use depends on what we heuristically believe about the mutual arithmetic behaviour of the numbers δ_{j} and λ_{j}. We shall distinguish between the following cases.

1. Irrational case For some j_{2} ∈ {1, …, r}, we believe that the number δ_{j_{2}}λ_{j_{1}} − δ_{j_{1}}λ_{j_{2}} is not a linear combination of δ_{j_{1}} and δ_{j_{2}} with rational coefficients.

2. Semirational case For some j_{2} ∈ {1, …, r}, we believe that the quotient δ_{j_{1}}^{−1}δ_{j_{2}} is irrational, but the number δ_{j_{2}}λ_{j_{1}} − δ_{j_{1}}λ_{j_{2}} is a linear combination of δ_{j_{1}} and δ_{j_{2}} with rational coefficients.

3. Totally rational case We believe that for all j ∈ {1, …, r} the numbers δ_{j_{1}}^{−1}δ_{j} and δ_{j_{1}}^{−1} (δ_{j}λ_{j_{1}} − δ_{j_{1}}λ_{j}) are rational.

In the first two cases we fix such a j_{2} and put

δ = δ_{j_{1}}^{−1}δ_{j_{2}}, λ = δ_{j_{1}}^{−1} (δ_{j_{2}}λ_{j_{1}} − δ_{j_{1}}λ_{j_{2}}) .

By (44) and by the definition of δ and λ one has

|b_{j_{2}}(x) − δb_{j_{1}}(x) + λ| ≤ (1 + |δ|) c_{10}|x|^{−1} ≤ 2c_{10}|x|^{−1}  (77)

because by the choice of j_{1} and j_{2} we have |δ| ≤ 1. Combining this with (45), we obtain

|b_{j_{2}}(x) − δb_{j_{1}}(x) + λ| ≤ c_{18} exp(−c_{17} |b(x)|_{∞})  (78)

with c_{18} = 2c_{10} exp(c_{9}/c_{8}) and c_{17} = c_{8}^{−1}.

Notice that in the first two cases j_{1} ≠ j_{2}, in particular r ≥ 2. On the other hand, the rational case covers the case r = 1.

4.6.2. The irrational case Choose a not very large number κ > 2. (We discuss the practical choice of κ in Subsection 4.6.5.) By the theorem of Dirichlet, there exists a positive integer q ≤ κB_{0} such that

∥qδ∥ ≤ (κB_{0})^{−1},  (79)

where ∥ … ∥ is the distance to the nearest integer. In practice q can be quickly found from the continuous fraction expansion of δ. Multiplying (78) by q, we obtain

∥±b_{j_{1}}(x)∥qδ∥ + qλ∥ ≤ c_{18}κB_{0} exp(−c_{17} |b|_{∞}),  (80)

where “±” should be “+” if qδ is smaller than the nearest integer and “−” otherwise.

It follows from (79) that |b_{j_{1}}(x)|·∥qδ∥ ≤ κ^{−1}. Therefore (80) implies that

∥qλ∥ − κ^{−1} ≤ c_{18}κB_{0} exp(−c_{17} |b(x)|_{∞}).  (81)

If ∥qλ∥ ≥ 2κ^{−1}, which is heuristically plausible when κ is large enough, then we have a new estimate for |b(x)|_{∞}:

|b(x)|_{∞} ≤ c_{17}^{−1} (log B_{0} + log(c_{18}κ^{2}))  (82)

(compare this with the lemma from [3, Section 3]).

The reduced bound for |b(x)|_{∞} can be reduced again, using the same procedure, etc.

4.6.3. The semirational case We have

q_{1} + q_{2}δ + q_{3}λ = 0,  (83)

where q_{1}, q_{2} and q_{3} are integers, q_{3} ≠ 0, and gcd(q_{1}, q_{2}, q_{3}) = 1. We expect that the integers q_{1}, q_{2} and q_{3} are “very small” (around 10 or so in absolute value). This was confirmed in all examples we considered.

Multiplying (78) by q_{3} and using (83), we obtain

|b_{j_{2}}(x) − q_{1} − δ(b_{j_{1}}(x) + q_{2})| ≤ |q_{3}|c_{18} exp(−c_{17} |b(x)|_{∞}).

It follows that

min_{b∈ℤ,|b|≤B_{0}+|q_{2}|} ∥bδ∥ ≤ |q_{3}|c_{18} exp(−c_{17} |b(x)|_{∞}).  (84)

However, this minimum can be quickly computed using continued fractions, and we expect it to be (κ′B_{0})^{−1}, where κ′ is a reasonable number. We conclude that

|b(x)|_{∞} ≤ c_{17}^{−1} (log B_{0} + log(|q_{3}|c_{18}κ′)) .  (85)

4.6.4. The totally rational case Since this case requires a rather lengthy case-by-case analysis, and seldom occurs in practice (when r ≥ 2), it is treated in Appendix D.

4.6.5. The technology of reduction When r ≥ 2, we pick j_{2} ≠ j_{1} and continue as if it were irrational case. We take as a starting value κ = 10, and try the first reduction. When it is ∥qλ∥ < 2κ^{−1}, we change κ by 10κ and repeat the process. In most of the cases we obtained successful reduction in two or three iterations at most.

When we do not obtain successful reduction after seven-eight iterations of κ, we conclude that probably γ is a linear combination of 1 and δ with rational coefficients. This can be easily verified (see the second comment in Subsection 4.6.6), and this guess was always confirmed. Now if δ is irrational then we continue as in the semirational case. If δ is rational, then we redefine j_{2} and repeat the process.

If δ and γ are rational for all possible j_{2} then we are in the totally rational case, see Appendix D.

When r = 1 we are in the totally rational case from the very beginning.

4.6.6. Computational comments

1. Since in practice we deal with approximate values of δ and λ, we usually obtain, instead of (83), an inequality of the form

|q_{1} + q_{2}δ + q_{3}λ| ≤ ε,  (86)

where ε is a very small positive number (ε = 10^{−20}B_{0}^{−2} is typical). Though we do believe that, whenever (86) is detected with small integers q_{i}, it corresponds to the actual equality (83), we do not prove this, and in fact we do not need this: (86) is completely sufficient for our purposes.

For simplicity of exposition we assumed the exact equality (83) in our treatment of the semirational case. However, in real computations we used (86), with all constant correspondingly modified.

The similar convention applies to the totally rational case.

2. It is very easy to verify whether (86) holds with small integers q_{i}. One has to find, using the three-dimensional LLL, the (almost) shortest vector of the lattice generated by (C, [Cδ], [Cλ]), (0, 1, 0) and (0, 0, 1), where C is a sufficiently large positive integer (we used C = 10^{10}).

We refer to [8, Subsection 2.4.3] for further computational details and other subtleties.

4.7. Final enumeration

Unfortunately, the reduced bound B′_{0} may also be too large for the direct enumeration, because one has to check (2B′_{0} + 1)^{r} possibilities for the vector b(x). One can imagine several ways to overcome this difficulty, for instance:

− sieving modulo several primes, as in [28] and [23];

− use of Fincke–Pohst algorithm for finding all short vectors in a lattice, as in [30] and [28].

In [6, 8] one further approach to final enumeration was proposed, based on the inequality (77). In the present paper we use a more efficient version of this method. For 1 ≤ j ≤ r put

b′_{j}(x) = δ_{j_{1}}^{−1}δ_{j}b_{j_{1}}(x) − δ_{j_{1}}^{−1} (δ_{j}λ_{j_{1}} − δ_{j_{1}}λ_{j}) ,  (87)

where j_{1} is defined from (76). Then, replacing in (77) index j_{2} by j, we rewrite it as |b_{j}(x) − b′_{j}(x)| ≤ 2c_{10}|x|^{−1}. Since X_{3} ≥ 20c_{10}, we obtain

|b_{j}(x) − b′_{j}(x)| < 0.1 (1 ≤ j ≤ r)  (88)

as soon as |x| > X_{3}. In particular,

∥b′_{j}(x)∥ < 0.1 (1 ≤ j ≤ r),  (89)

Now we do as follows. For every integer b such that |b| ≤ B′_{0}, compute the real numbers b′_{j} := δ_{j_{1}}^{−1}δ_{j}b − δ_{j_{1}}^{−1} (δ_{j}λ_{j_{1}} − δ_{j_{1}}λ_{j}), and for each j, check for the condition ∥b′_{j}∥ < 0.1. This condition trivially holds for j = j_{1}, but for j ≠ j_{1} it needs not. If it is false for at least one j, then there is no solution x with |x| > X_{3} such that b_{j_{1}}(x) = b, and we go to the next b.

The heuristic probability that the integer b passes this severe test is 5^{1−r}, quite a small number (when r ≥ 2). For those very few b that survive after the test, we used the second test, based on Lemma 4.7.1 below.

Fix i such that k_{i} ≠ 0. For x ∈ ℤ put

ω_{i}(x) := γ_{i}^{−1}φ_{i}(x) − γ′_{i},

where γ′_{i} = \frac{β_{i}−ζ_{i}α_{i}}{ζ_{i}−1} . Also, put

\begin{matrix}c_{19} = 4(3/2)^{p} − 4 − 2p, & c_{20} = c_{2}(|α_{i}|^{2} + |β_{i}|^{2})|ζ_{i} − 1|^{−1}, \\ c_{21} = p^{−1}|γ′_{i}| + c_{20}X_{3}^{−1}, & c_{22} = c_{21}X_{3}^{−1}, \\ c_{23} = c_{19}c_{21} + pc_{20}, & X_{5} = max(X_{3}, 2c_{22}, 2c_{23}). \end{matrix}

LEMMA 4.7.1. If |x| > X_{5} then

|x − ω_{i}(x)| < min(1/2, c_{23}/(|ω_{i}(x)| − 1/2)).  (90)

Proof. For |z| ≤ 1/2 we have

(1 + z)^{p} = 1 + pz + O(c_{19}z^{2}),  (91)

which can be proved in the same manner as (46). As follows from (91),

(46) and (48), for |x| > X_{3} we have

φ_{i}(x) = γ_{i}x (1 + γ′_{i}x^{−1}/p + O_{1}(c_{20}x^{−2}))^{p}
= γ_{i}x (1 + γ′_{i}x^{−1} + O_{1}(c_{23}x^{−2}))

which yields

|x − ω_{i}| ≤ c_{23}x^{−1}.  (92)

Since |x| > 2c_{23}, this proves |x−ω_{i}| < 1/2. In particular, |ω_{i}(x)| < |x|+ 1/2, which together with (92) yields |x − ω_{i}(x)| < c_{23}/(|ω_{i}(x)| − 1/2). This proves the lemma.

The second test is: If ω_{i} = ω_{i}(x) for a solution x with |x| > X_{5} then

|ω_{i}| > X_{5} − 1/2 and ∥ω_{i}∥ < c_{23}/(|ω_{i}(x)| − 1/2).  (93)

We computed b_{1}, …, b_{r} as the nearest integers to b′_{1}, …, b′_{r}, respectively, and verified whether

ω_{i} := γ_{i}^{−1}θ_{i}η_{i1}^{b_{1}} ⋯ η_{ir}^{b_{r}} − γ′_{i}  (94)

satisfied (93). If it did, we put x to be the nearest integer to ω_{i} and checked whether it is a solution, just substituting it to the equation (1).

4.8. The algorithm

We summarize the contents of this section in the following algorithm for complete solution of the superelliptic equation (1), where p ≥ 3.

Step 1 Construct a complete system of admissible fields, as described in Subsection 4.1.

Step 2 Fix an admissible field 𝕂 not considered yet. If all admissible fields have already been considered, go to Step 10.

Step 3 Construct the set Θ, as described in Subsection 4.2.

Step 4 Fix θ ∈ Θ and k ∈ P^{m} (subject to restrictions formulated in the beginning of Subsection 4.4). If all possible pairs (θ, k) have already been considered, go to Step 2.

Step 5 If (52) holds, compute X_{4} and go to Step 4. Otherwise, compute X_{3} and go to the next step.

Step 6 Construct the function Φ(x) and find all integral solutions of (64). For each of the latter check whether it is a solution of (1).

Step 7 Compute Baker’s bound B_{0}.

Step 8 Find the reduced bound B′_{0}, as described in Subsection 4.6.

Step 9 Final enumeration (see Subsection 4.7).

Go to Step 4.

Step 10 Find X_{6} as the maximum of all X_{4}, computed at Step 5, and all X_{5}, computed at Step 9.^{4}

Step 11 For any x ∈ ℤ such that |x| ≤ X_{6} check whether x is a solution of (1).

Step 12 Collect all solutions obtained at Steps 6, 9, and 11.

Step 13 End.

Note in conclusion that we should be able to perform the operations (PD), (U), (CG) in the fields ℚ(α) and ℚ(β), and the operations (PD), (U), (PI) in any admissible field 𝕂 constructed on the Step 1 of the algorithm. The last demand seems to be the most difficult point of the proposed method. Indeed, the maximal degree of admissible fields will be pn(n − 1) in the worst case. Even for (p, n) = (3, 4) we shall have to perform “multiplicative” operations in fields of degree 36 (in the worst case), which is beyond the possibilities of the Algorithmic Algebraic Number Theory at its present state.

In the next section we shall see how to reduce the degrees of the fields occurring in the process of solution.

5. The (α, β)-symmetry

In this section we assume that p ≥ 3.

4 If the totally rational case occurred (see Appendix D), then one should also take into account X_{7} and X_{8}.

5.1. Preliminary preparations

We say that we have an (α, β)-symmetry if there exists an automorphism of ℚ(α, β) sending α to β and β to α. The roots α and β are called in this case symmetric. We shall see that, in the case of (α, β)- symmetry, the field ℚ(α, β) can be replaced by ℚ(α + β, αβ). Our considerations will be based on the following lemma.

LEMMA 5.1.1. Let 𝕂_{0} ⊂ 𝕂_{1} ⊂ 𝕂_{2} be a tower of number fields with the following properties:

[𝕂_{1} : 𝕂_{0}] = 2 and [𝕂_{2} : 𝕂_{1}] = p;

𝕂_{2} = 𝕂_{1}(ν), where ν^{p} = μ ∈ 𝕂_{1} and μ is conjugate to μ^{−1} over 𝕂_{0}.

Then

(a) [𝕂_{0}(ν + ν^{−1}) : 𝕂_{0}] = p.

Furthermore, let 𝕂 be a number field such that 𝕂_{0} ⊂ 𝕂 ⊂ 𝕂_{2} and [𝕂: 𝕂_{0}] = p. Then

(b) if ζ ∉ 𝕂_{0} then 𝕂 = 𝕂_{0}(ν + ν^{−1});

(c) if ζ ∈ 𝕂_{0} then 𝕂 is one of the p distinct fields 𝕂_{0}(ζ^{k}ν + ζ^{−k}ν^{−1}), where k ∈ P;

(d) the composite 𝕂_{1}𝕂 is 𝕂_{2}.

Proof. Clearly, 𝕂_{2} = 𝕂_{0}(ν). Further, ν and ν^{−1} are conjugate over 𝕂_{0}. Define the automorphism τ : 𝕂_{2} → 𝕂_{2} by τ(ν) = ν^{−1}. Then ν +ν^{−1} is stable with respect to τ, whence the degree [𝕂_{0}(ν + ν^{−1}) : 𝕂_{0}] divides p. This proves (a), because ν + ν^{−1} ∉ 𝕂_{0}. (If it were ν + ν^{−1} ∈ 𝕂_{0}, then we would have had [𝕂_{2} : 𝕂_{0}] = [𝕂_{0}(ν) : 𝕂_{0}] ≤ 2, a contradiction).

Assertion (d) is obvious: since p is odd, we have 𝕂_{1} ⊄ 𝕂, whence 𝕂{⊂ \atop ≠}𝕂_{1}𝕂 ⊆ 𝕂_{2}, and the single option is 𝕂_{1}𝕂 = 𝕂_{2}.

To prove (b) and (c) note that the fields 𝕂 correspond to non-trivial involutions of 𝕂_{2} over 𝕂_{0}, i.e. automorphisms τ: 𝕂_{2} → 𝕂_{2} satisfying

τ ≠ id, τ^{2} = id, τ|_{𝕂_{0}} = id_{𝕂0}.

The conjugates of ν over 𝕂_{0} are among the numbers

ν, ζν, …, ζ^{p−1}ν, ν^{−1}, ζν^{−1}, …, ζ^{p−1}ν^{−1}.  (95)

Since [𝕂_{0}(ν) : 𝕂_{0}] = 2p, all the numbers (95) are conjugate to ν over 𝕂_{0}.

We distinguish between three cases.

(b)′ ζ ∉ 𝕂_{1}. Then, among the conjugates of ν over 𝕂_{0}, only ν^{−1} belongs to 𝕂_{2}. Hence the unique involution of 𝕂_{2} over 𝕂_{0} is the one taking ν to ν^{−1}, and the single possibility for 𝕂 is 𝕂_{0}(ν + ν^{−1}).

(b)′′ ζ ∈ 𝕂_{1} \ 𝕂_{0}. In this case all the numbers (95) belong to 𝕂_{2}. Hence 𝕂_{2} is normal over 𝕂_{0} and the group G := Gal(𝕂_{2}/𝕂_{0}) is generated by τ: ν → ν^{−1} and σ: ν → ζν. Clearly, τ|_{𝕂_{1}} is the non-trivial involution of 𝕂_{1}/𝕂_{0}, whence τ(ζ) = ζ^{−1}. Therefore τσ = στ, whence G is abelian, and again τ is the unique involution of 𝕂_{2}/𝕂_{0}.

(c) ζ ∈ 𝕂_{0}. In this case τσ = σ^{−1}τ, and there are exactly p distinct involutions τ_{k} := σ^{k}τσ^{−k}, where k ∈ P. Indeed, the involutions τ_{k} are pairwise distinct because the numbers τ_{k}(ν) = ζ^{−2k}ν are distinct for distinct k ∈ P. Further, by the theorem of Sylow, all two-element subgroups of G are conjugate. Since there are at most [G: {1, τ}] = p subgroups conjugate to {1, τ}, there are no involutions other than τ_{0} = τ, τ_{1}, …, τ_{p−1}. The involutions τ_{k} correspond to the p distinct fields 𝕂_{0}(ζ^{k}ν+ζ^{−k}ν^{−1}), which completes the proof.

The lemma is proved.

5.2. Admissible fields

In the case of (α, β)-symmetry we define admissible fields in a way different from the general case. We put 𝕂′_{0} = ℚ(α, β) and let τ : 𝕂′_{0}→𝕂′_{0} be defined by τ(α) = β, τ(β) = α. Put 𝕂_{0} = ℚ(α + β, αβ) = (𝕂′_{0})^{τ}.

DEFINITION 5.2.1. A number field 𝕂 is admissible for a solution x if for some k ∈ P we have 𝕂 = 𝕂_{0} (ζ^{k}(\frac{x−α}{x−β})^{1/p} + ζ^{−k}(\frac{x−α}{x−β})^{−1/p}).

A complete system of admissible fields and a minimal complete system are defined as in Subsection 4.1

Let M be the finite subset of ℚ(α, β) defined in (16) and (17).

PROPOSITION 5.2.2. The fields 𝕂_{0} and 𝕂_{0} (μ^{1/p} + μ^{−1/p}), where μ runs M, form a complete system of admissible fields.

Proof. Suppose first that ζ^{k}(\frac{x−α}{x−β})^{1/p} ∈ 𝕂′_{0} for some k ∈ P. We shall see that in this case 𝕂_{0} is admissible for the solution x. We have

τ (ζ^{k}(\frac{x−α}{x−β})^{1/p}) = ζ^{k′}(\frac{x−α}{x−β})^{−1/p} for some k′ ∈ P. Therefore

ζ^{k+k′} = N_{𝕂′_{0}/𝕂_{0}} (ζ^{k}(\frac{x−α}{x−β})^{1/p}) ∈ 𝕂_{0}.

If ζ ∉ 𝕂_{0} then k′ = −k, whence

ζ^{k}(\frac{x−α}{x−β})^{1/p} + ζ^{−k}(\frac{x−α}{x−β})^{−1/p} = Tr_{𝕂′_{0}/𝕂_{0}} (ζ^{k}(\frac{x−α}{x−β})^{1/p}) ∈ 𝕂_{0}. (96)

When ζ ∈ 𝕂_{0} we define k′′ ∈ P by 2k′′ = k − k′ (mod p). Then

τ (ζ^{k′′}(\frac{x−α}{x−β})^{1/p}) = ζ^{k′′−k}τ (ζ^{k}(\frac{x−α}{x−β})^{1/p})
= ζ^{k′′−k}ζ^{k′}(\frac{x−α}{x−β})^{−1/p}
= ζ^{−k′′}(\frac{x−α}{x−β})^{−1/p},

and we obtain (96) with k′′ instead of k.

Now suppose that

[𝕂′_{0} ((\frac{x−α}{x−β})^{1/p}) : 𝕂′_{0}] = p.

Then ζ^{k}(\frac{x−α}{x−β})^{1/p}μ^{−1/p} ∈ 𝕂′_{0} for some k ∈ P and μ ∈ M. We shall

see that the field 𝕂 = 𝕂_{0} (μ^{1/p} + μ^{−1/p}) is admissible for x. By Lemma 5.1.1 (a)

[𝕂_{0} (ζ^{k}(\frac{x−α}{x−β})^{1/p} + ζ^{−k}(\frac{x−α}{x−β})^{−1/p}) : 𝕂_{0}] = [𝕂: 𝕂_{0}] = p.

If ζ ∉ 𝕂_{0} then by Lemma 5.1.1 (b) we have

𝕂_{0} (ζ^{k}(\frac{x−α}{x−β})^{1/p} + ζ^{−k}(\frac{x−α}{x−β})^{−1/p}) = 𝕂.

If ζ ∈ 𝕂_{0} then by Lemma 5.1.1 (c) the field 𝕂 coincides with one of

the p fields 𝕂_{0} (ζ^{k′}(\frac{x−α}{x−β})^{1/p} + ζ^{−k′}(\frac{x−α}{x−β})^{−1/p}), where k′ ∈ P. The

proposition is proved.

5.3. A fixed admissible field

Fix an admissible field 𝕂 from the complete system constructed in the previous subsection and define m, s, t, and σ_{i} as in the first paragraph of Subsection 4.2. In particular

σ_{i}(γ) = \overline{σ_{i+t}(γ)} (s + 1 ≤ i ≤ s + t)  (97)

for any γ ∈ 𝕂.

Denote by 𝕂′ the composite 𝕂′_{0}𝕂. Then [𝕂′: 𝕂] = 2, and the involution τ : 𝕂′_{0}→𝕂′_{0} (defined in the beginning of the previous section) can be prolonged to the involution of 𝕂′/𝕂, which will be also denoted by τ. (Thus, starting from this point, τ : 𝕂′→𝕂′ is the involution of 𝕂′ satisfying τ|_{𝕂} = id.)

Further, there are exactly two prolongations of σ_{i} to the field 𝕂′. We fix one of them, also denoting it by σ_{i}; then the other is σ_{i}τ. The prolongations can be defined to satisfy (97) also for γ ∈ 𝕂′. Having prolonged σ_{i} to 𝕂′, we can define α_{i} and β_{i} as in the beginning of Subsection 4.2.

We say that a real embedding of 𝕂 is stable if it has real prolongations to 𝕂′, and unstable otherwise. Arrange σ_{i}, …, σ_{s} so that σ_{1}, …, σ_{s′} are stable, while σ_{s′+1}, …, σ_{s} are not. Then we have the following analogue of Proposition 4.2.1 (the proof is immediate).

PROPOSITION 5.3.1. Each stable real embedding of 𝕂_{0} has exactly one real prolongation to 𝕂, (which is stable as well) and \frac{p−1}{2} pairs of complex conjugate prolongations. Each unstable real embedding of 𝕂_{0} has p real prolongation to 𝕂, all of them being unstable. In particular, s′ = s′_{0}, s − s′ = p(s_{0} − s′_{0}) and t = pt_{0} + \frac{p−1}{2}s′_{0}, where s_{0}, s′_{0} and 2t_{0} are the numbers of real, stable real, and complex embeddings of 𝕂_{0}, respectively.

Again, denote by Sol(𝕂) the set of x ∈ Sol such that 𝕂 is admissible for x. For any x ∈ Sol(𝕂) there exists k(x) ∈ P such

that ζ^{k(x)}(\frac{x−α}{x−β})^{1/p} ∈ 𝕂′. Since σ_{i} are prolonged to 𝕂′, the numbers

σ_{i} (ζ^{k(x)}(\frac{x−α}{x−β})^{1/p}) are well-defined. As in the general case, we define

k(x) = (k_{1}(x), …, k_{m}(x)) from the relation (18).

Again, as in the general case, we have (20) and (21). However, (19) should be relaxed as follows:

k_{1}(x) = ⋯ = k_{s′}(x) = 0.  (19′)

As in the general case, it is easy to observe from Proposition 5.3.1 and relations (19′), (20), and (21), that there are at most

(2^{\frac{p−1}{2}} (\frac{p−1}{2})!)^{s′_{0}} (p!)^{t_{0}+s_{0}−s′_{0}} possibilities for k(x).

5.4. Function φ(x), etc.

Define φ(x) as in (22). Though φ(x) is merely in 𝕂′, its square φ^{2}(x) belongs to 𝕂. To see this, notice first of all that

ζ^{k(x)}(\frac{x−α}{x−β})^{1/p} + ζ^{−k(x)}(\frac{x−α}{x−β})^{−1/p} ∈ 𝕂

and

ζ^{k(x)}(\frac{x−α}{x−β})^{1/p} · ζ^{−k(x)}(\frac{x−α}{x−β})^{−1/p} = 1 ∈ 𝕂.

Hence ζ^{k(x)}(\frac{x−α}{x−β})^{1/p} and ζ^{−k(x)}(\frac{x−α}{x−β})^{−1/p} are conjugate over 𝕂, which means that

τ (ζ^{k(x)}(\frac{x−α}{x−β})^{1/p}) = ζ^{−k(x)}(\frac{x−α}{x−β})^{−1/p}.

Therefore

φ^{2}(x) = − (x − β) (ζ^{k(x)}(\frac{x−α}{x−β})^{1/p} − 1)^{p} ×
(x − α) (ζ^{−k(x)}(\frac{x−α}{x−β})^{−1/p} − 1)^{p}
= − φ(x)τ(φ(x)) ∈ 𝕂.

Now we have to repeat the material of Subsections 4.3–4.8, just replacing φ(x) by φ^{2}(x), and modifying accordingly the arguments and the constants. An interested reader can find in Appendix A the complete list of all required changes.

5.5. A final remark

In the case of (α, β)-symmetry one should deal, in the worst situation, with fields of degree \frac{1}{2}pn(n − 1). The following proposition shows that, whether there is (α, β)-symmetry or not, only fields of degree at most \frac{1}{2}pn(n − 1) are to be considered.

PROPOSITION 5.5.1. Let f(x) ∈ ℚ(x) have at least two distinct roots. Then either

(i) there exist two distinct roots α, β of f(x) with (α, β)-symmetry, or

(ii) there exist two distinct roots α, β of f(x) such that [ℚ(α, β): ℚ] ≤ \frac{1}{2}n(n − 1), where n = deg f. Proof. Only the case of irreducible f need to be considered. Let G

be the Galois group of the polynomial f over ℚ. If |G| is even, then there exists an element τ ∈ G of order 2. Since τ ≠ id, there is a root α such that β = τ(α) ≠ α. Since τ^{2} = id, we obtain τ(β) = α, whence we have (i).

Now suppose that |G| is odd. Fix a root α. Then g(x) = f(x)/(x−α) is reducible over ℚ(α); otherwise n(n − 1) would divide |G|, which is impossible. Let now g_{1} be an irreducible over ℚ(α) factor of g of the smallest degree. Then deg g_{1} ≤ \frac{1}{2}(n − 1), and for any root β of g_{1} we have (ii). The proposition is proved.

Thus, in any case multiplicative operations should be performed in fields of degree at most \frac{1}{2}pn(n − 1). In particular cases this bound can be reduced. For example, if f(x) has two symmetric roots, generating the same field over ℚ (as in the examples below), then fields of degree at most \frac{1}{2}pn are to be dealt with.

6. Examples

To illustrate the efficiency of our method, we have completely solved two concrete superelliptic Diophantine equations. The computations were performed by a program written in C, using the PARI/GP programming library, version 1.917. Its listing can be obtained by e-mail from the second author.

6.1. The equation y^{3} = x^{4} − x^{3} − 3x^{2} + x + 1

The roots of f(x) = x^{4} − x^{3} − 3x^{2} + x + 1 are

\frac{1 + \sqrt{5}}{4} ± \frac{1}{2}\sqrt{\frac{11 + \sqrt{5}}{2}}, \frac{1 − \sqrt{5}}{4} ± \frac{1}{2}\sqrt{\frac{11 − \sqrt{5}}{2}}

We take

\begin{aligned}α & = & \frac{1−\sqrt{5}}{4} − \frac{1}{2} \sqrt{\frac{11−\sqrt{5}}{2}} & = & −1.355674 …, \\ β & = & \frac{1−\sqrt{5}}{4} + \frac{1}{2} \sqrt{\frac{11−\sqrt{5}}{2}} & = & 0.737640 … = α^{3} − α^{2} − 3α + 1. \end{aligned}

We have the (α, β)-symmetry, and

𝕂_{0} = ℚ(\sqrt{5}), 𝕂′_{0} = ℚ(α, β) = ℚ(α).
M = {42α^{3} − 102α^{2} + 9α + 32, 23α^{3} − 55α^{2} + 5α + 17, α^{2},
6α^{3} − 10α^{2} + 3, 3α^{3} − 6α^{2} + 2, 2α^{3} − 4α^{2} − α + 2,
α^{3} + 3α^{2} − α − 1, −2α^{3} + 4α^{2} + α − 2,
−12α^{3} + 29α^{2} − 4α − 8}.

A system of fundamental units of 𝕂′_{0} is given by

α^{3} − α^{2} − 2α, α, α^{3} − 2α^{2} − α + 1.

For the admissible fields and data in them see Table II. (We write the fields as ℚ(λ), and express their elements in terms of the generator λ.)

30 Yuri F. Bilu and Guillaume Hanrot

Table II. Admissible fields and data for y^{3} = x^{4} − x^{3} − 3x^{2} + x + 1

minimal poly-  fundamental units  the set Θ_{0}

nomial of λ

λ^{2} − λ − 1 λ 1, λ − 6, 26λ − 11, −141λ + 92,

−λ − 5, 26λ − 15, −141λ + 49

λ^{6} + 6λ^{4} − λ^{3}+  λ^{3} + 3λ, λ,  2λ^{5} + 9λ^{3} − λ^{2} + 12λ − 3,
9λ^{2} − 3λ − 1  λ^{5} + λ^{4} + 6λ^{3}+  λ^{3} + 3λ + 5, −λ^{4} + 2λ + 6
λ^{2} + 10λ − 6  2λ^{5} + 12λ^{3} − λ^{2} + 21λ

λ^{3} + 3λ − 6

λ^{6} − 6λ^{4} − 7λ^{3}+  1/5λ^{3} − 3/5λ − 1/5,  −3/5λ^{5} − 1/5λ^{4} + 12/5λ^{3} + 21/5λ^{2} + 17/5λ − 23/5,
9λ^{2} + 21λ − 19  1/5λ^{4} − 1/5λ^{3} − 3/5λ^{2}−  −1/5λ^{3} + 3/5λ + 31/5,
8/5λ + 11/5,  −2/5λ^{5} − 4/5λ^{4} + 11/5λ^{3} + 29/5λ^{2} + 9/5λ − 13,
1/5λ^{5} + 1/5λ^{4} − 3/5λ^{3}−  1/5λ^{3} − 3/5λ − 31/5, −3/5λ^{5} − λ^{4} + 17/5λ^{3}+
9/5λ^{2} − 1/5λ + 2  43/5λ^{2} + 16/5λ − 48/5, 9λ^{2} + 3/5λ − 52/5,

3/5λ^{5} + 4/5λ^{4} − 16/5λ^{3} − 9λ^{2} − 3/5λ + 52/5, −λ^{5} − 2/5λ^{4} + 23/5λ^{3} + 41/5λ^{2} + 13/5λ − 58/5, −4/5λ^{5} − 2/5λ^{4} + 17/5λ^{3} + 9λ^{2} − 3/5λ − 13, 8/5λ^{5} + 2λ^{4} − 38/5λ^{3} − 98/5λ^{2} − 33/5λ + 154/5, −1/5λ^{5} + λ^{3} + 11/5λ^{2} + 4/5λ + 8/5, 1/5λ^{3} − 3/5λ + 24/5 −1/5λ^{5} − 2/5λ^{4} + 2λ^{3} + 17/5λ^{2} − 14/5λ − 37/5, −λ^{5} − λ^{4} + 22/5λ^{3} + 11λ^{2} + 29/5λ − 77/5, −λ^{5} − 7/5λ^{4} + 23/5λ^{3} + 61/5λ^{2} + 18/5λ − 103/5, −6/5λ^{3} + λ^{2} + 23/5λ − 4/5

λ^{6} − 3λ^{4} − 3λ^{3}−  1/3λ^{5} − 1/3λ^{4} − 2/3λ^{3} − 3λ − 3,  −4/3λ^{5} + 7/3λ^{4} + 2/3λ^{3} + 10λ + 8,
9λ^{2} − 18λ − 9  λ + 1  1/3λ^{5} − 1/3λ^{4} − 2/3λ^{3} − 3λ + 2
1/3λ^{4} − 2/3λ^{3} − λ − 1,  13/3λ^{5} − 11/3λ^{4} − 29/3λ^{3} − 5λ^{2} − 36λ − 52,

1/3λ^{5} − 2/3λ^{4} + λ^{3} − λ^{2} − 4λ − 4, 1/3λ^{5} − 1/3λ^{4} − 2/3λ^{3} − 3λ − 9

λ^{6} + 3λ^{4} − 5λ^{3}−  9/53λ^{5} + 3/53λ^{4} + 28/53λ^{3}−  48/53λ^{5} − 37/53λ^{4} + 114/53λ^{3}−
9λ^{2} + 5  18/53λ^{2} − 87/53λ − 29/53,  255/53λ^{2} − 199/53λ + 128/53,
3/53λ^{5} + 1/53λ^{4} + 27/53λ^{3}−  9/53λ^{5} + 3/53λ^{4} + 28/53λ^{3}−
6/53λ^{2} − 29/53λ + 8/53  18/53λ^{2} − 87/53λ + 289/53,
6/53λ^{5} + 2/53λ^{4} + 1/53λ^{3}−  97/53λ^{5} + 50/53λ^{4} + 396/53λ^{3}−
12/53λ^{2} − 111/53λ + 122/53  247/53λ^{2} − 655/53λ − 554/53,

26/53λ^{5} − 62/53λ^{4} + 128/53λ^{3}− 317/53λ^{2} + 208/53λ + 299/53, −9/53λ^{5} − 3/53λ^{4} − 28/53λ^{3}+ 18/53λ^{2} + 87/53λ + 294/53

We had X_{6} = 295, and (the worst value of) Baker’s bound B_{0} was 6.18 × 10^{29}. After the first reduction we obtained B_{0} ≤ 321, after the second reduction we had B_{0} ≤ 96, and after the final reduction step it was B_{0} ≤ 52 (there were at most 5 reduction steps at each case).

The solutions are (−1, −1), (0, 1), (1, −1), (2, −1). The total computational time on a PC Pentium Pro was 1 minute.

6.2. The equation 28y^{3} = x^{4} − 20x^{2} − 32x + 28

The roots of f(x) = x^{4} − 20x^{2} − 32x + 28 are

2\sqrt{2} ± \sqrt{2 + 2\sqrt{2}}, −2\sqrt{2} ± \sqrt{2 − 2\sqrt{2}}, and we put

α = 2\sqrt{2} − \sqrt{2 + 2\sqrt{2}}, β = 2\sqrt{2} + \sqrt{2 + 2\sqrt{2}}.

We again have the (α, β)-symmetry, and

𝕂_{0} = ℚ(\sqrt{2}), 𝕂′_{0} = ℚ(α, β) = ℚ(α).

Though the set M included 18 elements, there were only 4 admissible fields (together with 𝕂_{0}).

We had X_{6} = 873, and (the worst value of) Baker’s bound B_{0} was 8.29 × 10^{35}. After the first reduction we obtained B_{0} ≤ 233, and after the final reduction step it was B_{0} ≤ 56 (again, there were at most 5 reduction steps at each case).

The solutions are (−2, 1), (0, 1). The computation took 6 minutes on a PC Pentium Pro.

Appendix

A. Modifications for the case of (α, β)-symmetry.

In this appendix we list the changes that should be made in Subsections 4.3–4.8 in the case of (α, β)-symmetry.

1. Replace φ(x) (with and without index) and Φ(x) by φ^{2}(x) (with the same index, if there is any) and Φ^{2}(x), respectively, in the following equations: (23), (30), (31), (32), (34), (49), (50), (54), (64), (65), (67), (69), (72) and everywhere in Appendix D.

2. Modify u_{1}(𝔭) and u_{2}(𝔭) (see (24–25)) as follows: u_{1}(𝔭) = max(0, −Ord_{𝔭}(αβ)) and u_{2}(𝔭) = max (0, Ord_{𝔭} ((α − β)^{2})).

3. In (32) and (33) replace (β − α)^{p} by (β − α)^{2p}.

4. Modify δ_{i} and λ_{i} (see (41)) as follows: δ_{i} = 2 ∑_{j=1}^{r} a_{ij}ρ_{i} and λ_{i} = ∑_{j=1}^{r} (a_{ij} log |γ_{j}^{2}θ_{j}^{−1}|). Modify the right-hand side of (51) accordingly.

5. Modify the following constants:

c_{10} = 2c_{7} max_{1≤j≤r} ∑_{j=1}^{r}|a_{ij}|, c_{14} = max (1 + 2π^{−1}c_{12} + rc_{9}, e) ,

c_{16} = 2c_{13}c_{12} + c_{14},

X_{4} = max (X_{2}, 3mc_{7}, e^{1/(3|ρ′|)} |γ_{1} ⋯ γ_{m}|^{−1/ρ′} |θ_{1} ⋯ θ_{m}|^{1/(2ρ′)}) .

6. In Subsections 4.5 it suffices now to assume that [𝕂: ℚ] ≥ 2. To explain this point, recall that the assumption [𝕂: ℚ] ≥ 3 was required only when 𝕂 = 𝕂_{0}, to guarantee the existence of i_{1} and i_{2} such that among the numbers (62) there are at least three distinct. In the case of (α, β)-symmetry, it is enough to have [𝕂_{0} : ℚ] ≥ 2, because for any two distinct i_{1} and i_{2}, there at least three distinct among the numbers (62). (Otherwise it would be either α_{i_{1}} = β_{i_{1}} and α_{i_{2}} = β_{i_{2}}, or α_{i_{1}} = β_{i_{2}} and α_{i_{2}} = β_{i_{1}}. In both the cases α_{i_{1}} + α_{i_{2}} = β_{i_{1}} + β_{i_{2}} and α_{i_{1}}α_{i_{2}} = β_{i_{1}}β_{i_{2}}, which means that σ_{i_{1}} = σ_{i_{2}}.)

7. Modify ϑ_{0} (see (68)) as follows: ϑ_{0} = (γ_{i_{2}}^{2ρ_{i_{1}}} θ_{i_{1}}^{ρ_{i_{2}}} )/(γ_{i_{1}}^{2ρ_{i_{2}}} θ_{i_{2}}^{ρ_{i_{1}}} ).

8. Replace c_{12} by 2c_{12} in (70), (71), (73), (75) and everywhere in Appendix D.

9. Rewrite (94) as

ω_{i} := ±γ_{i}^{−1} (θ_{i}η_{i1}^{b_{1}} ⋯ η_{ir}^{b_{r}})^{1/2} − γ′_{i}.  (98)

(Now there are two possibilities for ω_{i}, both being to be considered.)

10. In Step 1 of the algorithm, replace the reference to Subsection 4.1 by Subsection 5.2.

B. On the number of possibilities for the vector k(x)

When the number of μ ∈ M such that 𝕂_{0} (μ^{1/p}) ≅ 𝕂 (or 𝕂_{0} (μ^{1/p} + μ^{−1/p}) ≅ 𝕂 in the case of (α, β)-symmetry) is not too large, one can reduce the number of possible k(x). For brevity, we consider only the general case.

Fix μ ∈ M such that 𝕂_{0} (μ^{1/p}) ≅ 𝕂. Then 𝕂_{0} (ζ^{κ}μ^{1/p}) = 𝕂 for some κ ∈ P. Put μ_{i} = σ_{i}(μ) and define l_{i} ∈ P from the equality σ_{i} (ζ^{κ}μ^{1/p}) = ζ^{l_{i}}μ_{i}^{1/p}.

Consider x ∈ Sol(𝕂) such that

ζ^{k}(\frac{x−α}{x−β})^{1/p}μ^{−1/p} ∈ 𝕂_{0} for some k ∈ P.  (99)

It follows that

ζ^{k(x)}(\frac{x−α}{x−β})^{1/p}ζ^{−κ}μ^{−1/p} ∈ 𝕂_{0}.  (100)

Indeed, since both ζ^{k(x)}(\frac{x−α}{x−β})^{1/p} and ζ^{κ}μ^{1/p} belong to 𝕂, we have

ζ^{k(x)}(\frac{x−α}{x−β})^{1/p}ζ^{−κ}μ^{−1/p} ∈ 𝕂.  (101)

Therefore ζ^{k−k(x)+κ} ∈ 𝕂, where k is defined from (99). It follows that the degree of ζ^{k−k(x)+κ} over 𝕂_{0} divides p. Since it also divides p − 1, the degree is 1, that is ζ^{k−k(x)+κ} ∈ 𝕂_{0}. Together with (99) this proves (100).

PROPOSITION B.1. Suppose that σ_{i}|_{𝕂_{0}} = σ_{i′} |_{𝕂_{0}} , that is α_{i} = α_{i′} and β_{i} = β_{i′}. Then for any x ∈ Sol(𝕂) with the property (99) we have

k_{i}(x) − k_{i′}(x) ≡ l_{i} − l_{i′} (mod p).  (102)

Proof. Put

λ = ζ^{k(x)}(\frac{x−α}{x−β})^{1/p}ζ^{−κ}μ^{−1/p}, λ_{i} = σ_{i}(λ).

Since λ and μ belong to 𝕂_{0}, we have λ_{i} = λ_{i′} and μ_{i} = μ_{i′}. Therefore

ζ^{k_{i}(x)}(\frac{x−α_{i}}{x−β_{i}} )^{1/p} = ζ^{l_{i}}μ_{i}^{1/p}λ_{i}
= ζ^{l_{i}−l_{i′}} ζ^{l_{i′}} μ_{i′}^{1/p}λ_{i′}
= ζ^{l_{i}−l_{i′}} ζ^{k_{i′} (x)}(\frac{x−α_{i′}}{x−β_{i′}} )^{1/p}
= ζ^{l_{i}−l_{i′}} ζ^{k_{i′} (x)}(\frac{x−α_{i}}{x−β_{i}} )^{1/p},

which proves the proposition.

Given a value of k_{i}(x) for some i, the condition (102) defines uniquely k_{i′}(x) for the p values of i′ satisfying σ_{i}|_{𝕂_{0}} = σ_{i′} |_{𝕂_{0}} . Together with (19) and (20) this leaves p^{t_{0}} possibilities for k(x), where 2t_{0} is the number of complex embeddings of 𝕂_{0}. Therefore there are at most

p^{t_{0}} |{μ ∈ M : 𝕂_{0} (μ^{1/p}) ≅ 𝕂}|  (103)

possibilities for k(x). In some cases this number can be smaller than

(2^{\frac{p−1}{2}} (\frac{p−1}{2})!)^{s_{0}} (p!)^{t_{0}}.

C. Solving the equation Φ(x) = 1

In Subsection 4.5 the equation Φ(x) = 1 had to be solved (in the case of (α, β)- symmetry it should be replaced by Φ(x) = ±1.) In the case [𝕂: 𝕂_{0}] = p ≥ 3 both k_{i_{1}} and k_{i_{2}} are non-zero. Therefore ρ_{i_{1}} = ρ_{i_{2}} = 1, and the equation Φ(x) = ±1 can be rewritten as

ζ_{i_{1}} (1 − α_{i_{1}}x^{−1})^{1/p} − (1 − β_{i_{1}}x^{−1})^{1/p} =
const · (ζ_{i_{2}} (1 − α_{i_{1}}x^{−1})^{1/p} − (1 − β_{i_{1}}x^{−1})^{1/p}) ,

which can be easily reduced to a linear equation in x.

In the case 𝕂 = 𝕂_{0} we need the following lemma, which is an immediate consequence of Kummer’s theory [12, Ch. 6, Th. 8.1] over the field ℂ(T).

LEMMA C.1. Let ς_{1}, …, ς_{ν} be distinct non-zero complex numbers and

F (T, T_{1}, …, T_{ν}) ∈ ℂ[T, T_{1}, …, T_{ν}]

a non-zero polynomial such that

F (T, (1 − ς_{1}T)^{1/p} , …, (1 − ς_{ν}T)^{1/p}) ≡ 0.

Then deg_{T_{i}} F ≥ p for 1 ≤ i ≤ ν.

Using this lemma we can prove that the function Φ(x) is non-constant. Indeed, if Φ(x) were a constant, then, depending on whether ρ_{i_{1}} and ρ_{i_{2}} are equal or distinct, we would have obtained one of the following identities: either

\begin{matrix}ζ_{i_{1}} (1 − α_{i_{1}}x^{−1})^{1/p} − (1 − β_{i_{1}}x^{−1})^{1/p} = \\ const (ζ_{i_{2}} (1 − α_{i_{2}}x^{−1})^{1/p} − (1 − β_{i_{2}}x^{−1})^{1/p}) , \end{matrix}  (104)

or

\begin{matrix}x (ζ_{i_{1}} (1 − α_{i_{1}}x^{−1})^{1/p} − (1 − β_{i_{1}}x^{−1})^{1/p}) × \\ (ζ_{i_{2}} (1 − α_{i_{2}}x^{−1})^{1/p} − (1 − β_{i_{2}}x^{−1})^{1/p})^{p−1} = ct. \end{matrix}  (105)

(We used (48), which holds for sufficiently large x, and in the case of distinct ρ_{i_{1}} and ρ_{i_{2}} we assumed that ρ_{i_{1}} = 1 and ρ_{i_{2}} = 1 − p.) Since among the radicals there are at least three distinct, both (104) and (105) contradict to the assertion of Lemma C.1. Therefore Φ(x) is non-constant.

We solve the equation Φ(x) = 1 in the following way. Let K be the field generated over ℂ(x) by the radicals involved in Φ(x). Then N_{K/ℂ(x)} (Φ(x) − 1) is rational function in x, and we write it as P (x)/Q(x). Since Φ(x) is non-constant, the polynomial P (x) is non-zero, and all the solutions of Φ(x) = 1 are among the roots of P (x).

Thus, finding integral solutions of the algebraic equation (64) reduces to finding integral roots of a polynomial P (x). In practice, the coefficients of P (x) are known approximately, and we had to estimate the precision of the roots. (Since we were interested only in integral roots, we did not need very high precision.) The following lemma was used for estimating the precision.

LEMMA C.2. Let P (x) = a_{0}x^{N} + a_{1}x^{N−1} + … + a_{N} and Q(x) = b_{0}x^{N} + b_{1}x^{N−1} + … + b_{N} be polynomials with complex coefficients. Let ε be a positive number with the following property:

(∗) for any two roots z and z′ of Q one has either |z − z′| ≤ ε/2 or |z − z′| ≥ 2ε.

Put

δ = δ(ε) = min_{1≤i≤N} \frac{|b_{0}| ∏_{j=1}^{N} ||z_{j} − z_{i}| − ε|}{∑_{j=0}^{N}(|z_{i}| + ε)^{j}} ,  (106)

where z_{1}, …, z_{N} are the roots of Q counted with multiplicities. Assume that

|a_{i} − b_{i}| < δ (0 ≤ i ≤ N).

Then for any root z of P there is a root z′ of Q such that |z − z′| < ε.

(It will follow from the proof that there is a one-to-one correspondence z ↔ z′ between the roots of P and the roots of Q such that |z − z′| < ε for every pair of corresponding roots.)

Proof. Define an equivalence relation on the set of roots of Q by z ∼ z′ when |z − z′| ≤ ε/2 (transitivity follows from (∗)). Let m_{1}, …, m_{k} be the cardinalities of the the equivalence classes (so that m_{1} + ⋯ + m_{k} = N), and assume that the roots are numbered so that z_{1}, …, z_{k} are respective representatives of the classes. In particular,

|z_{i} − z_{j}| ≥ 2ε (1 ≤ i < j ≤ k).  (107)

Fix i with 1 ≤ i ≤ k. Then Q has m_{i} roots in the disc Δ_{i} := {z ∈ ℂ: |z − z_{i}| < ε}. For any z on the circle Γ_{i} := {z ∈ ℂ: |z − z_{i}| = ε} one has

|Q(z)| = |b_{0}(z − z_{1}) … (z − z_{N})| ≥ |b_{0}| ∏_{j=1}^{N} ||z_{j} − z_{i}| − ε| .

Hence, for any z ∈ Γ_{i}

|P (z) − Q(z)| < δ ∑_{j=0}^{N}(|z_{i}| + ε)^{j} ≤ |Q(z)|.

By the theorem of Rouché, P also has m_{i} roots in Δ_{i}.

By (107), the discs Δ_{i} are pairwise disjoint. Since m_{1} +⋯+m_{k} = N, every root of P belongs to one of Δ_{i}. The lemma is proved.

We apply this lemma as follows. Assume we have to find all integral roots of a polynomial P (x), but instead of P, we have only an approximation Q(x), with a known precision δ_{0} (that is, max_{i=0,..., N} |a_{i} − b_{i}| ≤ δ_{0}). Having computed the roots of Q(x), one can easily decide which integers are “very close” to a root of Q(x). This integers (we call them suspicious) are probable roots of P (x).

To see that P (x) has no integral roots other than suspicious, we do as follows. For any z ∈ C denote by ρ(z) the distance to the nearest non-suspicious integer, and put ε_{0} = 0.1 min(ρ(z_{1}), …, ρ(z_{N})). If ε_{0} meets the condition (∗), we put ε = ε_{0}; otherwise put ε_{1} = 0.1 min_{|z−z′|≥ε_{0}} |z − z′|, where z and z′ independently run the set of all roots of Q. If ε_{1} meets the condition (∗), we put ε = ε_{1}; otherwise put ε_{2} = 0.1 min_{|z−z′|≥ε_{1}} |z − z′|, etc.; in practice, we always found a suitable ε after two–three iterations. When ε is found, compute δ; if δ > δ_{0} then P (x) indeed has no integral roots other than suspicious. If δ ≤ δ_{0} (which never happened in our practice) then one has to recompute Q with higher precision.

D. The totally rational case

In this appendix in we a detailed treatment of the totally rational case, see Subsection 4.6.1.

We have

δ_{j_{1}}^{−1}δ_{j} = q_{j}/q, δ_{j_{1}}^{−1} (δ_{j}λ_{j_{1}} − δ_{j_{1}}λ_{j}) = q′_{j}/q (1 ≤ j ≤ r),  (108)

where q is a positive integer, q_{j}, q′_{j} integers, and gcd(q_{1}, …, q_{r}, q) = 1. (To simplify the notation, we do not exclude j = j_{1}, in which case q_{j} = q and q′_{j} = 0.) As in the semirational case, we expect that the integers q_{j}, q′_{j} and q are “small”.

Replacing in (77) index j_{2} by j, and using (108), we obtain

|qb_{j}(x) − q_{j}b_{j_{1}}(x) + q′_{j} | ≤ 2qc_{10}|x|^{−1} (1 ≤ j ≤ r).  (109)

If |x| > X_{7} : max(X_{3}, 4qc_{10}) then (109) turns to

qb_{j}(x) − q_{j}b_{j_{1}}(x) + q′_{j} = 0 (1 ≤ j ≤ r).  (110)

If gcd(q, q_{j}) does not divide q′_{j} for some j then there are no solutions x with |x| > X_{7}. Otherwise, one easily finds integers b_{1}, …, b_{r} such that

qb_{j} − q_{j}b_{j_{1}} + q′_{j} = 0 (1 ≤ j ≤ r).  (111)

Then

b_{j}(x) = b_{j} + q_{j}b(x) (1 ≤ j ≤ r),  (112)

where b(x) ∈ ℤ. Substituting this to (67), we obtain

Φ(x) = ϑ′_{0}ϑ^{b(x)},  (113)

where

ϑ′_{0} = ϑ_{0}ϑ_{1}^{b_{1}} ⋯ ϑ_{r}^{b_{r}} , ϑ = ϑ_{1}^{q_{1}} ⋯ ϑ_{r}^{q_{r}} .

The further arguments splits into five cases.

1. |ϑ| ≠ 1 In this case (113), together with (66), yields

|log |ϑ′_{0}| + b(x) log |ϑ|| ≤ c_{12}|x|^{−1}.  (114)

Hence b(x) is the nearest integer to − log |ϑ′_{0}|/ log |ϑ| whenever |x| > X_{8} := max(X_{7}, 2c_{12}).

2. |ϑ| = 1, but |ϑ′_{0}| ≠ 1 We again have (114), which now reduces to

|log |ϑ′_{0}|| ≤ c_{12}|x|^{−1}.  (115)

Thus, |x| ≤ X_{8} := max (X_{7}, c_{12} |log |ϑ′_{0}||^{−1}).

3. |ϑ| = |ϑ′_{0}| = 1, but ϑ is not a root of unity Again using (113) and (66), we obtain

∥(2π)^{−1} arg ϑ′_{0} + (2π)^{−1} arg ϑb(x)∥ ≤ (2π)^{−1}c_{12}|x|^{−1},  (116)

and we continue as in the irrational (respectively, semirational) case if 2π, arg ϑ and arg ϑ′_{0} are linearly independent (respectively, linearly dependent) over ℤ.

4. ϑ is a primitive N-th root of unity and |ϑ′_{0}| = 1, but ϑ′_{0} is not an N-th root of unity We have

∥N(2π)^{−1} arg ϑ′_{0}∥ ≤ N(2π)^{−1}c_{12}|x|^{−1},  (117)

and since the left-hand side is non-zero, we obtain

|x| ≤ X_{8} := max (X_{7}, N(2π)^{−1}c_{12} ∥N(2π)^{−1} arg ϑ′_{0}∥^{−1}) .

5. ϑ is a primitive N-th root of unity and ϑ′_{0} is an N-th root of unity In this case Φ(x) is also an N-th root of unity. Since Φ(x) ≠ 1, we obtain | log Φ(x)| ≥ 2π/N. Hence |x| ≤ X_{8} := max(X_{7}, N(2π)^{−1}c_{12}).

E. The hyperelliptic equation

In this appendix we briefly explain how our method can be adapted for solving the hyperelliptic equation y^{2} = f(x), where f(x) is a separable polynomial of degree at least 3. (Probably, it would be more correct to call it elliptic equation when deg f ≤ 4; for brevity, we extend the term hyperelliptic also to this case.) What follows is merely a short draft, and many details are left out. In particular, we make no use in possible symmetry of the roots. For examples and generalization of (α, β)-symmetry to that case, see [11].

Again, fix two distinct roots α and β of f(x), and assume first that [ℚ(α, β) : ℚ] ≥ 3. It is easy to see that in this case the method of Section 4 extends also to p = 2. Indeed, the assumption p ≥ 3 was made in Section 4 only twice: in Proposition 4.2.1, and in Subsection 4.5. We leave to the reader the reformulation of Proposition 4.2.1 for p = 2. As for Subsection 4.5, it is indeed impossible to satisfy (60)–(61) when p = 2. However, since [ℚ(α, β) : ℚ] ≥ 3, we can always find i_{1} and i_{2} such that among the numbers (62) there are at least three distinct, which allows one to compute the Baker’s bound.

It remains to consider the case [ℚ(α, β) : ℚ] ≤ 2. Fix one more root γ, distinct from α and β. We may assume that [ℚ(α, γ) : ℚ] ≤ 2 and [ℚ(γ, β) : ℚ] ≤ 2; otherwise, redefining the roots, we return to the case [ℚ(α, β) : ℚ] ≥ 3.

It follows that [ℚ(α, β, γ) : ℚ] ≤ 2. Redefining the roots, we can additionally assume that

(i) either α, β, γ ∈ ℚ, (ii) or α and β are quadratic conjugates over ℚ, and γ ∈ ℚ(α). Case (i) is very simple: it can be reduced to two simultaneous Pell equations, see for instance [33]. In case (ii) put 𝕂_{0} = ℚ(α), and say that a number field 𝕂 is

admissible for a solution x if 𝕂 = 𝕂_{0} ((\frac{x−α}{x−γ})^{1/2}). One easily constructs a complete

system of admissible fields, which would consist of 𝕂_{0} and a finite amount of its quadratic extensions.

Now fix an admissible field 𝕂 and put φ(x) = (x − γ) ((\frac{x−α}{x−γ})^{1/2} + 1)^{2}. Then

we again have (34), where θ(x) belongs to a finite effectively constructible set. If 𝕂 = 𝕂_{0} then we have finitely many possible values for φ(x)σ(φ(x)), where

σ is the non-trivial automorphism of 𝕂_{0}. However, σ ((\frac{x−α}{x−γ})^{1/2}) = ± (\frac{x−β}{x−γ′} )^{1/2},

where γ′ = σ(γ). Using Kummer’s theory, as in Appendix C, we observe that

φ(x)σ(φ(x)) = (x − γ) ((\frac{x − α}{x − γ})^{1/2} + 1)^{2} (x − γ′) (± (\frac{x − β}{x − γ′} )^{1/2} + 1)^{2}

is a non-constant function of x, which allows one to compute the set Sol(𝕂_{0}). If [𝕂: 𝕂_{0}] = 2, then, putting

Φ(x) = \frac{(x − γ) ((\frac{x−α}{x−γ})^{1/2} + 1)^{2}}{(x − γ′) ((\frac{x−β}{x−γ′} )^{1/2} + 1)^{2}} ,

one can compute the Baker’s bound and proceed further as in Section 4. See [31, 32] for a similar algorithm in the case deg f = 3.

References

1. A. Baker, Linear forms in the logarithms of algebraic numbers I, Mathematica 13 (1966), 204–216; II, ibid. 14 (1967), 102–107; III, ibid. 14 (1967), 220–228; IV, ibid. 15 (1968), 204–216.

2. A. Baker, Bounds for the solutions of the hyperelliptic equations, Proc. Camb. Phil. Soc. 65 (1969), 439–444.

3. A. Baker, H. Davenport, The equations 3x^{2} − 2 = y^{2} and 8x^{2} − 7 = z^{2}, Quat. J. Math. Oxford (2) 20 (1969), 129–137.

4. A. Baker and G. Wüstholz, Logarithmic forms and group varieties, J. Reine Angew. Math. 442 (1993), 19–62.

5. Yu. Bilu, Effective analysis of integral points on algebraic curves, Israel J. of Math., 90 (1995), 235–252.

6. Yu. Bilu, Solving superelliptic Diophantine equations by the method of Gelfond–Baker, preprint 94–09, Mathématiques Stochastiques, Univ. Bordeaux 2, 1994.

7. Yu. Bilu, Quantitative Siegel’s theorem for Galois coverings, Compositio Math., to appear.

8. Yu. Bilu, G. Hanrot, Solving Thue equations of high degree, J. Number Th. 60 (1996), 373–392.

9. B. Brindza, On S-integral solutions of the equation y^{m} = f(x), Acta Math. Hungar. 44 (1984), 133–139.

10. H. Cohen, A Course in Computational Algebraic Number Theory, Graduate Texts in Math. 138, Springer, 1993.

11. G. Hanrot, Résolution effective d’équations diophantiennes : algorithmes et applications, Thèse, Université Bordeaux 1, 1997.

12. S. Lang, Algebra, Third Edition, Addison-Wesley, 1993.

13. A.K. Lenstra, H.W. Lenstra jr., L. Lovász, Factoring polynomials with rational coefficients, Math. Ann. 261 (1982), 515–534.

14. M. Mignotte, A. Pethö, Sur les carrés dans certaines suites de Lucas, J. Th. Nombr. Bordeaux 5 (1993), 333–341.

15. M. Mignotte, A. Pethö, On the system of diophantine equations x^{2} −6y^{2} = −5 and x = 2z^{2} − 1, Math. Scand., 76 (1995), 50–60.

16. M. Mignotte, B.M.M. de Weger, On the Diophantine equations x^{2} + 74 = y^{5} and x^{2} + 86 = y^{5}, Glasgow Math. J., 38 (1996).

17. A. Pethö, Computational Methods For the Resolution of Diophantine Equations, in R.A. Mollin (ed.), Number Theory: Proc. First Conf. Can. Number Th. Ass., Banff, 1988, de Gruyter, 1990, 477–492.

18. A. Pethö, B.M.M. de Weger, Products of Prime powers in Binary Recurrence Sequences Part I: The Hyperbolic Case, with an Application to the Generalized Ramanujan–Nagell Equation, Math. Comp. 47 (1987), 713–727.

19. M.E. Pohst, Computational Algebraic Number Theory, DMV Seminar, Vol. 21, Birkhäuser, Basel, 1993.

20. M.E. Pohst, H. Zassenhaus, Algorithmic Algebraic Number Theory, Cambridge Univ. Press, 1989.

21. D. Poulakis, Solutions entières de l’équation Y^{m} = f(x). Sém. Th. Nombr. Bordeaux 3 (1991), 187–199.

22. T.N. Shorey, R. Tijdeman, Exponential Diophantine equations, Cambridge Univ. Press, Cambridge, 1986.

23. N. Smart, The solution of triangularly connected decomposable form equation, Math. Comp. 64 (1995), 819–840.

24. V.G. Sprindžuk, The arithmetic structure of integral polynomials and class numbers (Russian), Trudy Mat. Inst. Steklov 143 (1977), 152–174; English transl.: Proc. Steklov Inst. Math. 1980, issue 1, 163–186.

25. V.G. Sprindžuk, Classical Diophantine Equations in Two Unknowns (Russian), Nauka, Moscow, 1982; English trans.: Lecture Notes in Math. 1559, Springer, 1994.

26. L.A. Trelina, On S-integral solutions of the hyperelliptic equation (Russian), Dokl. Akad. Nauk BSSR 22 (1978), 881–884.

27. N. Tzanakis, B. M. M. de Weger, On the Practical Solution of the Thue Equation, J. Number Th. 31 (1989), 99–132.

28. N. Tzanakis, B.M.M. de Weger, How to explicitly solve a Thue–Mahler Equation, Compositio Math. 84 (1992), 223–288.

29. P.M. Voutier, An Upper Bound for the Size of Integral Solutions to Y^{m} = f(X), J. Number Theory, 53 (1995), 247–271.

30. B.M.M. de Weger, Solving exponential diophantine equations using lattice basis reduction algorithms, J. Number Th. 26 (1987), 325–367.

31. B.M.M. de Weger, Integral and S-integral solutions of a Weierstrass equation, report 9452/B, Econometric Inst., Erasmus Univ., Rotterdam, 1994.

32. B.M.M. de Weger, Solving elliptic Diophantine equations by Bilu’s method, report 9469/B, Econometric Inst., Erasmus Univ., Rotterdam, 1994.

33. D. Zagier, Large integral points on elliptic curves, Math. Comp. 48 (1987), 425–436.