Re: Bug in classno, qbfclassno?

[Karim BELABAS <Karim.Belabas@math.u-psud.fr>]

>> > [Fernando Rodriguez-Villegas:]
>> >  classno(-174660)= 168 
>> >  classno(-272580)= 180
>> [Henri Cohen]
>> This function (written by me) should definitely be removed, or rewritten
>> correctly. It is based on a naive version of Shanks baby step giant step
>> method which assumes that the approximate class number obtained by an
>> Euler product is good enough, and that the class group is not too far
>> from cyclic. The main reason for the bug is that the class group has
>> large 2 rank. It is not difficult to write a correct baby step giant step
>> method which completely avoids this (one has to take into account the
>> full group structure, and I give the algorithm in my GTM 138 book,
>> starting from the second printing, the first printing has serious
>> errors), but in 10 years I have been lazy to do so because of the much
>> more powerful quadclassunit algorithms based on Hafner-McCurley
>> subexponential methods (assuming GRH).
>[Igor]
>
>Powerful yet not flawless (at least implementation-wise) :-)
>
>? setrand(1);quadclassunit(-108760)[1]
>48
>? setrand(58);quadclassunit(-108760)[1]
>72

According to the documentation: (??quadclassunit)

----------------------------------------------------------------------------
   Optional  parameter tech is a row vector of the form [c_1,c_2],  where c_1
and  c_2  are  positive real numbers which control the execution time and the
stack  size.   To get maximum speed,  set c_2 = c.   To get a rigorous result
(under GRH)  you must take c_2 = 6.   Reasonable values for c are between 0.1
and 2.       ^^^^^^^^^^^^^^^^^^^^^
----------------------------------------------------------------------------

In other words, by default, for the sake of speed (and sometimes, of
feasability...), none of the PARI classgroup functions have a guaranteed
output, even under GRH, because they replace Bach's bound by a small
multiple (about 1/50 times the correct bound).

In fact :

? setrand(58);quadclassunit(-108760, , [0.1, 6])[1]
48

(in this case it doesn't make a real difference in running times since the
answer is nearly instantaneous, but it's still about twice slower)

       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://hasse.mathematik.tu-muenchen.de/ntsw/pari/