Re: adding orders?

[Claus Fieker <fieker@mathematik.uni-kl.de>]

Dear All,

we have done this in Magma as there are many situations where this is
useful (it doesn't exist in Hecke (yet))
There are 2 different questions and solutions:
 - I have 2 orders and want the sum
 - I only have elements and want the smallest order
In the 1st case we tried to intersect the orders 1st, then construct
them over the intersection. Now, in most cases the indices are coprime
hence the addition is easy.

In the 2nd case, we ended up basically adding products until everything
stabilizes - a terrible method. So if you want a p-max function as well,
I'd do both interfaces...

Claus
On Mon, Jun 18, 2018 at 11:36:05AM +0200, Denis Simon wrote:
> Dear John, 
> 
> it seems that your second related request is done via nfbasis ([T,listP]). See the documentation of nfbasis. 
> 
> Denis SIMON. 
> 
> > De: "John Cremona" <john.cremona@gmail.com>
> > À: "Denis Simon" <denis.simon@unicaen.fr>
> > Cc: "Karim Belabas" <Karim.Belabas@math.u-bordeaux.fr>, "Aurel Page"
> > <aurel.page@normalesup.org>, "pari-users" <pari-users@pari.math.u-bordeaux.fr>
> > Envoyé: Lundi 18 Juin 2018 10:55:22
> > Objet: 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 < [ mailto:denis.simon@unicaen.fr |
> > denis.simon@unicaen.fr ] > wrote:
> 
> >> Hi,
> 
> >> I vote for nforder(T,arg) which seems good.
> 
> >> Denis SIMON.
> 
> >> ----- Mail original -----
> >>> De: "Karim Belabas" < [ mailto:Karim.Belabas@math.u-bordeaux.fr |
> >> > Karim.Belabas@math.u-bordeaux.fr ] >
> >>> À: "Aurel Page" < [ mailto:aurel.page@normalesup.org | aurel.page@normalesup.org
> >> > ] >
> >>> Cc: "pari-users" < [ mailto:pari-users@pari.math.u-bordeaux.fr |
> >> > 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/ |
> >> > http://www.math.u-bordeaux.fr/~kbelabas/ ]
> >>> F-33405 Talence (France) [ http://pari.math.u-bordeaux.fr/ |
> >> > http://pari.math.u-bordeaux.fr/ ] [PARI/GP]
> >> > `