Can algebraic numbers be compared using only rational arithmetic?

Question

I was working on a program to carry out some computations, and ran into an issue of needing to compare some algebraic numbers, but not having enough precision to do it without exact arithmetic, and not knowing how to do it with exact arithmetic.

A little algebra shows that the statement $$a+b\sqrt{n}>0$$ is equivalent to asking that either $a^2>nb^2$ and $a>0$ or $nb^2>a^2$ and $b>0$. In particular, this means that we can easily compute the order on $\mathbb Q(\sqrt{5})$ using only rational arithmetic on the coefficients of polynomials in $\sqrt{5}$.

However, it seems not so clear how to generalize this reasoning even to an example like deciding whether $a+b\sqrt[3]{n}+c\sqrt[3]{n}^2$ is positive.

In general, suppose that $f$ is an irreducible polynomial in $\mathbb Q[x]$ and has some real root $\alpha$. Let $F=\mathbb Q[x]/(f)\cong \mathbb Q(\alpha)$ be the corresponding field extension. This field clearly can be ordered, as it is identified with a subfield of $\mathbb R$.

Is it possible to compute an explicit order* on $F$ using only rational arithmetic? I feel that this must be possible, but can't figure out how.

I'm most interested in whether, for each fixed field extension $F$, there exists an algorithm taking as input a polynomial in $\alpha$ of degree less than $\deg f$ and deciding whether it is positive or not, using a bounded number of operations. I want this primarily for field extensions of low degree, so I'm less interested in how the complexity grows as $F$ becomes more complex than in how algorithms tailored to a single $F$ fare.

(*Obviously, I'm most interested in being able to compute the order on $\mathbb Q(\alpha)$ inherited from $\mathbb R$, but given that this field is isomorphic to $\mathbb Q(\alpha')$ for any other root of $f$, there are probably multiple orders - any of which would be interesting to compute)

Answer 1

Yes.

For the sledgehammer approach, note that the set of $(c_0,\dots,c_{\deg(\alpha)-1})$ such that $\sum_{n=0}^{\deg(\alpha)-1} c_n\alpha^n>0$ can be defined in the language of real-closed fields, so by the Tarski-Seidenberg theorem can be expressed by polynomial inequalities.

This is sort of circular (or at least overkill), since the proof of that theorem relies on Sturm theory which already gives such an algorithm more directly using polynomial remainder sequences; more efficient algorithms use subresultants/Sturm-Habicht sequences. Yap's "Fundamental Problems in Algorithmic Algebra" puts it this way:

(Generalized Sturm) Let $A$ dominate $B$ and let $α < β$ so that $A(α)A(β) \neq 0.$ Then $$\mathrm{Var}_{A,B}[α, β] = \sum_{γ,r,s}\mathrm{sign}(A^{(r)}(γ)B^{(s)}(γ))$$ where $γ$ ranges over all roots of $A$ in $[α, β]$ of multiplicity $r ≥ 1$ and $B$ has multiplicity $s$ at $γ,$ and $r + s$ is odd.

Here $\mathrm{Var}$ is the difference in the number of sign variations in a generalized Sturm sequence defined by $A$ and $B$ when evaluated at $\alpha$ and $\beta,$ and "dominate" is means that if $\gamma$ is an $r$-fold root of $A,$ it is at most an $r$-fold root of $B.$

My $\gamma$ will be your $\alpha,$ sorry. Taking $A\in\mathbb Q[X]$ to the minimal polynomial of $\gamma,$ and taking $[\alpha,\beta]$ to be a rational interval isolating $\gamma$ as a root of $A,$ we can determine the sign of a rational combination $B(\gamma)=\sum_{n=0}^{\deg(A)-1} c_n\gamma^n$ by the generalized Sturm theorem with $r=1$ and $s=0.$ The value of $\mathrm{sign}(A^{(1)}(\gamma))$ can be baked into the algorithm.

Answer 2

Just an observation, you may already know it:

If all the conjugates of the real algebraic number $\alpha$ are complex ( that is, $\alpha$ is the only real root of its minimal polynomial), then there exists a unique ordering on $\mathbb{Q}(\alpha)$. An element $\beta \in \mathbb{Q}(\alpha)$ is positive if and only if its norm $N(\beta)$ is positive. So for instance, to check whether $$-136 + 8 \sqrt[3]{7} + 33 \sqrt[3]{49}$$ calculate its norm, which equals $3025$. Therefore, the number is positive. To see that is is smaller than $1$, calculate $$N(1-(136 + 8 \sqrt[3]{7} + 33 \sqrt[3]{49}) ) = 47328$$

There is a theorem of Artin that says that an element of a number field is positive in all real embedding of the field if and only if the number is a sum of squares. In this case, there only one real embedding, so the positives are exactly the sum of squares, something that also follows from the norm being positive.