Balanced rectangles over Sturmian words and minimal discrepancy intervals

Resumen Técnico: Rectángulos Balanceados sobre Palabras de Sturmian y Intervalos de Discrepancia Mínima

1. Planteamiento del Problema

El artículo aborda el problema de la balanceidad (balancedness) en matrices rectangulares derivadas de palabras de Sturmian.

• Contexto: Una palabra de Sturmian $a$ con pendiente irracional $\alpha \in (0, 1)$ y intercepto $\theta$ se define mediante $a_n = \lfloor (n+1)\alpha + \theta \rfloor - \lfloor n\alpha + \theta \rfloor$. Estas palabras son conocidas por ser "balanceadas" en una dimensión (la diferencia en el peso de dos factores de la misma longitud es a lo sumo 1).
• Generalización Multidimensional: Se considera la matriz de Hankel infinita $A$ asociada a la palabra, donde $A_{k,\ell} = a_{k+\ell}$. El problema consiste en determinar cuándo los subrectángulos $m \times n$ de esta matriz son balanceados.
• Definición de Balanceidad para Rectángulos: Un rectángulo $m \times n$ es balanceado si existe un entero $c$ tal que la suma de todos sus elementos (el peso total) toma únicamente los valores $c$ o $c+1$, independientemente de la posición inicial del rectángulo en la matriz.
• Estado del Arte: Resultados previos (Anselmo et al., Shallit y la autora) habían caracterizado este fenómeno solo para pendientes $\alpha$ que son irracionales cuadráticos (usando representaciones de Zeckendorf y el software Walnut). El objetivo de este trabajo es resolver el problema para cualquier número irracional $\alpha$.

2. Metodología

La autora emplea una combinación de teoría de números, aproximación diofántica y teoría de la discrepancia. La estrategia se divide en los siguientes pasos lógicos:

1. Reducción a Intervalos Balanceados:

   • Se demuestra que la balanceidad de los rectángulos $m \times n$ es equivalente a la balanceidad de intervalos de longitud $\delta = \{n\alpha\}$ (parte fraccionaria) con respecto a la secuencia de puntos $\{0, \alpha, 2\alpha, \dots, (m-1)\alpha\}$ módulo 1.
   • Esto conecta el problema combinatorio de palabras con la teoría de la discrepancia de la secuencia $(n\alpha)_{n \ge 0}$.

2. Caracterización mediante Biyectividad:

   • Se introduce un enfoque geométrico en el toro $\mathbb{T} = \mathbb{R}/\mathbb{Z}$. La balanceidad de los intervalos se reduce a la biyectividad de ciertas funciones ($f_{left}$ y $f_{right}$) que mapean índices de puntos a sus vecinos más cercanos a la izquierda o derecha de un intervalo desplazado.
   • Si estas funciones son biyectivas, el sistema es balanceado; de lo contrario, no lo es.

3. Uso de Representaciones de Ostrowski:

   • Para analizar la posición de los puntos $\{k\alpha\}$ y las distancias mínimas, el autor utiliza la representación de Ostrowski de los enteros $m$ y $n$ con respecto a $\alpha$.
   • Dado que $\alpha = [0; a_1, a_2, \dots]$, cualquier entero $n$ tiene una representación única $n = \sum b_k q_k$, donde $q_k$ son los denominadores de las convergencias de $\alpha$.
   • Se analizan las propiedades de las aproximaciones diofánticas (convergencias y semi-convergencias) para determinar cuándo los valores $\{x\alpha\}$ minimizan la distancia a un punto de referencia en rangos específicos.

4. Análisis de Casos:

   • Se estudian casos separados dependiendo de si $n$ minimiza la distancia en el rango de interés (caso "trivial") o si el mínimo se alcanza en un entero diferente ($bx^* \neq n$).
   • Se utilizan lemas técnicos sobre la paridad de los índices de los primeros dígitos no nulos en las representaciones de Ostrowski para determinar la estructura de los conjuntos de puntos.

3. Contribuciones Clave y Resultados Principales

El resultado central es el Teorema 2.1, que proporciona una caracterización completa y necesaria de cuándo los rectángulos $m \times n$ son balanceados para cualquier $\alpha$ irracional. La condición se expresa en términos de las representaciones de Ostrowski de $m$ y $n$.

Suponiendo $2 \le m \le n$, los rectángulos son balanceados si y solo si las representaciones de $m$ y $n$ cumplen al menos una de las siguientes cuatro formas estructurales:

1. Representaciones "Divididas" (Split):

   • $m$ utiliza dígitos de índices bajos y $n$ utiliza dígitos de índices altos, sin superposición en los índices de las potencias de $q_k$.
   • Ejemplo: $m = \sum_{k=0}^M b_k q_k$ y $n = \sum_{k=M+1}^N b_k q_k$.

2. Caso de Separación con Salto Par:

   • $m$ tiene dígitos bajos, y $n$ comienza con una potencia específica $q_M$ seguida de dígitos con un salto de índice par ($2t$).
   • Ejemplo: $n = q_M + \sum_{k=M+1+2t}^N b_k q_k$.

3. $m$ como Denominador de Convergencia ($q_M$):

   • $m = q_M$ (un denominador de convergencia).
   • $n$ tiene una estructura específica que combina una parte baja y una parte alta con restricciones de paridad en los índices de los dígitos grandes.

4. $m$ como Denominador de Semi-Convergencia:

   • $m = q_{M-1} + a q_M$ (una semi-convergencia).
   • $n$ cumple una estructura similar al caso anterior con restricciones de paridad específicas en sus dígitos grandes.

Hallazgos Adicionales:

• Se demuestra que la balanceidad es simétrica respecto a $m$ y $n$ (debido a la simetría de la matriz de Hankel).
• Se establece que la condición de balanceidad es invariante bajo el cambio de $\alpha$ por $1-\alpha$.
• Se generalizan resultados previos que solo aplicaban a $\alpha$ cuadráticos, eliminando la necesidad de expansiones de fracciones continuas periódicas.

4. Significado e Impacto

• Generalización Universal: Este trabajo resuelve el problema de balanceidad 2D para todos los números irracionales, no solo para los cuadráticos. Esto cierra una brecha significativa en la teoría de palabras de Sturmian y sistemas dinámicos.
• Conexión Teórica: El artículo establece un puente profundo entre la combinatoria de palabras (balanceidad de rectángulos), la teoría de la discrepancia (distribución de $\{n\alpha\}$) y la teoría de números (representación de Ostrowski y aproximación diofántica).
• Herramientas Nuevas: La metodología basada en la biyectividad de funciones de mapeo en el toro y el uso de las propiedades finas de las representaciones de Ostrowski ofrece un marco robusto para analizar problemas similares en dimensiones superiores o con otras estructuras de palabras.
• Aplicaciones: Los resultados tienen implicaciones en la teoría de sistemas dinámicos (conjuntos de resto acotado), criptografía basada en palabras y la comprensión de la complejidad abeliana en secuencias aperiodicas.

En conclusión, Vukusic proporciona una solución completa y elegante al problema de la balanceidad rectangular, demostrando que la estructura algebraica de los enteros $m$ y $n$ (a través de Ostrowski) dicta completamente el comportamiento geométrico de las secuencias de Sturmian en dos dimensiones.