¿Son estas secuencias de señalización periódicas?

Question

Hace uno o dos años estuve trasteando con las secuencias y me topé con una familia de secuencias que parecen tener algunas propiedades interesantes. La familia, $\mathcal{S}$ se define como sigue:

$$ f\in\mathcal{S} \iff f : \mathbb{Z}\rightarrow\mathbb{N} \land \forall n\in\mathbb{Z}. f(n+1) = f(n-f(n)) $$

Es decir, si queremos encontrar el resultado de la secuencia en $n$ miramos el número anterior y retrocedemos tantos pasos, lo que hay es el valor en $n$ .

A continuación, un par de ejemplos de estas secuencias para que te hagas una idea:

$\dots 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 \dots$

$\dots 2,2,1,2,2,1,2,2,1,2,2,1,2,2,1,2,2,1 \dots$

$\dots 4,2,2,4,2,2,4,2,2,4,2,2,4,2,2,4,2,2 \dots$

Ahora hay un par de cosas simples que podemos probar rápidamente sobre estas secuencias.

• Si hay $n+1$ casos de $n$ en una fila la secuencia completa sólo debe ser $n$ .

• Si $m\leq n$ y hay un $m$ seguido de $n$ $n$ s en una fila entonces la secuencia debe ser esa y sólo esa repetida.

Todo esto es bastante fácil de mostrar, pero lo que he querido saber desde hace un año es cuán periódicas son estas secuencias. Hay dos conjeturas que tengo sobre estas secuencias, una débil que creo que es verdadera y otra fuerte que creo que es falsa.

Conjetura débil

Si una secuencia de la familia $\mathcal{S}$ está acotada entonces debe ser periódica.

Conjetura fuerte

Todas las secuencias de la familia $\mathcal{S}$ son periódicas.

---

Hasta ahora no he podido mostrar ninguna de las dos cosas. Empecé a construir una secuencia para refutar el segundo teorema, pero fue muy complicado. Empecé con una semilla llena de huecos. Fui añadiendo números a los huecos para intentar que siempre hubiera espacio para más huecos. Parecía que funcionaba, pero de vez en cuando me encontraba con un problema y tenía que volver atrás y cambiar una elección que había hecho. Nunca pude encontrar un método que garantizara la generación de una secuencia que obedeciera la regla.

Así que ahora que me he divertido quería ver si alguien más tenía alguna idea. ¿Puede alguien probar o refutar cualquiera de las conjeturas?

Answer 1

He aquí una prueba de la conjetura débil:

Supongamos que los términos de $f$ son todos estrictamente menores que $M$ . Entonces cada término de $f$ depende sólo de la anterior $M$ condiciones. Sólo hay $M^2$ posibilidades de la última $M$ términos, por lo que si escribimos cualquier $M^2 + M - 1$ términos consecutivos de $f$ debemos observar dos índices $n < n'$ tal que las subsecuencias $f(n), \dotsc, f(n+M-1)$ y $f(n'), \dotsc, f(n'+M-1)$ son idénticos. Esto implica que más allá del índice $n$ , $f$ es periódica con un período que divide a $n'-n$ . Ya que podemos empezar nuestro $M^2 + M - 1$ términos consecutivos arbitrariamente a la izquierda, $f$ debe ser periódica en todas partes.