Hay un procedimiento para determinar si un número dado es una raíz de la unidad?

Question

Deje $z$ ser una expresión algebraica número de módulo uno. Hay un número finito de procedimiento que nos dice si $z$ es una raíz de la unidad?

EDIT: Como TonyK y David le preguntó, a lo que yo tenía en mi mente es $z$ que tengo un polinomio $F \in \mathbf{Q}[x]$ tal que $F(z)=0$.

Answer 1

Voy a suponer que sabemos que algunos polinomio $F \in \mathbf{Q}[x]$ tal que $F(z)=0$. (Esto es de alguna manera la única razonable "certificado" para un número algebraico -- supongo que es posible que podamos tener un número finito de descripción de $z$ y un argumento que muestra $z$ es algebraicas sin llegar a producir un polinomio $F$, pero no puedo imaginar un caso en el que esto podría llegar en la práctica).

Comprueba en primer lugar si $F$ es irreductible-no son buenos algoritmos para esta basado en la liga de la leche de reducción. Si $F$ no es irreducible, factorise $F$, encontramos que el factor de ha $z$ como una raíz, y empezar de nuevo con este nuevo grado menor $F$. Si $F$ es irreductible, vamos a $N$ ser su grado; obviamente, hay sólo un número finito de enteros $M$ tal que $\phi(M) = N$ donde $\phi$ es de Euler del phi de la función, y sólo comprobar si $F$ coincide con el $M$-th cyclotomic polinomio para cualquier $M$ en este conjunto.

Answer 2

Como se discutió en otras respuestas, Deje $f(x)$ ser irreducible polinomio con coeficientes racionales que su número satisface. Normalizar $f$ a liderar a plazo $x^n$.

Son todos los coeficientes de $f$ enteros? Si no, no se trata de una cyclotomic polinomio. NO volver.

Supongamos que los coeficientes de $f$ son todos los números enteros. Por un teorema de Kronecker, $f$ es cyclotomic si y sólo si todas sus raíces se encuentran dentro del círculo unitario, si y sólo si todas las raíces se encuentran en el círculo unidad. (Recuerde que hemos normalizado $f$ a liderar el coeficiente de $1$, y todos los coeficientes de $f$ son números enteros.)

Vamos a comprobar si todas las raíces de $f$ están dentro del círculo unitario en el método 1, y si se encuentran en ella en el método 2.

Voy a romper ahora esta en lo que creo que es, probablemente, el método más eficaz en la práctica, y lo que es un método garantizado para darle la respuesta correcta.

Método 1: vamos a buscar numéricamente la mayor raíz de $f$. Deje $f(x) = x^n + f_{n-1} x^{n-1} + \cdots + f_0$. Deje $M$ ser la matriz $$\begin{pmatrix} & 1 & & & \\ & & 1 & & \\ & & & 1 & \\ & & & & \ddots \\ -f_0 & -f_1 & -f_2 & \cdots & -f_{n-1} \\ \end{pmatrix}.$$ Los autovalores de a $M$ son las raíces de $f$, y la mayoría de los sistemas de álgebra computacional se han optimizado las rutinas que encuentre el mayor valor propio de una matriz. No sé de un comando para "encontrar mí el más grande de la raíz de este polinomio" pero, si tu CAS tiene, obviamente, usted puede simplemente preguntar directamente para que.

Método 2 en Primer lugar, compruebe si $f(x) = x \pm 1$. Si es así, su número es raíz de la unidad, es decir,$\mp 1$. Voy a asumir que no estamos en este caso a partir de ahora.

Compruebe si su $f$ es capicúa y aún de grado. Con la excepción de $x \pm 1$, cada cyclotomic polinomio es, así que si tu $f$ no rechazar.

Si $f$ es capicúa de grado $2m$, escribir $f(x) = x^m g((x+x^{-1})/2)$, para un polinomio $g$ grado $m$. Tenga en cuenta que $g$ también ha racional de los coeficientes, y puede ser calculado exactamente.

Ahora, si $e^{i \theta}$ es una raíz de $f$, $\cos \theta$ es una raíz de $g$ y, por el contrario, si $\cos \theta$ es una raíz de $g$ $e^{\pm i \theta}$ es una raíz de $f$. Por lo $f$ $2m$ raíces en el círculo unitario si y sólo si $g$ $m$ raíces entre el$-1$$1$.

Sturm del método puede recuentos de las raíces de $g$$-1$$1$. El polinomio $f$ es cyclotomic si ha superado el procedimiento de pruebas y $g$ $m$ raíces en este intervalo.

Answer 3

Sí, ver las referencias a la más general de los algoritmos dado en mi respuesta a la pregunta ¿Cuándo un polinomio se divide $\rm\:x^k-1\:$ algunos $\rm\:k\:$?

Answer 4

Si su argumento es un racional múltiplo de 2$\pi$, entonces sí.

La solución de $e^{in\theta}=1$ da $\theta=2k\pi/n$$k\in\mathbb{Z^+}$, y un número con tal argumento es claramente una raíz de la unidad.