From: kesslert@surfree.com (Troy Kesslert)
Subject: Quadratic Fields With 3-rank 5
Date: 1 Sep 00 16:52:47 GMT
Newsgroups: sci.math.numberthy
Summary: [missing]

The simplest known quadratic fields with 3-rank of 5 are Q(-d) for d=:
         5393946914743.00
            16259689667204.00
            20795556211979.00
            35102371403731.00
            46283058974903.00
            56736325657288.00
            66061883923051.00
            93323257470244.00
           117145414362747.00
           119810819605171.00
           126543066437083.00
           130276398889003.00
           131690335168648.00


This data is from Quer. I would like to know how hard it would be to do a
search for more with minimum abs(d). If we found the best min value, I
would like a computer search below that to prove that it is the best value.
I am sure we could find many computers with cycles to spare. Each value of
d produces an elliptic curve of rank 10 or 11. If someone is interested in
trying this we could make a c++ program using a good class number algorithm
and a way of producing d's that should have high 3rank.
==============================================================================

From: Karim.Belabas@math.u-psud.fr (Karim BELABAS)
Subject: Re: Quadratic Fields With 3-rank 5
Date: 1 Sep 00 18:39:32 GMT
Newsgroups: sci.math.numberthy
Summary: [missing]

[Troy Kesslert:]
> The simplest known quadratic fields with 3-rank of 5 are Q(-d) for d=:
>             5393946914743.00
[...]
> This data is from Quer. I would like to know how hard it would be to do a
> search for more with minimum abs(d). If we found the best min value, I
> would like a computer search below that to prove that it is the best value.
> I am sure we could find many computers with cycles to spare. Each value of
> d produces an elliptic curve of rank 10 or 11. If someone is interested in
> trying this we could make a c++ program using a good class number algorithm
> and a way of producing d's that should have high 3rank.

I can suggest another approach: quadratic fields of discriminant d and 3-rank
r correspond to (3^r - 1) / 2 triples of conjugate cubic fields of the same
discriminant (cubic subfields of the Hilbert class field).

Via a famous result of Davenport and Heilbronn and reduction theory, you can
easily generate all cubic fields (modulo Galois action) up to a given
discriminant bound X. The program is quite simple: 4 embedded loops generate
the 4 coefficients of the (reduced) defining cubic polynomial, each field is
guaranteed to be generated only once. This takes linear time in the output
size (itself linear in X), assuming O(X) memory space [ to avoid factoring
discriminants by using a kind of sieve ((*) this is a major bottleneck but
see below) ].

To give an idea, generating all complex cubic fields of discriminant larger
than -10^11 took me 25 days on a slow DEC alpha 5 years ago (current ones are
about ten times faster). See Math. Comp. 66 (1997), "A fast algorithm to
compute cubic fields", pp 1213-1237 [ the approach was actually initiated by
Ennola and Turunen in Math. Comp. 44 (1985), pp. 495-518. John Cremona later
improved on the bounds of the 1997 paper in the complex case, by using a
better reduction theory ].

So it's a matter of generating cubic discriminants and look for discriminants
of multiplicity exactly (3^5-1)/2 = 121.


In fact in the case at hand the cubic fields you are looking for are of a
very special type, and you can drop the assumption on memory space above
since you can get away with sieving altogether: one of the numbers (2 for
each discriminant) you'd have needed to factor is more or less a conductor
and has to be 1 here, and the other you can always deal with once you have
found it occurring 121 times...

One last problem is that you have to generate discriminants in successive
ranges of the form [kZ,(k+1)Z] since you can't possibly store them in memory
all at once. The algorithm can do that without any genuine extra cost
assuming that Z = O(X^(3/4)).

For imaginary quadratic fields, I could prove a few years ago that -653329427
is the smallest occurrence of r = 4 in a few minutes [this was probably known
before, although I'm not aware of any reference (D. Buell's book on quadratic
forms mentionned it as a conjecture)]. Computing all class groups up to that
bound would take much more time [ quick guess based on a few sample
computations using PARI/GP : a few months ]

I *think* I could also prove that 58343207081 [ btw. does anybody have a
reference for that field also ? ] is the smallest occurence of r = 4 for real
quadratic fields (a few days of computation on the same slow DEC alpha), but
I never double checked the computation.

Your example d = -5393946914743, would require about 54 times as much time as
my -10^11 (behaviour is linear due to the special fields we're interested
in). We'd lose a further factor 4 because we now have to use double precision
even on 64-bit alpha (maximal intermediate value is of the order of
1000 X^(3/2), I stopped at -10^11 for that very reason). It looks very
feasible.

Cheers,

      Karim.
__
Karim Belabas                    email: Karim.Belabas@math.u-psud.fr
Dep. de Mathematiques, Bat. 425
Universite Paris-Sud             Tel: (00 33) 1 69 15 57 48
F-91405 Orsay (France)           Fax: (00 33) 1 69 15 60 19
--
PARI/GP Home Page: http://www.parigp-home.de/