Karim BELABAS on Thu, 28 Sep 2000 14:12:01 +0200 (MET DST)

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

Re: >0 ?

[Keith Briggs:]
> Is there a function or algorithm in pari which will decide
> if a given element x of a number field (expressed on an integral
> basis) is positive, without doing any floating-point arithmetic?

1) if r_1 = 1, you can compute Norm(x)  [ sign(norm(nfbasistoalg(nf,x))) ]
(this remains a cheap test even when r_1 > 1)

2) you can compute the minimal polynomial of x

[ y = charpoly(nfbasistoalg(nf,x)); pol = y / gcd(y,y') ]

then use polsturm(pol, 0) == poldegree(pol) to check the number of positive
real roots [ there are more efficient algorithms for real roots than Sturm's
(e.g Uspensky's), but they are not implemented in the distributed version yet ]

3) You could also get a guaranteed answer by computing the roots of pol. This
uses floating point arithmetic but produces a proven output (i.e if you ask
for 100 exact decimals, you obtain them), so given an initial approximation
of the roots, you can obtain a proof that they are indeed of the expected

Of course, multiplying by nf[5][1] is the fastest way (which is used in the
PARI code) but it neither avoids floating point arithmetic, nor provides a
guaranteed output.

Hope this helps,

Karim Belabas                    email: Karim.Belabas@math.u-psud.fr
Dep. de Mathematiques, Bat. 425
Universite Paris-Sud             Tel: (00 33) 1 69 15 57 48
F-91405 Orsay (France)           Fax: (00 33) 1 69 15 60 19
PARI/GP Home Page: http://www.parigp-home.de/