En matemáticas , una palabra sturmiana ( secuencia de Sturmian o secuencia de billar [1] ), llamada así en honor a Jacques Charles François Sturm , es un cierto tipo de secuencia de caracteres infinitamente larga . Esta secuencia puede generarse considerando una partida de billar inglés sobre una mesa cuadrada. La bola golpeada golpeará sucesivamente los bordes vertical y horizontal etiquetados 0 y 1 generando una secuencia de letras. [2] Esta secuencia es una palabra sturmiana.
Las secuencias de Sturmian se pueden definir estrictamente en términos de sus propiedades combinatorias o geométricamente como secuencias de corte para líneas de pendiente irracional o codificaciones para rotaciones irracionales . Tradicionalmente se consideran secuencias infinitas en el alfabeto de los dos símbolos 0 y 1.
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 (factores) contiguas distintas en w de longitud n . Entonces w es sturmiano si σ ( n ) = n + 1 para todo n .
Un conjunto X de cadenas binarias se denomina equilibrado si el peso Hamming de los elementos de X toma como máximo dos valores distintos. Es decir, para cualquier | s | 1 = k o | s | 1 = k' donde | s | 1 es el número de unos en s .
Sea w una secuencia infinita de 0 y 1 y denotemos el conjunto de todas las subpalabras de longitud n de w . La sucesión w es sturmiana si está equilibrada para todo n y w no es eventualmente periódica.
Sea w una secuencia infinita de 0 y 1. La secuencia w es sturmiana si para algunos y algunos irracionales , w se realiza como la secuencia cortante de la línea .
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
para todos o
para todos .
Para , defina por . Para definir la codificación θ de x como la secuencia ( x n ) donde
Sea w una secuencia infinita de 0 y 1. La secuencia w es sturmiana si para algunos y algunos irracionales , w es la codificación θ de x .
Un ejemplo famoso de palabra sturmiana (estándar) es la palabra de Fibonacci ; [3] su pendiente es , donde está la proporción áurea .
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 Hamming de las palabras en S n toma como máximo dos valores distintos. Una secuencia equilibrada es aquella en 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 sólo si es equilibrada y aperiódica. [4] : 43
Una secuencia sobre {0,1} es una palabra de Sturm si y sólo si existen dos números reales , la pendiente y el intercepto , con irracionales , tales que
para todos . [5] : 284 [6] : 152 Así, una palabra sturmiana 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 número entero k tenemos
Todas las palabras sturmianas correspondientes a una misma vertiente 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 tanto, si , la palabra característica es la primera diferencia de la secuencia de Beatty correspondiente al número irracional .
La palabra estándar es también el límite de una secuencia de palabras definida recursivamente de la siguiente manera:
Sea la expansión fraccionaria continua de y defina
donde el producto entre palabras es solo su concatenación . Cada palabra de la secuencia es un prefijo de las siguientes, de modo que la secuencia misma converge en una palabra infinita, que es .
La secuencia infinita de palabras definida por la recursión anterior se llama secuencia estándar para la palabra estándar , y la secuencia infinita d = ( d 1 , d 2 , d 3 , ...) de enteros no negativos, con d 1 ≥ 0 y d n > 0 ( n ≥ 2), se llama su secuencia directiva .
Una palabra de Sturmian w sobre {0,1} es característica si y solo si tanto 0 w como 1 w son Sturmian. [7]
Si s es una palabra de secuencia infinita y w es una palabra finita, sea μ N ( w ) el número de apariciones de w como factor en el prefijo de s de longitud N + | w | − 1. Si μ N ( w ) tiene un límite como N →∞, lo llamamos frecuencia de w , denotada por μ ( w ). [4] : 73
Para una palabra sturmiana s , cada factor finito tiene una frecuencia. El teorema de los tres espacios 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
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 un 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
Un número real cuyos dígitos con respecto a alguna base fija forman una palabra sturmiana es un número trascendental . [6] : 64, 85
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]
Definir 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 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]
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 tales secuencias, [5] : 295 [14] en honor al matemático Jacques Charles François Sturm por la relación con el teorema de comparación de Sturm . [6] : 114