A Mestre-style search for high-rank curves of small conductor

Method 1: The basic idea (inspired by [AB99])

Let P(x) be a polynomial of degree 8. We can compute, essentially by linear algebra, a polynomial Q(x) of degree 4 such that Q(x)² - P(x) = R(x) for R of degree at most three. Assume R has degree precisely three, changing P if it doesn't.

Now, if t is a root of P(x), we have Q(t)² = R(t), so the equation y²=R(t) has a point [t,Q(t)]. By writing P(x) = (x-u₁)(x-u₂)...(x-u₈), we can easily arrange for it to have eight rational roots, which means that y²=R(t) is an elliptic curve with at least eight rational points. And there is no a priori reason for these points not to be independent, so (reducing everything to a minimal model, and then computing height pairings or using some cleverer way of picking an independent subset out of a set of points) we can compute the rank of the subgroup of the Mordell group of the curve generated by those points, and we expect quite large values.

In fact, we find that we can frequently get rank 7 (for example for u = [0, 2, 4, 7, 8, 9, 10, 13]) -- which can be explained by noticing that you get the same minimal model if you perform an affine transform on the points, so we can insist that u₁=0, that the u_i are integers, and that they are in increasing order, without loss of generality.

Method 2: First refinement - look for extra points on the cubic

The algebra above guarantees that there are at least eight rational points on y²=R(t), but there's no reason for there not to be more. So we can conduct a quick search for rational points before proceeding to the minimal model and reducing; experimentally, this can increase the rank by up to 4. For example, u = [0, 1, 2, 4, 5, 13, 16, 18] has seven independent rational points from the construction, but a search on the cubic reveals 11.

Large rank boosts are rare; the following graph shows the statistics for the 8,008 vectors with u8 = 17:

Method 3: Why not use a quartic?

A curve of the form y² = quartic(x) possessing a rational point is an elliptic curve. So we could take a polynomial of degree 10, follow the polynomial-square-root technique of method 1 to get a quartic remainder with at least 10 rational points, search for extra points, and then convert to a minimal model and proceed. This requires code for converting y² = quartic to some sort of cubic form, which I've written following [IC92]. We get 'natural' (IE without looking for extra points on the quartic) rank-9 curves, for example from u = [0, 1, 2, 3, 4, 5, 6, 7, 8, 11, 12, 13], and putting in the search for extra points can pull the rank up to 12. The conversion from quartic to minimal cubic involves very large intermediate results, so this algorithm is both much slower than Method 2 and produces much larger conductors at a given rank.

Method 4: take advantage of coincidences (inspired by the second construction in [JFM91])

If we started with a polynomial of degree 12, method 1 would give us a y^2=quintic curve with many rational points. But it's entirely possible that, by a strange coincidence, the x^5 coefficient of the quintic is zero, giving us a quartic and letting us proceed in the same way as method 3. And checking whether the x^5 coefficient is zero is very quick.

Mestre in [JFM91] uses a similar idea but in an algebraic context, and constructs a whole family of y^2=quartic curves with 'general' rank 11; I attempt to describe the construction here. Searching for points on the quartics can increase the rank up to 13.

The software

I've implemented all of this in a Pari program mestre.gp. The main functions are

• mestreA([u1,u2,u3,u4,u5,u6,u7,u8]) performs the algorithm of Method 1, and returns a four-component vector : [m, conductor, minimal model, list of m independent points on the curve].
• mestreB([u1,u2,u3,u4,u5,u6,u7,u8]) performs the algorithm of Method 2 (IE the same as mestreA but with the intermediate search for extra points on the cubic), with output in the same format.
• mestreC([u1 .. u10]) implements method 3.

Some auxiliary functions which might be useful in other contexts are

• ptslst(P) finds some rational points on y²=P(x)
• ellliset(E,[points]) finds a linearly-independent subset of the given set of points on E
• ell_from_quart(Q,[points]) takes a quartic polynomial and a set of points, computes a model for the elliptic curve represented by Q, and transforms the points to that model.

Implementation notes

• For methods 1 and 2, there's no guarantee that R(x) will actually be a cubic, and if it turns out to be quadratic then the Pari elliptic-curve routines will complain that the curve is singular. So, before you call ellinit(), be sure that R(x) is a genuine cubic.
• For method 3, an annoying failure mode occurs if R(x) is the square of a quadratic -- so do an irreducibility test before proceeding.
• It's easy (using the Pari forvec command) to apply mestreB to thousands of u vectors and look for low conductors; some reasonably-low conductors (searching for u8<=23, which takes about a week of PC time) are given below. Note that the rank-5 and best rank-6 examples match the bound from the exhaustive search.
  

  Rank	log N	Expression
  5	16.762	mestreB([0, 1, 7, 10, 12, 14, 19, 21])
  6	22.383 22.801	mestreB([0, 2, 5, 12, 15, 17, 18, 23]) mestreB([0, 1, 3, 10, 13, 14, 16, 19])
  7	28.235	mestreB([0, 1, 2, 6, 7, 12, 13, 19])
  8	34.323	mestreB([0, 2, 5, 10, 11, 13, 16, 19])
  9	40.721 42.264 44.989	mestreB([0, 1, 2, 3, 5, 14, 20, 23]) mestreB([0, 1, 12, 13, 16, 17, 19, 22]) mestreB([0, 1, 4, 6, 12, 16, 19, 20])
  10	49.033 53.456	mestreB([0, 1, 10, 13, 15, 18, 19, 22]) mestreB([0, 2, 6, 8, 11, 12, 18, 20])
  11	62.392 63.430	mestreB([0, 3, 4, 11, 12, 17, 20, 23]) mestreB([0, 3, 6, 10, 12, 14, 16, 20])

References