Modulo Errors

Last time, I gave some procedures to generate an elliptic divisibility sequence from a point of an elliptic curve, the motivation being that the growth rate of the sequence corresponds to the height of the point- and thus we can compute heights by computing terms of the sequence.

But what about going the other way? Given that we seek points of low height, can we search more intelligently by crafting sequences with a small growth rate, rather than simply mapping from (typically uninteresting) random points to their sequence? The easiest way to achieve this would be to start from the sequence, rather than from the point- but that requires a means to recover the point from the sequence.

Fortunately, Ward’s Memoir¹ provides just such a technique, although presented in terms of elliptic functions (the complex analysis way to view elliptic curves). Recall that to define a sequence, we need only specify the second, third and fourth terms h₂, h₃ and h₄. Then the corresponding point is (X,Y) on curve E: Y²=4X³ -g₂X -g₃, given by the following unpleasant formulae:

However, these needn’t be integral, and it’s preferable to rescale to eliminate that X³ coefficient. Fortunately both of these problems can be solved by clearing denominators, leading to a more pleasant representation of the point and curve. My basic algebra being as rusty as it is, this procedure me a surprisingly long time to figure out in the general case, but I have now added suitable features to my eds SAGE class. For such an object X, a call to X.ward_point() will return a point of an elliptic curve: you can extract the curve from a point P in SAGE by P.curve(). There’s a slight issue in that an EDS may define a singular curve: I’ve caught this exception, and in such a case you’ll get back the integer zero instead. I needed this to prevent large searches over EDS from crashing when such a sequence arose from the parameters, but it’s a bit of an ugly solution.

Given a method to turn sequences into points, the obvious question is whether it acts as the inverse to the creation of sequences from points. The answer turns out to be, almost! Extra scaling factors creep in to the sequence terms each time you loop through a cycle of EDS→point→EDS. The larger the terms, the greater the time/space requirements for manipulation of the sequence; this also has a knock-on effect on the approximate height computed. However, this can be fixed for curves over number fields: considering field elements as polynomials, rescaling each of h₂,h₃,h₄ to have content 1 recovers the original EDS. I offer no mathematical justification for this other than that it works! Thus heights now also includes EDSfromPoint_nf to generate EDS by just such a scaling.

Armed with these techniques, it’s now easy to generate curves of moderately small height that would otherwise be presumably difficult to stumble upon: for instance, with u=1+√2, the curve over the number field Q(u) given by y²=x³ + (-432u-864)*x + (-1728u+6480) has a the point (24-12u,108) of height around 0.0107. This unlikely looking curve arises from the much simpler EDS with defining terms -1,u-1,2u-2, found after a search over sequences from K with small terms that took about an hour. Considering how easily it was found, this compares favourably to the lowest known height over Q of about 0.0045. However, in the context of the Elliptic Lehmer problem heights should be scaled by the degree of the field extension, so to set a record a value of around 0.002 is needed for quadratic extensions such as K. So the search continues…

References

1: Morgan Ward- Memoir on Elliptic Divisibility Sequences (MathSciNet entry)

Updated now that I’ve obtained a copy. If you’re in the UK, have a windows computer and are willing to use Internet Explorer, then you can currently download the program through the BBC’s iplayer service. It’s wrapped up in DRM, but the 7 day viewing licence granted means you can liberate it with FairUse4WM.

During my summer research at Bath I was briefly involved with preparations for the International Mathematical Olympiad, helping to mark the scripts that would select the shortlist of candidates for further training. Perhaps inspired by the drama that had surrounded the previous year (including a hurricane and a case of mistaken identity -as a murderer- for our team leader) , a film crew had been following the process. Tonight (Sunday 14th) their documentary, Beautiful Young Minds, aired.

The program mostly focused on personalities, rather than the mathematics, with particular interest in how those on the autistic spectrum can find refuge in the subject. This is certainly true, as characteristics that would be of hindrance in many pursuits can be an advantage in mathematical study: particularly of the kind needed for intense IMO training. Plus plenty of mathematicians not on the spectrum - myself included, although through different causes - would nonetheless identify with many of the traits associated with Aspergers.

But it’s a little disappointing that this was the main image portrayed of mathematicians- other members of the team were sociable and eloquent, but this was only highlighted to draw contrasts with the main subjects. At least they hinted that being a mathematician still isn’t easy for these individuals, whilst illustrating that the autistic spectrum contains a range of manifestations: Jos doesn’t find an emotional connection with the others, it just matters less; whilst Daniel is still too disturbed by crowds to collect his medals and gain the public recognition he deserves. I don’t think most people realise how social mathematics is as a discipline; the IMO experience is also rather different to undergraduate mathematics, with research in the subject requiring yet another skill set and outlook- the program didn’t help this, and I’m not sure it’ll attract many more people to the subject… Still, a fascinating bit of TV, although it was slightly strange to see Geoff on screen!

Today I gave the first of this year’s postgraduate colloquia series, The Mathematics of Being Nice- cooperation in the Prisoner’s Dilemma. You can grab the slideshow as pdf here; since the potential audience was quite broad (and I’m no expert) I think it’s fairly light technically, and thus hopefully more accessible than many of my posts here. It’s essentially the talk version of my article for iSquared, so you should invest in a copy of that if you want something that’s more fleshed out!

View as:   

In the classical logic typically applied to mathematics, a single contradiction is fatal, as it allows anything and everything - including its opposite- to be derived. However, real-world situations such as large software products often feature irresolvable conflicts, from which we would not wish to draw such broad conclusions. Reasoning about such systems motivates the study of paraconsistent logic. The linked article examines the various ways in which the explosion of inconsistency can arise, and thus which rules of inference need to be discarded for such logics.

My interest in this topic arises from a talk I recently attended by Carl Hewitt, and wading through two dozen short essays on Russell’s Paradox by my new students!