Weakly Consecutive Sequences

Resumen Técnico: Secuencias Débilmente Consecutivas

Definición del Problema
El artículo investiga las "secuencias débilmente consecutivas" (WCS, por sus siglas en inglés), una clase específica de permutaciones $\sigma$ del conjunto $\{1, \dots, k\}$. Una permutación se define como débilmente consecutiva si, para cualesquiera enteros $i, j \in [k]$ y cualquier entero $m$, la condición $m \mid \sigma(i)$ y $m \mid (i-j)$ implica que $m \mid \sigma(j)$. Intuitivamente, esta propiedad asegura que la estructura de divisibilidad de los valores se preserva en relación con sus posiciones; por ejemplo, todos los elementos a una distancia divisible por $d$ de la posición de $d$ deben ser también divisibles por $d$. El objetivo principal es comprender la estructura de estas secuencias y determinar $N(k)$, el número de WCS distintas de longitud $k$. Los autores señalan que, aunque $N(k)$ es a menudo una potencia de 2, exhibe un comportamiento irregular (por ejemplo, $N(21)=12$, $N(81)=40$) y es difícil de caracterizar mediante una fórmula cerrada.

Metodología
Los autores emplean un enfoque constructivo para generar y clasificar las WCS. Su metodología se basa en la identificación de un pequeño conjunto de "secuencias iniciales" y un conjunto de "reglas" (operaciones) que preservan la propiedad de débilmente consecutiva.

1. Lema de Caracterización: El artículo establece una equivalencia fundamental (Lema 2.2) que establece que una permutación es débilmente consecutiva si y solo si el conjunto de índices $S_m^\sigma$ (índices congruentes con la posición de $m$ módulo $m$) es igual al conjunto de índices $T_m^\sigma$ (índices donde el valor es un múltiplo de $m$) para todo $m$. Esta caracterización de "rebanada de división" se utiliza para probar la validez de todas las construcciones subsiguientes.
2. Secuencias Iniciales: Se identifican cuatro tipos específicos de permutaciones base, que dependen de las propiedades aritméticas de $k$:
   • Consecutiva: La secuencia identidad $(1, 2, \dots, k)$.
   • Inversión de 1: Válida cuando $k = p-1$ para un primo $p$, resultando en $(2, 3, \dots, k, 1)$.
   • Primos Gemelos Dobles: Válida cuando $k=2p$ o $2p+1$ para primos gemelos $p, p+2$, involucrando intercambios de posiciones para $2, 2p$ y $p, p+2$.
   • Sofía Germain Gemelo: Válida cuando $k=2p-1$ para primos $p, 2p+1, p+2$, involucrando el movimiento de $1, 2$ al final y el intercambio de $p, p+2$.
3. Reglas de Generación: Se definen tres operaciones para generar nuevas WCS a partir de las existentes:
   • Intercambio de Primos Gemelos: Intercambia los primos gemelos $q, q+2$ en la mitad superior de la secuencia (específicamente para la Secuencia Inicial 4).
   • Intercambio de Potencia de Primo: Intercambia $p^c$ y $p^{c-1}$ si $p^c \le k < p^c + p^{c-1}$. Esta regla es aplicable a cualquier secuencia inicial.
   • Reversión Trivial: Revierte la secuencia completa.

Contribuciones Clave y Resultados

• Construcción de WCS: El artículo proporciona un marco sistemático para generar WCS. Los autores conjeturan (Conjetura 5.1) que cualquier WCS puede derivarse de una de las cuatro secuencias iniciales aplicando las tres reglas. Esto ha sido verificado computacionalmente hasta $k=500$.
• Límites de $N(k)$:
  • Límites Inferiores: Al analizar la regla de "Intercambio de Potencia de Primo", los autores derivan un límite inferior sobre el crecimiento de $N(k)$. Definen $\#I(k)$ como el número de Intercambios de Potencia de Primo válidos para un $k$ dado. Dado que cada intercambio puede aplicarse o no, $N(k) \ge 2^{\#I(k)}$.
  • Teorema 4.1 y Corolario 4.2: Utilizando la aproximación de Dirichlet simultánea, los autores prueban que para cualquier $n$, existe un $k$ tal que $\#I(k) \ge n$. Específicamente, muestran que existe un $k \le 2^{n^2 \lg(\lg n)(1+o(1))}$ con $N(k) \ge n$. Esto prueba que $N(k)$ es una función no acotada de $k$.
  • Límites Superiores: Por el contrario, el artículo demuestra que $\#I(k)$ no siempre es grande. Utilizando argumentos probabilísticos que involucran variables aleatorias uniformes y la distribución de potencias de primos, el Teorema 4.8 muestra que $\liminf_{k \to \infty} \#I(k) \le 1$. Esto implica que para infinitos $k$, el número de Intercambios de Potencia de Primo es mínimo (como máximo 1), manteniendo $N(k)$ pequeño.
• Valores Específicos: El artículo proporciona una tabla de $N(k)$ para $k \le 100$, destacando que los valores que no son potencias de 2 ocurren específicamente cuando $k$ permite la secuencia inicial "Sofía Germain Gemelo" y los subsiguientes "Intercambios de Primos Gemelos".

Significancia y Reivindicaciones
El artículo afirma que la estructura de las secuencias débilmente consecutivas es "sorprendentemente rica" a pesar de su definición simple. La significancia del trabajo radica en:

1. No Acotación: Probar que el número de tales secuencias crece sin límite, aunque de manera errática, a medida que $k$ aumenta.
2. Conjetura Estructural: Proponer que el conjunto completo de WCS es generado por un conjunto finito de casos base y operaciones locales, vinculando la estructura combinatoria directamente con la distribución de los números primos (específicamente los primos gemelos y los primos de Sofía Germain).
3. Comportamiento Asintótico: Los autores conjeturan que si la conjetura de Dickson y la primera conjetura de Hardy-Littlewood son ciertas, la Secuencia Inicial 4 (Sofía Germain Gemelo) ocurrirá infinitas veces y dominará el conteo de WCS para $k$ grandes, llevando a valores de $N(k)$ significativamente mayores que el caso promedio derivado únicamente de los Intercambios de Potencia de Primo.
4. Modestia: Los autores declaran explícitamente que, si bien han verificado su conjetura de generación hasta $k=500$, no la han probado de manera general. También señalan que ciertas propiedades, como si toda WCS debe comenzar o terminar con 1 (Conjetura 5.2), permanecen sin probar desde los primeros principios.

El artículo concluye enmarcando el problema como un puente entre la combinatoria de permutaciones y la teoría de números, sugiriendo que la densidad de las WCS está profundamente ligada a la distribución de los primos y la existencia de constelaciones de primos específicas.