Aquí presento un resumen técnico detallado del artículo "Balanced Fibonacci word rectangles, and beyond" (Rectángulos de palabras de Fibonacci equilibrados y más allá), escrito por Jeffrey Shallit e Ingrid Vukusic.

1. Planteamiento del Problema

El artículo aborda el problema de determinar cuándo los subrectángulos de matrices infinitas generadas por secuencias de palabras específicas son "equilibrados".

• Definición de la Matriz: Dada una secuencia infinita $(a_i)_{i \ge 0}$, se define una matriz infinita $A$ donde la entrada $a_{k,\ell} = a_{k+\ell}$. Los subrectángulos de tamaño $m \times n$ comienzan en la posición $i$ y se denotan como $A(i, m, n)$.
• Suma de la Matriz: La suma de todos los elementos en un rectángulo $A(i, m, n)$ se denota como $T(i, m, n)$.
• Concepto de Equilibrio (Balance): Un par de dimensiones $(m, n)$ se considera equilibrado si, al variar el índice de inicio $i$, la suma $T(i, m, n)$ toma a lo sumo dos valores distintos. Esto es una refinación del concepto de equilibrio en palabras binarias (donde la diferencia entre el número de 0s y 1s en bloques de igual longitud es acotada).
• Objetivo: Determinar exactamente qué pares de números naturales $(m, n)$ son equilibrados para diferentes secuencias infinitas, específicamente la palabra de Fibonacci, la palabra de Tribonacci y la palabra de Thue-Morse.

2. Metodología

Los autores emplean una combinación de teoría de números, teoría de palabras y automatas finitos asistidos por computación.

• Automatas Finitos y Lógica de Primer Orden: Utilizan el hecho de que para ciertos números irracionales cuadráticos (como la proporción áurea $\gamma$), la relación $x = \lfloor n\alpha \rfloor$ es definible mediante un autómata finito en un sistema de numeración específico (sistema de numeración de Ostrowski).
• Herramienta Computacional (Walnut): Implementan sus pruebas utilizando el software de código abierto Walnut, que permite traducir fórmulas de lógica de primer orden sobre secuencias definidas por autómatas en autómatas finitos que aceptan o rechazan entradas.
• Criterio de Equilibrio (Lema 1): Para las palabras de Sturmian (como la de Fibonacci), establecen que un rectángulo $m \times n$ es equilibrado si y solo si la secuencia de diferencias $\Delta(i, m, n) = T(i+1, m, n) - T(i, m, n)$ no contiene bloques de la forma $1, 0, \dots, 0, 1$ o $-1, 0, \dots, 0, -1$.
• Representación de Zeckendorf: Para el caso de Fibonacci, utilizan el sistema de numeración de Zeckendorf (suma de números de Fibonacci no consecutivos) como entrada para los autómatas.

3. Contribuciones y Resultados Clave

A. Palabra de Fibonacci

• Caracterización Automática: Demuestran que existe un algoritmo que construye un autómata finito que acepta exactamente los pares $(m, n)$ equilibrados para la palabra de Fibonacci.
• El Autómata "bal": Presentan un autómata de 15 estados (Figura 1 en el paper) que resuelve el problema de equilibrio para la palabra de Fibonacci.
• Recuperación de Resultados Previos: Su método demuestra automáticamente el teorema de Anselmo et al., que establece que si $\max(m, n)$ es un número de Fibonacci, el rectángulo es equilibrado.
• Nuevas Propiedades: Derivan propiedades sobre la densidad de los pares equilibrados y simetrías dentro de los intervalos de números de Fibonacci (Proposiciones 5 y 6).
• Rectángulos Diversos (Sección 5): Demuestran que el número de valores distintos que toma $T(i, m, n)$ para $m=n=F_{3k/2}$ es al menos $k+1$, lo que implica que el número de valores distintos crece linealmente con $n$ ($\Theta(n)$), refutando la posibilidad de que un autómata simple pueda calcular la cantidad exacta de valores distintos para entradas arbitrarias.

B. Palabra de Tribonacci

• Generalización: Analizan la palabra de Tribonacci (fija bajo el morfismo $0 \to 01, 1 \to 02, 2 \to 0$), que es 2-equilibrada en el sentido unidimensional.
• Resultados para Rectángulos:
  • Si $m=1$, todos los rectángulos $1 \times n$ son 2-equilibrados.
  • Si $m=2$, existe un autómata de 77 estados que caracteriza los $n$ para los cuales los rectángulos $2 \times n$ son 2-equilibrados. La lista de tales $n$ es compleja y no parece tener una descripción simple en inglés.
  • Si $m \ge 3$, no existen rectángulos $m \times n$ que sean 2-equilibrados. Demuestran esto construyendo dos rectángulos que difieren en al menos 3 en la cuenta del símbolo '2'.

C. Palabra de Thue-Morse

• Análisis de Equilibrio: Para la palabra de Thue-Morse ($t = 01101001\dots$), logran una descripción completa del equilibrio.
• Acotación: Demuestran que para cualquier rectángulo $m \times n$, la diferencia $|2|A(i, m, n)|_1 - mn|$ está acotada por 4.
• Autómata de 92 Estados: Construyen un autómata masivo (92 estados) que, dada la entrada $(m, n)$ en base 2, determina el nivel de equilibrio exacto (1, 2, 3 o 4).
• Resultado Específico: Prueban que para $m, n \ge 3$, el equilibrio es exactamente 3 si y solo si tanto $m$ como $n$ son impares.
• Complejidad Computacional: Destacan la magnitud del cálculo: el autómata intermedio más grande tuvo más de 32 millones de estados, requiriendo 12834 segundos de tiempo de CPU y 100 GB de RAM.

4. Significado e Impacto

1. Unificación de Métodos: El trabajo demuestra que problemas de equilibrio en dimensiones superiores (rectángulos) sobre secuencias complejas pueden resolverse sistemáticamente mediante autómatas finitos y lógica de primer orden, extendiendo resultados conocidos sobre el equilibrio unidimensional.
2. Herramienta Computacional: Subraya la potencia de herramientas como Walnut para probar teoremas en teoría de números y combinatoria de palabras que serían intratables analíticamente debido a la complejidad de los casos.
3. Generalización a Irracionales Cuadráticos: El Teorema 2 establece que este enfoque es aplicable a cualquier palabra de Sturmian correspondiente a un número irracional cuadrático, no solo a la palabra de Fibonacci.
4. Límites de la Automatización: La sección sobre "rectángulos diversos" (Sección 5) ofrece una advertencia teórica importante: aunque se puede decidir si un par es equilibrado, calcular el número exacto de valores distintos de la suma para entradas arbitrarias puede no ser computable por un autómata finito simple, ya que la complejidad puede crecer linealmente con el tamaño de la entrada.

En resumen, el artículo proporciona una caracterización completa y algorítmica del equilibrio bidimensional en palabras de Fibonacci, Tribonacci y Thue-Morse, utilizando la teoría de autómatas como herramienta central de demostración y descubrimiento.