Re: Possible improvements for bnfcertify and documentation

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

* John Jones [2012-07-12 22:19]:
> The documentation for bnfinit says that the computation of both the class
> group and fundamental units assumes GRH.  In bnfcertify there is a flag to
> only certify that the class group is a quotient of the one which is
> computed.  It would be good if the documentation would clarify whether or
> not this affects certification of the units.

Done in master. Thanks !

> Also, there are fields where pari spends much longer than magma in
> certifying class group/unit data. I don't know the internal algorithms in
> detail, but have the impression that they are doing very similar things,
> but with different bounds.  If so and you can find out what bounds magma
> uses, then maybe pari could use the minimum of its current bound and
> whatever magma is using?

There are two bounds: 
- one to certify that our factorbase generate the class group (chosen so
  that this is true under GRH). PARI and Magma use analogous bounds
  here, that could in fact "easily" be improved, but this takes a
  negliglible amount of time in your (and most) examples anyway.

- one to certify that we have the full unit group, by ruling out all
  (possible) prime divisors of the index of our units in the unit group.
  This one is "computational" and hinges on a lower bound for the
  regulator for the fixed field under consideration. If the computation
  "fails", we use Zimmert's universal R > 0.2.

  In principle, Magma and PARI use the same general method, due to
  Pohst-Zassenhaus, but I think that Magma has a better algorithm
  than PARI, following Fieker-Pohst's :

    http://www.sciencedirect.com/science/article/pii/S0022314X08001121

  It's close to what we do, but there are a few differences; we should
  implement that one.

This would have the extra benefit of removing the single part of PARI
which I'm unsure of, mathematically: I have no precise reference in the
litterature corresponding to our regulator bound implementation (due to
Michel Olivier around 1995, who no longer maintains it). I only know it
follows roughly Pohst-Zassenhaus's method. (The original exposition in
"Algorithmic Algebraic Number Theory" has known counter-examples, one
being given in Fieker-Pohst's paper, but our implementation *does* work
in that case...).

Cheers,

    K.B.
-- 
Karim Belabas, IMB (UMR 5251)  Tel: (+33) (0)5 40 00 26 17
Universite Bordeaux 1          Fax: (+33) (0)5 40 00 69 50
351, cours de la Liberation    http://www.math.u-bordeaux1.fr/~belabas/
F-33405 Talence (France)       http://pari.math.u-bordeaux1.fr/  [PARI/GP]
`