💻 computer science

Witness-split + window-cardinality refinement for $r_3(N)$ : Architecture, empirical results, and a structural hard pocket

Este artículo presenta un marco computacional reproducible que combina la división de testigos (witness-splitting), la poda de cardinalidad de ventana (window-cardinality pruning) y resolvedores híbridos SAT/MIP para investigar rigurosamente el límite superior de $r_3(212)$ , eliminando con éxito la mayoría de los 44-conjuntos candidatos mientras aísla dos casos estructurales resistentes que permanecen sin probar a pesar de los extensos esfuerzos de verificación.

Autores originales: Mehmet Ergezer

Publicado 2026-06-04

📖 5 min de lectura🧠 Análisis profundo

CC BY 4.0

Autores originales: Mehmet Ergezer

Artículo original bajo licencia CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta es una explicación generada por IA del artículo a continuación. No ha sido escrita ni avalada por los autores. Para mayor precisión técnica, consulte el artículo original. Leer descargo de responsabilidad completo

Imagina que estás intentando empacar una maleta (los números del 1 al 212) con la mayor cantidad de artículos posible, pero con una regla estricta: no puedes elegir tres artículos que formen un patrón aritmético perfecto.

Por ejemplo, si eliges el número 2, no puedes elegir también el 4 y el 6, porque $2, 4, 6$ es un patrón donde cada número es 2 unidades mayor que el anterior. Esto se llama una "progresión aritmética de 3 términos".

Matemáticos han estado tratando de averiguar el número máximo absoluto de artículos que puedes meter en esta maleta sin romper la regla. Para una maleta de tamaño 211, la respuesta conocida es 43. La gran pregunta de este artículo es: ¿Puedes meter 44 artículos en una maleta de tamaño 212?

El autor, Mehmet Ergezer, no se limitó a adivinar; construyó una enorme fábrica digital para intentar probar que 44 es imposible. Así es como se desglosa el artículo, utilizando analogías sencillas:

1. La Estrategia: La Fábrica de "División de Testigos"

Intentar revisar todas las combinaciones posibles de 44 números de entre 212 es como intentar encontrar un grano de arena específico en todas las playas de la Tierra. Es demasiado grande para que una sola computadora lo gestione.

Por eso, el autor utilizó un truco ingenioso:

El Testigo: Comenzó con una lista "segura" conocida de 43 números que ya funciona.
La División: Tomó los 24 números más "importantes" de esa lista segura y le pidió a la computadora que revisara cada escenario posible de "Sí/No" para ellos.
El Resultado: Esto dividió la montaña imposible de datos en 12.5 millones de montones más pequeños y manejables (llamados "trozos" o "chunks"). La computadora luego intentó resolver cada montón uno por uno.

2. Las Herramientas: La "Ventana" y el "Refinamiento"

Para que la computadora fuera más rápida, el autor añadió dos herramientas especiales:

La Tarjeta de Ventana (El Podador): Imagina mirar a través de una ventana una pequeña sección de la maleta. Ya sabemos por matemáticas previas que una pequeña ventana de tamaño 50 solo puede contener, digamos, 10 artículos. La computadora usa esta regla para descartar instantáneamente cualquier montón que intente poner 11 artículos en esa ventana. Esta fue la herramienta más poderosa, reduciendo el número de montones difíciles en casi un 30%.
El Refinamiento (La Inmersión Profunda): Si un montón era demasiado difícil de resolver en 60 segundos, la computadora no se rendía. Tomaba ese montón difícil específico, le añadía más reglas y lo intentaba de nuevo con un límite de tiempo más largo. Esto es como tomar una caja cerrada, elegir una cerradura específica y volver a intentarlo con una llave más grande.

3. Los Resultados: El "Bolsillo Difícil"

Después de ejecutar millones de estas comprobaciones en un clúster de supercomputadoras, esto fue lo que sucedió:

Cero Éxitos: La computadora nunca encontró una sola forma válida de empacar 44 artículos. Cada vez que lo intentaba, chocaba contra un muro y decía: "Imposible".
La Evidencia: Esta es una fuerte evidencia de que 44 es imposible, pero no es una prueba formal todavía. ¿Por qué? Porque todavía quedan algunos montones obstinados que la computadora no pudo terminar a tiempo.

El "Bolsillo Difícil" (Los Trozos Resistentes):
De los millones de montones, el autor encontró un pequeño y obstinado grupo de 45 montones que se resistieron incluso después de recibir tiempo extra y diferentes herramientas.

El Ataque LP: Intentaron un tipo diferente de resolvedor matemático (llamado HiGHS) que analiza el problema como una curva suave. Falló al resolver cualquiera de los 45 montones.
El Ataque CDCL: Intentaron un tercer tipo de resolvedor (llamado CDCL) que trabaja como un detective, aprendiendo de sus errores. Este tuvo éxito! Resolvió 18 de los 45 montones.
Los 2 Finales: Sin embargo, 2 montones (etiquetados como T1c) permanecieron completamente sin resolver. Resistieron al primer resolvedor, al segundo y al tercero. Son el "jefe final" de este problema.

4. La Conclusión: El "Hueco de la Unidad"

El artículo concluye que:

Tenemos una lista verificada de 43 números que funciona.
Tenemos evidencia sólida de que 44 es imposible, porque la computadora lo intentó millones de veces y falló.
Sin embargo, debido a esos 2 últimos montones obstinados, aún no tenemos una prueba matemática del 100%. La respuesta es casi con seguridad 43, pero el "hueco" entre 43 y 44 sigue técnicamente abierto.

5. El Regalo a la Comunidad

En lugar de simplemente decir "me rindo", el autor está liberando todos los datos. Él le entrega los 2 montones obstinados al mundo como un desafío.

Proporciona el código y los datos exactos para que otros matemáticos puedan intentar resolver solo esos dos montones.
Incluso tradujo el problema a un lenguaje para sistemas de prueba formal (Lean), invitando a científicos de la computación a intentar probarlo usando motores de lógica.

En resumen: El autor construyó una enorme máquina digital que intentó romper el récord de empacar números sin patrones. La máquina falló al intentar romper el récord, pero se quedó trabada en dos rompecabezas diminutos e increíblemente difíciles. El artículo dice: "Estamos 99.9% seguros de que la respuesta es 43, pero aquí están los dos rompecabezas finales que necesitas resolver para probarlo".

Resumen Técnico: Refinamiento de Cardinalidad de Ventana + División de Testigos para $r_3(212)$

Planteamiento del Problema
El artículo aborda el cálculo exacto de $r_3(N)$ , definido como el tamaño máximo de un subconjunto de $[1, N]$ que no contiene una progresión aritmética de tres términos (3-AP) no trivial. Mientras que el comportamiento asintótico está bien estudiado (p. ej., el teorema de Roth, Kelley–Meka), el enfoque aquí es la frontera finita en $N=212$ . Basándose en OEIS A003002, $r_3(211) = 43$ . Los autores investigan el problema de decisión: ¿Existe un subconjunto de 44 elementos libre de 3-AP en $[1, 212]$ ?
Los autores han verificado independientemente un testigo de 43 elementos, estableciendo que $r_3(212) \ge 43$ . La pregunta sobre el límite superior es si $r_3(212) \le 43$ . Una condición necesaria para cualquier hipotético conjunto de 44 elementos es que debe contener ambos extremos, 1 y 212; de lo contrario, se traduciría a un conjunto de 44 elementos en $[1, 211]$ , contradiciendo el valor conocido. Por lo tanto, el problema se reduce a demostrar la inviabilidad de un conjunto de 44 elementos que contenga $\{1, 212\}$ .

Metodología y Arquitectura
Los autores proponen un marco computacional reproducible que combina cinco componentes para buscar un conjunto de 44 elementos factible:

Modelo CP-SAT de Forma de Decisión: El problema se codifica utilizando variables booleanas $x_i$ para $i \in [1, 212]$ . Las restricciones incluyen:
- Desigualdades de 3-AP: $x_a + x_b + x_c \le 2$ para todas las ternas $(a, b, c)$ que forman una AP.
- Igualdad de cardinalidad: $\sum x_i = 44$ (más estricto para la propagación que una desigualdad).
- Forzado de extremos: $x_1 = x_{212} = 1$ .
- Ruptura de simetría: Ordenamiento lexicográfico para eliminar la simetría de reflexión.
División de Testigos (Witness-Splitting): Para gestionar el espacio de búsqueda, los autores utilizan un testigo verificado de 43 elementos $A_{43}$ . Clasifican los elementos de $A_{43}$ por su grado de incidencia en AP y seleccionan los 24 superiores. El espacio de búsqueda se divide en $2^{24}$ "trozos" (chunks) fijando los valores de estas 24 variables. Muchos trozos se podan inmediatamente si el prefijo fijo fuerza una 3-AP.
Poda de Cardinalidad de Ventana: Una intervención crítica implica la adición de desigualdades válidas derivadas de OEIS A003002. Para cualquier ventana $[a, a+L-1]$ , la suma de las variables está acotada por $r_3(L)$ . Con $N=212$ , esto añade 22,154 desigualdades, fortaleciendo significativamente el modelo más allá de las restricciones puras de 3-AP.
Refinamiento Recursivo: Los trozos que devuelven UNKNOWN en la capa amplia (profundidad 24) se refinan extendiendo el prefijo fijo con las siguientes variables del testigo de mayor grado (profundidades 40, 48, 56, 64) y resolviendo nuevamente con límites de tiempo más largos.
Diversidad de Solvers e Ingeniería: La campaña utiliza un pipeline basado en SLURM ejecutado en el clúster Unity de la Universidad de Massachusetts. Emplea:
- CP-SAT (OR-Tools): Para el paso amplio y el refinamiento recursivo.
- HiGHS (MIP): Un solver basado en relajación LP utilizado para atacar los trozos "UNKNOWN" más difíciles.
- CDCL/SAT (CaDiCaL): Utilizado para re-atacar trochos resistentes a los métodos LP, generando pruebas DRAT de insatisfacibilidad.

Resultados Empíricos
La campaña procesó millones de subproblemas a través del barrido de profundidad 24 y varios niveles de refinamiento.

Cero Soluciones Factibles: En todos los subproblemas probados (paso amplio, refinamientos, HiGHS y CDCL), se encontraron cero conjuntos de 44 elementos factibles. Esto proporciona un fuerte apoyo empírico para $r_3(212) = 43$ , aunque no constituye una prueba formal.
Impacto de la Cardinalidad de Ventana: Habilitar las desigualdades de cardinalidad de ventana redujo la tasa de UNKNOWN en los pasos amplios en aproximadamente 28 puntos porcentuales (por ejemplo, de ~30% a ~1.65% en lotes controlados), convirtiéndose en la capa de poda más efectiva.
El Bolsillo de Dificultad Estructural (Hard Pocket):
- De un lote de expansión de 100,000 trochos, 6,071 devolvieron UNKNOWN.
- Un recuento de 300 segundos de una muestra aleatoria de estos dejó 45 trochos resistentes (Nivel T1).
- Ataque HiGHS: Una ejecución de una hora de HiGHS cerró 0/45. Una auditoría de 8 horas cerró 25/45, dejando 20 trochos (Nivel T1b) con cotas duales fijadas en 0.0, lo que indica que la relajación LP no proporcionó un certificado de inviabilidad.
- Ataque CDCL: Un ataque puro de CDCL/SAT sobre los 20 trochos T1b cerró 18/20, generando pruebas DRAT verificadas independientemente.
- El Residual (T1c): Dos trochos (IDs 40959 y 48895) permanecieron como UNKNOWN incluso tras ejecuciones de CDCL puro de 12 horas y diagnósticos de CDCL con ventanas de 4 horas. Estos dos trochos resisten los paradigmas CP-SAT, HiGHS (LP-MIP) y CDCL.

Contribuciones Clave
El artículo enmarca explícitamente su contribución como metodológica en lugar de un nuevo valor exacto para $r_3(212)$ . Las contribuciones específicas son:

Arquitectura: Un marco reproducible que combina división de testigos, poda de cardinalidad de ventana y refinamiento recursivo para búsquedas de límites superiores exactos.
Relato Empírico: Un análisis detallado de la campaña $N=212, K=44$ , incluyendo el intercambio de solvers y la no uniformidad del espacio de búsqueda (p. ej., los trochos "middle-out" con asignaciones de pin específicas son significativamente más difíciles).
Caracterización del Bolsillo de Dificultad: Identificación de una obstrucción estructural (T1c) que es invariante a través de los paradigmas CP-SAT, HiGHS y CDCL bajo límites de tiempo generosos.
Lanzamiento de Benchmarks: Un lanzamiento escalonado de instancias:
- T1a: 25 trochos cerrados por HiGHS.
- T1b \ T1c: 18 trochos cerrados por CDCL con pruebas DRAT.
- T1c: Los 2 trochos resistentes finales, planteados como el problema abierto más agudo.
- T2/T3: Los 6,071 UNKNOWN amplios y el generador completo de 12.5M de trochos para futuros intentos.
Formalización: Una codificación en Lean 4 de los objetivos T1c para sistemas de búsqueda de pruebas formales.

Significancia y Reivindicaciones
Los autores afirman modestamente que, si bien la campaña apoya fuertemente la conjetura $r_3(212) = 43$ , no constituye una prueba formal debido al residual T1c no resuelto. La significancia radica en aislar la barrera computacional específica:

La brecha entre las cotas certificadas es exactamente una ( $43 \le r_3(212) \le 44$ ).
El fallo de los métodos basados en LP (HiGHS) y el éxito parcial de CDCL sugieren que la dificultad no es meramente un artefacto de propagación, sino una propiedad estructural donde la brecha de la relajación LP es estrecha y el certificado de inviabilidad entera es combinatoriamente difuso.
El trabajo postula que cerrar la brecha requiere ya sea límites de combinatoria aditiva más fuertes (p. ej., de análisis de Fourier o límites de partición de múltiples ventanas) o sistemas de branch-and-bound personalizados que exploten simetrías específicas del problema no capturadas por los solvers de propósito general.

El trabajo sirve como un punto de referencia para la comunidad, ofreciendo instancias específicas y verificadas (T1c) que representan el límite actual de los solvers de optimización combinatoria de propósito general para esta clase de problemas.