How to solve a binary cubic equation in integers

Abstract

Given any polynomial in two variables of degree at most three with rational integer coefficients, we obtain a new search bound to decide effectively if it has a zero with rational integer coefficients. On the way we encounter a natural problem of estimating singular points. We solve it using elementary invariant theory but an optimal solution would seem to be far from easy even using the full power of the standard Height Machine.

1. Introduction

This paper is a kind of sequel to [ 7 ], where a sharp “search bound” for rational solutions of a quadratic equation in several variables was obtained. Namely if the quadratic equation has a rational solution, then there is one whose height is bounded above in terms of the height of the quadratic. Here we prove the following analogue.

Theorem. For $H \geq 1$ let F(X, Y) in ${\bf Z}[X,Y]$ be a polynomial of degree at most three, with coefficients of absolute values at most H, such that the equation $F(x,y)=0$ has a solution in integers x, y. Then there is a solution with

(1) \begin{equation}\max\{|x|,|y|\} \,\leq\, \exp \left((20H)^{600000}\right).\end{equation}

To this day we know no analogue at all of such a result for rational solutions, even for Mordell’s $y^2=x^3+m$ . And similarly for integral solutions of binary quartics, even for $x^4-2y^4+xy+x=m$ .

The result may not surprise the expert, who will recognise the usual bad dependence on H. But in the way we have stated the result, it would be false with the exponent 600000 replaced by any $\kappa<1$ (even if we allow larger constants). So while it is by no means sharp, it is at least not too blunt.

The impossibility of $\kappa<1$ arises in special situations only when F(X, Y) is not absolutely irreducible or of degree less than three. This has been shown already by Kornhauser [ 6 ].

When F is absolutely irreducible and the genus is one, then Baker and Coates [ 1 ] had obtained an upper bound for the size of all integer solutions (even with F of arbitrary degree), which in our case reduces to

\begin{align*}\exp\exp\exp{(2H)^{10^{59049}}}.\end{align*}

This was improved to a single exponential by Schmidt [ 14 ], which in our case reduces to something like (1) with 600000 replaced by $12^{13}=106993205379072$ but no explicit multiplying constant. These authors used the Riemann–Roch Theorem to reduce to linear forms in logarithms. Sometimes Runge’s Method secures a polynomial bound, which then can be comparatively small.

When F is absolutely irreducible and the genus is zero, Poulakis has carried out a detailed study in [ 9 ] and [ 10 ] (and see [ 8 ] for rational points). As in [ 1 ] he treated equations of arbitrary degree, and in [ 10 ] even over an arbitrary number field, so that it is hardly a surprise that for cubics over $\bf Q$ our own bounds are numerically better. Later on we shall refer to some of his results.

In this genus zero situation there may be infinitely many solutions and in that case we have to be content with a search bound in the sense above. This aspect may be slightly less familiar to the expert. Also the size of the singular point, while not at all crucial for our result, seems to raise new questions related to the Height Machine in diophantine geometry and involving the classical algebraic geometry of cubics.

Thanks to the abc conjecture one expects polynomial bounds for $y^2=x^3+m$ . Also $y^2=x^3+kx+m$ is covered by similar conjectures (see for example Silverman [ 15 , p.268]). Maybe there is always a polynomial bound when the number of solutions is finite.

Our methods here are rather standard, except perhaps for the invariant theory to get at singular points. Also we try to reduce the cubic to a particular “semi-rectangular” form whose highest homogeneous part is $XY(X+Y)$ . This allows a subsequent reduction to Tate form using explicit constructions without the need for Riemann–Roch (but sometimes the formulae involved are quite complicated). In special cases it also allows the solutions to be found by ad hoc elementary methods without the need for Runge. We have chosen to present in detail the worst estimate (based on linear forms in logarithms), and then for brevity omit the details when it is reasonably clear that subsequent estimates are much better. But later we also give the details for a slightly different use of linear forms in logarithms, and then again we relax. And we usually give the details in the more elementary estimates, even though they are comparatively infinitesimal especially our best estimate (which is even sharp), because these occupy relatively little space.

Throughout we use the notation

(2) \begin{equation}F=F(X,Y)=aX^3+bX^2Y+cXY^2+dY^3+eX^2+fXY+gY^2+kX+lY+m,\end{equation}

(3) \begin{equation}F_0=F_0(X,Y)=aX^3+bX^2Y+cXY^2+dY^3;\end{equation}

to begin with for algebraic coefficients.

2. Preliminaries on singular points

We use $h(\alpha)$ or more generally $h(\alpha_1,\ldots,\alpha_n)$ for the (non-homogeneous) logarithmic absolute height of algebraic numbers, with $H=e^h$ (non-logarithmic).

Lemma 1. Suppose F is absolutely irreducible with coefficients in a number field K such that

\begin{align*}H(a,b,c,d,e,f,g,k,l,m) \leq \mathcal{H}.\end{align*}

If the corresponding curve has genus zero with a singular point $(\tilde x,\tilde y)$ then $\tilde x,\tilde y$ are in K and

\begin{align*}H(\tilde x,\tilde y) \leq 500{\mathcal{H}}^{5/3}.\end{align*}

Proof. There is a discriminant

\begin{align*}G=19683a^4d^4m^4+\cdots\end{align*}

in ${\bf Z}[a,b,c,d,e,f,g,k,l,m]$ (actually primitive), which vanishes precisely at the singular cubic curves (it is essentially Ruppert’s R of [ 11 , p.181], the Macaulay resultant of $F,{\partial F / \partial X},{\partial F / \partial Y}$ ). It has 2040 terms (we checked this number given in [ 5 , p.4]), but it can be calculated most easily by

\begin{align*}G=19683(T^2+64S^3),\end{align*}

where

\begin{align*}T=a^2d^2m^2+\cdots-{1 \over 5832}f^6,\,\,S={1 \over 6}adfm+\cdots-{1 \over 1296}f^4\end{align*}

are the standard invariants for example in [ 4 , p.160] or [ 12 , pp 189-192]. Here the “dictionary” identification in [ 4 ] between the Dolgachev notation and the Salmon notation has to be extended to our notation (2); namely both sides have to be identified with

\begin{align*}(a,b,e,c,f,k,d,g,l,m)\end{align*}

when we identify the variables $(T_0,T_1,T_2)$ in [ 4 ] with our (X, Y, Z).

When the singular point is a node, it can be shown that the gradient

(4) \begin{equation}\nabla G=\nabla G(F)=\left({\partial G \over \partial a},{\partial G \over \partial b},{\partial G \over \partial c},{\partial G \over \partial d},{\partial G \over \partial e},{\partial G \over \partial f},{\partial G \over \partial g},{\partial G \over \partial k},{\partial G \over \partial l},{\partial G \over \partial m}\right),\end{equation}

evaluated at the coefficient vector

\begin{align*}C(F)=(a,b,c,d,e,f,g,k,l,m),\end{align*}

does not vanish. One way of seeing this would be by [ 5 , theorem 1·5, p.16], applied to the (non-singular) Veronese (see also [ 5 , corollary 1·2, p.14]), which implies that the projective point corresponding to (4) is the same as that corresponding to

(5) \begin{equation}(\tilde x^3,\tilde x^2\tilde y,\tilde x\tilde y^2,\tilde y^3,\tilde x^2,\tilde x\tilde y,\tilde y^2,\tilde x,\tilde y,1).\end{equation}

As G has degree 12, the projective height in (4) is of order at most ${\mathcal{H}}^{11}$ and that in (5) is exactly $H(\tilde x,\tilde y)^3$ , so we obtain the exponent $11/3$ instead of $5/3$ .

However this approach fails for a cusp, because then all the coordinates in (4) vanish, thanks to the defining equations $T=S=0$ for cuspidal cubics.

We present an alternative argument giving at first 11/3 that can then be modified to yield 5/3.

It is more convenient to work with the homogenised

\begin{align*}{\mathcal{F}}({\mathcal{P}})={\mathcal{Z}}^3{F}\left({{\mathcal{X}} \over {\mathcal{Z}}},{{\mathcal{Y}} \over {\mathcal{Z}}}\right)\end{align*}

for ${\mathcal{P}}=({\mathcal{X}},{\mathcal{Y}},{\mathcal{Z}})$ . Then ${\mathcal{F}}({\mathcal{P}})={\mathcal{P}}^{[3]}C({\mathcal{F}})^t$ for

\begin{align*}{\mathcal{P}}^{[3]}=({\mathcal{X}}^3,{\mathcal{X}}^2{\mathcal{Y}},{\mathcal{X}}{\mathcal{Y}}^2,{\mathcal{Y}}^3,{\mathcal{X}}^2{\mathcal{Z}},{\mathcal{X}}{\mathcal{Y}}{\mathcal{Z}},{\mathcal{Y}}^2{\mathcal{Z}},{\mathcal{X}}{\mathcal{Z}}^2,{\mathcal{Y}}{\mathcal{Z}}^2,{\mathcal{Z}}^3)\end{align*}

as in (5), with $C({\mathcal{F}})=C(F)$ being transposed.

We consider the effects of a non-singular linear transformation ${\mathcal{P}}={\mathcal{P}}_1\Phi$ for ${\mathcal{P}}_1=({\mathcal{X}}_1,{\mathcal{Y}}_1,{\mathcal{Z}}_1)$ . Then ${\mathcal{P}}^{[3]}={\mathcal{P}}_1^{[3]}\Phi^{[3]}$ for the “compound” $\Phi^{[3]}$ of the matrix $\Phi$ . Thus ${\mathcal{F}}({\mathcal{P}})={\mathcal{F}}_1({\mathcal{P}}_1)$ for

(6) \begin{equation}C({\mathcal{F}}_1)=C({\mathcal{F}})\Phi^{[3]t}.\end{equation}

By the invariance of G, we have $G({\mathcal{F}}_1)=\phi^{12}G({\mathcal{F}})$ for $\phi=\det\Phi \neq 0$ . Differentiating as in (4) using (6) gives

(7) \begin{equation}\nabla G({\mathcal{F}}_1)\Phi^{[3]}=\phi^{12}\nabla G({\mathcal{F}}).\end{equation}

Suppose it turns out that for some particular $\tilde{{\mathcal{P}}_1}$ and $\lambda_1$ that

(8) \begin{equation}\nabla G({\mathcal{F}}_1)=\lambda_1\tilde{{\mathcal{P}}_1}^{[3]}.\end{equation}

Then it follows from (7) that also

(9) \begin{equation}\nabla G({\mathcal{F}})=\lambda\tilde{{\mathcal{P}}}^{[3]}\end{equation}

for $\tilde {\mathcal{P}}=\tilde{{\mathcal{P}}_1}\Phi$ and $\lambda=\phi^{-12}\lambda_1$ .

If further, ${\mathcal{F}}_1(\tilde{{\mathcal{P}}_1})=0$ (so that $\tilde{{\mathcal{P}}_1}$ lies on the curve ${\mathcal{C}}_1$ corresponding to ${\mathcal{F}}_1$ ), then

\begin{align*}{\mathcal{F}}(\tilde{{\mathcal{P}}})=\tilde{{\mathcal{P}}}^{[3]}C({\mathcal{F}})^t=\tilde{{\mathcal{P}}_1}^{[3]}\Phi^{[3]}C({\mathcal{F}})^t=\tilde{{\mathcal{P}}_1}^{[3]}C({\mathcal{F}}_1)^t={\mathcal{F}}_1(\tilde{{\mathcal{P}}_1})=0\end{align*}

(so that $\tilde{{\mathcal{P}}}$ lies on the curve ${\mathcal{C}}$ corresponding to ${\mathcal{F}}$ - this curve is of course the image of ${\mathcal{C}}_1$ under the map corresponding to $\Phi$ ).

And if yet further, $\nabla_0{\mathcal{F}}_1(\tilde{{\mathcal{P}}_1})=0$ for $\nabla_0=(\partial/\partial{\mathcal{X}},\partial/\partial{\mathcal{Y}},\partial/\partial{\mathcal{Z}})^t$ (so that $\tilde{{\mathcal{P}}_1}$ is singular on ${\mathcal{C}}_1$ ) then similarly

\begin{align*}\nabla_0{\mathcal{F}}(\tilde{{\mathcal{P}}})=(\nabla_0\tilde{{\mathcal{P}}}^{[3]})C({\mathcal{F}})^t=(\nabla_0\tilde{{\mathcal{P}}_1}^{[3]})\Phi^{[3]}C({\mathcal{F}})^t=(\nabla_0\tilde{{\mathcal{P}}_1}^{[3]})C({\mathcal{F}}_1)^t=\nabla_0{\mathcal{F}}_1(\tilde{{\mathcal{P}}_1})=0\end{align*}

(so that $\tilde{{\mathcal{P}}}$ is singular on ${\mathcal{C}}$ ).

Now any nodal $\mathcal{F}$ can be transformed into say ${\mathcal{F}}_1={\mathcal{Y}}_1^2{\mathcal{Z}}_1-{\mathcal{X}}_1({\mathcal{X}}_1-{\mathcal{Z}}_1)^2$ with node $\tilde{{\mathcal{P}}_1}=(1,0,1)$ . After some computation we find that (8) holds with $\lambda_1=-64$ . Thus the node $\tilde{\mathcal{P}}=\tilde{{\mathcal{P}}_1}\Phi$ satisfies (9); and this is nothing other than the projective equality between (4) and (5) above.

As mentioned, this gives the exponent 11/3 in the present lemma. But we can repeat the whole argument with G replaced by T (and $\phi^{12}$ by $\phi^6$ ). Unfortunately (8) no longer holds at a node, but it does at a cusp $\tilde{{\mathcal{P}}_1}=(0,0,1)$ with ${\mathcal{F}}_1={\mathcal{Y}}_1^2{\mathcal{Z}}_1-{\mathcal{X}}_1^3$ and $\lambda_1=4/27$ . In this case we can proceed to an explicit bound as follows.

We find that 5832T has degree 6 and integer coefficients with absolute values at most $M=5832$ and with $N=103$ terms. On differentiating the degree goes down to 5 and then we pick up some extra factors at most 6. We find by standard methods that $H(\tilde x,\tilde y)^3 \leq 6MN{\mathcal{H}}^5$ so that

\begin{align*}H(\tilde x,\tilde y) \leq 154{\mathcal{H}}^{5/3}\end{align*}

for a cusp.

To get a similar bound for a node, we note that as $T^2+64S^3=0$ for $T=T(F),S=S(F)$ not both zero, there is a (unique) U with $S=-U^2,T=8U^3$ . Now

\begin{align*}\nabla G=19683(2T\nabla T+192S^2\nabla S)=314928U^3(\nabla T+12U\nabla S)\end{align*}

so that projectively we have $\nabla T+12U\nabla S$ (instead of the $\nabla T$ for a cusp). This time we need to know that 11664S has degree 4 and integer coefficients of absolute values at most 1944 and 25 terms. Using $U=\sqrt{-S}$ we find that the components of $104976(\nabla T+12U\nabla S)$ have the form $P_5+P_3\sqrt{P_4}$ , where $P_k$ has degree k. As above $P_5$ has integer coefficients of absolute value at most $M_5=18(6M)=629856$ and $N_5=N=103$ terms, while $P_4=-11664S$ has already been described, with $M_4=1944,N_4=25$ . And $P_3=11664\nabla S$ has integer coefficients of absolute values at most $M_3=4M_4=7776$ and $N_3=25$ terms.

Now the height estimation is not quite so standard, and we have to return to first principles with valuations. We find

\begin{align*}H(\tilde x,\tilde y)^3 \leq (M_5N_5+M_3N_3\sqrt{M_4N_4}){\mathcal{H}}^{5}\end{align*}

and so this time

\begin{align*}H(\tilde x,\tilde y) \leq 476{\mathcal{H}}^{5/3}.\end{align*}

That completes the proof of Lemma 1.

Since the invariant T worked for cusps, one might try the lower degree S instead for nodes. But unfortunately the key equation (8) fails for both nodes and cusps. Using different methods on S we can go a bit further and obtain the exponent $3/2\lt5/3$ for cusps; but we omit the details because the argument fails for nodes.

Note that lemma 3·4 (p.56) of Poulakis [ 8 ] gives (for cubics) the bound $H(\tilde x,\tilde y)\leq 2^{54}{\mathcal{H}}^{10}$ . He used ordinary resultants instead of the Macaulay resultant.

We believe that the curious exponent $5/3$ can be reduced, perhaps even to any $\sigma>1$ . This would be best possible in view of the family

(10) \begin{equation}(Y-nX)^2-X(X-n)^2\end{equation}

with $(\tilde x,\tilde y)=(n,n^2)$ . It seems that in (4) there are in some sense large common factors corresponding to reducibility or cusps.

For example, let us drop from projective ${\bf P}_9$ to affine ${\bf A}^2$ using a two-dimensional family linearly parametrized by $F=F_1+uF_u+vF_v$ with fixed $F_1,F_u,F_v$ chosen “at random”. Then $G=0$ defines a curve $\Gamma$ in ${\bf A}^2$ of degree 12 (seemingly absolutely irreducible of genus 10), and the various $\partial G / \partial t$ in (4) are polynomials in u, v of degree at most 11. The divisor of a typical such polynomial is liable to be $D_{132}-11\infty_{12}$ , where $D_{132}$ is a sum of 132 different points and $\infty_{12}$ is the sum of the 12 points at infinity. However it appears that for our $\partial G / \partial t$ we get the special form

(11) \begin{equation}2D_{21}+3D_{24}+iD_6^X+jD_6^Y+(3-i-j)D_6-11\infty_{12},\end{equation}

where i, j are determined by F containing the term $tX^iY^j$ , and where again the subscripts denote the number of different points. From computation it is practically certain that $D_{21}$ and $D_{24}$ correspond to reducible F and cuspidal F respectively (but $D_6^X,D_6^Y,D_6$ probably have no natural geometric interpretation).

We may note in passing that while the cuspidal F are defined by $T=S=0$ , the reducible F seem to be defined only as a determinantal variety and thus far from a complete intersection - see [ 11 , p.178], where no fewer than 45 equations are implicit.

If indeed (11) holds, then we find that the degree of $\nabla G$ in ${\bf P}_9({\bf C}(\Gamma))$ is only 18 due to the cancelling of $D_{21}$ and $D_{24}$ . So by the Height Machine, provided F is not reducible or cuspidal, we would get from (5) and (4)

\begin{align*}3h(\tilde x,\tilde y) \leq 18h_1+O(1+\sqrt{h_1}),\end{align*}

where $h_1$ is the height of (u, v) with respect to a divisor of degree 1. As u, v are themselves of degree 12 we have $h(u,v)=12h_1+O(1+\sqrt{h_1})$ , and also $h(u,v) \leq \log {\mathcal{H}}+O(1)$ ; so we end up with

\begin{align*}h(\tilde x,\tilde y) \leq {1 \over 2}\log {\mathcal{H}}+O(1+\sqrt{\log{\mathcal{H}}}).\end{align*}

In fact this gives any $\sigma>1/2$ . It does not contradict the example (10) because that is not linearly parametrised.

Of course dropping to ${\bf A}^2$ , and a special one at that, loses a lot. Still, it is tempting to think that something like (11) may sometimes persist in ${\bf P}_9$ or at least on some open subset of the singular locus $G=0$ . But even so there is no suitable Height Machine.

Maybe it is relevant here to recall dimensions, some of which are clear from the above discussion. Our cubics live in nine dimensions, and the nodal cubics occupy eight of them (with degree 12). Both the cuspidal and the reducible cubics make up seven dimensions (with degrees 24 and 21 respectively), and the unions of three lines come down to six (with degree 6).

There is a natural analogue of Lemma 1 for quadratic F that are not squares. Then using the determinant instead of G we obtain rather quickly the bound $H(\tilde x,\tilde y) \leq \sqrt{5}{\mathcal{H}}$ (no trouble with cusps). Here the exponent is sharp, as the family $(Y-nX)(X-n)$ , based on the same principle as (10), shows.

3. Preliminaries on special equations

Lemma 2. Let K be a number field of degree D over $\bf Q$ with ring of integers ${\mathcal{O}}$ and discriminant $\Delta$ . Suppose x, y are in $\mathcal{O}$ with

\begin{align*}y^2=ax^3+ex^2+kx+m\end{align*}

for a, e, k, m in $\mathcal{O}$ and non-zero discriminant on the right. Then

\begin{align*}\max\{h(x),h(y)\} \leq (12D)^{17172D}|\Delta|^{216}\exp(4050Dh'),\end{align*}

where $h'=h(a,e,k,m)$ .

Proof. This follows at once from Theorem 2·2 of Bérczes, Evertse and Györy [ 2 ] (p. 730) with $n=3$ and S as the set of all infinite places.

Of course it is linear forms in logarithms which are responsible for the large bound in Lemma 2. By contrast the next result uses (concealed) Runge-type methods so the bounds are much smaller.

Lemma 3.

1. (a) Suppose x, y are in $\bf Z$ with

   (12) \begin{equation}x^2y+gy^2+kx+ly+m=0\end{equation}
   for g, k, l, m in $\bf Z$ of absolute values at most $H \geq 1$ with not both k, m zero. Then
   \begin{align*}\max\{|x|,|y|\} \leq 145H^4.\end{align*}

2. (b) Suppose x, y are in $\bf Z$ with

   \begin{align*}x^3+fxy+ly+m=0\end{align*}
   for f, l, m in $\bf Z$ of absolute values at most $H \geq 1$ with f and $l^3-f^3m$ non-zero. Then
   \begin{align*}\max\{|x|,|y|\} \leq 15H^6.\end{align*}

Proof.

1. (a) If $y=0$ then $kx+m=0$ and we get the bound H. So from now on we assume $y \neq 0$ .

If $|x| \leq 12H^2$ then we use (12) to see that y divides $kx+m$ . If $kx+m \neq 0$ this implies

\begin{align*}|y| \leq |kx+m| \leq 13H^3\end{align*}

and we are done. If $kx+m=0$ and $g \neq 0$ then

\begin{align*}|y| \leq |gy| = |x^2+l| \leq 145H^4,\end{align*}

while if $g=0$ then $x^2+l=0$ contradicting $|x| \leq 12H^2$ .

So we will assume $|x|>12H^2$ .

The following argument was found by examining the Taylor expansions at $\infty$ .

We have

\begin{align*}|x|^2|y|=|gy^2+kx+ly+m|\leq 3H|y|^2+H|x| \leq 3H|y|^2+{1 \over 2}|x|^2|y|\end{align*}

and so $|x|^2 \leq 6H|y|$ . Now

\begin{align*}|x^2+gy+l||y|=|kx+m| \leq 2H|x|\end{align*}

and so

\begin{align*}|x^2+gy+l| \leq {12H^2 \over |x|}<1.\end{align*}

Thus $x^2+gy+l=0$ ; and then also $kx+m=0$ contradicting $|x|>12H^2$ . This settles (a).

Observe that if $k=m=0$ then there are infinitely many solutions with $y=0$ (due to reducibility).

1. (b) We verify

   \begin{align*}(fx+l)(f^3y+f^2x^2-flx+l^2)=l^3-f^3m \neq 0.\end{align*}
   Thus from the first factor $|fx| \leq 2H^3+fH^3$ so $|x| \leq 3H^3$ ; and then from the second factor $|f^3y| \leq 15|f|^3H^6$ so $|y| \leq 15H^6$ .

Observe that if $f=0$ then for example $l=1$ yields infinitely many solutions with $y=-x^3-m$ . And if $l^3-f^3m = 0$ then $f=1$ yields infinitely many solutions with $x=-l$ (also reducibility).

4. Smaller degree or not absolutely irreducible

When F has degree smaller then three, such as the “not-quite-Pell” $-X^2+gY^2-1$ , then Kornhauser [ 6 , p.83)] gives the search bound

(13) \begin{equation}\max\{|x|,|y|\} \leq (14H)^{5H}\end{equation}

for the smallest solution, comfortably better than in our Theorem.

Next, when F has degree three and is not absolutely irreducible but irreducible over $\bf Q$ , such as $X^3-2Y^3$ or $X^3-2$ , then it is a product of three conjugate polynomials of degree one. Then a, d are not both zero and after permuting we can assume $a \neq 0$ . So $F=aLL'L''$ for $L=X+\beta Y+\gamma$ and its conjugates. Then $\beta$ is not in $\bf Q$ , otherwise F would have no zeroes even in ${\bf Q}^2$ .

Using the notation H generally for the height of a polynomial via its vector of (algebraic) coefficients, we can check that

(14) \begin{equation}H(L_1L_2L_3) \geq 2^{-6}H(L_1)H(L_2)H(L_3)\end{equation}

for any $L_1,L_2,L_3$ in $\overline{\bf Q}[X,Y]$ of total degree at most one (in the usual way via Gauss’s Lemma and well-known archimedean inequalities in particular [ 13 , equation (41) of corollary 12, p.249].

For our quantity H we have

\begin{align*}H \geq H(LL'L'') \geq 2^{-6}H(L)H(L')H(L'')=2^{-6}H(L)^3\end{align*}

and so $H(L) \leq 4H^{1/3}$ . Now using

\begin{align*}x=-{\beta'\gamma-\beta\gamma' \over \beta'-\beta},\,\,y={\gamma-\gamma' \over \beta'-\beta}\end{align*}

as the unique solution (if existent) of $F(x,y)=0$ in ${\bf Q}^2$ , we find

\begin{align*}|x| = H(x) \leq 2H(\beta,\gamma,1)H(\beta',\gamma',1) = 2H(L)^2 \leq 32H^{2/3}\end{align*}

and the same bound for $|y|$ . Thus

(15) \begin{equation}\max\{|x|,|y|\} \leq 32H^{2/3}\end{equation}

for all solutions. This is by far the best of all our estimates. It is amusing to note that again the idea of (10) gives the family $(y-nx)^3=2(x-n)^3$ showing here too that the exponent is sharp (probably the only such search bound in this paper).

Note that if $F=0$ does have a rational solution, then the corresponding curve splits into three lines meeting at the corresponding point.

And if F is reducible over $\bf Q$ (still of degree three), then it is LQ for linear L and quadratic Q over $\bf Z$ . Now again from [ 13 ]

\begin{align*}H \geq H(LQ) \geq 2^{-6}H(L)H(Q)\end{align*}

so [ 6 ] for Q (and even L) gives the search bound $\max\{|x|,|y|\} \leq (896H)^{320H}$ .

From now on we shall assume that F is absolutely irreducible (so we can speak of genus) of degree three.

5. Genus one

As previously indicated, the search bounds obtained in this section are for all solutions.

We first treat the case of three points at infinity.

In geometric language we construct a sequence of rational maps ${\mathcal C} \to {\mathcal C}_1 \to {\mathcal C}_2 \to {\mathcal C}_3$ , where the curve $\mathcal C$ is defined by $F=0$ . But we shall not be pedantic about this.

Assume for simplicity that a, d are not both zero (we will address this issue later). We can assume $a \neq 0$ , and then we factorise

\begin{align*}F_0=a(X-\alpha Y)(X-\alpha' Y)(X-\alpha''Y)\end{align*}

with $L={\bf Q}(\alpha,\alpha',\alpha'')$ of degree $D \leq 6$ . We increase the symmetry by transforming this to $X_1Y_1(X_1+Y_1)$ and then we kill the coefficients of $X_1^2,Y_1^2$ to get

(16) \begin{equation}-a^8\delta^4F(X,Y)=F_1(X_1,Y_1)=X_1Y_1(X_1+Y_1)+f_1X_1Y_1+k_1X_1+l_1Y_1+m_1.\end{equation}

We note that the three pairs

(17) \begin{equation}(l_1,m_1),\,\,\,(k_1-l_1,f_1k_1-m_1),\,\,\,(k_1,f_1k_1-m_1)\end{equation}

cannot be (0,0) otherwise $F_1$ would be reducible. The transformation is given by

(18) \begin{equation}X_1=a^3\delta(\alpha-\alpha')(X-\alpha''Y)-a^2(\alpha-\alpha')^2(\alpha''^2e+\alpha''f+g)\end{equation}

(19) \begin{equation}Y_1=a^3\delta(\alpha''-\alpha)(X-\alpha'Y)-a^2(\alpha''-\alpha)^2(\alpha'^2e+\alpha'f+g)\end{equation}

with $\delta=(\alpha''-\alpha)(\alpha''-\alpha')(\alpha'-\alpha) \neq 0$ . And in the other direction we have

(20) \begin{equation}\Delta_0X=a\alpha'(\alpha''-\alpha)X_1+a\alpha''(\alpha'-\alpha)Y_1+\xi\end{equation}

(21) \begin{equation}\Delta_0Y=a(\alpha''-\alpha)X_1+a(\alpha'-\alpha)Y_1+\eta,\end{equation}

where $\Delta_0=a^4\delta^2$ is (up to sign) the discriminant of $F_0$ . Here the coefficients of $X_1,Y_1$ are in ${\mathcal{O}}_L$ because $a\alpha,a\alpha',a\alpha''$ and $a\alpha\alpha',a\alpha'\alpha'',a\alpha''\alpha$ are. So are $\xi,\eta$ because they are polynomials over $\bf Z$ in $e,f,g,a,\alpha,\alpha',\alpha''$ where each $\alpha^{i}\alpha'^{i'}\alpha''^{i''}$ comes multiplied by $a^I$ for $I=\max\{i,i',i''\}$ (we shall repeatedly use this property in what follows). Thus $f_1,k_1,l_1,m_1$ in (16) are also in ${\mathcal{O}}_L$ .

Next we transform (16) to Tate form. We used Riemann–Roch in the standard way, but the reader can be spared this through the identity

(22) \begin{equation}X_1(X_1Y_1+k_1)F_1(X_1,Y_1)=F_2(X_2,Y_2)=Y_2^2-f_2X_2Y_2-l_2Y_2-(X_2^3+e_2X_2^2+k_2X_2+m_2)\end{equation}

with

(23) \begin{equation}X_2=-X_1Y_1,\,\,\,Y_2=X_1^2Y_1+k_1X_1\end{equation}

and inverse (a map ${\mathcal C}_2 \to {\mathcal C}_1$ between curves as above)

(24) \begin{equation}X_1=-{Y_2 \over X_2-k_1},\,\,\,Y_1={X_2^2-k_1X_2 \over Y_2},\end{equation}

where

(25) \begin{equation}f_2=f_1,\,l_2=-m_1,\,e_2=-k_1-l_1,\,k_2=k_1l_1,\,m_2=0.\end{equation}

Finally we pass to Weierstrass form

\begin{align*}Y_3^2=4X_3^3+e_3X_3^2+k_3X_3+m_3\end{align*}

by means of

(26) \begin{equation}X_3=X_2,\,\,Y_3=2Y_2-f_2X_2-l_2\end{equation}

and

(27) \begin{equation}X_2=X_3,\,\,Y_2={1 \over 2}\left(Y_3+f_2X_3+l_2\right).\end{equation}

Here

(28) \begin{equation}e_3=f_2^2+4e_2=f_1^2-4k_1-4l_1,\,\,k_3=2f_2l_2+4k_2=-2f_1m_1,\,\,m_3=l_2^2+4m_2=m_1^2.\end{equation}

From all the above it should be clear that $e_3,k_3,m_3$ lie in L. But in fact they lie in $K={\bf Q}(\alpha)$ . This can be seen by direct computation. But here is a slicker method.

If $L=K$ it is trivial. Otherwise L is a quadratic extension of K with a galois generator that interchanges $\alpha',\alpha''$ (so changes the sign of $\delta$ ). Extending this to L(X, Y) we see from (18) and (19) that it also interchanges $X_1,Y_1$ . So by (16) it interchanges $k_1,l_1$ ; but fixes $f_1$ and $m_1$ (here we implicitly used the algebraic independence of $X_1,Y_1$ ). Now we get what we want from (28).

As $f_1,k_1,l_1,m_1$ are in ${\mathcal O}_L$ so are $e_3,k_3,m_3$ and even in ${\mathcal O}_K={\mathcal O}_L \cap K$ .

Going further along these galois lines, we see from (23) that $X_2$ is fixed but $Y_2$ is sent to

\begin{align*}X_1Y_1^2+l_1Y_1=F_1(X_1,Y_1)-Y_2-f_1X_1Y_1-m_1.\end{align*}

Also $X_3$ is fixed, and a short calculation then shows that $Y_3$ is sent to $2F_1(X_1,Y_1)-Y_3$ .

Let x, y in $\bf Z$ satisfy $F(x,y)=0$ , and define $(x_3,y_3)$ through $(x_1,y_1)$ and $(x_2,y_2)$ according to (18), (19), (23), (26). We deduce from the above that $x_3$ lies in K, and, because $F_1(x_1,y_1)=0$ , that $y_3$ is sent to $-y_3$ . Thus for example $a^2\delta y_3$ is in K. And so $x_3,a^2\delta y_3$ are in ${\mathcal O}_K$ . As

\begin{align*}(a^2\delta y_3)^2=\Delta_0(4x_3^3+e_3x_3^2+k_3x_3+m_3)\end{align*}

(note that the discriminant of the cubic is non-zero because the genus is one) Lemma 2 with $D \leq 3$ shows that

\begin{align*}\max\{h(x_3),h(a^2\delta y_3)\} \leq 36^{51516}|\Delta|^{216}\exp(12150h_3^{\prime})\end{align*}

with

\begin{align*}h_3^{\prime}=h(4\Delta_0,e_3\Delta_0,k_3\Delta_0,m_3\Delta_0).\end{align*}

From (3) follows easily $|\Delta| \leq |\Delta_0| \leq 54H^4$ and

\begin{align*}h(a^2\delta) = {1 \over 2}h(\Delta_0)={1 \over 2}\log|\Delta_0| \leq {1 \over 2}\log(54H^4).\end{align*}

Thus

(29) \begin{equation}\mu_3=\max\{h(x_3),h(y_3)\} \leq CH^{864}\exp(12150h_3^{\prime})\end{equation}

with $C/2=36^{51516}54^{216}$ . We now proceed to estimate $h_3^{\prime}$ .

It can be checked that $f_1,k_1,l_1,m_1$ are polynomials of total degree at most 9 in a, e, f, g, k, l, m and of total degree at most 12 in $\alpha,\alpha',\alpha''$ . By (14) we have

\begin{align*}H \geq H(F_0/a) \geq 2^{-6}H(\alpha)H(\alpha')H(\alpha'') \geq 2^{-6}H(\alpha,\alpha',\alpha'').\end{align*}

Next we check that $f_1,k_1,l_1,m_1$ each involve at most $N=574$ terms (who says mathematicians can’t count) and their coefficients in $\bf Z$ have absolute values at most $M=92$ . It follows that

(30) \begin{equation}h_1=h(f_1,k_1,l_1,m_1) \leq \log(MN)+9\log H+12\log(64H).\end{equation}

Thus by (28) we deduce

\begin{align*}h_3=h(e_3,k_3,m_3) \leq 2h_1+\log 9 \leq 2\log(MN)+42\log H+24\log 64+\log 9.\end{align*}

Finally

\begin{align*}h_3^{\prime} \leq \log(4|\Delta_0|)+h_3 \leq 2\log(MN)+46\log H+\log 216+24\log 64+\log 9.\end{align*}

Thus, recalling (29) we get

(31) \begin{equation}\mu_3 \leq C'H^{559764}\end{equation}

with

\begin{align*}C'=C(MN)^{24300}216^{12150}64^{291600}9^{12150}.\end{align*}

We now have to make our way back from $x_3,y_3$ to x, y. This is relatively easy (and the exponent $\kappa=559764$ will not change except in a silly way right at the end).

First (27) gives

\begin{align*}\mu_2=\max\{h(x_2),h(y_2)\} \leq \log 6+2\mu_3+h(f_2)+h(l_2)\end{align*}

which by (31) and (25) is at most $3C'H^\kappa$ .

Now we have to be careful of the denominators in (24).

Assume for the moment that $y_2 \neq 0$ . Then from (23) we see that $x_2=-x_1y_1 \neq k_1$ , and so (24) gives

(32) \begin{equation}\mu_1=\max\{h(x_1),h(y_1)\} \leq 4\mu_2+h_1+\log 2 \leq 13C'H^\kappa.\end{equation}

But if $y_2=0$ then the Tate form (22) implies $x_2=0,k_1,l_1$ . If $x_2 \neq k_1$ then (24) implies $x_1=0$ so $l_1y_1+m_1=0$ from (16). Thus by the first in (17) $y_1=-m_1/l_1$ . This leads to something a lot better than (32). If $x_2=k_1$ then (23) implies $x_1y_1+k_1=0$ . Now looking at the resultants with respect to $X_1,Y_1$ of $F_1(X_1,Y_1)$ and $X_1Y_1+k_1$ we see that

\begin{align*}y_1=0\,\,\,{\textrm{or}}\,\,\,(k_1-l_1)y_1+(f_1k_1-m_1)=0\end{align*}

and

\begin{align*}x_1=0\,\,\,{\textrm{or}}\,\,\,(f_1k_1-m_1)x_1-k_1(k_1-l_1)=0.\end{align*}

By the second expression of (17) the first here determines $y_1$ and using also the third expression of (17) we see that the second here determines $x_1$ . Again we end up with something better than (32).

Now

\begin{align*}\log|x| \leq \log|\Delta_0x| = h(\Delta_0x) \leq 8\log(2H)+2\mu_1+h(\xi)+\log 3\end{align*}

by (20), and in the usual way $h(\xi) \leq 10\log(2H)+\log 108$ leading to $\log|x| \leq 27C'H^{\kappa}$ , with the same bound for $\log|y|$ by (21). Finally $27C' \leq 20^{585653}$ giving the bound in our Theorem, and for all solutions. This is the worst of all our estimates.

We had assumed that a, d are not both zero. If $a=0,d=0$ then $D \leq 3$ drops to $D=1$ . For example, then b, c are non-zero and the analogues of (18) and (19) are

\begin{align*}X_1=b^2cX+b^2g,\,\,\,Y_1=bc^2Y+c^2e\end{align*}

and even the awful $m_1$ becomes just $b^3c^3(bcm-bgk-cel+efg)$ . As the upper bound in Lemma 2 is dominated by its last term, we improve substantially on the final estimate, getting

(33) \begin{equation}\max\{|x|,|y|\} \leq \exp((20H)^{300000})\end{equation}

for all solutions (the second worst estimate).

Next we do two points at infinity.

Then a, d cannot be both zero, so with $a \neq 0$ we have

\begin{align*}F_0=a(X-\alpha Y)^2(X-\alpha' Y)\end{align*}

for $\alpha \neq \alpha'$ in $\bf Q$ . We then simplify this to $X_1^2Y_1$ and kill the coefficients of $X_1^2,X_1Y_1$ to get

(34) \begin{equation}8a^8(\alpha-\alpha')^6F(X,Y)=F_1(X_1,Y_1)=X_1^2Y_1+g_1Y_1^2+k_1X_1+l_1Y_1+m_1.\end{equation}

Here

(35) \begin{equation}X_1=2a^3(\alpha-\alpha')^2(X-\alpha Y)-a^2(2\alpha\alpha'e+(\alpha+\alpha')f+2g),\end{equation}

(36) \begin{equation}Y_1=2a^3(\alpha-\alpha')^2(X-\alpha' Y)+2a^2(\alpha'^2e+\alpha'f+g).\end{equation}

Also $g_1=2a^2(\alpha^2e+\alpha f+g)$ and $k_1,l_1$ are polynomials of total degree at most 2 in e, f, g, k, l and degree at most 5 in each of $a,\alpha,\alpha'$ with coefficients in $\bf Z$ of absolute values at most 12 and at most 20 terms, and $m_1$ of total degree at most 3 in e, f, g, k, l, m and degree at most 8 in each of $a,\alpha,\alpha'$ with coefficients in $\bf Z$ of absolute values at most 160 and 55 terms. And as before $g_1,k_1,l_1,m_1$ are in $\bf Z$ .

We are now ready to apply Lemma 3(a). Note that $k_1=m_1=0$ would contradict the irreducibility.

It follows that for $x_1,y_1$ defined in terms of x, y by (35), (36) that $\mu_1=\max\{|x_1|,|y_1|\} \leq 154H_1^4$ for

\begin{align*}H_1=\max\{|g_1|,|k_1|,|l_1|,|m_1|\} \leq CH^{27}\end{align*}

and $C=55.160.2^{24}$ . So $\mu_1 \leq 154C^4H^{108}$ and then

\begin{align*}\max\{|x|,|y|\} \leq 10^{48}H^{109}\end{align*}

for all solutions.

Finally we do one point at infinity, so that

(37) \begin{equation}F=a(X-\alpha Y)^3+eX^2+fXY+gY^2+kX+lY+m\end{equation}

for $\alpha$ in $\bf Q$ . Here $\nu=\alpha^2 e+\alpha f+g \neq 0$ otherwise there would be a singularity at infinity $\infty_\alpha$ . Now it suffices to put

\begin{align*}X_1=-a^3\nu(X-\alpha Y),\,\,Y_1=-a^4\nu^2Y\end{align*}

to get

(38) \begin{equation}-a^8\nu^3F(X,Y)=F_1(X_1,Y_1)=X_1^3+e_1X_1^2+f_1X_1Y_1-Y_1^2+k_1X_1+l_1Y_1+m_1\end{equation}

with

\begin{align*}e_1=-a^2e\nu,\,f_1=-a(2\alpha e+f),\,k_1=a^5k\nu^2,\,l_1=a^4(\alpha k+l)\nu,\,m_1=-a^8m\nu^3.\end{align*}

Now (38) is none other than the Tate form, and the reader can easily believe that the resulting estimate is comparable with (33).

6. Genus zero and singular point infinite

Now $F_0$ is $a(X-\alpha Y)^2(X-\alpha'Y)$ or $a(X-\alpha Y)^3$ as above, with singular point $\infty_\alpha$ as above.

In the first case we reduce to (34), and with the Runge-type Lemma 3(a) again we end up with (33) for all solutions. A polynomial bound can also be found in [ 10 , theorem 1·2(i), p.252].

In the second case we are with (37) but now $\nu = 0$ .

If $\beta=2\alpha e+f \neq 0$ we can use

\begin{align*}X_1=3a^3\beta\left(X-\alpha Y+{e \over 3a}\right),\,\,Y_1=3a^3\beta\left(Y+{3ak-e^2 \over 3a\beta}\right)\end{align*}

in ${\bf Z}[X,Y]$ to reduce to

\begin{align*}X_1^3+f_1X_1Y_1+l_1Y_1+m_1\end{align*}

in ${\bf Z}[X_1,Y_1]$ . Here $f_1=3a^2\beta^2 \neq 0$ and by irreducibility $l_1^3-f_1^3m_1 \neq 0$ so now Lemma 3(b) works. We get $\max\{|x|,|y|\} \leq 10^{43}H^{75}$ for all solutions (here the singular point is a node because $f_1 \neq 0$ ).

If $\beta = 0$ then there can be infinitely many solutions; for example $y=x^3$ , so only a search bound is possible. Now

\begin{align*}F=a(X-\alpha Y)^3+e(X-\alpha Y)^2+k(X-\alpha Y)+l_1Y+m\end{align*}

with $l_1=l+\alpha k \neq 0$ by irreducibility.

Here $a\alpha=-b/3$ is actually an integer; call it $b^{\prime}$ . Then multiplying F by $a^2$ gives $C(aX-b'Y)+nY$ for

\begin{align*}C(Z)=Z^3+eZ^2+akZ+a^2m,\,\,\,\,n=a^2l_1=a^2l+ab'k \neq 0.\end{align*}

By hypothesis there are $x^\#,y^\#$ in $\bf Z$ with $C(ax^\#-b'y^\#)+ny^\#=0$ . We can find $x_1,y_1$ in $\bf Z$ congruent to $x^\#,y^\#$ modulo na with $|x_1|,|y_1| \leq |na|/2$ . Then

\begin{align*}C(ax_1-b'y_1)+ny_1=naz_1\end{align*}

for some $z_1$ in $\bf Z$ . Thus $C(ax-b'y)+ny=0$ for $x=x_1-b'z_1,\,y=y_1-az_1$ a small solution. We have

\begin{align*}|naz_1| \leq 4H^3|na|^3+{1 \over 2}|n^2a|\end{align*}

so

\begin{align*}|x| \leq {1 \over 2}|na|+H(4H^3|na|^2+{1\over 2}|n|)\end{align*}

and then $|n| \leq 2H^3$ gives $|x| \leq 18H^{12}$ ; with the same bound for $|y|$ . So we get the search bound $\max\{|x|,|y|\} \leq 18H^{12}$ (here the singular point is a cusp). A polynomial bound follows also from [ 10 , theorem 1·1, p.252], because $(x^\#,y^\#)$ must be a simple point.

7. Genus zero and singular point finite

By Lemma 1, this point $(\tilde x,\tilde y)$ has $\tilde x=r/n,\tilde y=s/n$ with $n \geq 1$ and $\max\{|r|,|s|,n\} \leq 500H^{5/3}$ . We shift this to (0,0) using

(39) \begin{equation}X_1=nX-r,\,\,Y_1=nY-s\end{equation}

yielding $n^3F(X,Y)=F_0(X_1,Y_1)+Q(X_1,Y_1)$ with

(40) \begin{equation}Q(X_1,Y_1)=e_1X_1^2+f_1X_1Y_1+g_1Y_1^2\end{equation}

and

\begin{align*}e_1=3ar+bs+en,\,\,f_1=2br+2cs+nf,\,\,g_1=cr+3ds+gn.\end{align*}

Thus $F(x,y)=0$ leads to $F_0(x_1,y_1)+Q(x_1,y_1)=0$ with $x_1,y_1$ as in (39).

We write $x_1=zu,y_1=zv$ for u, v coprime. If $z=0$ then we hit the singular point and the estimate is easy, giving of course $\max\{|x|,|y|\} \leq 500H^{5/3}$ . Otherwise $zF_0(u,v)=-Q(u,v)$ ; thus $F_0(u,v)$ divides both $F_0(u,v)$ and Q(u, v) (note that $F_0(u,v)\neq 0$ otherwise $Q(u,v)=0$ would give reducibility).

Now it is reasonably well known that the highest common factor of $F_0(u,v)$ and Q(u, v) must divide the resultant $W \neq 0$ of $F_0(X_1,Y_1)$ and $Q(X_1,Y_1)$ . We therefore obtain the equation $F_0(u,v)=w$ with $0<|w| \leq |W|$ .

This is a Thue equation if $F_0$ is irreducible over $\bf Q$ , and then we use Bugeaud and Györy [ 3 , theorem 3, p.275, equation (3·3)]. Our W is a polynomial of total degree at most 5 in a, b, c, d, e, f, g, k, l, m and total degree at most 3 in r, s, n, so we get

\begin{align*}|w| \leq 2052H^5(500H^{5/3})^3=CH^{10}\end{align*}

with $C=256500000000$ . Thus for example

(41) \begin{equation}\max\{|u|,|v|\} \leq M=\exp(2.10^{58}H^5).\end{equation}

Then

\begin{align*}|z| \leq |Q(u,v)| \leq 15H(500H^{5/3})M^2 \leq M^3\end{align*}

and $\max\{|nx-r|,|ny-s|\} \leq M^4$ . Finally

\begin{align*}\max\{|x|,|y|\} \leq M^5=\exp\!(10^{59}H^5)\end{align*}

for all solutions. When there are three points at infinity then there is also an exponential estimate in [ 9 , theorem 1·2(i), p.329].

If $F_0=L_0Q_0$ is reducible over $\bf Q$ with coprime $L_0,Q_0$ , then the estimates are elementary. For example one can take $M=72CH^{20}$ in (41) leading to $\max\{|x|,|y|\} \leq 10^{71}H^{100}$ for all solutions.

If $L_0,Q_0$ above cannot be taken as coprime, then $F_0(X,Y)=a(X-\alpha Y)^3$ and there can be infinitely many solutions, as for example with $x^3=y^2$ or $x^3-x^2=y^2$ , so once more it is a search bound that we need. We write as before $\alpha=b^{\prime}/a$ . After multiplying by $a^2$ we get

(42) \begin{equation}(aX_1-b^{\prime}Y_1)^3+e_1^{\prime}(aX_1-b^{\prime}Y_1)^2+f_1^{\prime}(aX_1-b^{\prime}Y_1)Y_1+g_1^{\prime}Y_1^2\end{equation}

with

\begin{align*}e_1^{\prime}=e_1,\,\,f_1^{\prime}=af_1+2b^{\prime}e_1,\,\,g_1^{\prime}=a^2g_1+ab^{\prime}f_1+b^{\prime 2}e_1 \neq 0\end{align*}

by irreducibility.

We introduce a parameter T carefully by $g_1^{\prime}Y_1=T(aX_1-b^{\prime}Y_1)$ . On the curve defined by the vanishing of (42) we get

(43) \begin{equation}ag_1^{\prime 2}X_1=-e_1^{\prime}g_1^{\prime 2}-(f_1^{\prime}g_1^{\prime}+b^{\prime}e_1^{\prime}g_1^{\prime})T-(g_1^{\prime}+b^{\prime}f_1^{\prime})T^2-b^{\prime}T^3,\end{equation}

(44) \begin{equation}g_1^{\prime 2}Y_1=-e_1^{\prime}g_1^{\prime}T-f_1^{\prime}T^2-T^3.\end{equation}

Now $F(x^\#,y^\#)=0$ leads to $x^\#_1$ congruent to $-r$ modulo n and $y^\#_1$ congruent to $-s$ modulo n by (39) and a corresponding $t^\#$ in $\bf Q$ (provided we do not have $ax^\#_1-b'y^\#_1=0$ , which would lead to $y^\#_1=0$ so $x^\#_1=0$ and again we have hit the singular point). From (44) we see that $t^\#$ is integral over $\bf Z$ so in $\bf Z$ .

We next choose t in $\bf Z$ congruent to $t^\#$ modulo $g_1^{\prime 2}an$ with $|t| \leq |g_1^{\prime 2} an|/2$ . The resulting $x_{1},y_{1}$ coming from (43), (44) are still integers because of the part $ag_1^{\prime 2}$ of the modulus; and they are still congruent to $-r,-s$ modulo n because of the part n. Thus via (39) they give $F(x,y)=0$ .

Now the coefficients in (40) are at most $2500H^{8/3}$ in absolute value. Thus those in (18) at most $7500H^{14/3}$ . We end up with the search bound $\max\{|x|,|y|\} \leq 10^{55}H^{50}$ . There is also a polynomial bound in [ 10 , theorem 1·1, p.252], because by Lemma 1 we can assume that our $(x^\#,y^\#)$ is simple.