Secuencias de diferencia absoluta de enteros

Question

Dada una secuencia arbitraria de enteros no negativos $x_0, \ldots, x_{n-1}$ , define su secuencia de diferencia como $x'_i = | x_i - x_{i+1} |$ , con índices mod $n$ (así $x_n = x_0$ ). La aplicación repetida de este proceso conduce a interesantes comportamiento. Por ejemplo, para $n=2^k$ parece que el proceso proceso siempre termina con la secuencia cero:

181,530,245,548,294,228,364,958
349,285,303,254,66,136,594,777
64,18,49,188,70,458,183,428
46,31,139,118,388,275,245,364
15,108,21,270,113,30,119,318
93,87,249,157,83,89,199,303
6,162,92,74,6,110,104,210
156,70,18,68,104,6,106,204
86,52,50,36,98,100,98,48
34,2,14,62,2,2,50,38
32,12,48,60,0,48,12,4
20,36,12,60,48,36,8,28
16,24,48,12,12,28,20,8
8,24,36,0,16,8,12,8
16,12,36,16,8,4,4,0
4,24,20,8,4,0,4,16
20,4,12,4,4,4,12,12
16,8,8,0,0,8,0,8
8,0,8,0,8,8,8,8
8,8,8,8,0,0,0,0
0,0,0,8,0,0,0,8
0,0,8,8,0,0,8,8
0,8,0,8,0,8,0,8
8,8,8,8,8,8,8,8
0,0,0,0,0,0,0,0

¿Es esto un teorema? Para $n$ no es una potencia de 2, cae en ciclos donde todos los elementos son 0 o $m$ para algún número entero $m$ (normalmente $m=1$ ).

¿Se han estudiado estas secuencias de diferencias? Parece que tienen una estructura rica.

Answer 1

Se llaman Secuencias de Ducci . La prueba de que terminan por $n = 2^k$ es bastante elemental: todo lo que hay que demostrar es que finalmente todos los términos son pares, y entonces se hace por inducción en la expansión binaria. Para demostrar que finalmente todos los términos son pares basta con trabajar $\bmod 2$ y entonces sólo estás mirando las potencias de la matriz $I + P$ en $\mathbb{F}_2$ , donde $P$ es una permutación cíclica. Tenemos $(I + P)^{2^k} \equiv I + P^{2^k} \bmod 2$ Así que cuando $n = 2^k$ tenemos la garantía de que después de un máximo de $n$ pasos todos los términos son parejos (y de lo contrario obtenemos el comportamiento que ya has descrito).