Largest Sidon subsets in weak Sidon sets

Este artículo mejora los límites conocidos para la constante $c_*$ que garantiza que todo conjunto $(4,5)$ de tamaño $n$ contenga un subconjunto Sidón de tamaño al menos $c_* n$, demostrando que $\frac{9}{17} \le c_* \le \frac{4}{7}$ mediante una reformulación del problema extremal y una construcción explícita.

Lo esencial

¡Hola! Vamos a desglosar este artículo matemático complejo como si fuera una historia sobre organizadores de fiestas y reglas de convivencia.

Imagina que tienes un grupo de personas (números) y quieres formar subgrupos especiales donde nadie se "confunda" con nadie más. Los matemáticos llaman a estos grupos especiales Conjuntos de Sidon.

1. ¿Qué es un "Conjunto de Sidon"? (La fiesta perfecta)

Imagina que cada persona tiene un número secreto. La regla de oro de un Conjunto de Sidon es:

"Si tomas a dos personas y sumas sus números, esa suma debe ser única en todo el grupo. Nadie más puede tener la misma suma."

Por ejemplo, si tienes a Ana (2) y Bob (5), su suma es 7. Si en el grupo también tienes a Carlos (3) y Dana (4), su suma también es 7. ¡Problema! Eso no es un Conjunto de Sidon porque la suma "7" se repite. En un Sidon, cada suma es como una huella dactilar única.

2. El primer misterio: Los "Casi Sidon" (Conjuntos débiles)

Los autores, Jie Ma y Quanyu Tang, se preguntaron: ¿Qué pasa si tenemos un grupo que casi cumple la regla, pero no del todo?
Llamaron a esto Conjunto de Sidon Débil.

• La regla débil: Solo importa que las sumas de personas diferentes sean únicas. Si alguien suma su propio número consigo mismo (ej. 3 + 3), no importa si se repite.

La gran pregunta de Sárközy y Sós:
Si tienes un grupo gigante de "casi Sidon" (débil), ¿cuántas personas puedes salvar para formar un grupo "Sidon perfecto" (donde la regla sea estricta)?

La respuesta del artículo:
¡Es muy simple y elegante! Si tienes un grupo de $n$ personas "casi Sidon", siempre podrás encontrar un grupo Sidon perfecto de aproximadamente la mitad de las personas.

• Si tienes 100 personas, puedes salvar 50.
• Si tienes 101, puedes salvar 51.
• La fórmula mágica: $(n + 1) / 2$.

La analogía: Imagina que tienes una caja llena de piezas de rompecabezas que encajan casi perfecto. El artículo demuestra que, sin importar cuán grande sea la caja, siempre puedes sacar la mitad exacta de las piezas para armar un cuadro perfecto sin errores.

---

3. El segundo misterio: Los "Conjuntos (4, 5)" (La prueba de distancia)

Luego, el artículo aborda otro problema propuesto por el famoso matemático Paul Erdős. Aquí no miramos sumas, sino distancias.

Imagina que tienes 4 personas en una fila. Entre ellas hay 6 distancias posibles (la distancia entre la 1 y la 2, la 1 y la 3, etc.).

• Un Conjunto (4, 5) es un grupo donde, si tomas cualquier grupo de 4 personas, las 6 distancias entre ellas deben ser al menos 5 valores diferentes. (Es decir, no pueden repetirse muchas distancias).

La pregunta de Erdős:
Si tienes un grupo gigante que cumple esta regla de distancias (un conjunto 4,5), ¿cuántas personas puedes salvar para formar un grupo Sidon perfecto?

Antes de este artículo, los matemáticos sabían que podías salvar al menos un poco más de la mitad (aprox. 50.000... algo) y como máximo el 60%.

La mejora de Ma y Tang:
Ellos han afinado estos números:

• Nuevo mínimo garantizado: Siempre puedes salvar al menos 9 de cada 17 personas (aprox. 53%).
• Nuevo máximo posible: Hay un ejemplo específico donde solo puedes salvar 4 de cada 7 personas (aprox. 57%).

La analogía: Imagina que estás buscando un equipo de baloncesto donde nadie mide lo mismo que otro. Sabías que en una liga muy estricta (distancias variadas), siempre podías formar un equipo decente. Estos autores han calculado exactamente cuán grande puede ser ese equipo "decente" en el peor de los casos.

---

4. ¿Cómo lo hicieron? (Las herramientas mágicas)

Para resolver esto, usaron dos trucos principales:

1. El "Hipercubo de las Progresiones" (Hipergrafos):
   Imagina que cada vez que tres números forman una secuencia ordenada (como 2, 4, 6), los conectas con una línea roja. Si logras quitar todas las líneas rojas (sin tener secuencias ordenadas), tienes tu grupo Sidon.

   • Para el primer problema, demostraron que en los grupos "débiles", las líneas rojas son tan pocas que siempre puedes cortar la mitad de los nodos y quedarte con un grupo limpio.
   • Para el segundo problema, usaron una estructura geométrica muy específica (llamada $F_7$) para demostrar que las líneas rojas no pueden estar tan desordenadas como se pensaba, lo que les permitió mejorar el cálculo.

2. La construcción de ejemplos:
   Para probar que el límite no puede ser mejor, crearon un grupo de 14 números muy especiales (usando una computadora para buscar la combinación perfecta) que cumple todas las reglas, pero donde es imposible salvar más de 8 personas. Esto demostró que el límite superior es real.

En resumen

Este artículo es como un manual de supervivencia para matemáticos:

1. Te dice que si tienes un grupo "casi perfecto" (débil), siempre puedes salvar exactamente la mitad para hacerlo perfecto.
2. Te dice que si tienes un grupo con reglas de distancia estrictas, siempre puedes salvar al menos el 53% para hacerlo perfecto, y que en el peor de los casos, el límite es el 57%.

Es un trabajo que cierra preguntas que habían estado abiertas durante décadas, transformando conjeturas en certezas matemáticas precisas. ¡Y lo mejor es que la respuesta final es tan simple como "la mitad"!

Resumen técnico

Resumen Técnico: Los Subconjuntos de Sidon Más Grandes en Conjuntos de Sidon Débiles

1. Planteamiento del Problema

El artículo aborda dos problemas fundamentales en la combinatoria aditiva relacionados con la densidad asintótica de los subconjuntos de Sidon dentro de conjuntos que poseen propiedades aditivas "cercanas" a ser de Sidon.

• Definiciones Clave:

  • Conjunto de Sidon ($S$): Un conjunto finito donde todas las sumas $x+y$ con $x, y \in S$ y $x \le y$ son distintas.
  • Conjunto de Sidon Débil ($A$): Un conjunto finito donde todas las sumas $x+y$ con $x, y \in A$ y $x < y$ son distintas (se permite la repetición en la suma $x+x$).
  • Conjunto $(4, 5)$: Un conjunto donde cualquier subconjunto de 4 elementos determina al menos 5 diferencias absolutas distintas entre sus 6 pares.
  • Funciones de Extremalidad:
    • $h(A)$: Tamaño máximo de un subconjunto de Sidon contenido en $A$.
    • $g(n) = \min \{ h(A) : |A|=n, A \text{ es Sidon débil} \}$.
    • $f(n) = \min \{ h(A) : |A|=n, A \text{ es conjunto } (4, 5) \}$.

• Preguntas de Investigación:

  1. Problema de Sárközy y Sós: ¿Existe el límite $\lim_{n \to \infty} g(n)/n$ y cuál es su valor?
  2. Problema de Erdős: Determinar la constante óptima $c^*$ tal que todo conjunto $(4, 5)$ de tamaño $n$ contenga un subconjunto de Sidon de tamaño al menos $c^* n$.

2. Metodología y Estrategia de Prueba

Los autores emplean una combinación de técnicas de teoría de grafos/hipergrafos, combinatoria aditiva y construcción explícita de conjuntos.

• Argumento de Subaditividad (Lema de Fekete):
  Para demostrar la existencia de los límites asintóticos, los autores prueban que las funciones $g(n)$ y $f(n)$ son subaditivas (es decir, $g(m+n) \le g(m) + g(n)$). Esto se logra mediante una construcción de "bloques": dados dos conjuntos $A$ y $B$, se escalan y trasladan ($qB + t$) de manera que las sumas (o diferencias) mixtas no colisionen con las internas, preservando así la propiedad de Sidon débil o $(4, 5)$.

  • Resultado: Esto garantiza la existencia de $\gamma^* = \lim g(n)/n$ y $c^* = \lim f(n)/n = \inf f(n)/n$.

• Marco de Hipergrafos de Progresiones Aritméticas (A.P.-hypergraphs):
  Utilizan la correspondencia entre subconjuntos de Sidon e conjuntos independientes en hipergrafos.

  • Se define un hipergrafo $H(A)$ donde las aristas son ternas que forman progresiones aritméticas de 3 términos (3-AP).
  • Lema Clave: Para un conjunto Sidon débil, un subconjunto es de Sidon si y solo si no contiene 3-AP. Por tanto, $h(A) = \alpha(H(A))$ (número de independencia).
  • Dado que $\alpha(H) + \tau(H) = n$ (donde $\tau$ es el número de transversal), el problema se reduce a acotar $\tau(H)$.

• Construcciones Explícitas y Búsqueda Computacional:

  • Para las cotas superiores, construyen conjuntos específicos con propiedades controladas.
  • Para el problema $(4, 5)$, utilizan una búsqueda exhaustiva asistida por IA para encontrar un conjunto de 14 puntos que maximice la densidad de no-Sidon, mejorando la cota superior.

3. Contribuciones y Resultados Principales

A. Resolución del Problema de Sárközy y Sós (Conjuntos Sidon Débiles)

• Teorema Principal: Determinan el valor exacto de $g(n)$ para todo $n \ge 1$:
  $$g(n) = \left\lfloor \frac{n+1}{2} \right\rfloor$$
• Consecuencia Asintótica: El límite existe y es exactamente:
  $$\gamma^* = \lim_{n \to \infty} \frac{g(n)}{n} = \frac{1}{2}$$
• Método de Prueba:
  • Cota Inferior: Usan el teorema de Chvátal-McDiarmid/Tuza sobre el número de transversal en hipergrafos 3-uniformes ($4\tau \le n + m$) combinado con la propiedad de que en un conjunto Sidon débil, el número de aristas$m \le n-2$. Esto lleva a$h(A) \ge n/2 + 1/2$.
  • Cota Superior: Construyen una familia de conjuntos $A_{2k+1}$ (basados en potencias de 2 y 3) que son Sidon débiles y tienen exactamente $k+1$ elementos en su mayor subconjunto de Sidon.

B. Mejora de las Cotas del Problema de Erdős (Conjuntos $(4, 5)$)

• Contexto: Gyárfás y Lehel habían demostrado previamente que $1/2 + \epsilon \le c^* \le 3/5$.
• Nuevo Resultado (Teorema 1.6): Los autores mejoran drásticamente ambas cotas:
  $$\frac{9}{17} \le c^* \le \frac{4}{7}$$
  (Nota: $9/17 \approx 0.529$y$4/7 \approx 0.571$).
• Mejora de la Cota Superior ($c^* \le 4/7$):
  • Construyeron explícitamente un conjunto $(4, 5)$ de 14 puntos ($A_{base}$) cuyo mayor subconjunto de Sidon tiene tamaño 8.
  • Esto da $f(14) \le 8$, y por tanto $c^* \le 8/14 = 4/7$. La construcción se verificó mediante búsqueda exhaustiva computacional.
• Mejora de la Cota Inferior ($c^* \ge 9/17$):
  • Utilizaron el hecho de que los hipergrafos $H(A)$ de conjuntos $(4, 5)$ son lineales y no contienen la configuración $F_7$ (un hipergrafo específico de 7 vértices).
  • Aplicaron una desigualdad de transversal más fuerte de Henning y Yeo para hipergrafos lineales libres de $F_7$: $17\tau(H) \le 5n + 3m$.
  • Combinando esto con $m \le n-2$, obtienen $\tau(H) \le \frac{8}{17}n$, lo que implica $\alpha(H) \ge \frac{9}{17}n$.

4. Significado e Impacto

• Cierre de un Problema Abierto: El artículo resuelve completamente la pregunta de Sárközy y Sós, proporcionando no solo el límite asintótico, sino la fórmula exacta para cualquier tamaño finito $n$.
• Avance en Combinatoria Extremal: Mejora significativamente las cotas conocidas para el problema de Erdős sobre conjuntos $(4, 5)$, reduciendo la brecha entre la cota inferior y superior de manera sustancial.
• Conexión Estructural: Refuerza la conexión profunda entre propiedades aditivas (sumas y diferencias) y la estructura de hipergrafos (independencia y transversales), demostrando cómo restricciones locales en diferencias (propiedad $(4, 5)$) imponen restricciones globales en la estructura de progresiones aritméticas.
• Uso de IA: El artículo destaca el uso de inteligencia artificial para la búsqueda de contraejemplos y construcciones explícitas (el conjunto de 14 puntos), marcando un precedente en la metodología de investigación en combinatoria pura.

En resumen, Ma y Tang demuestran que la densidad de los subconjuntos de Sidon en conjuntos "casi Sidon" es exactamente $1/2$para el caso débil, y acotan la densidad para el caso$(4, 5)$ en un rango mucho más estrecho que el previamente conocido.