2 added 153 characters in body

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.

1

# Exact arithmetic for real algebraic numbers

There was a reply to a question (that I can't find) which mentioned SARAG. 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.