Karim Belabas on Thu, 29 Aug 2002 12:08:47 +0200 (CEST)

[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Re: latest regression

> in the latest CVS, simple commands like bnfclassunit(x^2-5) hang.

Fixed. I had cleaned up some of the most sordid hacks in that area [fixing a
number of conceptual bugs in the process], while investigating a (still open)
bnfinit bug [cf pari-dev-{1624, 1630}], but had fallen into the following
(non-obvious) trap:

  under GRH, prime ideals of norm less than C log^2 |D_K| generate the class
group, with some suitable constant C, e.g C = 12. The current code cheats on
the value of C (takes a much smaller value, double it upon failure, until
things settle down). If K is quadratic, then C = 6 will always do, and I had
enforced that.

Unfortunately, the algorithm as implemented requires a "suitable"
sub-factor-base to generate relations, and Bach's bound does not guarantee
that such a sub-factor-base exists. Indeed, for very small discriminants
[which I had not included in my regression suite...], C = 6 is not enough,
and we entered an infinite loop: try to compute a factor base, fail, double
C, set C = min(C,6), etc.

I've put back the old code, which set C = min(C, 12) [and fails with an
alarming error message "couldn't deal with this field, PLEASE REPORT" upon
failure with C = 12].

Using the current default values in bnfinit, a suitable sub-factor-base seems
to always exist, although I don't think anybody bothered to try and prove
this [I certainly did not]. It does not if you change the default "technical
parameter" [request a _large_ subfactorbase, and you'll get the error


Karim Belabas                    Tel: (+33) (0)1 69 15 57 48
Dép. de Mathematiques, Bat. 425  Fax: (+33) (0)1 69 15 60 19
Université Paris-Sud             Email: Karim.Belabas@math.u-psud.fr
F-91405 Orsay (France)           http://www.math.u-psud.fr/~belabas/
PARI/GP Home Page: http://www.parigp-home.de/