5
$\begingroup$

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).

$\endgroup$
7
  • $\begingroup$ Also, in case what 'sufficiently nice' means becomes relevant, I can guarantee that any ordered ring that is a subring of an archimedean field is sufficiently nice, and I do not for now need anything more general than that. $\endgroup$
    – tailcalled
    Oct 28, 2014 at 19:59
  • 1
    $\begingroup$ In the second paragraph, I explained a way to compare elements in $R[X]/(X^2-K)$ (when you already have a method of comparing elements in $R$). That is the method I was talking about when I wrote 'this method'. $\endgroup$
    – tailcalled
    Oct 28, 2014 at 20:01
  • 1
    $\begingroup$ I asked essentially the same question some time ago: mathoverflow.net/questions/69805/… You may find some useful information in Igor Rivin's answer to that also. $\endgroup$ Oct 28, 2014 at 22:39
  • 1
    $\begingroup$ Sidenote: You don't want $R[X]/(X^2-K)$, because in this ring there is no preferred choice of a square root of $K$. You want a ring that has such a preferred square root, i.e. the positive one. Thus this isn't really about rings and ring extensions, it is about totally ordered rings and extensions of totally ordered rings. $\endgroup$ Oct 28, 2014 at 23:44
  • 1
    $\begingroup$ Do you need to deal with ${\bf R}[X]/(X^2+1)$? and if so, how do you do it? $\endgroup$ Oct 29, 2014 at 0:13

2 Answers 2

2
$\begingroup$

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)$.

$\endgroup$
3
  • $\begingroup$ Do these algorithms include determining positivity/negativity? $\endgroup$ Oct 29, 2014 at 0:15
  • $\begingroup$ Yes, sure. xxxxxxxxxxxx $\endgroup$ Oct 29, 2014 at 10:25
  • $\begingroup$ I'll look into those documents. How about simply computing in $R[\sqrt[n]{K}]$? $\endgroup$
    – tailcalled
    Oct 29, 2014 at 11:56
0
$\begingroup$

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$.

$\endgroup$

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.