Karim Belabas on Sat, 14 Jul 2012 14:40:17 +0200 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: Possible improvements for bnfcertify and documentation |
* 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] `