Dejemos que $f(x)$ sea un polinomio monico integral irreducible y $\alpha$ sea su raíz. ¿Cuál es la complejidad computacional de encontrar representantes de clases ideales del anillo integral $\mathbb{Q}[\alpha]$ ? ¿Cuál es un límite natural para los "tamaños" de los representantes en términos de los coeficientes de $f$ ? Como se explica en Las notas de Keith Conrad, esto está relacionado con el problema de conjugación de las matrices integrales.
Respuesta
¿Demasiados anuncios?
No soy un experto, pero esto es lo que aprendí de Lenstra Algoritmos en la teoría algebraica de los números (Bull AMS, 1992) y el documento de Kirschmer y Voight Enumeración algorítmica de clases ideales para órdenes de cuaterniones :
Para un campo numérico $F$ de grado $n$ y el discriminante absoluto $d_F$ parece que los mejores resultados generales sobre el cálculo del grupo de clase ideal provienen de los artículos de Buchmann de 1990 Un algoritmo subexponencial para la determinación de grupos de clase y reguladores de campos numéricos algebraicos y Complejidad de los algoritmos en la teoría algebraica de los números :
Se puede determinar el grupo de clases con un algoritmo determinista que se ejecuta en tiempo $d_F^{3/4}(2+\log d_F)^{O(n)}$ o en el tiempo de ejecución previsto $d_F^{1/2}(2+\log d_F)^{O(n)})$ con un algoritmo probabilístico. (En el marco de la GRH, se puede mejorar este último límite para un $n$ .)
Editar: Aurel señala en un comentario más abajo que una mejora de Schoof da un algoritmo determinista con tiempo de ejecución $d_F^{1/2}(2+\log d_F)^{O(n)})$ y heurísticamente debería ser computable en tiempo subexponencial (wrt $\log d_F$ ) tiempo.
Aunque esto no responde del todo a su pregunta, sugiere que un límite natural para el "tamaño" es el par del grado y el discriminante de $F=\mathbb Q(\alpha)$ . Su pregunta, por supuesto, implica órdenes más generales que el anillo completo de enteros de $F$ y no he pensado en los detalles, pero porque se puede reducir el cálculo del número de clase para $\mathbb Q[\alpha]$ a la de $F$ y el conductor de este suborden, esperaría que su problema fuera reducible al problema del grupo de clases para $F$ en el tiempo que es esencialmente el tamaño del anillo de enteros de $F$ modulo el tamaño de su suborden. (Esto parece similar a una reducción que hacen Kirschmer y Voight para los órdenes de Eichler en las álgebras de cuaterniones).
