Re: precision of result when adding t_REAL with lots of cancellation

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

* John Cremona [2014-02-14 09:29]:
> On 13 February 2014 22:15, Peter Bruin <P.Bruin@warwick.ac.uk> wrote:
> > I am not familiar enough with descent on elliptic curves to say if there
> > is any way to avoid such large number field elements (compared to the
> > apperently modest input size), or if one can somehow keep track of these
> > elements in a more compact factored form.  Maybe Denis can enlighten us?
> >
> 
> Bonjour.   The number field elements in question are representatives
> of a class in K^* / (K^*)^2 for some number field K.  I know that
> there are some very good tricks to obtain good representatives, asn
> have been assuming that Denis's code uses these, but it would be good
> to have that confirmed.  Otherwise, a reminder of the paper in which
> these tricks are described?

It may solve that instance, but we have a deeper problem. I believe we
are dealing with good representatives, in a wrong model. Namely, we have

  b = \prod_i y_i^e_i   in  K = Q[x] / (T)

where the y_i are fixed small S-units (for a small set S) and the e_i
are (possibly) *huge* integers. Working with b in factored form is
trivial, and libpari offers OK support for that; e.g in order to
compute signs of real embeddings, only (e_i mod 2) matters, and we are
back to the signs of the y_i  [ which can be precomputed ]. Same holds
for ideallogs, etc.

( One remaining problem in libpari is that the above in not quite true
for public functions: we express everything first in terms of
*fundamental units*, then S-units, which is a very bad ideal. An
experimental branch supports writing everything in terms of S-units,
which slows down simple examples, and speeds up immensely the
complicated ones. )

Working with b as an expanded t_POLMOD in Q[x] / (T)  or as a t_COL in
terms of K.zk [ better: no denominators... ] is unfortunate since the
above doesn't hold any longer: floating point embeddings become hard to
compute, etc.  Unfortunately, that's the documented way of working under GP.

In principle, one should be happy to stick to elements in factored form
defined implicitly via linear algebra in terms of small generators. But
the documented output of all GP routines are t_COLs in terms of K.zk
(which is often impossible to obtain in tough examples). I see no way of
changing this in a backward compatible way.

This requires adapting existing high level code as well. For instance, 
all routines whose input is a bnrinit(,,1), containing explicit expanded
generators [ which are mathematically unnecessary, although they make
implementations a little simpler ! ]

Also it's not so nice for users to no longer be able to check rigorously
whether two objects A = B (in different representations) are
mathematically equal. Indeed, writing A or B in normal form (as a
t_POLMOD or t_COL) is very hard, whereas testing whether A = B (mod whatever)
is fine.

Will be done, sometime. It's a lot of work ... (mostly adapting high
level routines + testing + documentation, though: the basic C code is 
already here).

Cheers,

    K.B.
--
Karim Belabas, IMB (UMR 5251)  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-bordeaux1.fr/~kbelabas/
F-33405 Talence (France)       http://pari.math.u-bordeaux1.fr/  [PARI/GP]
`