Re: rnfkummer-induced bug

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

On Fri, 26 Jul 2002, Igor Schein wrote:
> ? setrand(1);rnfkummer(bnrinit(bnfinit(quadpoly(124,y)),11,1),Mat(5))
>   ***   impossible division in diviiexact.
>
> This is happening in 2.2.3 and latest CVS.

I had decided to dump rnfkummer and wait for somebody to implement Claus
Fieker's algorithm [ Xavier Roblot already volunteered for this]. But I
changed my mind: for comparison/benching purposes, it will be useful to have
a decent implementation of rnfkummer [which uses purely Hecke's theorem].

Also, I believe the complexity of all these algorithms should be dominated by
the computation of bnfinit(polcompositum(nf, polcyclo(l)))


So I implemented a few ideas I had some years ago, the most important
of which was to do all computations formally [on formal products of "natural
basis elements", mostly S-unit generators]. Since the final generator is
defined modulo l-th powers, we are allowed to cancel arbitrary l-th powers
and the elements obtained by reducing exponents mod l before the final
'factorback' are much, much smaller than they used to be.

Another one was to extract further l-th powers from nf element x as follows:
factor x = A^l R (as a product of prime ideals, this is easy since x has
known support), such that valuation of R at any prime is less than l. Then
LLL-reduce A --> we get 'a' of small height in A. Then replace x by x / a^l.

[ LLL-reducing the logarithmic embedings of x modulo the logarithmic
embedings of the u^l, for some S-unit generators u (for some small set S of
finite places) was another idea, but it only marginally improves the situation
at this point ]

As a result rnfkummer should be a few orders of magnitude faster (esp. when
the class group of the base field is large) AND give usable results, i.e
relative equations that can actually be used.

To double check the results, I added a "lazy reduction" flag to rnfpolredabs
[analogous to the one already present in polredabs]. So

  rnfpolredabs(nf, x, 16)

use lazy reduction, without factoring the discriminant.


This is a huge and complicated patch [the resulting code is hopefully simpler
though], there are certainly a few remaining bugs such as:

On Fri, 2 Aug 2002, Igor Schein wrote:
> in latest CVS
>
> ? setrand(1);bnr=bnrinit(bnfinit(y^4-y^3-2404*y^2+2404*y+1154401),5,1);
> ? rnfkummer(bnr,matdiagonal([5,1]))
>   ***   not an Abelian extension in rnfnormgroup.

which Igor spotted before I could announce my changes ... and which I've
fixed in the meantime.

I ran preliminary regression tests without spotting further problems. Any
feedback will be much appreciated.

    Karim.

P.S: rnfkummer is still unable to handle extension of non-prime degree [this
is a "feature" of the method], as well as extensions of degree larger than 5
[this is pure laziness].
-- 
Karim Belabas                    Tel: (+33) (0)1 69 15 57 48
Dép. de Mathematiques, Bat. 425  Fax: (+33) (0)1 69 15 60 19
Université Paris-Sud             Email: Karim.Belabas@math.u-psud.fr
F-91405 Orsay (France)           http://www.math.u-psud.fr/~belabas/
--
PARI/GP Home Page: http://www.parigp-home.de/