Proving Properties of $φ$-Representations with the Walnut Theorem-Prover

Este artículo demuestra cómo utilizar el demostrador de teoremas Walnut para obtener una prueba computacionalmente directa de un teorema clásico sobre representaciones $\phi$, lo que permite recuperar automáticamente resultados existentes y obtener nuevos hallazgos de manera uniforme y sin inducción.

Lo esencial

Un Viaje Mágico a través de los Números: Cómo "Walnut" Resuelve Misterios Matemáticos

Imagina que los números no son solo símbolos aburridos en una hoja de papel, sino que tienen una "voz" y una forma de hablar. Normalmente, hablamos de números en base 10 (usando los dígitos del 0 al 9), como si tuviéramos 10 dedos. Pero, ¿qué pasaría si tuviéramos un sistema de conteo basado en el Número Áureo (φ, o "phi")? Este es un número mágico que aparece en las conchas de los caracoles, en las espirales de las galaxias y en la proporción perfecta del arte.

En este número, los dígitos solo pueden ser 0 o 1, pero las reglas son un poco extrañas: no puedes poner dos "1" juntos (como "11"), porque eso rompería la magia de la proporción.

El artículo que nos ocupa es como un manual de instrucciones para un detective matemático. El autor, Jeffrey Shallit, nos cuenta cómo usó un software llamado Walnut (una herramienta de "cerebro artificial" para matemáticas) para resolver acertijos sobre cómo se escriben los números en este sistema especial.

Aquí te explico las ideas principales con analogías sencillas:

1. El Problema: Traducir entre Idiomas

Imagina que tienes dos idiomas:

• El idioma de Zeckendorf: Una forma muy ordenada de escribir números usando la secuencia de Fibonacci (1, 1, 2, 3, 5, 8...). Es como escribir un número usando solo bloques de construcción de tamaños específicos.
• El idioma de φ (phi): La forma en que se ve el número cuando lo descomponemos en potencias del número áureo.

La pregunta es: ¿Cómo sabemos si una secuencia de ceros y unos en el idioma de φ representa realmente un número entero?

Antes, los matemáticos tenían que hacer demostraciones muy largas y complicadas (como construir una torre de ladrillos una por una) para probar esto. Shallit dice: "¡Espera! Hay una forma más rápida".

2. La Herramienta: Walnut, el Traductor Automático

Walnut es como un traductor automático superpoderoso. En lugar de que un humano escriba una prueba lógica paso a paso, tú le das a Walnut una regla simple (en un lenguaje lógico) y él:

1. Construye un robot (automata) que sabe exactamente cuándo una secuencia de números es correcta.
2. Verifica si esa regla es verdadera para todos los números posibles.
3. Si hay dudas, el robot las resuelve instantáneamente.

Es como si le dijeras a un robot: "Crea un guardia de seguridad que solo deje pasar a los números que se escriben correctamente en base phi". Y el robot construye ese guardia en segundos.

3. Los Descubrimientos: Lo que el Robot Encontró

Una vez que el robot (el autómata) estaba construido, Shallit le pidió que resolviera varios misterios que habían dejado otros matemáticos:

• El Misterio de los Palíndromos:
  Un palíndromo es una palabra que se lee igual al derecho y al revés (como "oso" o "radar"). ¿Hay números que, escritos en base phi, sean palíndromos?

  • La analogía: Imagina que los números son espejos. Walnut encontró exactamente qué números se reflejan a sí mismos perfectamente en este sistema. ¡Y descubrió que hay una regla muy clara para encontrarlos!

• La Cuenta de las "1":
  ¿Cuántas veces aparece el dígito "1" en la escritura de un número en base phi?

  • La analogía: Es como contar cuántas luces se encienden en una fila de farolas. Walnut pudo predecir exactamente cuántas luces se encenderán para cualquier número, sin tener que contar una por una.

• Las "Carreras Verticales" de 1s:
  Imagina que escribes los números uno debajo del otro, como una columna. A veces, verás una columna de "1" que sube y baja. Walnut descubrió que la longitud de estas columnas sigue un patrón matemático muy bonito relacionado con los números de Lucas (un primo hermano de los de Fibonacci).

• Los "Expansiones Knott":
  Algunos matemáticos anteriores (Dekking y Van Loon) habían creado reglas complicadas para contar cuántas formas diferentes existen de escribir un número sin romper ciertas reglas.

  • La analogía: Era como intentar contar cuántas rutas diferentes hay para subir una montaña sin pisar ciertas piedras. Antes, esto requería cálculos manuales agotadores. Con Walnut, el robot simplemente "caminó" por todas las rutas posibles y contó: "¡Hay exactamente X caminos!". Y lo hizo sin cansarse.

4. ¿Por qué es importante esto?

Este trabajo es como pasar de caminar a pie a usar un cohete.

• Antes: Los matemáticos tenían que usar "inducción" (probar el caso 1, luego el 2, luego asumir que funciona para el 100). Era lento y propenso a errores.
• Ahora: Con Walnut, se puede probar una propiedad para todos los números infinitos de una sola vez, de forma automática y sin errores.

Además, el autor no solo repitió lo que otros habían hecho; descubrió cosas nuevas que nadie había visto antes, como secuencias de números que nunca se habían estudiado.

En Resumen

Este artículo nos enseña que, a veces, la mejor manera de entender la belleza y el orden del universo matemático no es con más lápiz y papel, sino con la ayuda de computadoras inteligentes que pueden "pensar" en lógica pura.

Es como si el autor hubiera construido un telescopio matemático (Walnut) que nos permite ver patrones en los números que antes estaban ocultos en la oscuridad, revelando que incluso en el caos aparente de los números, hay una danza perfecta y predecible.

La moraleja: La matemática no tiene por qué ser un laberinto solitario. Con las herramientas correctas, podemos convertir problemas imposibles en juegos de lógica que una máquina puede resolver por nosotros, dejándonos a nosotros la tarea de disfrutar de la belleza del resultado.

Resumen técnico

Resumen Técnico: Demostración de Propiedades de Representaciones $\phi$ con el Proveedor de Teoremas Walnut

Título del artículo: Proving Properties of $\phi$-Representations with the Walnut Theorem-Prover
Autor: Jeffrey Shallit
Publicación: Communications in Mathematics 33 (2025), no. 2, Paper no. 3.

1. Introducción y Problema

El artículo aborda el estudio de las representaciones en base $\phi$ (donde $\phi = (1+\sqrt{5})/2$ es la razón áurea), un sistema de numeración introducido por George Bergman en 1957. En este sistema, los números reales no negativos se expresan como sumas de potencias de $\phi$ con coeficientes binarios $\{0, 1\}$.

El problema central es la complejidad analítica y computacional para demostrar propiedades sobre estas representaciones, especialmente aquellas relacionadas con la representación canónica (que evita la subcadena "11" y ciertas terminaciones infinitas). Históricamente, los resultados sobre estas representaciones, como los de Frougny y Sakarovitch (2009) y más recientemente de Dekking y Van Loon, se han demostrado mediante inducciones matemáticas complejas y métodos ad-hoc que son difíciles de generalizar o verificar.

El objetivo del artículo es proporcionar un método computacionalmente directo y automatizado para:

1. Reconstruir y verificar el autómata finito de Frougny-Sakarovitch que decide si una cadena binaria es la representación $\phi$ de un entero.
2. Demostrar teoremas existentes y descubrir nuevos resultados sobre estas representaciones sin recurrir a inducciones manuales tediosas.

2. Metodología: El Proveedor de Teoremas Walnut

La metodología se basa en el uso de Walnut, un software de código abierto desarrollado por Hamoon Mousavi y Jeffrey Shallit. Walnut es un proveedor de teoremas para secuencias automáticas que utiliza un procedimiento de decisión para una extensión de la aritmética de Presburger.

Los pasos metodológicos clave son:

1. Formalización Lógica: Se expresan las propiedades de las representaciones $\phi$ en lógica de primer orden.
2. Construcción de Automatas: Walnut toma estas fórmulas lógicas y construye automáticamente automatas finitos deterministas (DFA) que aceptan exactamente los valores de las variables que hacen verdadera la afirmación.
3. Representación Lineal: Para funciones numéricas (como la suma de dígitos o el número de expansiones válidas), el software genera representaciones lineales (triples $(v, \gamma, w)$) que permiten calcular la función de manera eficiente ($O(\log n)$).
4. Verificación Automática: El sistema verifica automáticamente si una afirmación es verdadera (devolviendo TRUE) o falsa, y puede enumerar contraejemplos o caracterizar secuencias infinitas mediante sus automatas subyacentes.

El autor construye el autómata de Frougny-Sakarovitch desde cero utilizando componentes modulares en Walnut:

• Normalizadores para sistemas de Zeckendorf y negaFibonacci.
• Desplazadores (shifters) para manejar las potencias de $\phi$.
• Extractores de bits finales.
• Convertidores entre sistemas de numeración.

3. Contribuciones Clave y Resultados

El artículo presenta una serie de resultados, muchos de los cuales son nuevos o se obtienen de forma mucho más sencilla que en la literatura previa:

A. Reconstrucción del Autómata de Frougny-Sakarovitch

Se demuestra explícitamente cómo construir el autómata que acepta triples $(n, x, y)$ tales que $n = [x.y]_\phi$.

• Se obtiene un autómata de 116 estados para representaciones generales y uno de 39 estados para representaciones canónicas.
• Esto permite caracterizar completamente las representaciones plegadas (folded) de todos los enteros naturales.

B. Propiedades de Números Específicos

• Números de Fibonacci y Lucas: Se derivan fórmulas cerradas para las representaciones canónicas de $F_n$ y $L_n$, demostrando patrones periódicos mod 4 y mod 2 respectivamente.
• Suma de Dígitos: Se resuelve una conjetura de Dale Gerdemann (2012) demostrando que la suma de dígitos en la representación de Zeckendorf es siempre menor o igual que la suma de dígitos en la representación base-$\phi$ canónica.
• Longitud de Representaciones: Se caracteriza cuándo la longitud de la parte izquierda de la representación $\phi$ aumenta, vinculándolo a los números de Lucas.

C. Nuevas Secuencias y Propiedades Combinatorias

• Bits Individuales: Se caracterizan los bits $d_0(n)$, $d_1(n)$ y $d_{-1}(n)$ de la representación $\phi$. Se descubre una conexión sorprendente: $d_{-1}(n) = 1$ si y solo si $n$ tiene exactamente dos representaciones distintas como suma de números de Lucas.
• Palíndromos y Antipalíndromos: Se construyen automatas para identificar números cuyas representaciones $\phi$ son palíndromos (canónicos y no canónicos) y antipalíndromos (complemento bit a bit).
• Expansiones de Knott: Se recupera y simplifica el trabajo de Dekking y Van Loon sobre "expansiones de Knott" (representaciones que no terminan en 011). Se obtiene una representación lineal para el número total de tales expansiones, permitiendo calcular promedios asintóticos.

D. Nuevos Tipos de Expansiones

• Expansiones Naturales y DVL: Se analizan las "expansiones naturales" (donde la longitud de la parte fraccionaria coincide con la parte entera) y las "expansiones DVL" (que permiten "11" solo en posiciones específicas), obteniendo automatas y resultados sobre sus longitudes y frecuencias.
• Enteros Algebraicos: Se extiende la metodología para manejar números de la forma $m\phi + n$ (enteros algebraicos en $\mathbb{Z}[\phi]$), construyendo automatas para determinar propiedades de sus representaciones.

4. Significado e Impacto

El trabajo de Shallit es significativo por varias razones:

1. Unificación Metodológica: Demuestra que una amplia gama de problemas complejos en teoría de números y sistemas de numeración pueden resolverse mediante un enfoque unificado basado en la lógica y la teoría de automatas, eliminando la necesidad de pruebas por inducción manuales y propensas a errores.
2. Automatización de la Investigación: Proporciona una herramienta práctica para "descubrir" teoremas. Al cambiar ligeramente las condiciones en el código de Walnut, el autor obtiene automáticamente nuevos resultados (como las expansiones de Knott o las secuencias de bits individuales) que serían difíciles de adivinar analíticamente.
3. Verificación Rigurosa: Los resultados obtenidos por Walnut son formalmente correctos dentro del marco de la aritmética de Presburger, ofreciendo un nivel de certeza que complementa las pruebas matemáticas tradicionales.
4. Nuevas Secuencias en OEIS: El artículo identifica y define múltiples nuevas secuencias de enteros (ej. A362970, A362716, A362780, etc.) relacionadas con las propiedades de las representaciones $\phi$, enriqueciendo la On-Line Encyclopedia of Integer Sequences.

En conclusión, el artículo establece un nuevo paradigma para el estudio de las representaciones en base $\phi$ y, por extensión, de las $\beta$-expansiones para números de Pisot, demostrando que la computación automática de teoremas es una herramienta poderosa y accesible para la investigación matemática moderna.