Karim Belabas on Tue, 16 Aug 2016 13:09:33 +0200

[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Re: Making idealmoddivisor_aux public

* Robert Harron [2016-08-16 12:12]:
> Indeed, the implementation I've written so far in Sage uses the discrete
> logs of the elements for computations, and it is true that in terms of
> working with Hecke characters this, together with bnrisprincipal suffices.
> But the implementation I've written mimics the current implementation for
> the class group which keeps track of not only the discrete logs, but also
> representative ideals. And like in the class group code, upon multiplication
> an equivalent 'small' ideal representative is found.

Sure, you don't have coprimality or sign conditions there: you can get
away with "actually small" representatives (controlled by the field
discriminant). Now try Algorithm 4.3.4 with "nice" totally real fields
of degree 20 or so with [K:Q] sign conditions and a non-trivial

> So, while one can get away without reducing and still compute with
> Hecke characters, I still want to be able to provide the user with
> representatives of the ray classes.

What for ? My point is that those are going to be relatively costly,
and much larger than they need to be. I honestly have never seen any
actual use for them, and I've been implementing CFT-related algorithms
for some time now.

In practice, it is better to have

1) exact representations (in an efficient format such as my formal
products, aka compact representations) than trying to "reduce" modulo
complicated rules. Then you can map locally to wherever group you realy
need them at 0 cost, e.g. R^*/(R^*)^2 for signs, or
(Z_K/\mathfrak{p}^k)^* for CRT-based representation of (Z_K/f)^*.

2) local computations (think Chinese Remainder Theorem) rather than
global representatives. (As a bonus, it is technically simpler, and
you don't have to handle global obstructions.)

> We're you saying that idealmul and idealred themselves allow for finding
> small representatives of an ray class? I couldn't understand how to do that.

Not quite. To compute exactly with ideals in a way that can be
efficiently mapped to ray class groups, or other situations.

> Or wait, I see now that you mention a public function idealmoddivisor, but
> it looks like that function has disappeared from the documentation, maybe
> even from being publicly available.

It's still there, both in documentation and headers. But useless, as I
tried to explain :-)

> I found it in a google search in pari 2.5.

Try extended help:

(12:54) gp > ???idealmoddivisor@        \\ @ means: search in the whole manual

Chapter 6:
  Ideal reduction, high level

(That's 2.8.0, or 'master' GIT branch.)


Karim Belabas, IMB (UMR 5251)  Tel: (+33) (0)5 40 00 26 17
Universite de Bordeaux         Fax: (+33) (0)5 40 00 69 50
351, cours de la Liberation    http://www.math.u-bordeaux.fr/~kbelabas/
F-33405 Talence (France)       http://pari.math.u-bordeaux.fr/  [PARI/GP]