Algorithm to determine sign of a polynomial - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-18T06:53:31Z http://mathoverflow.net/feeds/question/69805 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/69805/algorithm-to-determine-sign-of-a-polynomial Algorithm to determine sign of a polynomial Anthony Quas 2011-07-08T16:44:04Z 2011-07-08T18:08:06Z <p>I've been working with a collaborator (Arek Goetz) on a dynamics problem involving piecewise isometries (a map $T$ on a domain $X$ (say a subset of the plane) such that $X$ is divided into a finite number of polygonal regions and a separate isometry is applied to each).</p> <p>In the case where the defining isometries are all rotations through rational angles, it is often possible to use exact computer arithmetic to define points, lines, regions etc. in terms of integer linear combinations of roots of unity.</p> <p>The following algorithmic question then arises:</p> <blockquote> Let $(a_i)_{i=1}^n$ be a finite sequence of integers and $(p_i/K)_{i=1}^n$ be a sequence of rationals. Is there a <i>non-analytic</i> algorithm to decide the sign of $\sum a_i\sin(2\pi p_i/K)$? </blockquote> <p>More generally, given a real algebraic number $\zeta$, is there any nice way to decide the sign of an integer polynomial in $\zeta$ (I can do the quadratic case!)</p> http://mathoverflow.net/questions/69805/algorithm-to-determine-sign-of-a-polynomial/69812#69812 Answer by Igor Rivin for Algorithm to determine sign of a polynomial Igor Rivin 2011-07-08T18:08:06Z 2011-07-08T18:08:06Z <p>See</p> <p><a href="http://cgi.di.uoa.gr/~et/papers/et-computations-alg-numbers2.pdf" rel="nofollow">http://cgi.di.uoa.gr/~et/papers/et-computations-alg-numbers2.pdf</a></p> <p>particularly section 3.3</p>