Robert Harron on Tue, 16 Aug 2016 21:56:39 +0200


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

Re: Making idealmoddivisor_aux public


Thank you for your insight. My goal had indeed been to implement these computations using the representation of pairs [I, t] you describe (and as suggested in Henri Cohen's book), but I hadn't figured out how to do that with the pari functions I could find. I'll take some time now to figure that out.

Best,

Rob

On 8/16/16 1:09 AM, Karim Belabas wrote:
* 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
modulus...

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.)

Cheers,

    K.B.
--
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]
`