Sieving for (hyper)elliptic curves with lots of integer points

I haven't seen this written down anywhere, though I doubt it's my own invention. It's a fairly simple technique for looking in a one-parameter family of curves for the ones which have lots of integer points; I'll explain it by giving an example.

Say you want to find good values for B in the family y2=x3+29x+B. Start by constructing an array of as many counters as you have space for; the counters very rarely go above 50, so 8 bits should suffice. Label the counters with the integers -K through K.

Aside: if you wish to search a longer range than can fit in RAM (for example in my search for Mordell curves of high rank), you can simply repeat the sieving several times with offset sieves.

Now, run over a range of x values -- say -10000 .. 10000. For each x value, compute z = x3+29x, and consider the range [z-K, z+K]. It's trivial to list all the squares in this range (though you have to be slightly careful about the boundaries); if z+T is a square, add one to the counter labelled T.

After doing this (which ought to be very quick; on a 500MHz Alpha 21264 I was able to run through thirty thousand x values in about six seconds), have a look for counters with large values.

Aside: to save having to scan through the whole array after the sieving, it's worth noticing whenever a counter is incremented above a threshold, and saving the relevant T-value in a separate array, then going back at the end to display the actual counter value for only those T.

If counter T has value 47, there were 47 x values with x3+29x+T a square - that is, the curve x3+29x+T has at least 93 integral points (since (x,y) and (x,-y) are both points on the curve, and distinct unless x=0 which can occur only once).

Of course, you can search over large numbers of families; in constructing my entries in the table of curves with high rank and low conductor, I looked at y2 + a3y = x3 + a2x2 + a4x + a6 for a4 = -20000 .. 20000, a3 = 0 .. 1 and a2 = -1 .. 1. (for a3=1, see the paragraph below).

The technique doesn't use any arithmetic on the curve, so will work just as well for families of higher-degree curves; it's reasonably trivial to list all the solutions to any quadratic contained in an interval (though you have to be quite careful in regions where f(y)=A has multiple solutions), so you could search with similar speed for curves y2+19y = x5-x3+x+B; the difficult task would be finding a reason to perform the search :)

A strategy note for the low-conductor search

The output of the elliptic-curve sieve program is a long list of entries of the form [curve]: #pts. For the low-conductor search, I took this list and used Perl and Pari to compute the conductor and the rank-parity for each curve -- something that Pari can do in a few milliseconds per curve -- then ordered the curves by conductor. This causes the curves of each rank to clump together, so we find long stretches with the same rank-parity; I start at the best conductor value I'd observed, which usually appears as a break in the middle of such a long stretch, and then search backwards (using emacs incremental-search) for the 'wrong' rank parity, checking the ranks for the observed curves using mwrank. This is between three and four orders of magnitude quicker than using mwrank on all the curves and sorting by rank.

Back to Tom's maths page