Karim Belabas on Wed, 30 Apr 2008 11:14:24 +0200 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: Just curious... |
* Kurt Foster [2008-04-30 05:53]: > I ran into a warning and error message with bnfcertify() that piqued > my curiosity. I've had Pari simply bail out on bnfcertify() before, > because the Minkowski bound was too large. But this time it merely > issued a warning on the size of the Minkowski bound, and THEN > (probably fortunately) bailed out because my primelimit wasn't big > enough. "VERY long" sounds ominously like "a geological epoch." This message is a little obsolete, and so is the harsh dependency on primelimit. Basically, we have a small amount of work to do for each prime less than the Bound (see below). There is no need to have all primes simultaneously on memory, having them up to sqrt(Bound) is enough for a simple and efficient enumeration. [ And even then, compared to the work we have to do, nextprime(p+1) would be negligible. ] I'll fix this. > I compared the primelimit suggested by the error message to the > Minkowski bound. It's a little less than 1/12th as big. Does this > correspond to some refinement of the classical result that every ideal > class contains an integral ideal whose norm is at most the Minkowski > bound? The bound is based on Zimmert's "twin class theorem", itself a derivative of Weil's explicit formula. (What we're really asserting is that, for each ideal class C, either it has a small ideal representative or DC^(-1) has, where D is the class of the different.) @article{Zim:reg, AUTHOR = {Zimmert, R.}, TITLE = {Ideale kleiner {N}orm in {I}dealklassen und eine {R}egulatorabsch\"atzung}, JOURNAL = {Invent. Math.}, FJOURNAL = {Inventiones Mathematicae}, VOLUME = {62}, YEAR = {1981}, NUMBER = {3}, PAGES = {367--380}, ISSN = {0020-9910}, CODEN = {INVMBH}, MRCLASS = {12A45 (12A35)}, MRNUMBER = {83g:12008}, } Zimmert's paper is short but a little hard to follow, Oesterle gives a very lucid explanation: @incollection {MR902832, AUTHOR = {Oesterl{\'e}, Joseph}, TITLE = {Le th\'eor\`eme des classes jumelles de {Z}immert et les formules explicites de {W}eil}, BOOKTITLE = {S\'eminaire de th\'eorie des nombres, Paris 1983--84}, SERIES = {Progr. Math.}, VOLUME = {59}, PAGES = {181--197}, PUBLISHER = {Birkh\"auser Boston}, ADDRESS = {Boston, MA}, YEAR = {1985}, MRCLASS = {11R29 (11R42)}, MRNUMBER = {MR902832 (88j:11073)}, MRREVIEWER = {R. W. K. Odoni}, } Unfortunately, Zimmert's bound is "programmatic" (depends on free parameters, which we may optimize) and I have no reference for the *specific* bound used in PARI [ I partly wrote the current implementation but the bound was there before ]. Also, there are other bounds out there, which should be better in practice: @article {MR2373197, AUTHOR = {Belabas, Karim and Diaz y Diaz, Francisco and Friedman, Eduardo}, TITLE = {Small generators of the ideal class group}, JOURNAL = {Math. Comp.}, FJOURNAL = {Mathematics of Computation}, VOLUME = {77}, YEAR = {2008}, NUMBER = {262}, PAGES = {1185--1197}, ISSN = {0025-5718}, CODEN = {MCMPAF}, MRCLASS = {11R04 (11R29)}, MRNUMBER = {MR2373197}, } This paper has a conditional (GRH) and an unconditional part, the latter has not been developped / optimized; the few unconditional examples we checked often gave large improvements on PARI's bound, but sometimes worse. I have been trying to interest a (PhD) student in understanding / cleaning this up for some time... > ? bnfcertify(qtrnfield) > *** bnfcertify: Warning: large Minkowski bound: certification will be VERY long. > *** bnfcertify: not enough precomputed primes, need primelimit ~30439469497. 3*10^10 should be doable, even with the current implementation, provided the spurious "primelimit" obstruction is lifted. 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-bordeaux.fr/~belabas/ F-33405 Talence (France) http://pari.math.u-bordeaux.fr/ [PARI/GP] `