Dead ends in square-free digit walks

Resumen Técnico: Callejones sin Salida en Caminos de Dígitos Libres de Cuadrados

Planteamiento del Problema
El artículo investiga la existencia y la densidad de los "callejones sin salida" (dead ends) en los caminos de dígitos libres de cuadrados. Un camino libre de cuadrados en una base $b$ comienza con un entero libre de cuadrados $N_0$ e intenta construir una secuencia infinita $N_0, N_1, N_2, \dots$ donde cada término subsiguiente se forma añadiendo un dígito $d \in \{0, \dots, b-1\}$ tal que $N_{k+1} = bN_k + d$ permanezca libre de cuadrados.

Un entero positivo $N$ se define como un callejón sin salida si:

1. $N$ es libre de cuadrados.
2. Para cada dígito $d$ en la base, la extensión $bN + d$ no es libre de cuadrados.

La cuestión central, planteada por Miller et al. [5], es si existen caminos infinitos libres de cuadrados. Aunque un modelo estocástico (el "Modelo Ciego Ilimitado") sugiere que existen caminos infinitos con una probabilidad cercana a 1 (lo que implica que los callejones sin salida son raros, con una densidad asintótica de $\approx 5.218 \times 10^{-5}$ en base 10), este artículo analiza rigurosamente la densidad aritmética real de los callejones sin salida para determinar si la predicción estocástica se sostiene.

Metodología
Los autores emplean una combinación de teoría de números multiplicativa elemental y principios de inclusión-exclusión, evitando las suposiciones probabilísticas del modelo estocástico.

1. Funciones Indicadoras: El problema se reformula utilizando la función de Möbius $\mu(n)$. Dado que $\mu(n)^2$ es la función indicadora de los enteros libres de cuadrados, la indicadora de un callejón sin salida $N$ se expresa como:
   $$\mathbb{1}_{N \text{ es callejón sin salida}} = \mu(N)^2 \prod_{d \in D} (1 - \mu(bN + d)^2)$$
   donde $D$ es el conjunto de dígitos.

2. Inclusión-Exclusión: El término del producto se expande en una suma sobre todos los subconjuntos $S$ del conjunto de dígitos. Esto transforma la función de conteo $D_b(X)$ (el número de callejones sin salida $\le X$) en una suma alternante de funciones de conteo $Q_S(X)$, donde $Q_S(X)$ cuenta los enteros $n \le X$ tales que $n$ y todas sus extensiones $bn+d$ (para $d \in S$) son libres de cuadrados.

3. Análisis de Criba: Para un subconjunto fijo $S$, la condición de que $n$ y $bn+d$ sean libres de cuadrados se analiza primo a primo. Los autores definen clases de residuos "malas" módulo $p^2$ que deben evitarse. Utilizando el Teorema de la Restricción China, determinan la densidad de los enteros que evitan estas clases.

   • Para primos grandes (donde $p \nmid b$), la condición $p^2 \mid (bn+d)$ obliga a $n$ a entrar en una única clase de residuo módulo $p^2$. Crucialmente, un solo cuadrado de un primo puede obstruir, como máximo, una extensión de dígito a la vez.
   • La densidad se expresa como un producto infinito (producto de Euler) de factores locales $(1 - \nu_{p,b}(S)/p^2)$, donde $\nu_{p,b}(S)$ cuenta el número de clases de residuo prohibidas módulo $p^2$.

4. Control del Término de Error: La demostración controla cuidadosamente los términos de error que surgen de truncar la criba en un parámetro $z$ y de la contribución de los primos grandes, estableciendo un término de error de $O(X/\sqrt{\log X})$.

Resultados Clave

• Teorema 1.1 (Base 10): La densidad asintótica de los callejones sin salida en base 10 existe y está dada por:
  $$c_{\text{dead}} = \sum_{S \subseteq \{0,\dots,9\}} (-1)^{|S|} \prod_{p \text{ primo}} \left( 1 - \frac{\nu_p(S)}{p^2} \right)$$
  donde $\nu_p(S)$ es el recuento de clases de residuo $n \pmod{p^2}$ tales que $p^2 \mid n$ o $p^2 \mid (10n+d)$ para algún $d \in S$.
  El valor calculado es $c_{\text{dead}} \approx 1.317 \times 10^{-9}$.

• Teorema 1.2 (Base General $b$): El resultado se generaliza a cualquier base $b \ge 2$. La densidad $c_{\text{dead}}(b)$ está dada por una expresión de forma cerrada similar que involucra una suma alternante de productos de Euler. El artículo proporciona aproximaciones calculadas para bases primas $b \in \{2, 3, 5, 7\}$.

• Discrepancia con Modelos Estocásticos: La densidad real ($\approx 1.3 \times 10^{-9}$) es aproximadamente 40,000 veces más pequeña que la predicción estocástica ($\approx 5.2 \times 10^{-5}$). El artículo atribuye esto a las dependencias aritméticas: el modelo estocástico ingenuo asume independencia entre las extensiones de los dígitos, pero en la realidad, el requisito de que las diez extensiones fallen simultáneamente requiere la obstrucción simultánea por muchos cuadrados de primos distintos, una condición mucho más estricta de lo que sugiere el modelo de probabilidad independiente.

Significado y Reivindicaciones

• Resolución de la Conjetura: El artículo demuestra que, si bien la heurística estocástica predice que los caminos infinitos son casi seguros, la estructura aritmética real hace que los callejones sin salida sean significativamente más raros de lo previsto. Sin embargo, la existencia de un camino infinito sigue siendo un problema abierto; el artículo cuantifica la rareza de las "obstrucciones" (callejones sin salida), pero no prueba la existencia de un camino infinito.
• Formalización: Una reivindicación principal del artículo es que el teorema principal (Teorema 1.2) fue completamente formalizado en Lean/Mathlib y la demostración fue producida automáticamente por una herramienta de IA llamada AxiomProver. El sistema recibió únicamente una declaración en lenguaje natural del problema y derivó autónomamente la fórmula de forma cerrada y la demostración.
• Contexto Histórico (Actualización): Los autores señalan que, tras la publicación inicial en arXiv, supieron por Kannan Soundararajan que el resultado principal ya había sido obtenido por Mirsky en 1947 [6]. El artículo reconoce que el trabajo de 2024 de Miller et al. [5] no hizo referencia a este trabajo previo. En consecuencia, aunque la formalización en Lean constituye una demostración automatizada válida, los autores afirman que el manuscrito no se enviará para publicación en revistas como contribución de investigación primaria, sirviendo en cambio como un caso de estudio para la demostración automática de teoremas.

Conclusión
El artículo proporciona una derivación aritmética rigurosa de la densidad de los callejones sin salida en los caminos de dígitos libres de cuadrados, revelando una desviación masiva de las predicciones estocásticas debido a las dependencias de la teoría de números. Su contribución más novedosa, según plantean los autores, es la exitosa formalización de extremo a extremo de este resultado utilizando AxiomProver, demostrando la capacidad de los sistemas de IA actuales para manejar problemas no triviales de la teoría analítica de números.