Deciding positivity of real cyclotomic numbers efficiently Consider a cyclotomic field $\mathbb{Q}[\zeta_n]$ for fixed $n$ and assume that an embedding $\mathbb{Q}[\zeta_n] \hookrightarrow \mathbb{C}$ has been chosen, say by fixing once and for all $\zeta_n=\exp(\frac{2\pi i}{n})$ as the primitive $n$-th root of unity.
Given $x\in\mathbb{Q}[\zeta_n]$ (as a polynomial in $\zeta_n$ with rational coefficients) of which I know that it is also a real number, it is well-defined to ask whther it is positive. It is easy to see that deciding positivity is possible by computing enough digits of a decimal approximation to $x$.
My question is:

Can we do better than that? Is there a more efficient algorithm to decide positivity?

 A: This is a particular case of a more general problem of deciding if a real algebraic number is positive. Or even of a more general problem, deciding if a semialgebraic set is non-empty. Let $\Psi_n(t)$ be  the minimal polynomial for $\psi:=\zeta_n+\zeta_n^{-1}$,
and $x$ given by $x(\psi)=\sum_{k=0}^N x_k\psi^k$.
Then deciding whether for fixed $a, b\in\mathbb{Q}$, where $(a,b)$ contains unique root of $\Psi_n$, i.e. our image of $\zeta_n+\zeta_n^{-1}$ in the embedding into $\mathbb{R}$,
$$
x(t)>0,\ \Psi_n(t)=0,\ a< t< b
$$
holds true may be done by one of exact procedures described in Algorithms in Real Algebraic Geometry
by Saugata Basu, Richard Pollack, Marie-Françoise Roy, Springer 2008, e.g. as an instance of an existential 1st order theory for $\mathbb{R}$. We would like to elaborate a bit on this here.
We can assume that $\deg x<\deg\Psi_n$, as we can reduce higher degree monomials of $x$ using $\Psi_n$.
You can think of $x$ as an element of the quotient ring $A:=\mathbb{Q}[\psi]/(\Psi_n)$.
As described in Sect. 4.6 of [loc.cit.], one can construct a matrix representation $L_x$ of $x$ in $A$, so that the eigenvalues of $L_x$ are the values of $x$ on the roots of $\Psi_n$.
If we were to check that $x$ is totally positive,
we would merely need to check that $L_x$ is positive definite, a task we can be done exactly, by computing certain (sub)determinants, or by certified numerical algebra (computing minimal eigenvalue with needed precision, with guaranteed error).
Here we'd need to solve a different problem, as we're only interested in one eigenvalue of $L_x$, the one in the interval $[a,b]$.
For this, one can use (suitably modified) Sturm sequences. As [loc.cit.] is hard to navigate, let me cut and paste from Sect. 1.2.1 of
excellently written notes by Michel Coste, "Introduction to semialgebraic geometry" (2002):

We want to count the number of real roots $c$ of $P$ such that $Q(c) > 0$. We
modify the construction of the Sturm sequence by taking $P_0 = P$, $P_1 = P'Q$,
and, as before, $P_{i+1} =$ the negative of the remainder of the euclidean division
of $P_{i−1}$ by $P_i$, for $i > 0$. We stop just before we obtain $0$, i.e. we stop with $P_K$
which is the $\mathrm{gcd}$ of $P$ and $P'Q$. The sequence of polynomials we obtain in this
way is called the Sturm sequence of $P$ and $P'Q$. If the real number $a$ is not
a root of $P$, we denote by $v_{P,Q}(a)$ the number of sign changes in the sequence
$P_0(a), P_1(a),...,P_K(a)$.
Theorem 1.5. Let $a<b$ be real numbers which are not roots of $P$. Then
$v_{P,Q}(a) − v_{P,Q}(b)$ is equal to the number of distinct roots $c$ of P in $(a, b)$ such
that $Q(c) > 0$ minus the number of those such that $Q(c) < 0$.

Note that $v_{P,Q}(t)$ for $t\in\mathbb{Q}$ is easy to compute, exactly, it's just evaluating univariate polynomials, obtained by exact division with reminder, with coefficients in $\mathbb{Q}$,  at  $t$.
We apply Theorem 1.5 above to $P=\Psi_n$, $Q=x$. As $\Psi_n$ has exactly one root $\psi$ on $(a,b)$, $v_{\Psi_n,x}(a) − v_{\Psi_n,x}(b)=1$ iff $x(\psi)>0$, and we are done.
