palabra sturmiana

Una especie de secuencia infinitamente larga de personajes.

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

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.

Definición

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.

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 (factores) contiguas distintas 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 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 unos en s . ${\displaystyle s\in X}$

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. ${\displaystyle {\mathcal {L}}_{n}(w)}$ ${\displaystyle {\mathcal {L}}_{n}(w)}$

Definiciones geométricas

Secuencia de corte de irracional.

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 . ${\displaystyle x\in [0,1)}$ ${\displaystyle \theta \in (0,\infty )}$ ${\displaystyle f(t)=\theta t+x}$

Diferencia de 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 Sturmian generada por una rotación irracional con θ  ≈ 0,2882 y x  ≈ 0,0789

Para , defina por . Para definir 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 algunos y algunos irracionales , w es la codificación θ de  x . ${\displaystyle x\in [0,1)}$ ${\displaystyle \theta \in (0,\infty )}$

Discusión

Ejemplo

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

Secuencias aperiódicas equilibradas.

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}

Pendiente e intercepción

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 ${\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 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 ${\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 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 . ${\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 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 . ${\displaystyle (s_{n})_{n>0}}$ ${\displaystyle c_{\alpha }}$

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 ₁ , d ₂ , d ₃ , ...) de enteros no negativos, con d ₁ ≥ 0 y d _n > 0 ( n ≥ 2), se llama su secuencia directiva . ${\displaystyle (s_{n})_{n\geq 0}}$ ${\displaystyle c_{\alpha }}$

Una palabra de Sturmian w sobre {0,1} es característica si y solo si tanto 0 w como 1 w son Sturmian. ^[7]

Frecuencias

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}

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 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}

Números reales asociados

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}

Endomorfismos sturmianos

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]}

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 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}

Ver también

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

Referencias

1. Hordijk, A.; Laan, DA (2001). "Límites para secuencias de enrutamiento periódico deterministas". Programación entera y optimización combinatoria . Apuntes de conferencias sobre 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". Cartas de Procesamiento de Información . 54 (6): 307–312. doi :10.1016/0020-0190(95)00067-M.
4. Lothaire, M. (2002). "Palabras de Sturmian". Combinatoria algebraica de palabras . Cambridge: Prensa de la Universidad de Cambridge . ISBN 0-521-81220-8. Zbl  1001.68093 . Consultado el 25 de febrero de 2007 .
5. Allouche, Jean-Paul; Shalit, Jeffrey (2003). Secuencias automáticas: teoría, aplicaciones, generalizaciones . Prensa de la Universidad de Cambridge . 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). "Un comentario sobre las palabras mórficas de Sturmian". RAIRO, Informa. Teor. Aplica. 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 sturmianos", en Borzyszkowski, Andrzej M.; Sokołowski, Stefan (eds.), Mathematical Foundations of Computer Science 1993. XVIII Simposio internacional, MFCS'93 Gdańsk, Polonia, 30 de agosto a 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, Zbl  0925.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.

Otras lecturas

• Bugeaud, Yann (2012). Distribución módulo uno y aproximación diofántica . Tratados de Cambridge en Matemáticas. vol. 193. Cambridge: Prensa de la Universidad de Cambridge . ISBN 978-0-521-11169-0. Zbl  1260.11001.
• Lotario, M. (2011). Combinatoria algebraica sobre palabras . Enciclopedia de Matemáticas y sus aplicaciones. vol. 90. Con prefacio de Jean Berstel y Dominique Perrin (Reimpresión de la edición de tapa dura de 2002). Prensa de la Universidad de Cambridge . ISBN 978-0-521-18071-9. Zbl  1221.68183.