Modulo Errors

Tomorrow I give my first year presentation, which determines whether I’m allowed to continue my studies. At 20-30 minutes, it’s a rather condensed version of my recent geometry club talk on the point counting problem, although this time I’m skipping more quickly through the fundamentals so that I can discuss some of the algorithms in depth, and taking a (hopefully) clearer route.

Both the report itself and the OHP slides version are available (pdf). Content covered: hyperelliptic curves, points, divisors, mumford polynomials and the Picard group/Jacobian; the discrete logarithm problem; explicit group law computation; characteristic polynomial of Frobenius and Weil theorems/interval; group-theoretic approaches; Schoof’s algorithm, SEA in genus 1, genus 2 hybrid algorithms.

The plaque marking the discovery of the quarternions, Dublin.

I’ve spent the last three days in Dublin, and whilst there I couldn’t resist taking a rare opportunity for mathematical tourism. Hamilton figured out the structure of the quarternions in “a flash of genius” during a morning walk along Dublin’s royal canal, carving them into the nearby Brougham bridge. Whilst the carving does not survive, there is a plaque at the spot to mark this discovery, and it was that I set off to see.

Getting there doesn’t seem too difficult, though: I got the 120 bus from Parnell Street (conveniently close to my hotel on Parnell Square) to Broombridge road. This is the opposite of advice found elsewhere online, but the suggested 20 route doesn’t seem to exist any more. If you have a map, it’s easy enough to follow the bus route, but as I didn’t I just asked the driver to give me a shout when we got there. Brougham is pronounced broom, so all you need to do is to find where Broombridge road crosses the canal and (it turns out) railway tracks: presumably taking the western suburban line would be an even easier way to get there, as the platform is next to the bridge. Of course, I went the wrong way along Broombridge road, which is easily detected by reaching the end without finding a bridge!

It’s been described as “the least visited tourist attraction in Dublin”, partly because the area isn’t particularly appealing today but presumably because there aren’t that many mathematical tourists!

It does seem a shame that the site - and Hamilton - are so overlooked compared to the attention that, say, local authors or artists get. But it’s better than nothing, as mathematical tourist attractions are few and far between, especially outside of universities. The bridges of Königsberg are often suggested; I’d also be fascinated to tour Japan in search of sangaku. If you have other ideas, why not mention them in the comments?

Ask SAGE for the cardinality (that is, number of points) of an elliptic curve over a finite field and, unless you happen to have a prime field, it’ll warn you that it’s resorting to the “very, very stupid” algorithm of testing every point. Can we do better?

Background: The Zeta function

Recall that the zeta function of a curve encodes information about the number of points over an infinite family of fields. For a curve C over the field F_q This is defined as

Thus, we can recover the cardinality over F_q^r by differentiating r times with respect to T, evaluating for T=0 and dividing through by (r-1)!. This is all well and good, provided that computing the zeta function is less work than simply testing points in the field directly. For this, we need a couple of results:

Weil Conjectures for curve C over F_q
We have

such that

with the α_i algebraic integers such that |α_i|=q^1/2.

For such α_i we then have

For F_q to be a field, q=p^r for some prime p. Thus we need only compute the zeta function over F_p to be able to retrieve #C(F_q) or indeed any higher #C(F_q^r). The question is, therefore, whether computing the zeta function for F_p is any easier than the naive point search. With Weil’s result, we can see that knowledge of #C(F_p),…,#C(F_p^2g) would, via some Taylor series trickery, be enough to determine P(T) and hence Z(T). If q is a high power of p, or we are interested in high powers of q, then this is already progress. But if q was itself a (potentially very large) prime, this approach would be useless for finding #C(F_q) since it would require knowledge of #C(F_q) (!) and at least #C(F_q²) too! Fortunately SAGE does not complain about searching over prime fields- there are a couple of algorithms - so we can restrict our attention to the original problem, that of composite q.

Elliptic Curves

Let us consider then the problem of finding #E(F_q^r) where q=p^s for a prime p with rs≥2 and E an Elliptic curve with coefficients from F_p. Then by the above we need only find #E(F_p) and #E(F_p²), which by brute force is rarely more work than finding #E(F_q^r)=#E(F_p^rs). But, since the genus is 1 the various results allow us to cut down our workload still further:

Weil Conjectures for Elliptic curve E over F_p

We have

such that

with the α_i algebraic integers such that |α_i|=p^1/2.

For such α_i we then have

It follows that α₁, α₂ are conjugates, so over F_p we have

and

So,

meaning that the zeta function can be constructed from just #E(F_p) as it is simply:

This then allows us to recover #E(F_q^r)=#E(F_p^rs) as desired, by repeated differentiation to recover the rs‘th coefficient.

Comparison

For an elliptic curve over a finite field, using SAGE to calculate the cardinality over a field of p^r elements by the “very, very stupid” algorithm rapidly gets impractical. For instance, for a given elliptic curve y²=x³+Ax+b with A,B from F₅ determining the cardinality takes about 0.04s over F₅; about a second over F₂₅, around 3.7s for F₁₂₅ and a tedious 19s over F₆₂₅. Implementing the approach above, asking for the cardinality of three such curves over F₆₂₅ is rapid enough in Maple to not register on its timer. This is despite my program lazily using brute force for the #E(F₅) calculations! (The same machine, with a 2.6ghz celeron processor, was used for each run; with Maple on Windows XP and SAGE in Xubuntu Linux; SAGE timings were for CPU rather than wall time.)

Smarter Still

In fact, if we only wish to determine a single #E(F_q^r) we can sidestep the construction of the zeta function by working with the α_p, since

Thus if α_p=a+bi then

and

So

will suffice, and again this requires only knowledge of #E(F_p).

Maple Source

The file ellCount contains Maple procedures for finding the cardinality of elliptic curves over finite fields (with coefficients from the prime subfield). Simply put, CountPoints(F,q) will find the number of points over the field of q elements for an Elliptic curve F=0. For instance, CountPoints(y^2-x^3-x-2,625) gives the cardinality of E: y²=x³+x+2 over F_5⁴ (should be 640). The route taken is to find points over F₅, determine α then directly calculate from the formula in the previous section. You can retrieve the zeta function with ellZeta(F,q), or ellZetap(F,p), if you know that q is prime (which saves Maple trying to determine the prime factor). Thus the number of points over F_q^r can be retrieved with getZetaCoeffr(Z,r) which performs the appropriate differentiation and scaling; this is useful to avoid having to calculate the number of solutions over the prime field, or indeed determine the prime, every time. ZetaCountPoints(F,q) behaves as CountPoints except it follows this alternative route.

The procedure I described in my previous post for computing types of zeta functions is informative the first time you try it and tedious thereafter; thus I’ve cobbled together some maple code to do the job for some simple cases.

A call to totalTrace(d,t) will scurry off and determine all degree d polynomials of trace t, provided neither your chosen trace or degree are too high (data tables only exist up to a certain point, and I wasn’t patient enough to implement much of what is known, either!). If you’re confident that the trace is sufficiently small to guarantee a building block from the set of exceptional polynomials S, you can use the fractionally faster totalTraceS(d,t) instead- it’ll tell you if you’re wrong!

Calling smallDefectPol(g) will, for a genus g, display the possible polynomials Q (whose roots are the β_i) corresponding to small defect curves (where small means at most 0.780022g, using the exceptional set S). You can get the types (of the form used e.g. by Serre) instead by calling smallDefectTypes(g).

Some defects that don’t meet the bound for small can nonetheless be computed with totalTrace(d,t), use its output as the argument for zetaTypes(X) to recover their corresponding types. This will become more useful if I add additional cases from the data tables.

One of the central results in the study of Elliptic curves is the Mordell-Weil theorem, which asserts that the group E(K) is finitely generated. Thus it consists of a finite part- the torsion subgroup - and a free abelian part, the rank of which is notoriously difficult to compute. However, the torsion subgroup is relatively accessible, and this is something I’ve been playing with for a while. It covers a range of techniques and ideas and attempting a concrete implementation in Maple has helped considerably in my understanding of those, even if it is effectively reinventing the wheel given the existence of John Cremona’s Algorithms for elliptic curves. The procedures themselves and worked examples are after the cut; first, some theory.

Mazur’s Theorem

Let E/Q be an elliptic curve. Then the torsion subgroup E_tors(Q) is one of the following fifteen groups:

Z/nZ for 1≤n≤10 or n=12;

Z/2Z X Z/2nZ 1≤n≤4.

Further, each of these groups does occur as an E_tors(Q).

This result is particularly handy as it allows for an experimental approach to be taken, gathering enough computational evidence to determine which form the torsion subgroup takes; knowledge of the order of points being especially useful. For instance, the presence of an order 7 element instantly shows that E_tors(Q) is Z/7Z. Better still, there are results which aid in finding such points:

Nagell-Lutz Theorem

Let E/Q be an elliptic curve of the form

(that is, with the usual labelling of coefficients, a_1=a_3=0) with a,b,c integers. If P an element of E(Q) has finite order then x(P), y(P) are also integers.

Further, For such a point either y(P)=0 or y(P) divides

Hence for such curves it is sufficient to look for integer points; and only finitely many such points are suitable candidates for being torsion points.

Good and Bad Reduction

What of Elliptic curves not in the above form? It is possible to bound the number of torsion elements (and generate candidates) by working over finite fields (which I’ve coincidentally considered before). Save for finitely many primes of bad reduction - those which divide the discriminant of the elliptic curve - it transpires that the torsion subgroup maps injectively to E(F_p). For small primes, this is readily found without anything more sophisticated than brute force. Testing a number of primes can give an upper bound whilst naive searches for integer points can provide a lower bound: appealing again to Mazur’s theorem then usually settles the question.

Read the rest of this entry »

I’ve added a couple of extra toys to my Maple procedures for elliptic curves. The major change is that it now supports calculation over some finite fields; that is, the integers modulo some prime. To activate this, set workModM to true and specify a modulus M. Then the usual commands ella, ellm, ncopies and mnadd will compute answers mod M instead.

This also makes it much more likely that you’ll be interested in the order of a point, so a procedure modgetorder is included to calculate this by brute force- that is, repeated addition until the zero element is reached.

This makes questions of the type I faced in MA40188: Algebraic Curves much easier. For instance, consider the curve

Over the field with 37 elements, and with a suitable dehomogenisation, the point P: (x,y)=(0,23) is easily verified as an element of E. Then we may easily determine the point Q=-2P, the third intersection of E with the tangent to E at P:

>read “gla.mpl”;

> a_1:=0;a_2:=0;a_4:=-9;a_3:=0;a_6:=11;

>workModM:=true;

>

>M:=37;

>Q:=ncopies(-2,0,23);

1,22

So Q=(1,22). Further, Q is an inflexion point: that is, the tangent to E at Q meets E three times at Q. In terms of the group law, this means -2Q=Q, or equivalently 3Q=0. We can verify this in a couple of ways:

> ncopies(3,Q);

zero

> modgetorder(Q);

3

Since Q=-2P and 3Q=0, it should follow that 6P=0. Which, fortunately, it does:

> modgetorder(0,23);

6

Here are some applications of the procedures developed in the previous post.

Example 1

We consider example 2.4/problem 3.4 from Silverman;

By inspection we can identify some integer points, such as P₁=(-2,3) and P₃=(2,5). A brute force search for x in the range -1000 to 1000 generates the following results-

> #naive point search;

> for k from -1000 to 1000 do

> if(type(simplify((k^3+17)^(1/2)),integer)) then print(k,simplify((k^3+17)^(1/2))); end;

> end;

-2, 3

-1, 4

2, 5

4, 9

8, 23

43, 282

52, 375

Silverman tells us there is a further point, P₈=(5234,378661), plus we have missed all the inverses of our points (since only the positive square root was computed). Brute force on the range -6000 to 6000 of course uncovers P₈, but this computation takes 70.6 seconds, 10.24mb of memory and produces alarming sounds from my new office computer. Silverman observes that (due to a result of Nagell) the rational points are generated by integer combinations of P₁, P₃, so we can proceed by testing some of these instead:

> read “gla.mpl”;

> a_1:=0;a_3:=0;a_2:=0;a_4:=0;a_6:=17; #setting
up the curve;

>#smarter search

> for i from -5 to 5 do

> for j from -5 to 5 do

> if(type(mnadd(i,j,-2,3,-1,4)[1],integer) and type(mnadd(i,j,-2,3,-1,4)[2],integer)) then print(i,j,mnadd(i,j,-2,3,-1,4));

> end if;

> end:

> end:

-3, -2, 43, -282

-2, -3, 5234, -378661

-2, -1, 2, -5

-2, 0, 8, 23

-1, -1, 4, 9

-1, 0, -2, -3

-1, 1, 52, -375

0, -1, -1, -4

0, 1, -1, 4

1, -1, 52, 375

1, 0, -2, 3

1, 1, 4, -9

2, 0, 8, -23

2, 1, 2, 5

2, 3, 5234, 378661

3, 2, 43, 282

All sixteen points are recovered in 0.02 seconds, consuming merely 0.31mb of memory!

Of course, for this example I’m cheating somewhat because I know where I’d like to get to in that I know this list is complete; although a priori there’s no indication of how large the arguments m,n needed to be to generate points such as P₇ or P₈. Nonetheless, this indicates that the procedures allow for more rapid exploration of points on the curve, even if they don’t prove anything (besides existence) by themselves.

Example 2

Maple’s own algcurves package can also be useful to tackle problems given in projective terms. For instance, we can rapidly demonstrate the first result claimed in Exercise 3.3b. Here we are concerned with the curve

which homogenizing away from Z=0 gives

However, this is not of Weierstrass form; but we can retrieve this from Maple:

> with(algcurves):

> f:=x^3+y^3-A

> Weierstrassform(f,x,y,x0,y0)

This yields

But this is not quite of the Weierstrass form as used in Silverman; we substitute -x₀ for x₀ to arrive at

That is, we have that the curve coefficients a_i are all zero except a₆=27A²/4; we also have an isomorphism φ between E and its Weierstrass form given coordinatewise. We can verify with the procedure j_invariant that these are indeed the same curve (it turns out to have j invariant zero, too). Moreover, we can show the desired result, that

For this, let P=(x_0,y_0) a point on the curve in Weierstrass form. Then we compute -P:

> a_1:=0;a_3:=0;a_2:=0;a_4:=0,a_6=-27*A^2/4:

> read “gla.mpl”:

> ellm(x_0,y_0);

x_0, -y_0

Then, identifying P with a projective point via the isomorphism, we find

Which is the desired result.

Update: These procedures have been replaced with a more general (and efficient) set: see this post!

Overview

These maple procedures implement the group law algorithm for an elliptic curve as given in Chapter III Section 2.3 of Silverman’s The Arithmetic of Elliptic Curves. In particular, they can handle the group identity symbolically as it arises during calculations.

Loading the procedures

The procedures can be downloaded as the maple file gla.mpl, which should be placed in whatever directory Maple expects to find it. To be more helfpul, this is probably your home directory on Unix based systems; on Windows it could be the application directory, although if you invoke maple by opening a worksheet, it’ll be the directory that sheet resides in. If you’re unsure, entering the following:

> x:=5;

> save x, “test.m”;

Will create a file test.m which you can then search for to determine the appropriate directory.

Having established where the file goes, you then need to read it into Maple:

> read “gla.mpl”;

Which after some shameless self-promotion gives you the procedures. The assumption is that you have an Elliptic curve given by a Weierstrass equation determined by coefficients a₁,…,a₆ as in Silverman:

You can of course work in full generality without defining these coefficients. The point at infinity is referred to as zero, whilst a point P=(x,y) can be specified as x,y (using (x,y) will likely give errors).

The procedures

Looking at the source you’ll find various procedures, some of which are only needed for the internal workings- in particular, elladd cannot handle zero and should not be used directly. The operations available are:

Elliptic addition (ella)

Addition with the group law is achieved by a call to the ella procedure; a typical call is ella(x1,y1,x2,y2) to compute x1,y1+x2,y2=P₁⊕P₂; however, you may substitute zero for either or both points (for instance, ella(zero,x,y) is valid). In accordance with 2.3(b) this either returns zero or x(P₁+P₂),y(P₁+P₂).

Inverse of a point (ellm)

Given a point P=(x,y), ellm(x,y) returns the group inverse, i.e., the point -P. zero is understood and is its own inverse.

Integer multiples (ncopies)

Repeated iteration of ella for a single point P=(x,y) is made available by ncopies(n,x,y), for n an integer. As before, zero may be (somewhat pointlessly) subsituted for x,y. Care is taken to ensure zero is appropriately handled at each stage, and thus may be returned as an answer (always, for n=0). Negative values of n are of course handled by returning n copies of -P, so this provides an alternative to ellm.

Addition of integer multiples (mnadd)

For convenience, two such integer multiples [m]P₁,[n]P₂ can be added using mnadd(m,n,x1,y1,y2); as usual zero can replace a pair of coordinates (or both).

To save carrying the original paperwork about, and to give myself a recap on the material, I’ve written up the lecture notes from MA40037:Galois Theory as taught at the University of Bath by Geoff Smith.

The content is broadly as follows: Rings, Integral Domains, Fields of Fractions, Units, Ideals, Homomorphisms, The First Isomorphism Theorem, The Chinese Remainder Theorem, Irreducibles, Field Extensions, Characteristic, Minimal Polynomials and Algebraic Numbers, Galois Theory.

The notes very closely match those I made and hence the lectures given, except the section on the Chinese Remainder Theorem, which was adapted from problem sheets. There have been various minor linguistic tweaks, but few mathematical ones.

It should be noted (to avoid confusion under composition) that the convention of writing function arguments to the left (i.e., (x)f rather than f(x)) is adopted here; and that square brackets are sometimes used for factors in polynomials where these appear in expressions also featuring function or polynomial evaluations (which are denoted by round brackets).

Proof reading would be appreciated!

I managed to arrange a talk by Nina Snaith for the final event by the undergraduate maths club I helped set up this year. As at Durham, she spoke on her work connecting quantum chaos to the moments of the riemann zeta function, via random matrix theory. Turnout was good, including some postgrads and staff, and the advantage of hearing the talk here is that I benefit from any feedback or insights they have.

To calculate the moments requires knowledge of a particularly elusive coefficient g_k, about which very little is known: g₀ is trivially 1, Hardy and Littlewood established that g₁=1 in the early part of the 20th century, Ingham proved that g₂=2 in 1926. No progress was made until 1995, when Conrey and Ghosh conjectured that g₃ was, of all things, 42. At a conference in Vienna, Conrey and Gonek planned to present a conjecture for g₄; yet the random matrix theorists had a conjecture for all values of k. Following some frantic checking at a blackboard, it was confirmed that the two conjectures agreed for g₄=24024: and thus that quantum physics really could offer predictions about number theory!

One of my lecturers plugged the coefficients 1,1,2,42,24024 into the OEIS, and just one result comes up, sequence A039622. Curiously, this is about Young diagrams, which are linked to irreducible representations of the symmetric group. Young Tableau themselves describe a fairly elegant number theory puzzle. I’ve been studying representation theory this semester, and I’m always amazed by how different strands of mathematics can pull together like this- from quantum theory to distribution of primes to symmetry, somehow they’re all woven together.

For an overview of the current status of work on the Riemann Hypothesis, including Random Matrix Theory, see this article by Conrey. Marcus Du Sautoy’s the music of the primes also mentions Nina’s work, and Riemann’s own study of problems in Physics alongside the zeta function.