Re: idealred in narrow sense

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

* Pierre.Charollois@math.u-bordeaux1.fr [2006-02-22 14:54]:
>  Dealing with an ideal J in the narrow sense,
>  I was trying to use  the "idealred" command to
>  find an equivalent ideal in HNF form having smaller coefficients.
> 
> 
>  Unfortunately, it seems that  "idealred" returns
>  an equivalent ideal that can be in another narrow class.
> 
>  For instance, if you pick J to be one generator of the narrow class group,
>  idealred sometimes returns the trivial matrix.
> 
> e.g.
> (09:20) gp > K=bnfinit(x^2-6);
> (09:20) gp > bnfnarrow(K)
> %8 = [2, [2], [[5, 1; 0, 1]]]
> (09:20) gp > idealred(K, %[3][1])
> %9 =
> [1 0]
> 
> [0 1]
> 
> How can I handle a proper narrow reduction  ?

This is not easy in GP (OTOH, it's used intensively in libpari). If this
is a critical computation which needs to be very efficient, have a look at
the P.S.

The simple-minded (but _very slow_) approach is to just use bnrinit and
compute in the ray class group. Here's an example, written "generically"

  (18:38) gp >  K = bnfinit(x^2 - 6);

  \\ technical data to compute in the narrow class group [ with generators ]
  (18:38) gp > bnr = bnrinit(K, [1, vector(K.r1, i, 1)], 1);

  \\ narrow class group, the principal ideal (\sqrt{6} - 1) is a generator
  (18:38) gp > bnr.clgp
  %1 = [2, [2], [[-1, 1]~]]

  (18:38) gp > bnrisprincipal(bnr, [5, 1; 0, 1])
  %2 = [[1]~, [7/5, 2/5]~]

Usually, one does not care about the specific generators and are happy with
formal computations in terms of an unspecified (but fixed) "basis" of the
ray class group :

  \\ without generators
  (18:38) gp > bnr = bnrinit(K, [1, vector(K.r1, i, 1)]);

  \\ this time the ,0 flag is required
  (18:38) gp > bnrisprincipal(bnr, [5, 1; 0, 1], 0)
  %4 = [1]~

This just says that [5,1;0,1] is equal to the chosen generator of the
narrow class group stored in the bnr structure. The initial computation
above says that this ideal is in fact the product of 

  ( 7/5 + 2/5 \sqrt{6}) ( \sqrt{6} - 1 ),

which _is_ a reduction... ( both terms are guaranteed to be small,
bounded in terms of f and K only ). In general you would have an
explicit principal ideal times as many ideals as there are generators
in the narrow class group (with exponents).

Note that the "generators" in a bnr are in not canonical, and will
vary from one invocation to the next [ use setrand(1) if this is a
problem ].

Hope this helps,

    K.B.

P.S: Some background:

1) reducing the ideal A in K means writing A = (x) B where B 
has small norm (effectively bounded in terms of K only), and 'x' is an
explicit element in K.

2) For efficient computations in ray class groups modulo f (e.g. for f = f_oo,
you get the narrow class group), one performs ordinary ideal reductions,
and accumulate the 'x' as above as a formal product. 

Then one reduces x in (Z_K/f)^*, i.e replace x by y = c * x where c = 1
mod^* f and y is small (effectivement bounded in terms of K and f).

[ The 'formal product' bit is crucial when you think about things like
2^10000000, which takes just 10 characters. When reducing modulo f, one
can reduce 10000000 modulo the exponent of (Z_K/f)^*, and we are left
with a much, much simpler computation. ]

3) Unfortunately idealred(K,A) only returns B: x is lost.

There _is_ a way to get 'x', but it involves either
* install-ing an undocumented routine (idealred_elt), or
* using an undocumented hack ( use [B, [;]] as input instead of B )

Since we don't want to use undocumented features, this road is not open to us.

4) Unfortunately the functions used to reduce modulo f
(e.g. nfreducemodidele) are not available in GP, nor documented.

>From the above you can guess that to do it properly you will have to use
libpari (and I will have to document a relatively large number of internal
routines).
-- 
Karim Belabas                  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]