Karim BELABAS on Sun, 8 Sep 2002 22:32:18 +0200 (MEST)

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

Re: yet another rnfkummer() posting

On Wed, 4 Sep 2002, Igor Schein wrote:
> ? setrand(2);rnfkummer(bnrinit(bnfinit(quadpoly(-6580,y)),9,1),matdiagonal([3,1,1,1]));
>   ***   not an Abelian extension in rnfnormgroup.

On Fri, 6 Sep 2002, Igor Schein wrote:
> ? \p400
>    realprecision = 404 significant digits (400 digits displayed)
> ? setrand(3);rnfkummer(bnrinit(bnfinit(quadpoly(2540,y),1),9,1),[3,1;0,1]);
>   ***   precision too low in isunit.
> Before it was working fine at default precision.

Just to recap. These two are the only surviving bugs in the "bnfinit & friends"
list (including the long threads about rnfkummer), and I have no really good
idea to fix them.

   Both are due to a wrong bnf [respectively, wrong classgroup and wrong unit
group], computed internally by rnfkummer, due to a failure of the heuristic
bound we use instead of Bach's bound (and some amount of bad luck).

The only (proven) fix I see is to enforce the use of Bach's bound by default,
and let the user live dangerously if she wishes. That means setting c2 = 12 in
the terminology of the manual; or rather follow Bach's algorithm and compute a
good bound ourselves, which will be of the order of 1 except for small fields.
[ 12 is a nice looking universal bound, nowhere near optimal ]

Setting c2 = 12, the typical bnfinit() call [ as estimated by the nfields bench
and a series of tests on cubic fields ] would be about three times slower.

Setting c2 = 1; the overhead looks small, possibly about 50%.

Setting c2 = 0.4 fixes the 2 bugs for a ~ 10% slowdown.

Anyway, I have added these two examples to the TODO list.

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/