Palabra de Sturmian

Una especie de secuencia de caracteres infinitamente larga.

La palabra Fibonacci es un ejemplo de palabra Sturmiana. El comienzo de la secuencia de corte que se muestra aquí ilustra el comienzo de la palabra 0100101001.

En matemáticas , una palabra sturmiana ( secuencia sturmiana o secuencia de billar ^[1] ), llamada así por Jacques Charles François Sturm , es un cierto tipo de secuencia infinitamente larga de caracteres . Tal secuencia se puede generar considerando un juego de billar inglés en una mesa cuadrada. La bola golpeada golpeará sucesivamente los bordes verticales y horizontales etiquetados 0 y 1 generando una secuencia de letras. ^[2] Esta secuencia es una palabra sturmiana.

Definición

Las sucesiones de Sturm pueden definirse estrictamente en términos de sus propiedades combinatorias o geométricamente como sucesiones de corte para líneas de pendiente irracional o codificaciones para rotaciones irracionales . Tradicionalmente se las considera secuencias infinitas en el alfabeto de los dos símbolos 0 y 1.

Definiciones combinatorias

Secuencias de baja complejidad

Para una secuencia infinita de símbolos w , sea σ ( n ) la función de complejidad de w ; es decir, σ ( n ) = el número de subpalabras contiguas distintas (factores) en w de longitud n . Entonces w es Sturmiano si σ ( n ) =  n  + 1 para todo  n .

Secuencias equilibradas

Un conjunto X de cadenas binarias se denomina equilibrado si el peso de Hamming de los elementos de X toma como máximo dos valores distintos. Es decir, para cualquier | s | ₁  =  k o | s | ₁  =  k' donde | s | ₁ es el número de 1 en s . ${\displaystyle s\in X}$

Sea w una secuencia infinita de 0 y 1 y sea el conjunto de todas las subpalabras de longitud n de w . La secuencia w es sturmiana si está equilibrada para todos los n y w no es eventualmente periódica. ${\displaystyle {\mathcal {L}}_{n}(w)}$ ${\displaystyle {\mathcal {L}}_{n}(w)}$

Definiciones geométricas

Secuencia de corte de irracionales

Sea w una secuencia infinita de 0 y 1. La secuencia w es sturmiana si para algún y algún irracional , w se realiza como la secuencia de corte de la línea . ${\displaystyle x\in [0,1)}$ ${\displaystyle \theta \in (0,\infty )}$ ${\displaystyle f(t)=\theta t+x}$

Diferencias entre secuencias de Beatty

Sea w  = ( w _n ) una secuencia infinita de 0 y 1. La secuencia w es sturmiana si es la diferencia de secuencias de Beatty no homogéneas , es decir, para algunos y algunos irracionales . ${\displaystyle x\in [0,1)}$ ${\displaystyle \theta \in (0,1)}$

${\displaystyle w_{n}=\lfloor n\theta +x\rfloor -\lfloor (n-1)\theta +x\rfloor }$

para todos o ${\displaystyle n}$

${\displaystyle w_{n}=\lceil n\theta +x\rceil -\lceil (n-1)\theta +x\rceil }$

Para todos . ${\displaystyle n}$

Codificación de rotación irracional

Animación que muestra la secuencia de Sturm generada por una rotación irracional con θ  ≈ 0,2882 y x  ≈ 0,0789

Para , defina por . Para defina la codificación θ de x como la secuencia ( x _n ) donde ${\displaystyle \theta \in [0,1)}$ ${\displaystyle T_{\theta }:[0,1)\to [0,1)}$ ${\displaystyle t\mapsto t+\theta {\bmod {1}}}$ ${\displaystyle x\in [0,1)}$

${\displaystyle x_{n}={\begin{cases}1&{\text{if }}T_{\theta }^{n}(x)\in [0,\theta ),\\0&{\text{else}}.\end{cases}}}$

Sea w una secuencia infinita de 0 y 1. La secuencia w es sturmiana si para algún y algún irracional , w es la codificación  θ de x . ${\displaystyle x\in [0,1)}$ ${\displaystyle \theta \in (0,\infty )}$

Discusión

Ejemplo

Un ejemplo famoso de una palabra sturmiana (estándar) es la palabra Fibonacci ; ^[3] su pendiente es , donde es la proporción áurea . ${\displaystyle 1/\phi }$ ${\displaystyle \phi }$

Secuencias aperiódicas balanceadas

Un conjunto S de palabras binarias finitas está equilibrado si para cada n el subconjunto S _n de palabras de longitud n tiene la propiedad de que el peso de Hamming de las palabras en S _n toma como máximo dos valores distintos. Una secuencia equilibrada es aquella para la que el conjunto de factores está equilibrado. Una secuencia equilibrada tiene como máximo n + 1 factores distintos de longitud n . ^{[4] : 43} Una secuencia aperiódica es aquella que no consiste en una secuencia finita seguida de un ciclo finito. Una secuencia aperiódica tiene al menos n  + 1 factores distintos de longitud n . ^{[4] : 43} Una secuencia es sturmiana si y solo si es equilibrada y aperiódica. ^{[4] : 43}

Pendiente e intersección

Una secuencia sobre {0,1} es una palabra sturmiana si y solo si existen dos números reales , la pendiente y la intersección , con irracionales , tales que ${\displaystyle (a_{n})_{n\in \mathbb {N} }}$ ${\displaystyle \alpha }$ ${\displaystyle \rho }$ ${\displaystyle \alpha }$

${\displaystyle a_{n}=\lfloor \alpha (n+1)+\rho \rfloor -\lfloor \alpha n+\rho \rfloor -\lfloor \alpha \rfloor }$

para todo . ^{[5] : 284  [6] : 152} Por lo tanto, una palabra de Sturm proporciona una discretización de la línea recta con pendiente e intersección  ρ . Sin pérdida de generalidad, siempre podemos suponer , porque para cualquier entero k tenemos ${\displaystyle n}$ ${\displaystyle \alpha }$ ${\displaystyle 0<\alpha <1}$

${\displaystyle \lfloor (\alpha +k)(n+1)+\rho \rfloor -\lfloor (\alpha +k)n+\rho \rfloor -\lfloor \alpha +k\rfloor =a_{n}.}$

Todas las palabras de Sturm que corresponden a la misma pendiente tienen el mismo conjunto de factores; la palabra correspondiente a la intersección es la palabra estándar o palabra característica de pendiente . ^{[5] : 283} Por lo tanto, si , la palabra característica es la primera diferencia de la secuencia de Beatty correspondiente al número irracional . ${\displaystyle \alpha }$ ${\displaystyle c_{\alpha }}$ ${\displaystyle \rho =0}$ ${\displaystyle \alpha }$ ${\displaystyle 0<\alpha <1}$ ${\displaystyle c_{\alpha }}$ ${\displaystyle \alpha }$

La palabra estándar es también el límite de una secuencia de palabras definida recursivamente de la siguiente manera: ${\displaystyle c_{\alpha }}$ ${\displaystyle (s_{n})_{n\geq 0}}$

Sea la expansión fraccionaria continua de , y defina ${\displaystyle [0;d_{1}+1,d_{2},\ldots ,d_{n},\ldots ]}$ ${\displaystyle \alpha }$

• ${\displaystyle s_{0}=1}$
• ${\displaystyle s_{1}=0}$
• ${\displaystyle s_{n+1}=s_{n}^{d_{n}}s_{n-1}{\text{ for }}n>0}$

donde el producto entre palabras es simplemente su concatenación . Cada palabra de la secuencia es un prefijo de las siguientes, de modo que la secuencia misma converge a una palabra infinita, que es . ${\displaystyle (s_{n})_{n>0}}$ ${\displaystyle c_{\alpha }}$

La secuencia infinita de palabras definida por la recursión anterior se denomina secuencia estándar para la palabra estándar , y la secuencia infinita d = ( d ₁ , d ₂ , d ₃ , ...) de números enteros no negativos, con d ₁ ≥ 0 y d _n > 0 ( n ≥ 2), se denomina su secuencia directiva . ${\displaystyle (s_{n})_{n\geq 0}}$ ${\displaystyle c_{\alpha }}$

Una palabra sturmiana w sobre {0,1} es característica si y sólo si tanto 0 w como 1 w son sturmianos. ^[7]

Frecuencias

Si s es una palabra de secuencia infinita y w es una palabra finita, sea μ _N ( w ) el número de ocurrencias de w como un factor en el prefijo de s de longitud N  + | w | − 1. Si μ _N ( w ) tiene un límite cuando N →∞, llamamos a esto la frecuencia de w , denotada por μ ( w ). ^{[4] : 73}

Para una palabra de Sturm s , cada factor finito tiene una frecuencia. El teorema de los tres intervalos implica que los factores de longitud fija n tienen como máximo tres frecuencias distintas, y si hay tres valores, entonces uno es la suma de los otros dos. ^{[4] : 73}

Palabras no binarias

Para palabras sobre un alfabeto de tamaño k mayor que 2, definimos una palabra sturmiana como una con función de complejidad n  +  k  − 1. ^{[6] : 6} Se pueden describir en términos de secuencias de corte para el espacio k -dimensional. ^{[6] : 84} Una definición alternativa es como palabras de complejidad mínima sujetas a no ser en última instancia periódicas. ^{[6] : 85}

Números reales asociados

Un número real cuyos dígitos con respecto a una base fija forman una palabra sturmiana es un número trascendental . ^{[6] : 64, 85}

Endomorfismos de Sturm

Un endomorfismo del monoide libre B ^{∗ en un alfabeto} B de 2 letras es Sturmian si asigna cada palabra de Sturmian a una palabra de Sturmian ^{[8] [9]} y localmente Sturmian si asigna alguna palabra de Sturmian a una palabra de Sturmian. ^[10] Los endomorfismos de Sturm forman un submonoide del monoide de endomorfismos de B ^∗ . ^[8]

Definamos los endomorfismos φ y ψ de B ^∗ , donde B = {0,1}, por φ(0) = 01, φ(1) = 0 y ψ(0) = 10, ψ(1) = 0. Entonces I , φ y ψ son sturmianos, ^[11] y los endomorfismos sturmianos de B ^∗ son precisamente aquellos endomorfismos en el submonoide del monoide de endomorfismo generado por { I ,φ,ψ}. ^{[9] [10] [7]}

Un morfismo es sturmiano si y sólo si la imagen de la palabra 10010010100101 es una secuencia equilibrada ; es decir, para cada n , los pesos de Hamming de las subpalabras de longitud n toman como máximo dos valores distintos. ^{[9] [12]}

Historia

Aunque el estudio de las palabras Sturmianas se remonta a Johann III Bernoulli (1772), ^{[13] [5] : 295} fueron Gustav A. Hedlund y Marston Morse en 1940 quienes acuñaron el término Sturmiano para referirse a dichas sucesiones, ^{[5] : 295  [14]} en honor al matemático Jacques Charles François Sturm debido a la relación con el teorema de comparación de Sturm . ^{[6] : 114}

Véase también

• Secuencia de corte
• Palabra (teoría de grupos)
• Palabra mórfica
• Palabra de Lyndon

Referencias

1. Hordijk, A.; Laan, DA (2001). "Límites para secuencias de enrutamiento periódico determinista". Programación entera y optimización combinatoria . Apuntes de clase en informática. Vol. 2081. pág. 236. doi :10.1007/3-540-45535-3_19. ISBN 978-3-540-42225-9.
2. Győri, Ervin; Sós, Vera (2009). Tendencias recientes en combinatoria: el legado de Paul Erdős . Prensa de la Universidad de Cambridge. pag. 117.ISBN​ 978-0-521-12004-3.
3. de Luca, Aldo (1995). "Una propiedad de división de la palabra de Fibonacci". Information Processing Letters . 54 (6): 307–312. doi :10.1016/0020-0190(95)00067-M.
4. Lothaire, M. (2002). "Palabras de Sturm". Combinatoria algebraica sobre palabras . Cambridge: Cambridge University Press . ISBN 0-521-81220-8. Zbl  1001.68093 . Consultado el 25 de febrero de 2007 .
5. Allouche, Jean-Paul; Shallit, Jeffrey (2003). Secuencias automáticas: teoría, aplicaciones, generalizaciones . Cambridge University Press . ISBN 978-0-521-82332-6.Zbl 1086.11015  .
6. Pytheas Fogg, N. (2002). Berthé, Valérie ; Ferenczi, Sébastien; Mauduit, cristiano; Siegel, A. (eds.). Sustituciones en dinámica, aritmética y combinatoria . Apuntes de conferencias de matemáticas. vol. 1794. Berlín: Springer-Verlag . ISBN 3-540-44141-7.Zbl 1014.11015  .
7. Berstel, J.; Séébold, P. (1994). "Una observación sobre las palabras mórficas de Sturm". RAIRO, Inform. Théor. Appl. 2 . 8 (3–4): 255–263. doi : 10.1051/ita/1994283-402551 . ISSN  0988-3754. Zbl  0883.68104.
8. Lothaire (2011, pág. 83)
9. Pytheas Fogg (2002, pág. 197)
10. Lothaire (2011, pág. 85)
11. Lothaire (2011, pág. 84)
12. Berstel, Jean; Séébold, Patrice (1993), "Una caracterización de los morfismos de Sturm", en Borzyszkowski, Andrzej M.; Sokołowski, Stefan (eds.), Fundamentos matemáticos de la informática 1993. 18.º simposio internacional, MFCS'93 Gdansk, Polonia, 30 de agosto–3 de septiembre de 1993, Actas , Lecture Notes in Computer Science, vol. 711, págs. 281–290, doi :10.1007/3-540-57182-5_20, ISBN 978-3-540-57182-7, Zbl0925.11026 ​
13. J. Bernoulli III , Sur une nouvelle espece de calcul, Recueil pour les Astronomes, vol. 1, Berlín, 1772, págs. 255–284
14. Morse, M .; Hedlund, Georgia (1940). "Dinámica simbólica II. Trayectorias sturmianas". Revista Estadounidense de Matemáticas . 62 (1): 1–42. doi :10.2307/2371431. JSTOR  2371431.

Lectura adicional

• Bugeaud, Yann (2012). Distribución módulo uno y aproximación diofántica . Cambridge Tracts in Mathematics. Vol. 193. Cambridge: Cambridge University Press . ISBN. 978-0-521-11169-0.Zbl 1260.11001  .
• Lothaire, M. (2011). Combinatoria algebraica sobre palabras . Enciclopedia de matemáticas y sus aplicaciones. Vol. 90. Con prólogo de Jean Berstel y Dominique Perrin (reimpresión de la edición de tapa dura de 2002). Cambridge University Press . ISBN 978-0-521-18071-9.Zbl1221.68183  .​