# Differences between perfect powers : the Lebesgue-Nagell equation

Michael A. Bennett  Department of Mathematics, University of British Columbia,
Vancouver, B.C., V6T 1Z2 Canada<EMAIL_ADDRESS>and  Samir Siksek
Mathematics Institute, University of Warwick, Coventry CV4 7AL, United Kingdom
<EMAIL_ADDRESS>
###### Abstract.

We develop a variety of new techniques to treat Diophantine equations of the
shape $x^{2}+D=y^{n}$, based upon bounds for linear forms in $p$-adic and
complex logarithms, the modularity of Galois representations attached to Frey-
Hellegouarch elliptic curves, and machinery from Diophantine approximation. We
use these to explicitly determine the set of all coprime integers $x$ and $y$,
and $n\geq 3$, with the property that $y^{n}>x^{2}$ and $x^{2}-y^{n}$ has no
prime divisor exceeding $11$.

###### Key words and phrases:

Exponential equation, Lucas sequence, shifted power, Galois representation,
Frey curve, modularity, level lowering, Baker’s bounds, Hilbert modular forms,
Thue equation

###### 2020 Mathematics Subject Classification:

Primary 11D61, Secondary 11D41, 11F80, 11F03

The first-named author is supported by NSERC. The second-named author is
supported by EPSRC Grant EP/S031537/1 “Moduli of elliptic curves and classical
Diophantine problems”.

##  1\. Introduction

Understanding the gaps in the sequence of positive perfect powers

$1,4,8,9,16,25,27,32,36,49,64,81,\ldots$

is a problem at once classical and fundamentally difficult. Mihăilescu’s
Theorem [26] (née Catalan’s Conjecture) tells us that $8$ and $9$ are the only
consecutive integers here, but it is not, for instance, a consequence of
current technology that there are at most finitely many gaps of length $k$,
for any fixed integer $k>1$ (though this was conjectured to be the case by
Pillai; see e.g. [29]). If we simplify matters by considering instead gaps
between squares and other perfect powers, then we can show that such gaps, if
nonzero, grow as we progress along the sequence. Indeed, the same is even true
of the greatest prime factor of the gaps. Specifically, we have the following,
a special case of Theorem 2 of Bugeaud [10]; here, by $P(m)$ we denote the
greatest prime divisor of a nonzero integer $m$.

######  Theorem 1 (Bugeaud).

Let $n\geq 3$ be an integer. There exists an effectively computable positive
constant $c=c(n)$ such that if $x$ and $y$ are coprime positive integers with
$y\geq 2$, then

$P(x^{2}-y^{n})\geq c\log n$

and, for suitably large $x$,

$P(x^{2}-y^{n})\geq\frac{\log\log y}{30n}.$

This result is a consequence of bounds for linear forms in logarithms, complex
and $p$-adic. As such, it can be made completely explicit and leads to an
algorithm for solving the Lebesgue-Nagell equation

(1) $x^{2}+D=y^{n},$

where we suppose that $x$ and $y$ are coprime nonzero integers, and that
either

  1. (i)

$D$ is a fixed integer, or

  2. (ii)

all the prime divisors of $D$ belong to a fixed set of primes $S$.

The terminology here stems from the fact that equation (1) with $D=1$ was
first solved by V. A. Lebesgue [21], while T. Nagell [27], [28] was the first
researcher to study such equations in a systematic fashion.

Regrettably, this algorithm is still, in most instances, not a practical one.
Even in the very special case $D=-2$, we are not able to completely solve
equation (1) (though there are a number of partial results available in the
literature; see e.g. Chen [14]). Almost all the (very ample) literature on
this problem concerns cases where $D>0$ and $y$ is odd in (1). Under these
assumptions, we may solve the equation through appeal to a beautiful result of
Bilu, Hanrot and Voutier [6] on primitive divisors in binary recurrence
sequences, at least for all but a few small values of $n$. Proposition 5.1 of
[12] (sharpening work of Cohn [15]) provides a very explicit summary of this
approach – one bounds the exponent $n$ in (1) in terms of the class numbers of
a finite collection of imaginary quadratic fields, depending only upon the
primes dividing $D$; see Section 3 for details. Smaller values of $n$ may be
treated via techniques from elementary or algebraic number theory, or through
machinery from Diophantine approximation. By way of example, in cases (i) and
(ii), equation (1), for fixed $n$, reduces to finitely many Thue or Thue-
Mahler equations, respectively. These can be solved through arguments of
Tzanakis and de Weger [35], [36], [37] (see also [16] for recent refinements).

In case either $D>0$ and $y$ is even, or if $D<0$, the literature on equation
(1) is much sparser, primarily since the machinery of primitive divisors is no
longer applicable. In these cases, other than bounds for linear forms in
logarithms, the only general results that we know to apply to equation (1) are
derived from the modularity of Galois representations arising from associated
Frey-Hellegouarch curves. These are obtained by viewing (1) as a ternary
equation of signature $(n,n,2)$, i.e. as $y^{n}-D\cdot 1^{n}=x^{2}$. Such an
approach can work to solve equation (1) in one of two ways, either by

  1. (a)

producing an upper bound upon $n$ that is sharper than that coming from linear
forms in logarithms, leaving a feasible set of small $n$ to treat, or

  2. (b)

failing to produce such an upper bound, but, instead, providing additional
arithmetic information that allows one to solve all the remaining Thue or
Thue-Mahler equations below the bound coming from linear forms in logarithms.

An example of situation (a) is the case where $D$ is divisible by only the
primes in $S=\\{5,11\\}$ and $y$ is even. Then Theorem 1.5 of [5] implies that
equation (1) has no nontrivial solutions for all prime $n>11$ and $y$ even;
work of Soydan and Tzanakis [34] treats smaller values of $n$ and the case
where $y$ is odd (where the Primitive Divisor Theorem works readily). In
general, we are potentially in situation (a) precisely when there fails to
exist an elliptic curve $E/\mathbb{Q}$ with nontrivial rational $2$-torsion
and conductor

$N_{S^{*}}=2\prod_{p\in S^{*}}p,$

for each subset $S^{*}\subseteq S$ with the property that the product of the
primes in $S^{*}$ is congruent to $-1$ modulo $8$. Other examples of such sets
$S$ include

$\\{5,19\\},\;\\{11,13,41\\},\;\\{11,17,29\\},\;\\{11,17,37\\},\;\\{17,19,37\\}\;\mbox{
and }\;\\{19,29\\}.$

For situation (b), papers of Bugeaud, Mignotte and the second author [12], and
of Barros [1] deal with a number of cases of equation (1) with $D$ fixed and
positive or negative, respectively.

In this paper, we will concentrate on the first of the two difficult cases,
namely when $D>0$ and $y$ is even in (1) (so that necessarily
$D\equiv-1{\text{\rm\ (mod~{}$8$)}}$), under the additional hypothesis that
$D$ is divisible only by a few small primes. For completeness, we will also
treat the easier situation where $y$ is odd, under like hypotheses on $D$. In
a companion paper [4], we will consider equation (1) in the other challenging
situation where $D<0$. Our main result in the paper at hand is the complete
resolution of equation (1) in case $D>0$, $P(D)<13$, $\gcd(x,y)=1$ and $n\geq
3$. We prove the following.

######  Theorem 2.

There are precisely $1240$ triples of positive integers $(x,y,n)$ with $n\geq
3$, $\gcd(x,y)=1$, $y^{n}>x^{2}$ and

$P(x^{2}-y^{n})<13.$

They are distributed as follows.

$\begin{array}[]{|c|c|c|c|c|c|c|c|}\hline\cr
n&\\#(x,y)&n&\\#(x,y)&n&\\#(x,y)&n&\\#(x,y)\\\ \hline\cr
3&755&7&5&12&4&26&1\\\ 4&385&8&17&13&1&&\\\ 5&11&9&1&14&4&&\\\
6&51&10&4&15&1&&\\\ \hline\cr\end{array}$

We provide the complete list of the $1240$ solutions at

http://homepages.warwick.ac.uk/staff/S.Siksek/progs/lebnag/lebesgue_nagell_solutions.txt

Proving this result amounts to solving the equation

(2)
$x^{2}+2^{\alpha_{2}}3^{\alpha_{3}}5^{\alpha_{5}}7^{\alpha_{7}}11^{\alpha_{11}}=y^{n},$

where $x,y$ and $n$ are positive integers, with $\gcd(x,y)=1$, $n\geq 3$, and
the $\alpha_{i}$ are nonnegative integers, i.e. equation (1), where $D>0$ is
supported only on primes in $S=\\{2,3,5,7,11\\}$. We note that earlier work
along these lines typically either treat cases where there are no $S$-units
congruent to $-1{\text{\rm\ (mod~{}$8$)}}$, so that the analogous equations
cannot have $y$ even (see e.g. the paper of Luca [22] for $S=\\{2,3\\}$), or
simply exclude these cases (see Pink [30] for $S=\\{2,3,5,7\\}$, where
solutions with $y$ even are termed exceptional). The only exceptions to this
in the literature, of which we are aware, are the aforementioned paper of
Soydan and Tzanakis [34] where $S=\\{5,11\\}$ and work of Koutsianas [18]
treating $S=\\{7\\}$ with prime exponent $n\equiv 13,23{\text{\rm\
(mod~{}$24$)}}$. A comprehensive survey of the extensive literature on this
equation can be found in the paper of Le and Soydan [20].

To solve equation (2) completely, we are forced to introduce a variety of new
techniques, many of which are applicable in rather more general settings.
These include

  * •

appeal to bounds for linear forms in two $p$-adic logarithms; what is
interesting here is that the resulting inequalities are surprisingly strong,
leading to problems involving complex logarithms that are essentially the same
level of difficulty as for the apparently easier case where $D>0$ is fixed in
equation (1) (as treated in [12])

  * •

efficient sieving with Frey-Hellegouarch curves; on some level, this is likely
the most important computational innovation in this paper

  * •

refined use of lower bounds for linear forms in two and three complex
logarithms

  * •

a computationally efficient approach to treat the genus one curves encountered
when solving equation (2) for $n\in\\{3,4\\}$

  * •

new practical techniques for solving Thue-Mahler equations of moderate ($n\leq
13$) degree.

The outline of this paper is as follows. In Section 2, we deal with the cases
of exponents $3$ and $4$ in equation (2). In Section 3, we apply the Primitive
Divisor Theorem to handle larger exponents in (2), under the assumption that
the variable $y$ is odd. Section 4 begins our treatment of the complementary
(significantly harder) situation when $y$ is even, showing how equation (2)
with fixed exponent $n$ reduces to solving a number of Thue-Mahler equations.
From this, we are able to solve (2) completely for $n\leq 11$. In Section 5,
we show how to associate to a putative solution of (2) a Frey-Hellegouarch
elliptic curve. We then use this connection to develop a number of
computational sieves that enable us to show that equation (2) has no solutions
with prime exponents $n$ between $17$ and a reasonably large upper bound
(which depends upon $D$, but is, in all cases, of order exceeding $10^{8}$).
This approach also deals with $n=13$, except for one case that is solved
through reduction to a Thue–Mahler equation. Finally, in Section 6, we apply
inequalities for linear forms in $p$-adic and complex logarithms to show that
(2) has no solutions for exponents $n$ exceeding these upper bounds.

##  2\. (Very) small values of $n$

We begin by treating equation (2) in case $n\in\\{3,4\\}$. With these handled,
we will thus be able to assume, without loss of generality, that $n\geq 5$ is
prime. It is worth observing that our methods of proof in this section work
equally well in the analogous situation where $D$ is supported on
$S=\\{2,3,5,7,11\\}$, but $D<0$ (a conclusion that is far from true regarding
our techniques for handling larger exponents).

###  2.1. Exponent $n=3$

If we suppose that $n=3$ in equation (2), then the problem reduces to one of
determining $S$-integral points on

$3^{\\#S}=3^{5}=243$

Mordell elliptic curves of the shape $y^{2}=x^{3}-k$, where

$k=2^{\delta_{2}}3^{\delta_{3}}5^{\delta_{5}}7^{\delta_{7}}11^{\delta_{11}},\;\;\mbox{
for }\;\;\delta_{p}\in\\{0,1,2\\}.$

There are various ways to carry this out; if we try to do this directly using,
say, the Magma computer algebra package [7], we very quickly run into problems
arising from the difficulty of unconditionally certifying Mordell-Weil bases
for some of the corresponding curves. We will instead argue somewhat
differently.

Given a solution to equation (2) in coprime integers $x$ and $y$, consider the
Frey-Hellegouarch elliptic curve

$E_{x,y}\;\;:\;\;Y^{2}=X^{3}-3yX+2x,$

with corresponding discriminant

$\Delta_{E_{x,y}}\,=\,2^{\alpha_{2}+6}3^{\alpha_{3}+3}5^{\alpha_{5}}7^{\alpha_{7}}11^{\alpha_{11}}.$

This model has $c$-invariants

$c_{4}=144y\;\mbox{ and }\;c_{6}=-1728x.$

We may check via Tate’s algorithm that this curve is minimal at all primes
$p\geq 3$ and, while possibly not minimal at $2$, the fact that $x$ and $y$
are coprime implies that a corresponding minimal model over $\mathbb{Q}$ has
either

$c_{4}=144y,\;c_{6}=-1728x\;\mbox{ or }\;c_{4}=9y,\;c_{6}=-27x,$

with the latter case occurring only if $xy$ is odd.

The isomorphism classes of elliptic curves over $\mathbb{Q}$ with good
reduction outside $\\{2,3,5,7,11\\}$ have recently been completely and
rigorously determined using two independent approaches, by von Kanel and
Matschke [38] (via computation of $S$-integral points on elliptic curves,
based upon bounds for elliptic logarithms), and by the first author, Gherga
and Rechnitzer [3] (using classical invariant theory to efficiently reduce the
problem to solutions of cubic Thue-Mahler equations). One finds that there are
precisely $592192$ isomorphism classes of elliptic curves over $\mathbb{Q}$
with good reduction outside $\\{2,3,5,7,11\\}$; details are available at, e.g.

https://github.com/bmatschke/s-unit-equations/blob/master/elliptic-curve-
tables/good-reduction-away-from-first-
primes/K_deg_1/curves_K_1.1.1.1_S_2_3_5_7_11.txt

For each such class, we consider the corresponding $c$-invariants; if both
$c_{4}\equiv 0{\text{\rm\ (mod~{}$144$)}}$ and $c_{6}\equiv 0{\text{\rm\
(mod~{}$1728$)}},$ we define

(3) $y=\frac{c_{4}}{144}\mbox{ and }x=\frac{|c_{6}|}{1728},$

while if at least one of $c_{4}\equiv 0{\text{\rm\ (mod~{}$144$)}}$ or
$c_{6}\equiv 0{\text{\rm\ (mod~{}$1728$)}}$ fails to hold, but we have
$c_{4}\equiv 0{\text{\rm\ (mod~{}$9$)}}$ and $c_{6}\equiv 0{\text{\rm\
(mod~{}$27$)}}$, we define

(4) $y=\frac{c_{4}}{9}\mbox{ and }x=\frac{|c_{6}|}{27}.$

For the resulting pairs $(x,y)$, we check that $y>0$ and $\gcd(x,y)=1$. We
find $755$ such pairs, corresponding to $812$ triples $(x,y,n)$ satisfying
$3\mid n$. There are $5$ triples with $y>10^{9}$, with the largest value of
$y$ corresponding to the identity

$280213436582801^{2}+2^{16}\cdot 3^{6}\cdot 5\cdot 7^{8}\cdot
11^{2}=4282124641^{3}.$

###  2.2. Exponent $n=4$

In this case, we may rewrite equation (2) as

$(y^{2}-x)(y^{2}+x)=2^{\alpha_{2}}3^{\alpha_{3}}5^{\alpha_{5}}7^{\alpha_{7}}11^{\alpha_{11}}$

and so either $\alpha_{2}=0$, in which case

(5) $u_{1}+u_{2}=2y^{2},$

where $u_{i}$ are coprime $\\{3,5,7,11\\}$-units, or we have

(6) $u_{1}+u_{2}=y^{2},$

where $u_{i}$ are coprime $\\{2,3,5,7,11\\}$-units. In each case, since
$xy\neq 0$, we may suppose that $u_{1}>u_{2}$. To be precise, we have

$u_{1}u_{2}=3^{\alpha_{3}}5^{\alpha_{5}}7^{\alpha_{7}}11^{\alpha_{11}},\;\;\sqrt{\frac{1}{2}(u_{1}+u_{2})}=y\;\;\mbox{
and }\;\;\frac{1}{2}(u_{1}-u_{2})=x,$

and

$u_{1}u_{2}=2^{\alpha_{2}-2}3^{\alpha_{3}}5^{\alpha_{5}}7^{\alpha_{7}}11^{\alpha_{11}},\;\;\sqrt{u_{1}+u_{2}}=y\;\;\mbox{
and }\;\;u_{1}-u_{2}=x,$

in cases (5) and (6), respectively.

As for $n=3$, we can write down corresponding Frey-Hellegouarch curves which
have good reduction outside $\\{2,3,5,7,11\\}$ (and, additionally, in this
situation, have nontrivial rational $2$-torsion). It is easier to attack this
problem more directly. Both equations (5) and (6) take the form $a+b=c^{2}$,
where $a$ and $b$ are $\\{2,3,5,7,11\\}$-units with $\gcd(a,b)$ square-free.
Machinery for solving such problems has been developed by de Weger [39], [40].
Data from an implementation of this by von Kanel and Matschke [38] is
available at

https://github.com/bmatschke/solving-classical-diophantine-
equations/blob/master/sums-of-units-
equations/sumsOfUnitsBeingASquare__S_2_3_5_7_11.txt

We find that there are $1418$ pairs $(a,b)$ such that $a+b$ is a square,
$\gcd(a,b)$ is square-free, $a\geq b$, and the only primes dividing $a$ and
$b$ lie in $\\{2,3,5,7,11\\}$. We further restrict our attention to those with
additionally $a>b\geq 1$ and either $\gcd(a,b)=1$ (in which case we take
$x=a-b$, $y=\sqrt{a+b}$), or $\gcd(a,b)=2$ (whence we choose
$x=\frac{1}{2}(a-b)$ and $y=\sqrt{\frac{1}{2}(a+b)}$). This gives $385$ pairs
of coprime, positive integers $x,y$ with $y^{4}>x^{2}$ and
$P(y^{4}-x^{2})<13$. These pairs actually lead to $406$ triples $(x,y,n)$ with
$4\mid n$, since $17$ of the values of $y$ are squares and four of them are
cubes. However the four cubes have already appeared in our previous
computation, so altogether we obtain $402$ new triples $(x,y,n)$ with $4\mid
n$. Together with the $812$ triples satisfying $3\mid n$ we have altogether
$1214$ triples $(x,y,n)$. The largest $y$ with $n=4$ corresponds to the
identity

$1070528159^{2}\,+\,2^{18}\cdot 3^{3}\cdot 5\cdot 7^{4}\cdot
11^{2}\,=\,32719^{4}.$

For the remainder of the paper, we may therefore assume that the exponent $n$
in equation (2) is prime and $\geq 5$.

##  3\. Primitive divisors : equation (2) with $y$ odd

In this section, we treat (2) under the assumption that $y$ is odd, using the
celebrated Primitive Divisor Theorem of Bilu, Hanrot and Voutier [6], and
prove the following proposition.

######  Proposition 3.1.

The only solutions to (2) with $n\geq 5$ prime, $\gcd(x,y)=1$ and $y$ odd
correspond to the identities

$\displaystyle 1^{2}+2\cdot 11^{2}=3^{5},\quad 241^{2}+2^{3}\cdot
11^{2}=9^{5},\quad 401^{2}+2\cdot 5^{3}=11^{5},$ $\displaystyle
4201^{2}+2\cdot 3\cdot 5^{3}\cdot 11^{4}=31^{5}\;\;\mbox{ and
}\;\;4443^{2}+2^{2}\cdot 7\cdot 11^{6}=37^{5}.$

If we consider solutions with $\gcd(x,y)=1$, $y$ odd, and $n$ divisible by a
prime $\geq 5$, then we must count one more solution corresponding to
$241^{2}+2^{3}\cdot 11^{2}=3^{10}$. Thus our total number of solutions to (2)
for cases considered so far is $1214+6=1220$.

###  3.1. Lucas Sequences and the Primitive Divisor Theorem

It is convenient to first introduce Lucas sequences as defined in [6]. A pair
$(\gamma,\delta)$ of algebraic integers is called a Lucas pair if
$\gamma+\delta$ and $\gamma\delta$ are non-zero coprime rational integers, and
$\gamma/\delta$ is not a root of unity. Given a Lucas pair $(\gamma,\delta)$
we define the corresponding Lucas sequence by

$L_{m}=\frac{\gamma^{m}-\delta^{m}}{\gamma-\delta},\qquad m=0,1,2,\dotsc.$

A prime $\ell$ is said to be a primitive divisor of the $m$-th term if $\ell$
divides $L_{m}$ but $\ell$ does not divide $(\gamma-\delta)^{2}\cdot
u_{1}u_{2}\dotsc u_{m-1}$.

######  Theorem 3 (Bilu, Hanrot and Voutier [6]).

Let $(\gamma,\delta)$ be a Lucas pair and write $\\{L_{m}\\}$ for the
corresponding Lucas sequence. If $m\geq 30$, then $L_{m}$ has a primitive
divisor. Moreover, if $m\geq 11$ is prime, then $L_{m}$ has a primitive
divisor.

Let $\ell$ be a prime. We define the rank of apparition of $\ell$ in the Lucas
sequence $\\{L_{m}\\}$ to be the smallest positive integer $m$ such that
$\ell\mid L_{m}$. We denote the rank of apparition of $\ell$ by $m_{\ell}$.
The following theorem of Carmichael [13] will be useful to us; for a concise
proof see [2, Theorem 8].

######  Theorem 4 (Carmichael [13]).

Let $(\gamma,\delta)$ be a Lucas pair, and $\\{L_{m}\\}$ the corresponding
Lucas sequence. Let $\ell$ be a prime.

  1. (i)

If $\ell\mid\gamma\delta$ then $\ell\nmid L_{m}$ for all positive integers
$m$.

  2. (ii)

Suppose $\ell\nmid\gamma\delta$. Write $D=(\gamma-\delta)^{2}\in{\mathbb{Z}}$.

    1. (a)

If $\ell\neq 2$ and $\ell\mid D$, then $m_{\ell}=\ell$.

    2. (b)

If $\ell\neq 2$ and $\left(\frac{D}{\ell}\right)=1$, then
$m_{\ell}\mid(\ell-1)$.

    3. (c)

If $\ell\neq 2$ and $\left(\frac{D}{\ell}\right)=-1$, then
$m_{\ell}\mid(\ell+1)$.

    4. (d)

If $\ell=2$, then $m_{\ell}=2$ or $3$.

  3. (iii)

If $\ell\nmid\gamma\delta$ then

$\ell\mid L_{m}\iff m_{\ell}\mid m.$

###  3.2. Equation (2) with $y$ odd

For the remainder of this section, $(x,y,n,\alpha_{2},\dotsc,\alpha_{11})$
will denote a solution to the equation

(7)
$x^{2}+2^{\alpha_{2}}3^{\alpha_{3}}5^{\alpha_{5}}7^{\alpha_{7}}11^{\alpha_{11}}\;=\;y^{n}\;\;\mbox{
$x>0$, $y$ odd, }\;\gcd(x,y)=1\;\mbox{and}\;n\geq 5\;\mbox{prime}.$

We shall write

(8)
$2^{\alpha_{2}}3^{\alpha_{3}}5^{\alpha_{5}}7^{\alpha_{7}}11^{\alpha_{11}}\,=\,c^{2}d,\;\;\text{where
$d$ is squarefree}.$

######  Lemma 3.2.

There exist integers $u$ and $v$ such that

$x+c\sqrt{-d}\,=\,(u+v\sqrt{-d})^{n},\;\mbox{ where
}\;y=u^{2}+dv^{2},\;\;u\mid x,\;\;v\mid c\;\mbox{ and }\;\gcd(u,dv)=1.$

If we define

$\gamma=u+v\sqrt{-d}\;\;\mbox{ and }\;\;\delta=u-v\sqrt{-d},$

then $(\gamma,\delta)$ is a Lucas pair. Let $\\{L_{m}\\}$ be the corresponding
Lucas sequence. Then

(9) $L_{n}\,=\,\frac{\gamma^{n}-\delta^{n}}{\gamma-\delta}\,=\,\frac{c}{v}.$

###### Proof.

Write $M={\mathbb{Q}}(\sqrt{-d})$. From (7), we have

$(x+c\sqrt{-d})(x-c\sqrt{-d})=y^{n}$

where the two factors on the left generate coprime ideals of
${\mathcal{O}}_{M}$. Thus $(x+c\sqrt{-d}){\mathcal{O}}_{M}=\mathfrak{A}^{n}$,
for some ideal of $\mathfrak{A}$ of ${\mathcal{O}}_{M}$. There are $32$
possible values of $d$ and we checked, via Magma, that the corresponding
quadratic fields $M={\mathbb{Q}}(\sqrt{-d})$ have, in every case, class
numbers $h$ satisfying

$h\in\\{1,2,4,8,12,32\\}.$

In particular $n$ is coprime to $h$, and therefore $\mathfrak{A}$ is
principal. We deduce that $x+c\sqrt{-d}=\epsilon\cdot\gamma^{n}$ where
$\epsilon\in{\mathcal{O}}_{M}^{*}$ and $\gamma\in{\mathcal{O}}_{M}$. The order
of the unit group ${\mathcal{O}}_{M}^{*}$ is either $4$ (if $d=1$), $6$ (if
$d=3$) or $2$ (in all other cases). Thus the unit group is $n$-divisible and
we may absorb $\epsilon$ into the $\gamma^{n}$ factor to obtain
$x+c\sqrt{-d}=\gamma^{n}$ for some $\gamma\in{\mathcal{O}}_{M}$. We write
$\delta$ for the conjugate of $\gamma$. Note that $\gamma+\delta$ is a divisor
of $2x=\gamma^{n}+\delta^{n}$ and that $\gamma\delta=y$. It follows that
$\gamma+\delta$ and $\gamma\delta$ are non-zero coprime rational integers. We
claim that $\gamma/\delta$ is not a unit. If we suppose otherwise, then
$(x+c\sqrt{-d})/(x-c\sqrt{-d})=(\gamma/\delta)^{n}$ is a unit. By coprimality
of the numerator and denominator, we obtain that $x+c\sqrt{-d}$ is a unit and
therefore $y=1$, a contradiction. Thus $\gamma/\delta$ is not a unit and
$(\gamma,\delta)$ is a Lucas pair. Write $\\{L_{m}\\}$ for the corresponding
Lucas sequence.

Since $\gamma\in{\mathcal{O}}_{M}$, we have $\gamma=u+v\sqrt{-d}$ with $u$ and
$v$ are integers, or $\gamma=(u+v\sqrt{-d})/2$ where both $u$ and $v$ are odd
integers. Suppose first that we are in the latter case (whence we note that
necessarily $d\equiv 3\pmod{4}$). Observe that
$\gamma^{n}-\delta^{n}=2c\sqrt{-d}$, so that $v\sqrt{-d}=\gamma-\delta$
divides $2c\sqrt{-d}$. As $v$ is odd, we deduce that $v\mid c$ and that

$L_{n}=\frac{\gamma^{n}-\delta^{n}}{\gamma-\delta}=2\cdot\frac{c}{v}.$

In particular, $L_{n}$ is even. We note that $\gamma+\delta=u$ and
$\gamma\delta=(u^{2}+dv^{2})/4=y$. Thus the sequence $\\{L_{m}\\}$ satisfies
the recurrence

$L_{0}=0,\quad L_{1}=1,\qquad L_{m+2}=uL_{m+1}-yL_{m}.$

Using the fact that $u$ and $v$ are odd, one checks by induction that

$L_{m}\equiv 0\pmod{2}\;\iff\;3\mid m.$

Thus, in particular, $3\mid n$, contradicting the assumption that $n\geq 5$ is
prime. It follows that $\gamma=u+v\sqrt{-d}$ where $u$ and $v$ are integers.
Now observe that

$2u=(\gamma+\delta)\mid(\gamma^{n}+\delta^{n})=2x\;\;\mbox{ and
}\;\;2v\sqrt{-d}=(\gamma-\delta)\mid(\gamma^{n}-\delta^{n})=2c\sqrt{-d}.$

Thus $u\mid x$ and $v\mid c$. Since $y=u^{2}+dv^{2}$, we conclude that
$\gcd(u,dv)=1$. The lemma follows. ∎

######  Lemma 3.3.

Let $(x,y,n,\alpha_{2},\dotsc,\alpha_{11})$ be a solution to (7). Then $n=5$
and

(10) $5u^{4}-10du^{2}v^{2}+d^{2}v^{4}\,=\,\pm 5^{r}\cdot 11^{s},$

for some $r\in\\{0,1\\}$ and $s\geq 0$.

###### Proof.

We continue with the notation of Lemma 3.2. By (9), we have $L_{n}=c/v$; this
is coprime to $\gamma\delta=y$. If $\ell$ is any prime divisor of $L_{n}$ then
$m_{\ell}=n$, by part (iii) of Theorem 4 and the primality of $n$.

Suppose first that $n\geq 11$. By Theorem 3, $L_{n}$ must have a primitive
divisor, $q$ say. By definition, this does not divide
$D=(\gamma-\delta)^{2}=-4v^{2}d$. Thus by part (ii) of Theorem 4, $n\mid(q-1)$
if $(D/q)=1$ and $n\mid(q+1)$ if $(D/q)=-1$. As the possible values of
$q\mid(c/v)$ are $2$, $3$, $5$, $7$ and $11$, we obtain a contradiction. Thus
$n=5$ or $n=7$.

Next we deal with the case $n=7$. If we suppose that $L_{7}$ has a primitive
divisor $q$ then the above argument shows that $7\mid(q-1)$ or $7\mid(q+1)$
which is impossible as $q\in\\{2,3,5,7,11\\}$. Thus $L_{7}$ has no primitive
divisor and our Lucas pair $(\gamma,\delta)=(u+v\sqrt{-d},u-v\sqrt{-d})$ is
$7$-defective in the terminology of [6]. In particular, by the classification
of defective Lucas pairs (Theorem C of [6]) we have
$u+v\sqrt{-d}=\pm(1+\sqrt{-7})/2$ or $\pm(1+\sqrt{-19})/2$. Both are
impossible as $u$ and $v$ are integers. Hence there are no solutions to (7)
with $n=7$.

Finally we deal with $n=5$. Since $5\nmid\ell\cdot(\ell-1)(\ell+1)$ for any of
$\ell\in\\{2,3,7\\}$, we see that $L_{n}=c/v=\pm 5^{r}\cdot 11^{s}$. Moreover,
if $r\geq 1$ then $m_{5}=5$ and so $5\mid dv$ by Theorem 4.

Substituting $\gamma=u+v\sqrt{-d}$ and $\delta=u-v\sqrt{-d}$ in (9) gives
(10). We note that if $r\geq 2$ then $5\mid u$, contradicting the coprimality
of $u$ and $dv$. Therefore $r\in\\{0,1\\}$. ∎

It remains to solve the quartic Thue–Mahler equations (10) for our $32$
possible values of $d$. Appealing to the Thue-Mahler equation solver,
implemented in Magma and associated to the paper [16], we obtain the following
solutions:

$(d,u,v)\,=\,(2,-1,1),\;\;(2,1,-2),\;\;(7,3,-2),\;\;(10,1,1)\;\mbox{ and
}\;(30,1,1).$

These lead, respectively, to solutions of equation (2) with

$(x,y,n)\,=\,(1,3,5),\;(241,9,5),\;(4443,37,5),\;(401,11,5)\;\mbox{ and
}\;(4201,31,5),$

completing the proof of Proposition 3.1.

##  4\. Reduction to Thue-Mahler equations: the case of even $y$

From the results of the preceding sections, we are left to treat (2) with $y$
even and $n\geq 5$ prime. It therefore remains to consider the equation

(11)
$x^{2}+3^{\alpha_{3}}5^{\alpha_{5}}7^{\alpha_{7}}11^{\alpha_{11}}\;=\;y^{n}\;\;\mbox{
with $y$ even, }\;\gcd(x,y)=1\;\mbox{ and }\;n\geq 5\;\mbox{ prime}.$

Let us define

(12) $N(d)=\begin{cases}6\times 10^{8}\;\mbox{ if }\;d=7,\\\ 4\times
10^{8}\;\mbox{ if }\;d=15,\\\ 5\times 10^{8}\;\mbox{ if }\;d=55,\\\ 1.2\times
10^{9}\;\mbox{ if }\;d=231.\\\ \end{cases}$

The purpose of this section and the next is to prove the following
proposition.

######  Proposition 4.1.

The only solutions to (11) with $n<N(d)$ correspond to the identities

$\displaystyle 31^{2}+3^{2}\cdot 7=4^{5},\quad 5^{2}+7=2^{5},\quad
181^{2}+7=8^{5},\quad 17^{2}+3\cdot 5\cdot 7^{2}=4^{5},$ $\displaystyle
23^{2}+3^{2}\cdot 5\cdot 11=4^{5},\quad 130679^{2}+3\cdot 7^{3}\cdot
11^{7}=130^{5},\quad 47^{2}+3^{4}\cdot 5^{2}\cdot 7=4^{7},\quad
11^{2}+7=2^{7},$ $\displaystyle 7^{2}+3^{3}\cdot 5\cdot 11^{2}=4^{7},\quad
117^{2}+5\cdot 7^{2}\cdot 11=4^{7},\quad 103^{2}+3\cdot 5^{2}\cdot 7\cdot
11=4^{7},$ $\displaystyle\mbox{ and }\;\;8143^{2}+3^{3}\cdot 5\cdot 7^{2}\cdot
11^{2}=4^{13}.$

This gives $12$ new solutions to (2) with $n\in\\{5,7,13\\}$ and,
additionally, $8$ further solutions with exponents $10$, $14$ and $26$. Thus
the total number of solutions we have found so far for (2) is
$1220+12+8=1240$. We shall show in Section 6 that there are no further
solutions, and that therefore (2) has precisely $1240$ solutions as claimed in
Theorem 2.

We assume without loss of generality that $x\equiv 1{\text{\rm\
(mod~{}$4$)}}$. As before we shall write

(13)
$3^{\alpha_{3}}5^{\alpha_{5}}7^{\alpha_{7}}11^{\alpha_{11}}\;=\;c^{2}d,\;\text{where
$d$ is squarefree and
}c\;=\;3^{\beta_{3}}5^{\beta_{5}}7^{\beta_{7}}11^{\beta_{11}}.$

Since $y$ is even, it follows from (11) that $d\equiv-1{\text{\rm\
(mod~{}$8$)}}$, whence necessarily

(14) $d\in\\{7,15,55,231\\}.$

Let $M=M_{d}={\mathbb{Q}}(\sqrt{-d})$. We note the structure of the class
group of $M$:

$\operatorname{Cl}(M)\cong\begin{cases}1&d=7\\\ C_{2}&d=15\\\ C_{4}&d=55\\\
C_{2}\times C_{6}&d=231.\end{cases}$

######  Lemma 4.2.

Let $c^{\prime}=\pm c$ with the sign chosen so that $c^{\prime}\equiv
1{\text{\rm\ (mod~{}$4$)}}$. Let

$h=\begin{cases}1&d=7\\\ 2&d=2\\\ 4&d=55\\\ 6&d=231\end{cases}\;\mbox{ and
}\;\eta=r+s\sqrt{-d},\;\mbox{ where
}\;(r,s)\;=\;\begin{cases}(1/4,-1/4)&d=7\\\ (1/8,-1/8)&d=15\\\
(3/32,1/32)&d=55\\\ (5/128,-1/128)&d=231.\end{cases}$

Let $0\leq\kappa_{n}\leq h-1$ be the unique integer satisfying
$\kappa_{n}\cdot n\equiv-2{\text{\rm\ (mod~{}$h$)}}$. Then there is some non-
zero $\mu\in{\mathcal{O}}_{M}$ such that

(15) $\frac{x+c^{\prime}\sqrt{-d}}{2}\;=\;\eta^{(2+\kappa_{n}\cdot
n)/h}\cdot\mu^{n}.$

Moreover, $\eta$ is supported only on prime ideals dividing $2$ and $\mu$ is
supported only on prime ideals dividing $y$.

###### Proof.

As $d\equiv-1{\text{\rm\ (mod~{}$8$)}}$, the prime $2$ splits in
${\mathcal{O}}_{M}$ as
$2{\mathcal{O}}_{M}=\mathfrak{P}\cdot\overline{\mathfrak{P}}$, where

(16)
$\mathfrak{P}\;=\;2{\mathcal{O}}_{M}\;+\;\left(\frac{1+\sqrt{-d}}{2}\right)\cdot{\mathcal{O}}_{M}.$

We may rewrite (11) as

(17)
$\left(\frac{x+c^{\prime}\sqrt{-d}}{2}\right)\left(\frac{x-c^{\prime}\sqrt{-d}}{2}\right)\;=\;\frac{y^{n}}{4}.$

Note that the two factors on the left hand-side of this last equation are
coprime elements of ${\mathcal{O}}_{M}$. Since $x\equiv c^{\prime}\equiv
1{\text{\rm\ (mod~{}$4$)}}$, we see that $\mathfrak{P}$ divides the first
factor on the left-hand-side. We thus deduce that

(18)
$\left(\frac{x+c^{\prime}\sqrt{-d}}{2}\right)\cdot{\mathcal{O}}_{M}\;=\;\mathfrak{P}^{-2}\cdot\mathfrak{A}^{n},$

where $\mathfrak{A}$ is an integral ideal divisible by $\mathfrak{P}$, with
$\mathfrak{A}\cdot\overline{\mathfrak{A}}=y{\mathcal{O}}_{M}$. The order of
the class $[\mathfrak{P}]$ in $\operatorname{Cl}(M)$ is $h$. Thus
$\mathfrak{P}^{-h}$ is principal, and $\eta$ has been chosen so that
$\mathfrak{P}^{-h}=\eta{\mathcal{O}}_{M}$. Let
$\mathfrak{B}=\mathfrak{P}^{\kappa_{n}}\cdot\mathfrak{A}$. Then we may rewrite
(18) as

$\left(\frac{x+c^{\prime}\sqrt{-d}}{2}\right)\cdot{\mathcal{O}}_{M}\;=\;\mathfrak{P}^{-(2+\kappa_{n}\cdot
n)}\cdot\mathfrak{B}^{n}\;=\;\eta^{(2+\kappa_{n}\cdot
n)/h}\cdot\mathfrak{B}^{n}.$

Since $n$ is a prime that does not divide the order of $\operatorname{Cl}(M)$,
the ideal $\mathfrak{B}$ must be principal. Let $\mu$ be a generator for
$\mathfrak{B}$. Then

$\frac{x+c^{\prime}\sqrt{-d}}{2}\;=\;\pm\eta^{(2+\kappa_{n}\cdot
n)/h}\cdot\mu^{n}$

and (15) follows on absorbing the $\pm$ sign into $\mu$. It is clear that
$\eta$ is supported on $\mathfrak{P}$ only. Moreover $\mathfrak{B}$ is an
integral ideal with norm $2^{\kappa_{n}}y$. It follows, since $y$ is even,
that $\mu$ is supported only on prime ideals dividing $y$. ∎

######  Lemma 4.3.

The only solutions to equation (11) with $n\in\\{5,7,11\\}$ are those
corresponding to the identities in Proposition 4.1.

###### Proof.

We drop our requirement that $x>0$ and replace it with the assumption $x\equiv
1{\text{\rm\ (mod~{}$4$)}}$, so that we can apply Lemma 4.2. For each exponent
$n$, there are four cases to consider depending on the value of
$d\in\\{7,15,55,231\\}$ in (13). For each pair $(n,d)$, Lemma 4.2 asserts that
$(x,c^{\prime})$ satisfies (15) with $\mu\in{\mathcal{O}}_{M}$. We write

$\mu=r+s(1+\sqrt{-d})/2,$

with $r$ and $s$ rational integers. We will show that $\gcd(r,s)=1$. If $2\mid
r$ and $2\mid s$ then $\overline{\mathfrak{P}}\mid\mu$ which contradicts the
coprimality of the two factors in the left hand-side of (17). If $\ell$ is an
odd prime with $\ell\mid r$ and $\ell\mid s$, then again we contradict the
coprimality of those two factors. Hence $\gcd(r,s)=1$.

From (15), we have

$c^{\prime}=\frac{1}{\sqrt{-d}}\left(\eta^{m}\cdot(r+s(1+\sqrt{-d})/2)^{n}\,-\,\overline{\eta}^{m}\cdot(r+s(1-\sqrt{-d})/2)^{n}\right)$

where $m=(2+\kappa_{n}\cdot n)/h$. The expression on the right has the form
$2^{-hm}F(r,s)$ where $F\in{\mathbb{Z}}[X,Y]$ is homogeneous of degree $n$. We
therefore, in each case, obtain a Thue-Mahler equation of the form

$F(r,s)\;=\;2^{hm}\cdot c^{\prime}\;=\;\pm 2^{hm}\cdot
3^{\beta_{3}}5^{\beta_{5}}7^{\beta_{7}}11^{\beta_{11}}.$

We solved these Thue-Mahler equations using the Thue-Mahler solver associated
with the paper [16]. This computation took around one day and resulted in the
solutions in Proposition 4.1 for $n\in\\{5,7\\}$; there were no solutions for
$n=11$. ∎

##  5\. Frey-Hellegouarch curves and related objects

We continue to treat (2) with $y$ even, i.e. equation (11), where we maintain
the assumption that $x\equiv 1{\text{\rm\ (mod~{}$4$)}}$. Although the results
of the previous section allow us to assume more, for now we merely impose the
following constraint on the exponent: $n\geq 7$ is prime. Following the first
author and Skinner [5], we associate to a solution $(x,y,n)$ the Frey-
Hellegouarch elliptic curve $F=F(x,y,n)$ defined via

(19)
$F\;\;:\;\;Y^{2}+XY=X^{3}+\left(\frac{x-1}{4}\right)X^{2}+\frac{y^{n}}{64}X.$

The model here is minimal, semistable, and we note the following invariants,

$c_{4}=x^{2}-\frac{3}{4}y^{n},\qquad c_{6}=-x^{3}+\frac{9}{8}xy^{n}$

and

$\Delta_{F}\;=\;\frac{y^{2n}}{2^{12}}(x^{2}-y^{n})\;=\;-2^{-12}\cdot
3^{\alpha_{3}}5^{\alpha_{5}}7^{\alpha_{7}}11^{\alpha_{11}}\cdot y^{2n}.$

We invoke work of the first author and Skinner [5], building on the modularity
of elliptic curves over ${\mathbb{Q}}$ following Wiles and others [41], [8],
Ribet’s level lowering theorem [31], and the isogeny theorem of Mazur [24].
Write $N$ for the conductor of $E$ and let

$N^{\prime}=\frac{N}{\prod_{\stackrel{{\scriptstyle\ell\mid\mid
N}}{{n\mid\operatorname{ord}_{\ell}(\Delta_{F})}}}\ell}.$

The results of [5] assert the existence of a weight $2$ newform $f$ of level
$N^{\prime}$ such that

(20) $\overline{\rho}_{F,n}\sim\overline{\rho}_{f,\mathfrak{n}},$

with ${\mathfrak{n}}\mid n$ a prime ideal in the ring of integers
${\mathcal{O}}_{K}$ of the Hecke eigenfield $K$ of $f$.

######  Lemma 5.1.

We have $N^{\prime}=2R$ where $R\mid 3\cdot 5\cdot 7\cdot 11$. Moreover, for
$\ell\in\\{3,5,7,11\\}$, we have

(21) $\ell\nmid N^{\prime}\;\iff\;\alpha_{\ell}\equiv 0\pmod{n}\;\iff
2\operatorname{ord}_{\ell}(c)+\operatorname{ord}_{\ell}(d)\equiv 0\pmod{n}$

where $c$ and $d$ are given in (13).

###### Proof.

Since $E$ is semistable, $N$ is squarefree, and therefore $N^{\prime}$ is
squarefree. Note that
$\operatorname{ord}_{2}(\Delta_{F})=2n\operatorname{ord}_{2}(y)-12$. Thus
$2\mid\mid N$ and $n\nmid\operatorname{ord}_{2}(\Delta_{F})$, whereby
$2\mid\mid N^{\prime}$.

Next let $\ell\geq 13$. Then
$\operatorname{ord}_{\ell}(\Delta_{F})=2n\operatorname{ord}_{\ell}(y)$ and
hence $\ell\nmid N^{\prime}$. It follows that $N^{\prime}=2R$ with $R\mid
3\cdot 5\cdot 7\cdot 11$.

To prove the second part of the lemma, note that, for $\ell\in\\{3,5,7,11\\}$,

$\operatorname{ord}_{\ell}(\Delta)=\alpha_{\ell}+2n\operatorname{ord}_{\ell}(y)=2\operatorname{ord}_{\ell}(c)+\operatorname{ord}_{\ell}(d)+2n\operatorname{ord}_{\ell}(y).$

If $\alpha_{\ell}=0$ and $\operatorname{ord}_{\ell}(y)=0$, then $\ell\nmid N$
and so $\ell\nmid N^{\prime}$, and therefore (21) holds. Suppose
$\alpha_{\ell}>0$ or $\operatorname{ord}_{\ell}(y)>0$. Then $\ell\mid\mid N$.
By the formula for $N^{\prime}$, we have $\ell\nmid N^{\prime}$ if and only if
$n\mid\operatorname{ord}_{\ell}(\Delta)$ which is equivalent to
$n\mid\alpha_{\ell}$. This completes the proof. ∎

Let $f$ be the weight $2$ newform of level $N^{\prime}$ satisfying (20). Write

(22) $f=\mathfrak{q}+\sum_{m=2}^{\infty}c_{m}\mathfrak{q}^{m}$

for the usual $q$-expansion of $f$. Then $K={\mathbb{Q}}(c_{1},c_{2},\ldots)$,
and the coefficients $c_{i}$ belong to ${\mathcal{O}}_{K}$.

######  Lemma 5.2.

Let $\ell\nmid N^{\prime}$ be a prime and write

$\mathcal{C}_{f,\ell}^{\prime}=\begin{cases}(\ell+1)^{2}-c_{\ell}^{2}&\text{if
$K={\mathbb{Q}}$}\\\ \ell\cdot((\ell+1)^{2}-c_{\ell}^{2}))&\text{if
$K\neq{\mathbb{Q}}$}.\end{cases}$

Let $d$ be as in (13), and set

$T_{\ell}(f)=\begin{cases}\\{a\in{\mathbb{Z}}\cap[-2\sqrt{\ell},2\sqrt{\ell}]\;:\;\ell+1-a\equiv
0{\text{\rm\ (mod~{}$4$)}}\\}&\text{if $(-d/\ell)=1$}\\\
\\{a\in{\mathbb{Z}}\cap[-2\sqrt{\ell},2\sqrt{\ell}]\;:\;\ell+1-a\equiv
0{\text{\rm\ (mod~{}$2$)}}\\}&\text{if $(-d/\ell)=-1$}\\\ \hskip
107.63855pt\emptyset&\text{if $\ell\mid d$}.\end{cases}$

Let

$\mathcal{C}_{f,\ell}\;=\;\mathcal{C}_{f,\ell}^{\prime}\cdot\prod_{a\in
T_{\ell}(f)}(a-c_{\ell}).$

If $\overline{\rho}_{F,n}\sim\overline{\rho}_{f,{\mathfrak{n}}}$, then
${\mathfrak{n}}\mid\mathcal{C}_{f,\ell}$.

###### Proof.

Suppose $\ell\nmid N^{\prime}$ and write $N$ for the conductor of $F$. Suppose
$\overline{\rho}_{F,n}\sim\overline{\rho}_{f,{\mathfrak{n}}}$. A standard
consequence [32, Propositions 5.1, 5.2] of this is that

$\begin{cases}c_{\ell}\equiv a_{\ell}(F){\text{\rm\
(mod~{}${\mathfrak{n}}$)}}&\text{if $\ell\neq n$ and $\ell\nmid N$}\\\
c_{\ell}\equiv\pm(\ell+1){\text{\rm\ (mod~{}${\mathfrak{n}}$)}}&\text{if
$\ell\neq n$ and $\ell\mid N$}.\end{cases}$

Here the restriction $\ell\neq n$ is unnecessary if $K={\mathbb{Q}}$. It
follows if $\ell\mid N$ that
${\mathfrak{n}}\mid\mathcal{C}_{f,\ell}^{\prime}$. We observe that the
discriminant of $F$ can written as

$\Delta\;=\;(-d)\cdot(cy^{n}/2^{6})^{2}.$

If $\ell\mid d$ then $\ell\mid N$ and so we take
$\mathcal{C}_{f,\ell}=\mathcal{C}_{f,\ell}^{\prime}$.

Suppose $\ell\nmid N$ and so $\ell\nmid d$. Thus $c_{\ell}\equiv
a_{\ell}(F){\text{\rm\ (mod~{}${\mathfrak{n}}$)}}$. To complete the proof it
is sufficient to show that $a_{\ell}(F)\in T_{\ell}(f)$. The model for $F$
given in (19) is isomorphic to

(23) $F\;\;:\;\;Y^{2}=X^{3}+xX^{2}+\frac{y^{n}}{4}X,$

and so has a point of order $2$. Thus
$\ell+1-a_{\ell}(F)=\\#F({\mathbb{F}}_{\ell})\equiv 0{\text{\rm\
(mod~{}$2$)}}$. Moreover, if $(-d/\ell)=1$ then the discriminant is a square
modulo $\ell$, so $F/{\mathbb{F}}_{\ell}$ has full $2$-torsion, whence
$\\#F({\mathbb{F}}_{\ell})\equiv 0{\text{\rm\ (mod~{}$4$)}}$. It follows that
$a_{\ell}(F)\in T_{\ell}(f)$. ∎

There are a total of $76$ conjugacy classes of newforms $f$ at the levels
$N^{\prime}=2R$ with $R\mid 3\cdot 5\cdot 7\cdot 11$, of which $59$ are
rational (and so correspond to elliptic curves). Since there are four possible
values of $d\in\\{7,15,55,231\\}$, this gives $4\times 76=304$ pairs $(f,d)$
to consider. We apply Lemma 5.2 to each pair $(f,d)$, letting

$\mathcal{C}_{f,d}=\sum\mathcal{C}_{f,\ell}\cdot{\mathcal{O}}_{K},$

where the sum is over all primes $3\leq\ell<500$ not dividing $N^{\prime}$. It
follows from Lemma 5.2 that ${\mathfrak{n}}\mid\mathcal{C}_{f,d}$. We let

$C_{f,d}=\operatorname{Norm}_{K/{\mathbb{Q}}}(\mathcal{C}_{f,d}).$

Since ${\mathfrak{n}}\mid n$, we have that $n\mid C_{f,d}$. Of the $304$ pairs
$(f,d)$, the integer ${C}_{f,d}$ is identically zero for $114$ pairs, and non-
zero for the remaining $190$ pairs. For the $190$ pairs $(f,d)$ where
${C}_{f,d}\neq 0$, we find that the largest possible prime divisor of any of
these $C_{f,d}$ is $11$. By the results of the previous section we know all
the solutions to (11) with $n\in\\{7,11\\}$ and hence can therefore eliminate
these $190$ pairs from further consideration. We focus on the $114$ remaining
pairs $(f,d)$. Here, each $f$ satisfies $K={\mathbb{Q}}$ and so corresponds to
an elliptic curve $E/{\mathbb{Q}}$ whose conductor is equal to the level
$N^{\prime}$ of $f$. Moreover, each of these elliptic curve $E$ has non-
trivial rational $2$-torsion. This is unsurprising in view of the remarks
following [32, Proposition 9.1]. We observe that
$\overline{\rho}_{f,n}\sim\overline{\rho}_{E,n}$. Thus we have $114$ pairs
$(E,d)$ to consider, and if $(x,y,n)$ is a solution to (11) with $n\geq 13$
prime then there is some pair $(E,d)$ (among the $114$) where $d$ satisfies
(13) and $E/{\mathbb{Q}}$ is an elliptic curve such that
$\overline{\rho}_{F,n}\sim\overline{\rho}_{E,n}$. In particular, for any prime
$\ell\nmid N^{\prime}$,

$\begin{cases}a_{\ell}(E)\equiv a_{\ell}(F){\text{\rm\ (mod~{}$n$)}}&\text{if
$\ell\nmid N$}\\\ a_{\ell}(E)\equiv\pm(\ell+1){\text{\rm\
(mod~{}$n$)}}&\text{if $\ell\mid N$}.\end{cases}$

###  5.1. The Method of Kraus

######  Lemma 5.3.

Let $c^{\prime}=\pm c$ with the sign chosen so that $c^{\prime}\equiv
1{\text{\rm\ (mod~{}$4$)}}$. Let

$\gamma=u+v\sqrt{-d}\;\;\mbox{ where
}\;\;(u,v)\;=\;\begin{cases}(1/8,3/8)&d=7\\\ (7/8,1/8)&d=15\\\
(3/8,1/8)&d=55\\\ (5/16,-1/16)&d=231.\end{cases}$

Choose $\epsilon_{n}\in\\{1,-1\\}$ to satisfy $n\equiv\epsilon_{n}{\text{\rm\
(mod~{}$3$)}}$. Then there is some $\delta\in M^{*}$ such that

(24)
$\frac{x+c^{\prime}\sqrt{-d}}{x-c^{\prime}\sqrt{-d}}\;=\;\begin{cases}\gamma\cdot\delta^{n}&\mbox{
if }d=7,15,55\\\ \gamma^{(2+\epsilon_{n}\cdot n)/3}\cdot\delta^{n}&\mbox{ if
}d=231.\end{cases}$

Moreover, $\delta$ is supported only on prime ideals dividing $y$.

###### Proof.

From the proof of Lemma 4.2, and in particular (18), we have

(25)
$\left(\frac{x^{\prime}+c\sqrt{-d}}{x^{\prime}-c\sqrt{-d}}\right)\cdot{\mathcal{O}}_{M}\;=\;(\overline{\mathfrak{P}}/\mathfrak{P})^{2}\cdot\mathfrak{B}^{n}$

with $\mathfrak{B}=\mathfrak{A}/\overline{\mathfrak{A}}$. Here $\mathfrak{P}$
is given by (16), and $\mathfrak{A}$ is an integral ideal dividing $y$. We
observe that $\mathfrak{B}$ is supported only on prime ideals dividing $y$.
First let $d=7$, $15$ or $55$. In these cases the fractional ideal
$(\overline{\mathfrak{P}}/\mathfrak{P})^{2}$ is principal, and we have chosen
$\gamma$ so that it is a generator. Since $n$ is a prime not dividing the
order of $\operatorname{Cl}(M)$ we have that $\mathfrak{B}$ is also principal.
Let $\delta\in M^{*}$ be a generator of $\mathfrak{B}$. Then

$\frac{x+c^{\prime}\sqrt{-d}}{x-c^{\prime}\sqrt{-d}}=\pm\gamma\cdot\delta^{n},$

and we complete the proof for $d=7$, $15$ and $55$ by absorbing the $\pm$ sign
into $\delta$.

Suppose now that $d=231$. The class of the fractional ideal
$\overline{\mathfrak{P}}/\mathfrak{P}$ has order $3$, and we have chosen
$\gamma$ to be a generator of $(\overline{\mathfrak{P}}/\mathfrak{P})^{3}$. We
may rewrite (25) as

$\frac{x+c^{\prime}\sqrt{-d}}{x-c^{\prime}\sqrt{-d}}\;=\;(\overline{\mathfrak{P}}/\mathfrak{P})^{2+\epsilon_{n}\cdot
n}\cdot\mathfrak{C}^{n}$

where
$\mathfrak{C}=\mathfrak{B}\cdot(\mathfrak{P}/\overline{\mathfrak{P}})^{\epsilon_{n}}$.
Note that $3\mid(2+\epsilon_{n}\cdot n)$ and hence

$(\overline{\mathfrak{P}}/\mathfrak{P})^{2+\epsilon_{n}\cdot
n}\;=\;\gamma^{(2+\epsilon_{n}\cdot n)/3}\cdot{\mathcal{O}}_{M}.$

The ideal $\mathfrak{C}$ must be principal and hence we complete the proof by
letting $\delta$ be a suitably chosen generator for $\mathfrak{C}$. We note
that, in all cases, $\delta$ is supported only on primes of
${\mathcal{O}}_{M}$ dividing $y$. ∎

######  Lemma 5.4.

Let $n\geq 13$ be a prime and $(E,d)$ be one of the remaining $114$ pairs. Let
$q=kn+1$ be a prime. Suppose that $(-d/q)=1$, and choose $a$ such that
$a^{2}\equiv-d{\text{\rm\ (mod~{}$q$)}}$. Let $g_{0}$ be a generator for
${\mathbb{F}}_{q}^{*}$ and $g=g_{0}^{n}$. Let $(u,v)$ be as in the statement
of Lemma 5.3. If $d=7$, $15$ or $55$, then let

$\Theta_{q}^{\prime}\;=\;\left\\{(u+va)\cdot
g^{i}\;:\;i=0,1,\dotsc,k-1\right\\}\subset{\mathbb{F}}_{q}.$

If $d=231$, then set

$\Theta_{q}^{\prime}\;=\;\left\\{(u+va)^{(2+\epsilon_{n}\cdot n)/3}\cdot
g^{i}\;:\;i=0,1,\dotsc,k-1\right\\}\subset{\mathbb{F}}_{q}$

and, in all cases, let

$\Theta_{q}\;=\;\Theta_{q}^{\prime}\setminus\\{0,1\\}.$

Suppose the following two conditions hold:

  1. (i)

$a_{q}(E)^{2}\not\equiv 4{\text{\rm\ (mod~{}$n$)}}$.

  2. (ii)

$a_{q}(E)^{2}\not\equiv a_{q}(H_{\theta})^{2}{\text{\rm\ (mod~{}$n$)}}$ for
all $\theta\in\Theta_{q}$, where

$H_{\theta}\;\;:\;\;Y^{2}=X(X+1)(X+\theta).$

Then $\overline{\rho}_{F,n}\nsim\overline{\rho}_{E,n}$.

###### Proof.

We suppose that $\overline{\rho}_{F,n}\sim\overline{\rho}_{E,n}$ and derive a
contradiction. Since $n\geq 11$, we note that, in particular,
$q\not\in\\{2,3,5,7,11\\}$. Suppose first that $q\mid y$. Then $q+1\equiv\pm
a_{q}(E){\text{\rm\ (mod~{}$n$)}}$. But $q+1=kn+2\equiv 2{\text{\rm\
(mod~{}$n$)}}$ and hence $a_{q}(E)^{2}\equiv 4{\text{\rm\ (mod~{}$n$)}}$,
contradicting hypothesis (i). We may therefore suppose that $q\nmid y$. In
particular $q$ is a prime of good reduction for the Frey curve $F$, and also
for the curve $E$, whence $a_{q}(F)\equiv a_{q}(E){\text{\rm\ (mod~{}$n$)}}$.

Since $a^{2}\equiv-d{\text{\rm\ (mod~{}$q$)}}$, by the Dedekind-Kummer
theorem, the prime $q$ splits in ${\mathcal{O}}_{M}$ as a product of two
primes $q{\mathcal{O}}_{M}=\mathfrak{q}\cdot\overline{\mathfrak{q}}$ where we
choose

(26)
$\mathfrak{q}\;=\;q{\mathcal{O}}_{M}+(a-\sqrt{-d})\cdot{\mathcal{O}}_{M}.$

In particular $a\equiv\sqrt{-d}{\text{\rm\ (mod~{}$\mathfrak{q}$)}}$.
Moreover, ${\mathbb{F}}_{\mathfrak{q}}={\mathbb{F}}_{q}$. Since
$\mathfrak{q}\mid q$ and $q\nmid 2y$, it follows from (17) that
$\mathfrak{q}\nmid(x\pm c^{\prime}\sqrt{-d})$. We let
$\theta\in{\mathbb{F}}_{q}^{*}$ satisfy

(27)
$\theta\;\equiv\;\frac{x+c^{\prime}\sqrt{-d}}{x-c^{\prime}\sqrt{-d}}{\text{\rm\
(mod~{}$\mathfrak{q}$)}}.$

We will contradict hypothesis (ii), and complete the proof, by showing that
$\theta\in\Theta_{q}$ and $a_{q}(F)=\pm a_{q}(H_{\theta})$. If $\theta\equiv
1{\text{\rm\ (mod~{}$q$)}}$ then $\mathfrak{q}\mid 2c^{\prime}\sqrt{-d}$
giving that $q\mid 2\cdot 3\cdot 5\cdot 7\cdot 11$, which is impossible.
Therefore $\theta\not\equiv 1{\text{\rm\ (mod~{}$q$)}}$. Let $(u,v)$, $\gamma$
and $\delta$ be as in the statement of Lemma 5.3. Note that $\gamma$ is
supported only at the primes above $2$ and that $\delta$ is supported at only
the primes above $y$. Since $\mathfrak{q}\nmid y$, we may reduce $\gamma$ and
$\delta$ modulo $\mathfrak{q}$. In particular,

$\gamma\equiv u+av{\text{\rm\ (mod~{}$\mathfrak{q}$)}}.$

Moreover, $\delta^{n}{\text{\rm\ (mod~{}$\mathfrak{q}$)}}$ belongs to the
subgroup of ${\mathbb{F}}_{q}^{*}$ generated by $g=g_{0}^{n}$ of order $k$.
The fact that $\theta$ belongs to $\Theta_{q}^{\prime}$ (and therefore to
$\Theta_{q}$) follows from (27) and (24).

It remains to show that $a_{q}(F)=\pm a_{q}(H_{\theta})$. The model for $F$ in
(19) is isomorphic to the model in (23). We note that the polynomial on the
right hand-side of (23) can be factored as

(28)
$X\left(X\,+\,\frac{x+c^{\prime}\sqrt{-d}}{2}\right)\left(X\,+\,\frac{x-c^{\prime}\sqrt{-d}}{2}\right).$

Thus, $F{\text{\rm\ (mod~{}$\mathfrak{q}$)}}$ is a quadratic twist of
$H_{\theta}$, whence

$a_{q}(F)=a_{\mathfrak{q}}(F)=\pm a_{\mathfrak{q}}(H_{\theta})=\pm
a_{q}(H_{\theta}),$

completing the proof. ∎

Remark. We know by Dirichlet’s theorem that the natural density of primes $q$
satisfying the conditions $q=kn+1$ and $(-d/q)=1$ is $1/2n$. We now give a
heuristic estimate for the probability of succeeding to show that
$\overline{\rho}_{F,n}\nsim\overline{\rho}_{E,n}$ using a single $q=kn+1$ that
satisfies $(-d/q)=1$. The set $\Theta_{q}^{\prime}$ has size $k$, and so
$\Theta_{q}$ has size close to $k$. For a given $\theta\in\Theta_{q}$, we
expect the probability that $a_{q}(E)^{2}\not\equiv
a_{q}(H_{\theta})^{2}{\text{\rm\ (mod~{}$n$)}}$ to be roughly $(1-2/n)$. Thus
the probability of the criterion succeeding is around $(1-2/n)^{k}$. In
particular, if $k$ is large compared to $n/2$ then we expect failure, but if
$k$ is small compared to $n/2$ then we expect success. Moreover, if we fail
with one particular value of $q$, we are likely to fail with larger values of
$q$ (which correspond to larger values of $k$).

However, this heuristic is likely to be inaccurate when $\sqrt{q}$ is small
compared to $n$, since $a_{q}(E)$ and $a_{q}(H_{\theta})$ both belong to the
Hasse interval $[-2\sqrt{q},2\sqrt{q}]$, and the probability of the criterion
succeeding is around $(1-1/\sqrt{q})^{k}$.

$d$ | $N(d)$ | Number of primes $13\leq n<N(d)$ | Number of pairs $(E,d)$
---|---|---|---
$7$ | $6\times 10^{8}$ | $31324698$ | $39$
$15$ | $4\times 10^{8}$ | $21336321$ | $28$
$55$ | $5\times 10^{8}$ | $26355862$ | $27$
$231$ | $1.2\times 10^{9}$ | $60454700$ | $20$
Table 1. The upper bounds $N(d)$ are as in (12). The table records the number
of primes in the interval $13\leq n<N(d)$ and the number of pairs $(E,d)$.

We are working towards proving Proposition 4.1. Recall that we have $114$
remaining pairs $(E,d)$ with $E/{\mathbb{Q}}$ an elliptic curve and
$d\in\\{7,15,55,231\\}$; these are distributed among the values of $d$
according to Table 1. The table also records the upper bounds $N(d)$ of
Proposition 4.1. We wrote a Magma script that applied the criterion of Lemma
5.4 to the

$39\cdot 31324698+28\cdot 21336321+27\cdot 26355862+20\cdot
60454700=3739782484\approx 3.7\times 10^{9}$

triples $(E,d,n)$. For each such triple, the script searches for a prime
$q=kn+1$ with $k<10^{3}$ such that the hypotheses of Lemma 5.4 are satisfied.
This computation took around $29000$ hours, but was in fact distributed over
$64$ processors, and finished in around $20$ days. For all but $1230$ of the
$3739782484$ triples $(E,d,n)$ the script found some $q$ satisfying the
hypotheses of Lemma 5.4. We are therefore reduced to considering the remaining
$1230$ triples $(E,d,n)$. While these are somewhat too numerous to record
here, we note that the largest value of $n$ appearing in any of these triples
is $n=1861$ and this corresponds to $E$ being the elliptic curve with Cremona
label 210A1 and $d=15$.

###  5.2. A refined sieve

Our adaptation of the method of Kraus (Lemma 5.4) makes use of one auxiliary
prime $q$ satisfying $q=kn+1$ and $(-k/q)=1$. To treat the remaining $1230$
triples $(E,d,n)$, we will use a refined sieve that combines information from
several such primes $q$.

######  Lemma 5.5.

Let $(E,d,n)$ be one of the remaining $1230$ triples. Let $q=kn+1$ be a prime.
Suppose that $(-d/q)=1$ and choose $a$ such that $a^{2}\equiv-d{\text{\rm\
(mod~{}$q$)}}$. Let $c^{\prime}$, $h$, $(r,s)$, $\kappa_{n}$ be as in Lemma
4.2, $m=(2+\kappa_{n}\cdot n)/h\in{\mathbb{Z}}$, and set

$\rho_{1}=(r+sa)^{m}\;\;\mbox{ and }\;\;\rho_{2}=(r-sa)^{m}.$

Let $g_{0}$ be a generator for ${\mathbb{F}}_{q}^{*}$ and set $g=g_{0}^{n}$.
Further, let us define

$\Upsilon_{q}^{\prime\prime}\;=\;\left\\{\left(\rho_{1}\cdot
g^{i},\rho_{2}\cdot
g^{j}\right)\;:\;i=0,1,\dotsc,k-1,~{}j=0,1\right\\}\subset{\mathbb{F}}_{q}\times{\mathbb{F}}_{q},$
$\Upsilon_{q}^{\prime}\;=\;\left\\{(\theta_{1},\theta_{2})\in\Upsilon_{q}^{\prime\prime}\;:\;\theta_{1}\theta_{2}(\theta_{1}-\theta_{2})\neq
0\right\\}$

and

$\Upsilon_{q}\;=\;\left\\{(\theta_{1},\theta_{2})\in\Upsilon_{q}^{\prime}\;:\;a_{q}(H_{\theta_{1},\theta_{2}})\equiv
a_{q}(E){\text{\rm\ (mod~{}$n$)}}\right\\},$

where $H_{\theta_{1},\theta_{2}}/{\mathbb{F}}_{q}$ is the elliptic curve

$H_{\theta_{1},\theta_{2}}\;:\;Y^{2}=X(X+\theta_{1})(X+\theta_{2}).$

Write

$\Phi_{q}^{\prime}\;=\;\left\\{(\theta_{1}-\theta_{2})/a\cdot({\mathbb{F}}_{q}^{*})^{2n}\;:\;(\theta_{1},\theta_{2})\in\Upsilon_{q}\right\\}\subset{\mathbb{F}}_{q}^{*}/({\mathbb{F}}_{q}^{*})^{2n}$

and

$\Phi_{q}\;=\;\begin{cases}\Phi_{q}^{\prime}\cup\\{(\omega/a)\cdot({\mathbb{F}}_{q}^{*})^{2n}\;:\;\omega\in\\{\rho_{1},~{}\rho_{1}g,~{}-\rho_{2},~{}-\rho_{2}g\\}\\}&\text{if
$a_{q}(E)^{2}\equiv 4{\text{\rm\ (mod~{}$n$)}}$}\\\ \hskip
94.72192pt\Phi_{q}^{\prime}&\text{otherwise}.\end{cases}$

If $\overline{\rho}_{F,n}\sim\overline{\rho}_{E,n}$, then necessarily

(29) $c^{\prime}\cdot({\mathbb{F}}_{q}^{*})^{2n}\;\in\;\Phi_{q}.$

###### Proof.

Let $M={\mathbb{Q}}(\sqrt{-d})$ and $\mathfrak{q}\mid q$ be the prime ideal of
${\mathcal{O}}_{M}$ given by (26), so that
${\mathcal{O}}_{M}/\mathfrak{q}={\mathbb{F}}_{q}$ and $\sqrt{-d}\equiv
a{\text{\rm\ (mod~{}$\mathfrak{q}$)}}$. Let $\mu$ be as in Lemma 4.2. From
(15) and its conjugate, we have

(30) $\frac{x+c^{\prime}\sqrt{-d}}{2}\equiv\rho_{1}\cdot\mu^{n}{\text{\rm\
(mod~{}$\mathfrak{q}$)}}\;\;\mbox{ and
}\;\;\frac{x-c^{\prime}\sqrt{-d}}{2}\equiv\rho_{2}\cdot\overline{\mu}^{n}{\text{\rm\
(mod~{}$\mathfrak{q}$)}}.$

Suppose first that $q\nmid y$. Thus both $F$ and $E$ have good reduction at
$q$, and so $a_{q}(F)\equiv a_{q}(E){\text{\rm\ (mod~{}$n$)}}$. It follows
from (17) that $\mathfrak{q}\nmid((x\pm c^{\prime}\sqrt{-d})/2)$ and that
$\mathfrak{q}\nmid\mu$, $\overline{\mu}$. Recall that $g=g_{0}^{n}$ where
$g_{0}$ is a generator for ${\mathbb{F}}_{q}^{*}$; in particular, $g$ is a
non-square, it generates $({\mathbb{F}}_{q}^{*})^{n}$, and has order $k$. We
note that the class of $\overline{\mu}^{n}$ modulo $\mathfrak{q}$ is either in
$({\mathbb{F}}_{q}^{*})^{2n}$ or in $g\cdot({\mathbb{F}}_{q}^{*})^{2n}$. Hence
there is some $\phi\in({\mathbb{F}}_{q}^{*})^{2n}$ and some $0\leq j\leq 1$
such that

$\frac{x-c^{\prime}\sqrt{-d}}{2}\equiv\rho_{2}\cdot g^{j}\cdot\phi{\text{\rm\
(mod~{}$\mathfrak{q}$)}}.$

Now the class of $\mu^{n}/\phi$ modulo $\mathfrak{q}$ belongs to
$({\mathbb{F}}_{q}^{*})^{n}$ and so is equal to $g^{i}$ for some $0\leq i\leq
k-1$. We note that

$\frac{x+c^{\prime}\sqrt{-d}}{2}\equiv\rho_{1}\cdot g^{i}\cdot\phi{\text{\rm\
(mod~{}$\mathfrak{q}$)}}.$

Hence

$\left(\frac{x+c^{\prime}\sqrt{-d}}{2}\,,\,\frac{x-c^{\prime}\sqrt{-d}}{2}\right)\;\equiv\;(\theta_{1}\cdot\phi,\theta_{2}\cdot\phi){\text{\rm\
(mod~{}$\mathfrak{q}$)}}$

where $(\theta_{1},\theta_{2})\in\Upsilon_{q}^{\prime\prime}$. Since
$\mathfrak{q}\nmid((x\pm c^{\prime}\sqrt{-d})/2)$, we see that
$\theta_{1}\theta_{2}\neq 0$. Moreover,
$\theta_{1}-\theta_{2}=c^{\prime}\sqrt{-d}/\phi\in{\mathbb{F}}_{q}^{*}$. Thus
$(\theta_{1},\theta_{2})\in\Upsilon_{q}^{\prime}$. Now recall that the model
for the Frey curve $F$ in (19) is isomorphic to the model given in (23). The
polynomial on the right hand-side of the latter model factors as in (28). Thus
$F/{\mathbb{F}}_{\mathfrak{q}}$ is isomorphic to the elliptic curve

$Y^{2}=X(X+\theta_{1}\phi)(X+\theta_{2}\phi).$

As $\phi$ is a square in ${\mathbb{F}}_{q}$, we see that this elliptic curve
is in turn isomorphic to the elliptic curve $H_{\theta_{1},\theta_{2}}$. Then
$a_{q}(F)=a_{\mathfrak{q}}(F)=a_{\mathfrak{q}}(H_{\theta_{1},\theta_{2}})=a_{q}(H_{\theta_{1},\theta_{2}})$.
Since $a_{q}(E)\equiv a_{q}(F){\text{\rm\ (mod~{}$n$)}}$, it follows that
$(\theta_{1},\theta_{2})\in\Upsilon_{q}$. Moreover,

$c^{\prime}\;=\;\frac{1}{\sqrt{-d}}\cdot\left(\frac{x+c^{\prime}\sqrt{-d}}{2}\;-\;\frac{x-c^{\prime}\sqrt{-d}}{2}\right)\;\equiv\;\frac{\theta_{1}-\theta_{2}}{a}\cdot\phi{\text{\rm\
(mod~{}$\mathfrak{q}$)}}.$

Since $\phi\in({\mathbb{F}}_{q}^{*})^{2n}$, this proves (29).

So far we have considered only the case $q\nmid y$. We know that if $q\mid y$,
then

$a_{q}(E)\equiv\pm(q+1)\equiv\pm 2{\text{\rm\ (mod~{}$n$)}}.$

Thus if $a_{q}(E)^{n}\not\equiv 4{\text{\rm\ (mod~{}$n$)}}$, then $q\nmid y$
and the proof is complete. Suppose $a_{q}(E)^{2}\equiv 4{\text{\rm\
(mod~{}$n$)}}$ and that $q\mid y$. In particular, either $\mathfrak{q}\mid\mu$
or $\mathfrak{q}\mid\overline{\mu}$, but not both (by the coprimality of the
factors on the right hand-side of (17)). Suppose
$\mathfrak{q}\mid\overline{\mu}$. Then $x\equiv c^{\prime}\sqrt{d}{\text{\rm\
(mod~{}$\mathfrak{q}$)}}$ and so from (30) we have

$c^{\prime}\;\equiv\;\frac{\rho_{1}}{\sqrt{-d}}\cdot\mu^{n}\;\equiv\;\frac{\rho_{1}}{a}\cdot\mu^{n}{\text{\rm\
(mod~{}$\mathfrak{q}$)}}.$

However, the class of $\mu^{n}$ modulo $\mathfrak{q}$ belongs to either
$({\mathbb{F}}_{q}^{*})^{2n}$ or $g\cdot({\mathbb{F}}_{q}^{*})^{2n}$,
establishing (29). The case $\mathfrak{q}\mid\mu$ is similar. This completes
the proof. ∎

######  Lemma 5.6.

Let $(E,d,n)$ be one of the remaining $1230$ triples. Let $q=kn+1$ be a prime.
Suppose that $(-d/q)=-1$. Let $M={\mathbb{Q}}(\sqrt{-d})$ and let
$\mathfrak{q}=q{\mathcal{O}}_{M}$. Write
${\mathbb{F}}_{\mathfrak{q}}={\mathcal{O}}_{M}/\mathfrak{q}\cong{\mathbb{F}}_{q^{2}}$.
Let $c^{\prime}$, $h$, $(r,s)$, $\kappa_{n}$ be as in Lemma 4.2, and set
$m=(2+\kappa_{n}\cdot n)/h\in{\mathbb{Z}}$. Define $\rho_{1}=(r+sa)^{m}$,
choose $g_{0}$ to be a generator for ${\mathbb{F}}_{\mathfrak{q}}^{*}$, and
set $g=g_{0}^{n}$. Define

$\Upsilon_{q}^{\prime\prime}\;=\;\left\\{\rho_{1}\cdot
g^{i}\;:\;i=0,1,\dotsc,2q+1\right\\}\subset{\mathbb{F}}_{\mathfrak{q}}^{*},$
$\Upsilon_{q}^{\prime}\;=\;\left\\{\theta\in\Upsilon_{q}^{\prime\prime}\;:\;\theta\neq\theta^{q}\right\\}$

and

$\Upsilon_{q}\;=\;\left\\{\theta\in\Upsilon_{q}^{\prime}\;:\;a_{q}(H_{\theta})\equiv
a_{q}(E){\text{\rm\ (mod~{}$n$)}}\right\\},$

where $H_{\theta}/{\mathbb{F}}_{q}$ is the elliptic curve

$H_{\theta}\;:\;Y^{2}=X(X+\theta)(X+\theta^{q}).$

Let

$\Phi_{q}\;=\;\left\\{(\theta-\theta^{q})/\sqrt{-d}\cdot({\mathbb{F}}_{q}^{*})^{2n}\;:\;\theta\in\Upsilon_{q}\right\\}\subset{\mathbb{F}}_{q}^{*}/({\mathbb{F}}_{q}^{*})^{2n}.$

If $\overline{\rho}_{F,n}\sim\overline{\rho}_{E,n}$ then necessarily (29)
holds.

###### Proof.

We note that in ${\mathbb{F}}_{\mathfrak{q}}$ Galois conjugation agrees with
the action of Frobenius. Thus if $\alpha\in{\mathcal{O}}_{M}$ and
$\overline{\alpha}$ denotes its conjugate, then
$\overline{\alpha}\equiv\alpha^{q}\pmod{\mathfrak{q}}$.

Since $(-d/q)=-1$ and $x^{2}+c^{2}d=y^{n}$ we observe that $q\nmid y$. Thus
$F$ and $E$ both have good reduction at $q$, and so $a_{q}(F)\equiv
a_{q}(E)\pmod{n}$. Let $\mu$ be as in Lemma 4.2. Thus $\mathfrak{q}\nmid\mu$,
$\overline{\mu}$. Recall that $g=g_{0}^{n}$ where $g_{0}$ is a generator for
${\mathbb{F}}_{\mathfrak{q}}^{*}$, whence $\mu^{n}\equiv g^{j}$ for some
integer $j$. From (15),

$\frac{x+c^{\prime}\sqrt{-d}}{2}\equiv\rho_{1}\cdot g^{j}{\text{\rm\
(mod~{}$\mathfrak{q}$)}}\;\;\mbox{ and
}\;\;\frac{x-c^{\prime}\sqrt{-d}}{2}\equiv(\rho_{1}\cdot g^{j})^{q}{\text{\rm\
(mod~{}$\mathfrak{q}$)}}.$

Write $j=i+(2q+2)t$, where $i\in\\{0,1,\dotsc,2q+1\\}$ and $t$ is an integer.
We note that

$g^{2q+2}=(g_{0}^{q+1})^{2n}.$

Moreover, $g_{0}^{q+1}=g_{0}g_{0}^{q}\in{\mathbb{F}}_{q}^{*}$. Thus there is
some $\theta\in\Upsilon_{q}^{\prime\prime}$ and some
$\phi\in({\mathbb{F}}_{q}^{*})^{2n}$ such that

$\frac{x+c^{\prime}\sqrt{-d}}{2}\equiv\theta\cdot\phi{\text{\rm\
(mod~{}$\mathfrak{q}$)}}\;\;\mbox{ and
}\;\;\frac{x-c^{\prime}\sqrt{-d}}{2}\equiv\theta^{q}\cdot\phi{\text{\rm\
(mod~{}$\mathfrak{q}$)}}.$

Since $\mathfrak{q}\nmid c^{\prime}\sqrt{-d}$, we see that
$\theta\neq\theta^{q}$ and so $\theta\in\Upsilon_{q}^{\prime}$. We note that
the model for $F$ in (23) can, over ${\mathbb{F}}_{q}$, be written as

$Y^{2}=X(X^{2}+\phi\cdot(\theta+\theta^{q})X+\phi\cdot(\theta\theta^{q})),$

where the coefficients are fixed by Frobenius and so do indeed belong to
${\mathbb{F}}_{q}$. This model is a twist by $\phi$ of $H_{\theta}$. As $\phi$
is a square in ${\mathbb{F}}_{q}^{*}$, we have
$a_{q}(H_{\theta})=a_{q}(F)\equiv a_{q}(E)\pmod{n}$. Thus
$\theta\in\Upsilon_{q}$. Finally,

$c^{\prime}\;=\;\frac{1}{\sqrt{-d}}\cdot\left(\frac{x+c^{\prime}\sqrt{-d}}{2}\;-\;\frac{x-c^{\prime}\sqrt{-d}}{2}\right)\;\equiv\;\frac{\theta-\theta^{q}}{\sqrt{-d}}\cdot\phi{\text{\rm\
(mod~{}$\mathfrak{q}$)}}.$

Since $\phi\in({\mathbb{F}}_{q}^{*})^{2n}$, this proves (29). ∎

######  Lemma 5.7.

Let $(E,d,n)$ be one of the remaining $1230$ triples. Let
$q_{1},q_{2},\dotsc,q_{r}$ be primes satisfying $q_{i}\equiv 1{\text{\rm\
(mod~{}$n$)}}$. Let

$\psi_{q}\;:\;({\mathbb{Z}}/2n{\mathbb{Z}})^{4}\rightarrow{\mathbb{F}}_{q}^{*}/({\mathbb{F}}_{q}^{*})^{2n},\qquad\psi_{q}(x_{1},x_{2},x_{3},x_{4})=(-3)^{x_{1}}5^{x_{2}}(-7)^{x_{3}}(-11)^{x_{4}}\cdot({\mathbb{F}}_{q}^{*})^{2n}.$

If $(-d/q)=1$, let $\Phi_{q_{i}}$ be as in Lemma 5.5 and if $(-d/q)=-1$, let
$\Phi_{q_{i}}$ be as in Lemma 5.6. Suppose

$\bigcap_{i=1}^{r}\psi_{q_{i}}^{-1}(\Phi_{q_{i}})\;=\;\emptyset.$

Then $\overline{\rho}_{F,n}\nsim\overline{\rho}_{E,n}$.

###### Proof.

Recall, from (11) and (13), that

$c=3^{\beta_{3}}5^{\beta_{5}}7^{\beta_{7}}11^{\beta_{11}}.$

Thus $c\equiv(-1)^{\beta_{3}+\beta_{7}+\beta_{11}}{\text{\rm\ (mod~{}$4$)}}$
and hence, since we choose $c^{\prime}=\pm c$ so that $c^{\prime}\equiv
1{\text{\rm\ (mod~{}$4$)}}$,

$c^{\prime}=(-1)^{\beta_{3}+\beta_{7}+\beta_{11}}\cdot
3^{\beta_{3}}5^{\beta_{5}}7^{\beta_{7}}11^{\beta_{11}}=(-3)^{\beta_{3}}5^{\beta_{5}}(-7)^{\beta_{7}}(-11)^{\beta_{11}}.$

Suppose $\overline{\rho}_{F,n}\sim\overline{\rho}_{E,n}$. Thus

$\psi_{q}(\beta_{3},\beta_{5},\beta_{7},\beta_{11})=c^{\prime}\cdot({\mathbb{F}}_{q_{i}}^{*})^{2n}\in\Phi_{q_{i}}$

by (29). Therefore

$((\beta_{3},\beta_{5},\beta_{7},\beta_{11})\bmod{2n})\;\in\;\bigcap_{i=1}^{r}\psi_{q_{i}}^{-1}(\Phi_{q_{i}})$

giving a contradiction. ∎

We wrote a Magma script which for each of the $1230$ remaining triples
$(E,d,n)$ recursively computes the intersections

$\psi_{q_{1}}^{-1}(\Phi_{q_{1}}),\quad\bigcap_{i=1}^{2}\psi_{q_{i}}^{-1}(\Phi_{q_{i}}),\quad\bigcap_{i=1}^{3}\psi_{q_{i}}^{-1}(\Phi_{q_{i}}),\dots$

where the $q_{i}$ are primes $\equiv 1\pmod{n}$. It stops when the
intersection is empty, or when we have used $200$ primes $q_{i}$, whichever
comes first. If the intersection is empty, then we know from Lemma 5.7 that
$\overline{\rho}_{F,n}\nsim\overline{\rho}_{E,n}$ and we may eliminate the
particular triple $(E,d,n)$ from further consideration. We reached an empty
intersection in $1224$ cases. Table 2 gives the details for the six triples
$(E,d,n)$ where the intersection is non-empty.

Table 2. This table gives the six triples $(E,d,n)$ such that the intersection $\bigcap_{i=1}^{200}\psi_{q_{i}}^{-1}(\Phi_{q_{i}})$ is non-empty. Here the elliptic curve $E$ is given in the first column in Cremona notation. We note that $n=13$ for all six triples. Therefore the intersection given in the last column is a subset of $({\mathbb{Z}}/26{\mathbb{Z}})^{4}$. Elliptic Curve | $d$ | $n$ | $\displaystyle\bigcap_{i=1}^{200}\psi_{q_{i}}^{-1}(\Phi_{q_{i}})$
---|---|---|---
462b1 | $231$ | $13$ | $\\{\;(7,2,19,3),\;(9,1,24,9)\;\\}$
462f1 | $231$ | $13$ | $\\{\;(0,15,25,13),\;(15,18,5,0)\;\\}$
2310j1 | $231$ | $13$ | $\\{\;(11,6,6,18),\;(24,19,19,5)\;\\}$
2310l1 | $231$ | $13$ | $\\{\;(10,5,22,8)\;\\}$
2310m1 | $231$ | $13$ | $\\{(5,14,11,21),\;(7,21,19,19)\;\\}$
2310o1 | $15$ | $13$ | $\\{\;(1,0,1,1)\;\\}$

###  5.3. Proof of Proposition 4.1

We now complete the proof of Proposition 4.1. To summarise, Lemma 4.3 showed
that the only solutions to (11) with exponent $n\in\\{5,7,11\\}$ are the ones
given in the statement of Proposition 4.1. In view of the results of this
section, it only remains to consider the six triples $(E,d,n)$ given in Table
2. To eliminate further cases, we make use of the following result of
Halberstadt and Kraus [17, Lemme 1.6].

######  Theorem 5 (Halberstadt and Kraus).

Let $E_{1}$ and $E_{2}$ be elliptic curves over $\mathbb{Q}$ and write
$\Delta_{j}$ for the minimal discriminant of $E_{j}$. Let $n\geq 5$ be a prime
such that $\overline{\rho}_{E_{1},n}\sim\overline{\rho}_{E_{2},n}$. Let
$q_{1}$, $q_{2}\neq n$ be distinct primes of multiplicative reduction for both
elliptic curves such that $\operatorname{ord}_{q_{i}}(\Delta_{j})\not\equiv
0\pmod{n}$ for $i,j\in\\{1,2\\}$. Then

$\frac{\operatorname{ord}_{q_{1}}(\Delta_{1})\cdot\operatorname{ord}_{q_{2}}(\Delta_{1})}{\operatorname{ord}_{q_{1}}(\Delta_{2})\cdot\operatorname{ord}_{q_{2}}(\Delta_{2})}$

is congruent to a square modulo $n$.

We shall use Theorem 5 and Lemma 5.1 to eliminate the first five of the six
outstanding triples $(E,d,n)$ given in Table 2. In all these cases $n=13$. We
know from the proof of Lemma 5.7 that
$(\beta_{3},\beta_{5},\beta_{7},\beta_{11}){\text{\rm\ (mod~{}$26$)}}$ belongs
to the intersection in the last column of Table 1.

Consider the first triple, corresponding to the first row of the table. The
$\beta_{5}\equiv 1$ or $2\pmod{26}$. But
$\beta_{5}=\operatorname{ord}_{5}(c)$. Thus
$2\operatorname{ord}_{5}(c)+\operatorname{ord}_{5}(d)\equiv
2\beta_{5}+\operatorname{ord}_{5}(231)\equiv 2$ or $4\pmod{13}$ and so by
Lemma 5.1, $5$ must divide the conductor of $E$ which is $462$ giving a
contradiction. The same argument eliminates the second triple.

Next we consider the third triple. Here $\beta_{7}\equiv 6$ or $19\pmod{26}$,
and so $\operatorname{ord}_{7}(c)\equiv\beta_{7}\equiv 6\pmod{13}$. Then
$2\operatorname{ord}_{7}(c)+\operatorname{ord}_{7}(d)\equiv
2\beta_{7}+\operatorname{ord}_{7}(231)\equiv 0\pmod{13}$. By Lemma 5.1, $7$
does not divide the conductor of $E$ which is $2310$, again a contradiction.

We next consider the fourth triple. Here the elliptic curve $E$ with Cremona
reference 2310l1 has minimal discriminant

$\Delta_{E}=2^{4}\times 3^{12}\times 5^{3}\times 7\times 11.$

We apply Theorem 5 with $E_{1}=F$, $E_{2}=E$, $q_{1}=2$ and $q_{2}=3$. From
the proof of Lemma 5.1 we have

$\operatorname{ord}_{2}(\Delta_{F})\equiv-12\equiv
1\pmod{13},\qquad\operatorname{ord}_{3}(\Delta_{F})=2\beta_{3}+\operatorname{ord}_{3}(231)\equiv
2\times 10+1\equiv 8\pmod{13}.$

Hence

$\frac{\operatorname{ord}_{2}(\Delta_{F})\cdot\operatorname{ord}_{3}(\Delta_{F})}{\operatorname{ord}_{2}(\Delta_{E})\cdot\operatorname{ord}_{3}(\Delta_{E})}\equiv\frac{1\times
8}{4\times 12}\equiv 11\pmod{13}$

which is a non-square modulo $13$, contradicting Theorem 5.

Next we consider the fifth triple. Here there are two possibilities for
$(\beta_{3},\beta_{5},\beta_{7},\beta_{11})$. In the second possibility we
have $\beta_{7}\equiv 19\pmod{26}$ which leads to a contradiction via Lemma
5.1. We focus on the first possibility. The minimal discriminant of the curve
$E$ is

$\Delta_{E}=2^{4}\times 3^{8}\times 5\times 7^{3}\times 11.$

We obtain a contradiction by applying Theorem 5 with $q_{1}=2$ and $q_{2}=3$.

We are left with the last triple, which we have been unable to eliminate by
appealing to Theorem 5 or Lemma 5.1, or by further sieving. In fact, (11) has
the solution

(31) $8143^{2}+3^{3}\cdot 5\cdot 7^{2}\cdot 11^{2}=4^{13}.$

Here $n=13$, $d=15$ and $c=3\cdot 7\cdot 11$. We note that the vector of
exponents for this value of $c$ is
$(\beta_{3},\beta_{5},\beta_{7},\beta_{11})=(1,0,1,1)$ which agrees with the
prediction in the last column of the table. Moreover, letting $x=-8143\equiv
1\pmod{4}$, and $y^{n}=4^{13}$ in the Frey curve $F$ gives the elliptic curve
2310o1. To complete the proof, we need to solve (11) with $d=15$ and $n=13$.
We do this by reducing this case to a Thue-Mahler equation using the approach
in the proof of Lemma 4.3. After possibly changing the sign of $x$ so that
$x\equiv 1\pmod{4}$, we have that

$\frac{x+c^{\prime}\sqrt{-15}}{2}=\left(\frac{1-\sqrt{-15}}{8}\right)\left(r\,+\,s\cdot\frac{(1+\sqrt{-15})}{2}\right)^{13},$

where $y=r^{2}+rs+4s^{2}$ for some integers $r$ and $s$. Equating imaginary
parts leads to the conclusion that

$F_{13}(r,s)=\sum_{i=0}^{13}a_{i}r^{13-i}s^{i}=\pm 4\cdot 3^{\beta_{3}}\cdot
5^{\beta_{5}}\,\cdot\,7^{\beta_{7}}\cdot 11^{\beta_{11}},$

where

$\begin{array}[]{|cc|cc|cc|}\hline\cr i&a_{i}&i&a_{i}&i&a_{i}\\\ \hline\cr
0&1&5&36036&10&195624\\\ 1&0&6&-34320&11&-95160\\\
2&-312&7&-226512&12&-51428\\\ 3&-1144&8&-66924&13&924.\\\ 4&8580&9&340340&&\\\
\hline\cr\end{array}$

We solved this Thue-Mahler equation using the Magma package associated to the
paper [16]. The only solution is with

$r=0,\quad s=\pm
1,\quad\beta_{3}=1,\quad\beta_{5}=0,\quad\beta_{7}=1\;\;\mbox{ and
}\;\;\beta_{11}=1.$

This corresponds to the identity (31) and completes the proof of Proposition
4.1.

Remark. It is natural to ask if the case $n=13$ could have been dealt with
entirely using the Thue-Mahler approach, just as we did for $n\in\\{5,7,11\\}$
in Lemma 4.3. The Thue-Mahler solver that we are using can quickly deal with
the Thue-Mahler equations associated to the pairs $(d,n)=(7,13)$ and
$(55,13)$. However, the Thue-Mahler equation for the pair $(d,n)=(231,13)$
appears to be somewhat beyond its capabilities. The approach in [16] reduces
solving a Thue-Mahler equation to a certain number of $S$-unit equations. By
way of example, the Thue-Mahler equation for the pair $(d,n)=(15,13)$ reduces
to solving four $S$-unit equations. The Thue-Mahler equation for the pair
$(d,n)=(231,13)$, on the other hand, corresponds to $2240$ $S$-unit equations.
This explains the effort we invested into eliminating $(d,n)=(231,13)$ via
sieving and appeal to Theorem 5 and Lemma 5.1.

##  6\. Equation (2) with $y$ even : large exponents

From the results of the preceding sections, it remains to solve equation (2)
with $y$ even and exponent $n$ prime and

(32) $n>N(d),$

where $N(d)$ is as defined in (12). We will accomplish this through (quite
careful) application of bounds for linear forms in logarithms.

###  6.1. Upper bounds for $n$ : linear forms in logarithms, complex and
$q$-adic

Our first order of business will be to produce an upper bound for the exponent
$n$; initially it will be somewhat larger than $N(d)$. To this end, as it
transpires, it will prove useful to have at our disposal a lower bound upon
$y$. From the discussion following Lemma 5.2, we have that
$\overline{\rho}_{F,n}\sim\overline{\rho}_{E,n}$ for $E/\mathbb{Q}$ with
nontrivial rational $2$-torsion.

To begin, we will need to treat the case where $y$ in equation (2) has no odd
prime divisors. Suppose that we have a solution to equation (11) with
$y=2^{\kappa}$ for $\kappa$ a positive integer. For the time being, we will
relax our assumptions upon $n$ and suppose only that $n\geq 7$ is prime. Then
the Frey-Hellegouarch curve $F$ has nontrivial rational $2$-torsion and
conductor

$N=2\cdot 3^{\delta_{3}}5^{\delta_{5}}7^{\delta_{7}}11^{\delta_{11}}\;\mbox{
where }\;\delta_{i}\in\\{0,1\\},$

so that

$N\in\\{14,30,42,66,70,154,210,330,462,770,2310\\},$

and minimal discriminant

$-2^{2\kappa n-12}3^{\alpha_{3}}5^{\alpha_{5}}7^{\alpha_{7}}11^{\alpha_{11}}.$

A quick check of Cremona’s tables reveals that we find such curves with
minimal discriminant negative and divisible by precisely $2^{2\kappa n-12}$,
with $n\geq 7$ prime, only for $18$ isomorphism classes of curves, given, in
Cremona’s notation, by

$\begin{array}[]{l}14a4,\,210b5,\,210e1,\,210e6,\,330c1,\,330c6,\,330e4,\,462a1,\,462d1,\,462e1,\\\
462g3,\,770a1,\,770e1,\,770g3,\,2310d4,\,2310n1,\,2310n6,\,2310o1.\\\
\end{array}$

Most of these have $2\kappa n-12=2$ and so $\kappa=1$ and $n=7$. Since
$P(2^{7}-x^{2})>11$ for $1\leq x<11$ odd, only the curve 14a4 with
$\Delta=-2^{2}\cdot 7$ corresponds to a solution, arising from the identity
$11^{2}+7=2^{7}$. Four more curves have $2\kappa n-12=16$ and so $\kappa=2$
and $n=7$. Corresponding identities are

$7^{2}+3^{3}\cdot 5\cdot 11^{2}=2^{14},\;47^{2}+3^{4}\cdot 5^{2}\cdot
11=2^{14},\;\;103^{2}+3\cdot 5^{2}\cdot 7\cdot 11=2^{14},\;\;117^{2}+5\cdot
7^{2}\cdot 11=2^{14},$

arising from the curves 330c1, 210e1, 2310n1 and 770e1, with discriminants

$-2^{16}\cdot 3^{3}\cdot 5\cdot 11^{2},\;\;-2^{16}\cdot 3^{4}\cdot 5^{2}\cdot
7,\;\;-2^{16}\cdot 3\cdot 5^{2}\cdot 7\cdot 11\;\mbox{ and }\;-2^{16}\cdot
5\cdot 7^{2}\cdot 11,$

respectively. Neither 462d1 nor 462e1 lead to any solutions while 2310o1, with
discriminant $-2^{40}\cdot 3^{3}\cdot 5\cdot 7^{2}\cdot 11^{2}$, corresponds
to the identity

$8143^{2}+3^{3}\cdot 5\cdot 7^{2}\cdot 11^{2}=2^{26}.$

We may thus suppose that $y$ is divisible by an odd prime factor, provided
$n\geq 17$.

######  Lemma 6.1.

If $n\geq 17$ and $y$ is even, we have

$y>4n-4\sqrt{2n}+2.$

###### Proof.

By our preceding remarks, there necessarily exists an odd prime $p\mid y$.
Since $\overline{\rho}_{F,n}\sim\overline{\rho}_{E,n}$ where $E/\mathbb{Q}$
has nontrivial rational $2$-torsion, the fact that $\gcd(x,y)=1$ thus allows
us to conclude that

$a_{p}(E)\equiv\pm(p+1){\text{\rm\ (mod~{}$n$)}}.$

From the Hasse-Weil bounds, we have that $a_{p}(E)$ is bounded in modulus by
$2\sqrt{p}$, so that, using the fact that $a_{p}(E)$ is even,

$n<\frac{1}{2}(\sqrt{p}+1)^{2}\leq\frac{1}{2}(\sqrt{y/2}+1)^{2}.$

The desired inequality follows. ∎

As before, define $c$ and $d$ via (13), where, since $y$ is even,
$d\in\\{7,15,55,231\\}$, and let $c^{\prime}=\pm c$ with the sign chosen so
that $c^{\prime}\equiv 1{\text{\rm\ (mod~{}$4$)}}$. To derive an upper bound
upon $n$, we will begin by using (24) to find a “small” linear form in
logarithms. Specifically, let us define

(33)
$\Lambda=\log\left(\frac{x+c^{\prime}\sqrt{-d}}{x-c^{\prime}\sqrt{-d}}\right).$

We prove

######  Lemma 6.2.

If we suppose that

(34) $y^{n}>100\,c^{2}d,$

then

$\log\left|\Lambda\right|<0.75+\log c+\frac{1}{2}\log d-\frac{n}{2}\log y.$

###### Proof.

Assumption (34), together with, say, Lemma B.2 of Smart [33], implies that

$\left|\Lambda\right|\leq-10\log(9/10)\left|\frac{x+c^{\prime}\sqrt{-d}}{x-c^{\prime}\sqrt{-d}}-1\right|=20\log(10/9)\frac{c\sqrt{d}}{y^{n/2}},$

whence the lemma follows. ∎

To show that $\log|\Lambda|$ here is indeed small, we first require an upper
bound upon the exponents $\alpha_{q}$ in equation (11). From (24), we have
that

(35) $\frac{2\cdot
c^{\prime}\sqrt{-d}}{x-c^{\prime}\sqrt{-d}}=\begin{cases}\gamma\cdot\delta^{n}-1&\mbox{
if }d\in\\{7,15,55\\}\\\ \gamma^{(2+\epsilon_{n}\cdot
n)/3}\cdot\delta^{n}-1&\mbox{ if }d=231.\end{cases}$

For prime $q$, let $\overline{\mathbb{Q}_{q}}$ denote an algebraic closure of
the $q$-adic field $\mathbb{Q}_{q}$, and define $\nu_{q}$ to be the unique
extension to $\overline{\mathbb{Q}_{q}}$ of the standard $q$-adic valuation
over $\mathbb{Q}_{q}$, normalized so that $\nu_{q}(q)=1$. For any algebraic
number $\alpha$ of degree $d$ over $\mathbb{Q}$, we define the absolute
logarithmic height of $\alpha$ via the formula

(36)
$h(\alpha)=\dfrac{1}{d}\left(\log|a_{0}|+\sum\limits_{i=1}^{d}\log\max\left(1,|\alpha^{(i)}|\right)\right),$

where $a_{0}$ is the leading coefficient of the minimal polynomial of $\alpha$
over $\mathbb{Z}$ and the $\alpha^{(i)}$ are the conjugates of $\alpha$ in
$\mathbb{C}$. Since $\gcd(x,q)=1$, it follows from (35) that, if we set

$\Lambda_{1}=\begin{cases}\delta^{n}-(1/\gamma)&\mbox{ if
}d\in\\{7,15,55\\}\\\ \delta^{n}-(1/\gamma)^{(2+\epsilon_{n}\cdot n)/3}&\mbox{
if }d=231,\end{cases}$

then $\nu_{q}(\Lambda_{1})\geq\alpha_{q}/2$, for $q\in\\{3,5,7,11\\}$.

To complement this with an upper bound for linear forms in $q$-adic
logarithms, we will appeal to Théorème 4 of Bugeaud and Laurent [11], with, in
the notation of that result, the choices $(\mu,\nu)=(10,5)$.

######  Theorem 6 (Bugeaud-Laurent).

Let $q$ be a prime number and let $\alpha_{1},\alpha_{2}$ denote algebraic
numbers which are $q$-adic units. Let $f$ be the residual degree of the
extension $\mathbb{Q}_{q}(\alpha_{1},\alpha_{2})/\mathbb{Q}_{q}$ and put
$D=[\mathbb{Q}_{q}(\alpha_{1},\alpha_{2}):\mathbb{Q}_{q}]/f$. Let $b_{1}$ and
$b_{2}$ be positive integers and put

$\Lambda_{1}=\alpha_{1}^{b_{1}}-\alpha_{2}^{b_{2}}.$

Denote by $A_{1}>1$ and $A_{2}>1$ real numbers such that

$\log A_{i}\geq\max\left\\{h(\alpha_{i}),\frac{\log
q}{D}\right\\},\;\;i\in\\{1,2\\},$

and put

$b^{\prime}=\frac{b_{1}}{D\log A_{2}}+\frac{b_{2}}{D\log A_{1}}.$

If $\alpha_{1}$ and $\alpha_{2}$ are multiplicatively independent, then we
have the bound

$\nu_{q}(\Lambda_{1})\leq\frac{24q(q^{f}-1)}{(q-1)\log^{4}(q)}\,D^{4}\left(\max\left\\{\log
b^{\prime}+\log\log q+0.4,\frac{10\log q}{D},5\right\\}\right)^{2}\cdot\log
A_{1}\cdot\log A_{2}.$

We will choose $q\in\\{3,5,7,11\\}$ and apply this result with the following
choices of parameters :

$f=1,\;\;D=2,\;\alpha_{1}=\delta,\;\;\alpha_{2}=1/\gamma,\;b_{1}=n$

and

(37) $b_{2}=\begin{cases}\;\;\;\;\;\;\;\;1&\mbox{ if }d\in\\{7,15,55\\}\\\
(2+\epsilon_{n}\cdot n)/3&\mbox{ if }d=231.\end{cases}$

We have

$h(1/\gamma)=\begin{cases}\log 2&\mbox{ if }d\in\\{7,15,55\\}\\\
\frac{3}{2}\log 2&\mbox{ if }d=231\end{cases}$

and

$h(\delta)\leq\frac{1}{2}\log(y/2),$

and hence, from (32) and Lemma 6.1, may choose

$\log A_{1}=\frac{1}{2}\log(y/2)<\frac{1}{2}\log y$

and

$\log A_{2}=\begin{cases}\log 2&\mbox{if }d\in\\{7,15,55\\}\mbox{ and }q=3,\\\
\frac{3}{2}\log 2&\mbox{if }d=231\mbox{ and }q\in\\{3,5,7\\},\\\
\frac{1}{2}\log q&\mbox{otherwise}.\\\ \end{cases}$

Once again appealing to (32) and Lemma 6.1, we have, in all cases, that
$b^{\prime}>5\log q$ and

$b^{\prime}\leq\frac{n}{2\log 2}+\frac{1}{\log y}<0.722n.$

We thus have

$\log b^{\prime}+\log\log q+0.4<1.05\log n,$

whence, from Theorem 6,

$\nu_{q}(\Lambda_{1})<c(d,q)\cdot 1.05^{2}\log^{2}n\log y,$

where

$c(d,q)=\begin{cases}\frac{576\log 2}{\log^{4}3}&\mbox{if
}d\in\\{7,15,55\\}\mbox{ and }q=3,\\\ \frac{288q\log 2}{\log^{4}q}&\mbox{if
}d=231\mbox{ and }q\in\\{3,5,7\\},\\\
\frac{96q}{\log^{3}q}&\mbox{otherwise}.\\\ \end{cases}$

It follows that

(38) $\sum_{q\in\\{3,5,7,11\\}}\alpha_{q}\log q<C(d)\cdot
1.05^{2}\log^{2}n\log y,$

where

$C(d)=2\sum_{q\in\\{3,5,7,11\\}}c(d,q)\log q.$

We have

$C(7)=C(15)=C(55)=2\left(\frac{576\log
2}{\log^{3}3}+\frac{480}{\log^{2}5}+\frac{672}{\log^{2}7}+\frac{1056}{\log^{2}11}\right)<1696$

and

$C(231)=2\left(\frac{864\log 2}{\log^{3}3}+\frac{1440\log
2}{\log^{3}5}+\frac{2016\log
2}{\log^{3}7}+\frac{1056}{\log^{2}11}\right)<2129.$

From (24) and (33), we can write

(39) $\Lambda=n\log\left(\tau\delta\right)+b_{2}\log\left(\gamma\right)+j\pi
i,$

with $b_{2}$ as in (37), while, if $d=231$, we also have

(40)
$\Lambda^{\prime}=3\Lambda=n\log\left(\tau^{\prime}\delta^{3}\gamma^{\epsilon_{n}}\right)+2\log\left(\gamma\right)+j^{\prime}\pi
i.$

In each case, we take the principal branches of the logarithms, choose
$\tau,\tau^{\prime}\in\\{-1,1\\}$ so that
$\mbox{Im}(\log\left(\tau\delta\right))$ and
$\mbox{Im}(\log\left(\tau^{\prime}\delta^{3}\gamma^{\epsilon_{n}}\right))$
have opposite signs to $\mbox{Im}(\log\gamma)$, and take integers $j$ and
$j^{\prime}$ so that $|\Lambda|$ and $|\Lambda^{\prime}|$ are minimal. Notice
that, with these choices,

(41)
$n|\log(\tau\delta)|=|\log\left(\gamma\right)|+|j|\,\pi\pm|\Lambda|,\;\mbox{
if }\;d\in\\{7,15,55\\}$

and

(42)
$n|\log(\tau^{\prime}\delta^{3}\gamma^{\epsilon_{n}})|=2\,|\log\left(\gamma\right)|+|j^{\prime}|\,\pi\pm|\Lambda^{\prime}|.$

Note further that we have

$\begin{array}[]{|c|c|}\hline\cr d&|\log\left(\gamma\right)|\\\ \hline\cr
7&\arccos(1/8)\\\ 15&\arccos(7/8)\\\ 55&\arccos(3/8)\\\ 231&\arccos(5/16).\\\
\hline\cr\end{array}$

Assume first that inequality (34) fails to hold. Then, from (38), we have

$n<\frac{2\log 10}{\log y}+C(d)\cdot 1.05^{2}\log^{2}n,$

contradicting Lemma 6.1, (32) and $C(d)<2129$. It follows that inequality (34)
holds and hence we may conclude, from Lemma 6.2, that

$\log\left|\Lambda\right|<0.75+\frac{1}{2}C(d)\cdot 1.05^{2}\log^{2}n\log
y-\frac{n}{2}\log y.$

From Lemma 6.1, (32) and $C(d)<2129$, we find, in all cases, that

(43) $\log\left|\Lambda\right|<-0.499\,n\,\log y.$

####  6.1.1. Linear forms in three logarithms

To deduce an initial lower bound upon the linear form in logarithms
$\left|\Lambda\right|$, we will use the following, the main result (Theorem
2.1) of Matveev [23].

######  Theorem 7 (Matveev).

Let $\mathbb{K}$ be an algebraic number field of degree $D$ over $\mathbb{Q}$
and put $\chi=1$ if $\mathbb{K}$ is real, $\chi=2$ otherwise. Suppose that
$\alpha_{1},\alpha_{2},\ldots,\alpha_{n_{0}}\in\mathbb{K}^{*}$ with absolute
logarithmic heights $h(\alpha_{i})$ for $1\leq i\leq n_{0}$, and suppose that

$A_{i}\geq\max\\{D\,h(\alpha_{i}),\left|\log\alpha_{i}\right|\\},\;1\leq i\leq
n_{0},$

for some fixed choice of the logarithm. Define

$\Lambda=b_{1}\log\alpha_{1}+\cdots+b_{n_{0}}\log\alpha_{n_{0}},$

where the $b_{i}$ are integers and set

$B=\max\\{1,\max\\{|b_{i}|A_{i}/A_{n_{0}}\;:\;1\leq i\leq n_{0}\\}\\}.$

Define, with $e:=\exp(1)$, further,

$\Omega=A_{1}\cdots A_{n_{0}},$
$C(n_{0})=C(n_{0},\chi)=\frac{16}{n_{0}!\chi}e^{n_{0}}(2n_{0}+1+2\chi)(n_{0}+2)(4n_{0}+4)^{n_{0}+1}\left(en_{0}/2\right)^{\chi},$
$C_{0}=\log\left(e^{4.4n_{0}+7}n_{0}^{5.5}D^{2}\log(eD)\right)\;\mbox{ and
}\;W_{0}=\log\left(1.5eBD\log(eD)\right).$

Then, if $\log\alpha_{1},\ldots,\log\alpha_{n_{0}}$ are linearly independent
over $\mathbb{Z}$ and $b_{n_{0}}\neq 0$, we have

$\log\left|\Lambda\right|>-C(n_{0})\,C_{0}\,W_{0}\,D^{2}\,\Omega.$

We apply Theorem 7 to $\Lambda$ as given in (39), with

$D=2,\;\chi=2,\;n_{0}=3,\;b_{3}=n,\;\alpha_{3}=\tau\delta,\;\alpha_{2}=\gamma,\;b_{1}=j,\;\alpha_{1}=-1,$

and $b_{2}$ as in (37).

We may thus take

$A_{3}=\log y,\;A_{2}=3\log 2,\;A_{1}=\pi\;\mbox{ and }\;B=n.$

Since

$4\,C(3)\,C_{0}=2^{18}\cdot 3\cdot 5\cdot 11\cdot
e^{5}\cdot\log\left(e^{20.2}\cdot 3^{5.5}\cdot 4\log(2e)\right)<1.80741\times
10^{11},$

and

$W_{0}=\log\left(3en\log(2e)\right)<2.63+\log n,$

we may therefore conclude that

$\log\left|\Lambda\right|>-1.181\times 10^{12}\left(2.63+\log n\right)\log y.$

It thus follows from (43) that

$n<2.37\times 10^{12}(\log n+2.63),$

whence

(44) $n<8.22\times 10^{13}.$

To improve this inequality, we appeal to a sharper but less convenient lower
bound for linear forms in three complex logarithms, due to Mignotte (Theorem 2
of [25]).

######  Theorem 8 (Mignotte).

Consider three non-zero algebraic numbers $\alpha_{1}$, $\alpha_{2}$ and
$\alpha_{3}$, which are either all real and ${}>1,$ or all complex of modulus
one and all ${}\not=1$. Further, assume that the three numbers
$\alpha_{1},\alpha_{2}$ and $\alpha_{3}$ are either all multiplicatively
independent, or that two of the numbers are multiplicatively independent and
the third is a root of unity. We also consider three positive rational
integers $b_{1}$, $b_{2}$, $b_{3}$ with $\gcd(b_{1},b_{2},b_{3})=1$, and the
linear form

$\Lambda=b_{2}\log\alpha_{2}-b_{1}\log\alpha_{1}-b_{3}\log\alpha_{3},$

where the logarithms of the $\alpha_{i}$ are arbitrary determinations of the
logarithm, but which are all real or all purely imaginary. We assume that

$0<|\Lambda|<2\pi/w,$

where $w$ is the maximal order of a root of unity in
$\mathbb{Q}(\alpha_{1},\alpha_{2},\alpha_{3})$. Suppose further that

(45)
$b_{2}|\log\alpha_{2}|=b_{1}\,|\log\alpha_{1}|+b_{3}\,|\log\alpha_{3}|\pm|\Lambda|$

and put

$d_{1}=\gcd(b_{1},b_{2}),\;\;d_{3}=\gcd(b_{3},b_{2})\;\mbox{ and
}\;b_{2}=d_{1}b_{2}^{\prime}=d_{3}b_{2}^{\prime\prime}$

Let $K,L,R,R_{1},R_{2},R_{3},S,S_{1},S_{2},S_{3},T,T_{1},T_{2},T_{3}$ be
positive rational integers with

$K\geq 3,\;L\geq 5,\;R>R_{1}+R_{2}+R_{3},\;S>S_{1}+S_{2}+S_{3}\;\mbox{ and
}\;T>T_{1}+T_{2}+T_{3}$

Let $\rho\geq 2$ be a real number. Let $a_{1},a_{2}$ and $a_{3}$ be real
numbers such that

$a_{i}\geq\rho|\log\alpha_{i}|-\log|\alpha_{i}|+2D\,{\rm h}\kern
0.5pt(\alpha_{i}),\qquad i\in\\{1,2,3\\},$

where
$\,D=[\mathbb{Q}(\alpha_{1},\alpha_{2},\alpha_{3}):\mathbb{Q}]\bigm{/}[\mathbb{R}(\alpha_{1},\alpha_{2},\alpha_{3}):\mathbb{R}]$,
and set

$U=\left(\frac{KL}{2}+\frac{L}{4}-1-\frac{2K}{3L}\right)\log\rho.$

Assume further that

(46) $U\geq(D+1)\log(K^{2}L)+gL(a_{1}R+a_{2}S+a_{3}T)+D(K-1)\log
b-2\log(e/2),$

where

$g=\frac{1}{4}-\frac{K^{2}L}{12RST}\;\mbox{ and
}\;b=(b_{2}^{\prime}\eta_{0})(b_{2}^{\prime\prime}\zeta_{0})\left(\prod_{k=1}^{K-1}k!\right)^{-\frac{4}{K(K-1)}},$

with

$\eta_{0}=\frac{R-1}{2}+\frac{(S-1)b_{1}}{2b_{2}}\;\mbox{ and
}\;\zeta_{0}=\frac{T-1}{2}+\frac{(S-1)b_{3}}{2b_{2}}.$

Put

$\mathcal{V}=\sqrt{(R_{1}+1)(S_{1}+1)(T_{1}+1)}.$

If, for some positive real number $\chi$, we have

  1. (i)

$(R_{1}+1)(S_{1}+1)(T_{1}+1)>K\mathcal{M}$,

  2. (ii)

$\mbox{Card}\\{\alpha_{1}^{r}\alpha_{2}^{s}\alpha_{3}^{t}\;:\;0\leq r\leq
R_{1},\;0\leq s\leq S_{1},\;0\leq t\leq T_{1}\\}>L$,

  3. (iii)

$(R_{2}+1)(S_{2}+1)(T_{2}+1)>2K^{2}$,

  4. (iv)

$\mbox{Card}\\{\alpha_{1}^{r}\alpha_{2}^{s}\alpha_{3}^{t}\;:\;0\leq r\leq
R_{2},\;0\leq s\leq S_{2},\;0\leq t\leq T_{2}\\}>2KL$, and

  5. (v)

$(R_{3}+1)(S_{3}+1)(T_{3}+1)>6K^{2}L$,

where

$\mathcal{M}=\max\Bigl{\\{}R_{1}+S_{1}+1,\,S_{1}+T_{1}+1,\,R_{1}+T_{1}+1,\,\chi\;\mathcal{V}\Bigr{\\}},\;\;$

then either

(47)
$\left|\Lambda\right|\cdot\frac{LSe^{LS|\Lambda|/(2b_{2})}}{2|b_{2}|}>\rho^{-KL},$

or at least one of the following conditions (C1), (C2), (C3) holds :

(C1) $|b_{1}|\leq R_{1}$ and $|b_{2}|\leq S_{1}$ and $|b_{3}|\leq T_{1}$,

(C2) $|b_{1}|\leq R_{2}$ and $|b_{2}|\leq S_{2}$ and $|b_{3}|\leq T_{2}$,

(C3) either there exist non-zero rational integers $r_{0}$ and $s_{0}$ such
that

(48) $r_{0}b_{2}=s_{0}b_{1}$

with

(49) $|r_{0}|\leq\frac{(R_{1}+1)(T_{1}+1)}{\mathcal{M}-T_{1}}\;\mbox{ and
}\;|s_{0}|\leq\frac{(S_{1}+1)(T_{1}+1)}{\mathcal{M}-T_{1}},$

or there exist rational integers $r_{1}$, $s_{1}$, $t_{1}$ and $t_{2}$, with
$r_{1}s_{1}\not=0$, such that

(50)
$(t_{1}b_{1}+r_{1}b_{3})s_{1}=r_{1}b_{2}t_{2},\qquad\gcd(r_{1},t_{1})=\gcd(s_{1},t_{2})=1,$

which also satisfy

$|r_{1}s_{1}|\leq\gcd(r_{1},s_{1})\cdot\frac{(R_{1}+1)(S_{1}+1)}{\mathcal{M}-\max\\{R_{1},S_{1}\\}},$
$|s_{1}t_{1}|\leq\gcd(r_{1},s_{1})\cdot\frac{(S_{1}+1)(T_{1}+1)}{\mathcal{M}-\max\\{S_{1},T_{1}\\}}$

and

$|r_{1}t_{2}|\leq\gcd(r_{1},s_{1})\cdot\frac{(R_{1}+1)(T_{1}+1)}{\mathcal{M}-\max\\{R_{1},T_{1}\\}}.$

Moreover, when $t_{1}=0$ we can take $r_{1}=1$, and when $t_{2}=0$ we can take
$s_{1}=1$.

We will apply this result to our $\Lambda$ (if $d\in\\{7,15,55\\}$) or
$\Lambda^{\prime}$ (if $d=231$). To do this, we must distinguish between a
number of cases, depending on $d$ and the signs of the coefficients in (39) or
(40). By way of example, suppose first that $d=231$. If we have $j^{\prime}=0$
or $j^{\prime}=\pm n$, then $\Lambda^{\prime}$ reduces to a linear form in two
logarithms and we may appeal to Corollary 1 of Laurent [19]; actually, what we
state here is specialized for our purposes and follows from the arguments of
[19] (see pages 346 and 347) after a short computation (in each case using, in
the notation of [19], values of $\mu$ in $[0.555,0.562]$ and $\rho$ in
$[6.12,6.31]$).

######  Theorem 9 (Laurent).

Consider the linear form

$\Lambda=c_{2}\log\beta_{2}-c_{1}\log\beta_{1},$

where $c_{1}$ and $c_{2}$ are positive integers, and $\beta_{1}$ and
$\beta_{2}$ are multiplicatively independent algebraic numbers. Define
$\,D=[\mathbb{Q}(\beta_{1},\beta_{2}):\mathbb{Q}]\bigm{/}[\mathbb{R}(\beta_{1},\beta_{2}):\mathbb{R}]$
and set

$b^{\prime}=\frac{c_{1}}{D\log B_{2}}+\frac{c_{2}}{D\log B_{1}},$

where $B_{1},B_{2}>1$ are real numbers such that

$\log
B_{i}\geq\max\\{h(\beta_{i}),|\log\beta_{i}|/D,1/D\\},\;\;i\in\\{1,2\\}.$

Then

$\log\left|\Lambda\right|\geq-CD^{4}\left(\max\\{\log
b^{\prime}+0.21,m_{1}/D,1\\}\right)^{2}\log B_{1}\log B_{2},$

for each pair $(m_{1},C)$ in the following set

$\begin{array}[]{c}\left\\{(14,28.161),(14.5,27.812),(15,27.486),(15.5,27.182),(16,26.896),(16.5,26.627),(17,26.374),\right.\\\
\left.(17.5,26.136),(18,25.911),(18.5,25.697),(19,25.495),(19.5,25.303),(20,25.120)\right\\}.\\\
\end{array}$

If $j^{\prime}=0$, we apply this with

$c_{2}=n,\;\beta_{2}=\tau^{\prime}\delta^{3}\gamma^{\epsilon_{n}},\;c_{1}=2,\;\beta_{1}=1/\gamma,\;D=1,$

whence

$h(\beta_{2})\leq\frac{3}{2}\log(y),\;\;h(\beta_{1})=\frac{3\log 2}{2},\;$

and we can take

$\log B_{2}=\frac{3}{2}\log(y)\;\mbox{ and }\;\log B_{1}=\arccos(5/16).$

Choosing $(m_{1},C)=(18,25.911)$, it follows that

$\log\left|\Lambda^{\prime}\right|\geq-39\arccos(5/16)\left(\log(n)+0.18\right)^{2}\log
y,$

whereby, from (43) and $\Lambda^{\prime}=3\Lambda$, $n<8300$, contradicting
(32). Similarly, if $j^{\prime}=\pm n$, we may apply Theorem 9 with

$c_{2}=n,\;c_{1}=2,\;\beta_{1}=1/\gamma,\;D=1,$

where

$\log\beta_{2}=\log(\tau^{\prime}\delta^{3}\gamma^{\epsilon_{n}})\pm\pi i.$

We can once again choose

$\log B_{2}=\frac{3}{2}\log(y)\;\mbox{ and }\;\log B_{1}=\arccos(5/16),$

and derive a contradiction from taking $(m_{1},C)=(18,25.911)$. Note that from
(40),

$|j^{\prime}|\pi<\pi n+2\arccos(5/16)+3\cdot y^{-0.499n}<\pi n+2.51,$

whereby $|j^{\prime}|\leq n$. We may thus suppose that $|j^{\prime}|<n$ and
$j^{\prime}\neq 0$ (so that, in particular, we have $\gcd(j^{\prime},n)=1$).

We will now apply Theorem 8. From (42), we can take, in the notation of
Theorem 8 and writing $\upsilon=-j^{\prime}/|j^{\prime}|$,

(51)
$b_{1}=2,\;\alpha_{1}=\gamma^{-\upsilon},\;b_{2}=n,\;\alpha_{2}=(\tau^{\prime}\delta^{3}\gamma^{\epsilon_{n}})^{\upsilon},\;b_{3}=|j^{\prime}|\;\mbox{
and }\;\alpha_{3}=-1.$

It follows that

$h(\alpha_{1})=\frac{3\log 2}{2},\;h(\alpha_{2})\leq\frac{3}{2}\log(y)\;\mbox{
and }\;h(\alpha_{3})=0.$

We can thus choose

$a_{1}=\rho\arccos(5/16)+3\log(2),\;a_{2}=\rho\pi+3\log(y)\;\mbox{ and
}\;a_{3}=\rho\pi.$

As noted in [12], if we suppose that $m\geq 1$ and define

(52)
$\begin{array}[]{c}K=[mLa_{1}a_{2}a_{3}],\;R_{1}=[c_{1}a_{2}a_{3}],\;S_{1}=[c_{1}a_{1}a_{3}],\;T_{1}=[c_{1}a_{1}a_{2}],\;R_{2}=[c_{2}a_{2}a_{3}],\\\
\\\
S_{2}=[c_{2}a_{1}a_{3}],\;T_{2}=[c_{2}a_{1}a_{2}],\;R_{3}=[c_{3}a_{2}a_{3}],\;S_{3}=[c_{3}a_{1}a_{3}]\;\mbox{
and }\;T_{3}=[c_{3}a_{1}a_{2}],\\\ \end{array}$

where

(53) $\begin{array}[]{c}c_{1}=\max\\{(\chi
mL)^{2/3},(2mL/a_{1})^{1/2}\\},\;c_{2}=\max\\{2^{1/3}(mL)^{2/3},(m/a_{1})^{1/2}L\\}\\\
\\\ \mbox{ and }c_{3}=(6m^{2})^{1/3}L,\\\ \end{array}$

then conditions (i)-(v) are automatically satisfied. It remains to verify
inequality (46).

Define

$R=R_{1}+R_{2}+R_{3}+1,\;S=S_{1}+S_{2}+S_{3}+1\;\mbox{ and
}\;T=T_{1}+T_{2}+T_{3}+1.$

We choose

$\rho=5.9,\;L=206,\;m=25\;\mbox{ and }\;\chi=2.89,$

so that

$c_{1}=(\chi mL)^{2/3},\;\;c_{2}=2^{1/3}(mL)^{2/3},$

and we have

$K=[K_{1}+K_{2}\log(y)],$

where

$K_{1}=16759141.618\ldots\;\mbox{ and }\;K_{2}=2712508.708\ldots.$

We thus have

$S_{1}=106229,\;S_{2}=65966\;\mbox{ and }\;S_{3}=561893.$

Since Lemma 6.1, (32) and $N(231)=1.2\times 10^{9}$ together imply that

(54) $\log y>22.2,$

we find, after a little work, that $\mathcal{M}=\chi\mathcal{V}$ and that
$g<0.2438$.

Since $\gcd(j^{\prime},n)=1$, we have

$d_{1}=d_{3}=1,\;b_{2}^{\prime}=b_{2}^{\prime\prime}=n,\;$

and it follows that

$\eta_{0}=\frac{1}{2}\left(R_{1}+R_{2}+R_{3}\right)+\frac{1}{n}\left(S_{1}+S_{2}+S_{3}\right)<718258+116252\log
y,$

and, from $|j^{\prime}|<n$,

$\zeta_{0}=\frac{1}{2}\left(T_{1}+T_{2}+T_{3}\right)+\frac{-j^{\prime}}{2n}\left(S_{1}+S_{2}+S_{3}\right)<\frac{1}{2}\left(T_{1}+T_{2}+T_{3}+S_{1}+S_{2}+S_{3}\right),$

whereby

$\zeta_{0}<734089+59408\log y.$

From Lemma 3.4 of [25], we have the inequality

(55) $\log\left(\prod_{k=1}^{K-1}k!\right)^{\frac{4}{K(K-1)}}\geq 2\log
K-3+\frac{2\log\left(2\pi K/e^{3/2}\right)}{K-1}-\frac{2+6\pi^{-2}+\log
K}{3K(K-1)},$

whence, from $K>10^{6}$,

$\log\left(\prod_{k=1}^{K-1}k!\right)^{\frac{4}{K(K-1)}}>2\log K-3.$

It follows, from (54), that

$b<e^{3}n^{2}\frac{\left(718258+116252\log y\right)\left(734089+59408\log
y\right)}{\left(16759141.6+2712508.7\log
y\right)^{2}}<0.023062n^{2}<1.559\times 10^{26},$

where the last inequality is a consequence of (44). The right-hand-side of
inequality (46) is thus bounded above by

$4\log(K)+2.051\times 10^{9}+3.319\times 10^{8}\log(y)+60.312K$

while the left-hand-side satisfies

$U>182.814K+89.635.$

If inequality (46) fails to hold, it follows that

$122.502K<4\log(K)+2.051\times 10^{9}+3.318\times 10^{8}\log(y),$

contradicting

$K>16759141+2712508\log y$

and (54).

Note that we have

$\frac{LSe^{LS|\Lambda|/(2b_{2})}}{2|b_{2}|}=\frac{75611167\,e^{75611167|\Lambda|/n}}{n}$

and hence, from (43),

$\frac{LSe^{LS|\Lambda|/(2b_{2})}}{2|b_{2}|}<\frac{75611167\,\mbox{exp}\left(\frac{75611167}{ny^{0.499n}}\right)}{n}<0.127,$

where the last inequality is a consequence of Lemma 6.1 and (32). If we have
inequality (47), it thus follows that

$\log\left|\Lambda\right|>2-365.65K.$

Once again appealing to (43), we find that

$0.499\,n\log y<365.65K-2<365.65\left(16759141.62+2712508.71\log y\right)$

and so

$n<1.988\times 10^{9}+\frac{1.229\times 10^{10}}{\log y},$

whence, from (54),

(56) $n<2.6\times 10^{9}.$

If, on the other hand, inequality (47) fails to be satisfied, from inequality
(32) and our choices of $S_{1}$ and $S_{2}$, necessarily (C3) holds. If (48)
holds then $n\mid s_{0}$, where

$|s_{0}|\leq\frac{(S_{1}+1)(T_{1}+1)}{\mathcal{M}-T_{1}}\leq\frac{(S_{1}+1)(T_{1}+1)}{R_{1}+1}<\frac{106230\,(106230.73+17193.55\log
y)}{207878+33645\log y}<54287,$

from calculus. It follows that necessarily $s_{0}=0$, a contradiction. We thus
have (50). In particular,

(57) $\left(2t_{1}+r_{1}|j^{\prime}|\right)s_{1}=r_{1}t_{2}n,$

for integers $r_{1},s_{1},t_{1},t_{2}$ with
$\gcd(r_{1},t_{1})=\gcd(s_{1},t_{2})=1$,

(58)
$|s_{1}t_{1}|\leq\gcd(r_{1},s_{1})\cdot\frac{(S_{1}+1)(T_{1}+1)}{\chi\mathcal{V}-T_{1}}<\gcd(r_{1},s_{1})\cdot
81$

and

(59)
$|r_{1}s_{1}|\leq\gcd(r_{1},s_{1})\cdot\frac{(R_{1}+1)(S_{1}+1)}{\chi\mathcal{V}-R_{1}}<\gcd(r_{1},s_{1})\cdot
158,$

again via calculus. It follows that

(60) $|t_{1}|\leq 80\;\;\mbox{ and }\;\;|r_{1}|\leq 157.$

Since $r_{1}$ is coprime to $t_{1}$, necessarily $r_{1}\mid 2s_{1}$, while the
fact that $\gcd(s_{1},t_{2})=1$ while $n>1.2\times 10^{9}$ is prime, together
imply that $s_{1}\mid r_{1}$. We thus have that $r_{1}=\pm s_{1}$ or
$r_{1}=\pm 2s_{1}$, whence, from (57),

(61) $r_{1}j^{\prime}=t_{3}n\pm 2t_{1},$

where $t_{3}=\pm t_{2}$ or $t_{3}=\pm t_{2}/2$. We can thus rewrite
$r_{1}\Lambda^{\prime}$ as a linear form in two logarithms,

$r_{1}\Lambda^{\prime}=n\log\alpha-2\log\beta,$

where

$\log\alpha=r_{1}\log\left(\tau^{\prime}\delta^{3}\gamma^{\epsilon_{n}}\right)+t_{3}\pi
i\;\mbox{ and }\;\log\beta=-r_{1}\log(\gamma)\pm t_{1}\pi i.$

We apply Theorem 9 with

$D=1,\;c_{2}=n,\;\beta_{2}=\alpha,\;c_{1}=2\;\mbox{ and
}\;\log\beta_{1}=\log\beta.$

We may take

$\log B_{2}=\frac{3}{2}|r_{1}|\log(y)\;\mbox{ and }\;\log
B_{1}=|r_{1}|\arccos(5/16)+|t_{1}|\pi,$

whence

$b^{\prime}=\frac{n}{|r_{1}|\arccos(5/16)+|t_{1}|\pi}+\frac{4}{3|r_{1}|\log(y)}.$

From (60), we thus have

$\log B_{1}<448.05.$

Again choosing $(m_{1},C)=(18,25.911)$, we conclude that

$\log|\Lambda^{\prime}|>-39\times 157\times 448.05\log^{2}(n)\log(y)-\log
157.$

From (43) and $\Lambda^{\prime}=3\Lambda$, we thus have

$0.499\,n<\frac{\log 471}{\log y}+2.744\times 10^{6}\log^{2}(n),$

whence, from (54), we once again obtain inequality (56).

We now iterate this argument, using slightly more care and, in each case,
assuming that $n>N(231)=1.2\times 10^{9}$. We begin by taking

$\rho=5.8,\;L=144,\;m=27\;\mbox{ and }\;\;\chi=3.14,$

and, arguing as previously, find that either

(62) $n<1.3\times 10^{9},$

or that we have (61) with

(63) $|t_{1}|\leq 68\;\;\mbox{ and }\;\;|r_{1}|\leq 133.$

From (56), we have that

$b^{\prime}=\frac{n}{|r_{1}|\arccos(5/16)+|t_{1}|\pi}+\frac{4}{3|r_{1}|\log(y)}<e^{18-0.21},$

provided, crudely, $|r_{1}|\geq 39$. Applying Theorem 9 as previously, once
again with $(m_{1},C)=(18,25.911)$, if $39\leq|r_{1}|\leq 133$, we find that

$\log|\Lambda^{\prime}|>-39\times 133\times 380.28\times 18^{2}\log(y)-\log
133,$

while, in case $1\leq|r_{1}|\leq 38$,

(64) $\log|\Lambda^{\prime}|>-39\times 38\times 261.25\log^{2}(n)\log(y)-\log
38.$

Once more, we have, in either case, inequality 62.

To finish the case $d=231$, we repeat this argument, only now using

$\rho=6.3,\;L=125,\;m=27\;\mbox{ and }\;\;\chi=3.28,$

and appealing to Theorem 9 with $(m_{1},C)=(17,26.38)$. We conclude then, in
all cases with $d=231$, that

$n<1.2\times 10^{9}=N(231).$

We argue similarly for $d\in\\{7,15,55\\}$, applying Theorem 8 to $\Lambda$ as
in (39). As in the case $d=231$, we either have inequality (47), or we find
ourselves in the degenerate case where, analogous to (61), we deduce the
existence of “small” integers $t_{1},t_{3}$ and $r_{1}$, the last nonzero,
such that $r_{1}j=t_{3}n\pm 2t_{1}$. In the latter case, we rewrite
$r_{1}\Lambda$ as a linear form in two logarithms,

$r_{1}\Lambda=n\log\alpha-\log\beta,$

where

$\log\alpha=r_{1}\log\left(\tau\delta\right)+t_{3}\pi i\;\mbox{ and
}\;\log\beta=-r_{1}\log(\gamma)\pm 2t_{1}\pi i,$

and apply Theorem 9 with

$D=1,\;c_{2}=n,\;\beta_{2}=\alpha,\;c_{1}=1,\;\log\beta_{1}=\log\beta,\;\log
B_{2}=\frac{1}{2}|r_{1}|\log(y),\;\log B_{1}=|r_{1}||\log\gamma|+2|t_{1}|\pi$

and

$b^{\prime}=\frac{n}{|r_{1}||\log\gamma|+2|t_{1}|\pi}+\frac{2}{|r_{1}|\log(y)}.$

We make our parameter choices for Theorems 8 and 9 as in the following table.
In practice, once we have a reasonable upper bound upon $n,|r_{1}|$ and
$|t_{1}|$, we loop over $|r_{1}|$ and $|t_{1}|$, compute upper and lower
bounds upon $b^{\prime}$ and, in case $b^{\prime}$ potentially exceeds
$\exp(m_{1}-0.21)$, deduce sharpened versions of inequality (64).

$\begin{array}[]{|c|c|c|c|c|c|c|}\hline\cr
d&\rho&L&m&\chi&(m_{1},C)&\mbox{upper bound upon $n$}\\\ \hline\cr
7&4.8&205&45&2.96&(20,25.120)&1.27\times 10^{9}\\\
7&5.1&142&40&3.91&(20,25.120)&6.44\times 10^{8}\\\
7&6.2&100&40&3.00&(14,28.161)&6\times 10^{8}=N(7)\\\ \hline\cr
15&5.8&180&36&2.77&(20,25.120)&6.00\times 10^{8}\\\
15&5.1&140&40&3.00&(20,25.120)&4\times 10^{8}=N(15)\\\ \hline\cr
55&5.7&189&33&3.00&(20,25.120)&1.11\times 10^{9}\\\
55&5.2&144&35&3.41&(18,25.911)&5.22\times 10^{8}\\\
55&6.2&100&40&3.00&(14,28.161)&5\times 10^{8}=N(55)\\\ \hline\cr\end{array}$

This, with Proposition 4.1, completes the proof of Theorem 2.

As mentioned previously, of note here is that the bounds we obtain upon the
exponent $n$ for the equation $x^{2}+c^{2}d=y^{n}$, with
$d\in\\{7,15,55,231\\}$ and $c$ an $S$-unit, $S=\\{3,5,7,11\\}$, are
essentially identical to those deduced for the simpler equation
$x^{2}+d=y^{n}$. This is admittedly not immediately apparent from perusal of
Section 15 of [12], where the treatment of the degenerate cases (which reduce
to linear forms in two logarithms) requires some modification.

##  7\. Concluding remarks

Extending the results of this paper to the more general equation

$x^{2}+D=y^{n},\;\;\gcd(x,y)=1,\;\;D>0,\;\;P(D)\leq 13$

is probably computationally feasible with current technology, if one is
suitably enthusiastic, while the equation

$x^{2}+D=y^{n},\;\;\gcd(x,y)=1,\;\;D>0,\;\;P(D)\leq 17$

is certainly out of reach without the introduction of fundamentally new ideas.
The two main obstructions arise from both large exponents $n$ (where the
corresponding spaces of modular forms have extremely large dimensions) and
moderately small ones (where one will encounter Thue-Mahler equations with
very many associated $S$-unit equations). Additionally, it is possible to
relax the restriction that $\gcd(x,y)=1$ in (2) (at least provided this $\gcd$
is odd), though the computational difficulties increase substantially since,
once again, the spaces of modular forms one encounters have significantly
higher dimensions.

##  8\. Acknowledgements

The authors would like to thank the anonymous referee, Vandita Patel and
Pedro-Jose Carzola Garcia for numerous helpful suggestions that improved both
the exposition and correctness of this paper.

## References

  * [1] C. F. Barros.  On the Lebesgue-Nagell equation and related subjects.  University of Warwick PhD thesis, August 2010.
  * [2] M. Bennett, A. Gherga, V. Patel, and S. Siksek.  Odd values of the Ramanujan tau function.  Math. Ann., 382:203–238, 2022
  * [3] M. A. Bennett, A. Gherga, and A. Rechnitzer.  Computing elliptic curves over $\mathbb{Q}$.  Math. Comp., 88(317):1341–1390, 2019.
  * [4] M. A. Bennett and S. Siksek.  Differences between perfect powers : prime power gaps.  submitted for publication.
  * [5] M. A. Bennett and C. M. Skinner.  Ternary Diophantine equations via Galois representations and modular forms.  Canad. J. Math., 56(1):23–54, 2004.
  * [6] Y. Bilu, G. Hanrot, and P. M. Voutier.  Existence of primitive divisors of Lucas and Lehmer numbers.  J. Reine Angew. Math., 539:75–122, 2001.  With an appendix by M. Mignotte.
  * [7] W. Bosma, J. Cannon, and C. Playoust.  The Magma algebra system. I. The user language.  volume 24, pages 235–265. 1997.  Computational algebra and number theory (London, 1993).
  * [8] C. Breuil, B. Conrad, F. Diamond, and R. Taylor.  On the modularity of elliptic curves over $\mathbb{Q}$: wild 3-adic exercises.  J. Amer. Math. Soc., 14(4):843–939, 2001.
  * [9] Y. Bugeaud.  On the Diophantine equation $x^{2}-p^{m}=\pm y^{n}$.  Acta Arith., 80(3):213–223, 1997.
  * [10] Y. Bugeaud.  On the greatest prime factor of $ax^{m}+by^{n}$. II.  Bull. London Math. Soc., 32(6):673–678, 2000.
  * [11] Y. Bugeaud and M. Laurent.  Minoration effective de la distance $p$-adique entre puissances de nombres algébriques.  J. Number Theory 61:311–342, 1996.
  * [12] Y. Bugeaud, M. Mignotte, and S. Siksek.  Classical and modular approaches to exponential Diophantine equations. II. The Lebesgue-Nagell equation.  Compos. Math., 142(1):31–62, 2006.
  * [13] R. D. Carmichael.  On the numerical factors of the arithmetic forms $\alpha^{n}\pm\beta^{n}$.  Ann. of Math. (2), 15(1-4):49–70, 1913/14.
  * [14] I. Chen.  On the equations $a^{2}-2b^{6}=c^{p}$ and $a^{2}-2=c^{p}$.  LMS J. Comput. Math., 15:158–171, 2012.
  * [15] J. H. E. Cohn.  The Diophantine equation $x^{2}+C=y^{n}$. II.  Acta Arith., 109(2):205–206, 2003.
  * [16] A. Gherga, R. von Känel, B. Matschke, and S. Siksek.  Efficient resolution of Thue-Mahler equations.  to appear.
  * [17] E. Halberstadt and A. Kraus.  Courbes de Fermat: résultats et problèmes.  J. Reine Angew. Math., 548:167–234, 2002.
  * [18] A. Koutsianas.  An application of the modular method and the symplectic argument to a Lebesgue-Nagell equation.  Mathematika, 66(1):230–244, 2020.
  * [19] M. Laurent.  Linear forms in two logarithms and interpolation determinants. II.  Acta Arith., 133(4):325–348, 2008.
  * [20] Maohua Le and G. Soydan.  A brief survey on the generalized Lebesgue-Ramanujan-Nagell equation.  Surveys in Math. App. 15 (2020), 473–523.
  * [21] V. A. Lebesgue.  Sur l’impossibilité, en nombres entiers, de l’équation $x^{m}=y^{2}+1$.  Nouv. Ann. de Math., 9(1), 1850.
  * [22] F. Luca.  On the equation $x^{2}+2^{a}\cdot 3^{b}=y^{n}$.  Int. J. Math. Math. Sci., 29(4):239–244, 2002.
  * [23] E. M. Matveev.  An explicit lower bound for a homogeneous rational linear form in logarithms of algebraic numbers. II.  Izv. Ross. Akad. Nauk Ser. Mat., 64(6):125–180, 2000.
  * [24] B. Mazur.  Rational isogenies of prime degree (with an appendix by D. Goldfeld).  Invent. Math., 44(2):129–162, 1978.
  * [25] M. Mignotte.  A kit on linear forms in three logarithms.  http://www-irma.u-strasbg.fr/~bugeaud/travaux/kit.ps, 2008.
  * [26] P. Mihăilescu.  Primary cyclotomic units and a proof of Catalan’s conjecture.  J. Reine Angew. Math., 572:167–195, 2004.
  * [27] T. Nagell.  Sur l’impossibilité de quelques equations à deux indéterminées.  Norsk Mat. Forenings Skr., 13:65–82, 1923.
  * [28] T. Nagell.  Contributions to the theory of a category of Diophantine equations of the second degree with two unknowns.  Nova Acta Soc. Sci. Upsaliensis (4), 16(2):38, 1955.
  * [29] S. S. Pillai.  On the inequality “$0<a^{x}-b^{y}\leq n$”.  J. Indian Math. Soc., 19:1–11, 1931.
  * [30] I. Pink.  On the Diophantine equation $x^{2}+2^{\alpha}3^{\beta}5^{\gamma}7^{\delta}=y^{n}$.  Publ. Math. Debrecen, 70(1-2):149–166, 2007.
  * [31] K. A. Ribet.  On modular representations of ${\rm Gal}(\overline{\bf Q}/{\bf Q})$ arising from modular forms.  Invent. Math., 100(2):431–476, 1990.
  * [32] S. Siksek.  The modular approach to Diophantine equations.  In Explicit methods in number theory, volume 36 of Panor. Synthèses, pages 151–179. Soc. Math. France, Paris, 2012.
  * [33] N. P. Smart.  The algorithmic resolution of Diophantine equations, volume 41 of London Mathematical Society Student Texts.  Cambridge University Press, Cambridge, 1998.
  * [34] G. Soydan and N. Tzanakis.  Complete solution of the Diophantine equation $x^{2}+5^{a}\cdot 11^{b}=y^{n}$.  Bull. Hellenic Math. Soc., 60:125–151, 2016.
  * [35] N. Tzanakis and B. M. M. de Weger.  On the practical solution of the Thue equation.  J. Number Theory, 31(2):99–132, 1989.
  * [36] N. Tzanakis and B. M. M. de Weger.  Solving a specific Thue-Mahler equation.  Math. Comp., 57(196):799–815, 1991.
  * [37] N. Tzanakis and B. M. M. de Weger.  How to explicitly solve a Thue-Mahler equation.  Compositio Math., 84(3):223–288, 1992.
  * [38] R. von Känel and B. Matschke.  Solving $S$-unit, Mordell, Thue, Thue-Mahler and generalized Ramanujan-Nagell equations via Shimura-Taniyama conjecture.  to appear in Mem. Amer. Math. Soc.
  * [39] B. M. M. de Weger.  Algorithms for Diophantine equations, volume 65 of CWI Tract.  Stichting Mathematisch Centrum, Centrum voor Wiskunde en Informatica, Amsterdam, 1989.
  * [40] B. M. M. de Weger.  The weighted sum of two $S$-units being a square.  Indag. Math. (N.S.), 1(2):243–262, 1990.
  * [41] A. Wiles.  Modular elliptic curves and Fermat’s last theorem.  Ann. of Math. (2), 141(3):443–551, 1995.