# Efficient Resolution of Thue–Mahler Equations

Adela Gherga<EMAIL_ADDRESS>Mathematics Institute, University of
Warwick, Coventry CV4 7AL, United Kingdom  and  Samir Siksek
<EMAIL_ADDRESS>Mathematics Institute, University of Warwick, Coventry
CV4 7AL, United Kingdom

###### Abstract.

A Thue-Mahler equation is a Diophantine equation of the form

$F(X,Y)=a\cdot p_{1}^{z_{1}}\cdots p_{v}^{z_{v}},\qquad\gcd(X,Y)=1$

where $F$ be an irreducible homogeneous binary form of degree at least $3$
with integer coefficients, $a$ is a non-zero integer and $p_{1},\dots,p_{v}$
are rational primes. Existing algorithms for resolving such equations require
computations in the field
$L=\mathbb{Q}(\theta,\theta^{\prime},\theta^{\prime\prime})$, where $\theta$,
$\theta^{\prime}$, $\theta^{\prime\prime}$ are distinct roots of $F(X,1)=0$.
We give a new algorithm that requires computations only in
$K=\mathbb{Q}(\theta)$ making it far more suited for higher degree examples.
We also introduce a lattice sieving technique reminiscent of the Mordell–Weil
sieve that makes it practical to tackle Thue–Mahler equations of higher degree
and with larger sets of primes. We give several examples including one of
degree $11$.

Let $P(m)$ denote the largest prime divisor of an integer $m\geq 2$. As an
application of our algorithm we determine all pairs $(X,Y)$ of coprime non-
negative integers such that $P(X^{4}-2Y^{4})\leq 100$, finding that there are
precisely $49$ such pairs.

###### Key words and phrases:

Thue equation, Thue–Mahler equation, LLL, linear form in logarithms

###### 2020 Mathematics Subject Classification:

Primary 11D59, Secondary 11D61

The authors are supported by the EPSRC grant _Moduli of Elliptic curves and
Classical Diophantine Problems_ (EP/S031537/1).

##  1\. Introduction

Let

$F(X,Y)=a_{0}X^{d}+a_{1}X^{d-1}Y+\cdots+a_{d}Y^{d}$ (1)

be a homogeneous binary form of degree $d\geq 3$ with coefficients
$a_{i}\in\mathbb{Z}$. Suppose $F$ is irreducible. Let $a$ be a non-zero
integer and let $p_{1},\dotsc,p_{v}$ be distinct primes such that $p_{i}\nmid
a$. The purpose of this paper is to give an efficient algorithm to solve the
Thue–Mahler equation

$F(X,Y)=a\cdot p_{1}^{z_{1}}\cdots p_{v}^{z_{v}},\qquad
X,~{}Y\in\mathbb{Z},\;\gcd(X,Y)=1,$ (2)

for unknown integers $X,Y$, and unknown non-negative integers
$z_{1},\dots,z_{v}$. The set of solutions is known to be finite by a famous
result of Mahler [25] which extends classical work of Thue [29]. Mahler’s
theorem is ineffective. The first effective bounds on the size of the
solutions are due to Vinogradov and Sprindžuk [31] and to Coates [17]. Vastly
improved effective bounds have since been given by Bugeaud and Győry [12].
Evertse [19, Corollary 2] showed that the number of solutions to (2) is at
most $2\times 7^{d^{3}(2v+3)}$. For $d\geq 6$, this has been improved by
Bombieri [8, Main Theorem] who showed that the number of solutions is at most
$16v^{2}\cdot(4d)^{26v}$.

Besides being of independent interest, Thue–Mahler equations frequently arise
in a number of contexts:

  * •

The problem of determining all elliptic curves over $\mathbb{Q}$ with good
reduction outside a given set of primes algorithmically reduces to the problem
of solving certain cubic Thue–Mahler equations (here cubic means $d=3$). The
earliest example appears to be due to Agrawal, Coates, Hunt, and van der
Poorten [1] who used it to determine all elliptic curves over $\mathbb{Q}$ of
conductor $11$. The recent paper of Bennett, Gherga and Rechnitzer [5] gives a
systematic and general treatment of this approach. In fact, the link between
cubic Thue–Mahler equations and elliptic curves can be used in conjunction
with modularity of elliptic curves to give an algorithm for solving cubic
Thue–Mahler equations as in the work of von Känel and Matschke [32, Section 5]
and of Kim [23].

  * •

Many Diophantine problems naturally reduce to the resolution of Thue–Mahler
equations. These include the Lebesgue–Nagell equations (e.g. [16], [28]), and
Goormaghtigh’s equation (e.g. [3]). The most striking of such applications is
the reduction, due to Bennett and Dahmen [2], of asymptotic cubic
superelliptic equations to cubic Thue–Mahler equations, via the modularity of
Galois representation attached to elliptic curves.

Before the current paper, the only general algorithm for solving Thue–Mahler
equations was the one due to Tzanakis and de Weger [30]. A modern
implementation of this algorithm, due Hambrook [22], has been profitably used
to solve a number of low degree Thue–Mahler equations, for example in [16],
[28].

Instead of (2), we consider the equation

$F(X,Y)=a\cdot p_{1}^{z_{1}}\cdots p_{v}^{z_{v}},\qquad
X,~{}Y\in\mathbb{Z},\;\gcd(X,Y)=\gcd(a_{0},Y)=1.$ (3)

Thus we have added the assumption $\gcd(a_{0},Y)=1$, where $a_{0}$ is the
leading coefficient of $F$ as in (1). This is a standard computational
simplification in the subject, and is also applied by Tzanakis and de Weger.
There is no loss of generality in adding this assumption in the following
sense: an algorithm for solving (3) yields an algorithm for solving (2). To
see this, let $(X,Y)$ be a solution to (2) and let Let $b=\gcd(a_{0},Y)$.
Write $Y=bY^{\prime}$ with $Y^{\prime}\in\mathbb{Z}$. The possible values for
$b$ are the divisors of $a_{0}$; for each divisor $b$ we need to solve
$F(X,bY^{\prime})=a\cdot p_{1}^{z_{1}}\cdots p_{v}^{z_{v}}$. Note that
$F(X,bY^{\prime})=bG(X,Y^{\prime})$ where $G$ has integral coefficients and
leading coefficient $a_{0}^{\prime}=a_{0}/b$, which satisfies
$\gcd(a_{0}^{\prime},Y^{\prime})=1$. The equation $bG(X,Y^{\prime})=a\cdot
p_{1}^{z_{1}}\cdots p_{v}^{z_{v}}$ is impossible unless
$b/\gcd(a,b)=p_{1}^{w_{1}}\cdots p_{v}^{w_{v}}$ where $w_{i}\geq 0$, in which
case

$G(X,Y^{\prime})=(a/\gcd(a,b))\cdot p_{1}^{z_{1}-w_{1}}\cdots
p_{v}^{z_{v}-w_{v}}$

which is now a Thue–Mahler equation of the form (3).

The approach of Tzanakis and de Weger breaks down into a number of steps.

  1. (I)

First (3) is reduced to a number of ideal equations:

$(a_{0}X-\theta
Y){\mathcal{O}}_{K}=\mathfrak{a}\cdot\mathfrak{p}_{1}^{n_{1}}\cdots\mathfrak{p}_{s}^{n_{s}}.$
(4)

Here $\theta$ is a root of the monic polynomial $a_{0}^{d-1}F(X/a_{0},1)$, and
$K=\mathbb{Q}(\theta)$. Moreover, $\mathfrak{a}$ is a fixed prime ideal of the
ring of integers ${\mathcal{O}}_{K}$, and
$\mathfrak{p}_{1},\dotsc,\mathfrak{p}_{s}$ are fixed prime ideals of
${\mathcal{O}}_{K}$. The variables $X$, $Y$, $n_{1},\dotsc,n_{s}$ represent
the unknowns.

  2. (II)

Next, each ideal equation (4) is reduced to a number of equations of the form

$a_{0}X-\theta Y=\tau\cdot\delta_{1}^{b_{1}}\cdots\delta_{r}^{b_{r}}$ (5)

where $\tau$, $\delta_{1},\cdots,\delta_{r}\in K^{\times}$ are fixed and $X$,
$Y$, $b_{1},\dotsc,b_{r}$ are unknowns.

  3. (III)

The next step generates a very large upper bound for the exponents
$b_{1},\dotsc,b_{r}$ using the theory of real, complex, and $p$-adic linear
forms in logarithms. This bound is then considerably reduced using the LLL
algorithm [24] applied to approximation lattices associated to these linear
forms, and finally, all solutions below this reduced bound are found using the
algorithm of Fincke and Pohst [20].

To compute these approximation lattices alluded to in step (III), the
algorithm of Tzanakis and de Weger relies on extensive computations in the
number field $K^{\prime}=\mathbb{Q}(\theta_{1},\theta_{2},\theta_{3})$ where
$\theta_{1}$, $\theta_{2}$, $\theta_{3}$ are distinct roots of
$a_{0}^{d-1}F(X/a_{0},1)$, as well as $\mathfrak{p}$-adic completions of
$K^{\prime}$. The field $K^{\prime}$ typically has degree $d(d-1)(d-2)$,
making their algorithm impractical if the degree $d$ is large. Even if the
degree $d$ is small (say $d=3$), we have found that the Tzanakis-de Weger
algorithm runs into a combinatorial explosion of cases in step (I) if the
number of primes $v$ is large, and in step (II) if the class number $h$ of $K$
is large.

In this paper, we present an algorithm that builds on many of the powerful
ideas in the paper of Tzanakis and de Weger but avoids computations in number
fields other than the field $K=\mathbb{Q}(\theta)$ of degree $d$, and avoids
all computations in $p$-adic fields or their extensions. The algorithm
includes a number of refinements that circumvent the explosion of cases in
steps (I) and (II). For example, to each ideal equation (4) we associate at
most one equation (5); by contrast, the algorithm of Tzanakis and de Weger,
typically associates $h^{s-1}$ equations (5) to each ideal equation (4), where
$h$ is the class number of $K$. Moreover, inspired by the Mordell–Weil sieve
(e.g. [10], [11], [15]), we introduce a powerful “Dirichlet sieve” that vastly
improves the determination of the solutions to (5) after the LLL step, even if
the remaining bound on the exponents $b_{i}$ is large.

We have implemented the algorithm described in this paper in the computer
algebra system Magma [9]; our implementation is available from
https://github.com/adelagherga/ThueMahler/tree/master/Code/TMSolver

Below we give five examples of Thue–Mahler equations solved using our
implementation. Our solutions will always be subject to the assumptions

$\gcd(X,Y)=\gcd(a_{0},Y)=1.$

They will be given in the form $[X,Y,z_{1},z_{2},\dotsc,z_{v}]$. We will
revisit these examples later on in the paper to illustrate the differences
between our algorithm and that of Tzanakis and de Weger [30]. We do point out
that a number of recent papers also make use of our implementation, or the
ideas in the present paper, to solve various Thue–Mahler equations where the
degree $d$, or the number of primes $v$ are large. For example in [3], [4],
[6], [7], our algorithm is used to solve Thue–Mahler equations of degrees $5$,
$20$, $11$ and $7$ respectively.

### Example 1

We consider the problem of computing all elliptic curves $E/\mathbb{Q}$ with
trivial $2$-torsion and conductor

$771456\;=\;2^{7}\cdot 3\cdot 7^{2}\cdot 41.$

Applying Theorem 1 of [5] yields $13$ cubic Thue–Mahler equations of the form

$a_{0}X^{3}+a_{1}X^{2}Y+a_{2}XY^{2}+a_{3}Y^{3}=3^{z_{1}}\cdot 7^{z_{2}}\cdot
41^{z_{3}},\qquad\gcd(X,Y)=1,$

whose resolution algorithmically yields the desired set of elliptic curves.
The coefficients for these $13$ forms are as follows:

$\begin{array}[]{c|c}(a_{0},a_{1},a_{2},a_{3})&(a_{0},a_{1},a_{2},a_{3})\\\
\hline\cr(1,7,2,-2)&(2,1,0,3)\\\ (1,4,3,6)&(3,4,4,4)\\\ (4,4,6,3)&(2,5,0,6)\\\
(1,7,4,12)&(3,3,-1,7)\\\ (3,7,14,14)&(1,3,17,43)\\\ (8,12,13,8)&(4,1,12,-6)\\\
(3,9,5,19)&\end{array}$

Our implementation solved all $13$ of these Thue–Mahler equations and computed
the corresponding elliptic curves in a total of $2.6$ minutes on a single
core. Full computational details, as well as a list of all corresponding
elliptic curves can be found at
https://github.com/adelagherga/ThueMahler/tree/master/GhSiData/Example1

For illustration, we consider one of these $13$ Thue–Mahler equations:

$4X^{3}+X^{2}Y+12XY^{2}-6Y^{3}=3^{z_{1}}\cdot 7^{z_{2}}\cdot
41^{z_{3}},\qquad\gcd(X,Y)=1.$

Our implementation solved this in 21 seconds. The solutions are

$\displaystyle[-3,-7,1,0,1],\quad[-1,-5,2,2,0],\quad[1,-1,1,1,0],$
$\displaystyle[3,1,1,2,0],\quad[5,11,0,2,0],\quad[9,17,1,2,1],\quad[19,23,5,3,0].$

Of the seven solutions, only $(X,Y)=(1,-1)$ gives rise to elliptic curves of
conductor $771456$:

$E_{1}:y^{2}=x^{3}-x^{2}+13655x+2351833,$
$E_{2}:y^{2}=x^{3}-x^{2}+3414x-295686.$

### Example 2

We consider the Thue–Mahler equation

$7X^{3}+X^{2}Y+29XY^{2}-25Y^{3}\;=\;2^{z_{1}}\cdot 3^{z_{2}}\cdot
7^{z_{3}}\cdot 37^{z_{4}}\cdot 53^{z_{5}}\,.$

Our implementation solved this in 19 seconds. The solutions are

$[1,1,2,1,0,0,0],\qquad[19,-23,2,4,0,1,1].$

### Example 3

Consider

$F(X,Y)=3X^{5}+65X^{4}Y-290X^{3}Y^{2}-2110X^{2}Y^{3}+975XY^{4}+3149Y^{5}.$ (6)

In [28], Soydan and Tzanakis use the method of Tzanakis and de Weger [30] to
solve the equation

$F(X,Y)\;=\;-2^{5}\cdot 3^{4}\cdot 5^{z_{1}}\cdot 11^{z_{2}},$

finding no solutions (subject to the usual condition $\gcd(X,Y)=\gcd(3,Y)=1$).
As a consequence of Lemma 2.3 and Algorithm 1 of this paper – an improved
variant of the Prime Ideal Removing Lemma of [30] – this Thue–Mahler equation
yielded no ideal equations (4) to solve, and hence no solutions. Our program
took 0.1 seconds to arrive at this contradiction, terminating after the first
setup stage of the algorithm, whereas the Hambrook implementation [22] of the
method of Tzanakis and de Weger required roughly 72 days, and a less automated
variant due to Soydan and Tzanakis took around $2$ hours with human
intervention. Moreover, as a result of where our program terminated, we may
also conclude that

$F(X,Y)=\pm\;3^{4}\cdot m$

has no solutions for any integer $m$ coprime to $3$, subject to the condition
that $\gcd(X,Y)=\gcd(3,Y)=1$.

Finally, using the method of this paper, we solved the more general
Thue–Mahler equation

$F(X,Y)\;=\;-2^{z_{1}}\cdot 3^{z_{2}}\cdot 5^{z_{3}}\cdot 7^{z_{4}}\cdot
11^{z_{5}}\cdot 13^{z_{6}}\cdot 17^{z_{7}}.$

Our program took around 6 minutes to solve this. The solutions are

$\displaystyle[-27,1,8,0,0,1,1,1,1],\qquad[-7,-1,5,0,2,0,0,0,1],$
$\displaystyle[-3,1,8,0,2,0,0,0,0],\qquad[-1,-1,8,0,0,1,0,0,0],$
$\displaystyle[1,-1,5,0,0,0,0,1,0],\qquad[5,1,8,0,0,0,2,0,0],$
$\displaystyle[17,-4,0,0,2,2,0,2,0]\,.$

### Example 4

For a non-zero integer $m$, let $P(m)$ denote the maximum prime divisor of $m$
(where we take $P(1)=P(-1)=0$). In this example, we solve the equation

$P(X^{4}-2Y^{4})\leq 100,\qquad\gcd(X,Y)=1.$

Let $F(X,Y)=X^{4}-2Y^{4}$. We therefore would like to solve (3) with $a=\pm 1$
and with $p_{1},\dotsc,p_{v}$ being the set of primes $\leq 100$ (of which
there are $25$). However, it is clear that if $-2$ is not a fourth power
modulo $p$, then $p\nmid(X^{4}-2Y^{4})$. Thus we reduce to the much smaller
set of primes $p\leq 100$ for which $-2$ is a fourth power. This is the set

$\\{2,7,23,31,47,71,73,79,89\\}.$

Thus the Thue–Mahler equation we shall consider is

$X^{4}-2Y^{4}\;=\;\pm 2^{z_{1}}\cdot 7^{z_{2}}\cdot 23^{z_{3}}\cdot
31^{z_{4}}\cdot 47^{z_{5}}\cdot 71^{z_{6}}\cdot 73^{z_{7}}\cdot
79^{z_{8}}\cdot 89^{z_{9}},\qquad\gcd(X,Y)=1.$

Our implementation took roughly 3.5 days to solve this Thue–Mahler equation.
There are $49$ solutions (up to changing the signs of $X$, $Y$):

$\displaystyle[0,1,1,0,0,0,0,0,0,0,0],\quad[1,0,0,0,0,0,0,0,0,0,0],$
$\displaystyle[1,1,0,0,0,0,0,0,0,0,0],\quad[1,2,0,0,0,1,0,0,0,0,0],$
$\displaystyle[1,3,0,1,1,0,0,0,0,0,0],\quad[1,4,0,1,0,0,0,0,1,0,0],$
$\displaystyle[1,11,0,1,0,0,1,0,0,0,1],\quad[2,1,1,1,0,0,0,0,0,0,0],$
$\displaystyle[2,3,1,0,0,0,0,0,1,0,0],\quad[2,27,1,1,0,2,0,0,0,1,0],$
$\displaystyle[3,1,0,0,0,0,0,0,0,1,0],\quad[3,2,0,2,0,0,0,0,0,0,0],$
$\displaystyle[3,14,0,0,1,0,1,1,0,0,0],\quad[4,3,1,0,0,0,1,0,0,0,0],$
$\displaystyle[4,5,1,1,0,0,0,1,0,0,0],\quad[5,1,0,1,0,0,0,0,0,0,1],$
$\displaystyle[5,8,0,1,1,0,1,0,0,0,0],\quad[6,5,1,0,1,0,0,0,0,0,0],$
$\displaystyle[6,19,1,0,0,1,1,0,0,0,1],\quad[8,1,1,0,1,0,0,0,0,0,1],$
$\displaystyle[10,23,1,2,0,0,0,1,0,1,0],\quad[11,9,0,2,0,1,0,0,0,0,0],$
$\displaystyle[11,20,0,0,0,0,1,0,1,0,1],\quad[15,1,0,0,1,1,0,1,0,0,0],$
$\displaystyle[15,13,0,0,0,0,0,0,1,0,1],\quad[16,21,1,0,1,0,0,0,0,1,1],$
$\displaystyle[17,5,0,2,1,0,0,0,1,0,0],\quad[19,20,0,4,0,0,0,0,0,1,0],$
$\displaystyle[21,11,0,0,0,1,0,0,2,0,0],\quad[22,49,1,0,1,1,0,0,0,0,2],$
$\displaystyle[33,13,0,1,0,0,2,0,1,0,0],\quad[37,19,0,0,1,2,0,0,1,0,0],$
$\displaystyle[40,13,1,1,0,1,0,0,1,1,0],\quad[52,51,1,2,1,1,0,0,0,0,1],$
$\displaystyle[53,44,0,1,1,1,0,0,0,1,0],\quad[59,56,0,0,0,1,1,1,1,0,0],$
$\displaystyle[61,48,0,1,0,0,0,1,1,0,1],\quad[66,101,1,0,2,1,0,0,1,1,0],$
$\displaystyle[68,43,1,1,1,2,1,0,0,0,0],\quad[95,58,0,1,0,1,1,0,1,1,0],$
$\displaystyle[118,101,1,2,1,0,0,1,0,0,1],\quad[142,57,1,1,3,1,0,0,1,0,0],$
$\displaystyle[162,137,1,2,0,0,2,0,1,0,0],\quad[181,124,0,0,1,0,1,0,0,2,1],$
$\displaystyle[221,295,0,0,2,0,1,0,1,1,1],\quad[281,199,0,1,1,0,1,1,1,1,0],$
$\displaystyle[286,283,1,3,1,0,0,0,3,0,0],\quad[389,96,0,4,0,1,1,0,1,0,1],$
$\displaystyle[420,437,1,0,0,1,3,0,1,0,1].$

### Example 5

Our last example is

$5X^{11}+X^{10}Y+4X^{9}Y^{2}+X^{8}Y^{3}+6X^{7}Y^{4}+X^{6}Y^{5}+6X^{5}Y^{6}+6X^{3}Y^{8}+4XY^{10}-2Y^{11}\\\
=2^{z_{1}}\cdot 3^{z_{2}}\cdot 5^{z_{3}}\cdot 7^{z_{4}}\cdot 11^{z_{5}}\,.$

Our program solved this in around 4.7 hours. However this time was almost
entirely taken up with the computation of the class group and the units. Once
the class group and unit computations were complete, it took only 2.3 minutes
to provably determine the solutions. These are

$\displaystyle[0,-1,1,0,0,0,0],\qquad[1,-1,1,1,1,0,0],$
$\displaystyle[1,1,5,0,0,0,0],\qquad[1,2,0,3,0,1,1]\,.$

###  1.1. Notation and Organization of the paper

As before $F\in\mathbb{Z}[X,Y]$ will be a homogeneous irreducible binary form
of degree $d\geq 3$ with coefficients $a_{0},\dotsc,a_{d}$ as in (1). Let $a$
be a non-zero integer, and $p_{1},\dotsc,p_{v}$ be distinct primes satisfying
$p_{i}\nmid a$. Let

$f(x)=a_{0}^{d-1}\cdot
F(x/a_{0},1)=x^{d}+a_{1}x^{d-1}+a_{0}a_{2}x^{d-2}+\cdots+a_{0}^{d-1}a_{d}.$

This is an irreducible monic polynomial with coefficients in $\mathbb{Z}$. Let
$\theta$ be a root of $f$ and let $K=\mathbb{Q}(\theta)$. Note that $K$ is a
number field of degree $d$. Write ${\mathcal{O}}_{K}$ for the ring of integers
of $K$. We can rewrite our Thue–Mahler equation (3) as

$\operatorname{Norm}(a_{0}X-\theta Y)=a_{0}^{d-1}\cdot a\cdot
p_{1}^{z_{1}}\cdots p_{v}^{z_{v}}.$ (7)

Note that we do not assume that $(a_{0},p_{i})=1$.

The paper is organized as follows.

  1. (a)

In Section 2 we consider the decomposition of the ideal $(a_{0}X-\theta
Y){\mathcal{O}}_{K}$ as a product of prime ideals. In particular, we introduce
an algorithm to compare and restrict the possible valuations of all prime
ideals above each of $p_{1},\dots,p_{v}$.

  2. (b)

We summarize the results of applying this algorithm in Section 3, wherein we
reduce solving (7) to solving a family of ideal equations of the form (4).

  3. (c)

In Section 4, we show that such ideal equations are either impossible due to a
class group obstruction, or reduce to a single equation of the form (5). The
remainder of the paper is devoted to solving equations of the form (5) where
the unknowns are coprime integers $X$, $Y$ and non-negative integers
$b_{1},\dotsc,b_{r}$.

  4. (d)

In Section 5, we recall key theorems from the theory of lower bounds for
linear forms in complex and $p$-adic logarithms due to Matveev and to Yu.

  5. (e)

In Section 6, with the help of these theorems, we obtain a very large upper
bound on the exponents $b_{1},\dotsc,b_{r}$ in (5).

  6. (f)

In Section 7 we show how an application of close vector algorithms allows us
to obtain a substantially improved bound on the $\mathfrak{p}$-adic valuation
of $a_{0}X-\theta Y$ for any prime $\mathfrak{p}$. This step avoids the
$\mathfrak{p}$-adic logarithms of earlier approaches.

  7. (g)

Section 8 uses the real embeddings of $K$ applied to (5) to obtain $d-2$
approximate relations involving the exponents $b_{i}$. In Section 9, we setup
an ‘approximation lattice’ using these $d-2$ approximate relations. We explain
how close vector algorithms can be used to substantially reduce our bound for
the exponents $b_{1},\dotsc,b_{r}$ in (5). Earlier approaches used just one of
the $d-2$ relations to construct the approximation lattice, but we explain why
using just one approximate relation can fail in certain situations.

  8. (h)

Steps (f) and (g) are applied repeatedly until no further improvement in the
bounds are possible. In Section 10 we introduce an analogue of the
Mordell–Weil sieve, which we call the “Dirichlet sieve” which is capable of
efficiently sieving for the solutions up to the remaining bounds, thereby
finally resolving the Thue-Mahler equation (3).

### Acknowledgements

The authors are grateful to Mike Bennett, Rafael von Känel and Benjamin
Matschke for many stimulating discussions.

##  2\. The $p$-part of $(a_{0}X-\theta Y){\mathcal{O}}_{K}$

If $\mathfrak{c}$ is a fractional ideal of ${\mathcal{O}}_{K}$, and $p$ is a
rational prime, we define the $p$-part of $\mathfrak{c}$ to be the fractional
ideal

$\prod_{\mathfrak{p}\mid
p}\mathfrak{p}^{\operatorname{ord}_{\mathfrak{p}}(\mathfrak{c})}.$

For each rational prime $p\in\\{p_{1},\dots,p_{v}\\}$ of (7), we want to study
the $p$-part of ${(a_{0}X-\theta Y){\mathcal{O}}_{K}}$ coming from the prime
ideals above $p$. The so-called Prime Ideal Removal Lemma in Tzanakis and de
Weger compares the possible valuations of ${(a_{0}X-\theta
Y){\mathcal{O}}_{K}}$ at two prime ideals $\mathfrak{p}_{1}$,
$\mathfrak{p}_{2}\mid p$ to help cut down the possibilities for the the
$p$-part of $(a_{0}X-\theta Y){\mathcal{O}}_{K}$. However if
$\mathfrak{p}_{1}\mid(a_{0}X-\theta Y){\mathcal{O}}_{K}$ then this restricts
the values of $X$ and $Y$ modulo $p$. Indeed, any choice of $X$ and $Y$ modulo
$p$ affects the valuations of $(a_{0}X-\theta Y){\mathcal{O}}_{K}$ at all
primes $\mathfrak{p}\mid p$. So we study all valuations at the same time, not
just two of them. This enables us to give a much smaller list of possibilities
for the $p$-part of $(a_{0}X-\theta Y){\mathcal{O}}_{K}$ than in Tzanakis and
de Weger, as we will see in Section 4.

######  Definition 2.1.

Let $p$ be a rational prime. Let $L_{p}$ be a subset of the ideals
$\mathfrak{b}$ supported at the prime ideals above $p$. Let $M_{p}$ be a
subset of the set of pairs $(\mathfrak{b},\mathfrak{p})$ where $\mathfrak{b}$
is supported at the prime ideals above $p$, and $\mathfrak{p}\mid p$ is a
prime ideal satisfying $e(\mathfrak{p}|p)=f(\mathfrak{p}|p)=1$, where
$e(\mathfrak{p}|p)$ and $f(\mathfrak{p}|p)$ are, respectively, the
ramification index and inertial degree of $\mathfrak{p}$ over $p$. We call the
pair $L_{p}$, $M_{p}$ satisfactory if for every solution $(X,Y)$ to (3),

  1. (i)

either there is some $\mathfrak{b}\in L_{p}$ such that the $p$-part of
$(a_{0}X-\theta Y){\mathcal{O}}_{K}$ is equal to $\mathfrak{b}$,

  2. (ii)

or there is a pair $(\mathfrak{b},\mathfrak{p})\in M_{p}$ and a non-negative
integer $l$ such that the $p$-part of $(a_{0}X-\theta Y){\mathcal{O}}_{K}$ is
equal to $\mathfrak{b}\mathfrak{p}^{l}$.

At this point the definition is perhaps mysterious. Lemma 2.4 and the
following remark give an explanation for the definition and for the existence
of finite satisfactory sets $L_{p}$, $M_{p}$. We will give an algorithm to
produce (hopefully small) satisfactory sets $L_{p}$ and $M_{p}$. Before that
we embark on a simplification. The expression $a_{0}X-\theta Y$ is a linear
form in two variables $X$, $Y$. It is easier to scale so that we are dealing
with a linear expression in just one variable.

For a rational prime $p$, let

$\mathbb{Z}_{(p)}=\\{U\in\mathbb{Q}\;:\;\operatorname{ord}_{p}(U)\geq 0\\}.$

######  Definition 2.2.

Let $p$ be a rational prime. Let $\alpha\in K$ and $\beta\in K^{\times}$. Let
$L$ be a subset of the ideals $\mathfrak{b}$ supported on the prime ideals of
${\mathcal{O}}_{K}$ above $p$. Let $M$ be a subset of the set of pairs
$(\mathfrak{b},\mathfrak{p})$ where $\mathfrak{b}$ is supported on the prime
ideals above $p$, and where $\mathfrak{p}$ is a prime ideal above $p$
satisfying $e(\mathfrak{p}|p)=f(\mathfrak{p}|p)=1$. We call $L$, $M$ adequate
for $(\alpha,\beta)$ if for every $U\in\mathbb{Z}_{(p)}$,

  1. (i)

either there is some $\mathfrak{b}\in L$ such that the $p$-part of
$\beta\cdot(U+\alpha){\mathcal{O}}_{K}$ equals $\mathfrak{b}$,

  2. (ii)

or there is a pair $(\mathfrak{b},\mathfrak{p})\in M$ and a non-negative
integer $l$ such that the $p$-part of $\beta\cdot(U+\alpha){\mathcal{O}}_{K}$
equals $\mathfrak{b}\mathfrak{p}^{l}$.

######  Lemma 2.3.

Let $L$, $M$ be adequate for $(-\theta/a_{0},a_{0})$ and let
$L_{p}=L\cup\\{1\cdot\mathcal{O}_{K}\\}$ and $M_{p}=M$. Then the pair $L_{p}$,
$M_{p}$ is satisfactory.

###### Proof.

Recall that $\gcd(X,Y)=\gcd(a_{0},Y)=1$.

If $p\mid Y$ then $\operatorname{ord}_{\mathfrak{p}}(Y)>0$ for any
$\mathfrak{p}$ above $p$, and thus

$\operatorname{ord}_{\mathfrak{p}}(a_{0}X-\theta Y)=0.$

If $p\nmid Y$, we write

$U=\frac{X}{Y},\qquad\alpha=\frac{-\theta}{a_{0}},\qquad\beta=a_{0}.$

Then $U\in\mathbb{Z}_{(p)}$ and
$\operatorname{ord}_{\mathfrak{p}}(a_{0}X-\theta
Y)=\operatorname{ord}_{\mathfrak{p}}(\beta\cdot(U+\alpha))$ for all prime
ideals $\mathfrak{p}$ above $p$. Thus the $p$-part of $\beta\cdot(U+\alpha)$
is equal to the $p$-part of $\operatorname{ord}_{\mathfrak{p}}(a_{0}X-\theta
Y)$.

The lemma follows. ∎

We now demystify Definitions 2.1 and 2.2.

######  Lemma 2.4.

Let $p$ be a rational prime. Choose $\gamma\in K$ such that $\gamma\neq\theta$
is another generator of $K$. Then there is a bound $B$ depending only on $p$
and $\gamma$ such that the following hold:

  1. (a)

For any $U\in\mathbb{Z}_{(p)}$ and any pair of distinct prime ideals
$\mathfrak{p}_{1}$, $\mathfrak{p}_{2}$ lying over $p$, either

$\operatorname{ord}_{\mathfrak{p}_{1}}(U+\gamma)\leq
B,\qquad\text{or}\qquad\operatorname{ord}_{\mathfrak{p}_{2}}(U+\gamma)\leq B.$

  2. (b)

For any $U\in\mathbb{Z}_{(p)}$ and any prime ideal $\mathfrak{p}$ over $p$
with $e(\mathfrak{p}|p)\neq 1$ or ${f(\mathfrak{p}|p)\neq 1}$,

$\operatorname{ord}_{\mathfrak{p}}(U+\gamma)\leq B.$

###### Proof.

Let $\mathfrak{p}$ be a prime ideal above $p$, and suppose that
$\operatorname{ord}_{\mathfrak{p}}(U+\gamma)$ is unbounded for
$U\in\mathbb{Z}_{(p)}$. Thus there is an infinite sequence
$\\{U_{i}\\}\subset\mathbb{Z}_{(p)}$ such that

$\lim_{i\rightarrow\infty}\operatorname{ord}_{\mathfrak{p}}(U_{i}+\gamma)\;=\;\infty.$

However, $\mathbb{Z}_{(p)}\subset\mathbb{Z}_{p}$, where the latter is compact.
Thus $\\{U_{i}\\}$ contains an infinite subsequence $\\{U_{n_{i}}\\}$
converging to, say, $U\in\mathbb{Z}_{p}$. Write
$\phi_{\mathfrak{p}}\;:\;K\hookrightarrow{\mathbb{C}}_{p}$ for the embedding
of $K$ corresponding to the prime ideal $\mathfrak{p}$. It follows that
${\phi_{\mathfrak{p}}(\gamma)=-U\in\mathbb{Z}_{p}}$. Recall the assumption
that $K=\mathbb{Q}(\gamma)$. Thus $K_{\mathfrak{p}}$, the topological closure
of $\phi_{\mathfrak{p}}(K)$ in ${\mathbb{C}}_{p}$, is in fact
$\mathbb{Q}_{p}$. Thus $e(\mathfrak{p}|p)=f(\mathfrak{p}|p)=1$. This proves
(b).

For (a), suppose that there is a pair of distinct primes $\mathfrak{p}_{1}$,
$\mathfrak{p}_{2}$ above $p$ and an infinite sequence
$\\{U_{i}\\}\subset\mathbb{Z}_{(p)}$ such that

$\lim_{i\rightarrow\infty}\operatorname{ord}_{\mathfrak{p}_{1}}(U_{i}+\gamma)\;=\;\lim_{i\rightarrow\infty}\operatorname{ord}_{\mathfrak{p}_{2}}(U_{i}+\gamma)\;=\;\infty.$
(8)

Again, let $\\{U_{n_{i}}\\}$ be an infinite subsequence of $\\{U_{i}\\}$
converging to, say, $U\in\mathbb{Z}_{p}$. Then
$\phi_{\mathfrak{p}_{1}}(\gamma)=-U=\phi_{\mathfrak{p}_{2}}(\gamma)$. As
$K=\mathbb{Q}(\gamma)$, the embeddings $\phi_{\mathfrak{p}_{1}}$,
$\phi_{\mathfrak{p}_{2}}$ are equal, contradicting
$\mathfrak{p}_{1}\neq\mathfrak{p}_{2}$. ∎

Remark. We apply Lemma 2.4 with $\gamma=\alpha$ as in Lemma 2.3 in order to
explain Definitions 2.1 and 2.2. The valuation of $\beta\cdot(U+\alpha)$ can
be arbitrarily large only for those $\mathfrak{p}$ above $p$ that satisfy
$e(\mathfrak{p}|p)=f(\mathfrak{p}|p)=1$, and if it is sufficiently large for
one such $\mathfrak{p}$ then it is bounded for all others. Thus there must
exist finite adequate sets $L$, $M$. We now turn to the task of giving an
algorithm to determine such adequate sets $L$, $M$.

######  Lemma 2.5.

Let $\alpha\in K$ and $\beta\in K^{\times}$. Let $p$ be a rational prime and
let $\mathfrak{p}$ be a prime ideal of ${\mathcal{O}}_{K}$ above $p$. Suppose
$U\in\mathbb{Z}_{(p)}$ and

$\operatorname{ord}_{\mathfrak{p}}(\beta\cdot(U+\alpha))>\operatorname{ord}_{\mathfrak{p}}(\beta)+\min\\{0,\operatorname{ord}_{\mathfrak{p}}(\alpha)\\}.$
(9)

Then the following hold:

  1. (i)

$\operatorname{ord}_{\mathfrak{p}}(\alpha)\geq 0$.

  2. (ii)

The image of $\alpha$ in
${\mathbb{F}}_{\mathfrak{p}}:={\mathcal{O}}_{K}/\mathfrak{p}$ belongs to the
prime subfield ${\mathbb{F}}_{p}$. In particular, there is a unique
$u\in\\{0,\dots,p-1\\}$ such that $u\equiv-\alpha\pmod{\mathfrak{p}}$.

  3. (iii)

With $u$ as in (ii), $U=pU^{\prime}+u$ where $U^{\prime}\in\mathbb{Z}_{(p)}$.

###### Proof.

Since $U\in\mathbb{Z}_{(p)}$, we have
$\operatorname{ord}_{\mathfrak{p}}(U)\geq 0$ and thus
${\operatorname{ord}_{\mathfrak{p}}(U+\alpha)=\operatorname{ord}_{\mathfrak{p}}(\alpha)}$
if $\operatorname{ord}_{\mathfrak{p}}(\alpha)<0$. In this case,
$\operatorname{ord}_{\mathfrak{p}}(\beta\cdot(U+\alpha))=\operatorname{ord}_{\mathfrak{p}}(\alpha)+\operatorname{ord}_{\mathfrak{p}}(\beta)$,
contradicting (9). Thus $\operatorname{ord}_{\mathfrak{p}}(\alpha)\geq 0$,
proving (i).

Write $\overline{\alpha}$ for the image of $\alpha$ in
${\mathbb{F}}_{\mathfrak{p}}$, and suppose this does not belong to the prime
subfield ${\mathbb{F}}_{p}$. In particular
$\operatorname{ord}_{\mathfrak{p}}(\alpha)=0$. However, the image
$\overline{U}$ of $U$ in ${\mathbb{F}}_{\mathfrak{p}}$ does belong to
${\mathbb{F}}_{p}$. Thus $U\not\equiv-\alpha\pmod{\mathfrak{p}}$, or
equivalently $\operatorname{ord}_{\mathfrak{p}}(U+\alpha)=0$. Therefore,
$\operatorname{ord}_{\mathfrak{p}}(\beta\cdot(U+\alpha))=\operatorname{ord}_{\mathfrak{p}}(\beta)$,
contradicting (9). We deduce that $\overline{\alpha}\in{\mathbb{F}}_{p}$, and
thus (ii) holds.

Now, let $u$ be as in (ii). By (9), we have
$\operatorname{ord}_{\mathfrak{p}}(U+\alpha)>0$, and thus
$\overline{U}=-\overline{\alpha}=\overline{u}$. But $\overline{U}$,
$\overline{u}\in{\mathbb{F}}_{p}$. Therefore, $\operatorname{ord}_{p}(U-u)>0$,
and so $U=pU^{\prime}+u$ for some $U^{\prime}\in\mathbb{Z}_{(p)}$. ∎

######  Algorithm 1.

Given $p$ a rational prime, $\alpha\in K$ satisfying $K=\mathbb{Q}(\alpha)$,
and $\beta\in K^{\times}$, to compute $L$, $M$ adequate for $(\alpha,\beta)$:

  1. Step (a)

Let

$\mathcal{B}=\\{\mathfrak{p}\mid
p\;:\;\operatorname{ord}_{\mathfrak{p}}(\alpha)\geq 0\text{ and }\text{the
image of $\alpha$ in ${\mathbb{F}}_{\mathfrak{p}}$ belongs to
${\mathbb{F}}_{p}$}\\},$

and

$\mathfrak{b}=\prod_{\mathfrak{p}\mid
p}\mathfrak{p}^{\operatorname{ord}_{\mathfrak{p}}(\beta)+\min\\{0,\operatorname{ord}_{\mathfrak{p}}(\alpha)\\}}.$

  2. Step (b)

If $\mathcal{B}=\emptyset$ then return $L=\\{\mathfrak{b}\\}$, $M=\emptyset$
and terminate the algorithm.

  3. Step (c)

If $\mathcal{B}$ consists of a single prime ideal $\mathfrak{p}^{\prime}$
satisfying $e(\mathfrak{p}^{\prime}|p)=f(\mathfrak{p}^{\prime}|p)=1$ then
return $L=\emptyset$, $M=\\{(\mathfrak{b},\mathfrak{p}^{\prime})\\}$ and
terminate the algorithm.

  4. Step (d)

Let

$\mathcal{U}=\\{0\leq u\leq p-1\;:\;\text{there is some
$\mathfrak{p}\in\mathcal{B}$ such that
$\alpha\equiv-u\pmod{\mathfrak{p}}$}\\}.$

Loop through the elements $u\in\mathcal{U}$. For each $u$, use Algorithm 1 to
compute adequate $L_{u}$, $M_{u}$ for the pair $((u+\alpha)/p,p\beta)$.

    1. Step (d1)

If $\mathcal{U}=\\{0,1,2,\dotsc,p-1\\}$ then return

$L=\bigcup_{u\in\mathcal{U}}L_{u},\qquad M=\bigcup_{u\in\mathcal{U}}M_{u},$
(10)

and terminate the algorithm.

    2. Step (d2)

Else, return

$L=\\{\mathfrak{b}\\}\cup\bigcup_{u\in\mathcal{U}}L_{u},\qquad
M=\bigcup_{u\in\mathcal{U}}M_{u},$ (11)

and terminate the algorithm.

Remarks.

  * •

Algorithm 1 is recursive. If the hypotheses of (b) and (c) fail then the
algorithm replaces the linear form $\beta\cdot(U+\alpha)$ with a number of
linear forms

$p\beta\cdot(U^{\prime}+(u+\alpha)/p)=\beta\cdot(pU^{\prime}+u+\alpha).$

In essence we are replacing $\mathbb{Z}_{(p)}$ with a number of the cosets of
$p\mathbb{Z}_{(p)}$. The algorithm is then applied to each of these linear
forms individually.

  * •

Note that the number of prime ideals $\mathfrak{p}$ above $p$ is bounded by
the degree $[K:\mathbb{Q}]$. In particular,
$\\#\mathcal{U}\leq[K:\mathbb{Q}]$. Therefore the number of branches at each
iteration of the algorithm is bounded independently of $p$.

######  Proposition 2.6.

Suppose $\beta\in K^{\times}$, $\alpha\in K$ and moreover,
$K=\mathbb{Q}(\alpha)$. Then Algorithm 1 terminates in finite time and
produces adequate $L$, $M$ for $(\alpha,\beta)$.

###### Proof.

Let $\mathcal{B}$ and $\mathfrak{b}$ be as in Step (a). Observe that, for any
$\mathfrak{p}$ above $p$,

$\operatorname{ord}_{\mathfrak{p}}(\beta\cdot(U+\alpha))\geq\operatorname{ord}_{\mathfrak{p}}(\beta)+\min\\{0,\operatorname{ord}_{\mathfrak{p}}(\alpha)\\}=\operatorname{ord}_{\mathfrak{p}}(\mathfrak{b}).$

It follows that $\mathfrak{b}$ divides the $p$-part of $\beta\cdot(U+\alpha)$.
Lemma 2.5 tells us that

$\operatorname{ord}_{\mathfrak{p}}(\beta\cdot(U+\alpha))=\operatorname{ord}_{\mathfrak{p}}(\beta)+\min\\{0,\operatorname{ord}_{\mathfrak{p}}(\alpha)\\}=\operatorname{ord}_{\mathfrak{p}}(\mathfrak{b})$
(12)

for all prime ideals $\mathfrak{p}$ lying above $p$, except possibly for
$\mathfrak{p}\in\mathcal{B}$. If $\mathcal{B}=\emptyset$ (i.e. the hypothesis
of (b) is satisfied), then the $p$-part of $\beta\cdot(U+\alpha)$ is
$\mathfrak{b}$, and hence the pair $L=\\{\mathfrak{b}\\}$, $M=\emptyset$ is
adequate for $(\alpha,\beta)$. If $\mathcal{B}=\\{\mathfrak{p}^{\prime}\\}$
where $e(\mathfrak{p}^{\prime}|p)=f(\mathfrak{p}^{\prime}|p)=1$ (i.e. the
hypothesis of step (c) is satisfied) then the $p$-part of
$\beta\cdot(U+\alpha)$ has the form
$\mathfrak{b}\cdot{\mathfrak{p}^{\prime}}^{l}$ for some $l\geq 0$. Hence
$L=\emptyset$, $M=\\{(\mathfrak{b},\mathfrak{p}^{\prime})\\}$ are adequate for
$(\alpha,\beta)$.

Suppose the hypotheses of Step (b) and Step (c) fail. Let $\mathcal{U}$ be as
in Step (d). If $U\equiv u\pmod{p}$ for some $u\in\mathcal{U}$, then
$U=pU^{\prime}+u$ for some $U^{\prime}\in\mathbb{Z}_{(p)}$. Thus
$\beta\cdot(U+\alpha)=p\beta\cdot(U^{\prime}+(u+\alpha)/p)$, and so naturally
the $p$-parts of $\beta\cdot(U+\alpha)$ and
$p\beta\cdot(U^{\prime}+(u+\alpha)/p)$ agree. In (d1), $\mathcal{U}$
represents all of the congruence classes modulo $p$, and this justifies (10).
In (d2), $\mathcal{U}$ represents some of the congruence classes. If
$u\notin\mathcal{U}$, then by Lemma 2.5, the equality (12) holds for all prime
ideals $\mathfrak{p}$ above $p$, and hence $\mathfrak{b}$ is the $p$-part of
$\beta\cdot(U+\alpha)$. This justifies (11).

Next we show that the algorithm terminates in finitely many steps. Suppose
otherwise. Then there will be an infinite sequence of
$u_{i}\in\\{0,1,\dotsc,p-1\\}$ and pairs $(\alpha_{i},\beta_{i})$ with

$\alpha_{0}=\alpha,\qquad\beta_{0}=\beta,\qquad\alpha_{i+1}=\frac{u_{i}+\alpha_{i}}{p},\qquad\beta_{i+1}=p\beta_{i}.$

Let us denote by $\mathcal{B}_{i}$ the set $\mathcal{B}$ for the pair
$(\alpha_{i},\beta_{i})$. It is easy to see from the definition that
$\mathcal{B}_{i+1}\subseteq\mathcal{B}_{i}$. Suppose $\mathfrak{p}$ belongs to
infinitely many of the $\mathcal{B}_{i}$. Then, infinitely often,
$\operatorname{ord}_{\mathfrak{p}}(\alpha_{i})\geq 0$. However,

$\alpha=\alpha_{0}=-u_{0}-u_{1}p-u_{2}p^{2}-\cdots-
u_{i-1}p^{i-1}+p^{i}\alpha_{i}.$

Let $\mu=-u_{0}-u_{1}p-\cdots\in\mathbb{Z}_{p}$. Let
$\phi_{\mathfrak{p}}:K\hookrightarrow{\mathbb{C}}_{p}$ be the embedding
corresponding to $\mathfrak{p}$. Then $\phi_{\mathfrak{p}}(\alpha)=\mu$. Since
$K=\mathbb{Q}(\alpha)$, the embedding $\phi_{\mathfrak{p}}$ is determined by
the image of $\alpha$. Since
$\phi_{\mathfrak{p}}\neq\phi_{\mathfrak{p}^{\prime}}$ whenever
$\mathfrak{p}\neq\mathfrak{p}^{\prime}$, we see that $\mathcal{B}_{i}$
consists of at most one prime for $i$ sufficiently large. Moreover, for such a
prime, $\phi_{\mathfrak{p}}(K)=\mathbb{Q}_{p}$ and so must satisfy
$e(\mathfrak{p}|p)=f(\mathfrak{p}|p)=1$. Thus for sufficiently large $i$ the
algorithm must terminate at Step (b) or Step (c), giving a contradiction. ∎

Following Lemma 2.3, we thus let $L_{p}=L\cup\\{1\cdot\mathcal{O}_{K}\\}$ and
$M_{p}=M$, where we compute $L$ and $M$ using Algorithm 1 with
$\alpha=-\theta/a_{0}$ and $\beta=a_{0}$.

Refinements. Let $L_{p}$, $M_{p}$ be a satisfactory pair (for example,
produced by Algorithm 1). We explain here some obvious refinements that will
reduce or simplify these sets, whilst maintaining the satisfactory property.

  * •

If some pair $(\mathfrak{b},\mathfrak{p})$ is in $M_{p}$ then we may replace
this with the pair $(\mathfrak{b}^{\prime},\mathfrak{p})$ where

$\mathfrak{b}^{\prime}=\frac{\mathfrak{b}}{\mathfrak{p}^{\operatorname{ord}_{\mathfrak{p}}(\mathfrak{b})}}\,.$

  * •

If some $\mathfrak{b}$ is contained in $L_{p}$, and some
$(\mathfrak{b}^{\prime},\mathfrak{p})$ is contained in $M_{p}$ with
$\mathfrak{b}^{\prime}\mid\mathfrak{b}$ and
$\mathfrak{b}/\mathfrak{b}^{\prime}=\mathfrak{p}^{w}$ for some $w\geq 0$, then
we may delete $\mathfrak{b}$ from $L_{p}$.

  * •

Suppose $p\mid a_{0}$. Observe that if $\mathfrak{b}\in L_{p}$ is the $p$-part
of $(a_{0}X-\theta Y){\mathcal{O}}_{K}$ then
$\operatorname{ord}_{p}(\operatorname{Norm}(a_{0}X-\theta
Y))=\operatorname{ord}_{p}(\operatorname{Norm}(\mathfrak{b}))$. However, it is
clear that $\operatorname{ord}_{p}(\operatorname{Norm}(a_{0}X-\theta
Y))\geq(d-1)\operatorname{ord}_{p}(a_{0})$. Thus, we may delete $\mathfrak{b}$
from $L_{p}$ if
$\operatorname{ord}_{p}(\operatorname{Norm}(\mathfrak{b}))<(d-1)\operatorname{ord}_{p}(a_{0})$.

##  3\. An Equation in Ideals

For every $p\in P:=\\{p_{1},\dotsc,p_{v}\\}$ we let $L_{p}$, $M_{p}$ be a
corresponding satisfactory pair. From Definition 2.1, we see that there is
some partition $P=P_{1}\cup P_{2}$ such that for every $p\in P_{1}$, the
$p$-part of $(a_{0}X-\theta Y){\mathcal{O}}_{K}$ equals
$\mathfrak{b}\mathfrak{p}^{l}$ for some $(\mathfrak{b},\mathfrak{p})\in M_{p}$
and $l\geq 0$, and for every $p\in P_{2}$, it equals some $\mathfrak{b}\in
L_{p}$. Let $P=P_{1}\cup P_{2}$ be a partition of $P$ and write

$P_{1}=\\{q_{1},\dotsc,q_{s}\\},\qquad P_{2}=\\{q_{s+1},\dotsc,q_{v}\\}.$

Let $\mathcal{Z}_{P_{1},P_{2}}$ be the set of all pairs $(\mathfrak{a},S)$
such that there are $(\mathfrak{b}_{i},\mathfrak{p}_{i})\in M_{q_{i}}$ for
$1\leq i\leq s$, and $\mathfrak{b}_{j}\in L_{q_{j}}$ for $s+1\leq j\leq v$
satisfying

$\mathfrak{a}=\mathfrak{b}_{0}\cdot\mathfrak{b}_{1}\mathfrak{b}_{2}\cdots\mathfrak{b}_{s}\cdot\mathfrak{b}_{s+1}\cdots\mathfrak{b}_{v},\qquad
S=\\{\mathfrak{p}_{1},\dotsc,\mathfrak{p}_{s}\\},$

where $\mathfrak{b}_{0}$ denotes an ideal of ${\mathcal{O}}_{K}$ of norm

$R=\bigg{|}\frac{a\cdot
a_{0}^{d-1}}{\gcd(\operatorname{Norm}(\mathfrak{b}_{1}\cdots\mathfrak{b}_{v}),a\cdot
a_{0}^{d-1})}\bigg{|}.$

Let

$\mathcal{Z}\;:=\;\bigcup_{P_{1}\subseteq P}\mathcal{Z}_{P_{1},P-P_{1}}.$

######  Proposition 3.1.

Let $(X,Y)$ be a solution to (3). Then there is some
$(\mathfrak{a},S)\in\mathcal{Z}$ such that

$(a_{0}X-\theta
Y){\mathcal{O}}_{K}=\mathfrak{a}\cdot\mathfrak{p}_{1}^{n_{1}}\cdots\mathfrak{p}_{s}^{n_{s}}$
(13)

where $S=\\{\mathfrak{p}_{1},\dotsc,\mathfrak{p}_{s}\\}$, and
$n_{1},\dotsc,n_{s}$ are non-negative integer. Moreover, the set $S$ has the
following properties:

  1. (a)

$e(\mathfrak{p}_{i}|q_{i})=f(\mathfrak{p}_{i}|q_{i})=1$ for $1\leq i\leq s$.

  2. (b)

Let $1\leq i\leq s$. Let $p$ be the unique rational prime below
$\mathfrak{p}_{i}$. Then $\mathfrak{p}_{j}\nmid p$ for all $1\leq j\leq s$
with $j\neq i$.

To solve (3), we will solve (13) for every possible choice of
$(\mathfrak{a},S)\in\mathcal{Z}$.

Remark. Observe that for any $(\mathfrak{a},S)\in\mathcal{Z}$, there may be
several possibilities for $\mathfrak{b}_{0}$. Let $\mathcal{R}$ denote the set
of all ideals $\mathfrak{b}_{0}$ having norm $R$ for some
$(\mathfrak{a},S)\in\mathcal{Z}$. Here, we provide a simple refinement to cut
down the number of ideals in $\mathcal{R}$. In particular, we apply Algorithm
1 and Lemma 2.3 to each rational prime $p$ dividing $R$, generating the
corresponding sets $M_{p}$ and $L_{p}$. For each
$\mathfrak{b}_{0}\in\mathcal{R}$, if the $p$-part of $\mathfrak{b}_{0}$ cannot
be made up of any of the elements of $M_{p}$ or $L_{p}$, we may remove
$\mathfrak{b}_{0}$ from $\mathcal{R}$. Moreover, if this process yields
$\mathcal{R}=\emptyset$, we may remove $(\mathfrak{a},S)$ from $\mathcal{Z}$.

###  3.1. Example 3 continued

We revisit Example 3 to provide more details on our resolution of

$F(X,Y)=-2^{5}\cdot 3^{4}\cdot 5^{z_{1}}\cdot 11^{z_{2}},$

where $F$ is given in (6). We first note the decomposition into prime ideals
of $5$ and $11$ in ${\mathcal{O}}_{K}$:

$5\cdot{\mathcal{O}}_{K}\,=\,\mathfrak{p}_{5,1}^{5},\qquad
11\cdot{\mathcal{O}}_{K}\,=\,\mathfrak{p}_{11,1}^{2}\cdot\mathfrak{p}_{11,2}^{2}\cdot\mathfrak{p}_{11,3},$

where

$\displaystyle\mathfrak{p}_{5,1}$ $\displaystyle=\Big{\langle}5,\
\frac{1}{23760}(\theta^{4}+8\theta^{3}+1410\theta^{2}+46512\theta+33669)\Big{\rangle},$
$\displaystyle\mathfrak{p}_{11,1}$ $\displaystyle=\Big{\langle}11,\
\frac{1}{990}(\theta^{3}+227\theta^{2}+5583\theta+14859)\Big{\rangle},$
$\displaystyle\mathfrak{p}_{11,2}$ $\displaystyle=\Big{\langle}11,\
\frac{1}{15840}(\theta^{4}+20\theta^{3}+10734\theta^{2}+126708\theta+172377)\Big{\rangle},$
$\displaystyle\mathfrak{p}_{11,3}$ $\displaystyle=\Big{\langle}11,\
\frac{1}{24}(\theta^{2}+14\theta+117)\Big{\rangle}$

are all degree $1$ prime ideals (specified using the standard $2$-element
representation). Applying Algorithm 1 and Lemma 2.3 to each of these rational
primes, we thus obtain the following possibilities for satisfactory pairs
$M_{p}$, $L_{p}$:

$\displaystyle M_{11}$ $\displaystyle=\\{(1\cdot{\mathcal{O}}_{K},\
\mathfrak{p}_{11,3})\\}\quad\text{ and }\quad
L_{11}=\\{\mathfrak{p}_{11,1}\cdot\mathfrak{p}_{11,2}\\},$ $\displaystyle
M_{5}$ $\displaystyle=\emptyset\quad\text{ and }\quad
L_{5}=\\{1\cdot{\mathcal{O}}_{K}\\}\quad\text{ or }\quad
L_{5}=\\{\mathfrak{p}_{5,1}^{2}\\}.$

Now, we have $4$ possible ideal equations of the form $(a_{0}X-\theta
Y){\mathcal{O}}_{K}$,

$(a_{0}X-\theta
Y){\mathcal{O}}_{K}=\begin{cases}\mathfrak{b}_{0}\cdot\mathfrak{p}_{11,1}\cdot\mathfrak{p}_{11,2},&\text{where
}S=\emptyset,\\\
\mathfrak{b}_{0}\cdot\mathfrak{p}_{5,1}^{2}\cdot\mathfrak{p}_{11,1}\cdot\mathfrak{p}_{11,2},&\text{where
}S=\emptyset,\\\ \mathfrak{b}_{0}\cdot\mathfrak{p}_{11,3}^{n_{1}},&\text{where
}S=\\{\mathfrak{p}_{11,3}\\}\\\
\mathfrak{b}_{0}\cdot\mathfrak{p}_{5,1}^{2}\cdot\mathfrak{p}_{11,3}^{n_{1}},&\text{where
}S=\\{\mathfrak{p}_{11,3}\\}.\end{cases}$ (14)

In each case, $\mathfrak{b}_{0}$ is an ideal of ${\mathcal{O}}_{K}$ of norm
$R=2^{5}\cdot 3^{8}$. To compute this ideal, we first note that

$2\cdot{\mathcal{O}}_{K}\,=\,\mathfrak{p}_{2,1}^{5},\qquad
3\cdot{\mathcal{O}}_{K}\,=\,\mathfrak{p}_{3,1}\mathfrak{p}_{3,2},$

where

$\mathfrak{p}_{2,1}\,=\,\Big{\langle}2,\frac{1}{7920}(\theta^{3}+557\theta^{2}+4263\theta+6939)\Big{\rangle},\quad\mathfrak{p}_{3,1}\,=\,\Big{\langle}3,\frac{1}{2}(\theta+11)\Big{\rangle},\quad\mathfrak{p}_{3,2}\,=\,\langle
3,\theta+3\rangle;$

the ideals $\mathfrak{p}_{2,1}$ and $\mathfrak{p}_{3,1}$ have degree $1$, and
the ideal $\mathfrak{p}_{3,2}$ has degree $4$. Applying Algorithm 1 to $p=2$
and $p=3$, we obtain

$\displaystyle M_{3}$ $\displaystyle=\emptyset\quad\text{ and }\quad
L_{3}=\\{\mathfrak{p}_{3,2}\\},$ $\displaystyle M_{2}$
$\displaystyle=\emptyset\quad\text{ and }\quad
L_{2}=\\{1\cdot{\mathcal{O}}_{K}\\}\quad\text{ or }\quad
L_{2}=\\{\mathfrak{p}_{2,1}^{5}\\}\quad\text{ or }\quad
L_{2}=\\{\mathfrak{p}_{2,1}^{8}\\}.$

The $p$-part of $\mathfrak{b}_{0}$ is composed of these sets $M_{p}$, $L_{p}$.
In particular, the only possible $2$-part of $\mathfrak{b}_{0}$ is
$\mathfrak{p}_{2,1}^{5}$ as
$\operatorname{ord}_{2}(\operatorname{Norm}(\mathfrak{p}_{2,1}^{5}))=5=\operatorname{ord}_{2}(R)$.
However, since

$\operatorname{ord}_{3}(\operatorname{Norm}(\mathfrak{p}_{3,2}))=4\neq
8=\operatorname{ord}_{3}(R),$

the $3$-part of $\mathfrak{b}_{0}$ cannot be made up of any elements of
$M_{3}$ or $L_{3}$. In other words, there are no ideals $\mathfrak{b}_{0}$
having norm $R=2^{5}\cdot 3^{8}$ satisfying (14). Thus none of the $4$ ideal
equations listed in (14) are possible. We may thus conclude that the
Thue–Mahler equation

$F(X,Y)=-2^{5}\cdot 3^{4}\cdot 5^{z_{1}}\cdot
11^{z_{2}},\qquad\gcd(X,Y)=\gcd(3,Y)=1$

has no solutions. Moreover, we may also conclude that there are no ideals
$\mathfrak{b}_{0}$ having norm $3^{8}$ and therefore the Thue–Mahler form
$F(X,Y)=\pm 3^{4}\cdot m$ has no solutions for any $m$ coprime to $3$.

##  4\. Making the Ideals Principal

From now on we fix $(\mathfrak{a},S)\in\mathcal{Z}$ and we focus on a solution
of (13). The method of Tzanakis and de Weger [30] reduces (13) to at most
$(m/2)\cdot h^{s}$ $S$-unit equations, where $m$ is the number of roots of
unity and $h$ is the class number of $K$. Our method, explained below, gives
at most only $m/2$ $S$-unit equations.

Given an ideal $\mathfrak{b}$ of ${\mathcal{O}}_{K}$, we denote its class in
the class group $\operatorname{Cl}(K)$ by $[\mathfrak{b}]$.

######  Lemma 4.1.

Let

$\phi:\mathbb{Z}^{s}\rightarrow\operatorname{Cl}(K),\qquad(m_{1},\dotsc,m_{s})\mapsto[\mathfrak{p}_{1}]^{m_{1}}\cdots[\mathfrak{p}_{s}]^{m_{s}}.$

  1. (a)

If $[\mathfrak{a}]^{-1}$ is not in the image of $\phi$ then (13) has no
solutions.

  2. (b)

Suppose $[\mathfrak{a}]^{-1}=\phi(\mathbf{r})$, where
$\mathbf{r}=(r_{1},\dotsc,r_{s})$. Let $\zeta$ be a generator of the roots of
unity in $K$, and suppose it has order $m$. Let $\delta_{1},\dotsc,\delta_{r}$
be a basis for the group of $S$-units ${\mathcal{O}}_{S}^{\times}$ modulo the
torsion subgroup $\langle\zeta\rangle$. Let $\alpha$ be a generator of the
principal ideal
$\mathfrak{a}\cdot\mathfrak{p}_{1}^{r_{1}}\cdots\mathfrak{p}_{s}^{r_{s}}$. Let
$(X,Y)$ satisfy (13). Then, after possibly replacing $(X,Y)$ by $(-X,-Y)$, we
have

$a_{0}X-\theta Y\;=\;\tau\cdot\delta_{1}^{b_{1}}\cdots\delta_{r}^{b_{r}}$ (15)

where $\tau=\zeta^{a}\cdot\alpha$ with $0\leq a\leq\frac{m}{2}-1$, and
$b_{1},\dotsc,b_{r}\in\mathbb{Z}$.

###### Proof.

Note that if (13) has a solution $\mathbf{n}=(n_{1},\dotsc,n_{s})$ then

$\phi(\mathbf{n})=[\mathfrak{a}]^{-1}.$

This proves $(a)$. For $(b)$, suppose
$[\mathfrak{a}]^{-1}=\phi(r_{1},\dotsc,r_{s})$. Thus
$\mathfrak{a}\cdot\mathfrak{p}_{1}^{r_{1}}\cdots\mathfrak{p}_{s}^{r_{s}}$ is
principal and we let $\alpha$ be a generator. Then the fractional ideal
$((a_{0}X-\theta Y)/\alpha){\mathcal{O}}_{K}$ is supported on
$S=\\{\mathfrak{p}_{1},\dotsc,\mathfrak{p}_{s}\\}$. Hence $(a_{0}X-\theta
Y)/\alpha\in{\mathcal{O}}_{S}^{\times}$. Now
$\zeta,\delta_{1},\dotsc,\delta_{r}$ is a basis for the $S$-unit group. Thus
(15) holds for some $0\leq a\leq m-1$, and $b_{1},\dotsc,b_{r}\in\mathbb{Z}$.
However $\zeta^{m/2}=-1$. Thus we can suppose $0\leq a\leq m/2-1$ by replacing
$(X,Y)$ by $(-X,-Y)$ if necessary. ∎

######  Lemma 4.2.

The denominator of the fractional ideal $\tau{\mathcal{O}}_{K}$ is supported
on the set of prime ideals
${S=\\{\mathfrak{p}_{1},\dotsc,\mathfrak{p}_{s}\\}}$.

###### Proof.

This follows immediately from (15) since $\delta_{1},\dotsc,\delta_{r}$ are
$S$-units. ∎

We have reduced the task of solving our original Thue–Mahler equation (3) to
solving equations of the form

$a_{0}X-\theta Y=\tau\cdot\delta_{1}^{b_{1}}\cdots\delta_{r}^{b_{r}},$ (16)

subject to the conditions

$X,~{}Y\in\mathbb{Z},\quad\gcd(X,Y)=1,\quad\gcd(a_{0},Y)=1,\quad
b_{i}\in\mathbb{Z}.$ (17)

For technical reasons we would like to exclude the case
$b_{1}=b_{2}=\cdots=b_{r}=0$; of course we can trivially test if this case
leads to a solution. Hence we shall henceforth suppose in addtion to (17) that

$\min\\{\lvert b_{1}\rvert,\dotsc,\lvert b_{r}\rvert\\}\;\geq\;1.$ (18)

We will tackle each of these equations (16) separately. In [30], the authors
work in the field generated by three conjugates of $\theta$ and its
completions. This is fine theoretically but difficult computationally. We will
work with that extension theoretically simply to obtain a bound for

$B:=\max\\{\lvert b_{1}\rvert,\dotsc,\lvert b_{r}\rvert\\}.$ (19)

(The reason for restriction (18) is that in Section 6 we work with $\log{B}$).
To reduce the bound, we will need to carry out certain computations; these
will take place only in $K$, $\mathbb{R}$, ${\mathbb{C}}$, but not in
extensions of $K$, and certainly not in extensions of $\mathbb{Q}_{p}$.

To obtain our initial bound for $B$ we shall mostly follow ideas found in
[13], [15], [21]. However, we have a key advantage that will allow us to
obtain sharper bounds: namely we assume knowledge of the $S$-unit basis
$\delta_{1},\dotsc,\delta_{r}$ rather than working with estimates for the size
of a basis.

###  4.1. Convention on the choice of $S$-unit basis

As before let $\zeta$ be a generator for the roots of unity in
${\mathcal{O}}_{K}^{\times}$. We note that the unit group
${\mathcal{O}}_{K}^{\times}$ is a subgroup of the $S$-unit group
${\mathcal{O}}_{S}^{\times}$. Moreover, it is saturated in the sense that the
quotient ${\mathcal{O}}_{S}^{\times}/{\mathcal{O}}_{K}^{\times}$ is torsion-
free. Hence there is a basis $\delta_{1},\dotsc,\delta_{r}$ for
${\mathcal{O}}_{S}^{\times}/\langle\zeta\rangle$ such that
$\delta_{1},\dotsc,\delta_{u+v-1}$ is a basis for
${\mathcal{O}}_{K}^{\times}/\langle\zeta\rangle$, where $(u,v)$ is the
signature of $K$. We shall in fact work with such a basis.

###  4.2. Examples continued

Table 1 gives some data for Examples 1–5. At this stage of the algorithm, we
would like to stress the main difference between our approach and that of
Tzanakis and de Weger [30]. When dealing with

$(a_{0}X-\theta
Y){\mathcal{O}}_{K}=\mathfrak{a}\cdot\mathfrak{p}_{1}^{n_{1}}\cdots\mathfrak{p}_{s}^{n_{s}},$

they write each exponent $n_{i}$ as $n_{i}=k_{i}h_{i}+m_{i}$, where $h_{i}$ is
the order of $\mathfrak{p}_{i}$ in the class group of ${\mathcal{O}}_{K}$ and
$0\leq m_{i}\leq h_{i}-1$. Now $\mathfrak{p}_{i}^{h_{i}}$ is principal and we
may write it as $(\beta_{i}){\mathcal{O}}_{K}$. It follows from (13) that
$\mathfrak{a}\cdot\mathfrak{p}_{1}^{m_{1}}\cdots\cdot\mathfrak{p}_{s}^{m_{s}}$
is principal. Clearly $h_{i}|h$ and there are at most $h^{s}$ possibilities
for this ideal. In the worst case, we expect around $h^{s-1}$ ideals to be
principal, and so of the form $(\tau){\mathcal{O}}_{K}$. This results in a
huge explosion of cases when $h$ is non-trivial, as it is often the case that
$h_{i}=h$. For instance, in our Example 2, the class number is $33$. There are
$16$ possibilities for $(\mathfrak{a},S)$ in $\mathcal{Z}$. The $16$ possible
values for $s=\\#S$ are

$0,~{}0,~{}1,~{}1,~{}1,~{}1,~{}1,~{}1,~{}2,~{}2,~{}2,~{}2,~{}2,~{}2,~{}3,~{}3,$

where all possible ideals in $S$ have order $33$ in ${\mathcal{O}}_{K}$.
Following the method of Tzanakis and de Weger, we would need to check $78608$
ideals if they are principal, and this approach leads to $2382$ equations of
the form (16). With our approach, as we need only to deal with $16$ ideal
equations, we expect to deal with at most $16$ equations of the form (16).
Indeed, in doing so, we obtain merely $14$ equations of the form (16).

| $\\#\mathcal{Z}$ | number of $(\tau,\delta_{1},\dotsc,\delta_{r})$ | rank frequencies
---|---|---|---
Example 1 | $16$ | $16$ |  $(1,2)$, $(2,6)$, $(3,6)$, $(4,2)$
Example 2 | $16$ | $14$ |  $(2,6)$, $(3,6)$, $(4,2)$
Example 3 | $12$ | $12$ |  $(7,6)$, $(8,6)$
Example 4 | $4096$ | $4096$ | $(10,4096)$
Example 5 | $2$ | $2$ |  $(9,1)$, $(10,1)$
Table 1. This table gives the sizes of the set $\mathcal{Z}$, the number of
resulting $(\tau,\delta_{1},\dotsc,\delta_{r})$ for Examples 1–5. The last
column is a list of pairs $(r,t)$ meaning there are $t$ cases where the
$S$-unit rank is $r$.

##  5\. Lower Bounds for Linear Forms in Logarithms

In this section, we state theorems of Matveev [26] and of Yu [33] for lower
bounds for linear forms in complex and $p$-adic logarithms. In the next
section, we will use these results to obtain bounds for $b_{1},\dots,b_{r}$.
We begin by establishing some notation, as well as some key results which we
will need for the lower bound.

$L$ |  | a number field.
---|---|---
$D$ |  | the degree $[L:\mathbb{Q}]$.
$M_{L}$ |  | the set of all places of $L$.
$M_{L}^{\infty}$ |  | the subset of infinite places.
$M_{L}^{0}$ |  | the subset of finite places.
$\nu$ |  | a place of $L$.
$D_{\nu}$ |  | the local degree $[L_{\nu}:\mathbb{Q}_{\nu}]$.
$\lvert\cdot\rvert_{\nu}$ |  | the usual normalized absolute value associated to $\nu$.
|  | If $\nu$ is infinite and associated to a real or complex embedding $\sigma$ of $L$,
|  | then $\lvert\alpha\rvert_{\nu}=\lvert\sigma(\alpha)\rvert$.
|  | If $\nu$ is finite and above the rational prime $p$, then $\lvert p\rvert_{\nu}=p^{-1}$.
$\lVert\cdot\rVert_{\nu}$ |  |  $=\lvert\cdot\rvert_{\nu}^{D_{\nu}}$.
$h(\cdot)$ |  | the absolute logarithmic height, defined in (24).

Let $L$ be a number field of degree $D$ over $\mathbb{Q}$. We shall write
$M_{L}$ for the set of all places of $L$, and $M_{L}^{\infty}$, $M_{L}^{0}$
for the subset of infinite and finite places, respectively. For $\nu\in
M_{L}$, we let $\lvert\cdot\rvert_{\nu}$ denote the usual normalized absolute
value corresponding to $\nu$. If $\nu$ is finite and $p$ is the rational prime
below $\nu$, then $\lvert p\rvert_{\nu}=p^{-1}$. We denote by $D_{\nu}$ the
local degree $[L_{\nu}:\mathbb{Q}_{\nu}]$, and define

$\lVert\alpha\rVert_{\nu}=\lvert\alpha\rvert_{\nu}^{D_{\nu}}.$ (20)

The product formula may be stated as

$\prod_{\nu\in M_{L}}\lVert\alpha\rVert_{\nu}=1$ (21)

for all $\alpha\in L^{\times}$. In particular, if $\nu$ is infinite,
corresponding to a real or complex embedding $\sigma$ of $L$, then

$\lvert\alpha\rvert_{\nu}=\lvert\sigma(\alpha)\rvert,\qquad\text{and}\qquad\lVert\alpha\rVert_{\nu}=\begin{cases}\lvert\sigma(\alpha)\rvert&\text{if
$\sigma$ is real,}\\\ \lvert\sigma(\alpha)\rvert^{2}&\text{if $\sigma$ is
complex.}\end{cases}$ (22)

If $\nu$ is finite, and $\mathfrak{P}$ is the prime ideal corresponding to
$\nu$, then for $\alpha\in L^{\times}$ we have

$\lVert\alpha\rVert_{\nu}=\operatorname{Norm}(\mathfrak{P})^{-\operatorname{ord}_{\mathfrak{P}}(\alpha)};$
(23)

this easily follows from $D_{\nu}=e(\mathfrak{P}|p)f(\mathfrak{P}|p)$, where
$e(\mathfrak{P}|p)$ and $f(\mathfrak{P}|p)$ are respectively the ramification
index and the inertial degree of $\mathfrak{P}$.

For $\alpha\in L$, we define the absolute logarithmic height $h(\alpha)$ by

$h(\alpha)=\frac{1}{[L:\mathbb{Q}]}\sum_{\nu\in
M_{L}}D_{\nu}\log\max\\{1,\lvert\alpha\rvert_{\nu}\\}=\frac{1}{[L:\mathbb{Q}]}\sum_{\nu\in
M_{L}}\log\max\\{1,\lVert\alpha\rVert_{\nu}\\}.$ (24)

######  Lemma 5.1.

The absolute logarithmic height of an algebraic number $\alpha$ is independent
of the number field $L$ containing $\alpha$. Moreover, if $\alpha$ and $\beta$
are Galois conjugates, then $h(\alpha)=h(\beta)$.

For proofs of the following two lemmata, see [15, Lemma 4.1] and [21, Lemma
3.2].

######  Lemma 5.2.

For $\alpha_{1},\dotsc,\alpha_{n}\in L$ we have

$h(\alpha_{1}\cdots\alpha_{n})\leq h(\alpha_{1})+\cdots+h(\alpha_{n}),\quad
h(\alpha_{1}+\cdots+\alpha_{n})\leq\log{n}+h(\alpha_{1})+\cdots+h(\alpha_{n}).$

For any $\alpha\in L^{\times}$, we have $h(\alpha)=h(\alpha^{-1})$. Moreover,
for any place $\nu\in M_{L}$,

$\log{\lVert\alpha\rVert_{\nu}}\leq[L:\mathbb{Q}]\cdot h(\alpha).$ (25)

######  Lemma 5.3.

Let $L$ be a number field of degree $D$. Let $\mathfrak{S}$ be a finite set of
finite places of $L$. Let
$\varepsilon\in{\mathcal{O}}_{\mathfrak{S}}^{\times}$. Let $\eta\in M_{L}$ be
a place of $L$ chosen so that $\lVert\varepsilon\rVert_{\eta}$ is minimal.
Then $\lVert\varepsilon\rVert_{\eta}\leq 1$ and

$h(\varepsilon)\leq\frac{(\\#M_{L}^{\infty}+\\#\mathfrak{S})}{D}\cdot\log(\lVert\varepsilon^{-1}\rVert_{\eta}).$

###  5.1. Lower bounds for linear forms in $\mathfrak{P}$-adic logarithms

Let $L$ be a number field of degree $D$. Let $\mathfrak{P}$ be a prime ideal
of ${\mathcal{O}}_{L}$ and let $p$ be a rational prime below $\mathfrak{P}$.
Let $\nu\in M_{L}^{0}$ correspond to $\mathfrak{P}$. Let
$\alpha_{1},\dotsc,\alpha_{n}\in L^{\times}$. Write $e=\exp(1)$.

Let

$\displaystyle h_{j}$
$\displaystyle:=\;\max\left\\{h(\alpha_{j}),\,\frac{1}{16e^{2}D^{2}}\right\\},\qquad
j=1,\dotsc,n\,;$ (26) $\displaystyle c_{1}(n,D)$
$\displaystyle:=\;(16eD)^{2n+2}\cdot n^{5/2}\cdot\log(2nD)\cdot\log(2D)\,;$
$\displaystyle c_{2}(n,\mathfrak{P})$
$\displaystyle:=\;e(\mathfrak{P}|p)^{n}\cdot\frac{p^{f(\mathfrak{P}|p)}}{f(\mathfrak{P}|p)\cdot\log{p}}\,;$
$\displaystyle c_{3}(n,D,\mathfrak{P},\alpha_{1},\dotsc,\alpha_{n})$
$\displaystyle:=\;c_{1}(n,D)\cdot c_{2}(n,\mathfrak{P})\cdot h_{1}\cdots
h_{n}\,.$

We shall make use of the following theorem of Yu [33].

######  Theorem 1 (K. Yu).

Let $b_{1},\dotsc,b_{n}$ be rational integers and let

$B=\max\\{\lvert b_{1}\rvert,\dotsc,\lvert b_{n}\rvert\\},$

and suppose $B\geq 3$. Let

$\Lambda=\alpha_{1}^{b_{1}}\cdots\alpha_{n}^{b_{n}}-1,$

and suppose $\Lambda\neq 0$. Then

$\log{\lVert\Lambda^{-1}\rVert_{\nu}}\;<\;c_{3}(n,D,\mathfrak{P},\alpha_{1},\dotsc,\alpha_{n})\cdot\log{B}.$

###### Proof.

Let

$c_{4}(n,D,\mathfrak{P})\;:=\;(16eD)^{2n+2}\cdot
n^{3/2}\cdot\log(2nD)\cdot\log(2D)\cdot
e(\mathfrak{P}|p)^{n}\cdot\frac{p^{f(\mathfrak{P}|p)}}{\left(f(\mathfrak{P}|p)\cdot\log{p}\right)^{2}}.$

As stated in [33, page 190], a consequence of the Yu’s Main Theorem is

$\operatorname{ord}_{\mathfrak{P}}(\Lambda)\;<\;n\cdot
c_{4}(n,D,\mathfrak{P})\cdot h_{1}\cdots h_{n}\cdot\log{B}.$

By (23) we have

$\log{\lVert\Lambda^{-1}\rVert_{\nu}}\;=\;\log{(\operatorname{Norm}(\mathfrak{P}))}\cdot\operatorname{ord}_{\mathfrak{P}}(\Lambda)\;=\;f(\mathfrak{P}|p)\cdot\log{p}\cdot\operatorname{ord}_{\mathfrak{P}}(\Lambda).$

The theorem follows. ∎

###  5.2. Lower bounds for linear forms in real or complex logarithms

We continue with the above notation. Let

$h_{j}^{\prime}=\sqrt{h(\alpha_{j})^{2}+\frac{\pi^{2}}{D^{2}}},\qquad
j=1,\dotsc,n.$ (27)

The following theorem is a version of Matveev’s bound for linear forms in
logarithms [26].

######  Theorem 2 (Matveev).

Let $\nu$ be an infinite place of $L$. Suppose $\Lambda\neq 0$. Let

$c_{5}(n,D,\alpha_{1},\dotsc,\alpha_{n})=6\cdot 30^{n+4}\cdot(n+1)^{5.5}\cdot
D^{n+2}\cdot\log(eD)\cdot h_{1}^{\prime}\cdots h_{n}^{\prime}.$

Then

$\log{\lVert\Lambda^{-1}\rVert_{\nu}}\;\leq\;c_{5}(n,D,\alpha_{1},\dotsc,\alpha_{n})\cdot(\log(en)+\log{B}).$

###### Proof.

This in fact follows from a version of Matveev’s theorem derived in [14]. Let
$\sigma$ be a real or complex embedding of $L$ corresponding to $\nu$. Let

$h_{j}^{\prime\prime}=\max\left\\{Dh(\alpha_{j}),\;\lvert\log(\sigma(\alpha_{j}))\rvert,\;0.16\right\\},$

where $\log(\sigma(\alpha_{j}))$ is the principal determination of the
logarithm (i.e. the imaginary part of $\log$ lies in $(-\pi,\pi]$). Let

$c_{6}(n,D)=3\cdot 30^{n+4}\cdot(n+1)^{5.5}\cdot D^{2}\cdot\log(eD).$

Then Theorem 9.4 of [14] asserts that

$\log{\lvert\Lambda\rvert_{\nu}}\geq-c_{6}(n,D)\cdot
h_{1}^{\prime\prime}\cdots h_{n}^{\prime\prime}\cdot(\log(en)+\log{B}).$

Since $\lVert\Lambda\rVert=\lvert\Lambda\rvert^{D_{\nu}}$, where $D_{\nu}$ is
either $1$ or $2$, we have

$\log{\lVert\Lambda^{-1}\rVert}\leq 2\cdot c_{6}(n,D)\cdot
h_{1}^{\prime\prime}\cdots h_{n}^{\prime\prime}\cdot(\log(en)+\log{B}).$

Thus it is sufficient to show that $h_{j}^{\prime\prime}\leq Dh_{j}^{\prime}$.
However,

$\log(\sigma(\alpha_{j}))=\log\lvert\sigma(\alpha_{j})\rvert+i\theta$

where $-\pi<\theta\leq\pi$. But by (20) and (25),

$\log\lvert\sigma(\alpha_{j})\rvert=\frac{1}{D_{\nu}}\log\lVert\alpha_{j}\rVert_{\nu}\leq\log\lVert\alpha_{j}\rVert_{\nu}\leq
D\cdot h(\alpha_{j}).$

Thus

$\lvert\log(\sigma(\alpha_{j}))\rvert\;\leq\;\sqrt{D^{2}\cdot
h(\alpha_{j})^{2}+\pi^{2}}\;=\;D\cdot h_{j}^{\prime}.$

It is now clear that $h_{j}^{\prime\prime}\leq D\cdot h_{j}^{\prime}$. ∎

##  6\. The $S$-Unit Equation

We now return to the task of studying the solutions of (16) satisfying (17),
(18). Here, we use the theorems of Matveev and Yu (recalled in the previous
section) to establish bounds for $b_{1},\dots,b_{r}$, following the ideas of
[13], [15] and [21], and taking care to keep our constants completely explicit
and as small as possible.

We begin by establishing the following notation:

$\theta$, $K$ |  | as defined in Section 1.
---|---|---
$d$ |  | the degree $[K:\mathbb{Q}]\geq 3$.
$S$ |  | a set $\\{\mathfrak{p}_{1},\dotsc,\mathfrak{p}_{s}\\}$ of prime ideals of $K$ satisfying
|  | conditions (a), (b) of Proposition 3.1.
$s$ |  | the cardinality $\\#S$ of the set $S$.
$\delta_{1},\dotsc,\delta_{r}$ |  | a basis for the $S$-unit group ${\mathcal{O}}_{S}^{\times}$ modulo torsion,
|  | also appearing in (16).
$\tau$ |  | a non-zero element of $K$, appearing in (16).
$X$, $Y$, $b_{1},\dotsc,b_{r}$ |  | a solution to (16) satisfying (17), (18).
$\varepsilon$ |  |  $=\delta_{1}^{b_{1}}\cdots\delta_{r}^{b_{r}}$. Thus (16) can be rewritten as
|  |  $a_{0}X-\theta Y=\tau\cdot\varepsilon$.
$\mu$ |  |  $=\tau\cdot\varepsilon=a_{0}X-\theta Y$.
$B$ |  |  $=\max\\{\lvert b_{1}\rvert,\dotsc,\lvert b_{r}\rvert\\}$.
$\theta_{1}$, $\theta_{2}$, $\theta_{3}$ |  | three conjugates of $\theta$ chosen below, with $\theta=\theta_{1}$.
$L$ |  | the extension $\mathbb{Q}(\theta_{1},\theta_{2},\theta_{3})\supseteq K$.
$D$ |  | the degree $[L:\mathbb{Q}]$.
$\sigma_{i}$ |  | the embedding $K\hookrightarrow L$, $\theta\mapsto\theta_{i}$.
$\mu^{(i)}$, $\varepsilon^{(i)}$, $\tau^{(i)}$, $\delta_{j}^{(i)}$ |  | the images of $\mu$, $\varepsilon$, $\tau$, $\delta_{j}$ under the embedding $\sigma_{i}$.
$\xi_{1}$, $\xi_{2}$, $\xi_{3}$ |  | defined in (28).

We want to write down an $S$-unit equation starting with (16). For this we
will need to work with three conjugates of $\theta$. Let $d=[K:\mathbb{Q}]$,
and let $\theta_{1},\dotsc,\theta_{d}$ be the conjugates of $\theta$ in some
splitting field $M\supseteq K$. We shall not need $M$ explicitly, but we
assume that we are able to compute the Galois group $G$ of $M/\mathbb{Q}$ as a
transitive permutation group on the conjugates $\theta_{i}$. From this we are
able to list all subgroups (up to conjugacy), and for each subgroup determine
if it fixes at least three conjugates of $\theta$. Let $H$ be a subgroup of
$G$ fixing at least three conjugates of $\theta$ with index $[G:H]$ as small
as possible. Let $L=M^{H}$ be the fixed field of $H$. Then
$L=\mathbb{Q}(\theta_{1},\theta_{2},\theta_{3})$ for some three conjugates of
$\theta$ (after a possible reordering of conjugates) and it has the property
that its degree is minimal amongst all extensions generated by three
conjugates. Write

$D:=[G:H]=[L:\mathbb{Q}].$

Again we shall not need the field $L$ explicitly, but only its degree $D$,
which we can deduce from the Galois group. We identify $\theta=\theta_{1}$,
and so can think of $K\subseteq L$.

Write $\mu=a_{0}X-\theta Y$. Let
$\varepsilon=\delta_{1}^{b_{1}}\cdots\delta_{r}^{b_{r}}$. Then
$\mu=\tau\cdot\varepsilon$. Let $\mu^{(i)}$, $\varepsilon^{(i)}$,
$\tau^{(i)}$, $\delta_{j}^{(i)}$ be the images of $\mu$, $\varepsilon$,
$\tau$, $\delta_{j}$ under the embeddings $\sigma_{i}:K\hookrightarrow L$,
$\theta\mapsto\theta_{i}$. We observe the following Siegel identity:

$(\theta_{3}-\theta_{2})\mu_{1}+(\theta_{1}-\theta_{3})\mu_{2}+(\theta_{2}-\theta_{1})\mu_{3}=0.$

Let

$\xi_{1}=(\theta_{3}-\theta_{2})\cdot\tau_{1},\qquad\xi_{2}=(\theta_{1}-\theta_{3})\cdot\tau_{2},\qquad\xi_{3}=(\theta_{2}-\theta_{1})\cdot\tau_{3}.$
(28)

Then

$\xi_{1}\varepsilon_{1}+\xi_{2}\varepsilon_{2}+\xi_{3}\varepsilon_{3}=0.$ (29)

Note that $\varepsilon_{1}$ is an $S$-unit in $K$ and $\varepsilon_{2}$,
$\varepsilon_{3}$ are Galois conjugates of $\varepsilon$. This equation will
serve as our $S$-unit equation. We would like to rewrite (29) in a manner that
makes it convenient to apply Theorems 1 and 2. Observe that (29) can be
rewritten as

$\frac{\xi_{3}\varepsilon_{3}}{\xi_{1}\varepsilon_{1}}\;=\;\left(\frac{-\xi_{2}}{\xi_{1}}\right)\left(\frac{\varepsilon_{2}}{\varepsilon_{1}}\right)\;-\;1.$
(30)

Let

$\alpha_{j}:=\frac{\delta_{j,2}}{\delta_{j,1}}\quad(j=1,\dotsc,r),\qquad\alpha_{r+1}:=\frac{-\xi_{2}}{\xi_{1}},\qquad
b_{r+1}=1.$

Then

$\frac{\xi_{3}\varepsilon_{3}}{\xi_{1}\varepsilon_{1}}\;=\;\Lambda$ (31)

where $\Lambda$ is the “linear form”

$\Lambda:\;=\;\alpha_{1}^{b_{1}}\cdots\alpha_{r+1}^{b_{r+1}}\;-\;1.$

We assume that we know $\theta$, $\tau$ and $\delta_{1},\dotsc,\delta_{r}$
explicitly and can therefore compute their absolute logarithmic heights. We
will use this to estimate the heights of other algebraic numbers, such as
$\xi_{i}$, $\alpha_{j}$, without computing their minimal polynomials. Then, by
Lemmas 5.1 at 5.2

$h(\xi_{i})\;\leq\;c_{7},\qquad c_{7}\;:=\;\log{2}+2h(\theta)+h(\tau).$

######  Lemma 6.1.

Let

$c_{8}\;:=\;2Dc_{7}.$

Let $\nu$ be any place of $L$. Then

$\log{\lVert(\varepsilon_{3}/\varepsilon_{1})^{-1}\rVert_{\nu}}\;\leq\;\log{\lVert\Lambda^{-1}\rVert_{\nu}}\;+\;c_{8}.$

###### Proof.

Note that

$\log{\lVert(\varepsilon_{3}/\varepsilon_{1})^{-1}\rVert_{\nu}}\;=\;\log{\lVert\Lambda^{-1}\rVert_{\nu}}\;+\;\log{\lVert\xi_{3}/\xi_{1}\rVert_{\nu}}.$

By Lemma 5.2

$\log{\lVert\xi_{3}/\xi_{1}\rVert_{\nu}}\;\leq\;D\cdot
h(\xi_{3}/\xi_{1})\;\leq\;D\cdot(h(\xi_{3})+h(\xi_{1}))\,.$

∎

By definition $B=\max\\{\lvert b_{1}\rvert,\dotsc,\lvert b_{r}\rvert\\}$.
However, by (18), and since $b_{r+1}=1$, we have

$B=\max\\{\lvert b_{1}\rvert,\dotsc,\lvert b_{r}\rvert,\lvert
b_{r+1}\rvert\\}.$

We now apply Matveev’s theorem in order to obtain a bound for $B$.

######  Lemma 6.2.

Let

$h_{j}^{*}\;:=\;\sqrt{4h(\delta_{j})^{2}+\frac{\pi^{2}}{D^{2}}}\quad\text{for
$j=1,\dotsc,r$},\quad\text{and}\qquad
h_{r+1}^{*}\;:=\;\sqrt{4c_{7}^{2}+\frac{\pi^{2}}{D^{2}}}.$

Let

$c_{9}\;=\;6\cdot 30^{r+5}\cdot(r+2)^{5.5}\cdot D^{r+3}\cdot\log(eD)\cdot
h_{1}^{*}\cdots h_{r+1}^{*}\,,$

and

$c_{10}\;=\;c_{8}+c_{9}\cdot\log(e(r+1)).$

Let $\nu$ be an infinite place of $L$. Then

$\log{\lVert(\varepsilon_{3}/\varepsilon_{1})^{-1}\rVert_{\nu}}\;\leq\;c_{10}\;+\;c_{9}\cdot\log{B}.$

###### Proof.

We will apply Theorem 2 with $n=r+1$. Observe that

$h(\alpha_{j})\leq 2h(\delta_{j})\qquad\text{for
$j=1,\dotsc,r$},\quad\text{and}\qquad h(\alpha_{r+1})\leq 2c_{7}.$

Thus $h_{j}^{\prime}\leq h_{j}^{*}$ where $h_{j}^{\prime}$ is defined in (27).
By Theorem 2,

$\log{\lVert\Lambda^{-1}\rVert_{\nu}}\;\leq\;c_{9}\cdot(\log(e(r+1))+\log{B}).$

Lemma 6.1 completes the proof. ∎

We also apply Yu’s theorem.

######  Lemma 6.3.

Let

$h_{j}^{\dagger}\;:=\;\max\left\\{2h(\delta_{j}),\,\frac{1}{16e^{2}D^{2}}\right\\}\qquad\text{for
$j=1,\dotsc,r$},$

and

$h_{r+1}^{\dagger}\;:=\;\max\left\\{2c_{7},\,\frac{1}{16e^{2}D^{2}}\right\\}\,.$

Let $T$ be the set of rational primes $p$ below the primes $\mathfrak{p}\in
S$. Let

$c_{11}:=\max_{p\in T}\;\max\left\\{\frac{u^{r+1}\cdot
p^{v}}{v\cdot\log{p}}\;:\;\text{$u$, $v$ are positive integers and $\;uv\leq
D/d$}\right\\},$

and

$c_{12}:=c_{1}(r+1,D)\cdot c_{11}\cdot h_{1}^{\dagger}\cdots
h_{r+1}^{\dagger}.$

Let $\nu$ be a finite place of $L$. Then

$\log{\lVert(\varepsilon_{3}/\varepsilon_{1})^{-1}\rVert_{\nu}}\;\leq\;c_{8}+c_{12}\log{B}.$

###### Proof.

Of course we may suppose that
$\lVert(\varepsilon_{3}/\varepsilon_{1})^{-1}\rVert_{\nu}\neq 1$. Let
$\mathfrak{P}$ be the prime ideal of ${\mathcal{O}}_{L}$ corresponding to
$\nu$. We will deduce the lemma from Theorem 1 combined with Lemma 6.1. For
this, it suffices to show that
${c_{3}(r+1,D,\mathfrak{P},\alpha_{1},\dotsc,\alpha_{r+1})\leq c_{12}}$.
Observe that $h_{j}\leq h_{j}^{\dagger}$ for $j=1,\dotsc,r+1$. Thus it is
enough to show that $c_{2}(r+1,\mathfrak{P})\leq c_{11}$.

Let $K_{i}=\mathbb{Q}(\theta_{i})\subseteq L$. Recall that $\varepsilon$ is an
$S$-unit and that $\varepsilon_{i}$ is the image of $\varepsilon$ under the
map $\sigma_{i}:K\rightarrow K_{i}$, $\theta\mapsto\theta_{i}$. As
$\lVert(\varepsilon_{3}/\varepsilon_{1})^{-1}\rVert_{\nu}\neq 1$, we see that
$\operatorname{ord}_{\mathfrak{P}}(\varepsilon_{i})\neq 0$ for $i=1$ or $3$.
Thus $\mathfrak{P}$ must be a prime above
$\mathfrak{p}_{i}:=\sigma_{i}(\mathfrak{p})$ of ${\mathcal{O}}_{K_{i}}$ for
some $\mathfrak{p}\in S$, where $i=1$ or $3$. In particular $\mathfrak{P}$ is
above some rational prime $p\in T$. However,
$e(\mathfrak{p}|p)=f(\mathfrak{p}|p)=1$ for all $\mathfrak{p}\in S$. Thus
$e(\mathfrak{P}|p)=e(\mathfrak{P}|\mathfrak{p}_{i})$ and
$f(\mathfrak{P}|p)=f(\mathfrak{P}|\mathfrak{p}_{i})$ for $i=1$ or $3$. Let
$u=e(\mathfrak{P}|p)$ and $v=f(\mathfrak{P}|p)$. We see that
$uv=e(\mathfrak{P}|\mathfrak{p}_{i})f(\mathfrak{P}|\mathfrak{p}_{i})\leq[L:K_{i}]=D/d$.
Now $c_{2}(r+1,\mathfrak{P})\leq c_{11}$ follows from the definitions of
$c_{2}$ and $c_{11}$. ∎

######  Lemma 6.4.

Let

$c_{13}\;:=\;\frac{\\#M_{K}^{\infty}+2\cdot\\#S}{d},$

and

$c_{14}\;:=\;2h(\tau)+c_{13}\cdot\max(c_{8},c_{10}),\qquad
c_{15}\;:=\;c_{13}\cdot\max(c_{9},c_{12}).$

Then

$h(\mu_{3}/\mu_{1})\;\leq\;c_{14}\,+\,c_{15}\cdot\log{B}.$

###### Proof.

Let $\mathfrak{S}$ be the prime ideals appearing in the support of
$\varepsilon_{3}/\varepsilon_{1}$. We will show that
$\\#\mathfrak{S}\leq(2D/d)\cdot\\#S$. Indeed, $\varepsilon_{i}$ belongs to
$K_{i}=\mathbb{Q}(\theta_{i})$ and its support in $K_{i}$ is contained in
$\sigma_{i}(S)$. Now a prime belonging to $\sigma_{i}(S)$ has at most
$[L:K_{i}]=D/d$ primes above it in $L$. Thus

$\\#\mathfrak{S}\;\leq\;(D/d)\cdot\\#\sigma_{1}(S)+(D/d)\cdot\\#\sigma_{3}(S)\;\leq(2D/d)\cdot\\#S$

as required. Moreover, since $[L:K]=D/d$, we have
$\\#M_{L}^{\infty}\leq(D/d)\cdot\\#M_{K}^{\infty}$.

Let $\eta\in M_{L}$ be the place of $L$ such that
$\lVert\varepsilon_{3}/\varepsilon_{1}\rVert_{\eta}$ is minimal. By Lemma 5.3

$h(\varepsilon_{3}/\varepsilon_{1})\;\leq\;\frac{\\#M_{L}^{\infty}+\\#\mathfrak{S}}{D}\cdot\lVert(\varepsilon_{3}/\varepsilon_{1})^{-1}\rVert_{\eta}.$

From the above inequalities for $\\#M_{L}^{\infty}$ and $\\#\mathfrak{S}$, we
deduce that

$h(\varepsilon_{3}/\varepsilon_{1})\;\leq\;c_{13}\cdot\lVert(\varepsilon_{3}/\varepsilon_{1})^{-1}\rVert_{\eta}.$

We now apply Lemmas 6.2 and 6.3 to obtain

$h(\varepsilon_{3}/\varepsilon_{1})\;\leq\;c_{13}\cdot\left(\max(c_{8},c_{10})\;+\;\max(c_{9},c_{12})\cdot\log{B}\right).$

Finally, observe that
$\mu_{3}/\mu_{1}=(\tau_{3}/\tau_{1})\cdot(\varepsilon_{3}/\varepsilon_{1})$
and thus

$h(\mu_{3}/\mu_{1})\;\leq\;2h(\tau)\,+\,h(\varepsilon_{3}/\varepsilon_{1}).$

∎

We shall henceforth suppose $(X,Y)\neq(\pm 1,0)$. As $\gcd(X,Y)=1$, this
forces $Y\neq 0$.

######  Lemma 6.5.

Let $\nu$ be a place of $L$. Let

$\kappa_{\nu}=\begin{cases}1&\text{if $\nu\in M_{L}^{0}$},\\\
1/2^{D_{\nu}}&\text{if $\nu\in M_{L}^{\infty}$}.\end{cases}$

Then

$\max\\{\lVert\mu_{1}\rVert_{\nu}\,,\,\lVert\mu_{3}\rVert_{\nu}\\}^{2}\;\geq\;\kappa_{\nu}\cdot\min\left\\{1,\lVert\theta_{1}-\theta_{3}\rVert_{\nu}\right\\}^{2}\cdot\max\\{1\,,\,\lVert\mu_{1}\rVert_{\nu}\\}\cdot\max\\{1\,,\,\lVert\mu_{3}\rVert_{\nu}\\}\,.$

###### Proof.

There is nothing to prove unless, $\lVert\mu_{i}\rVert_{\nu}\leq 1$ for both
$i=1$, $2$. In this case, it is enough to show that

$\max\\{\lVert\mu_{1}\rVert_{\nu}\,,\,\lVert\mu_{3}\rVert_{\nu}\\}\;\geq\;\kappa_{\nu}\cdot\lVert\theta_{1}-\theta_{3}\rVert_{\nu}.$
(32)

Suppose first that $\nu$ is finite and let $\mathfrak{P}$ be the prime ideal
of ${\mathcal{O}}_{L}$ corresponding to $\nu$. Then (32) is equivalent to

$\min\\{\operatorname{ord}_{\mathfrak{P}}(\mu_{1})\,,\,\operatorname{ord}_{\mathfrak{P}}(\mu_{3})\\}\;\leq\;\operatorname{ord}_{\mathfrak{P}}(\theta_{1}-\theta_{3}).$

Let
$k=\min\\{\operatorname{ord}_{\mathfrak{P}}(\mu_{1})\,,\,\operatorname{ord}_{\mathfrak{P}}(\mu_{3})\\}$.
Then $\mathfrak{P}^{k}\mid\mu_{i}$ for $i=1$, $3$. Recall that
${\mu_{i}=a_{0}X-\theta_{i}Y}$. Thus $\mathfrak{P}^{k}$ divides both

$(\theta_{1}-\theta_{3})a_{0}X\;=\;\theta_{1}\mu_{3}-\theta_{3}\mu_{1}\quad\text{and}\quad(\theta_{1}-\theta_{3})Y\;=\;\mu_{3}-\mu_{1}.$

However $\gcd(X,Y)=\gcd(a_{0},Y)=1$, thus
$\mathfrak{P}^{k}\mid(\theta_{1}-\theta_{3})$ as desired.

Next suppose $\nu$ is infinite. As $(\theta_{1}-\theta_{3})Y=\mu_{3}-\mu_{1}$,
and $Y\neq 0$ is a rational integer, we have

$\begin{split}\lVert\theta_{1}-\theta_{3}\rVert_{\nu}\;&\leq\;\lVert\mu_{1}-\mu_{3}\rVert_{\nu}\;\\\
&=\;\lvert\mu_{1}-\mu_{3}\rvert_{\nu}^{D_{\nu}}\;\\\
&\leq\;2^{D_{\nu}}\cdot\max\\{\lvert\mu_{1}\rvert_{\nu},~{}\lvert\mu_{3}\rvert_{\nu}\\}^{D_{\nu}}\\\
&\leq\;2^{D_{\nu}}\cdot\max\\{\lVert\mu_{1}\rVert_{\nu},~{}\lVert\mu_{3}\rVert_{\nu}\\}.\end{split}$

This completes the proof. ∎

######  Lemma 6.6.

Let

$c_{16}\;=\;c_{14}+\frac{3}{2}\log{2}+2h(\theta)+h(\tau)\,.$

Then

$h(\varepsilon)\;\leq\;c_{16}+c_{15}\cdot\log{B}\,.$ (33)

###### Proof.

First note that

$\begin{split}h(\mu_{3}/\mu_{1})\;&=\;\frac{1}{D}\sum_{\nu\in
M_{L}}\log\max\left\\{1,~{}\lVert\mu_{3}/\mu_{1}\rVert_{\nu}\right\\}\\\
&=\;\frac{1}{D}\sum_{\nu\in
M_{L}}\log\max\left\\{1,~{}\lVert\mu_{3}/\mu_{1}\rVert_{\nu}\right\\}+\frac{1}{D}\sum_{\nu\in
M_{L}}\log{\lVert\mu_{1}\rVert_{\nu}}\quad\text{(from
\eqref{eqn:productformula})}\\\ &=\;\frac{1}{D}\sum_{\nu\in
M_{L}}\log\max\\{\lVert\mu_{1}\rVert,~{}\lVert\mu_{3}\rVert_{\nu}\\}\\\
&\geq\;\frac{1}{2}(h(\mu_{1})+h(\mu_{3}))+\frac{1}{D}\sum_{\nu\in
M_{L}}\left(\frac{1}{2}\log{\kappa_{\nu}}+\log\min\\{1,~{}\lVert(\theta_{1}-\theta_{3})\rVert_{\nu}\\}\right)\end{split}$

by Lemma 6.5. However $\mu_{1}$, $\mu_{3}$ are conjugates of $\mu$, thus
$h(\mu_{1})=h(\mu_{3})=h(\mu)$. Moreover,

$\frac{1}{D}\sum_{\nu\in
M_{L}}\frac{1}{2}\log{\kappa_{\nu}}\;=\;-\frac{\log{2}}{2D}\sum_{\nu\in
M_{L}^{\infty}}D_{\nu}\;=\;-\frac{1}{2}\log{2}\,.$

Thus

$\begin{split}h(\mu)\;&\leq\;h(\mu_{3}/\mu_{1})\,+\,\frac{1}{2}\log{2}\,-\,\frac{1}{D}\sum_{\nu\in
M_{L}}\log\min\\{1,~{}\lVert(\theta_{1}-\theta_{3})\rVert_{\nu}\\}\\\
&=\;h(\mu_{3}/\mu_{1})\,+\,\frac{1}{2}\log{2}\,+\,\frac{1}{D}\sum_{\nu\in
M_{L}}\log\max\\{1,~{}\lVert(\theta_{1}-\theta_{3})^{-1}\rVert_{\nu}\\}\\\
&=\;h(\mu_{3}/\mu_{1})\,+\,\frac{1}{2}\log{2}\,+\,h((\theta_{1}-\theta_{3})^{-1})\\\
&\leq\;h(\mu_{3}/\mu_{1})\,+\,\frac{3}{2}\log{2}\,+\,2h(\theta)\,,\end{split}$

by Lemmas 5.1 and 5.2. But $\varepsilon=\tau^{-1}\mu$, thus

$h(\varepsilon)\;\leq\;h(\mu_{3}/\mu_{1})\,+\,\frac{3}{2}\log{2}\,+\,2h(\theta)\,+\,h(\tau)\,.$

Applying Lemma 6.4 completes the proof. ∎

It is worthwhile to take stock for a moment. The inequality (33) relates the
height of $\varepsilon=\delta_{1}^{b_{1}}\cdots\delta_{r}^{b_{r}}$ to
$B=\max\\{\lvert b_{1}\rvert,\dotsc,\lvert b_{r}\rvert\\}$. The constants
$c_{7},\dotsc,c_{16}$ are given explicitly in terms of $\theta$, $\tau$,
$\delta_{1},\dotsc,\delta_{r}$ (all belonging to $K$), the prime ideals of $K$
belonging to $S$, the signature of $K$, and the degree $D$, which can be
deduced from the Galois group of the minimal polynomial of $\theta$. We do not
need the field $L$ explicitly.

######  Lemma 6.7.

Let $U$ be any subset of $S\cup M_{K}^{\infty}$ of size $r$. Let $\mathcal{M}$
be the $r\times r$-matrix

$\mathcal{M}=(\,\log{\lVert\delta_{j}\rVert_{\nu}}\,)_{\nu\in U,~{}1\leq j\leq
r}\,.$

The matrix $\mathcal{M}$ is invertible. Let $c_{17}$ be the largest of the
absolute values of the entries of $\mathcal{M}^{-1}$. Then

$B\;\leq\;2d\cdot c_{17}\cdot h(\varepsilon).$

###### Proof.

The determinant of $\mathcal{M}$ is in fact

$\pm\left(\prod_{\nu\in U}D_{\nu}\right)\cdot R(\delta_{1},\dotsc,\delta_{r})$

where $R(\delta_{1},\dotsc,\delta_{r})$ is the regulator of system of
$S$-units $\delta_{1},\dotsc,\delta_{r}$, and therefore does not vanish (c.f.
[13, Section 3]). Consider the vectors
$\mathbf{b}:=\big{[}b_{j}\big{]}_{j=1,\dotsc,r}$ and
$\mathbf{u}:=\big{[}\log{\lVert\varepsilon\rVert_{\nu}}\big{]}_{\nu\in U}$ in
$\mathbb{R}^{r}$. As $\varepsilon=\delta_{1}^{b_{1}}\cdots\delta_{r}^{b_{r}}$
we see that $\mathbf{u}=\mathcal{M}\mathbf{b}$ and so
$\mathbf{b}=\mathcal{M}^{-1}\mathbf{u}$. It follows, for $j=1,\dotsc,r$ that

$\begin{split}\lvert b_{j}\rvert\;\;&\leq\;c_{17}\cdot\sum_{\nu\in
U}\lvert\log{\lVert\varepsilon\rVert_{\nu}}\rvert\\\
&\leq\;c_{17}\cdot\sum_{\nu\in
M_{K}}\log{\max\\{1,\lVert\varepsilon\rVert_{\nu}\\}}+\log{\max\\{1,\lVert\varepsilon^{-1}\rVert_{\nu}\\}}\\\
&=\;2d\cdot c_{17}\cdot h(\varepsilon)\end{split}$

as required. ∎

Remark. Observe that there are $r+1$ possibilities for the set $U$. To compute
$c_{17}$ in practice, we iterate across all such sets and select $c_{17}$ as
the smallest possible value across each of the associated $r+1$ matrices
$\mathcal{M}$.

######  Proposition 6.8.

Let

$c_{18}\;:=\;2d\cdot c_{17}\cdot c_{16}\,,\qquad c_{19}\;:=\;2d\cdot
c_{17}\cdot c_{15}\,,\qquad
c_{20}\;:=\;2c_{18}\,+\,\max\\{2c_{19}\log{c_{19}},~{}4e^{2}\\}.$

Then

$B\;\leq\;c_{20}.$ (34)

###### Proof.

Combining Lemma 6.7 with (33) we have

$B\;\leq\;2d\cdot
c_{17}\cdot\big{(}c_{16}+c_{15}\cdot\log{B}\big{)}\;\leq\;c_{18}+c_{19}\log{B}.$

The Proposition follows from a result of Pethő and de Weger (Lemma B.1 of [27,
Appendix B]). ∎

###  6.1. Example 5 continued

We give some further details for Example 5. Here $a_{0}=5$ and the minimal
polynomial for $\theta$ is

$x^{11}+x^{10}+20x^{9}+25x^{8}+750x^{7}+625x^{6}+18750x^{5}+468750x^{3}+7812500x-19531250.$

The field $K=\mathbb{Q}(\theta)$ has degree $11$, and signature $(1,5)$. In
this case we have $2$ possibilities for $(\tau,\delta_{1},\dotsc,\delta_{r})$;
one has $S$-unit rank $r=9$ and the other has $S$-unit rank $r=10$. We take a
closer look at one of these $2$ possibilities, with $r=10$:

$\displaystyle\tau=\frac{1}{5^{8}}$
$\displaystyle(11114\theta^{10}-156626\theta^{9}-3960\theta^{8}+713050\theta^{7}+3733000\theta^{6}-129663750\theta^{5}+175803125\theta^{4}$
$\displaystyle-184687500\theta^{3}+1457890625\theta^{2}-70168750000\theta+134298828125),$
$\displaystyle\delta_{1}=\frac{1}{5^{9}}$
$\displaystyle(62639\theta^{10}-748196\theta^{9}-4621980\theta^{8}-22207025\theta^{7}+38965000\theta^{6}-34195000\theta^{5}-449543750\theta^{4}$
$\displaystyle-21271312500\theta^{3}-51765703125\theta^{2}-209809765625\theta+942912109375),$
$\displaystyle\delta_{2}=\frac{1}{5^{8}}$
$\displaystyle(-304507\theta^{10}-1286200\theta^{9}-8286278\theta^{8}-14744530\theta^{7}-120138150\theta^{6}+295735000\theta^{5}$
$\displaystyle+31769375\theta^{4}+19645671875\theta^{3}-1856078125\theta^{2}+159741562500\theta-1543269140625),$
$\displaystyle\delta_{3}=\frac{1}{5^{9}}$
$\displaystyle(-506181269733\theta^{10}-15199081379048\theta^{9}+3417039996000\theta^{8}+20631263730850\theta^{7}$
$\displaystyle-862101634598875\theta^{6}-11248761245089375\theta^{5}+13277953474900000\theta^{4}-47969344104562500\theta^{3}$
$\displaystyle-481688292060625000\theta^{2}-5526042413395703125\theta+13231499496662109375),$
$\displaystyle\delta_{4}=\frac{1}{5^{9}}$
$\displaystyle(375938718\theta^{10}+1113068513\theta^{9}+9701253830\theta^{8}+28420450900\theta^{7}+337680104250\theta^{6}+897075371250\theta^{5}$
$\displaystyle+8807817215625\theta^{4}+17270145140625\theta^{3}+210084124843750\theta^{2}+411927193359375\theta+3744720025390625),$
$\displaystyle\delta_{5}=\frac{1}{5^{9}}$
$\displaystyle(-44039\theta^{10}-174484\theta^{9}-2041150\theta^{8}-12553050\theta^{7}-48229625\theta^{6}-380426875\theta^{5}-367550000\theta^{4}$
$\displaystyle-6470828125\theta^{3}+8499687500\theta^{2}-60500781250\theta+157595703125),$
$\displaystyle\delta_{6}=\frac{1}{5^{9}}$
$\displaystyle(156\theta^{10}+1076\theta^{9}+7590\theta^{8}+32475\theta^{7}+181375\theta^{6}+466250\theta^{5}+1753125\theta^{4}-4156250\theta^{3}$
$\displaystyle-7578125\theta^{2}-133984375\theta+267578125),$
$\displaystyle\delta_{7}=\frac{1}{5^{9}}$
$\displaystyle(3783\theta^{10}-10047\theta^{9}-20595\theta^{8}+94800\theta^{7}+2714750\theta^{6}-9815000\theta^{5}+11365625\theta^{4}$
$\displaystyle+6562500\theta^{3}+1218125000\theta^{2}-6610156250\theta+7017578125),$
$\displaystyle\delta_{8}=\frac{1}{5^{9}}$
$\displaystyle(21\theta^{10}-169\theta^{9}+680\theta^{8}-325\theta^{7}-2500\theta^{6}-11875\theta^{5}+459375\theta^{4}$
$\displaystyle-3640625\theta^{3}+20156250\theta^{2}-65625000\theta+72265625),$
$\displaystyle\delta_{9}=\frac{1}{5^{9}}$
$\displaystyle(-2386\theta^{10}-126366\theta^{9}-363925\theta^{8}+2473650\theta^{7}-14427125\theta^{6}-87118750\theta^{5}-55203125\theta^{4}+281968750\theta^{3}$
$\displaystyle-4114296875\theta^{2}-68742968750\theta+152501953125),$
$\displaystyle\delta_{10}=\frac{1}{5^{9}}$
$\displaystyle(-173\theta^{10}-1528\theta^{9}-4840\theta^{8}+6800\theta^{7}+54125\theta^{6}-298750\theta^{5}-4609375\theta^{4}$
$\displaystyle-19546875\theta^{3}-11953125\theta^{2}+270703125\theta+1181640625).$

The set $S$ is composed of the following five primes of ramification degree
$1$ and inertial degree $1$:

$\mathfrak{p}_{1}=\langle 11,3+\theta\rangle,\quad\mathfrak{p}_{2}=\langle
7,1+\theta\rangle,\quad\mathfrak{p}_{3}=\langle 5,\phi\rangle,\\\
\mathfrak{p}_{4}=\langle 3,5+\theta\rangle,\quad\mathfrak{p}_{5}=\langle
2,1+\theta\rangle,$ (35)

where

$\phi=\frac{1}{5^{9}}(4\theta^{10}+9\theta^{9}+185\theta^{8}+425\theta^{7}+4625\theta^{6}+13750\theta^{5}+131250\theta^{4}\\\
+750000\theta^{3}+3203125\theta^{2}+26953125\theta+5859375).$

The bound for $B$ given by Proposition 6.8 is

$B\leq 1.57\times 10^{222}.$

##  7\. Controlling the Valuations of $a_{0}X-\theta Y$

In this section and the next, we will suppose that we have a bound

$B\leq\mathcal{B}_{\infty}$ (36)

and we will explain a method for replacing this bound with what is hopefully a
smaller bound. Our subsequent constants will depend on $\mathcal{B}_{\infty}$.
Initially we may take $\mathcal{B}_{\infty}=c_{20}$ by Proposition 6.8.
However, if we succeed in obtaining a smaller bound for $B$, we may replace
$\mathcal{B}_{\infty}$ by that bound and repeat the process.

We shall replace the reduction step using linear forms in $\mathfrak{p}$-adic
logarithms as in the paper of Tzanakis and de Weger [30]. In particular we
will eliminate all computations with completions of extensions of $K$, as
these are extremely tedious and error-prone.

###  7.1. The bounds $\mathcal{B}_{\infty}$, $\mathcal{B}_{1}$ and
$\mathcal{B}_{2}$.

Henceforth $\mathcal{B}_{\infty}$, $\mathcal{B}_{1}$ and $\mathcal{B}_{2}$
will denote the known bounds for the $\infty$-norm, $1$-norm and $2$-norm of
our exponent vector $\mathbf{b}=\big{[}b_{j}\big{]}_{j=1,\dotsc,r}$:

$B:=\lVert\mathbf{b}\rVert_{\infty}\leq\mathcal{B}_{\infty},\qquad\lVert\mathbf{b}\rVert_{1}\leq\mathcal{B}_{1}\qquad\lVert\mathbf{b}\rVert_{2}\leq\mathcal{B}_{2}.$
(37)

Initially, thanks to Proposition 6.8, we can make the assignments

$\mathcal{B}_{\infty}=c_{20},\quad\mathcal{B}_{2}=\sqrt{r}\cdot\mathcal{B}_{\infty},\quad\mathcal{B}_{1}=r\cdot\mathcal{B}_{\infty},\quad\text{(initial
values for $\mathcal{B}_{\infty}$, $\mathcal{B}_{1}$, $\mathcal{B}_{2}$)}.$
(38)

However, as we progress in our algorithm, we will update the values of
$\mathcal{B}_{\infty}$, $\mathcal{B}_{1}$, $\mathcal{B}_{2}$ so that (37) is
still satisfied.

Given a lattice $L\subseteq\mathbb{Z}^{r}$ and a vector
$\mathbf{w}\in\mathbb{Z}^{r}$, we denote by $D(L,\mathbf{w})$ the shortest
length of a vector belonging to the coset $\mathbf{w}+L$. This value can be
computed using a closest vector algorithm. Indeed, for
$\mathbf{v}\in\mathbb{Z}^{r}$, write $\mathbf{c}(L,\mathbf{v})$ for the
closest vector in $L$ to $\mathbf{v}$ (if there is more than one at the
closest distance, choose any of them).

######  Lemma 7.1.

$D(L,\mathbf{w})=\lVert\mathbf{w}+\mathbf{c}(L,-\mathbf{w})\rVert_{2}$.

###### Proof.

Let $\mathbf{l}\in L$ and suppose

$\lVert\mathbf{w}+\mathbf{l}\rVert_{2}<\lVert\mathbf{w}+\mathbf{c}(L,-\mathbf{w})\rVert_{2}.$

Then

$\lVert\mathbf{l}-(-\mathbf{w})\rVert_{2}<\lVert\mathbf{c}(L,-\mathbf{w})-(-\mathbf{w})\rVert_{2}.$

Thus $\mathbf{l}$ is a vector belonging to $L$ that is strictly closer to
$-\mathbf{w}$ than $\mathbf{c}(L,-\mathbf{w})$ giving a contradiction. ∎

Our first goal is to use the bounds (37) to deduce bounds on the valuations
$\operatorname{ord}_{\mathfrak{p}}(a_{0}X-\theta Y)$ for $\mathfrak{p}\in S$.

######  Proposition 7.2.

Let $\mathfrak{p}\in S$ and let $p$ be the rational prime below
$\mathfrak{p}$. Let $k\geq 1$. Then there is some $\theta_{0}\in\mathbb{Z}$
such that

$\theta\equiv\theta_{0}\pmod{\mathfrak{p}^{k}}.$

Write

$\mathfrak{a}:=(p{\mathcal{O}}_{K})/\mathfrak{p},\qquad\tau{\mathcal{O}}_{K}=\mathcal{T}_{1}/\mathcal{T}_{2},$
(39)

where $\mathcal{T}_{1}$ and $\mathcal{T}_{2}$ are coprime ideals. The
following hold:

  1. (i)

If
$\gcd(\mathfrak{a}^{k},\theta-\theta_{0})\neq\gcd(\mathfrak{a}^{k},\mathcal{T}_{1})$
then

$\operatorname{ord}_{\mathfrak{p}}(a_{0}X-\theta Y)\leq k-1.$ (40)

Suppose
$\gcd(\mathfrak{a}^{k},\theta-\theta_{0})=\gcd(\mathfrak{a}^{k},\mathcal{T}_{1})$.
Let

$\mathfrak{b}:=\mathfrak{a}^{k}/\gcd(\mathfrak{a}^{k},\mathcal{T}_{1})\,.$

Let

$k^{\prime}\;:=\;\max_{\mathfrak{q}\mid\mathfrak{b}}\left\lceil\frac{\operatorname{ord}_{\mathfrak{q}}(\mathfrak{b})}{e(\mathfrak{q}|p)}\right\rceil\,;$

this is the smallest integer such that $\mathfrak{b}\mid p^{k^{\prime}}$.
Given $u\in K^{\times}$ whose support is coprime with $\mathfrak{b}$, denote
its image in
$({\mathcal{O}}_{K}/\mathfrak{b})^{\times}/(\mathbb{Z}/p^{k^{\prime}}\mathbb{Z})^{\times}$
by $\overline{u}$. Let

$\phi:\mathbb{Z}^{r}\rightarrow({\mathcal{O}}_{K}/\mathfrak{b})^{\times}/(\mathbb{Z}/p^{k^{\prime}}\mathbb{Z})^{\times},\qquad(n_{1},\dotsc,n_{r})\mapsto\overline{\delta_{1}}^{n_{1}}\cdots\overline{\delta_{r}}^{n_{r}}.$

Write

$\tau_{0}:=\frac{(\theta_{0}-\theta)}{\tau}.$

Then the support of $\tau_{0}$ is coprime with $\mathfrak{b}$.

  1. (ii)

If $\overline{\tau_{0}}$ does not belong to $\operatorname{Image}(\phi)$ then
(40) holds.

  2. (iii)

Suppose $\overline{\tau_{0}}=\phi(\mathbf{w})$ for some
$\mathbf{w}\in\mathbb{Z}^{r}$. Let $L=\operatorname{Ker}(\phi)$ and suppose
$D(L,\mathbf{w})>\mathcal{B}_{2}$. Then (40) holds.

###### Proof.

Let $\mathfrak{p}$, $p$, and $k$ be as in the statement of the proposition. We
suppose that

$\operatorname{ord}_{\mathfrak{p}}(a_{0}X-\theta Y)\geq k$ (41)

and show that this leads to a contradiction under the hypotheses of any of
(i), (ii), (iii). Recall $k\geq 1$. From the proof of Lemma 2.3, we know
$p\nmid Y$.

Since $e(\mathfrak{p}|p)=f(\mathfrak{p}|p)=1$, we have
${\mathcal{O}}_{K}/\mathfrak{p}^{k}\cong\mathbb{Z}/p^{k}$. Thus there is some
$\theta_{0}\in\mathbb{Z}$ such that $\theta-\theta_{0}\equiv
0\pmod{\mathfrak{p}^{k}}$. However, $a_{0}X-\theta Y\equiv
0\pmod{\mathfrak{p}^{k}}$ and so therefore $a_{0}X-\theta_{0}Y\equiv
0\pmod{\mathfrak{p}^{k}}$. However $a_{0}X-\theta_{0}Y\in\mathbb{Z}$. Thus,
recalling that $e(\mathfrak{p}|p)=1$, we have $a_{0}X-\theta_{0}Y\equiv
0\pmod{p^{k}}$. From (16)

$Y(\theta_{0}-\theta)\equiv\tau\cdot\delta_{1}^{b_{1}}\cdots\delta_{r}^{b_{r}}\pmod{(p{\mathcal{O}}_{K})^{k}}.$

Note that the prime $\mathfrak{p}$ belongs to the support of the $\delta_{i}$.
However the other primes $\mathfrak{p}^{\prime}\mid p$,
$\mathfrak{p}^{\prime}\neq\mathfrak{p}$ do not belong to the support of the
$\delta_{i}$. We now eliminate $\mathfrak{p}$; as in the statement of the
proposition we take $\mathfrak{a}:=(p{\mathcal{O}}_{K})/\mathfrak{p}$. Then

$Y(\theta_{0}-\theta)\equiv\tau\cdot\delta_{1}^{b_{1}}\cdots\delta_{r}^{b_{r}}\pmod{\mathfrak{a}^{k}}.$

Observe that $\mathfrak{a}$ is coprime to the support of the $\delta_{i}$ and
$Y$. Recall $\tau{\mathcal{O}}_{K}=\mathcal{T}_{1}/\mathcal{T}_{2}$ where
$\mathcal{T}_{1}$, $\mathcal{T}_{2}$ are coprime integral ideals. By Lemma
4.2, the ideal $\mathcal{T}_{2}$ is supported on $S$ and therefore coprime to
$\mathfrak{a}$. We therefore have a contradiction if
${\gcd(\theta_{0}-\theta,\mathfrak{a}^{k})\neq\gcd(\mathcal{T}_{1},\mathfrak{a}^{k})}$.
This proves (i). Suppose
$\gcd(\theta_{0}-\theta,\mathfrak{a}^{k})=\gcd(\mathcal{T}_{1},\mathfrak{a}^{k})$.
Then

$Y\cdot\tau_{0}\equiv\delta_{1}^{b_{1}}\cdots\delta_{r}^{b_{r}}\pmod{\mathfrak{b}},$

where $Y$, $\tau_{0}$, and $\delta_{i}$ all have support disjoint from
$\mathfrak{b}$. As in the proposition, $k^{\prime}$ is the smallest positive
integer such that $\mathfrak{b}\mid p^{k^{\prime}}$, and thus
$(\mathbb{Z}/p^{k^{\prime}}\mathbb{Z})^{\times}$ is a subgroup of
$({\mathcal{O}}_{K}/\mathfrak{b})^{\times}$ containing the image of $Y$. Note
that $\overline{Y}=\overline{1}$. Thus $\phi(\mathbf{b})=\overline{\tau_{0}}$.
If $\overline{\tau_{0}}\notin\operatorname{Image}(\phi)$, then we have a
contradiction, and so our original assumption (41) is false. This proves (ii).

Suppose now that $\overline{\tau_{0}}\in\operatorname{Image}(\phi)$ and write
$\overline{\tau_{0}}=\phi(\mathbf{w})$ with $\mathbf{w}\in\mathbb{Z}^{r}$.
Then $\mathbf{b}\in\mathbf{w}+L$. Thus $\lVert\mathbf{b}\rVert_{2}\geq
D(L,\mathbf{w})$. If $D(L,\mathbf{w})>\mathcal{B}_{2}$ then
$\lVert\mathbf{b}\rVert_{2}>\mathcal{B}_{2}$ and we contradict (37). This
proves (iii). ∎

Remarks.

  * •

$\theta_{0}$ can be easily computed using Hensel’s Lemma.

  * •

To apply the proposition in practice, it is necessary to compute the abelian
group structure of $({\mathcal{O}}_{K}/\mathfrak{b})^{\times}$ for ideals
$\mathfrak{b}$ of very large norm (but supported on the primes above $p$). For
this we may apply the algorithms in [18, Section 4.2].

  * •

$\mathbf{c}(-\mathbf{w},L)$ (and therefore $D(\mathbf{w},L)$) can be computed
using a closest vector algorithm such as Fincke and Pohst [20].

  * •

To effectively apply Proposition 7.2 in practice, we need to guess a value of
$k$ such that $D(L,\mathbf{w})>\mathcal{B}_{2}$. We expect $D(L,\mathbf{w})$
to be around $I^{1/r}$ where $I$ is the index $[\mathbb{Z}^{r}:L]$. Let us
make two simplifying assumptions: the first is that $\phi$ is surjective, and
the second is that $\gcd(\mathfrak{a}^{k},\mathcal{T}_{1})=1$ so that
$\mathfrak{b}=\mathfrak{a}^{k}$ and $k^{\prime}=k$. Then

$I=\frac{\\#({\mathcal{O}}_{K}/\mathfrak{a}^{k})^{\times}}{\\#(\mathbb{Z}/p^{k}\mathbb{Z})^{\times}}\approx\frac{\operatorname{Norm}(\mathfrak{a})^{k}}{{p^{k}}}=p^{(d-2)k}$

where $d$ is the degree of $K$. Thus we should expect a contradiction if
$p^{(d-2)k/r}$ is much bigger than $\mathcal{B}_{2}$, or equivalently

$k\gg\frac{r\log{\mathcal{B}_{2}}}{(d-2)\log{p}}.$

This heuristic gives a good guide for which values of $k$ to try.

###  7.2. Example 5 continued

We continue giving details for Example 5, and in particular for the specific
tuple $(\tau,\delta_{1},\dotsc,\delta_{10})$ given on page 6.1. In Section 6
we noted that $B\leq 1.57\times 10^{222}$. Thus we take

$\mathcal{B}_{\infty}=1.57\times
10^{222},\qquad\mathcal{B}_{2}=\sqrt{10}\cdot\mathcal{B}_{\infty}\approx
4.96\times 10^{222}.$ (42)

We let $\mathfrak{p}=\mathfrak{p}_{1}=\langle 11,3+\theta\rangle$ which is a
prime above $11$. The above heuristic suggests that we choose $k$ to be larger
than

$\frac{10\log{\mathcal{B}_{2}}}{(11-2)\cdot\log{11}}\approx 237.60\,.$

Our program tries $k=238$. It turns out (in the notation of Proposition 7.2)
that
$\gcd(\mathfrak{a}^{k},\theta-\theta_{0})=\gcd(\mathfrak{a}^{k},\mathcal{T}_{1})=1$,
thus $\mathfrak{b}=\mathfrak{a}^{k}$, and moreover $k^{\prime}=k=238$. The map
$\phi$ is surjective, and thus $L$ does indeed have index

$I=\frac{\\#({\mathcal{O}}_{K}/\mathfrak{a}^{k})^{\times}}{\\#(\mathbb{Z}/p^{k}\mathbb{Z})^{\times}}=2^{7}\times
3^{2}\times 5\times 11^{2133}\times 61\times 7321\approx 5.02\times
10^{2230}.$

We do not give $L$ as its basis vectors are naturally huge. However, we find
that

$D(L,\mathbf{w})\approx 1.14\times 10^{223}.$

This is much larger than $\mathcal{B}_{2}$ and we therefore know from
Proposition 7.2 that $\operatorname{ord}_{\mathfrak{p}}(a_{0}X-\theta Y)\leq
k-1=237$.

It is interesting to note that $I^{1/10}\approx 1.18\times 10^{223}$ which is
rather close to $D(L,\mathbf{w})$. If instead we take $k=237$, we find that
$I^{1/10}\approx 1.36\times 10^{222}$ and ${D(L,\mathbf{w})\approx 9.55\times
10^{221}}$ which is somewhat less than $\mathcal{B}_{2}$. We have generally
found the above heuristic to be remarkably accurate in predicting a good
choice for $k$.

Now let $\mathfrak{p}_{1},\dotsc,\mathfrak{p}_{5}$ be the primes of $S$ as in
(35), where $\mathfrak{p}_{1}=\mathfrak{p}$ as above. Proposition 7.2 gives
upper bounds $237$, $292$, $354$, $518$, $821$ for
$\operatorname{ord}_{\mathfrak{p}_{j}}(a_{0}X-\theta Y)$ with $j=1,\dotsc,5$
respectively.

##  8\. Linear Forms in Real Logarithms

In this section, we determine bounds on linear forms in logarithms which we
will subsequently use in Section 9 to successively reduce the large upper
bound $\mathcal{B}_{\infty}$ established in Section 6.

We let $s:=\\#S$ and write

$S=\\{\mathfrak{p}_{1},\dotsc,\mathfrak{p}_{s}\\}.$

Using Proposition 7.2, we suppose that we have obtained, for $1\leq j\leq s$,
integers $k_{j}$ such that

$\operatorname{ord}_{\mathfrak{p}_{j}}(a_{0}X-\theta Y)\leq k_{j}-1.$ (43)

Recall that

$\delta_{1}^{b_{1}}\cdots\delta_{r}^{b_{r}}\;=\;\varepsilon\;=\;(a_{0}X-\theta
Y)/\tau\,.$ (44)

We write $k_{j}^{\prime}:=\operatorname{ord}_{\mathfrak{p}_{j}}(\tau)$, and
$k_{j}^{\prime\prime}:=k_{j}-1-k_{j}^{\prime}$. We obtain

$-k_{j}^{\prime}\;\leq\;\operatorname{ord}_{\mathfrak{p}_{j}}(\varepsilon)\;\leq\;k_{j}^{\prime\prime}\,.$
(45)

###  8.1. Updating $\mathcal{B}_{1}$ and $\mathcal{B}_{2}$

Recall that $\mathcal{B}_{\infty}$, $\mathcal{B}_{1}$, $\mathcal{B}_{2}$ are
respectively the known bounds for $\lVert\mathbf{b}\rVert_{\infty}$,
$\lVert\mathbf{b}\rVert_{1}$, $\lVert\mathbf{b}\rVert_{2}$ as in (37).
Initially we take these as in (38). In practice, we are often able to update
$\mathcal{B}_{1}$ and $\mathcal{B}_{2}$ with a smaller bound after each
iteration of Proposition 7.2. Let $(u,v)$ be the signature of $K$. Since $r$
is the rank of the $S$-unit group ${\mathcal{O}}_{S}^{\times}$, we have

$r=u+v-1+s.$

Recall our convention (page 4.1) on the choice of $S$-unit basis
$\delta_{1},\dotsc,\delta_{r}$: we suppose that the basis is chosen so that
$\delta_{1},\dotsc,\delta_{u+v-1}$ is in fact a basis for the unit group
modulo torsion. Thus $\log\lVert\delta_{i}\rVert_{\nu}=0$ for all $\nu\in
M_{K}^{0}$ and $1\leq i\leq u+v-1$. Let $\mathcal{M}_{0}$ denote the $s\times
s$ matrix

$\mathcal{M}_{0}=(\,\log{\lVert\delta_{j}\rVert_{\nu}}\,)_{\nu\in S,~{}u+v\leq
j\leq r}\,.$

In Lemma 6.7 let $U=\\{\nu_{1},\dotsc,\nu_{r}\\}$ where
$\nu_{1},\dotsc,\nu_{u+v-1}$ are any $u+v-1$ elements of $M_{K}^{\infty}$ and
the remainder are the elements of $S$. Then, in the notation of Lemma 6.7,

$\mathcal{M}=\left(\begin{array}[]{c|c}*&*\\\ \hline\cr
0&\mathcal{M}_{0}\end{array}\right).$

Since $\mathcal{M}$ is invertible by Lemma 6.7, it follows that
$\mathcal{M}_{0}$ is invertible. We partition our exponent vector $\mathbf{b}$
as

$\mathbf{b}=\big{[}\mathbf{b}^{\prime}|\mathbf{b}^{\prime\prime}\big{]},\qquad\mathbf{b}^{\prime}=\big{[}b_{i}\big{]}_{i=1,\dotsc,u+v-1},\qquad\mathbf{b}^{\prime\prime}=\big{[}b_{i}\big{]}_{i=u+v,\dotsc,r}.$

Write
$\mathbf{u}^{\prime\prime}:=\big{[}\log{\lVert\varepsilon\rVert_{\nu}}\big{]}_{\nu\in
S}$ in $\mathbb{R}^{s}$. By the above, we have
$\mathbf{u}^{\prime\prime}=\mathcal{M}_{0}\mathbf{b}^{\prime\prime}$ and thus
$\mathbf{b}^{\prime\prime}=\mathcal{M}_{0}^{-1}\mathbf{u}^{\prime\prime}$.
That is, for $1\leq i\leq s$,

$b_{u+v-1+i}=m_{i1}\log\lVert\varepsilon\rVert_{\mathfrak{p}_{1}}+\cdots+m_{is}\log\lVert\varepsilon\rVert_{\mathfrak{p}_{s}},$

where $\mathcal{M}_{0}^{-1}=\big{[}m_{ij}\big{]}$. It follows that

$|b_{u+v-1+i}|\;\leq\;|m_{i1}|\cdot\lvert\log\lVert\varepsilon\rVert_{\mathfrak{p}_{1}}\rvert+\cdots+|m_{is}|\cdot\lvert\log\lVert\varepsilon\rVert_{\mathfrak{p}_{s}}\rvert.$
(46)

Applying Proposition 7.2 to any $\mathfrak{p}_{j}$ for $1\leq j\leq s$ and
using (45) and (23), we obtain

$|\log\lVert\varepsilon\rVert_{\mathfrak{p}_{j}}|\leq\log(\operatorname{Norm}(\mathfrak{p}_{j}))\cdot\max\\{|k_{j}^{\prime}|,|k_{j}^{\prime\prime}|\\}.$

Write

$\rho_{i}^{\prime}:=\sum_{j=1}^{s}\lvert
m_{i,j}\rvert\cdot\log(\operatorname{Norm}(\mathfrak{p}_{j}))\cdot\max\\{|k_{j}^{\prime}|,|k_{j}^{\prime\prime}|\\},\qquad\rho_{i}=\min\\{\mathcal{B}_{\infty},\rho_{i}^{\prime}\\}.$
(47)

From equation (46) it follows that $\lvert
b_{u+v-1+i}\rvert\leq\rho_{i}^{\prime}$ for $1\leq i\leq s$. However,
$\max\\{\lvert
b_{i}\rvert\\}_{i=1}^{r}=\lVert\mathbf{b}\rVert_{\infty}\leq\mathcal{B}_{\infty}$,
so we know that $\lvert b_{u+v-1+i}\rvert\leq\mathcal{B}_{\infty}$. We deduce
that

$\lvert b_{u+v-1+i}\rvert\leq\rho_{i},\qquad 1\leq i\leq s.$ (48)

Hence

$\lVert\mathbf{b}\rVert_{1}\;=\;\lVert\mathbf{b}^{\prime}\rVert_{1}+\lVert\mathbf{b}^{\prime\prime}\rVert_{1}\;\leq\;(u+v-1)\mathcal{B}_{\infty}+\rho_{1}+\cdots+\rho_{s}$

and

$\lVert\mathbf{b}\rVert_{2}\;=\;\sqrt{\lVert\mathbf{b}^{\prime}\rVert_{2}^{2}+\lVert\mathbf{b}^{\prime\prime}\rVert_{2}^{2}}\;\leq\;\sqrt{(u+v-1)\mathcal{B}_{\infty}^{2}+\rho_{1}^{2}+\cdots+\rho_{s}^{2}}.$

We now update our values for $\mathcal{B}_{1}$ and $\mathcal{B}_{2}$:

$\mathcal{B}_{1}=(u+v-1)\mathcal{B}_{\infty}+\rho_{1}+\cdots+\rho_{s},$ (49)
$\mathcal{B}_{2}=\sqrt{(u+v-1)\mathcal{B}_{\infty}^{2}+\rho_{1}^{2}+\cdots+\rho_{s}^{2}}.$
(50)

Note, since by (47) we have $\rho_{i}\leq\mathcal{B}_{\infty}$, these new
values for $\mathcal{B}_{1}$ and $\mathcal{B}_{2}$ are bounded above by the
old values given in (38). In practice we usually find that these give
significantly better bounds for $\lVert\mathbf{b}\rVert_{1}$,
$\lVert\mathbf{b}\rVert_{2}$.

###  8.2. Embeddings and Improving the initial bound (36)

To improve our initial bound (36), we rely on the inequality ${B\leq
2c_{17}\cdot d\cdot h(\varepsilon)}$ furnished by Lemma 6.7. However
$h(\varepsilon)=h(\varepsilon^{-1})$ and so

$B\;\leq\;2c_{17}\sum_{\nu\in
M_{K}}\log{\max\\{1,\,\lVert\varepsilon^{-1}\rVert_{\nu}\\}}\,.$

However, since $\varepsilon$ is an $S$-unit, for $\nu\notin M_{K}^{\infty}\cup
S$, we have $\lVert\varepsilon\rVert_{\nu}=1$. Thus

$B\;\leq\;2c_{17}\sum_{\nu\in M_{K}^{\infty}\cup
S}\log{\max\\{1,\,\lVert\varepsilon^{-1}\rVert_{\nu}\\}}\,.$ (51)

Therefore, to obtain a better bound for $B$, it is enough to gain good control
on the contributions to the sum on the right hand-side of (51).

######  Lemma 8.1.

Let

$c_{21}\;=\;\sum_{i=1}^{s}\max\\{0,\,k_{i}^{\prime\prime}\\}\cdot\log{(\operatorname{Norm}(\mathfrak{p}_{i}))}\,.$

Then

$B\;\leq\;2c_{17}\left(c_{21}\,+\,\sum_{\nu\in
M_{K}^{\infty}}\log{\max\\{1,\,\lVert\varepsilon^{-1}\rVert_{\nu}\\}}\right)\,.$
(52)

###### Proof.

From (45) and (23) we have

$\sum_{\nu\in
S}\log\max\\{1,\lVert\varepsilon^{-1}\rVert_{\nu}\\}\;\leq\;c_{21}\,.$

The lemma now follows from (51). ∎

We shall write

$M_{K}^{\infty}\;=\;M_{K}^{\mathbb{R}}\,\cup\,M_{K}^{{\mathbb{C}}}\,,$

where $M_{K}^{\mathbb{R}}$ and $M_{K}^{{\mathbb{C}}}$ are respectively the
sets of real and complex places. Recall that $(u,v)$ denotes the signature of
$K$. Thus we have embeddings

$\sigma_{1},\dotsc,\sigma_{u},\qquad\sigma_{u+1},\dotsc,\sigma_{u+v},\overline{\sigma_{u+1}},\dotsc,\overline{\sigma_{u+v}}$

of $K$, where $\sigma_{i}$ are real embeddings for $1\leq i\leq u$, and
$\sigma_{u+i}$, $\overline{\sigma_{u+i}}$ are pairs of complex conjugate
embeddings. Let

$\mathcal{E}_{K}^{\mathbb{R}}\;:=\;\\{\sigma_{1},\dotsc,\sigma_{u}\\},\qquad\mathcal{E}_{K}^{{\mathbb{C}}}\;:=\;\\{\sigma_{u+1},\dotsc,\sigma_{u+v}\\}.$
(53)

For the membership of $\mathcal{E}_{K}^{{\mathbb{C}}}$, we are making an
arbitrary choice of a member from each pair of conjugate complex embeddings,
but that is unimportant. Note that $M_{K}^{\mathbb{R}}$ is in one-to-one
correspondence with $\mathcal{E}_{K}^{\mathbb{R}}$ and $M_{K}^{{\mathbb{C}}}$
is in one-to-one correspondence with $\mathcal{E}_{K}^{{\mathbb{C}}}$. We
consider the contribution to the sum (52) coming from $\nu\in
M_{K}^{{\mathbb{C}}}$, or equivalently from
$\sigma\in\mathcal{E}_{K}^{{\mathbb{C}}}$.

Let $\Im(z)$ denote the imaginary part of a complex number $z$.

######  Lemma 8.2.

If $v=0$ (i.e. $\mathcal{E}_{K}^{{\mathbb{C}}}=\emptyset$) then let
$c_{22}:=0$. Otherwise let

$c_{22}\;=\;2\sum_{\sigma\in\mathcal{E}_{K}^{{\mathbb{C}}}}\log\max\left\\{1,\,\frac{\lvert\sigma(\tau)\rvert}{\lvert\Im(\sigma(\theta))\rvert}\right\\}\,.$

Then

$B\;\leq\;2c_{17}\left(c_{21}\,+\,c_{22}\,+\,\sum_{\sigma\in\mathcal{E}_{K}^{\mathbb{R}}}\log{\max\\{1,\,\lvert\sigma(\varepsilon)\rvert^{-1}\\}}\right)\,.$
(54)

###### Proof.

Note that (52) can be rewritten as

$B\;\leq\;2c_{17}\left(c_{21}\,+\,2\sum_{\sigma\in\mathcal{E}_{K}^{{\mathbb{C}}}}\log{\max\\{1,\,\lvert\sigma(\varepsilon)\rvert^{-1}\\}}\,+\,\sum_{\sigma\in\mathcal{E}_{K}^{\mathbb{R}}}\log{\max\\{1,\,\lvert\sigma(\varepsilon)\rvert^{-1}\\}}\right)\,.$

Let $\sigma\in\mathcal{E}_{K}^{{\mathbb{C}}}$. Then, as $a_{0}X-\theta
Y=\tau\cdot\varepsilon$, we have

$\lvert\sigma(\varepsilon)\rvert\;=\;\frac{1}{\lvert\sigma(\tau)\rvert}\cdot\lvert\sigma(a_{0}X-\theta
Y)\rvert\;\geq\;\frac{1}{\lvert\sigma(\tau)\rvert}\cdot\lvert
Y\rvert\cdot\lvert\Im(\sigma(\theta))\rvert\;\geq\;\frac{\lvert\Im(\sigma(\theta))\rvert}{\lvert\sigma(\tau)\rvert}\,,$

because of our assumption $\lvert Y\rvert\neq 0$. The lemma follows. ∎

The following is immediate.

######  Proposition 8.3.

If $K$ is totally imaginary then

$B\;\leq\;{2c_{17}}({c_{21}+c_{22}})\,.$

###  8.3. The non-totally complex case

Suppose now that $K$ has one or more real embeddings. Recall that the
signature of $K$ is $(u,v)$. Thus $u\geq 1$.

######  Lemma 8.4.

If $u=1$ we let $c_{23}:=1$. If $u\,\geq\,2$ we let

$c_{23}:=\min\left\\{\frac{\lvert\sigma(\theta)-\sigma^{\prime}(\theta)\rvert}{\lvert\sigma(\tau)\rvert+\lvert\sigma^{\prime}(\tau)\rvert}\;:\;\sigma,~{}\sigma^{\prime}\in\mathcal{E}_{K}^{\mathbb{R}},\;\sigma\neq\sigma^{\prime}\right\\}\,.$

Then there is at most one $\sigma\in\mathcal{E}_{K}^{\mathbb{R}}$ such that
$\lvert\sigma(\varepsilon)\rvert<c_{23}$.

###### Proof.

Suppose otherwise. Then there are $\sigma$,
$\sigma^{\prime}\in\mathcal{E}_{K}^{\mathbb{R}}$ with
$\sigma\neq\sigma^{\prime}$ such that $\lvert\sigma(\varepsilon)\rvert<c_{23}$
and $\lvert\sigma^{\prime}(\varepsilon)\rvert<c_{23}$. As $a_{0}X-\theta
Y=\tau\cdot\varepsilon$ we find that

$\lvert
a_{0}X-\sigma(\theta)Y\rvert\;<c_{23}\cdot\lvert\sigma(\tau)\rvert,\qquad\lvert
a_{0}X-\sigma^{\prime}(\theta)Y\rvert\;<c_{23}\cdot\lvert\sigma^{\prime}(\tau)\rvert\,.$

Thus

$\lvert\sigma(\theta)-\sigma^{\prime}(\theta)\rvert\cdot\lvert
Y\rvert<c_{23}\cdot(\lvert\sigma(\tau)\rvert+\lvert\sigma^{\prime}(\tau)\rvert).$

Recall our assumption that $Y\neq 0$. This inequality now contradicts our
definition of $c_{23}$. ∎

######  Lemma 8.5.

Let

$c_{24}\;:=\;c_{21}\;+\;c_{22}\;+\;(u\,-\,1)\log\max\\{1,\,c_{23}^{-1}\\},$

and

$c_{25}\;:=\;\exp(c_{24})\,,\qquad c_{26}\;:=\frac{1}{2c_{17}}\,.$

Suppose $B>2c_{17}\cdot c_{24}$. Let $\sigma\in\mathcal{E}_{K}^{\mathbb{R}}$
be chosen so that $\lvert\sigma(\varepsilon)\rvert$ is minimal. Then

$\lvert\sigma(\varepsilon)\rvert\;\leq\;c_{25}\cdot\exp(-c_{26}\cdot B)\,.$
(55)

###### Proof.

From Lemma 8.4, we have

$\lvert\sigma^{\prime}(\varepsilon)\rvert\;\geq c_{23}$

for all $\sigma^{\prime}\in\mathcal{E}_{K}^{\mathbb{R}}$ with
$\sigma^{\prime}\neq\sigma$. From (54) we deduce that

$\begin{split}B\;&\leq\;2c_{17}\left(c_{21}\,+\,c_{22}\,+\,(u\,-\,1)\log\max\\{1,\,c_{23}^{-1}\\}\,+\,\log{\max\\{1,\,\lvert\sigma(\varepsilon)\rvert^{-1}\\}}\right)\\\
&=\;2c_{17}\left(c_{24}\,+\,\log{\max\\{1,\,\lvert\sigma(\varepsilon)\rvert^{-1}\\}}\right)\,.\end{split}$

It follows that

$\log\max\\{1,\,\lvert\sigma(\varepsilon)\rvert^{-1}\\}\;\geq\;\frac{1}{2c_{17}}B\,-\,c_{24}\;\geq\;c_{26}\cdot
B\,-\,c_{24}\,.$

The hypothesis $B>2c_{17}\cdot c_{24}$ forces the right hand-side to be
positive, and so the left hand-side must simply be
$\log{\lvert\sigma(\varepsilon)^{-1}\rvert}$. After exponentiating and
rearranging, we obtain (55). ∎

###  8.4. Approximate relations

As in Lemma 8.5 we shall let $\sigma\in\mathcal{E}_{K}^{\mathbb{R}}$ be the
real embedding that makes $\lvert\sigma(\varepsilon)\rvert$ minimal. Recall
that the signature of $K$ is $(u,v)$. Let

$n\;:=r+v\,.$ (56)

In this section we introduce additional unknown integers
$b_{r+1},\dotsc,{b_{n}}$, closely related to the exponents
$b_{1},\dotsc,b_{r}$ found in (16). We shall use Lemma 8.5 to write down $d-2$
linear forms in $b_{1},\dotsc,b_{n}$ with real coefficients, whose values are
very small. We shall later give a method, based on standard ideas originally
due to de Weger, that uses these ‘approximate relations’ to reduce our bound
for $B=\max(\lvert b_{1}\rvert,\dotsc,\lvert b_{r}\rvert,1)$.

We label the elements of $\mathcal{E}_{K}^{\mathbb{R}}$ and
$\mathcal{E}_{K}^{{\mathbb{C}}}$ as in (53), where $\sigma_{1}=\sigma$. Write

$\theta_{j}=\sigma_{j}(\theta),\quad\tau_{j}=\sigma_{j}(\tau),\quad\varepsilon_{j}=\sigma_{j}(\varepsilon),\quad\delta_{i,j}=\sigma_{j}(\delta_{i}),\qquad
1\leq j\leq u+v,\;1\leq i\leq r.$

Let $2\leq j\leq u+v$ and write

$z_{j}\;:=\;\frac{a_{0}X-\theta_{1}Y}{a_{0}X-\theta_{j}Y}\,.$

Observe that

$\begin{split}Y(\theta_{1}-\theta_{j})\;&=\;(a_{0}X-\theta_{j}Y)\;-\;(a_{0}X-\theta_{1}Y)\\\
&=\;(a_{0}X-\theta_{j}Y)\cdot(1-z_{j})\\\
&=\;\tau_{j}\cdot\delta_{1,j}^{b_{1}}\cdots\delta_{r,j}^{b_{r}}\cdot(1-z_{j}).\end{split}$
(57)

In the following lemma, as always, $\log$ denotes the principal determination
of the logarithm (i.e. the imaginary part of $\log$ lies in $(-\pi,\pi]$).

######  Lemma 8.6.

Let

$c_{27}\;:=\;\frac{\lvert\tau_{1}\rvert\cdot
c_{25}}{\min\\{\,{\lvert\tau_{i}\rvert}\;:\;\sigma_{i}\in\mathcal{E}_{K}^{\mathbb{R}}\,,\sigma_{i}\neq\sigma\\}\cdot
c_{23}}\,,\qquad c_{28}\;:=\>\frac{\lvert\tau_{1}\rvert\cdot
c_{25}}{\min\\{\,\lvert\Im(\theta_{i})\rvert\;:\;\sigma_{i}\in\mathcal{E}_{K}^{{\mathbb{C}}}\,\\}},$

and

$c_{29}(j)\;:=\begin{dcases}\frac{\lvert\tau_{1}\rvert\cdot
c_{25}}{\lvert\tau_{j}\rvert\cdot c_{23}}&\text{ for }\ 2\leq j\leq u\\\
\frac{\lvert\tau_{1}\rvert\cdot c_{25}}{\lvert\Im(\theta_{j})\rvert}&\text{
for }\ u+1\leq j\leq u+v.\end{dcases}$

Define

$c_{30}\;:=\;\max\\{2c_{17}\cdot
c_{24}\,,\;\log{(2c_{27})}/c_{26},\;\log{(2c_{28})}/c_{26}\\}$

and suppose $B\,>\,c_{30}$. Then

$\lvert\,\log(1-z_{j})\rvert\;\leq\;2c_{29}(j)\cdot\exp(-c_{26}\cdot
B)\,\qquad\text{for }2\leq j\leq u+v.$

###### Proof.

Let $2\leq j\leq u+v$. If $\sigma_{j}\in\mathcal{E}_{K}^{\mathbb{R}}$, Lemma
8.4 yields

$\lvert
a_{0}X-\theta_{j}Y\rvert\;=\;\lvert\tau_{j}\rvert\cdot\lvert\varepsilon_{j}\rvert\;\geq\;\lvert\tau_{j}\rvert\cdot
c_{23}\,.$

Conversely, if $\sigma_{j}\in\mathcal{E}_{K}^{{\mathbb{C}}}$, following the
proof of Lemma 8.2, we have

$\lvert
a_{0}X-\theta_{j}Y\rvert\;=\;\lvert\tau_{j}\rvert\cdot\lvert\varepsilon_{j}\rvert\;\geq\;\lvert\Im(\theta_{j})\rvert\,.$

Now, by Lemma 8.5 we have

$\lvert
a_{0}X-\theta_{1}Y\rvert\;=\;\lvert\tau_{1}\rvert\cdot\lvert\varepsilon_{1}\rvert\;\leq\;\lvert\tau_{1}\rvert\cdot
c_{25}\cdot\exp(-c_{26}\cdot B)\,;$

it is in invoking this lemma that we have made use of the assumption
$B>2c_{17}\cdot c_{24}$. Thus

$\lvert z_{j}\rvert\;\leq\;c_{29}(j)\cdot\exp(-c_{26}\cdot B)\,.$

Our assumption $B>c_{30}\geq\log{(2c_{29}(j))}/c_{26}$ gives $\lvert
z_{j}\rvert<1/2$. From the standard Maclaurin expansion for $\log(1-x)$ we
conclude that $\lvert\log(1-z_{j})\rvert\,\leq\,2\cdot\lvert z_{j}\rvert$,
completing the proof. ∎

To ease notation, let

$w\;:=\;u+v-2.$ (58)

We now give our first set of $w$ approximate relations. These only involve our
original unknown exponents $b_{1},\dotsc,b_{r}$ found in (16).

######  Lemma 8.7.

Suppose $B>c_{30}$ holds. Let $1\leq j\leq w$. Let

$\beta_{j}:=\log\left\lvert\frac{(\theta_{1}-\theta_{2})\cdot\tau_{j+2}}{(\theta_{1}-\theta_{j+2})\cdot\tau_{2}}\right\rvert\,,\qquad\alpha_{1,j}:=\log\left\lvert\frac{\delta_{1,{j+2}}}{\delta_{1,2}}\right\rvert\,,\ldots,\,\alpha_{r,j}:=\log\left\lvert\frac{\delta_{r,{j+2}}}{\delta_{r,2}}\right\rvert\,.$

Then

$\lvert\beta_{j}+b_{1}\alpha_{1,j}+\cdots+b_{r}\alpha_{r,j}\lvert\;\leq\;2(c_{29}(2)+c_{29}(j+2))\cdot\exp(-c_{26}\cdot
B).$ (59)

###### Proof.

From (57),

$\frac{(\theta_{1}-\theta_{2})\cdot\tau_{j+2}}{(\theta_{1}-\theta_{j+2})\cdot\tau_{2}}\cdot\left(\frac{\delta_{1,j+2}}{\delta_{1,2}}\right)^{b_{1}}\cdots\left(\frac{\delta_{r,j+2}}{\delta_{r,2}}\right)^{b_{r}}\;=\;\frac{1-z_{2}}{1-z_{j+2}}\,.$

Taking absolute values and then logs gives

$\lvert\beta_{j}+b_{1}\alpha_{1,j}+\cdots+b_{r}\alpha_{r,j}\lvert\;\leq\;\lvert\log\lvert
1-z_{2}\rvert\rvert+\lvert\log\lvert 1-z_{j+2}\rvert\rvert.$

For a complex number $w$, we have

$\lvert\log\lvert w\rvert\rvert\;\leq\;\lvert\log{w}\rvert$

since $\log\lvert w\rvert$ is the real part of $\log{w}$. The lemma now
follows from Lemma 8.6. ∎

In essence, in the above lemma, we have made use of the fact that

$K^{\times}\rightarrow\mathbb{R},\qquad\phi\mapsto\log\lvert\sigma(\phi)\rvert$
(60)

is a homomorphism for each embedding $\sigma$ of $K$, and applied this to the
approximate multiplicative relation (57) to obtain an approximate (additive)
relation (59). If $\sigma$ is complex, then $\sigma$ and its conjugate
$\overline{\sigma}$ induce the same homomorphism (60), and thus we need only
consider the embeddings $\sigma_{1},\dotsc,\sigma_{u+v}$. Note that although
these are $u+v$ embeddings, we have obtained only $u+v-2$ approximate
relations so far. That is, we have had to sacrifice embeddings because we
wanted to eliminate the two unknowns, $X$ and $Y$. For $\sigma$ real,
$\log\lvert\sigma(\phi)\rvert$ determines $\sigma(\phi)$ up to signs. However,
if $\sigma$ is complex, then (60) loses the argument of $\sigma(\phi)$. Thus
we should consider another homomorphism

$K^{\times}\rightarrow\mathbb{R}/\mathbb{Z}\pi,\qquad\phi\mapsto\Im(\log\sigma(\phi))$
(61)

where $\Im(z)$ denotes the imaginary part of a complex number $z$. Applying
these homomorphisms to (57) allows us to obtain additional approximate
relations. Since there are $v$ complex embeddings, we obtain an additional $v$
approximate relations. However since these homomorphism are into
$\mathbb{R}/\mathbb{Z}\pi$, the approximate relations are only valid after
shifting by an appropriate multiple of $\pi$; thus for each complex embedding
$\sigma_{u+j}$, we will need an additional parameter $b_{r+j}$.

Recall that $w=u+v-2$.

######  Lemma 8.8.

Let $1\leq j\leq v$. Let

$\beta_{w+j}:=\Im\left(\log\left(\frac{\theta_{1}-\theta_{u+j}}{\tau_{u+j}}\right)\right),$
$\alpha_{1,w+j}:=-\Im(\log\delta_{1,u+j})\,,\ldots,\,\alpha_{r,w+j}:=-\Im(\log\delta_{r,u+j})\,,\quad\alpha_{r+j,w+j}:=\pi\,.$

Suppose $B\,>\,c_{30}$ holds. Then there is some $b_{r+j}\in\mathbb{Z}$ such
that

$\lvert\beta_{w+j}+b_{1}\alpha_{1,w+j}+\cdots+b_{r}\alpha_{r,w+j}+b_{r+j}\alpha_{r+j,w+j}\lvert\\\
\;\leq\;2c_{29}(u+j)\cdot\exp(-c_{26}\cdot B).$ (62)

Moreover,

$\lvert b_{r+j}\rvert\;\leq\;\lvert b_{1}\rvert+\cdots+\lvert
b_{r}\rvert+\frac{\pi+1}{\pi}\,.$ (63)

###### Proof.

From (57), and Lemma 8.6,

$\lvert\log(Y)+\log((\theta_{1}-\theta_{u+j})/\tau_{u+j})-b_{1}\log{\delta_{1,u+j}}-\cdots-
b_{r}\log{\delta_{r,u+j}}+b^{\prime}\cdot\pi i\rvert\\\
\;\leq\;2c_{29}(u+j)\cdot\exp(-c_{26}\cdot B),$

for some $b^{\prime}\in\mathbb{Z}$. Thus

$\lvert\Im(\log(Y))+\beta_{w+j}+b_{1}\alpha_{1,w+j}+\cdots+b_{r}\alpha_{r,w+j}+b^{\prime}\pi\rvert\\\
\;\leq\;2c_{29}(u+j)\cdot\exp(-c_{26}\cdot B).$

Recall that $Y\in\mathbb{Z}\setminus\\{0\\}$, so $\Im(\log(Y))$ is either $0$
or $\pi$ depending on whether $Y$ is positive or negative. We take
$b_{r+j}=b^{\prime}$ in the former case and $b_{r+j}=b^{\prime}+1$ in the
latter case. This gives (62).

It remains to prove (63). Our assumption $B>c_{30}$ gives

$2c_{29}(u+j)\cdot\exp(-c_{26}\cdot B)<1.$

Moreover, $\lvert\beta_{w+j}\rvert\leq\pi$ and
$\lvert\alpha_{i,w+j}\rvert\leq\pi$ for $0\leq i\leq r$. From (62),

$\begin{split}\pi\cdot\lvert
b_{r+j}\rvert\;&=\;\lvert\alpha_{r+j,w+j}\rvert\cdot\lvert b_{r+j}\rvert\\\
&\leq\;\lvert\beta_{w+j}\rvert+\lvert\alpha_{1,w+j}\rvert\cdot\lvert
b_{1}\rvert+\cdots+\lvert\alpha_{r,w+j}\rvert\cdot\lvert b_{r}\rvert+1\\\
&\leq\;\pi(1+\lvert b_{1}\rvert+\cdots+\lvert b_{r}\rvert)+1.\\\ \end{split}$

The lemma follows. ∎

Summing up, Lemma 8.7 and Lemma 8.8 give us $(u+v-2)+v=d-2$ approximate
relations (59), (62) in integer unknowns $b_{1},\dotsc,b_{r+v}$.

##  9\. Reduction of Bounds

We do not know which real embedding $\sigma\in\mathcal{E}_{K}^{\mathbb{R}}$
makes $\lvert\sigma(\varepsilon)\rvert$ minimal. So the procedure described
below for reducing the bound (36) needs to be repeated for each possible
choice of embedding $\sigma$ in $\mathcal{E}_{K}^{\mathbb{R}}$. Thus, for
every possible choice of $\sigma\in\mathcal{E}_{K}^{\mathbb{R}}$, we let
$\sigma_{1}=\sigma$ and we choose an ordering of the other embeddings as in
(53). Given a real number $\gamma$, we denote by $[\gamma]$ the nearest
integer to $\gamma$, with the convention that $[k+1/2]=k+1$ for
$k\in\mathbb{Z}$. Let $n$ be as in (56) and observe that

$n=(s+1)+d-2,$

where we recall that $s=\\#S$. Let $C$ be a positive integer to be chosen
later. Let $\mathbf{I}_{m}$ and $\mathbf{0}_{i,j}$ be the $m\times m$ identity
matrix and $i\times j$ zero matrix, respectively. Let $M$ be the following
$n\times n$ matrix

$M:=\left[\begin{array}[]{c:@{}c@{}:@{}c@{}}\mathbf{0}_{w,s+1}&\begin{array}[]{ccc}[C\alpha_{1,1}]&\cdots&[C\alpha_{1,w}]\\\
\vdots&&\vdots\\\
[C\alpha_{w,1}]&\cdots&[C\alpha_{w,w}]\end{array}&\begin{array}[]{ccc}[C\alpha_{1,w+1}]&\cdots&[C\alpha_{1,d-2}]\\\
\vdots&&\vdots\\\
[C\alpha_{w,w+1}]&\cdots&[C\alpha_{w,d-2}]\end{array}\rule[-21.52771pt]{0.0pt}{0.0pt}\\\
\hdashline\mathbf{I}_{s+1}&\begin{array}[]{ccc}[C\alpha_{w+1,1}]&\cdots&[C\alpha_{w+1,w}]\\\
\vdots&&\vdots\\\
[C\alpha_{r,1}]&\cdots&[C\alpha_{r,w}]\end{array}&\begin{array}[]{ccc}[C\alpha_{w+1,w+1}]&\cdots&[C\alpha_{w+1,d-2}]\\\
\vdots&&\vdots\\\
[C\alpha_{r,w+1}]&\cdots&[C\alpha_{r,d-2}]\end{array}\rule[-21.52771pt]{0.0pt}{0.0pt}\rule{0.0pt}{25.83325pt}\\\
\hdashline\mathbf{0}_{v,s+1}&\mathbf{0}_{v,w}&[C\pi]\cdot\mathbf{I}_{v}\rule{0.0pt}{25.83325pt}\end{array}\right]$

and let $L$ be the sublattice of $\mathbb{Z}^{n}$ spanned by the rows of $M$.
Let

$\displaystyle\mathbf{w}:=(\underbrace{0,0,\dotsc,0}_{s+1},[C\beta_{1}],\dotsc,[C\beta_{d-2}])\in\mathbb{Z}^{n},$
$\displaystyle\mathcal{A}_{1}\;:=\;\frac{1+\mathcal{B}_{1}}{2},\qquad\mathcal{A}_{2}\;:=\;\frac{2\pi(1+\mathcal{B}_{1})+1}{2\pi},$
$\displaystyle\mathcal{B}_{3}\;:=\;\sum_{j=1}^{w}(c_{29}(2)+c_{29}(j+2))^{2}+\sum_{j=1}^{v}c_{29}(u+j)^{2},$
$\displaystyle\mathcal{B}_{4}\;:=\;\mathcal{A}_{1}\sum_{j=1}^{w}(c_{29}(2)+c_{29}(j+2))+\mathcal{A}_{2}\sum_{j=1}^{v}c_{29}(u+j),$
$\displaystyle\text{ and
}\quad\mathcal{B}_{5}\;:=\;\sqrt{\mathcal{B}_{2}^{2}-w\mathcal{B}_{\infty}^{2}+w\mathcal{A}_{1}^{2}+v\mathcal{A}_{2}^{2}}\,.$

######  Proposition 9.1.

Suppose $\mathbf{w}\notin L$ and $D(L,\mathbf{w})>\mathcal{B}_{5}$. Then

$B\;\leq\;\max\left(\;c_{30}\quad,\quad\frac{1}{c_{26}}\cdot\log{\left(\frac{2C\cdot\mathcal{B}_{3}}{\sqrt{\mathcal{B}_{3}(D(L,\mathbf{w})^{2}-\mathcal{B}_{5}^{2})+\mathcal{B}_{4}^{2}}\,-\,\mathcal{B}_{4}}\right)}\right)\,.$
(64)

###### Proof.

If $B\leq c_{30}$ then (64) holds. We will therefore suppose that $B>c_{30}$.
Thus, inequalities (59) and (62) hold. Write

$\mathbf{b}_{e}\,:=\,(b_{1},b_{2},\dotsc,b_{r},b_{r+1},\dotsc,b_{r+v})$

where $b_{r+1},\dotsc,b_{r+v}$ are as in Lemma 8.8. We think of this as the
‘extended exponent vector’. Note that the number of entries in
$\mathbf{b}_{e}$ is

$r+v=u+v+s-1+v=d+s-1=n.$

Write

$\mathbf{w}+\mathbf{b}_{e}\cdot
M\;=\;(b_{u+v-1},b_{u+v},\dotsc,b_{r},\Theta_{1},\Theta_{2},\dotsc,\Theta_{d-2})\,,$

where we take this equality as the definition of
$\Theta_{1},\dotsc,\Theta_{d-2}$. Thus, for $1\leq j\leq w$,

$\Theta_{j}\;=\;[C\beta_{j}]+b_{1}[C\alpha_{1,j}]+\cdots+b_{r}[C\alpha_{r,j}].$

Hence, again for $1\leq j\leq w$,

$\begin{split}\lvert\Theta_{j}\rvert\;&\leq\;\frac{1}{2}+\frac{\lvert
b_{1}\rvert}{2}+\cdots+\frac{\lvert
b_{r}\rvert}{2}\,+\,C\cdot\lvert\beta_{j}+b_{1}\alpha_{1,j}+\cdots+b_{r}\alpha_{r,j}\rvert\\\
\;&\leq\frac{1+\mathcal{B}_{1}}{2}\,+2C\cdot(c_{29}(2)+c_{29}(j+2))\cdot\exp(-c_{26}\cdot
B)\\\ \;&\leq\;\mathcal{A}_{1}\,+(c_{29}(2)+c_{29}(j+2))\cdot\eta,\\\
\end{split}$

where the second inequality follows by (36) and (59), and

$\eta:=2C\cdot\exp(-c_{26}\cdot B).$

Recall that $w:=u+v-2$. For $1\leq j\leq v$,

$\Theta_{w+j}\;=\;[C\beta_{w+j}]+b_{1}[C\alpha_{1,w+j}]+\cdots+b_{r}[C\alpha_{r,w+j}]+b_{r+j}[C\pi].$

Thus, for $1\leq j\leq v$,

$\displaystyle\lvert\Theta_{w+j}\rvert\;$
$\displaystyle\leq\;\frac{1}{2}+\frac{\lvert
b_{1}\rvert}{2}+\cdots+\frac{\lvert b_{r}\rvert}{2}+\frac{\lvert
b_{r+j}\rvert}{2}$
$\displaystyle\qquad\qquad+C\cdot\lvert\beta_{w+j}+b_{1}\alpha_{1,w+j}+\cdots+b_{r}\alpha_{r,w+j}+b_{r+j}\pi\rvert$
$\displaystyle\leq\;\frac{2\pi+1}{2\pi}+\mathcal{B}_{1}+\,2C\cdot
c_{29}(u+j)\cdot\exp(-c_{26}\cdot B)$
$\displaystyle\leq\;\mathcal{A}_{2}+c_{29}(u+j)\cdot\eta,$

where the second inequality follows from (36), (62), and (63).

Since $\mathbf{w}\notin L$, we have

$\begin{split}D(L,\mathbf{w})^{2}\;&\leq\;\lVert\mathbf{w}+\mathbf{b}_{e}\cdot
M\rVert_{2}^{2}\\\
&=\;b_{u+v-1}^{2}+\cdots+b_{r}^{2}+\Theta_{1}^{2}+\cdots+\Theta_{d-2}^{2}\\\
&=\;b_{u+v-1}^{2}+\cdots+b_{r}^{2}+w\mathcal{A}_{1}^{2}+v\mathcal{A}_{2}^{2}+(2\mathcal{B}_{4})\eta+\mathcal{B}_{3}\eta^{2}.\end{split}$

However, $\lvert
b_{u+v-1}\rvert\leq\lVert\mathbf{b}\rVert_{\infty}\leq\mathcal{B}_{\infty}$.
Moreover, by (48) we have $\lvert b_{u+v-1+i}\rvert\leq\rho_{i}$ for
$i=1,\dotsc,s$, where $\rho_{i}$ is given in (47). It follows that

$\begin{split}D(L,\mathbf{w})^{2}\;&\leq\;\mathcal{B}_{\infty}^{2}+\rho_{1}^{2}+\cdots+\rho_{s}^{2}+w\mathcal{A}_{1}^{2}+v\mathcal{A}_{2}^{2}+(2\mathcal{B}_{4})\eta+\mathcal{B}_{3}\eta^{2}\\\
&=\;\mathcal{B}_{2}^{2}-w\mathcal{B}_{\infty}^{2}+w\mathcal{A}_{1}^{2}+v\mathcal{A}_{2}^{2}+(2\mathcal{B}_{4})\eta+\mathcal{B}_{3}\eta^{2}\qquad\text{(from
\eqref{eqn:cB2new}})\\\
&=\;\mathcal{B}_{5}^{2}+(2\mathcal{B}_{4})\eta+\mathcal{B}_{3}\eta^{2}\\\
&=\;\mathcal{B}_{5}^{2}+\mathcal{B}_{3}\left(\eta+\frac{\mathcal{B}_{4}}{\mathcal{B}_{3}}\right)^{2}-\frac{\mathcal{B}_{4}^{2}}{\mathcal{B}_{3}}.\end{split}$

Recall our assumption that $\mathcal{B}_{5}\,<\,D(L,\mathbf{w})$. Thus

$\frac{\mathcal{B}_{4}^{2}}{\mathcal{B}_{3}}\;<\;D(L,\mathbf{w})^{2}-\mathcal{B}_{5}^{2}+\frac{\mathcal{B}_{4}^{2}}{\mathcal{B}_{3}}\;\leq\;\mathcal{B}_{3}\left(\eta+\frac{\mathcal{B}_{4}}{\mathcal{B}_{3}}\right)^{2},$

and so

$0\;<\;\frac{\sqrt{\mathcal{B}_{3}(D(L,\mathbf{w})^{2}-\mathcal{B}_{5}^{2})+\mathcal{B}_{4}^{2}}\,-\,\mathcal{B}_{4}}{\mathcal{B}_{3}}\;\leq\;\eta.$

However $\eta:=2C\cdot\exp(-c_{26}\cdot B)$. This yields the bound

$B\;\leq\;\frac{1}{c_{26}}\cdot\log{\left(\frac{2C\cdot\mathcal{B}_{3}}{\sqrt{\mathcal{B}_{3}(D(L,\mathbf{w})^{2}-\mathcal{B}_{5}^{2})+\mathcal{B}_{4}^{2}}\,-\,\mathcal{B}_{4}}\right)},$

which gives (64). ∎

Heuristic. It remains to decide on a reasonable choice for $C$. We expect that
the determinant of the matrix $M$ is approximately $C^{d-2}$. Thus the
distance between adjacent vectors in $L$ is expected to be in the region of
$C^{(d-2)/n}$, and so we anticipate (very roughly) that $D(L,\mathbf{w})\sim
C^{(d-2)/n}$. We would like $D(L,\mathbf{w})>\mathcal{B}_{5}$. Therefore it is
reasonable to choose $C\gg\mathcal{B}_{5}^{n/(d-2)}$. If, for a particular
choice of $C$, the condition $D(L,\mathbf{w})>\mathcal{B}_{5}$ fails, then we
simply try again with a larger choice of $C$.

Remark. Our approach is somewhat unusual in that it uses all $d-2$ available
approximate relations to reduce the initial bound. In contrast, it is much
more common to use one relation (e.g. [30, Section 16]) to reduce the bound.
In most examples, we have found that both approaches give similar reductions
in the size of the bound and that there is no advantage in using one over the
other. However in some examples the approach of using only one relation fails
spectacularly. Here are two such scenarios.

  1. (i)

Suppose $\delta_{1}$ (say) belongs to a proper subfield $K^{\prime}$ of $K$.
Now let $\sigma_{2}$, $\sigma_{3}$ be distinct embeddings of $K$ that agree on
$K^{\prime}$. Then, in the notation of Lemma 8.7 we find
$\alpha_{1,3}=\log\lvert\sigma_{3}(\delta_{1})/\sigma_{2}(\delta)\rvert=0$,
and so the coefficient of the unknown $b_{1}$ is zero in the approximate
relation (59). Therefore the one relation (59) on its own fails to provide any
information on the size of $b_{1}$. In practice, the lattice constructed in
[30, Section 16] from this one relation will contain the tiny vector
$(1,0,\dotsc,0)$, and this will result in the computational failure of the
closest vector algorithm.

  2. (ii)

We continue to suppose that $\delta_{1}$ belongs to the proper subfield
$K^{\prime}$ as above. Let $\sigma_{u+1}$ be a complex embedding of $K$ that
extends a real embedding of $K^{\prime}$, and suppose for simplicity that
$\sigma_{u+1}(\delta_{1})$ is positive. Then again, $\alpha_{1,w+1}=0$ in the
approximate relation (62), and so that relation on its own fails to control
$b_{1}$.

In the above two examples, we chose to illustrate the possible failure of the
approach of using one relation by imposing $\delta_{1}\in K^{\prime}$ where
$K^{\prime}$ is a subfield of $K$. However, a similar failure occurs (and is
more difficult to find) if the $S$-unit basis $\delta_{1},\dotsc,\delta_{r}$
is multiplicatively dependent over $K^{\prime}$, meaning that there is some
non-trivial $(c_{1},\dotsc,c_{r})\in\mathbb{Z}^{r}$ such that
$\delta_{1}^{c_{1}}\cdots\delta_{r}^{c_{r}}\in K^{\prime}$.

###  9.1. Example 5 continued

We continue giving details for the tuple
$(\tau,\delta_{1},\dotsc,\delta_{10})$ given on page 6.1. The values of
$\mathcal{B}_{\infty}$ and $\mathcal{B}_{2}$ are given in (42). The set $S$
consists of five primes $\mathfrak{p}_{1},\dotsc,\mathfrak{p}_{5}$ given by
(35). By applying Proposition 7.2 we had (page 7.2) obtained bounds $237$,
$292$, $354$, $518$, $821$ for
$\operatorname{ord}_{\mathfrak{p}_{j}}(a_{0}X-\theta Y)$ with $i=1,\dotsc,5$
respectively; these are the values denoted $k_{j}-1$ in (43). Now
$\operatorname{ord}_{\mathfrak{p}_{j}}(\tau)=0,0,1,0,0$ respectively for
$j=1,\dotsc,5$. Letting $\varepsilon$ be as in (44), we may take
$(-k_{j}^{\prime},k_{j}^{\prime\prime})$ in (45) to be $(0,237)$, $(0,292)$,
$(-1,353)$, $(0,518)$, $(0,821)$ respectively. This allows us to compute the
constant $c_{21}$ defined in Lemma 8.1. We find that $c_{21}\approx 2842.79$.
The field $K$ has signature $(u,v)=(1,5)$ and thus there is only one
possibility for $\sigma\in\mathcal{E}_{K}^{\mathbb{R}}$. We therefore take
$\sigma_{1}=\sigma$ to be the unique real embedding. For illustration, we give
the values of constants appearing in Section 8:

$\displaystyle c_{22}\approx 30.31,\quad c_{23}=1,\quad c_{24}\approx
2873.10,\quad c_{25}\approx 5.91\times 10^{1247},\quad c_{26}\approx 0.35,$
$\displaystyle c_{27}\approx 5.91\times 10^{1247},\quad c_{28}\approx
1.40\times 10^{1246},\quad c_{29}(2)\approx 1.25\times 10^{1246},$
$\displaystyle c_{29}(3)\approx 8.30\times 10^{1245},\quad c_{29}(4)\approx
7.83\times 10^{1245},\quad c_{29}(5)\approx 9.21\times 10^{1245},$
$\displaystyle c_{29}(6)\approx 1.40\times 10^{1246},\quad c_{30}\approx
8290.02.$

Lemma 8.7 gives $w=u+v-2=4$ approximate relations and Lemma 8.8 gives another
$v=5$ relations. Therefore we have $d-2=9$ relations altogether, and
$n=\\#S+d-2=15$. Therefore the matrix $M$ is $15\times 15$ and the lattice $L$
belongs to $\mathbb{Z}^{15}$. We find that

$\displaystyle\mathcal{B}_{1}\approx 7.85\times
10^{222},\quad\mathcal{A}_{1}\approx 3.92\times
10^{222},\quad\mathcal{A}_{2}\approx 7.85\times
10^{222},\quad\mathcal{B}_{3}\approx 2.59\times 10^{2493},$
$\displaystyle\mathcal{B}_{4}\approx 7.57\times 10^{1469},\quad\text{ and
}\quad\mathcal{B}_{5}\approx 1.93\times 10^{223}.$

In accordance with the above heuristic, our program chooses

$C=\left[\mathcal{B}_{5}^{n/(d-2)}\right]\approx 1.39\times 10^{372}.$

The matrix $M$ and the lattice $L$ are too huge to reproduce here, but we
point out that

$[\mathbb{Z}^{15}:L]\approx 2.66\times 10^{3357};\qquad D(L,\mathbf{w})\approx
7.23\times 10^{223}.$

Hence the hypothesis $D(L,\mathbf{w})>\mathcal{B}_{5}$ of Proposition 9.1 is
satisfied. We also find (rather unsurprisingly) that $\mathbf{w}\notin L$. We
may therefore apply Proposition 9.1 to obtain a new bound for $B$ given by
(64):

$B\leq 9270.82.$

We now start again with $\mathcal{B}_{\infty}=9270$ and repeat the previous
steps, first for obtaining bounds for
$\operatorname{ord}_{\mathfrak{p}_{j}}(a_{0}X-\theta Y)$ and then for writing
down the lattice $L$ and applying Proposition 9.1. The following table
illustrates the results.

Iteration | $\mathcal{B}_{\infty}$ | bounds for $\operatorname{ord}_{\mathfrak{p}_{j}}(a_{0}X-\theta Y)$
---|---|---
|  | with $1\leq j\leq 5$
0 | $1.57\times 10^{222}$ | 237 | 292 | 354 | 518 | 821
1 | 9270 | 4 | 5 | 8 | 10 | 15
2 | 251 | 3 | 3 | 5 | 6 | 10
3 | 190 | 2 | 3 | 5 | 6 | 9
4 | 180 | 2 | 3 | 5 | 6 | 9
5 | 180 | 2 | 3 | 5 | 6 | 9
Table 2. We successively reduce the bounds for $B$ and for
$\operatorname{ord}_{{\mathfrak{p}_{j}}}(a_{0}X-\theta Y)$ where
$j=1,\dotsc,5$.

Note that at the fifth iteration we fail to obtain any improvement on the
bounds, and so we stop there. Recall that $r=10$ and that $B=\max(\lvert
b_{1}\rvert,\dotsc,\lvert b_{10}\rvert)$, where $b_{1},\dotsc,b_{10}$ are the
exponents in (16). Our final bound is $B\leq 180$. The set of possible integer
tuples $(b_{1},\dotsc,b_{10})$ satisfying this bound has size

$(2\times 180+1)^{10}\;=\;362^{10}\approx 3.86\times 10^{25}.$

The huge size of this region does not allow brute force enumeration of the
solutions. Instead, one can reduce the number of tuples to consider by using
the bounds we have obtained for
$\operatorname{ord}_{\mathfrak{p}_{j}}(a_{0}X-\theta Y)$. We let
$\kappa_{j}=2$, $3$, $5$, $6$, $9$ for $j=1,\dotsc,5$, respectively. We know
that $0\leq\operatorname{ord}_{\mathfrak{p}_{j}}(a_{0}X-\theta
Y)\leq\kappa_{j}$, and so there are $\kappa_{j}+1$ possibilities for the
$\operatorname{ord}_{\mathfrak{p}_{j}}(a_{0}X-\theta Y)$. Let
$(k_{1},\dotsc,k_{5})$ be some tuple of integers satisfying $0\leq
k_{j}\leq\kappa_{j}$. The condition
$\operatorname{ord}_{\mathfrak{p}_{j}}(a_{0}X-\theta Y)=k_{j}$ simply defines
a hyperplane of codimension $1$ in the space of possible
$(b_{1},\dotsc,b_{10})$. Imposing all five conditions
$\operatorname{ord}_{\mathfrak{p}_{j}}(a_{0}X-\theta Y)=k_{j}$ with
$j=1,\dotsc,5$ cuts down the dimension from $10$ to $5$. Thus we expect that
the search region should (very roughly) have size

$(\kappa_{1}+1)\cdots(\kappa_{5}+1)\cdot 362^{5}\approx 3.13\times 10^{16}.$

This is still way beyond brute force enumeration and motivates our next
section.

##  10\. Sieving

In order to resolve the Thue–Mahler equation

$F(X,Y)=a\cdot p_{1}^{z_{1}}\cdots p_{v}^{z_{v}},\qquad
X,~{}Y\in\mathbb{Z},\;\gcd(X,Y)=\gcd(a_{0},Y)=1,$

we have first reduced the problem to that of resolving a number of equations
of the form (16), subject to the restrictions (17), (18). Recall that
$B=\max\\{\lvert b_{1}\rvert,\dotsc,\lvert b_{r}\rvert\\}$, where
$\mathbf{b}=(b_{1},\dotsc,b_{r})\in\mathbb{Z}^{r}$ denotes the vector of
unknown exponents to solve for. For each such equation (16), we have used the
theory of linear forms in logarithms to obtain a bound for $B$, and moreover,
we have explained how to repeatedly reduce this bound. During each of these
iterations, we have simultaneously reduced the bounds on the $\infty$-norm,