6
$\begingroup$

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.

Improve this question
$\endgroup$
9
  • $\begingroup$ What is SARAG? In about the context of the question I know SALSA, which also got mentioned on MO. Also, it is not clear to me from your question whether you want/need this specific presentation or actually just want some way to exactly compute with such numbers. Could you please clarify? There are several ways know how to compute exactly with algebraic numbers (real or otherwise). $\endgroup$
    – user9072
    Commented Dec 11, 2012 at 12:21
  • $\begingroup$ I had not heard of SALSA. Is this what you mean inria.fr/en/teams/salsa $\endgroup$
    – Bruce Westbury
    Commented Dec 11, 2012 at 12:27
  • $\begingroup$ The only methods I know for working exactly with algebraic numbers are derived from Grobner bases. $\endgroup$
    – Bruce Westbury
    Commented Dec 11, 2012 at 12:29
  • $\begingroup$ My question is mainly about deciding if a real algebraic number is positive or negative. This question does not make sense unless you know the number is real. $\endgroup$
    – Bruce Westbury
    Commented Dec 11, 2012 at 12:30
  • $\begingroup$ Yes, it is. Sorry if the quess was of, I thought for example due to this paper metioning Thom encoding and salsa hal.archives-ouvertes.fr/docs/00/36/28/70/PDF/… that you might just have mixed up an acronym. $\endgroup$
    – user9072
    Commented Dec 11, 2012 at 12:34

1 Answer 1

Reset to default
6
$\begingroup$

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
Improve this answer
$\endgroup$
5
  • $\begingroup$ Thanks. It will take me a while to understand this but it does seem to be very close to what I am looking for. $\endgroup$
    – Bruce Westbury
    Commented Dec 11, 2012 at 18:12
  • $\begingroup$ In fact, my pet project is to implement Thom encodings in Sage (a system some people in your department have quite a bit of experience with). $\endgroup$
    – Dima Pasechnik
    Commented Dec 12, 2012 at 6:50
  • $\begingroup$ Yes, I use Sage. I was wondering about that. I did find that root isolation (over the real numbers) has been implemented in Sage. $\endgroup$
    – Bruce Westbury
    Commented Dec 12, 2012 at 9:30
  • $\begingroup$ In Sage there is an implementation of the field of algebraic numbers as arbitrary precision numbers. E.g. sage: s=sqrt(AA(2)) sage: s.numerical_approx(prec=1000) 1.41421356237309504880168872420969807856967187537694807317667973799073247846210703885038753432764157273501384623091229702492483605585073721264412149709993583141322266592750559275579995050115278206057147010955997160597027453459686201472851741864088919860955232923048430871432145083976260362799525140799 Would it suffice for you? $\endgroup$
    – Dima Pasechnik
    Commented Dec 12, 2012 at 12:58
  • $\begingroup$ I would like to understand Chapter 10 before I comment on applications. Do you want to discuss your pet project offline? $\endgroup$
    – Bruce Westbury
    Commented Dec 12, 2012 at 14:01

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .