Subpalabras de la palabra Fibonacci

Question

En Palabra Fibonacci es el límite de la secuencia de palabras que empiezan por " $0$ " y el cumplimiento de las normas $0 \to 01, 1 \to 0$ . Es equivalente a tener condiciones iniciales $S_0 = 0, S_1 = 01$ y luego la recursión $S_n= S_{n-1}S_{n-2}$ .

Quiero saber qué palabras no pueden aparecer como subpalabras en el límite $S_\infty$ . Al principio pensé $000$ y $11$ fueron los dos únicos que no pudieron aparecer. Entonces me di cuenta de que $010101$ . ¿Existe alguna caracterización de las palabras que pueden o no aparecer como subpalabras de la palabra Fibonacci?

Relacionada vagamente, esta palabra aparece como la secuencia de corte de la línea de pendiente $\phi^{-1}$ a través del origen donde $\phi = \frac{1 + \sqrt{5}}{2}$ .

Answer 1

Ya hay algunas respuestas excelentes a esta pregunta, pero como podrá apreciar ahora la palabra Fibonacci está muy estructurada y tiene una diversidad de propiedades interesantes que restringen su clase de subpalabras. He observado que ninguna de las respuestas hasta ahora aborda directamente el hecho de que la palabra Fibonacci --como todas las palabras esturmianas-- es equilibrado . Decir que una palabra está equilibrada significa que para cualquier par de subpalabras de igual longitud, el número de ceros de cada subpalabra debe ser igual o diferir exactamente en uno. La palabra desequilibrada más sencilla es 0011, porque el número de ceros de las subpalabras 00 y 11 es dos y cero, respectivamente. Como sólo hay $O(n^3)$ palabras equilibradas de longitud $n$ esta propiedad restringe bastante el número de subpalabras permitidas.

Los ejemplos de palabras prohibidas que enumera (000, 11 y 010101) son palabras equilibradas, pero la regla del equilibrio impide que aparezcan en la palabra Fibonacci. Para ver esto podemos argumentar de la siguiente manera. Puesto que 101 aparece en la palabra Fibonacci, no puede contener 000, porque el número de ceros en estas dos subpalabras diferiría en dos. Del mismo modo, como contiene 00 no puede contener 11, y como contiene 00100 no puede contener 10101.

Si una palabra infinita está equilibrada, entonces la relación entre ceros y unos en sus subpalabras de longitud $n$ converge rápida y uniformemente a una relación constante en el límite como $n \to \infty$ . En el caso de la palabra Fibonacci, este límite es la proporción áurea. Desde una perspectiva dinámica, esta convergencia se debe a la ergodicidad única del sistema dinámico simbólico asociado, pero también tiene fuertes conexiones con las fracciones continuas: observará que las aproximaciones de las fracciones continuas a la proporción áurea surgen como relaciones de ceros a unos en ciertas subpalabras de la palabra Fibonacci. Los excelentes libros de Lothaire ( Combinatoria algebraica de palabras mencionado anteriormente) y por Fogg ( Sustituciones en dinámica, aritmética y combinatoria ) son buenas referencias para la palabra Fibonacci y para las palabras esturmianas y equilibradas en general.