Voy a mostrar que los siguientes son equivalentes:
Definir v(t) = \sum_k v_k t^k. Voy a mostrar los siguientes son equivalentes.
(1) Una de las raíces de v(t) es una raíz de la unidad.
(2) Hay una solución distinto de cero w_k donde w_k permanecen acotados como k \a \pm \infty.
(3) No es una solución distinto de cero w_k donde todos los w_k están en \{ -1, 0, 1 \}.
Yo también muestran que los siguientes son equivalentes.
(4) Una de las raíces de v(t) es un 2^j-ésima raíz de la unidad, por unos j.
(5) El polinomio v(t) es divisible por 1-t o por 1+t^{2^{j-1}}, j.
(6) El polinomio v(t) es divisible por un polinomio de la forma 1-t^m o 1+t^m.
(7) es una solución de w_k donde todos los w_k \pm 1.
Obviamente, la parte inferior cuatro son más restrictivos que los tres primeros.
Para desprender los fáciles, claramente (7) \implica (3) \implica (2) y (4) \implica (1). También, (4) y (5) son fácilmente equivalente: yo soy solo el listado de cyclotomic polinomios de 2^j-th raíces de la unidad. Obviamente, (5) \implica (6). A la inversa implicación (6) \implica (5) es casi tan fácil: 1-t^n es divisible por 1-t, y, si n = 2^j (2k+1), entonces 1+t^{2^j} divide a 1+t^n.
También es fácil ver que (6) \implica (7): Si 1-t^n divide a v(t) tomar w_k con w_{k+n} = w_k; si 1+t^n divide a v(t) tomar w_k con w_k=-w_{k+n}.
El resto de argumentos, que será más difícil, mostrar (1) \Longleftrightarrow (2), (1) \implica (3) y (7) \implica (4).
En primer lugar, discutir la prueba de (1) \Longleftrightarrow (2), como se establece en el contexto de todas las demás:
Fijo v, la relación \sum_j v_{j} w_{k+j}=0 da una recurrencia lineal para el w_i. Las soluciones generales para esta recurrencia son de la forma
w_k = \sum p_i(k) \alpha_i^k \quad (\ast)
donde p_i son polinomios y el \alpha_i son las raíces de v(t^{-1}).
Supongamos que existe una limitada distinto de cero expresión de la forma (\ast). Ya que debe permanecer delimitada como k \to \infty y k \ - \infty, podemos deducir que todos los \alpha_i han norma 1. Pero el principio y el final de los coeficientes de v(t) es \pm 1 y todos los coeficientes de v(t) son números enteros, por lo que el \alpha_i son las raíces de la unidad (leer los comentarios en los enlaces de respuesta). Por el contrario, si \alpha es una raíz de la unidad y de la raíz de v(t^{-1}), entonces w_k = \alpha^{-k} es un almacén de solución a la recurrencia. Esto establece la equivalencia de los dos primeros puntos.
Ahora nos muestran (7) \implica (1). De nuestra discusión en (1) \Longleftrightarrow (2), cualquiera limitada solución debe ser de la forma
w_k = \sum c_r \alpha_r^k
por \alpha_r varias raíces de la unidad, que son los ceros de v(t).
Suponemos que todo el c_r son cero (de lo contrario, descartar la correspondiente \alpha_r de la lista).
Deja $$ N ser el MCM de los pedidos de los \alpha_r, entonces w_k periodo N.
Vamos a N=2^k (2m+1).
Supongamos, por el bien de la contradicción, de que ninguno de los \alpha_r \alpha_r^{2^k}=1.
Conjunto \beta_r=\alpha_r^{2^k}, entonces \beta_r es un (2m+1)-ésima raíz de la unidad que no es 1.
Note que \sum_{j=0}^{2m} w_{2^k j} es una suma de 2m+1 de números que son \pm 1, por lo que es distinto de cero.
Por otro lado,
\sum_{j=0}^{2m} w_{2^k j} = \sum_{j=0}^{2m} \sum_r c_r \sum_{j=0}^{2m} (\alpha_r^{2^k})^j = \sum_{j=0}^{2m} \sum_r c_r \beta_r^j = \sum_{j=0}^{2m} \sum_r c_r \frac{\beta_r^{2m+1}-1}{\beta_r-1} = 0
donde la última igualdad es porque \beta_r es un (2m+1)-ésima raíz de la unidad que no es 1.
La última, la más dura y, con el argumento de que (1) \implica (3). No es estrictamente necesario para responder a su pregunta, pero estoy orgulloso de ello.
Deje que \alpha, un primitivo $$n-ésima raíz de la unidad, la raíz de v(t^{-1}). Dado que los coeficientes de v(t) son números enteros, y el $$n-ésimo cyclotomic polinomio es irreducible, todos los de la primitiva n-ésimo raíces de la unidad son las raíces de $v(t)$. Vamos a encontrar una secuencia de $w_k$, de modo que la totalidad de los $w_k \en \{ -1, 0, 1 \}$ y $w_k$ puede ser escrito como
w_k = \sum_{i,\ GCD(r,n)=1} c_r \alpha^{rk} \quad (\daga)$$
para algunas constantes de c_r.
Definir el polinomio
f(t) = \prod_{p | n} (1-t^{n/p})
donde el producto es más números primos dividiendo n.
Lema Cada coeficiente de f es \pm 1, y todos los exponentes de f son distintos modulo n.
Prueba Dejar r ser el número de los distintos números primos dividiendo n. Pretendemos que todos los 2^n exponentes que ocurren en el producto son distintos modulo n. Supongamos que al contrario que P y Q son dos diferentes conjuntos de números primos dividiendo n que
\sum_{p \P} \frac{n}{p} \equiv \sum_{p \Q} \frac{n}{p} \bmod n. \quad (\mathbb{S})
Desde P \neq Q, podemos asumir que hay algo de p en P y no en Q (o viceversa). Deje que p^e se precisa de la energía de p dividiendo n. A continuación, la reducción de (\mathbb{S}) modulo p^e da
p^{e-1} + 0 + \cdots + 0 \equiv 0+ \cdots + 0 \bmod p^{e-1}
un absurdo. \square
Deje que g(t)=\sum_{k=0}^{n-1} g_k t^k ser el polinomio formado a partir de f(t) mediante la reducción de los exponentes de f(t) modulo n a estar entre 0 y n-1, mientras que el mantenimiento de los coeficientes de la misma. Deje de w_k ser la secuencia formada por la repetición de los coeficientes de g(t) periódicamente modulo n. Por lo que w_k \en \{ -1, 0, 1 \}, y debemos comprobar que w_k puede ser escrita en la forma (\daga).
Así tenemos
g_k = \sum_r c_r \alpha^{rk}
donde c_r está dada por la transformada de Fourier discreta
c_r = \frac{1}{n} \sum g_k \alpha^{rk}.
Si r NO es primo relativo a n, entonces \sum g_k \alpha^{rk} = g(\alpha^{-r}) = f(\alpha^{-r})=0. Así que el único distinto de cero los coeficientes de Fourier son los con MCD(r,n)=1, y w_k es de la forma (\daga), como se desee.
