26
$\begingroup$

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)

$\endgroup$
  • 1
    $\begingroup$ It's semicomputable; $\alpha$ can be computed to arbitrary precision using interval arithmetic and therefore so can arbitrary polynomials in $\alpha$. Exact equivalence can be tested using Gröbner bases, IIRC, so that doesn't throw a wrench in things. I suspect you may even be able to use results on approximability of algebraic numbers to prove full decidability. $\endgroup$ – Steven Stadnicki Feb 6 '18 at 2:47
  • 1
    $\begingroup$ That said, the problem is of unknown complexity even when you're talking about a tower of quadratics; have a look at cs.stackexchange.com/questions/84800/… and some of the references there. $\endgroup$ – Steven Stadnicki Feb 6 '18 at 2:49
  • $\begingroup$ @StevenStadnicki Ah, good point; exact equivalence is quite easy, so interval arithmetic suffices for decidability. I suppose my main interest is if, for a fixed polynomial $f$ or algebraic number $\alpha$, I can carry out this operation in a bounded number of operations. I'll add this to the question. (I guess this is orthogonal to the open problem you link to, since that's regarding algebraic numbers of ever increasing degrees) $\endgroup$ – Milo Brandt Feb 6 '18 at 2:55
  • $\begingroup$ I'd be amazed if it can be computed in a bounded number of operations regardless of the height of the coefficients; this would give a way of computing the algebraics to arbitrary precision very quickly. (Consider $A\alpha-B$ for huge $A$ and $B$). I would expect to need at least $O(\log H(P))$ operations (with $H()$ the height); this is commensurate with things like computing the GCD of two large numbers. $\endgroup$ – Steven Stadnicki Feb 6 '18 at 4:59
  • $\begingroup$ @StevenStadnicki Perhaps I'm misunderstanding, but I don't think the existence of such an algorithm would allow such computation any faster than bisection. In any case, for fixed $\alpha$ (which is what I'm asking about), there is an algorithm for deciding whether $A\alpha -B$ is positive (for $A>0$): Fix an interval $I$ with rational endpoints in which $\alpha$ lies. If $B/A$ isn't in this interval, we just check which side of $I$ it's on. Otherwise, we compute the minimal polynomial $f(B/A)$ - then $A\alpha - B>0$ if and only if the sign of this equals the sign of the upper endpoint of $I$ $\endgroup$ – Milo Brandt Feb 6 '18 at 18:36
4
+50
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ To clarify, for the definition of "dominate", one doesn't consider random points to be $0$-fold roots, right? (So $B$ can have whatever roots it wants as long as they are not just roots of $A$?). So, the answer I'm looking for would be $\mathrm{sign}(B(\gamma))=\mathrm{Var}_{A,B}[\alpha,\beta]\cdot \mathrm{sign}(A^{(1)}(\gamma))$. $\endgroup$ – Milo Brandt Feb 9 '18 at 20:35
  • $\begingroup$ @MiloBrandt: yes, only positive order zeroes of $A$ are considered in the definition. The magic of Sturm sequences is that the changes in the number of sign variations only depends on the behavior at roots of $A.$ $\endgroup$ – Dap Feb 10 '18 at 3:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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