Re: Just curious...

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

* 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]
`