¿Números algébricos se puede comparar usando aritmética solamente racional?

Question

Yo estaba trabajando en un programa para llevar a cabo algunos cálculos, y se topó con un tema de la necesidad de comparar algunos de los números algebraicos, pero al no tener la precisión suficiente para hacerlo sin exacta de la aritmética, y no saber cómo hacerlo con exactitud aritmética.

Un poco de álgebra se muestra que la declaración de $$a+b\sqrt{n}>0$$ es equivalente a pedir que cualquiera de las $a^2>nb^2$ $a>0$ o $nb^2>a^2$$b>0$. En particular, esto significa que podemos fácilmente calcular el orden en $\mathbb Q(\sqrt{5})$ utilizando sólo racional aritmética de los coeficientes de los polinomios en la $\sqrt{5}$.

Sin embargo, no parece tan claro cómo generalizar este razonamiento, incluso para un ejemplo como decidir si $a+b\sqrt[3]{n}+c\sqrt[3]{n}^2$ es positivo.

En general, supongamos que $f$ es un polinomio irreducible en $\mathbb Q[x]$ y tiene alguna raíz real $\alpha$. Deje $F=\mathbb Q[x]/(f)\cong \mathbb Q(\alpha)$ la correspondiente extensión de campo. Este campo claramente se puede pedir, como es identificado con un subcampo de la $\mathbb R$.

Es posible calcular una orden explícita* $F$ utilizando sólo racional de la aritmética? Siento que esto debe ser posible, pero no puede averiguar cómo.

Estoy más interesado en si, para cada uno de los fijos de extensión de campo $F$, existe un algoritmo toma como entrada un polinomio en $\alpha$ de grado menor que $\deg f$ y decidir si es positivo o no, el uso de un acotado número de operaciones. Quiero principalmente para el campo de las extensiones de bajo grado, por lo que estoy menos interesado en la forma en la que crece la complejidad como $F$ se torna más compleja que en el modo en que los algoritmos adaptados a un solo $F$ de la tarifa.

(*Obviamente, estoy más interesado en ser capaz de calcular el orden en $\mathbb Q(\alpha)$ heredado de $\mathbb R$, pero dado que este campo es isomorfo a $\mathbb Q(\alpha')$ para cualquier otro raíz de $f$, probablemente hay varios pedidos - ninguna de las cuales sería interesante calcular)

Answer 1

Sí.

Para el acercamiento de la almádena, tenga en cuenta que el conjunto de $(c_0,\dots,c_{\deg(\alpha)-1})$ tal que $\sum_{n=0}^{\deg(\alpha)-1} c_n\alpha^n>0$ se puede definir en el lenguaje real de los campos cerrados, así que por el Tarski-Seidenberg teorema puede expresarse mediante el polinomio de desigualdades.

Esta es una especie de circular (o, al menos, una exageración), ya que la prueba de que el teorema se basa en la teoría de Sturm que ya le da un algoritmo más directamente utilizando el polinomio resto de las secuencias; más eficiente de los algoritmos de uso subresultants/Sturm-Habicht secuencias. Yap "Problemas Fundamentales en Algoritmos Álgebra", que pone de esta manera:

(Generalizada Sturm) Deje $A$ dominar $B$ y deje $α < β$, de modo que $A(α)A(β) \neq 0.$ $$\mathrm{Var}_{A,B}[α, β] = \sum_{γ,r,s}\mathrm{sign}(A^{(r)}(γ)B^{(s)}(γ))$$ donde $γ$ rangos de todas las raíces de $A$ $[α, β]$ de la multiplicidad $r ≥ 1$ $B$ tiene multiplicidad $s$ $γ,$ $r + s$ es impar.

Aquí $\mathrm{Var}$ es la diferencia en el número de variaciones de signo en un generalizado Sturm definir la secuencia de las $A$ $B$ cuando se evaluó en $\alpha$ $\beta,$ y "dominar" es un medio que si $\gamma$ $r$veces la raíz de $A,$ es en la mayoría de las $r$veces la raíz de $B.$

Mi $\gamma$ su $\alpha,$ lo siento. Tomando $A\in\mathbb Q[X]$ a, el polinomio mínimo de a $\gamma,$ y teniendo en $[\alpha,\beta]$ a un ser racional intervalo de aislar $\gamma$ como una raíz de $A,$, se puede determinar el signo de una combinación racional $B(\gamma)=\sum_{n=0}^{\deg(A)-1} c_n\gamma^n$ por la generalizada del teorema de Sturm con $r=1$ $s=0.$ $\mathrm{sign}(A^{(1)}(\gamma))$ puede ser horneados en el algoritmo.