John Cremona on Mon, 18 Jun 2018 10:55:55 +0200


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

Re: adding orders?


Interesting discussion -- thanks.  Karim is certainly right that this is useful when we do not (yet) have a maximal order.  It may be worth emphasising that this process is not just adding Z-modules (that's one difference between this and adding fractional ideals),  but it can be built out of a function for expanding a Z-submodule of full rank in a field (given just by a defining polynomial, and working with the power basis) by a single element:  to add the orders with Z-bases A=[a1,a2,...,an] and B=[b1,b2,...,bn] one starts with A as a Z-module and  repeatedly module-adds ai*bj until done;  most of these small additions will have no effect so the first thing to do in each step is to check whether the next ai*bj is in the module we have so far, which in turn involves a matrix*vector computation and checking whether the result is integral.  When it is not integral, the denominator tells you what index you are about to grow by.  It might be nice to keep these single growth indices in a list, not just as a product, so that by the time you have added the two orders you already know the discriminant of the result and the index of A in it in partially factored form.

A second related request is for a GP function to compute the p-maximal order of a given order and prime p.  The use case is for when again you do not know the maximal order and all the equations orders Z[a], Z[b], ... you have all have huge discriminant, but after doing some order additions you have an order Z[a,b] or Z[a,b,c] whise discriminant is easily factored.  One example of this is the Hecke field of the dimension 44 newform of weight 6, level 25, where disc(Z[a2,a3]) is easily factored while Z[a2] and Z[a3] have ~2000-digit coefficients.

John

On 18 June 2018 at 07:53, Denis Simon <denis.simon@unicaen.fr> wrote:
Hi,

I vote for nforder(T,arg) which seems good.

Denis SIMON.

----- Mail original -----
> De: "Karim Belabas" <Karim.Belabas@math.u-bordeaux.fr>
> À: "Aurel Page" <aurel.page@normalesup.org>
> Cc: "pari-users" <pari-users@pari.math.u-bordeaux.fr>
> Envoyé: Dimanche 17 Juin 2018 22:53:23
> Objet: Re: adding orders?

> Now that I think of it, my suggestion was stupid : we can't have an 'nf'
> as a first arguement since the function will be mostly used in case
> the maximal order is not computable.
>
> So the only sensible interface I can thing of is something like nforder(T, v)
> where  T is a monic polynomial in Z[X] and v is a vector of elements in
> Q[X] / (T)  [ t_INT or t_FRAC or t_POL or t_POLMOD mod T... ]
>
> It would return a matrix in HNF (say) for the order
> Z[v[1], ..., v[k]] in terms of the power basis of Z[X]/(T). [ With rational
> coefficients of course. ]
>
> But since it's indeed useful to adjoin elements to an existing order,
> we can allow square t_MAT as well as elements of v [ representing orders
> as per the previous convention...].
>
> It would be mostly useless in library mode (already exists and hardcoded
> in a few places), but it's nice to export it for GP use.
>
> Cheers,
>
>    K.B.
>
> * Aurel Page [2018-06-17 22:38]:
>> Hi,
>>
>> Why not a single argument, which can be a t_VEC for several elements? One
>> might want an order generated by more than two elements. Or 'a' itself can
>> be an order?
>> For the name, "nfordergenerated" would be accurate but a bit too long :-(
>>
>> Cheers,
>> Aurel
>>
>> On 17/06/18 22:31, Karim Belabas wrote:
>> > * Bill Allombert [2018-06-17 20:59]:
>> > > On Wed, Jun 13, 2018 at 02:41:46PM +0100, J E Cremona wrote:
>> > > > Is there a pari or gp function to add two orders in a number field?  Here
>> > > > of course I mean to return the smallest order containing both the summands,
>> > > > not just their sum as Z-modules, so the sum of Z[a] and Z[b] would Z[a,b].
>> > > I do not think this is readily available, though it is probably
>> > > done inside nfmaxord.
>> > > Do you have an algorithm for this task ?
>> > It's mostly available (internally). What would be a suitable name ?
>> > nforderadd ? (not too fond of that one...). Maybe, just nforder(nf, a, {b}) ?
>> > (cf idealhnf(nf, a, {b}).
> --
> Karim Belabas, IMB (UMR 5251)  Tel: (+33) (0)5 40 00 26 17
> Universite de Bordeaux         Fax: (+33) (0)5 40 00 21 23
> 351, cours de la Liberation    http://www.math.u-bordeaux.fr/~kbelabas/
> F-33405 Talence (France)       http://pari.math.u-bordeaux.fr/  [PARI/GP]
> `