THIS FILE IS OBSOLETE -- SEE MWRANK.INFO INSTEAD Program mwrank: uses 2-descent (via 2-isogeny if possible) to determine the rank of an elliptic curve E over Q, list a set of points which generate E(Q) modulo 2E(Q), and finally search for further points on the curve. For details of algorithms see the author's book. Please acknowledge use of this program in published work, and send problems to cremona@maths.exeter.ac.uk. For changes since first distribution the file mwrank.changes. For command line options, see the file mwrank.options. MWRANK vs. MRANK There used to be two separate programs called mwrank and mrank; they both did the same 2-descent, but mwrank also went on to enlarge the subgroup of rank r found to give the full Mordell-Weil group by searching for rational points on E up to a certain naive height. This latter procedure is not very efficient, and to avoid reports of known problems at this stage I have put a ceiling on this search at 15 (=logarithmic naive height). This means that in many cases the points finally output are NOT guaranteed to be a basis for E(Q) (but the output should say this). Now the same functionality is provided by adjusting options for the one program mwrank. A HOW TO USE MWRANK 1. Options All options and parameter adjustments are now made via command line options: see the file mwrank.options for details, or run mwrank -h which displays the options briefly and exit. 2. Curve input The input consists of one or more curves, in the format a1 a2 a3 a4 a6 (separated by whitespace), or [a1,a2,a3,a4,a6] These can of course be from a file, as in mrank < curves.in To end the input either use a "null curve" [0,0,0,0,0] or EOF (e.g. Control-d at the terminal). The input coefficients MUST be integers: attempting to input non-integral rationals including the '/' symbol will cause an error message to be output and the program will abort. The curves are prompted for, unless verbosity is set to 0. For example, given the input file r5.in containing 0 0 1 -79 342 0 0 1 -169 930 0 1 1 -30 390 0 0 1 -301 2052 0 0 1 -457 3786 the command mrank -q -v 0 < r5.in produces the output Curve [0,0,1,-79,342] : Rank = 5 Curve [0,0,1,-169,930] : Rank = 5 Curve [0,1,1,-30,390] : Rank = 5 Curve [0,0,1,-301,2052] : Rank = 5 Curve [0,0,1,-457,3786] : Rank = 5 adding "-l" to the parameters will cause the generators and regulators to be output; adding "-o" results in an abbreviated form of output to be output also for post-processing by Pari; for the first curve above it gives [[5],[[3,11],[43,276],[45,296],[62,483],[92,878]]] 3. There are two types of point search carried out by mwrank. (a) On the homogeneous spaces which represent elements of the appropriate Selmer group, called "quartics" in the program (they have equations y^2=g(x) where g is quartic). Here existence of rational points is necessary for the homogeneous space to come from a point on the curve rather than an element of the Tate-Shafarevitch group. The bound used is a bound on the logarithmic height. If (x,y)=(u/w,v/w^2) it is a bound on max(log|u|,log|w|). The default value is 10; to change the default to (say) 12 use command-line option "-b 12". Warning: increasing this bound even by 1 can increase the running time considerably when there really are homogeneous spaces with no rational point (but with points everywhere locally, of course). I would not recommend setting this to more than 15: even if you are "sure" that the quartic has a rational point, other methods such as higher descents are probably better to find such large points. For entirely logical reasons it can also happen that reducing the value of this parameter can increase the running time -- and vice versa. So while 10 is the default it is sometimes worth running with a smaller value. (In the above examples, -b 1 works just as well, i the same time). If the curve has rational 2-torsion, then the search on the first descent curves has a bound of at most 6 (less if you set it using -b), and then a second descent is used if necessary, where the full bound is used. NB This second descent works pretty well, but is the newest part of the program so is the most likely to cause problems. One problem is this: part of the quartic reduction process works much better using multiprecision floating point arithmetic, but the distributed version of the program does not have this. The reason: my programs currently either use multi-fp for ALL fp arithmetic, or for NONE; and turning it on (which is a simple compiler switch) slows down other parts of the program a lot, so for most curves it is better to have it off. Ask me for a multi-fp version if you want one. (b) if the parameter -c is set to a nonzero value, then after the 2-descent when we (should) have points covering the cosets of 2E(Q) in E(Q) a further search is done, on the curve itself, up to a certain bound on the logarithmic height. The program computes a suitable bound such that if it searches that far you are guaranteed to have the full Mordell-Weil group. You can use this value by entering "-c -1", BUT for many curves it will not be practical to search that far. So I have put a ceiling on this of 15. You can put your chosen bound on it with the command-line option -c, for example "mwrank -c 5 ...". Here is an idea of how long this point search takes on a curve of rank 3 on my 90MHz Pentium (NB times not updated for recent version): Bound Time 10 8.5 secs 11 34 12 147 13 652 14 2895 secs =48 mins estimates (by simple-minded extrapolation): 15 3.5 hours 16 15.4 h 17 67.8 h = 2.8 days 18 12.4 days 19 55 days 20 241 days So you are recommended to give a small value for a first run (or even 0, i.e. leave it as the default in which this step is omitted entirely) B. WHAT IT DOES There are two main sub-cases depending on whether the curve has a point of order 2 or not. If so, it uses the 2-isogeny in the well-known way, and can list the quartics to be considered with little trouble. Then the only difficulty is finding rational points on them. I have successfully run curves of rank 13, such as Fermigier's 0 36861504658225 0 1807580157674409809510400 0 and also his rank 14 curve 0 2429469980725060 0 275130703388172136833647756388 0 (approx 5 minutes with default parameters, no 2nd descent required) but am having difficulty with his rank 15 curve with 2-torsion. If there is no 2-torsion it goes back to the original Birch-Swinnerton-Dyer method, which involves searching for the quartics, and eliminating equivalent ones. The search region can be very large if the curve coefficients are large. Also the search is divided into between 1 and 4 sub-searches. Recent developments make this rather more efficient, (a) by improving the bounds, (b) by using a quadratic sieve in the search for quartics, and (c) by using maps to E(Qp)/2E(Qp) for certain auxiliary primes p. NB One effect of the last-named feature is that the program usually finds generators for E(Q)/2E(Q) rather than a complete set of coset representatives. In general, it will express E(Q)/2E(Q) as a direct sum A+B, and will give all nonzero elements of A and generators for B (the output will explain this when it occurs). The points in A are those which lie in 2E(Qp) for all the auxiliary primes used. For curves of higher rank one can increase the number of primes used from the default of 6 to something a little higher than the suspected rank, using the option "-x 8" say. This does carry a little overhead. Example: The curve [0,0,0,-9217,300985] has rank 7 and runs very quickly. With the default ("-x 6") we find three nonzero points in A, so rank(A)=2, and 5 generators of B, so rank(B)=5 and the total rank is 2+5=7. With "-x 9" this becomes 1+6=7, and with "-x 10" we have A=0. (These runs all took approx 3.8 seconds on my P90). After this stage we know the rank (either certainly, if all the everywhere-locally-soluble homogeneous spaces have rational points, or conditionally, if we have decided that some of them do not but have not proved that). Next, from each homogeneous space with a point we compute a point on the original curve. This gives a set of between r and 2^r-1 points (depending on how the rank is divided between the groups A and B defined above) covering the non-trivial cosets of 2E in E (when there is no 2-torsion), and a more complicated set of points when there is 2-torsion, also covering these cosets. [If nothing else, this gives one way of finding points on curves. For example the curve [0,0,0,0,-618] has rank 2, generated (up to finite odd index) by [19 : -79 : 1] of height 3.21143 and [550688955674 : 2182722347909 : 31136956136] of height 19.2662. A simple point search would take a very long time to find that second generator!] The third stage is to try to enlarge the group of points found to a basis for the full Mordell-Weil group (so far we have a subgroup of finite ODD index). This stage (the "infinite descent") is not at all efficient at present (see 2b above); we hope to implement new ideas of Siksek to improve this one day. So unless you have set the third parameter to -1 and waited for the program to stop, and have NOT seen a warning that the bound computed is too large to reach, then you can NOT say for sure that you have the whole group. DISCLAIMER You are welcome to use the program as is. There have been bugs and certainly there still are some. The program can and will be improved. Please report strange behaviour to me in a reasonable way (you must say when you got your copy of the program and include an input file which gives the problem); I do not guarantee to do anything about it -- I am busy and this is not a commercial package! -- but I will do my best. I particularly do NOT want to hear problems which are machine-dependent! John Cremona 3 February 1995 updated 12 January 1998