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

En utilisant une construction formalisée en Lean 4, les auteurs réfutent la conjecture d'Erdős sur le diamètre des ensembles de points à distances séparées en démontrant qu'il existe des contre-exemples en haute dimension dont le diamètre est strictement inférieur à la borne conjecturée.

L'essentiel

🌟 Le Titre : "Le pari d'Erdős a perdu (dans les hautes dimensions)"

Imaginez que vous êtes un architecte chargé de construire une ville (un ensemble de points) dans un espace géométrique. Vous avez une règle très stricte : chaque paire de routes (distances) entre deux bâtiments doit avoir une longueur différente, et ces longueurs doivent être espacées d'au moins 1 mètre.

Le célèbre mathématicien Paul Erdős a fait un pari il y a longtemps : il pensait que si vous respectiez cette règle, votre ville devrait inévitablement être très grande. Plus précisément, il croyait que le diamètre de la ville (la distance entre les deux bâtiments les plus éloignés) devrait être énorme, proportionnel au carré du nombre de bâtiments ($n^2$).

Le résultat de ce papier ? Ce pari est faux, mais seulement si vous construisez votre ville dans un espace à très nombreuses dimensions (comme un monde invisible à 100 ou 1000 dimensions). L'auteur, Boon Suan Ho, a construit une "ville" où les routes sont bien espacées, mais où la ville elle-même reste étonnamment petite.

---

🏗️ L'Analogie : Le Collier de Perles et le Tambour

Pour comprendre comment l'auteur a trompé le pari, imaginons deux choses :

1. Le Collier de Perles (La structure mathématique)

L'auteur utilise une structure mathématique ancienne et élégante appelée un ensemble de différence de Singer.

• L'image : Imaginez un collier de perles disposé sur un cercle. Il y a un nombre spécial de perles (disons $q+1$).
• La magie : Si vous mesurez la distance entre n'importe quelle paire de perles sur ce cercle, vous obtiendrez des longueurs uniques. C'est comme si chaque paire de perles avait sa propre "signature" de distance. C'est la base de la construction.

2. Le Tambour à N Dimensions (L'espace géométrique)

Ensuite, l'auteur ne place pas ces perles sur un simple cercle 2D. Il les projette dans un espace gigantesque à $N$ dimensions (comme un tambour avec des milliers de peaux différentes).

• L'analogie : Imaginez un tambour géant où chaque peau résonne à une fréquence différente. L'auteur fait vibrer ces peaux avec des poids précis pour créer des points dans cet espace.
• Le résultat : Grâce à une astuce mathématique (une "perturbation à une fréquence"), il arrange les vibrations de telle sorte que les distances entre les points deviennent de plus en plus serrées à mesure qu'on regarde les paires les plus éloignées.

---

📉 Le Tour de Magie : Comment on triche (légèrement)

Le secret de l'auteur réside dans la façon dont il organise les distances.

1. Le problème : Pour que toutes les distances soient séparées d'au moins 1, il faut que l'écart entre la distance la plus courte et la suivante soit de 1, entre la suivante et celle d'après aussi, etc.
2. L'astuce : L'auteur arrange les distances pour qu'elles soient très proches les unes des autres à la fin de la liste.
   • Imaginez une échelle où les premiers barreaux sont espacés de 10 mètres, mais les derniers barreaux sont si proches qu'ils sont presque collés.
   • En mathématiques, cela signifie que la différence entre la plus grande distance et la deuxième plus grande est très petite.
3. Le redimensionnement : Puisque l'écart entre les deux plus grandes distances est minuscule, l'auteur peut "agrandir" tout le système (comme zoomer sur une photo) pour que cet écart devienne exactement 1 mètre.
   • Conséquence : Comme il a dû agrandir le système pour respecter la règle de l'écart de 1, toutes les autres distances ont aussi augmenté, mais la taille totale de la ville (le diamètre) reste beaucoup plus petite que ce qu'Erdős avait prévu.

---

🧠 Pourquoi c'est important ?

• La leçon principale : La géométrie change radicalement quand on passe de notre monde à 3 dimensions à des mondes à 1000 dimensions. Ce qui semble "évident" ou "inévitable" dans notre monde quotidien (comme le pari d'Erdős) peut s'effondrer dans des dimensions supérieures.
• La précision : L'auteur montre que le diamètre peut être environ 89,8 % de ce que Erdős pensait être le minimum. C'est une différence énorme en mathématiques !
• La touche moderne : Le papier mentionne que la preuve a été vérifiée par une intelligence artificielle (Lean 4), ce qui ajoute une couche de confiance moderne à ce résultat classique.

En résumé

L'auteur a construit un labyrinthe mathématique dans un espace à très haute dimension. Il a réussi à placer des points de telle sorte que chaque distance entre eux soit unique et bien séparée, tout en gardant le tout plus compact que ce que la théorie prévoyait. C'est comme réussir à faire tenir une foule immense dans une petite pièce, à condition que chaque personne ait une distance unique avec ses voisins, mais seulement si la pièce a assez de dimensions invisibles pour se plier sur elle-même !

Le verdict : Le pari d'Erdős tient dans notre monde à 3 dimensions, mais il s'effondre dans l'univers infini des hautes dimensions.

Résumé technique

1. Le Problème : La Conjecture d'Erdős sur le Diamètre

L'article s'attaque à une question ouverte posée par Paul Erdős concernant la géométrie des ensembles de points dans l'espace euclidien.

• Contexte : Soit $C$ un ensemble de $n$ points dans un espace euclidien. On suppose que toutes les distances paires distinctes entre ces points sont séparées d'au moins 1 (c'est-à-dire que pour deux paires distinctes $\{x, y\} \neq \{x', y'\}$, on a $|||x-y| - |x'-y'|| \ge 1$).
• La Conjecture : Erdős a conjecturé que, quelle que soit la dimension de l'espace ambiant, le diamètre de cet ensemble (la distance maximale entre deux points) doit satisfaire la borne inférieure suivante :
  $$\text{diam}(C) \ge (1 + o(1)) n^2$$
  Cette conjecture a été prouvée pour la dimension 1, mais restait ouverte pour les dimensions supérieures. Erdős suggérait que la contrainte de séparation des distances force la configuration à s'étendre sur une échelle quadratique en $n$.

2. Méthodologie et Construction

L'auteur réfute cette conjecture en dimension élevée en construisant explicitement des contre-exemples pour une infinité de valeurs de $n$. La méthode repose sur une combinaison de théorie des nombres (ensembles de différence) et d'analyse harmonique.

A. Utilisation des Ensembles de Différence de Singer

La construction initie avec un ensemble de différence cyclique (Singer difference set).

• Soit $q$ une puissance d'un nombre premier.
• On définit $m = q^2 + q + 1$ et $n = q + 1$.
• Le théorème de Singer garantit l'existence d'un sous-ensemble $D \subset \mathbb{Z}/m\mathbb{Z}$ de taille $n$ tel que chaque résidu non nul modulo $m$ s'écrit de manière unique comme une différence $a-b$ avec $a, b \in D$.
• Cela permet d'indexer les $\binom{n}{2}$ paires non ordonnées de $D$ par les séparations cycliques $s \in \{1, \dots, N\}$, où $N = (m-1)/2$.

B. Réalisation Géométrique dans un Espace de Haute Dimension

Les points sont placés dans un espace de dimension $2N = m-1 \approx n^2$.

• Chaque point $t \in D$ est associé à un vecteur $v_t \in \mathbb{R}^{2N}$ défini comme un produit pondéré de polygones réguliers $m$-gones.
• Les coordonnées sont construites à l'aide de poids $W_r$ et de fonctions trigonométriques :
  $$v_t = \left( \sqrt{W_r/2} \cos(2\pi rt/m), \sqrt{W_r/2} \sin(2\pi rt/m) \right)_{1 \le r \le N}$$
• La distance euclidienne au carré entre deux points $v_t$ et $v_u$ dépend uniquement de la séparation cyclique $s$ de la paire $\{t, u\}$ :
  $$\|v_t - v_u\|^2 = \sum_{r=1}^N W_r \left( 1 - \cos\left(\frac{2\pi rs}{m}\right) \right)$$

C. Choix des Poids et Perturbation

Le cœur de la preuve réside dans le choix astucieux des poids $W_r$ pour contrôler le profil des distances.

• L'auteur définit une fonction $H(\theta)$ basée sur une série de Fourier avec des coefficients $c_j$ :
  $$H(\theta) = \sum_{j \text{ impair}} c_j (1 - \cos(j\theta))$$
• Les poids sont choisis de manière à ce que $W_r$ corresponde aux coefficients de Fourier associés.
• Une perturbation spécifique est introduite : $c_1 = 1 - \varepsilon$ (avec $\varepsilon = 1/8$) et $c_j = 1/j^2$ pour $j \ge 3$ impair.
• Cela conduit à une fonction de distance $d_s = G(2\pi s/m)$, où $G(\theta) = \sqrt{H(\theta)}$.

D. Propriétés de Concavité et Mise à l'Échelle

• L'auteur démontre que la fonction $G$ est strictement croissante et strictement concave sur $(0, \pi)$.
• Cette concavité implique que les écarts entre distances consécutives ($d_{s+1} - d_s$) sont décroissants. Par conséquent, le plus petit écart se situe entre les deux plus grandes distances ($d_N - d_{N-1}$).
• Pour satisfaire la condition de séparation (écarts $\ge 1$), l'ensemble est mis à l'échelle par un facteur $\lambda_m = 1/(d_N - d_{N-1})$.
• Le diamètre final de l'ensemble échelonné $X_m$ est alors $\text{diam}(X_m) = \lambda_m d_N = \frac{d_N}{d_N - d_{N-1}}$.

3. Résultats Principaux

Le résultat central est le Théorème 1 de l'article :

• Contre-exemple : Pour une infinité de $n$ (de la forme $q+1$), il existe un ensemble de $n$ points $X_n \subset \mathbb{R}^{n^2-n}$ dont les distances paires sont séparées d'au moins 1.
• Diamètre borné : Le diamètre de cet ensemble satisfait :
  $$\text{diam}(X_n) \le \left( 1 - \frac{1}{\pi^2} + o(1) \right) n^2$$
• Constante critique : La constante $c^* = 1 - 1/\pi^2 \approx 0.89867$ est strictement inférieure à 1.
• Conclusion : La conjecture de la borne inférieure $(1+o(1))n^2$ est fausse en haute dimension.

4. Signification et Implications

• Réfutation de l'uniformité dimensionnelle : L'article démontre que la borne inférieure conjecturée par Erdős ne peut pas être uniforme en fonction de la dimension de l'espace ambiant. En dimension suffisamment élevée (proche de $n^2$), on peut "comprimer" la configuration géométrique tout en maintenant la séparation des distances.
• Ouverture pour les dimensions fixes : La question reste ouverte pour une dimension fixe $d \ge 2$. Il est possible que la conjecture soit vraie pour chaque $d$ fixé, mais que la constante dépende de $d$ et tende vers 0 lorsque $d$ augmente.
• Optimisation potentielle : L'auteur note que la constante $c^*$ pourrait être encore améliorée (abaissée) en optimisant les coefficients $c_j$ ou en utilisant des familles de fréquences plus complexes. Une optimisation numérique suggère une constante potentielle d'environ $0.854$.
• Formalisation : La preuve est entièrement formalisée dans le langage de preuve Lean 4, garantissant une rigueur mathématique absolue. L'auteur mentionne l'utilisation de l'IA (GPT-5.4 Pro et Harmonic Aristotle) pour la découverte de la construction et la formalisation, bien que la vérification finale et la responsabilité des arguments mathématiques incombent à l'auteur.

En résumé, ce travail résout un problème ouvert majeur en combinatoire géométrique en montrant que la géométrie des espaces de haute dimension permet des configurations de points beaucoup plus denses que ce que la conjecture d'Erdős ne le prévoyait, en exploitant les propriétés des ensembles de différence et de l'analyse de Fourier.