🔢 mathematics

Exact values and exact upper bounds for families of integers with arithmetic progression intersections (Erd\H{o}s Problem #272)

Este artículo resuelve el Problema de Erdős #272 para $3 \leq N \leq 12$ al demostrar que el límite inferior de Szabó es exacto en este rango, establece que este límite es el máximo para familias que comparten un elemento común y reduce la conjetura general a la única cuestión restante de si una familia extremal debe siempre contener un elemento común.

Autores originales: Zhanfu Yang

Publicado 2026-07-28

📖 5 min de lectura🧠 Análisis profundo

CC BY 4.0

Autores originales: Zhanfu Yang

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 organizando una fiesta masiva en una casa con habitaciones numeradas del 1 al $N$ . Quieres invitar a grupos de invitados a pasar el rato en estas habitaciones, pero hay una regla muy específica y peculiar sobre quién puede estar en el mismo grupo: si tomas dos grupos cualesquiera y observas a las personas que tienen en común, ese grupo compartido debe formar una línea perfecta y uniformemente espaciada. En el lenguaje matemático, esto se llama una "progresión aritmética". Es como si el Grupo A tuviera a los invitados {2, 5, 8} y el Grupo B tuviera a {5, 8, 11}; su traslape es {5, 8}, que es una línea perfecta con un intervalo de 3. Pero si el traslape fuera {5, 9}, eso sería una línea rota, y la regla se rompería.

La gran pregunta que los matemáticos han estado planteando durante décadas es: ¿Cuántos grupos diferentes puedes invitar antes de quedarte sin formas de organizarlos sin romper la regla? Este es un rompecabezas sobre cómo encajar la mayor cantidad de piezas en una caja donde cada pieza tiene que encajar perfectamente con cada otra pieza siguiendo un patrón específico. Esto no es solo un juego; es un problema fundamental en la combinatoria, la rama de las matemáticas que estudia cómo se pueden organizar y contar las cosas. Resolver esto ayuda a comprender los límites ocultos de la estructura dentro de la aleatoriedad, mostrando cuánto orden podemos forzar en un sistema caótico antes de que colapse.

Durante mucho tiempo, los expertos pensaron que sabían la respuesta. Creían que el número máximo de grupos era aproximadamente la mitad del número de pares posibles de personas, más un poquito. Pero entonces, un matemático llamado Szabó apareció y dijo: "Un momento, ¡en realidad puedes meter unos cuantos grupos más de lo que se pensaba!". Él construyó una construcción ingeniosa que demostró que podías obtener algo ligeramente superior a la vieja conjetura. Sin embargo, no pudo probar si ese era el límite absoluto o si había alguna disposición aún más loca escondida en las sombras. También planteó una "pregunta del núcleo": ¿Existe siempre una persona específica que es invitada a todos y cada uno de los grupos en la mejor disposición posible?

Este artículo, escrito por Zhanfu Yang, se sumerge profundamente en este rompecabezas para encontrar las respuestas exactas para tamaños de fiesta más pequeños y para probar qué sucede cuando obligamos a que una persona específica esté en cada grupo. El autor no se limitó a adivinar; utilizó potentes programas informáticos para comprobar cada combinación posible para fiestas de hasta 12 habitaciones. ¿El resultado? Para estos tamaños más pequeños, la construcción ingeniosa de Szabó era perfecta. No fue solo una buena conjetura; fue el máximo absoluto. El artículo encontró los números exactos: para una fiesta con 12 habitaciones, puedes tener exactamente 69 grupos. Esta secuencia de números (4, 7, 12, 17, 23, 30, 39, 48, 58, 69) es tan nueva que ni siquiera aparece todavía en la famosa base de datos de secuencias numéricas.

Pero el artículo va más allá de solo contar. Aborda la "pregunta del núcleo" probando un teorema masivo: si sí obligas a que una persona esté en todos los grupos (una familia "estrellada"), entonces la construcción de Szabó es definitivamente lo mejor que puedes hacer. No importa cómo intentes reorganizar los grupos alrededor de esa única persona central, no puedes superar su número. Esto es un gran paso adelante porque estrecha la búsqueda. La única forma en que el máximo absoluto pudiera ser mayor que el número de Szabó es si la mejor disposición no tiene a una sola persona en todos los grupos.

El autor también descubrió una regla estructural fascinante sobre los grupos que no siguen el patrón de la línea perfecta (miembros "torcidos"). Probó que cualquier grupo tan extraño debe contener un "par malo" de personas —un par que no encaja con la regla de la línea— que ninguna otra agrupación en toda la fiesta pueda compartir. Es como un saludo secreto que solo ese grupo extraño conoce. Este "par privado" actúa como un cuello de botella, evitando que estos grupos extraños se acumulen demasiado sin romper las reglas.

Entonces, ¿dónde nos deja esto? El artículo ha resuelto el rompecabezas para números pequeños y ha probado que si existe un "invitado común", la respuesta es conocida y exacta. Lo único que queda por resolver es la última y obstinada pregunta: ¿Tiene la fiesta que rompa el récord siempre un invitado común? El artículo sugiere que si existe una fiesta que rompa el récord sin un invitado común, tendría que ser una estructura muy extraña y altamente específica que el autor ya ha comenzado a descartar. Si bien el artículo no ha cerrado el libro sobre el último misterio para cada número posible, ha convertido una conjetura vaga en un mapa preciso, mostrando exactamente dónde está escondido el tesoro y demostrando que el viejo mapa estaba equivocado. El viaje hacia la respuesta final es ahora mucho más corto, con el camino claramente marcado por la nueva regla del "par privado" del autor y los valores exactos confirmados para los primeros doce casos.

Resumen Técnico: Valores Exactos y Cotas Superiores Exactas para Familias de Enteros con Intersecciones de Progresiones Aritméticas

Planteamiento del Problema
El artículo aborda el Problema de Erdős #272, que busca determinar la función $t(N)$ , definida como el número máximo de subconjuntos distintos $A_1, \dots, A_t \subseteq \{1, \dots, N\}$ tales que la intersección de cualquier par de conjuntos distintos $A_i \cap A_j$ sea una progresión aritmética (PA) no vacía.

Históricamente, Simonovits y Sós establecieron que $t(N) = O(N^2)$ y conjeturaron que el máximo es alcanzado por la familia de todos los subconjuntos de tamaño a lo sumo 3 que contienen un elemento fijo, arrojando una cota de $\binom{N}{2} + 1$ . Szabó posteriormente refutó esta conjetura de exactitud mediante la construcción de una familia que logra $t(N) \ge \binom{N}{2} + 1 + \lfloor (N-1)/4 \rfloor$ . Szabó además estableció el comportamiento asintótico $t(N) = N^2/2 + O(N^{5/3}(\log N)^3)$ y planteó dos preguntas críticas: (i) si $t(N) = \binom{N}{2} + O(N)$ , y (ii) la "pregunta del núcleo" (kernel question), preguntando si toda familia extremal (una que alcanza el máximo) debe contener un elemento común compartido por todos sus conjuntos.

Metodología
Los autores emplean un enfoque híbrido que combina la verificación computacional exhaustiva, la combinatoria estructural y las técnicas de acotación analítica:

Computación Exacta: Para valores pequeños de $N$ $N$ ( $N \le 12$ $N \leq 12$ ), el problema se modela como la búsqueda del máximo clique en un grafo donde los vértices son subconjuntos no vacíos de $[N]$ $[N]$ y las aristas conectan conjuntos con intersecciones de PA no vacías.
- Para $N \le 10$ , se utilizó un resolvedor de rama y cota (branch-and-bound) con paralelismo de bits y cotas de coloración ávida (greedy coloring).
- Para $N=11$ y $12$, se empleó una búsqueda de decisión utilizando descomposición de raíz, ordenamiento de degeneración, pelado de núcleo (core peeling) y un riguroso paso de "poda de estrella" (star pruning) para probar la inexistencia de familias más grandes.
Descomposición Estructural: La demostración para la cota superior general se basa en la descomposición de una familia "estrellada" (una con un elemento común $m$ ) en subconjuntos de tamaño $\le 2$ , tamaño $3$, y tamaño $\ge 4$ .
Desigualdad de Conteo de Defecto Uno: Una herramienta técnica central es una desigualdad de conteo para "regiones de escalera" (familias de intervalos de enteros que contienen 0). Los autores demuestran que, para cualquier familia de este tipo, el número de miembros está acotado por el número de "pares malos" (pares $\{u,v\}$ tales que $\{0,u,v\}$ no es una PA) que cubren, más un pequeño término de defecto. Esto se verifica mediante un programa dinámico exacto para parámetros de hasta 500 y un argumento asintótico utilizando formas cuadráticas definidas positivas para parámetros mayores.
Teorema del Par Privado: Se establece un teorema estructural que muestra que cada miembro "torcido" (un conjunto de tamaño $\ge 4$ que no es una PA) contiene un "par malo privado": un par de elementos no contenidos en ningún otro miembro de la familia. Esto evita que se compartan "eliminaciones" (pares malos) entre miembros que no son PA, permitiendo un límite de conteo ajustado.

Contribuciones Clave y Resultados

Valores Exactos para $N$ Pequeños: El artículo determina $t(N)$ exactamente para $N = 3, \dots, 12$ . Los valores son $4, 7, 12, 17, 23, 30, 39, 48, 58, 69$. En todo este rango, la cota inferior de Szabó es exacta. La secuencia no aparece actualmente en la OEIS.
Conjetura Refinada: Basándose en la evidencia computacional, los autores conjeturan que para todo $N \ge 1$ :
$t(N) = \binom{N}{2} + 1 + \left\lfloor \frac{N-1}{4} \right\rfloor$
Esto refina la pregunta asintótica de Szabó hacia una fórmula exacta.
Cota Superior Exacta para Familias Estrelladas: El principal resultado teórico (Teorema 1.4) demuestra que para cualquier familia estrellada (donde todos los conjuntos comparten un elemento común), el tamaño está acotado por la cota inferior de Szabó. Este es el primer límite superior exacto de este tipo conocido para cualquier $N \ge 5$ $N \geq 5$ .
- La prueba combina la desigualdad de conteo de "defecto uno" con el "teorema del par privado" para manejar los miembros que no son PA.
Reducción a la Pregunta del Núcleo: Los autores demuestran que la conjetura refinada (que la fórmula se cumple para todo $N$ ) se sigue inmediatamente si la conjetura del núcleo de Szabó es cierta (es decir, si toda familia extremal es estrellada). Por lo tanto, el problema de determinar $t(N)$ exactamente se reduce a probar que las familias extremales deben tener un elemento común.
Restricciones Estructurales sobre Contraejemplos: El artículo analiza la estructura hipotética de una familia extremal no estrellada (un contraejemplo a la conjetura del núcleo). Demuestran que, si tal familia existiera, sus tríos deben compartir un elemento común, y cualquier miembro que evite dicho elemento debe ser una progresión aritmética larga con diferencias pequeñas. Los autores argumentan que tales configuraciones son "autolimitadas" y poco probables de alcanzar la cota conjeturada, aunque una prueba completa permanece abierta.

Significancia
El artículo afirma proporcionar la primera determinación exacta de $t(N)$ para cualquier $N \ge 5$ (específicamente $N \le 12$ ) y establece la primera cota superior exacta para la clase restringida de familias estrelladas. Al demostrar que la cota inferior es exacta para todas las familias estrelladas, el trabajo aisla la "propiedad del núcleo" como el único obstáculo restante para resolver completamente el Problema de Erdős #272. Los autores señalan que sus resultados confirman que la construcción de Szabó es óptima dentro de la clase de familias que comparten un elemento común, y proporcionan las primeras restricciones estructurales rigurosas sobre cómo sería un potencial contraejemplo no estrellado. El trabajo también introduce nuevas técnicas combinatorias, específicamente la desigualdad de conteo de defecto uno y el teorema del par privado, que pueden ser aplicables a otros problemas de intersección.

Más como este