¿Hallar el período de una secuencia recursiva definida por el operador modular?

Question

Si $f(x)$ se define como :

$f(x)=i$ si $x\equiv i$ (mod n), $0\leq i< n$

¿Cómo puedo demostrar si las siguientes secuencias recursivas son periódicas o no?

$$x_{i+1}=f(k_0+k_1x_{i}+k_2x_{i-1}+...+k_{m+1}x_{i-m})$$

et $$x_i=1,0\leq i< m$$

Y por ejemplo, ¿cómo puedo encontrar el período de un caso especial:( $k_0=k_1=k_2=1$ )

$$x_{i+1}=f(1+x_{i}+x_{i-1}) $$ $$x_0=x_1=1$$

Answer 1

1)Todas las secuencias son periódicas a partir de cierto punto

Las primeras secuencias son periódicas después de un cierto número entero,y su período es menor que $$(m+1)^n $$ Para demostrarlo se puede considerar la secuencia $$y_k=(x_k,x_{k+1},\cdots,x_{k+m}) $$ y observe que si existen dos números enteros $i< N$ tal que $y_i=y_N$ entonces $x_i$ es periódico y su período es menor que $N$ la segunda observación es el hecho de que $y_k$ puede tomar sus valores en el conjunto $[0,n-1]^{m+1}$ que es finito y su cardinal es $(m+1)^{n}$ y esto significa que $N,i$ (en la primera observación) debe existir.

2)¿Son todas las secuencias completamente periódicas desde el primer punto ,

Esto equivale a preguntarse si existe un número entero tal que $N$ tal que: $$y_N=y_1 $$ Esto no es cierto en general, tomemos por ejemplo la secuencia (hay ejemplos más sencillos, pero este ejemplo muestra por qué podría ser así): $$n=4\quad f(n)= (n\mod 4)$$ y considerar la secuencia: $$x_{n+1}=f(4x_{n-4}) $$

3)estudio avanzado del problema

La secuencia como se ha dicho es muy conocida y su periodicidad está bien estudiada, ya que definiste la función $f$ sea la identidad en $K=\mathbb{Z}_n$ el conjunto de secuencias podría definirse en el anillo $\mathbb{Z}_n$ por : $$x_{i+1}=k_0+k_1x_{i}+k_2x_{i-1}+...+k_{m+1}x_{i-m}$$ y a partir de aquí, este tipo de secuencias se denomina : secuencias de recurrencia lineal cuando $K$ es un campo están relacionadas con las raíces de su polinomio correspondiente $P$ teniendo $k_i$ como coeficientes e incluso podemos encontrar una forma cerrada para la secuencia $a_k$ . En particular, cuando $K=\mathbb{Z}_n$ con $n$ es una potencia de un primo, conocemos un teorema debido a Peterson que relaciona el período de la sucesión con el número entero más pequeño $r$ tal que el polinomio correspondiente $P$ divide $x^r-1$ . Véase, por ejemplo, el documento SECUENCIAS LINEALES RECURRENTES SOBRE CAMPOS FINITOS para una revista.

La periodicidad se estudia en "PERIODICIDAD MODULAR DE SECUENCIAS DE RECURRENCIA LINEAL" en general, pero no hay resultados más potentes que los que demostramos en $(1)$

4) La segunda pregunta

Para la siguiente secuencia: $$x_{i+1}=1+x_i+x_{i-1} \quad \quad x_0=x_1=1$$ consideramos $y_i=(x_i+1)/2$ que tenemos: $$y_{i+1}=y_i+y_{i-1}\quad \quad y_0=y_1=1 $$ que es una sucesión de Fibonacci desplazada y su período se denomina $n$ th Época Pisano , escrito $\pi(n)$ y no conozco una forma cerrada para este número pero también está bien estudiado y se pueden demostrar muchas relaciones entre estos números.