Exact arithmetic for real algebraic numbers

2012-12-11T10:56:41Z

There was a reply to a question (that I can't find) which mentioned SARAG (Some Algorithms in Real Algebraic Geometry) see http://perso.univ-rennes1.fr/marie-francoise.roy/bpr-ed2-posted2.html. This is a package for Maxima.

I looked into this and came across the Thom encoding of real algebraic numbers. If I have understood correctly, you are given a square-free polynomial with, say integer coefficients, and a real root. Then evaluate the derivatives of the polynomial at the root to get a sequence of signs. The polynomial together with the sign sequence is an encoding of the root.

My question is whether you can implement the operations of an ordered field on these encodings? The operation I not clear on is the ordering. A specific question is: given an encoding as above and a polynomial; evaluate the polynomial at the real number. Is there an algorithm for deciding if this is positive, negative, (or zero)?

I assume it is possible to evaluate this numerically using interval arithmetic and that if you did this with sufficient accuracy you would eventually arrive at a solution. However this seems clumsy and I am asking for something more effective.

As an illustration of why this could be useful. There was a question on the word problem in a Coxeter group (which again I could not find). One solution to the word problem is to look at the image of a fixed vector in the geometric representation. Then you can determine the descent set of a word by looking at which entries are negative. This is fine theoretically but not if you work with fixed precision real numbers as the entries will rapidly become very small in absolute value. A positive solution to my question would make this an effective algorithm.

Answer by Dima Pasechnik for Exact arithmetic for real algebraic numbers

2012-12-11T13:04:52Z

In the reference you posted there is a link to an online version of the monograph by S.Basu, M.-F.Roy, and R.Pollack, where algorithms like this are described (cf. Sect. 10.4, Algorithm 10.15).

The technique there is very general, and applies to non-Archimedean real closed fields, e.g. to fields of Puseaux series w.r.t. to an infinitesimal. There you don't have anything like "numeric evaluation".

Having said this, I wonder whether Thom encoding is really better for the range of problems like "straight" arbitrary precision computations with algebraic reals. For the latter, isolating roots by rational numbers works as well, and is faster, in theory, according to the reference.

Thom encodings really shine when one has a parametric (e.g. multivariate), or/and a non-Archimedean, setting.

Computation with isolating intervals is implemented e.g. in Sage.

sage: s=sqrt(AA(2))
sage: s.numerical_approx(prec=1000)
1.4142135623730950488016887242096980785696718753769480731766797379907324784...
sage: s>AA(0)
True
sage: t=s-sqrt(AA(3))
sage: t.minpoly()
x^4 - 10*x^2 + 1
sage: t.sign()
-1

Exact arithmetic for real algebraic numbers - MathOverflow

Exact arithmetic for real algebraic numbers

Answer by Dima Pasechnik for Exact arithmetic for real algebraic numbers