Palabras binarias de baja complejidad evitando potencias $(5/2)^+$

Información Básica

• ID del Artículo: 2506.19050
• Título: Palabras binarias de baja complejidad evitando potencias $(5/2)^+$
• Autores: James Currie, Narad Rampersad
• Clasificación: math.CO (Matemática Combinatoria), cs.FL (Lenguajes Formales)
• Fecha de Publicación: 13 de octubre de 2025 (preimpresión en arXiv)
• Enlace del Artículo: https://arxiv.org/abs/2506.19050

Resumen

Las secuencias Rote son secuencias infinitas que contienen exactamente $2n$ factores de longitud $n$ para cada $n \geq 1$. Shallit y Shur, así como Ollinger y Shallit, demostraron la existencia de secuencias Rote que evitan potencias $(5/2)^+$, siendo esto óptimo. Este artículo proporciona un teorema de estructura para secuencias Rote que evitan potencias $(5/2)^+$, confirmando una conjetura de Ollinger y Shallit.

Antecedentes y Motivación de la Investigación

Problema Central

Esta investigación se enfoca en dos conceptos fundamentales de la teoría combinatoria de palabras: la evitación de potencias y la complejidad de factores. El problema específico a resolver es: caracterizar la estructura de todas las secuencias binarias infinitas que evitan potencias $(5/2)^+$ y poseen la complejidad más baja ($2n$).

Importancia del Problema

1. Significado Teórico: La evitación de potencias y la complejidad de factores son conceptos fundamentales de la teoría combinatoria de palabras, y su interrelación es una dirección de investigación central en este campo
2. Teoría Estructural: Similar al teorema de estructura clásico de Restivo-Salemi sobre secuencias sin solapamiento, esta investigación establece nuevos teoremas de estructura
3. Verificación de Conjeturas: Confirma la importante conjetura de Ollinger y Shallit sobre la estructura de secuencias Rote

Limitaciones de la Investigación Existente

• Aunque Shallit y Shur, así como Ollinger y Shallit, demostraron la existencia y optimalidad de secuencias Rote que evitan potencias $(5/2)^+$, carecían de una caracterización estructural completa
• Los trabajos existentes solo proporcionaban ejemplos de construcciones concretas, sin ofrecer teoremas de estructura general

Motivación de la Investigación

Establecer un teorema de estructura completo, similar a cómo el teorema de Restivo-Salemi caracteriza secuencias binarias sin solapamiento, para proporcionar una base teórica que permita comprender las propiedades de evitación de potencias en secuencias de baja complejidad.

Contribuciones Principales

1. Introducción de los conceptos de secuencias propias y antipropias: Se definen dos subclases importantes de secuencias ternarias
2. Establecimiento del primer teorema de estructura: Se caracteriza la estructura recursiva de secuencias propias y antipropias
3. Demostración del segundo teorema de estructura: Se caracteriza completamente la estructura de secuencias Rote que evitan potencias $(5/2)^+$
4. Verificación de la conjetura de Ollinger-Shallit: Se proporciona una caracterización estructural completa que involucra los morfismos $f$ y $g$
5. Verificación computacional: Se validan los lemas clave mediante búsqueda de retroceso

Explicación Detallada de Métodos

Definición de la Tarea

Entrada: Secuencia binaria infinita $w$Condiciones de Restricción:

1. $w$ es una secuencia Rote (complejidad de factores igual a $2n$)
2. $w$ evita potencias $(5/2)^+$

Salida: Caracterización de la estructura de $w$, es decir, demostrar que $w$ puede expresarse como la aplicación de morfismos específicos a secuencias propias o antipropias

Definiciones Clave

Secuencias Propias y Antipropias

Para una secuencia ternaria $u \in \Sigma_3^*$, se define el vector de Parikh $\pi(u) = [|u|_0, |u|_1, |u|_2]$.

Secuencias propias satisfacen:

1. No contienen el factor $xyxyx$, donde $\pi(x) > \pi(y)$
2. No contienen los factores: $00, 11, 22, 20, 10101, 2121, 10210210$

Secuencias antipropias: Su inversa es una secuencia propia

Morfismos Clave

Se definen los morfismos $f: \Sigma_3^* \to \Sigma_3^*$ y $h: \Sigma_3^* \to \Sigma_3^*$:

• $f(0) = 0121$, $f(1) = 021$, $f(2) = 01$
• $h(0) = 1210$, $h(1) = 120$, $h(2) = 10$

Se define el morfismo $g: \Sigma_3^* \to \Sigma_2^*$:

• $g(0) = 011$, $g(1) = 0$, $g(2) = 01$

Métodos Técnicos Principales

1. Método de Análisis de Factores

Mediante el análisis detallado de los factores de longitud 4 que deben contener las secuencias binarias que evitan potencias $(5/2)^+$, se determinan las restricciones estructurales fundamentales de estas secuencias.

Lemas Clave:

• Lema 1: Toda secuencia binaria infinita que evita potencias $(5/2)^+$ debe contener los factores $0110$ y $1001$
• Lema 3: Las secuencias con complejidad de factores $\leq 2n$ que evitan potencias $(5/2)^+$ deben contener los factores $0011$ y $1100$

2. Verificación por Búsqueda de Retroceso

Se utiliza un programa computacional para verificar los lemas clave, determinando mediante prueba constructiva la necesidad de las condiciones de restricción.

3. Análisis de Estructura Recursiva

Se demuestra que las secuencias propias y antipropias poseen una estructura recursiva autosimilar que puede caracterizarse mediante los morfismos $f$ y $h$.

Configuración Experimental

Método de Verificación Computacional

El artículo implementa en Python un algoritmo de búsqueda de retroceso para verificar los lemas clave:

def fhpf(w): # Verifica si la secuencia w evita potencias 5/2+
    p=1
    while (5*p<2*len(w)):
        if (w[(-(p+1)//2)-p:]==w[(-(p+1)//2)-2*p:-p]):
            return(False)
        p=p+1
    return(True)

Contenido de la Verificación

1. Verificación del Lema 1: La secuencia más larga que no contiene $0110$ y evita potencias $(5/2)^+$ tiene longitud 14
2. Verificación del Lema 2: Se verifica que al menos 3 elementos del conjunto $C = \{0010, 0100, 1011, 1101\}$ deben aparecer
3. Verificación del Lema 3: Se realiza verificación detallada para cada elemento del conjunto $A$
4. Verificación del Lema 4: Se verifican las condiciones de restricción de 17 secuencias específicas de longitud 9

Resultados Experimentales

Resultados Principales

Teorema 1 (Primer Teorema de Estructura)

1. Para una secuencia propia $u \in \Sigma_3^{\omega}$, algún sufijo tiene la forma $f(v)$, donde $v$ es una secuencia propia
2. Para una secuencia antipropia $u \in \Sigma_3^{\omega}$, algún sufijo tiene la forma $h(v)$, donde $v$ es una secuencia antipropia

Teorema 2 (Segundo Teorema de Estructura)

Las secuencias Rote que evitan potencias $(5/2)^+$ tienen cuatro casos, cuyos conjuntos de factores de longitud 4 son respectivamente:

1. $F = \{0110, 1001, 0011, 1100, 0010, 0100, 1101, 1010\}$
2. $\bar{F}$ (complemento de $F$)
3. $F^R$ (inversa de $F$)
4. $\overline{F^R}$ (complemento de la inversa de $F$)

En cada caso, algún sufijo de $w$ puede expresarse en la forma $g(f^n(u))$ o $g(h^n(u))$, donde $u$ es una secuencia propia.

Resultados de Verificación Computacional

• Secuencia más larga sin $0110$ que evita potencias $(5/2)^+$: longitud 14
• Secuencia más larga sin dos elementos de $C$: longitud 44
• Secuencia más larga sin $0011$ y algún elemento de $A$: longitud 31
• Las longitudes máximas de secuencias bajo diversas condiciones de restricción están dentro del rango esperado

Trabajos Relacionados

Resultados Clásicos

1. Teorema de Restivo-Salemi: Caracteriza la estructura de secuencias binarias sin solapamiento, utilizando el morfismo de Thue-Morse
2. Teoría de Secuencias Sturmian: La secuencia de Fibonacci evita potencias $(5+\sqrt{5})/2$, siendo este el resultado óptimo entre secuencias Sturmian

Avances Recientes

1. Trabajo de Shallit-Shur: Establece el marco de investigación de la relación entre evitación de potencias y complejidad de factores
2. Trabajo de Ollinger-Shallit: Construye ejemplos concretos de secuencias Rote que evitan potencias $(5/2)^+$
3. Trabajo de Dvořáková et al.: Demuestra que $g(f^{\omega}(0))$ evita potencias $(5/2)^+$ y es una secuencia Rote

Contribución de Este Artículo

Este artículo proporciona un teorema de estructura completo, similar a la posición del teorema de Restivo-Salemi en secuencias sin solapamiento, llenando un vacío teórico.

Conclusiones y Discusión

Conclusiones Principales

1. Caracterización Completa: Se proporciona una estructura completa de todas las secuencias Rote que evitan potencias $(5/2)^+$
2. Verificación de Conjeturas: Se confirma la conjetura de Ollinger-Shallit sobre la acción de los morfismos $f$ y $g$
3. Innovación Metodológica: Combina argumentos combinatorios y verificación computacional, proporcionando una prueba rigurosa

Limitaciones

1. Dependencia Computacional: Algunos lemas clave dependen de verificación computacional; aunque los resultados son confiables, carecen de pruebas puramente teóricas
2. Exponente Específico: Los resultados solo se aplican a potencias $(5/2)^+$; la generalización a otros exponentes requiere investigación adicional
3. Restricción Binaria: Los resultados principales se concentran en secuencias binarias; el caso ternario aún requiere exploración

Direcciones Futuras

1. Generalización Ternaria: Explorar la relación entre complejidad $2n+1$ y evitación de potencias en secuencias ternarias
2. Otros Exponentes: Investigar la estructura de secuencias de baja complejidad que evitan potencias de otros exponentes
3. Aplicaciones Algorítmicas: Aplicar teoremas de estructura a algoritmos de generación e identificación de secuencias

Evaluación Profunda

Fortalezas

1. Completitud Teórica: Proporciona una caracterización estructural completa, resolviendo un problema abierto importante
2. Rigor Metodológico: Combina análisis teórico y verificación computacional, con un proceso de prueba sólido y confiable
3. Innovación Técnica: Los conceptos de secuencias propias/antipropias poseen originalidad
4. Valor Práctico: El teorema de estructura proporciona herramientas teóricas para la construcción y análisis de secuencias relacionadas

Deficiencias

1. Complejidad de Prueba: Las pruebas de algunos lemas dependen de análisis exhaustivos de casos; pueden existir métodos más elegantes
2. Verificación Computacional: Los pasos clave dependen de búsqueda computacional; la pureza teórica se ve algo comprometida
3. Generalización: La posibilidad de generalizar resultados a otros parámetros o alfabetos no está suficientemente clara

Impacto

1. Contribución Teórica: Proporciona nuevos teoremas de estructura para la teoría combinatoria de palabras, con importante valor teórico
2. Significado Metodológico: Demuestra la efectividad de combinar análisis teórico con verificación computacional
3. Investigación Posterior: Proporciona nuevas ideas y herramientas para la investigación de problemas relacionados

Escenarios de Aplicación

1. Investigación Teórica: Investigación en teoría combinatoria de palabras y teoría de lenguajes formales
2. Análisis de Secuencias: Construcción y análisis de secuencias infinitas con propiedades específicas
3. Diseño de Algoritmos: Algoritmos para generar secuencias que eviten patrones específicos

Referencias Bibliográficas

El artículo cita trabajos importantes en este campo, incluyendo:

• El teorema de estructura clásico de Restivo & Salemi sobre secuencias sin solapamiento
• El trabajo pionero de Shallit & Shur sobre la relación entre evitación de potencias y complejidad
• La investigación reciente de Ollinger & Shallit sobre umbrales de repetición en secuencias Rote
• Los resultados clásicos de Carpi & de Luca sobre secuencias Sturmian

Evaluación General: Este es un artículo de alta calidad que resuelve un problema importante en la teoría combinatoria de palabras, proporcionando una caracterización estructural completa y verificando una conjetura importante, con contribuciones significativas para el campo. Aunque algunas pruebas dependen de verificación computacional, el método general es riguroso, los resultados son confiables y proporcionan una base sólida para investigaciones posteriores.