Can this way of comparing numbers of the form a+b sqrt(K) be generalized?

Question

So I want to make a system for computing with various classes of numbers. One of those is a class of number closed under the standard arithmetic operators ($+$, $-$, $*$ and $/$) along with square roots. This is pretty simple: I can extend any sufficiently nice ordered ring $R$ into $R[X]/(X^2-K)$. How to calculate the standard arithmetic operators on this ring is well-known, and I found a very elegant algorithm for computing the order:

Take $f(x) = x\cdot\!\!\left|x\right|$. Suppose you want to know if $a+b\sqrt{K}<c+d\sqrt{K}$. With simple algebra we can change this question to $a-c<(d-b)\sqrt{K}$. If we apply $f$, we get $f(a-c)<f(d-b)\cdot K$. This reduces the inequality in $R[X]/(X^2-K)$ to an inequality in $R$. Thus, if we take $R$ to be some ring that we already have an algorithm for computing $<$ (such as $\mathbb{Z}$), we have a way of computing $<$ in $R[X]/(X^2-K)$.

This is all well and good. However, this only gives us square roots, and I would like as powerful of a system as possible. Even cube roots seem impossible to work with. Initially, they might seem easy, but one has to remember that members of $R[X]/(X^3-K)$ are of the form $a+b\sqrt[3]{K}+c\sqrt[3]{K}^2$, not $a+b\sqrt[3]{K}$. Thus, the 'easiest' question is this: can this method be extended to work with $n$'th roots? A harder question lies in extending this method to deal with roots of polynomials that are not of the form $x^n-k$, such as the polynomial $x^5-x-1$ (thus letting me compute nicely with real algebraic numbers).

Answer 1

Yes, you can compute with roots of arbitrary polynomials in a real-closed field. The algorithms are nowhere near as simple to describe, but in one way or another they can be thought of as generalizing the trivial algorithms for computing in $R[\sqrt K]$. See e.g. Yap, Fundamental problems in algorithmic algebra (in particular §VII), or Basu, Pollack, Roy, Algorithms in Real Algebraic Geometry (§10).

Let me sketch some possibilities for the setup specifically mentioned in the question: we have a fixed ordered field $R$ where we know how to compute, an ordered algebraic extension $R[\alpha]$ of $R$, and we want to compute the ordering on elements of $R[\alpha]$; in other words, given a polynomial $f\in R[x]$, determine the sign of $f(\alpha)$.

First, there are several useful ways how to specify $\alpha$. One thing we want is an irreducible (or at least square-free) polynomial $g\in R[\alpha]$ such that $g(\alpha)=0$. Then we need something to uniquely determine $\alpha$ among the roots of $g$ in the real closure $\def\rcl#1{\tilde{#1}^\mathrm{real}}\rcl R$:

• The isolating interval representation consists of $u,v\in R\cup\{\pm\infty\}$ such that $\alpha$ is the unique root of $g$ in the interval $(u,v)$ of $\rcl R$. (Such an interval does not necessarily exist if $R$ is nonarchimedean.)

• The sign encoding consists of the sequence of signs of $g'(\alpha),g''(\alpha),\dots,g^{(d)}(\alpha)$, $d=\deg(g)$.

• Generalizing these two cases, we may be given a sequence of polynomials $h_1,\dots,h_k\in R[x]$ such that $\alpha$ is the unique root of $g$ in $\rcl R$ such that $h_1(\alpha),\dots,h_k(\alpha)>0$.

For example, for $\alpha=\sqrt[n]a$, we can take $g(x)=x^n-a$, and the isolating interval $(0,+\infty)$, or the sign encoding $(+,\dots,+)$, or $h_1(x)=x$.

Now, assume we want to determine the sign of $f(\alpha)$:

• If $\alpha$ is given by an isolating interval $(u,v)$, and $f$ is square-free (which we can arrange by first computing its square-free decomposition), we can compute the Sturm sequence $f_0=g$, $f_1=f$, $f_{i+1}=-(f_{i-1}\bmod f_i)$. Then the sign of $f(\alpha)$ is the sign of $(g(v)-g(u))(V(u)-V(v))$, where $V(u)$ is the number of sign changes (ignoring $0$) in the sequence $f_0(u),f_1(u),\dots$.

• If $\alpha$ is given by a sign encoding, or the more general representation with $h_1,\dots,h_k$: we run the BKR algorithm (see Yap, §VII.7–8) with $A=g$, $\overline B=[f,h_1,\dots,h_k]$. This will output all sequences of signs $[s,s_1,\dots,s_k]$ of $\overline B$ on the roots of $g$; one of them will be $[s,+,\dots,+]$, where $s$ is the sign of $f(\alpha)$.

Answer 2

Suppose $p$ is an irreducible polynomial over $\mathbb Z$, with real root $r$, and we wish to compare $f(r)$ to $g(r)$, where $f$ and $g$ are polynomials over $\mathbb Z$. Swapping terms with negative coefficients to the other side, we may assume all coefficients of $f$ and $g$ are nonnegative integers. Of course $f(r) = g(r)$ iff $f - g$ is divisible by $p$; let's suppose it isn't. If $s < r < t$ where $s$ and $t$ are rationals, then $f(r) \le f(t)$ and $g(s) \le g(r)$, so to prove $f(r) < g(r)$ (resp. $f(r) > g(r)$) it suffices to find rationals $s$ and $t$ such that $f(t) < g(s)$ (resp $f(s) > g(t)$), and if $s$ and $t$ are sufficiently close to $r$ one of these must be true. Suitable sequences $s_n$ and $t_n$ increasing and decreasing to $r$ can be found by successive bisection: given $s_n$ and $t_n$ with $r$ the only root of $p$ in the interval $(s_n, t_n)$, consider $x = (s_n + t_n)/2$, use Sturm's theorem to count the number of roots of $p$ in the interval $(s_n, x)$, and take either $s_{n+1} = x$ and $t_{n+1} = t_n$ or $s_{n+1} = s_n$ and $t_{n+1} = x$
according to whether this is $0$ or $1$.