| Michael Stoll on Fri, 19 Jun 1998 14:49:12 +0200 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
| Re: Class groups |
Gerhard Niklasch <nikl@mathematik.tu-muenchen.de> writes
GN> Anybody know which version of the PARI kernel would be included in that
GN> version of MAGMA?
The number field algorithms of Magma are based on KANT, not on PARI.
GN> And whether the result computed by MAGMA is in fact correct? :)
You can never know with absolute certainty whether such a result is correct...
But see below.
GN> > gp (18:18)> bnfclgp(x^4 + 5*239*x^2 + 5*239^2)
GN>
GN> >From running this with verbose diagnostics turned on (default(debug) is
GN> your friend, if you can read fast :^),
Even default(debug,1) is too fast for me... or maybe my computer is too
fast...
GN> it seems the thing keeps doubling
GN> the size of its ideal factor base since after each iteration it still
GN> sees a factor-of-2 discrepancy between the class number-so-far times the
GN> regulator-so-far and the zeta function residue. (So far I can't say
GN> whether this discrepancy is real, or whether it gets one of those numbers
GN> wrong. Several other fields defined by similar polynomials are handled
GN> quickly by pari-between-2.0.9.alpha-and-2.0.10... e.g. when 239 is replaced
GN> by 199, 229, 269; with 349, it takes two factor base doublings to arrive
GN> at a result.)
GN>
GN> You may want to play around with the `tech' optional argument to see
GN> whether you can coax it into returning a result in reasonable time
GN> (and look at the diagnostic output to get an indication of what changes).
GN> I'll be chasing some other booboos in the meantime... :^)
And Claus Fieker <fieker@math.TU-Berlin.DE> says
CF> Da die relevanten Teile des Magma Systems in Berlin von der Kant Gruppe
CF> (Pohst) entwickelt werden, sind wir gewissermassen die Schuldigen.
CF> Das Problem zumindest mit x^5-539 ist die grosse Minkowskischranke.
CF> gp rechnet (standartmaessig) mit log(D)/*0.3 als Schranke fuer Primideals
CF> in der Faktorbasis, daher kommt gp weiter als wir. Wenn Du in Kash jedoch
CF> OrderClassGroup(OrderMaximal(x^5-539), 200, euler,fast); auprobierst
CF> (in magma so etwas wie (ClassGroup(o:Bound := 200, Verify := false)))
CF> solltest Du in ca. 10sec (HP735/100) ein Ergebnis erhalten.
CF> (Du rechnest dann mit 200 als Schranke, das Ergebnis ist daher nicht
CF> garantiert)
CF> Prinzipiell gebe ich Dir jedoch recht: da ist noch jede Menge zu tun.
CF> Die anderen Beispiele werde ich mal morgen testen.
(It was 239, not 539, but I believe that this is not so very important here.)
In what way could the result be wrong? Or does `not guaranteed' mean that
there might be no result at all?
I've played around a little bit with the `Bound' and `Verify' options in
Magma and with the `tech' parameters in PARI, with the result that you can
get both systems to do the computations fairly quickly (and the results agree
:) ).
Magma:
--------------------------------------------------------------------------
Magma V2.4-BETA Fri Jun 19 1998 11:11:04 on lordly [Seed = 948381221]
Type ? for help. Type <Ctrl>-D to quit.
> P<x> := PolynomialRing(Rationals());
> K := NumberField(x^5+239);
> MinkowskiBound(K);
198779
> BachBound(K);
10766
> time ClassGroup(K : Bound := 200, Verify := false);
Abelian Group isomorphic to Z/10
Defined on 1 generator
Relations:
10*$.1 = 0
Mapping from: Abelian Group isomorphic to Z/10
Defined on 1 generator
Relations:
10*$.1 = 0 to Set of ideals of Equation Order of K
Time: 2.529
> Log(Discriminant(K));
29.95304376989654454085645104312
> Regulator(K);
7800.8001823817906213676431585017409167098078958959719999999216
// ^-- This takes several minutes
> time UnitGroup(K);
Abelian Group isomorphic to Z/2 + Z + Z
Defined on 3 generators
Relations:
2*$.1 = 0
Mapping from: Abelian Group isomorphic to Z/2 + Z + Z
Defined on 3 generators
Relations:
2*$.1 = 0 to Equation Order of K
Time: -1.999
// i.e. instantaneous, since computation already done for Regulator
// I don't know why the timing is negative here...
> L := NumberField(x^4 + 5*239*x^2 + 5*239^2);
> time ClassGroup(L);
Abelian Group isomorphic to Z/2 + Z/8 + Z/8
Defined on 3 generators
Relations:
2*$.1 = 0
8*$.2 = 0
8*$.3 = 0
Mapping from: Abelian Group isomorphic to Z/2 + Z/8 + Z/8
Defined on 3 generators
Relations:
2*$.1 = 0
8*$.2 = 0
8*$.3 = 0 to Set of ideals of Maximal Order of L
Time: 44.460
> MinkowskiBound(L);
1624
> BachBound(L);
4130
> Regulator(L);
0.9624236501192068949955178268487368462703686687716283999998
> time UnitGroup(L);
Abelian Group isomorphic to Z/2 + Z
Defined on 2 generators
Relations:
2*$.1 = 0
Mapping from: Abelian Group isomorphic to Z/2 + Z
Defined on 2 generators
Relations:
2*$.1 = 0 to Maximal Order of L
Time: -1.999
> M := NumberField(x^4 + 5*458*x^2 + 5*458^2);
// ClassGroup(M) triggers a bug
> time ClassGroup(M : Bound := 200, Verify := false);
Abelian Group isomorphic to Z/2 + Z/4 + Z/40
Defined on 3 generators
Relations:
2*$.1 = 0
4*$.2 = 0
40*$.3 = 0
Mapping from: Abelian Group isomorphic to Z/2 + Z/4 + Z/40
Defined on 3 generators
Relations:
2*$.1 = 0
4*$.2 = 0
40*$.3 = 0 to Set of ideals of Maximal Order of M
Time: 4.749
> time UnitGroup(M);
Abelian Group isomorphic to Z/2 + Z
Defined on 2 generators
Relations:
2*$.1 = 0
Mapping from: Abelian Group isomorphic to Z/2 + Z
Defined on 2 generators
Relations:
2*$.1 = 0 to Maximal Order of M
Time: 3.419
> Regulator(M);
0.9624236501192068949955178268487368462703686687693403999999
// The regulators of L and M are the same, since the unit comes
// from their common maximal real subfield Q(sqrt(5)).
--------------------------------------------------------------------------
PARI:
--------------------------------------------------------------------------
GP/PARI CALCULATOR Version 2.0.7 (alpha)
i586 running linux (ix86 kernel) 32-bit version
(readline enabled, extended help available)
Copyright 1989-1998 by
C. Batut, K. Belabas, D. Bernardi, H. Cohen and M. Olivier.
Type ? for help.
realprecision = 28 significant digits
seriesprecision = 16 significant terms
format = g0.28
parisize = 4000000, primelimit = 500000, buffersize = 30000
? bnfclgp(x^5+239)
%1 = [10, [10], [[39, 15, 3, 24, 13; 0, 3, 0, 0, 1; 0, 0, 3, 0, 1; 0, 0, 0,
3, 1; 0, 0, 0, 0, 1]]]
? ##
*** last result computed in 2,840 ms.
? bnf = bnfinit(x^5+239);
? ##
*** last result computed in 2,870 ms.
? bnf.reg
%3 = 7800.800182381790621367643158
? bnf=bnfinit(x^4+5*239*x^2+5*239^2,0,[1.0,1.0,10,1.0,10,5]);
time = 8,130 ms.
? bnf.clgp
time = 0 ms.
%8 = [128, [8, 8, 2], [[191, 58, 105, 22; 0, 1, 0, 0; 0, 0, 1, 0; 0, 0, 0,
1], [262, 204, 93, 1; 0, 2, 1, 0; 0, 0, 1, 0; 0, 0, 0, 1], [10, 0, 5, 5; 0,
2, 1, 0; 0, 0, 1, 0; 0, 0, 0, 1]]]
? bnf.reg
time = 0 ms.
%9 = 0.9624236501192068949955178268
? bnf.fu
time = 0 ms.
%10 = [Mod(1/239*x^2 + 2, x^4 + 1195*x^2 + 285605)]
? bnf=bnfinit(x^4+5*458*x^2+5*458^2,0,[1.0,1.0,10,1.0,10,5]);
time = 20,440 ms.
? bnf.clgp
time = 0 ms.
%12 = [320, [40, 4, 2], [[101, 93, 25, 99; 0, 1, 0, 0; 0, 0, 1, 0; 0, 0, 0,
1], [1321, 1195, 871, 103; 0, 1, 0, 0; 0, 0, 1, 0; 0, 0, 0, 1], [229, 0, 150,
0; 0, 1, 0, 0; 0, 0, 1, 0; 0, 0, 0, 1]]]
? bnf.reg
time = 0 ms.
%13 = 0.9624236501192068949955178268
? bnf.fu
time = 0 ms.
%14 = [Mod(1/458*x^2 + 2, x^4 + 2290*x^2 + 1048820)]
--------------------------------------------------------------------------
My machine has a Pentium 200 S CPU, in case you want to compare timings
(timings vary, however, because of some probabilistic parts of the algorithms,
I guess).
Finally, here is a general question for you Algorithmic Number Theory people.
Let U (written additively) be the unit group and C the class group of some
number field. Is it in any way easier to get generators for U/2U, C[2] and
C/2C (with the possibility to decide if a given ideal I is mapped to zero in
this last group, and if so, to get an ideal J such that I*J^2 is principal)
rather than to compute all of U and C?
Cheers,
Michael