¿Por qué son los periodos de estas permutaciones menudo 1560?

Question

Corrí a través de un rompecabezas de la matemáticas, que fue así:

Considere la lista de $1,9,9,3, \cdots$ cuando la siguiente entrada es igual a la suma mod 10 de las anteriores 4. Así que la lista empieza $1,9,9,3,2,3,7,\cdots$. Será la secuencia de $7,3,6,7$ nunca se producen?

(Siéntase libre de hacer una pausa y resolver este problema para su propia diversión, si usted quiere. Spoiler de abajo.)

Así que la respuesta es "sí", y podemos resolver este al darse cuenta de que la función a derivar el siguiente dígito es invertible, entonces podemos derivar dígitos a la izquierda también. Ir a la izquierda, nos encontramos con $7,3,6,7$ bastante rapidez.

Escribí un programa y se encontró que el período (equivalente a la longitud de la permutación del ciclo) es de 1560. Pero, sorprendentemente (para mí) la alteración de la secuencia de arranque de 1,9,9,3 a la mayoría de cualquier otra secuencia a la izquierda el período en 1560. Hay un par de casos donde los cambios; por ejemplo, empezando con 4,4,4,4 tenemos un período de longitud sólo 312.

Por lo tanto, mi pregunta: ¿qué es especial acerca de 1560 aquí?

Nota: Esto se siente mucho como LFSRs, pero no sé mucho acerca de ellos.

Answer 1

Su recurrencia es lineal en el que se pueden agregar dos series plazo junto a término y aún así tener una serie. El período de (0,0,0,1) es 1560, por lo que todos los períodos será un divisor de ello. Para obtener 1560 sólo hay que evitar los ciclos más cortos.

Answer 2

Este es un lineal homogénea de la recurrencia de la relación con polinomio característico $p(x) = x^4 - x^3 - x^2 - x - 1$. Para calcular el período de $\bmod 10$ es suficiente para calcular su período de $\bmod 2, 5$ por el Teorema del Resto Chino.

Sobre cualquier campo, una recurrencia $a_n$ con polinomio característico $p(x)$ ha cerrado de forma

$$a_n = \sum c_i(n) r_i^n$$

donde $r_i$ es una raíz de $p$ $c_i(n)$ es un polinomio de grado a lo más uno menos que la multiplicidad de $r_i$ (con coeficientes en una división de campo de la $p$). Ahora $\bmod 2$ vemos que $p(x)$ no tiene raíces, por lo que es irreducible o el producto de dos irreductible cuadráticas. $\bmod 2$ el único irreductible cuadrática es $x^2 + x + 1$, que no dividen $p(x)$, lo $p(x)$ es irreductible $\bmod 2$. Se desprende de los hechos básicos sobre campos finitos que $p(x)$ divide $x^{2^4} - x$, por lo que las raíces de $p(x) \bmod 2$ $15^{th}$ raíces de la unidad y el período de $a_n \bmod 2$ divide $15$.

Del mismo modo, $\bmod 5$ vemos que $p(x)$ no tiene raíces, por lo que es irreducible o el producto de dos irreductible cuadráticas. Del estudio de antecentes reglas de esta última. De nuevo, se deduce que el $p(x)$ divide $x^{5^4} - x$, por lo que las raíces de $p(x) \bmod 5$ $624^{th}$ raíces de la unidad y el período de $a_n \bmod 5$ divide $624$.

Poner juntos vemos que el periodo de $a_n \bmod 10$ divide $\text{lcm}(15, 624) = 2 \cdot 1560$. El hecho de que a menudo se obtiene $1560$ significa que el período de $a_n \bmod 2$ a menudo es $5$ o $15$ y el período de $a_n \bmod 5$ a menudo es $312$ o $104$ (y al menos uno de estos es el de una divisible por $3$) lo que significa que las raíces de $p(x) \bmod 2, p(x) \bmod 5$ son generadores o cerca de los generadores de la multiplicación de los grupos de la división de los campos de $\mathbb{F}_{2^4}, \mathbb{F}_{5^4}$.