Descomposición de un número algebraico a la suma o producto de números algébricos con menor grado

Question

Un algebraica de números puede ser identificado por su polinomio mínimo , junto con el aislamiento de los intervalos de con racional de los límites de sus partes real e imaginaria. El grado de una expresión algebraica número es el grado de su polinomio mínimo. No se conocen algoritmos que permiten fácilmente calcular la suma y el producto de números algebraicos en esta representación, elevarlos a un racional de energía, extraer partes real e imaginaria, comparar o evaluar numéricamente a una precisión arbitraria.

Hay un eficiente algoritmo que dado un número algebraico $\alpha$ en esta representación puede decidir si $\alpha$ puede ser representada como una suma o producto de números algebraicos de menor grado?

Answer 1

Como en http://mathoverflow.net/a/26859/10423si su número de $x$ ($p(x)=0$) es una suma de dos números algebraicos $y, z$, e $[\mathbb{Q}(y): \mathbb{Q}]$ $[\mathbb{Q}(z): \mathbb{Q}]$ son relativamente primos, tendríamos $$ \mathbb{Q}(x) = \mathbb{Q}(y, z). $$ Para usar esto, podemos fijarnos para los subcampos $\mathbb{Q}(y) \subset \mathbb{Q}(x) $ generado por particular los elementos simples $y$ ($q(y)=0$). A continuación, $x$ satisfacen una ecuación polinómica $r(x)=0$ grado $\deg(x)/deg(y)$ cuyos coeficientes son los mismos polinomios en $y$.

Esto se puede hacer en sage. Definir el número de campo generadas por su número en el comentario:

t = var('t')
K.<x> = NumberField(t^6-12*t^5+54*t^4-116*t^3+132*t^2-120*t+92)

entonces el bucle a través de todos los subcampos $\mathbb{Q}(y)$ generado por sage K.optimized_subfields:

xValue = K.polynomial().real_roots()[0]
abstol, reltol = 1e-8, 1e-8
for K0 in K.optimized_subfields(0, name="y"):
    print "K0.<%s>:" % K0[0].gen(), K0[0].polynomial()
    L.<y,z> = K.relativize(K0[1])
    Lp.<w> = K0[0]["w"]
    # print "L: ", L
    Lrp = L.relative_polynomial();
    print "Lrp(x):", Lrp
    print "Lrp(w+z):", Lrp(w+z)
    if all([c.is_integer() for c in Lrp(w+z).coefficients()]):
        print "+++FOUND IT+++"
    print "Weight:", sum(c.global_height() for c in L.relative_polynomial().coefficients())
    # print "Heights:", (x.global_height(), y.global_height(), z.global_height())
    for emb in L.embeddings(ComplexField(200)):
        if abs(emb(y) - xValue) > abstol + reltol * abs(xValue): continue
        print "Embedding: %s: %s" % (z, emb(z))

Este código considera, a su vez, cada subcampo generado por $y$, e imprime los polinomios $q(y)\in\mathbb{Q}[y]$ y el polinomio $r(x)\in\mathbb{Q}(y)[x]$, la comprobación de si $r(x)$ puede ser escrito como un polinomio en $x-y=z$ con coeficientes enteros.

Hay 12 subcampos, cortar una parte de la salida, algunas de las $y$'s son muy simples:

K0.<y3>: t^2 - 2
Lrp(x): x^3 + (-3*y3 - 6)*x^2 + (12*y3 + 18)*x - 14*y3 - 22
Lrp(w+z): w^3 - 6*w^2 + 12*w - 10
+++FOUND IT+++
Weight: 5.49783963670066
Embedding: y3:
-1.4142135623730950488016887242096980785696718753769480731767

$$ x = -\sqrt{2} + \mathrm{Root}_w(w^3-6w^2+12w-10) $$

K0.<y12>: t^6 - 2
Lrp(x): x - y12^3 - y12^2 - 2
Lrp(w+z): w - y12^3 - y12^2 + y12 - 2
Weight: 0.753631429508173
Embedding: y12:
-1.1224620483093729814335330496791795162324111106139867534404

$$ x = -2-y^2-y^3, \qquad y = -2^{1/6} $$

One might also check for all simple linear expressions $x = z + \lambda y$ by expanding $r(z+\lambda y)$ and checking whether all coefficients of $x^{\geq0}y^{>0}$ can be set to $0$ by a particular choice of $\lambda\in\mathbb{Z}$.

In my testing, I used the root near $-72.5006$ of

333030430968457063019646779392 - 23571307899875281888190922752 * x + 11325756868205077014516072448 * x^2 + 2880637967760945947804168192 * x^3 + 782990884159596744735457280 * x^4 + 40070228472035777844367360 * x^5 + 10282486223601703758015488 * x^6 + 192715657601424647782400 * x^7 + 21281445409747778775040 * x^8 - 2726796545369319832704 * x^9 - 83259682551880061952 * x^10 + 4445241731011609472 * x^11 + 1435507363311897496 * x^12 + 355547636535862912 * x^13 + 37061676308129376 * x^14 + 2332115507866947 * x^15 + 238642514161488 * x^16 + 13466590646101 * x^17 + 1032053823392 * x^18 + 55985523438 * x^19 + 2712768664 * x^20 + 109992986 * x^21 + 2837824 * x^22 + 41695 * x^23 + 320 * x^24 * x^25

which is

$$ 7 \mathrm{Root}_{x\approx-1.214}(8 + 3 x^3 + x^5) + 8 \mathrm{Root}_{x\approx-8.000}(2 + 8 x^4 + x^5). $$

So it works for $\deg(x)=25$, pero en general es probablemente toma exponencial de tiempo o, peor aún, no polinomio. En el signo más (?) lado se generaliza el problema de mirar por la suma de (no productos) a la búsqueda de polinomio de relaciones con algebraica de coeficientes.

Answer 2

Un par de comentarios para empezar la discusión.

1. No creo que este problema de sumas es muy significativa. Cada elemento en ${\mathbb Q}(\sqrt{a},\sqrt{b})$ es una suma de tres elementos en buen subcampos, y un elemento en ${\mathbb Q}(\sqrt[4]{m})$ es una suma de elementos en buen subcampos si y sólo si es ya un elemento de ${\mathbb Q}(\sqrt{m})$, con la excepción de unos pocos casos donde la extensión pasa a ser bicíclico.

2. El problema es más interesante para los productos. Aquí la primera idea sería escribir el ideal $(\alpha)$ de los elementos de $\alpha$ como un producto de primer ideales y, a continuación, comprobar si este producto puede ser escrito como un producto de ideales de vida en subcampos. Si $(\alpha)$ es un producto de ideales de vida en subcampos, a continuación, varios de los principales ideales de la prueba se muestran si son un producto de los elementos de subcampos, hasta una unidad en el piso de arriba. Esto reduce el problema a la escritura de una unidad de un producto de unidades procedentes de los subcampos.

Mi conjetura es que el último problema de hecho puede ser resuelto de manera eficiente, buscando en todos los reales y complejos incrustaciones de las unidades en los subcampos.