Re: yet another rnfkummer() posting

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

On Tue, 10 Sep 2002, Igor Schein wrote:
> On Tue, Sep 10, 2002 at 06:05:24PM +0200, Karim BELABAS wrote:
> > 1) unit group (hence regulator) is correct
> > 2) bnf structure = [60,2] (hence class number) is correct
> >
> > BUT
> >
> > 3) the generators are incorrect !!! [first one has order 60, but the second
> > one is principal]
> >
> > Again, no way to fix this without increasing the heuristic bound we use in
> > place of Bach's bound [ again 0.4 would do here ].
>
> How expensive is it to check correctness of generators and rerun with
> higher Bach's bound in worst case scenario?

If the bnf is incorrect, very bad things can happen.

1) with the current bnfcertify(), you get an infinite loop (apparent at \g2).

It's easy to modify the bnfcertify code so as to prevent infinite loops, e.g
abort after trying "hard enough" (no proven bound, the thing is
probabilistic). Currently the output is either

  1 [ correct ] or oo loop [ incorrect...].

This change would turn it into

  1 [ correct ] or 0 [ don't know. Probably incorrect ]

2) with bnfisprincipal(), you can get wrong answers [ in the case at hand,
you don't, bnfisprincipal uncovers the pretender ], possibly "proving"
everything fine, when it is not.

I don't see how to provably check that everything is fine (with guaranteed
answer, and positive probability of termination), without using the exact
Bach's bound (and assuming GRH).

Again the least expensive solution I see is to use the built-in 2-stage
bound (currently unused by default): first (heuristic) bound C1 to compute
the bnf, second (proven under GRH) bound C2 to check it, restarting with
larger C1 if things look bad in C2-stage.

I believe this would make bnfinit() about 3 times slower for easy examples
(say a few minutes running time), and it shouldn't be noticeable for tough
examples. In short it should be quite OK for individual fields, but possibly
annoying for large scale computations dealing with a lot of fields.

For direct calls to bnfinit, there's always the possibility of explicitly
cheating by fixing C2, but for internal calls in high level fonction (e.g
rnfkummer, bnrstark, etc), the user is stuck, unless we make C2 a 'default',
but then we first have to make the library aware of defaults first [ which
would not be a bad thing ]

Still thinking...

    Karim.
-- 
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/