Elliptic Curves (mastermath 2007-2008): Computer class
Practical matters
The computer class takes place:
VU, Science buildingroom P4.47 (Linux terminals)
Tue 15 April 2009, 10.15-13.00
Exercises
In this computer class, you will learn to use two practical and free computer programs to compute with elliptic curves. You will not be actually analyzing algorithms, but rather see how to make the computer solve problems for you that you used to do by hand. For this reason, I have picked most problems from the exercise sheets or from the correspondence between Fermat and his contemporaries. For some algebraic manipulations, it might be useful to invoke things such as Mathematica or Maple.
The standard number theoretical package is pari (http://pari.math.u-bordeaux.fr/). You can call this from a terminal window with
gp <enter>
Check through the section on elliptic curves of the "User's
Guide" in the "Documentation" area of the web page to see the syntax
for elementary calculation with elliptic curves (input, j-invariant,
lattice, torsion group, addition, ...). Now you can do this exercise:
Exercise 1. Compute nP for all n in Z where P is the point P=(3,8) on the elliptic curve y2=x3-43x+166.
Pari has two algorithms to compute the rational torsion
subgroup: Doud's algorithm and Lutz-Nagell. Use both in the following
example, and compare running times:
Exercise 2. Compute the torsion subgroup of E(Q) for E: y2+xy-5y=x3-5x2.
The next exercise is about determining the lattice of an elliptic curve.
Exercise 3. (Homework: hand in the solution to this exercise on paper, in groups of two people.) Determine the lattices corresponding to the elliptic curves y2=x3+1 and y2=x3+2. Explain why both elliptic curves are isomorphic over C in two ways: (a) in terms of the Weierstrass equations; (b) in terms of the lattice generators that you found. The lattice (up to scaling) of these elliptic curves is very special: it is generated by quadratic numbers (i.e., sollutions of equations of degree two over Q - in general, the lattice has only transcendental generators). Use the command algdep to find a closed expression for quadratic generators for the lattice (Note that the generators that pari found for you are not necessarily algebraic themselves).
To compute the rank of elliptic curves, we use mwrank
(http://www.warwick.ac.uk/~masgaj/mwrank/). You can call this program by typing
mwrank <enter>
on a console. You are then asked to input the coefficients a1,...,a6
of a curve with integer coefficients in Weierstrass form, separated by
blank spaces. After "enter", the program will try to compute the rank
and generators for the free part of the MW-group, and give you
information on how it was computed. After a computation is finished,
mwrank will ask for a new curve. If you want to interrupt the program,
press ctrl-z.
Exercise 4. Compute the rank of the following elliptic curves (see Stevenhagen's notes, par. 4)
(a) y2=x(x-3)(x+4);
(b) y2=x(x-1)(x+3);
(c) y2=x(x+1)(x-4);
(d) y2=x(x2+1)
Exercise 5. Cubic Fermat x3+y3=z3 leads to an elliptic curve in Weierstrass form y2=x3-432. Use pari and mwrank to compute the group of rational points on this curve (torsion and rank). This solves a problem that only Euler could do!
Fermat asked Mersenne: find a triple (X,Y,Z) of mutually coprime integers that are sides of a right angled triangle, so that both the hypothenuse Z and the sum X+Y of the other sides are squares. In formulas: X2+Y2=Z2, Z=b2, X+Y=a2. With e=X-Y this gives e2=2b4-a4, and hence we find a rational point on v2=2u4-1. The tranformation
Exercise 6. Can the sum of the first y integers equal the sum of the first x squares? The usual formulas for those sums transform this problem into finding positive integer points on an elliptic curve. Find that elliptic curve, and find its Mordell-Weil group. Conjecture what the full set of solutions to the original problem is.
y=4((2u-1)v+2u3-1)/(u-1)3
An integer is congruent if it is the area of a right angled triangle with rational sides. The number 6 is congruent as the area of a triangle with sides (3,4,5). Fermat proved that 1,2,3 are not congruent and Fibonacci showed that 5 is congruent for (3/2, 20/3, 41/6). For squarefree n, the following are equivalent:
Exercise 7. Check this. Find an inverse transformation that expresses u and v in terms of x and y. Compute the group of rational points on the elliptic curves and, in this way, generate a nice complicated looking solution for the initial problem.
(a) n is congruent,i.e., n=ab/2 with a2+b2=c2.
(b) There exists a rational point on the elliptic curve y2=x3-n2x different from (0,0), (-n,0),(n,0) and O.
The Fermat equation of exponent 4 (x4+y4=z4) has no solutions, as was already known to Fermat, by looking at u4+v4=w2. A solution leads to a rational point on the quartic Y2=X4+1. The tranformation
Exercise 8. Check the claim of Fermat using this equivalence. Try finding a right angled triangle with area 157. (It exists, but whether you will find it... Don Zagier computed the smallest solution some years ago: it involves rational numbers with 24 digits in numerator/denominator.)
Y=(y2+8x)/(4x2)
Let Np denote the number of projective points on the elliptic curve y2=x3-4x2+16 over a finite field Fp with p elements (p prime). Let Mn denote the coefficient of qn in the formal power series expansion of the infinite product q ∏ (1-qn)2(1-q11n)2.
Exercise 9. Prove Fermat for exponent 4 by computing the rational points on this curve.
Exercise 10. Compute Mp+Np for all primes p<100. What do you observe?
Exercise 11. Conjecture a formula for the rank of the elliptic curves E_p: y2=x3+px depending on a variable prime number p.
Exercise 12. Investigate whether, for any integer n in the interval [24-2√23, 24+2√23], there exists an elliptic curve with precisely n projective points over the field F23 with 23 elements.
Exercise 13. Choose a point P of infinite order on your favourite elliptic curve in short Weierstrass form, and compute a square root hn of the denominator of the x-coordinates of the first few multiples nP of P. Study connections between the values ha and hb.- The End -