Cómo determinar exactamente si una suma de raíz n-ésima de la unidad es cero

Question

Definir el conjunto $R = \{e^{2\pi i k/n} | k=0,1,\ldots,n-1\}$ $n$- th raíces de la unidad.

Deje $S \subseteq R$ ser un subconjunto. ¿Cómo puedo (a través de algoritmos?) determinar si $\sum_{s\in S} s = 0$?

Estoy buscando una manera general/algoritmo que puede ser implementado sin el uso de un CAS o, incluso, la aritmética de precisión arbitraria.

Si el modelo de los números complejos utilizando números de punto flotante, estamos muy rápidamente en un problema, como lo no-cero sumas que ser arbitrariamente cercano a cero $n$ se hace más grande. Por lo que si utilizamos floats o dobles que terminan haciendo que los errores debido a la precisión limitada. (Cuando se trabaja con números de punto flotante usted también puede comprobar realmente por la igualdad, debido al redondeo de las cifras, sólo se puede ver si algo está dentro de una distancia dada.)

Es allí una manera de hacer lo mismo con la aritmética de enteros? (Si es necesario, incluyendo arbitrariamente grande enteros son aceptables).

Answer 1

Podemos resolver el problema más general de decidir si, para los coeficientes de $a_k\in \mathbb Z$ la suma $$\sum_{k=0}^{n-1}a_k\zeta^k=0$$ donde $\zeta=e^{2\pi i/n}$. El problema restringe $a_k$$\{0,1\}$. En particular, podemos aplicar la siguiente instrucción (donde "polinomio" siempre se refiere a uno con coeficientes racionales):

Deje $z$ ser una expresión algebraica número y $Q$ ser el polinomio mínimo de a $z$. Si, por algún otro polinomio $P$,$P(z)=0$, $Q$ divide $P$.

El polinomio mínimo de a $\zeta$ $n^{th}$ cyclotomic polinomio, por lo que uno puede decidir si esta suma es cero por dividir el polinomio $P(x)=\sum_{k=0}^{n-1}a_kx^k$ $n^{th}$ cyclotomic polinomio (que puede ser calculado a través de diversos medios). Desde el cyclotomic polinomios son monic, aquí todo lo que puede ser calculada usando la aritmética de enteros.

Tenga en cuenta que cuando se $k$ es primo, vamos a encontrar que $R$ tiene suma cero, pero no es subconjunto de sí. No estoy seguro de si hay más reglas generales para su restringido problema, pero se puede investigar mediante el algoritmo y la teoría sugiere más arriba.