Exact arithmetic for real algebraic numbers - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-26T09:03:01Z http://mathoverflow.net/feeds/question/116069 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/116069/exact-arithmetic-for-real-algebraic-numbers Exact arithmetic for real algebraic numbers Bruce Westbury 2012-12-11T10:56:41Z 2012-12-12T13:51:39Z <p>There was a reply to a question (that I can't find) which mentioned SARAG (Some Algorithms in Real Algebraic Geometry) see <a href="http://perso.univ-rennes1.fr/marie-francoise.roy/bpr-ed2-posted2.html" rel="nofollow">http://perso.univ-rennes1.fr/marie-francoise.roy/bpr-ed2-posted2.html</a>. This is a package for Maxima.</p> <p>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.</p> <p>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)?</p> <p>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.</p> <p>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.</p> http://mathoverflow.net/questions/116069/exact-arithmetic-for-real-algebraic-numbers/116077#116077 Answer by Dima Pasechnik for Exact arithmetic for real algebraic numbers Dima Pasechnik 2012-12-11T13:04:52Z 2012-12-12T13:51:39Z <p>In the <a href="http://perso.univ-rennes1.fr/marie-francoise.roy/bpr-ed2-posted2.html" rel="nofollow">reference</a> 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). </p> <p>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".</p> <p>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 <a href="http://perso.univ-rennes1.fr/marie-francoise.roy/bpr-ed2-posted2.html" rel="nofollow">reference</a>. </p> <p>Thom encodings really shine when one has a parametric (e.g. multivariate), or/and a non-Archimedean, setting. </p> <p>Computation with isolating intervals is implemented e.g. in <a href="http://sagemath.org/" rel="nofollow">Sage</a>.</p> <pre><code>sage: s=sqrt(AA(2)) sage: s.numerical_approx(prec=1000) 1.4142135623730950488016887242096980785696718753769480731766797379907324784... sage: s&gt;AA(0) True sage: t=s-sqrt(AA(3)) sage: t.minpoly() x^4 - 10*x^2 + 1 sage: t.sign() -1 </code></pre>