MATHEMATICS OF COMPUTATION Volume 70, Number 236, Pages 1661–1674 S 0025-5718(01)01275-3 Article electronically published on March 7, 2001

SIEVING FOR RATIONAL POINTS ON HYPERELLIPTIC CURVES

SAMIR SIKSEK

To Shaheen

Abstract. We give a new and efficient method of sieving for rational points on hyperelliptic curves. This method is often successful in proving that a given hyperelliptic curve, suspected to have no rational points, does in fact have no rational points; we have often found this to be the case even when our curve has points over all localizations ℚ_{p}. We illustrate the practicality of the method with some examples of hyperelliptic curves of genus 1.

1. Introduction

By a hyperelliptic curve we mean a curve of the form

C : y^{2} = f(x), (1)

where f is a nonconstant polynomial in ℤ[x] with no repeated roots. We restrict our attention to the case where the degree of f is even, though doubtless the methods of this paper can easily be adapted to the case where f has odd degree, and presumably with more trouble to other classes of algebraic curves. We are concerned with finding rational points on (1), and with proving that there are no rational points if this seems to be the case. Using what is essentially an algorithm due to Birch and Swinnerton-Dyer, one can check whether equation (1) is everywhere locally soluble; this is explained in Section 3. Trivially, this is a necessary condition for the existence of rational points, and so we assume that equation (1) is everywhere locally soluble. It is trivial to check if the points at infinity on (1) are rational, and thus we may restrict our attention to points on the affine model. By computing the real roots of f, we can write down a finite list of disjoint real intervals I_{1}, …, I_{m} such that for any real number x we have that f(x) ≥ 0 if and only if x ∈ I_{j} for some j. We let I be one of these intervals, and we look at rational points (x, y) on the affine curve C, such that x ∈ I. We can write

x = \frac{X}{Z} , y = \frac{Y}{Z^{n}} ,

\begin{matrix}c \\ ◯ \end{matrix}2001 American Mathematical Society

Received by the editor November 21, 1996 and, in revised form, January 28, 1997 and November 29, 1999.

2000 Mathematics Subject Classification. Primary 11G05; Secondary 11Y16, 11Y50.

Key words and phrases. Diophantine equations, elliptic curves.

The author’s research was conducted while the author was at the University of Kent and funded by a grant from the EPSRC (UK)..

where 2n = d is the degree of f and X, Y, Z are integers satisfying

(2) X, Z are coprime integers, Z ≥ 1, and \frac{X}{Z} ∈ I.

Let F be the homogeneous binary form satisfying F (X, Z) = Z^{d}f(X/Z). Then

Y^{2} = F (X, Z). (3)

In this paper we use quadratic reciprocity to derive finite sets of congruences for expressions of the form βX − αZ for suitably chosen pairs of integers α, β. It is these congruences, gathered for many such pairs α, β, which will help us sieve for solutions to (3) satisfying (2), which in turn correspond to rational points on (1). In practice, we have often found that these congruences are “incompatible with the curve” (a term explained later), and this leads to a proof of the nonexistence of rational points on the curve. This is illustrated by the example in Section 4. Even when the congruences derived are “compatible with the curve” they can still help in finding rational points as in the example in Section 9.

The basic idea in this paper is motivated by Lind’s counterexample to the Hasse principle (see [Sil], pages 316–318, or [Ca2], page 284). I am grateful to Nigel Smart for many helpful discussions during the course of writing this paper, and to John Cremona and the referee for pointing out many corrections and improvements in both the presentation and contents of this paper.

2. Quadratic reciprocity

Suppose that α, β is a given pair of coprime integers such that

F (α, β) = γδ^{2}, (4)

where γ, δ are nonzero integers, and γ is square-free and not equal to 1. We want to derive information about the prime divisors of βX − αZ where (X, Z, Y) is any point on (3) satisfying the conditions (2). As we will see, this will allow us to write down a finite set of congruences for βX − αZ.

Lemma 2.1. Suppose the triple (X, Z, Y) satisfies (2) and (3). Suppose p^{r}|(βX − αZ), where p is a prime and r ≥ 1. Then γδ^{2} is congruent to a square modulo p^{r}.

Proof. Suppose that p^{r}|(βX − αZ), where p is a prime and r ≥ 1. Since X, Z are coprime, and α, β are coprime, it follows that there exists an integer λ, not divisible by p, such that

X ≡ λα, Z ≡ λβ (mod p^{r}).

Combining these congruences with the equations (3) and (4) we get

Y^{2} = F (X, Z) ≡ λ^{2n}F (α, β) = γδ^{2}.λ^{2n} (mod p^{r}). (5)

The lemma now follows.

We need the following standard result from the theory of quadratic reciprocity.

Lemma 2.2. Suppose as above that γ is a square-free integer, γ ≠ 0, 1, and let

N = \{ \begin{matrix}|γ| & if & γ ≡ 1 & (mod 4), \\ 4|γ| & if & γ ≡ 2 or 3 & (mod 4). \end{matrix}

Then there exists a unique subgroup H of (ℤ/Nℤ)^{∗} such that if p is any prime not dividing N, then γ is a square modulo p if and only if the reduction of p modulo N is contained in H. Moreover H has index 2 in (ℤ/Nℤ)^{∗}. Further −1 ∈ H if and only if γ > 0.

Proof. The Lemma follows trivially from the definition and standard properties of of the Kronecker-Jacobi symbol (see [Cohen], page 28). Using these same properties, the subgroup H can be computed easily.

Before proceeding further, we set the following notations. If R is a unique factorization domain, we denote by ℙC(R) the set of triples (X, Z, Y) in R^{3} such that X and Z are coprime and equation (3) is satisfied. Moreover we let

R(p)  be the quantity sup {v_{p}(βX − αZ) | (X, Z, Y) ∈ ℙC(ℤ_{p})} ,
p_{1}, …, p_{l}  be the distinct primes dividing N,
q_{1}, …, q_{m}  be the distinct primes dividing 2δ which do not divide N and

whose reduction modulo N is not contained in H.

Finally we define B to be the set of all products p_{1}^{r_{1}} ⋯ p_{l}^{r_{l}}q such that • 0 ≤ r_{i} ≤ R(p_{i}) for i = 1, …, l,

• q = 1 or q = q_{j} for some j such that R(q_{j}) ≥ 1.

Lemma 2.3. For any prime p dividing N we have R(p) ≤ 2v_{p}(δ) + 1. It trivially follows that the set B is finite.

Proof. Suppose first that p is odd. Now p divides N and hence it divides γ exactly once. Suppose that (X, Z, Y) ∈ ℙC(ℤ_{p}) and let e = v_{p}(δ), r = v_{p}(βX − αZ). If r ≥ 2e + 2, then by equation (5) we get that

Y^{2} ≡ p^{2e+1} × (p-adic unit) (mod p^{2e+2})

giving a contradiction. This proves Lemma 2.3 when p is odd.

Suppose now that p = 2. The proof is exactly the same as above in the case 2|γ. So suppose that γ is odd. Since 2 divides N we must have that γ ≡ 3 (mod 4). Thus if r ≥ 2e + 2, then

Y^{2} ≡ 3 × 2^{2e} (mod 2^{2e+2}),

which implies that 3 is a square modulo 4 giving a contradiction. This completes the proof.

We come now to our main theorem which gives us our possible congruences for βX − αZ.

Theorem 2.4. Let I be an interval in ℝ such that f(x) ≥ 0 for all x ∈ I. Let

ζ = \begin{cases}−1 & if βw − α is strictly negative for all w in I, \\ 1 & otherwise. \end{cases}

Moreover suppose that (X, Z, Y) is an integer triple satisfying (3) and (2). Then

βX − αZ ≡ ζP h (mod P.N) (6)

for some P ∈ B, and h ∈ H.

Proof. We first note that βX −αZ cannot be zero for otherwise it is easy to deduce that γ is a square, contradicting our assumptions. Write

|βX − αZ| = p_{1}^{r_{1}} ⋯ p_{l}^{r_{l}}M, (7)

where M is a positive integer coprime to N, and r_{1}, …, r_{l} are nonnegative. We want to write down a set of possible congruences for |βX −αZ|. We begin by doing this for M.

We claim that M satisfies one of the following congruences: either

M ≡ h (mod N)

for some h ∈ H, or

M ≡ hq_{j} (mod Nq_{j})

for some h ∈ H and some q_{j} satisfying R(q_{j}) ≥ 1. To see this, suppose that q is a prime dividing M. Recall that M is coprime to N and thus q does not divide γ. By Lemma 2.1 we see that if q does not divide 2δ, then γ is a quadratic residue modulo q and so by Lemma 2.2 the reduction of q modulo N is in H. Hence we can write

M = q_{1}^{s_{1}} ⋯ q_{m}^{s_{m}}M′,

where the reduction of M′ modulo N is contained in H.

Recall that H is a subgroup of index 2 in (ℤ/Nℤ)^{∗}. Thus if ∑ s_{j} ≡ 0 (mod 2), then the reduction of M modulo N is in H; that is M ≡ h (mod N) for some h ∈ H.

Otherwise M = q_{j}M′′ for some 1 ≤ j ≤ m, where M′′ ≡ h (mod N) for some h ∈ H. Thus M ≡ h_{i}q_{j} (mod Nq_{j}), and as q_{j} divides M and thus divides βX −αZ, it follows from the definition of R above that R(q_{j}) ≥ 1. This establishes our claim.

Next we observe from (7), again by the definition of R, that 0 ≤ r_{i} ≤ R(p_{i}) for i = 1, …, l. Thus

|βX − αZ| ≡ P.h (mod P.N)

for some P ∈ B and h ∈ H.

The theorem now follows trivially in the case that w → βw − α has a fixed sign over the interval I. Thus we may suppose that β is nonzero and \frac{α}{β} is contained in I. But by assumption f(x) ≥ 0 for all x in I. Thus γδ^{2} = β^{2n}f(α/β) ≥ 0, where 2n is the degree of f. Hence as γ, δ are nonzero it follows that γ is positive, and so by Lemma 2.2 that −1 ∈ H. Thus multiplication by −1 simply permutes the elements of H, and so

βX − αZ ≡ P.h (mod P.N)

for some P ∈ B and h ∈ H. This completes the proof of Theorem 2.4.

3. Local solubility I

Given a hyperelliptic curve C defined by equation (1), where as before f is a square-free nonconstant polynomial in ℤ[x] with even degree, we would like to be able to test whether C has points over all localizations of ℚ (by which we mean ℝ and ℚ_{p} for finite primes p). Testing for the existence of real points is trivial; we merely have to check that the polynomial f is not totally negative.

Recall that the genus of C is g = n−1, where 2n = d is the degree of f. Suppose now that p does not divide 2Δ, where Δ is the discriminant of f. Then C has good reduction at p and its genus over the finite field 𝔽_{p} is still g. Thus by a Theorem of Weil (the so-called Riemann hypothesis for function fields, see [Cal], page 342), we know that we need only test that C (ℚ_{p}) is nonempty for the finitely many primes p which either divide 2Δ or satisfy p < 4g^{2}.

Thus far everything is standard. Now we need a method of testing for a given prime p whether or not C has points over ℚ_{p}. Here we use an algorithm due to Birch and Swinnerton-Dyer given in [Cre1]. The algorithm is stated on page 81 of [Cre1] for the case d = 4. However, it is pointed out (page 82 of [Cre1]) that the same algorithm works for any degree with essentially trivial changes. In fact the algorithm does much more than just testing for local solubility.

Lemma 3.1. For any x_{0} ∈ ℤ_{p}, and r ≥ 0, we can determine whether or not there exists x ∈ ℤ_{p} with v_{p}(x − x_{0}) ≥ r and f(x) = y^{2} for some y ∈ ℤ_{p}. If Δ is the discriminant of f and s = v_{p}(Δ), then this decision can be made in time O (p^{s+1} log(p)^{2}).

Proof. The first part of the lemma is an elementary consequence of Hensel’s Lemma. The details are given in the algorithm ℤ_{p}-soluble in [Cre1], page 82, which is originally due to Birch and Swinnerton-Dyer. The book does not give a complexity estimate but it is not hard to supply one. Assume p is odd, the case p = 2 being similar. The algorithm involves invoking a certain “subalgorithm” at most p^{s+1} times. In this “subalgorithm” one is required to decide if a certain p-adic integer is a p-adic square; i.e., that its p-adic valuation is even, and that what is left after the powers of p have been removed is a square modulo p. The estimate given in the lemma is now clear once we recall that a Legendre symbol (\frac{a}{p}) can be computed in O(log(p)^{2}) (see [Cohen], page 31).

3.1. Computing R(p). We start by rephrasing Lemma 3.1 as follows:

Lemma 3.2. Given coprime integers α, β, a prime p and an integer r ≥ 0, we can determine whether or not there exists (X, Z, Y) ∈ ℙC(ℤ_{p}) such that p^{r}|(βX − αZ). Again, if Δ is the discriminant of f and s = v_{p}(Δ), then this decision can be made in time O (p^{s+1} log(p)^{2}).

Proof. Suppose first that p does not divide α. Let g be the reverse polynomial to f; that is g(x) = x^{d}f(1/x). It is then easy to show that there exists (X, Z, Y) ∈ ℙC(ℤ_{p}) with p^{r}|(βX −αZ) if and only if there exists x in ℤ_{p} such that v_{p}(x− \frac{β}{α}) ≥ r and g(x) is a p-adic square. By Lemma 3.1 this decision can be made and in the time stated.

If p divided α, then p does not divide β and we proceed similarly.

Corollary 3.3. Suppose α, β, γ, δ are integers satisfying (4), where α, β are coprime, δ is nonzero, and γ is square-free and not equal to 0 or 1. Let p be a prime. Then R(p) is effectively computable. If s is as in the previous lemma, then this computation can be carried out in time O ((v_{p}(δ) + 1) p^{s+1} log(p)^{2}).

Proof. It follows from the definition of R and the proof of Lemma 2.1 that R(p) = ∞ if and only if γ is a p-adic square.

Suppose now that γ is not a p-adic square. Then we can simply continue testing, for each r ≥ 0, if there exists (X, Z, Y) ∈ ℙC(ℤ_{p}) such that p^{r}|(βX − αZ). The greatest value of r for which the answer is yes is R(p), and thus R(p) is effectively computable. It remains to prove the complexity estimate given. From equation (5), since γ is not a p-adic square, r ≤ 2v_{p}(δ) if p is odd and r ≤ 2v_{p}(δ) + 2 if p = 2. The estimate can now be trivially deduced from the previous lemma.

4. An example

Consider the elliptic curve

E : Y^{2} + Y = X^{3} − X^{2} − 929X − 10595.

This is the first curve in the tables of [Cre1] whose Mordell-Weil group is torsionfree but whose Tate-Shafarevich group is nontrivial. In [Me,Si,Sm] the authors used the method of further descents to show that all three nontrivial 2-coverings of E have no rational points and thus that the curve has rank 0 and that the 2-primary part of the Tate-Shafarevich group of the curve has order 4. This has also been proved in [Ca3] using a different method. The results are in agreement with the values predicted by the Birch and Swinnerton-Dyer conjectures. We show the same result using our method which we claim is the simplest since, unlike the methods used in [Me,Si,Sm] and [Ca3], it does not involve any number field arithmetic. The 2-coverings are

y^{2} = −4x^{4} + 4x^{3} + 92x^{2} − 104x − 727,
y^{2} = −108x^{4} − 4x^{3} − 76x^{2} − 112x − 31,
y^{2} = −229x^{4} − 135x^{3} − 238x^{2} − 84x − 8,

and were in fact generated by Cremona’s program mwrank; see [Cre1]. Let us consider the first 2-covering above and denote it by C. Write

f(x) = −4x^{4} + 4x^{3} + 92x^{2} − 104x − 727,
F (X, Z) = −4X^{4} + 4X^{3}Z + 92X^{2}Z^{2} − 104XZ^{3} − 727Z^{4}.

By considering the roots of f we see that f(x) is nonnegative if and only if x ∈ I, where I = [−3.31353, −3.31277] (the end-points of the interval have been rounded to five decimal places). Clearly C has no points at infinity and so it is sufficient to show that there are no triples (X, Z, Y) satisfying (2) and (3). We have programmed the algorithms in this paper (including the ones to follow) using the package pari/gp and ran them on a SGI workstation.

First we looked at all pairs of coprime α, β such that −100 ≤ α ≤ 100 and 0 ≤ β ≤ 100. We expressed F (α, β) in the form γδ^{2} with γ square-free, and noted all the quadruples with |γ| ≤ 10. We found the following values.

\begin{matrix}α & β & γ & δ \\ 1 & 0 & -1 & 2 \\ −53 & 16 & −1 & 2 \\ −27 & 8 & −1 & 58 \\ −33 & 8 & −1 & 838 \\ −10 & 3 & −7 & 1 \\ 5 & 2 & −7 & 34 \end{matrix}

It took 17 seconds to produce this table, and only about 0.4 seconds for our program based on the algorithm in Section 8 to show that there are no triples (X, Z, Y) satisfying (2) and (3); hence C has no rational points. For illustration we do some of the calculations explicitly. Suppose (X, Z, Y) satisfies (2) and (3). Let us take the second quadruple in the above table, that is α = −53, β = 16, γ = −1, δ = 2, and determine the possible congruences for 16X + 53Z using the method in Section 2; we follow the notation of that section. Here N = 4 and H = {1}. Note that the only prime dividing 2γδ = −4 is 2. Hence all the odd primes dividing 16X + 53Z must be congruent to 1 modulo 4. Further our program tells us that R(2) = 1; that is, the power of 2 dividing 16X + 53Z does not exceed 2. However it is easy to show that 4 does not divide 16X + 53Z. Otherwise 4 divides Z, and by considering the coefficients of F in Y^{2} = F (X, Z) it follows that 16 divides Y^{2} + 4X^{2}. This implies that 2 divides X contradicting the fact that X and Z must be coprime (since (X, Z, Y) satisfies (2)).

Thus |16X + 53Z| ≡ 1 (mod 4) or |16X + 53Z| ≡ 2 (mod 8). However since by assumption (X, Z, Y) satisfies (2), we know that Z ≥ 1 and X/Z ∈ I. It is easy to see that 16x + 53 is negative for all x ∈ I. Thus 16X + 53Z is negative. Hence either 16X + 53Z ≡ 3 (mod 4) or 16X + 53Z ≡ 6 (mod 8), or equivalently either Z ≡ 3 (mod 4) or Z ≡ 6 (mod 8). Similarly, using the first quadruple in the above table, either Z ≡ 1 (mod 4) or Z ≡ 2 (mod 8). This contradiction shows that our first 2-covering does not have any rational points.

Our program also showed that the second and third 2-coverings do not have any rational points in a few seconds.

5. Solving a general inhomogeneous system of linear equations over ℤ and ℤ_{p}

We will need to solve systems of simultaneous inhomogeneous linear equations over some principal ideal domain R which will be either ℤ or ℤ_{p} (where p is some prime). I am indebted to John Cremona for showing me how to do this using Smith Normal Forms. Suppose our system is given by

Ax = b, (8)

where b ∈ R^{m} and A is an m×n matrix with entries from R. By the standard theory of Smith Normal Forms (see, for example, [Cohn], page 322), one can compute invertible square matrices U, V of orders m and n, respectively, over R, such that UAV has a diagonal submatrix in the top left-hand corner and zeros elsewhere; the diagonal has entries d_{i} ≠ 0 for i = 1, …, r, and d_{i} divides d_{i+1} for i = 1, …, r − 1 (here r is the rank of A).

Lemma 5.1. With the notation as above, let S = UAV and b′ = Ub. Let b′_{1}, …, b′_{m} be the entries of b′, and let e_{j} be the element of R^{n} which has 1 in the jth position and 0 elsewhere. Then equation (8) has solutions if and only if d_{i} divides b′_{i} for i = 1, …, r. If this is the case, let y_{0} be the (column) vector in R^{n} with entries b′_{1}/d_{1}, …, b′_{r}/d_{r}, 0, …, 0, and let x_{0} = V y_{0}. Then the general solution to equation (8) is x = x_{0} + ∑_{j=1}^{n−r} k_{j}x_{j} for any k_{1}, …, k_{n−r} in R, where x_{j} = V e_{j+r} for j = 1, …, n − r.

Proof. Write y = V^{−1}x. Then Ax = b if and only if Sy = b′. The rest is now trivial.

6. Inhomogeneous congruences

Later in this paper, we need to parametrize the solutions to systems of simultaneous congruences of the form

β_{i}X − α_{i}Z ≡ c_{i} (mod d_{i}) (9) for i = 1, …, n. Here α_{i}, β_{i}, c_{i}, d_{i} are all integers. Each d_{i} ≥ 2 and each pair α_{i}, β_{i} are coprime.

Lemma 6.1. Let A be the set of ( \begin{matrix}X \\ Z \end{matrix}) ∈ ℤ^{2} which satisfies the system of congruences (9). Suppose A is nonempty. Then there exists vectors u, v, w ∈ ℤ^{2} such that

A = {u + λv + μw : λ, μ ∈ ℤ} , (10)

v and w being linearly independent. Moreover if we write

v = (\begin{matrix}v_{1} \\ v_{2} \end{matrix}) , w = (\begin{matrix}w_{1} \\ w_{2} \end{matrix}) (11)

and we let d = lcm(d_{1}, …, d_{n}), then d divides w_{2}v_{1} − w_{1}v_{2}.

Proof. The lemma is elementary except perhaps for the last part. Let u, v, w be as in the statement of the lemma. Let B_{i} (for i = 1, …, n) be the set of solutions in ℤ^{2} to the single congruence β_{i}X − α_{i}Z ≡ 0 (mod d_{i}). Let B be the intersection of B_{1}, …, B_{n}. Clearly B has ℤ-basis v, w, and is a submodule of each B_{i} which is in turn a submodule of ℤ^{2}, all having rank 2. Thus the index of each B_{i} in ℤ^{2} divides the index of B in ℤ^{2}. Now the latter index is w_{2}v_{1} − w_{1}v_{2}, while for each i, the former index is d_{i} (for this we need the assumption, made above, that each pair α_{i}, β_{i} is coprime). The lemma now follows.

To parametrize the solutions to the system (9), we write X_{1} = X, X_{2} = Z and then solve the simultaneous equations

β_{i}X_{1} − α_{i}X_{2} + d_{i}X_{i+2} = c_{i}, i = 1, …, n (12)

using the method explained above in Section 5. It is clear that the n × (n + 2) matrix with ith row β_{i}, −α_{i}, 0, …, 0, d_{i}, 0, …, 0, where the d_{i} is in the i + 2 place (i = 1, …, n), has rank n, and therefore its kernel has rank 2. Thus for (12), if it has a solution at all we are able to write down vectors u′, v′, w′ ∈ ℤ^{n+2}, with v′, w′ independent, such that X is a solution to (12) if and only if X = u′ + λv′ + μw′ for some λ, μ ∈ ℤ. We let u, v, w be the vectors in ℤ^{2} obtained from the first two entries of u′, v′, w′, respectively. These can be taken to be the u, v, w in the above lemma.

7. Local solubility II

It is apparent from above that we should be looking for triples (X, Z, Y) which satisfy (2) and (3) as well as a system of linear congruences such as (9). Clearly a necessary condition for the existence of such solutions is that (9) should itself have solutions. We assume that this is the case and that we have parametrized the solutions as in Lemma 6.1. Another necessary condition is that for each prime p there exists (X, Z, Y) ∈ ℙC(ℤ_{p}), such that

(\begin{matrix}X \\ Z \end{matrix}) = u + λv + μw

for some λ, μ in ℤ_{p} (where we abuse notation by letting ℤ_{∞} = ℝ). We would like to test whether this is the case for all primes p. We write v, w as in (11). If p = ∞ or if p is finite and does not divide w_{2}v_{1} − w_{1}v_{2}, then it is clear that every element of ℤ_{p}^{2} can be written in the form u + λv + μw for some λ, μ ∈ ℤ_{p}. However, we have made the assumption that C has points over all localizations of ℚ, thus it is sufficient to check solubility only for the finitely many primes dividing w_{2}v_{1} −w_{1}v_{2}.

Then we want to ask for each prime p dividing w_{2}v_{1} − w_{1}v_{2}, does there exist λ, μ ∈ ℤ_{p} such that if we let

X = u_{1} + λv_{1} + μw_{1},
Z = u_{2} + λv_{2} + μw_{2},

then min(v_{p}(X), v_{p}(Z)) = 0 and F (X, Z) is a p-adic square? We can answer yes precisely when we can positively answer one of the following two questions:

1. Is there a solution to the simultaneous equations

\begin{matrix}x & = & ϵu_{1} + λv_{1} + μw_{1} \\ 1 & = & ϵu_{2} + λv_{2} + μw_{2} \end{matrix} \} (13)

with x, λ, μ ∈ ℤ_{p} and ϵ ∈ ℤ_{p}\pℤ_{p} such that f(x) is a p-adic square?

2. Is there a solution to the simultaneous equations

\begin{matrix}1 & = & ϵu_{1} + λv_{1} + μw_{1} \\ pz & = & ϵu_{2} + λv_{2} + μw_{2} \end{matrix} \}

with z, λ, μ ∈ ℤ_{p} and ϵ ∈ ℤ_{p}\pℤ_{p} such that F (1, pz) is a p-adic square? Let us look at the first question. We can rewrite equation (13) in the form

(\begin{matrix}u_{1} & v_{1} & w_{1} & −1 \\ u_{2} & v_{2} & w_{2} & 0 \end{matrix}) (\begin{matrix}ϵ \\ λ \\ μ \\ x \end{matrix}) = (\begin{matrix}0 \\ 1 \end{matrix}) . (14)

We can solve this using the methods of Section 5. If this does not have a solution, then we cannot answer Question 1 positively and we move on to Question 2. Suppose (14) has a solution. Since w_{2}v_{1} − w_{1}v_{2} ≠ 0, the rank of the matrix in (14) is 2. Thus we can write down ϵ_{j}, λ_{j}, μ_{j}, x_{j} ∈ ℤ_{p} for j = 1, 2, 3, such that the solutions to (14) are precisely those vectors which can be written in the form

(\begin{matrix}ϵ \\ λ \\ μ \\ x \end{matrix}) = (\begin{matrix}ϵ_{1} \\ λ_{1} \\ μ_{1} \\ x_{1} \end{matrix}) + ϕ (\begin{matrix}ϵ_{2} \\ λ_{2} \\ μ_{2} \\ x_{2} \end{matrix}) + ψ (\begin{matrix}ϵ_{3} \\ λ_{3} \\ μ_{3} \\ x_{3} \end{matrix})

for some ϕ, ψ ∈ ℤ_{p}.

We now proceed as follows. We first write down a finite set S of “p-adic intervals”; that is, subsets of ℤ_{p} of the form x_{0} + p^{s}ℤ_{p} where x_{0} ∈ ℤ_{p} and s ≥ 0. We require that S satisfies the following: x is contained in one of the intervals in S if and only if there exists ϕ, ψ ∈ ℤ_{p} such that

• x = x_{1} + ϕx_{2} + ψx_{3},

• ϵ_{1} + ϕϵ_{2} + ψϵ_{3} is a p-adic unit. Once we have S, we know that to answer our question we must check if there exists x in some interval x_{0} +p^{s}ℤ_{p} in S such that f(x) is a p-adic square. For each interval x_{0} + p^{s}ℤ_{p} in S we can use Lemma 3.1 to decide if it contains an x for which f(x) is a p-adic square. Thus to answer Question 1 it is now sufficient to write down S.

Let s = min(v_{p}(x_{2}), v_{p}(x_{3})). Let x′_{2} = x_{2}/p^{s} and x′_{3} = x_{3}/p^{s}. If x = x_{1} + ϕx_{2} + ψx_{3}, then p^{s}|(x − x_{1}) and (x − x_{1})/p^{s} = ϕx′_{2} + ψx′_{3}. Now if p does not divide (ϵ_{3}x′_{2} − ϵ_{2}x′_{3}) then for any values we wish to give to (x − x_{1})/p^{s} and ϵ − ϵ_{1} we can solve the simultaneous system

(x − x_{1})/p^{s} = ϕx′_{2} + ψx′_{3},
ϵ − ϵ_{1} = ϕϵ_{2} + ψϵ_{3},

with ϕ, ψ ∈ ℤ_{p}. Hence in this case S = {x_{1} + p^{s}ℤ_{p}}. If however p|(ϵ_{3}x′_{2} − ϵ_{2}x′_{3}), then we can write down ω in ℤ, such that ϵ_{i} ≡ ωx′_{i} (mod p) for i = 2, 3. Thus if x = x_{1} + ϕx_{2} + ψx_{3} and ϵ = ϵ_{1} + ϕϵ_{2} + ψϵ_{3}, then ϵ − ϵ_{1} ≡ ω {(x − x_{1})/p^{s}} (mod p). Thus if p|ω and p|ϵ_{1}, then S is empty and we are finished. If p divides ω but not ϵ_{1}, then S = {x_{1} + p^{s}ℤ_{p}} and we are finished. If p does not divide ω, then we want (x − x_{1})/p^{s} ≢ −ϵ_{1}/ω (mod p). Let t′ be the element of {0, 1, …, p − 1} which is congruent to −ϵ_{1}/ω modulo p, and let T = {0, 1, …, p − 1} \ {t′}. Then S = {(x_{1} + p^{s}t) + p^{s+1}ℤ_{p} : t ∈ T }.

Question 2 can be decided in a similar manner and can be left for the reader to verify.

Definition. We say that the system of congruences (9) is compatible with the curve (3), if

1. The system has solutions (and thus a parametric solution which we can write down as in Section 6),

2. If it passes the above test. Otherwise, we say that the system of congruences is not compatible with the curve (3).

The following lemma is trivial.

Lemma 7.1. With notation as above, given a system of congruences (9), we know 1. We can test if it is compatible with the curve using the above method.

2. If the system of congruences is not compatible with the curve then there is no triple (X, Z, Y) satisfying (2) and (3) such that (X, Z) satisfies the simultaneous congruences.

8. The algorithm

Given an interval I such that f(x) is nonnegative for all x ∈ I, and a quadruple (α, β, γ, δ) satisfying α, β are coprime, δ is nonzero, γ is square-free and not equal to 0 or 1, and F (α, β) = γδ^{2}.

Notation. Let B, N, ζ be as in Theorem 2.4. Define

G(α, β, I) = {(ζP h, P N) | P ∈ B, h ∈ H} .

We now restate the main result of Section 2.

Theorem 8.1. Let I be an interval in ℝ such that f(x) is nonnegative for all x ∈ I. Suppose (α, β, γ, δ) is a quadruple of integers satisfying the conditions above, and let G(α, β, I) be as above. If (X, Z, Y) satisfies (2) and (3), then there exists a pair (u, M) in G(α, β, I) such that βX − αZ ≡ u (mod M).

Proof. This is simply a restatement of Theorem 2.4.

Suppose now that we are given an interval I such that f(x) is nonnegative for all x ∈ I, and a set of quadruples (α_{i}, β_{i}, γ_{i}, δ_{i}), i = 1, …, m, each satisfying the usual conditions: α_{i}, β_{i} are coprime, F (α_{i}, β_{i}) = γ_{i}δ_{i}^{2}, δ_{i} is nonzero, and γ_{i} is square-free and is neither 0 nor 1. We have by the above theorem, for each i, a finite set of pairs G_{i} = G(α_{i}, β_{i}, I), such that if (X, Z, Y) satisfies (2) and (3), then for each i, β_{i}X − α_{i}Z ≡ u (mod M) for some pair (u, M) ∈ G_{i}.

Now for each i we can fix a pair (u_{i}, M_{i}) ∈ G_{i} and ask if there exists some (X, Z, Y) satisfying (2) and (3) such that

β_{i}X − α_{i}Z ≡ u_{i} (mod M_{i}) (15)

for i = 1, …, m. We do not know of a way which will always answer this question. Rather we can attempt to show that the congruences are inconsistent: that is, we can apply the method of Section 7 to test if the system of congruences is compatible with the curve (3) (this term is explained at the end of Section 7). If it is not, then the answer is clearly no. If it is compatible with the curve, then while performing that test we will have parametrized the solutions to the simultaneous congruences (15); we will have written down a triple of vectors u, v, w ∈ ℤ^{2} such that any solution to the simultaneous congruences is of the form

(\begin{matrix}X \\ Z \end{matrix}) = u + λv + μw (16)

for some λ, μ ∈ ℤ. We can then try small values of λ, μ ∈ ℤ and ask if these give a pair X, Z such that F (X, Z) is a square in ℤ.

If we find that for each possible combination of the (u_{i}, M_{i}) ∈ G_{i} the system of congruences (15) is not compatible with the curve, then it is clear that there are no triples (X, Z, Y) satisfying (2) and (3). That this can happen is illustrated by our example in Section 4.

If we are to follow this strategy, then we will have to look at d_{1} × d_{2} × ⋯ × d_{m} systems of simultaneous congruences, where d_{i} is the size of G_{i}. This number can be enormous. In practice we aim to choose our quadruples (α_{i}, β_{i}, γ_{i}, δ_{i}) in such a way that many of the γ’s have common factors. Now for each i, the integer γ_{i} divides every M of every pair (u, M) in G_{i}. We rearrange the quadruples so that, as often as possible, several consecutive γ’s have a common factor. We then do what is called a “depth-first search”. Given a set of quadruples (α_{i}, β_{i}, γ_{i}, δ_{i}), i = 1, …, m, and the corresponding G_{i}, the algorithm below (which we write in pseudo-code) produces a set of triples u, v, w ∈ ℤ^{2}. The algorithm is designed so that such a triple is in the output if and only if for some choice of (u_{1}, M_{1}) ∈ G_{1}, …, (u_{m}, G_{m}) ∈ G_{m}, the system (15) is compatible with (3), and this triple gives a parametric solution to the system of congruences.

In the algorithm we think of G_{i} as an ordered list of pairs. Thus it makes sense to speak of the FIRST PAIR(G_{i}), and the LAST PAIR(G_{i}). If (u, M) is in G_{i} but is not the last pair, then we let the one after it be NEXT PAIR(G_{i}, (u, M)). In the algorithm L is a sequence of pairs [(u_{i}, M_{i}) : i = 1, …, r], where always r = LENGTH(L) is at most ≤ m, the number of our G_{i}. We always have that each (u_{i}, M_{i}) is an element of G_{i} for i = 1, …, r. Further APPEND(L, (u, M)) appends the pair (u, M) to end of L.

TEST(L) means test the system of congruences β_{i}X − α_{i}Z ≡ u_{i} (mod M_{i}) with i = 1, …, r for compatibility with the curve (3). If it is not compatible with the curve then TEST(L) = 0, and otherwise TEST(L) = [u, v, w], where u, v, w parametrize the solutions to the congruences in the usual way.

INPUT: Interval I, quadruples (α_{i}, β_{i}, γ_{i}, δ_{i}), and G_{i}, i = 1, . . . , m.
OUTPUT: A set of triples u, v, w ∈ ℤ^{2} (see Theorem 8.2 below).
1. BEGIN
2. L = [FIRST PAIR(G_{1})];
3. T = TEST(L); IF T = 0 GO TO STEP 5;
4. IF LENGTH(L) < m THEN L = APPEND(L, FIRST PAIR(G_{r+1})) AND GO
TO STEP 3 OTHERWISE OUTPUT T;

(Compute the largest i such that L[i] ≠ LAST PAIR(G_{i}) and let this be s)

5. s = m; f = 1;

6. WHILE s ≥ 0 AND f = 1 DO
7.  IF L[s] ≠ LAST PAIR(G_{s}) THEN f = 0 OTHERWISE s = s − 1 OD;
8. IF s = m THEN END;

9. L[s] = NEXT PAIR(G_{s}, L[s]); L = [L[i] : i = 1, …, s];

10. GO TO STEP 3;

Theorem 8.2. Given an interval I such that f(x) ≥ 0 for all x ∈ I, quadruples (α_{i}, β_{i}, γ_{i}, δ_{i}) (i = 1, …, m) satisfying the usual conditions, and the corresponding G_{i}, the above algorithm produces a finite set of triples of vectors [u, v, w] (with u, v, w ∈ ℤ^{2}) subject to the following condition: a triple is in the output if and only if there exists (u_{1}, M_{1}) ∈ G_{1}, …, (u_{m}, M_{m}) ∈ G_{m} such that the system of congruences (15) is compatible with the curve (3), and [u, v, w] give a parametric solution to the congruences.

In particular, if there exists (X, Z, Y) satisfying (2) and (3) then X, Z satisfies equation (16) for some integers λ, μ, and some triple in the output [u, v, w]. If the algorithm does not give any output, then there are no triples (X, Z, Y) satisfying (2) and (3).

Proof. Suppose for now that the first statement of the theorem holds. If (X, Z, Y) satisfies (2) and (3), then by Theorem 8.1, there exists for each i a pair (u_{i}, M_{i}) ∈ G_{i} such that the simultaneous congruences (15) hold. Then these congruences have a global solution on the curve and thus are compatible with it. Now the second part of the theorem follows from the first.

Let us now come to the first statement. Consider a directed graph where the vertices are the elements of G_{i} for i = 1, …, m, and where vertices (u, M), (u′, M′) are connected by an arrow (u, M) → (u′′, M′′) if and only if there is some 1 ≤ i ≤ m − 1 such that (u, M) ∈ G_{i} and (u′, M′) ∈ G_{i+1}. We write [(u_{1}, M_{1}), …, (u_{r}, M_{r})] for the path which starts with (u_{1}, M_{1}) ∈ G_{1} and finishes in (u_{r}, M_{r}) ∈ G_{r}. What we want in effect is for our algorithm to determine all paths [(u_{1}, M_{1}), …, (u_{m}, M_{m})] such that the corresponding system (15) is compatible with the curve (3). Now we observe that if, for some r < m, the system of congruences corresponding to the path [(u_{1}, M_{1}), …, (u_{r}, M_{r})] is not compatible with the curve, then neither is any extension of it [(u_{1}, M_{1}), …, (u_{r}, M_{r}), (u_{r+1}, M_{r+1}), …, (u_{m}, M_{m})] for any elements (u_{j}, M_{j}) ∈ G_{j} with j = r + 1, …, m.

What is now needed is merely to carry out a “depth-first search” of a directed graph (see for example [AHU]) and it can safely be left for the reader to see that our algorithm does exactly that (bearing in mind that the algorithm L records the current path).

The above algorithm minimizes the storage requirement. Essentially the only storage is the input and final output. Also the fact that we choose and rearrange our input so that successive γ’s often have common factors probably greatly reduces the running time. To see this, suppose say that γ_{1} and γ_{2} have the common factor l > 1. Suppose in the above algorithm that L = [(u_{1}, M_{1}), (u_{2}, M_{2})] is given. Here we must have that (u_{i}, M_{i}) ∈ G_{i} for i = 1, 2. Then M_{1}, M_{2} have l as a common factor. It is then fairly likely that for each prime p dividing l, the simultaneous pair of congruences (15) with i = 1, 2 will have exactly one solution, say x, z modulo that p. We expect that roughly 50 percent of the time F (x, z) is not a square modulo p, and that even if it is, our solution modulo p does not necessarily lift to give us a p-adic point on ℙC(ℤ_{p}). Thus when running our algorithm, we have a good chance of not having to go any deeper at this stage and we simply replace (u_{2}, M_{2}) with the next pair in G_{2} (or if (u_{2}, M_{2}) is the last pair in G_{2}, then we replace (u_{1}, M_{1}) by the next pair in G_{1} and we let L = [(u_{1}, M_{1})]).

9. A second example

If our algorithm fails to prove the nonexistence of rational points on our hyperelliptic curve, or if indeed the curve does have rational points, then it may still be useful to search for all rational points whose height is less than a certain given bound. It is the purpose of this example to illustrate how the output from the algorithm of the previous section may be used to speed up this search.

Consider the curve

y^{2} = x^{3} − 1063395x − 422075394

of conductor 3672. This curve comes from Cremona’s extended tables of elliptic curves available via the World Wide Web from: http://www.nott.ac.uk/personal/jec/ftp/data. The conjecture of Birch and Swinnerton-Dyer predicts that it has rank 1, and we content ourselves with finding one point of infinite order on the curve. Cremona’s mwrank gives the following 2-covering:

Y^{2} = −216X^{4} + 252X^{3}Z − 315X^{2}Z^{2} − 1476XZ^{3} − 762Z^{4}.

We define f(x) and F (X, Z) as usual. Note that f(x) is nonnegative if and only if x ∈ I, where I = [−0.81295674, −0.81294900] (we have rounded the end-points of the interval to eight decimal places). We did a search for quadruples α, β, γ, δ as in the example in Section 4 but this time with range −200 ≤ α ≤ 200 and 0 ≤ β ≤ 200. We found the following values.

\begin{matrix}α & β & γ & δ \\ −113 & 139 & 3 & 1 \\ −13 & 16 & −6 & 2 \\ −5 & 6 & −3 & 18 \\ 1 & 0 & −6 & 6 \end{matrix}

As stated previously, we implemented all the algorithms in this paper in pari/GP. Our main algorithm of Section 8 took 4.5 seconds to run and gave 4 triples [u, v, w], which we give here as triples of row vectors:

\begin{matrix}[(421, 6), (36, 0), (24, 144)] , & [(23, 66), (36, 0), (24, 144)] , \\ [(1273, 6), (108, 0), (96, 144)] , & [(71, 66), (108, 0), (96, 144)] . \end{matrix}

In the notation of Lemma 6.1, the quantities |w_{2}v_{1} − w_{1}v_{2}| are 432, 432, 1296, 1296, respectively. To get an idea of just how efficient our sieve is, we note that given (say) a very large square in ℝ^{2}, the proportion of (X, Z) ∈ ℤ^{2} in our square which can be expressed in the form u + λv + μw for some integral λ, μ, where [u, v, w] is one of our four triples is roughly 2/432 + 2/1296 = 1/162. In fact using these four triples, it took our program roughly 4 minutes to search the region

−10^{7} ≤ X ≤ 10^{7}, 1 ≤ Z ≤ 10^{7},

and to find one point (X, Z, Y) = (−2021077, 2486082, 168298146) on our 2-cover-ing; here

(X, Z) = u − 67651v + 17264w,

where [u, v, w] is the second triple given above. Using the standard syzygy in Section 3.6 of [Cre1] we get the point

[\frac{5580280211292650758}{87420573910609}, \frac{13180351117189258356213783626}{817373361745081357273}]

on our original elliptic curve. By contrast, a program written by Cremona based on more usual sieving ideas (as described in Section 3.6 of of [Cre1]) and running on the same machine, took roughly 95 minutes to find the point on the 2-covering.

We point out that there are other methods/programs which can be used to compute the generator above. For example, there is an (unpublished) experimental method due to Cremona and Silverman ([Cre2]) for curves of rank 1 using Heegner points and canonical heights. We would like to thank J. Cremona for running his implementation of this method on the above example. The program, running on a 90MHZ Pentium, took just 79 seconds to find the point on the elliptic curve.

References

[AHU] A. V. Aho, J. E. Hopcroft, J. D. Ullman, Data Structures and Algorithms, Addison-Wesley, 1982. MR 84f:68001

[Cal] J. W. S. Cassels, Local Fields, LMS Student Texts, Cambridge University Press, 1986. MR 87i:11172

[Ca2] J. W. S. Cassels, Survey Article: Diophantine Equations with Special Reference to Elliptic Curves, J.L.M.S. 41 (1966), 193-291. MR 33:7299

[Ca3] J. W. S. Cassels, Second Descents for Elliptic Curves, J. reine angew. Math. 494 (1998), 101–127. MR 99d:11058

[Cohen] H. Cohen, A Course in Computational Algebraic Number Theory, GTM 138, Springer-Verlag, third corrected printing, 1996. MR 94i:11105

[Cohn] P. M. Cohn, Algebra, Volume I, second edition, John Wiley and Sons, 1982. MR 83e:00002

[Cre1] J. E. Cremona, Algorithms for Modular Elliptic Curves, second edition, Cambridge University Press, 1997. MR 99e:11068

[Cre2] J. E. Cremona, Personal Communication, 1996. [Me,Si,Sm] J.R. Merriman, S. Siksek and N.P. Smart, Explicit 4-Descents on an Elliptic Curve,

Acta Arith. LXXVII (1996), 385-404. MR 97j:11027

[Sil] J. H. Silverman, The Arithmetic of Elliptic Curves, GTM 106, Springer-Verlag, 1986. MR 87g:11070

Institute of Mathematics and Statistics, Cornwallis Building, University of Kent, Canterbury, UK

Current address: Department of Mathematics, College of Science, PO Box 36, Sultan Qaboos University, Oman

   E-mail address: siksek@squ.edu.om