Erd\H{o}s's diameter conjecture for separated distances fails in high dimensions

Los autores refutan la conjetura de Erdős sobre el diámetro de conjuntos de puntos con distancias separadas en espacios de alta dimensión, demostrando mediante una construcción formalizada en Lean 4 que existen configuraciones cuyo diámetro es significativamente menor al límite propuesto.

Lo esencial

¡Hola! Vamos a desglosar este artículo matemático complejo como si fuera una historia sobre organizar una fiesta en un espacio gigante.

El Problema: La Fiesta de los Invitados Distantes

Imagina que eres el anfitrión de una fiesta con $n$ invitados. Tienes una regla estricta para la seguridad: cualquier par de invitados debe mantener una distancia mínima de 1 metro entre sí. No pueden estar más cerca que eso.

Ahora, el famoso matemático Paul Erdős (un genio que planteó muchos acertijos) se hizo una pregunta hace décadas:

"Si tengo que mantener a todos mis invitados separados por al menos 1 metro, ¿qué tan grande tiene que ser el tamaño total de mi casa (el diámetro) para que todos quepan?"

Erdős conjeturó (supuso) que, sin importar cuántas dimensiones tenga tu casa (si es plana como un papel o tiene miles de dimensiones), el tamaño de la casa tendría que crecer muy rápido, casi como el cuadrado del número de invitados ($n^2$). Es decir, si duplicas los invitados, el tamaño de la casa debería cuadruplicarse.

La Sorpresa: ¡La Conjetura Falla en Espacios Altos!

El autor de este artículo, Boon Suan Ho, dice: "¡Eso no siempre es cierto!".

Ha demostrado que si construyes tu casa en un espacio con muchas dimensiones (imagina un edificio con miles de pisos, pero todos conectados de formas extrañas), puedes acomodar a tus invitados cumpliendo la regla de "1 metro de distancia" en un espacio mucho más pequeño de lo que Erdős pensaba.

En lugar de necesitar un tamaño de $n^2$, el espacio necesario puede ser aproximadamente $0.89 \times n^2$. Es decir, el espacio es un 11% más pequeño de lo que se creía necesario.

¿Cómo lo hizo? (La Analogía de los Relojes y los Músicos)

Para lograr este truco, el autor usó una construcción muy ingeniosa que combina dos ideas:

1. El Mapa Secreto (Conjuntos de Diferencia de Singer):
   Imagina que tienes un reloj con un número muy específico de horas (basado en números primos). El autor eligió un grupo especial de personas (puntos) en este reloj de tal manera que, si calculas la distancia entre cualquier par de ellos, obtienes una distancia única. Ningún par tiene la misma distancia que otro par. Es como si cada pareja de amigos tuviera su propia "canción" de distancia.

2. La Escultura de Múltiples Dimensiones:
   Ahora, imagina que en lugar de poner a la gente en una habitación normal, los colocas en una estructura gigante compuesta por muchos círculos (polígonos) girando a diferentes velocidades.

   • El autor asignó "pesos" o "volumen" a cada círculo.
   • Usó una fórmula matemática (una serie de Fourier) para asegurar que las distancias entre los puntos fueran casi iguales, pero con un pequeño truco: las distancias crecían de forma muy suave y predecible.

El Truco Final:
Como las distancias entre los puntos eran casi iguales pero crecían muy lentamente al final, el autor pudo estirar toda la figura un poco. Al estirarla, la distancia más pequeña entre dos puntos se convirtió en exactamente 1 metro (cumpliendo la regla). Pero, gracias a la magia de las altas dimensiones y la forma de la curva, el punto más lejano (el diámetro) no tuvo que estirarse tanto como se esperaba.

La Analogía de la "Goma Elástica"

Piensa en una goma elástica con muchos nudos atados a lo largo de ella.

• La visión de Erdős: Creía que para que los nudos no se toquen, tendrías que estirar la goma hasta que fuera muy larga.
• La visión de este paper: El autor encontró una forma de enrollar esa goma en un espacio multidimensional (como una bobina de cable muy compleja) y estirarla de tal manera que los nudos se separan, pero la bobina total ocupa menos espacio del que pensábamos.

¿Por qué es importante?

1. Rompe un mito: Demuestra que las reglas que funcionan en 1 o 2 dimensiones (como en un plano) no necesariamente se aplican en dimensiones gigantes.
2. La Geometría es extraña: Muestra que en dimensiones muy altas, el espacio se comporta de maneras contraintuitivas. Puedes "empaquetar" puntos de forma más eficiente de lo que intuimos.
3. El uso de la IA: Curiosamente, el autor menciona que usó una Inteligencia Artificial avanzada (GPT-5.4 Pro) para descubrir la construcción matemática y otra herramienta para verificar la prueba. Es un ejemplo fascinante de cómo la IA está empezando a ayudar a resolver problemas matemáticos profundos.

En Resumen

El artículo dice: "Erdős tenía razón para espacios pequeños, pero si te metes en un universo con miles de dimensiones, puedes organizar a tus invitados más cerca de lo que pensabas, violando su conjetura original."

Es una victoria para la geometría de altas dimensiones y una prueba de que, a veces, la intuición humana falla cuando el espacio se vuelve demasiado complejo.

Resumen técnico

Resumen Técnico: Fallo de la Conjetura de Erdős en Dimensiones Altas

1. El Problema y el Contexto

El artículo aborda una pregunta clásica planteada por Paul Erdős sobre la geometría de conjuntos de puntos en espacios euclídeos.

• La Conjetura: Erdős preguntó si, para cualquier conjunto $C$ de $n$ puntos en un espacio euclídeo (independientemente de la dimensión), donde todas las distancias pairwise (entre pares) son mutuamente separadas por al menos 1 (es decir, $||x-y| - |x'-y'|| \ge 1$ para pares distintos), el diámetro del conjunto debe ser al menos $(1+o(1))n^2$.
• Estado anterior: Se sabía que esto era cierto en dimensión 1. Sin embargo, la forma exacta en dimensiones superiores había recibido poca atención directa. La literatura existente se centraba en casos planares o en distancias "casi iguales", pero no en la separación estricta de todas las distancias en dimensiones arbitrarias.

2. Metodología y Construcción

El autor demuestra que la conjetura es falsa en general construyendo explícitamente contraejemplos para infinitos valores de $n$. La construcción se basa en la teoría de números combinatoria y análisis armónico:

1. Conjuntos Diferencia de Singer:

   • Se utiliza un teorema clásico de Singer para un entero $q$ (potencia de un primo).
   • Se define $m = q^2 + q + 1$ y $n = q + 1$.
   • Existe un conjunto $D \subset \mathbb{Z}/m\mathbb{Z}$ con $|D| = n$ tal que cada residuo no nulo en $\mathbb{Z}/m\mathbb{Z}$ se puede escribir de manera única como $a-b$ con $a,b \in D$.
   • Esto genera $N = \binom{n}{2}$ pares no ordenados, indexados por sus "separaciones cíclicas" $s \in \{1, \dots, N\}$.

2. Inmersión en Espacio de Alta Dimensión:

   • Se construye un conjunto de puntos $Y_m \subset \mathbb{R}^{2N}$ (donde $2N = m-1$) colocando los puntos sobre un producto ponderado de polígonos regulares $m$-gonos.
   • Las coordenadas se definen mediante una suma de vectores trigonométricos con pesos $W_r$.

3. Perfil de Distancias y Perturbación de Frecuencia:

   • El objetivo es diseñar los pesos $W_r$ de tal manera que las distancias resultantes $d_s$ formen una secuencia estrictamente creciente con diferencias decrecientes.
   • Se introduce una perturbación de una sola frecuencia: Se definen coeficientes $c_j$ para impares $j \ge 1$ (con $c_1 = 7/8$ y $c_j = 1/j^2$ para $j \ge 3$).
   • Los pesos $W_r$ se calculan sumando estos coeficientes según la congruencia módulo $m$.
   • Esto define una función $H(\theta)$ y una función de distancia $G(\theta) = \sqrt{H(\theta)}$.

4. Propiedades Clave de la Construcción:

   • Concavidad Estricta: Se demuestra que la función $G(\theta)$ es estrictamente creciente y estrictamente cóncava en $(0, \pi)$.
   • Separación de Distancias: Debido a la concavidad, las diferencias entre distancias consecutivas ($d_{s+1} - d_s$) disminuyen a medida que $s$ aumenta. Por lo tanto, la menor diferencia es la última: $d_N - d_{N-1}$.
   • Escalado: Se escala el conjunto $Y_m$ por un factor $\lambda_m = 1/(d_N - d_{N-1})$ para obtener el conjunto final $X_m$. Esto garantiza que la diferencia mínima entre cualquier par de distancias sea exactamente 1, cumpliendo la condición de separación.

3. Resultados Principales

El teorema principal (Teorema 1) establece que para infinitos valores de $n$ (específicamente $n = q+1$ donde $q$ es potencia de primo), existe un conjunto $X_n \subset \mathbb{R}^{n^2-n}$ tal que:

1. Todas las distancias pairwise son mutuamente separadas por al menos 1.
2. El diámetro del conjunto está acotado superiormente por:
   $$\text{diam}(X_n) \le \left( 1 - \frac{1}{\pi^2} + o(1) \right) n^2$$
   Donde $1 - 1/\pi^2 \approx 0.89867$.

Este resultado contradice directamente la conjetura de Erdős, que sugería un límite inferior de $(1+o(1))n^2$.

4. Contribuciones Clave

• Refutación de la Conjetura: Se demuestra que el límite inferior propuesto por Erdős no se mantiene uniformemente en todas las dimensiones. La geometría de los puntos en dimensiones altas permite "comprimir" el diámetro más allá de lo que se pensaba posible bajo la restricción de distancias separadas.
• Construcción Explícita: A diferencia de pruebas de existencia no constructivas, este trabajo proporciona una construcción algebraica y geométrica explícita basada en conjuntos diferencia de Singer y series de Fourier.
• Formalización en Lean 4: El autor destaca que la prueba ha sido completamente formalizada en el asistente de prueba Lean 4, lo que añade un nivel de verificación riguroso a los resultados matemáticos.
• Optimización de Constantes: En las observaciones finales, el autor sugiere que la constante $c^* \approx 0.898$ no es óptima. Mediante la optimización de los coeficientes de frecuencia, se estima que la constante podría reducirse hasta aproximadamente $0.854$.

5. Significado e Implicaciones

• Geometría de Dimensiones Altas: El trabajo ilustra cómo las restricciones de separación de distancias, que son muy restrictivas en dimensiones bajas (como la línea real), se vuelven mucho más flexibles en dimensiones altas, permitiendo configuraciones de puntos con diámetros sorprendentemente pequeños.
• Nuevas Preguntas Abiertas: Aunque la conjetura falla en dimensiones variables, queda abierto el problema de si, para una dimensión fija $d \ge 2$, el límite $(1+o_d(1))n^2$ podría ser válido. Es decir, ¿la dimensión fija impone una restricción que la dimensión variable no tiene?
• Interacción IA-Matemáticas: El artículo menciona explícitamente el uso de modelos de IA avanzados (GPT-5.4 Pro y Harmonic Aristotle) para descubrir la construcción y formalizar la prueba, marcando un hito en el uso de herramientas de IA para la investigación matemática de alto nivel y la verificación formal.

En conclusión, el papel de Ho cierra una pregunta abierta de décadas mostrando que la intuición geométrica basada en dimensiones bajas no se extiende a dimensiones arbitrarias para este problema específico, redefiniendo los límites conocidos sobre la relación entre la separación de distancias y el diámetro en espacios euclídeos.