8
$\begingroup$

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?

$\endgroup$
8
  • $\begingroup$ Observation: $\mathbb Q[\zeta_n]\cap\mathbb R=\mathbb Q[\zeta_n+\zeta_n^{-1}]$ is independent of the choice of the embedding. Positivity of an element still does, but perhaps working in a totally real field will help. $\endgroup$
    – Wojowu
    Jun 27, 2018 at 13:07
  • $\begingroup$ Do you want an algorithm that practically works, or do you insist on having an exact algorithm? $\endgroup$ Jun 27, 2018 at 17:05
  • $\begingroup$ The Mahler measure of the minimal polynomial gives you an effective lower bound for the absolute value of your number. Using this you know up to which precision to compute and you can do interval arithmetic. $\endgroup$ Jun 27, 2018 at 17:47
  • $\begingroup$ @FrançoisBrunault I'm interested in practical algorithms. Why do make the distinction between "pratical" and "exact" ? $\endgroup$ Jul 1, 2018 at 17:58
  • $\begingroup$ @Johannes Hahn By "practical" I meant for example the algorithm you mentioned in your post, that is computing an approximation without certifying the precision. By "exact" I mean providing a proof that the number is positive. This makes a difference, as shows the whole area of "interval arithmetic", the problems there can be very difficult although "practical" algorithms are easier and faster but not completely rigorous. $\endgroup$ Jul 1, 2018 at 21:58

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
9
  • 1
    $\begingroup$ This seems to be about checking whether $x$ is totally positive -- i.e. $\sigma(x) > 0$ for all embeddings $\sigma : \mathbb{Q}(\psi) \hookrightarrow \mathbb{R}$. The original question (from 4 years ago...) was about whether we can determine if $\sigma(x)$ is positive for one specific embedding $\sigma$, which is a different question. $\endgroup$ Sep 19, 2022 at 8:31
  • $\begingroup$ But real cyclotomic fields are totally positive, so there is no difference. Am I missing something? $\endgroup$ Sep 19, 2022 at 8:39
  • $\begingroup$ @DimaPasechnik E.g., $\zeta_5=\exp(2\pi i/5)$ and $\zeta_5^2$ are both primitive 5th roots of unity, but $\zeta_5+\zeta_5^{-1}>0>\zeta_5^2+\zeta_5^{-2}$. $\endgroup$ Sep 19, 2022 at 8:52
  • $\begingroup$ @EmilJeřábek $\zeta_5$ is not real, so I don't see what you say here. $\zeta_5^2+\zeta_5^{-2}$ is not in a sum of squares in the real cyclotomic field $\mathbb{Q}[\zeta_5+\zeta_5^{-1}]$. $\endgroup$ Sep 19, 2022 at 8:55
  • 1
    $\begingroup$ fixed; now it explains it's just Sturm sequences, more or less. $\endgroup$ Sep 20, 2022 at 16:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.