Secuencia Autogeneradora de Cloitre

Información Básica

• ID del Artículo: 2501.00784
• Título: Secuencia Autogeneradora de Cloitre
• Autor: Jeffrey Shallit (Universidad de Waterloo)
• Clasificación: math.CO cs.DM cs.FL math.NT
• Fecha de Publicación: 3 de enero de 2025
• Enlace del Artículo: https://arxiv.org/abs/2501.00784

Resumen

En 2009, Benoit Cloitre introdujo una secuencia autogeneradora especial $(a_n)_{n\geq 1} = 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 2, 1, 1, 2, 2, \ldots$, que posee la propiedad de que la suma de todos los términos en la $n$-ésima carrera (run) es igual al doble del $n$-ésimo término de la secuencia. Este artículo establece la conexión entre esta secuencia y la secuencia de plegado de papel, y demuestra la conjetura de Cloitre sobre la densidad del dígito 1 en la secuencia.

Antecedentes de Investigación y Motivación

Problemas de Investigación

El problema central de investigación de este artículo es analizar las propiedades estructurales de la secuencia autogeneradora de Cloitre, en particular:

1. La relación entre esta secuencia y objetos matemáticos conocidos (secuencia de plegado de papel)
2. El problema de la densidad asintótica del dígito 1 en la secuencia

Importancia del Problema

Las secuencias autogeneradoras ocupan un lugar importante en la matemática combinatoria, exhibiendo propiedades estructurales complejas mientras se relacionan con múltiples ramas matemáticas. La investigación de la secuencia de Cloitre tiene el siguiente significado:

• Amplía la comprensión de las propiedades de las secuencias autogeneradoras
• Establece nuevas conexiones con secuencias clásicas como la secuencia de plegado de papel
• Proporciona nuevos casos de aplicación de la teoría de autómatas en el análisis de secuencias

Limitaciones de la Investigación Existente

La investigación existente sobre secuencias similares (como la secuencia de Oldenburger-Kolakoski) indica que las propiedades asintóticas de estas secuencias son a menudo difíciles de analizar. Por ejemplo, para la secuencia de Oldenburger-Kolakoski, la cuestión de si la densidad de 1 es 1/2 sigue siendo una conjetura sin resolver.

Motivación de la Investigación

Cloitre propuso en la entrada OEIS A157196 una conjetura sobre que la densidad de 1 en esta secuencia es 2/3, lo que proporciona un objetivo claro para la investigación de este artículo.

Contribuciones Principales

1. Establecimiento de nuevas conexiones de secuencias: Descubrimiento por primera vez de la conexión profunda entre la secuencia autogeneradora de Cloitre y la secuencia regular de plegado de papel
2. Demostración de la conjetura de densidad: Prueba rigurosa de la conjetura de Cloitre sobre que la densidad de 1 en la secuencia es 2/3
3. Provisión de límites precisos: Demostración de que $0 \leq 3g_n - 2n \leq 4$, donde $g_n$ es el número de 1 en los primeros $n$ términos
4. Desarrollo del método de autómatas: Uso de autómatas finitos y software Walnut para proporcionar un marco de verificación computacional para el análisis de secuencias
5. Extensión al caso general: Generalización de resultados a secuencias de plegado de papel arbitrarias

Explicación Detallada de Métodos

Definición de Tareas

Investigación de la secuencia de Cloitre $(a_n)_{n\geq 1}$, definida por la siguiente regla autogeneradora:

• La secuencia toma valores en el alfabeto {1,2}
• Comienza con $a_1 = 1$
• La suma de todos los elementos en la $n$-ésima carrera es igual a $2a_n$

Arquitectura del Método Principal

1. Cadena de Construcción de Secuencias

El artículo construye una serie de secuencias interrelacionadas:

• Secuencia regular de plegado de papel $(p_n)$
• Versión binaria $(q_n)$, satisfaciendo $p_n = (-1)^{q_n}$
• Secuencia de diferencias de primer orden $(d_n)$
• Secuencia de valores absolutos $(d'_n)$
• Posiciones de fin de carrera $(e'_n)$
• Obtención final de $(b_n) = (a_n)$

2. Representación de Autómatas

Cada secuencia puede representarse mediante un autómata finito:

• DFAO (Autómata Finito Determinista con Salida): Utilizado para secuencias que toman valores finitos
• Autómata Sincrónico: Utilizado para secuencias que toman valores enteros
• Todos los autómatas utilizan representación binaria con el bit menos significativo primero

3. Marco de Verificación Walnut

Uso del software Walnut para verificación formal:

eval q_test "?lsd_2 An (Q[2*n]=Q[n] & Q[4*n+1]=@0 & Q[4*n+3]=@1)":

Puntos de Innovación Técnica

1. Conexión de Secuencia de Plegado de Papel

Descubrimiento innovador de la conexión entre la secuencia de Cloitre y la secuencia de plegado de papel: $q_{2n} = q_n, \quad q_{4n+1} = 0, \quad q_{4n+3} = 1$

2. Estrategia de Conjetura-Verificación

Para secuencias complejas (como posiciones de fin de carrera), se adoptó una estrategia de "conjeturar autómata y luego verificar", que es un método efectivo para procesar secuencias automáticas.

3. Análisis de Secuencias Multicapa

Mediante la construcción de múltiples secuencias intermedias, se descomponen las propiedades autogeneradoras complejas en cálculos de autómatas manejables.

Configuración Experimental

Herramientas Computacionales

• Software Walnut: Utilizado para cálculos de autómatas y verificación formal
• Autómatas Finitos: Todas las secuencias se representan y calculan mediante autómatas
• Base de Datos OEIS: Utilizada para verificación y comparación de secuencias

Métodos de Verificación

1. Verificación de Corrección de Autómatas: Verificación de la corrección del autómata mediante múltiples condiciones
2. Verificación de Relaciones de Recurrencia: Verificación de que la secuencia satisface las relaciones de recurrencia
3. Comprobación de Condiciones Límite: Verificación de condiciones iniciales y casos especiales

Detalles de Implementación

• Uso de representación binaria con el bit menos significativo primero
• Número de estados de autómata que varían de 4 a 32
• Todos los cálculos se verifican formalmente mediante Walnut

Resultados Experimentales

Demostración del Teorema Principal

Teorema 2: Sea $g_n$ el número de 1 en la secuencia $a_1a_2\cdots a_n$, entonces: $0 \leq 3g_n - 2n \leq 4$ Por lo tanto, $\lim_{n\to\infty} g_n/n = 2/3$.

Resultados de Verificación Clave

1. Consistencia de Secuencia: Verificación de que $b_n = a_n$, es decir, la secuencia construida es efectivamente la secuencia de Cloitre
2. Propiedad Autogeneradora: Verificación de que $\sigma_n = 2b_n$, donde $\sigma_n$ es la suma de la $n$-ésima carrera
3. Longitud de Carrera: Demostración de que la longitud de carrera solo puede ser 1, 2 o 4
4. Límites de Densidad: Verificación de límites de densidad mediante autómata de 16 estados

Descubrimientos Adicionales

Demostración de que la secuencia $w_n = \min\{t \geq 1 : e'_t \geq n\}$ es la secuencia OEIS A091960, satisfaciendo:

• $w_1 = 1$
• $w_{2n} = w_{2n-1} + (w_n \bmod 2)$
• $w_{2n+1} = w_{2n} + 1$

Trabajo Relacionado

Secuencias Principales Relacionadas

1. Secuencia de Oldenburger-Kolakoski: $k := 1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, \ldots$
   • El $n$-ésimo término es igual a la longitud de la $n$-ésima carrera
   • El problema de la densidad de 1 sigue sin resolverse
2. Secuencia de Dekking: $1, 3, 3, 3, 1, 1, 1, 3, 3, 3, \ldots$
   • La secuencia de longitud de carrera es igual a la secuencia misma
   • Puede entenderse como punto fijo de un morfismo
3. Secuencia de Plegado de Papel: Generada por iteración de plegado de papel
   • Tiene conexión profunda con representación binaria
   • Puede calcularse mediante autómata finito

Singularidad de la Contribución de Este Artículo

La secuencia de Cloitre es más manejable que la secuencia de Oldenburger-Kolakoski porque tiene una conexión sutil pero clara con la representación binaria, lo que hace que el método de autómatas sea particularmente efectivo.

Conclusiones y Discusión

Conclusiones Principales

1. Teorema de Densidad: Demostración rigurosa de que la densidad de 1 en la secuencia de Cloitre es 2/3
2. Conexiones Estructurales: Establecimiento de conexión profunda con la secuencia de plegado de papel
3. Marco Computacional: Demostración del poder del método de autómatas en análisis de secuencias

Universalidad del Método

El artículo en la sección 7 indica que todos los resultados pueden generalizarse a secuencias de plegado de papel arbitrarias, aunque en el caso general no hay un análogo obvio de la propiedad autogeneradora.

Direcciones Futuras

1. Investigación de conexiones entre otras secuencias autogeneradoras y secuencias clásicas
2. Desarrollo de un marco de análisis de autómatas más general
3. Exploración de aplicaciones en otras ramas matemáticas

Evaluación Profunda

Ventajas

1. Innovación Metodológica: Combinación ingeniosa de teoría de autómatas con análisis de secuencias
2. Rigor: Todos los resultados se verifican formalmente
3. Completitud: No solo demuestra la conjetura principal, sino que también descubre propiedades estructurales adicionales
4. Extensibilidad: El método puede generalizarse a categorías más amplias de secuencias

Puntos Destacados Técnicos

1. Estrategia de Conjetura-Verificación: Proporciona un método práctico para análisis de secuencias automáticas complejas
2. Construcción de Secuencias Multicapa: Simplifica el análisis de propiedades complejas mediante secuencias intermedias
3. Verificación Computacional: El uso del software Walnut asegura la confiabilidad de los resultados

Limitaciones

1. Complejidad Computacional: Algunos autómatas tienen un número considerable de estados, lo que puede limitar el análisis de secuencias más complejas
2. Dependencia de Conjetura: Algunos autómatas requieren conjetura previa seguida de verificación, careciendo de un método de construcción sistemático
3. Restricciones de Generalización: Aunque puede generalizarse a secuencias de plegado de papel arbitrarias, se pierde la propiedad autogeneradora

Impacto

1. Contribución Teórica: Proporciona nuevas herramientas de análisis para investigación de secuencias autogeneradoras
2. Valor Metodológico: Demuestra la aplicación de pruebas asistidas por computadora en matemática combinatoria
3. Practicidad: Proporciona un modelo para investigación de secuencias relacionadas en OEIS

Escenarios Aplicables

Este método es particularmente aplicable a:

• Análisis de secuencias relacionadas con representación binaria
• Investigación de secuencias automáticas con estructura recursiva
• Análisis de densidad precisa de secuencias combinatorias

Referencias

El artículo cita 14 referencias importantes que abarcan teoría de secuencias automáticas, secuencias de plegado de papel, secuencia de Kolakoski y otros campos relacionados, proporcionando una base teórica sólida para la investigación.