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

This paper disproves Erdős's conjecture that every $n$-point set in Euclidean space with pairwise distances at least 1 apart must have a diameter of at least $(1+o(1))n^2$ by constructing a counterexample in high dimensions where the diameter is bounded by approximately $(1-1/\pi^2)n^2$, a result that has been fully formalized in Lean 4.

The Gist

The Big Question: How Big Does a Crowd Have to Be?

Imagine you are organizing a party in a giant, empty room. You have a rule for your guests: No two pairs of people can stand at the exact same distance from each other.

To make it even stricter, let's say that if you measure the distance between any two guests, and then measure the distance between any other two guests, those two distances must be different. In fact, they must be at least 1 meter apart from each other on the "distance scale."

So, if Guest A and Guest B are standing 5 meters apart, Guest C and Guest D cannot be standing 5.1 meters apart. They must be at least 6 meters apart (or 4 meters, but not in that tiny 5-to-6 zone).

The Big Question (Erdős's Conjecture):
The famous mathematician Paul Erdős asked: "If you have a huge number of guests ($n$), and you follow this strict 'no-tiny-gaps' rule, how big does the room need to be?"

Specifically, he guessed that the room's diameter (the distance from the farthest person on the left to the farthest person on the right) would have to be roughly $n^2$.

He thought: "If you force all the distances to be unique and spaced out, the people will be forced to spread out so much that the whole group will be massive."

The Plot Twist: The High-Dimensional Escape

This paper, written by Boon Suan Ho (with help from advanced AI), says: "Erdős was wrong, but only if you go to a very high-dimensional universe."

In our normal 3D world (or even 2D), the rule might hold true. But in a world with hundreds or thousands of dimensions (think of a hyper-cube with many more directions than up/down/left/right), you can cheat the system.

The Analogy: The "Perfectly Spaced" Dance Floor

Imagine a dance floor with thousands of dimensions.

1. The Setup: You have $n$ dancers.
2. The Rule: Every pair of dancers must have a unique distance, and no two distances can be "close" to each other.
3. The Trick: Instead of spreading out in a straight line (which would make the room huge), the author arranges the dancers on a complex, multi-layered geometric shape (like a giant, twisted donut made of many rings).

By using a special mathematical pattern called a Singer Difference Set (which is like a secret code that ensures every "step" size is unique), the author places the dancers in a way that:

• All their distances are unique.
• The gaps between distances are all at least 1 meter.
• BUT, the dancers are all huddled relatively close together.

The Result: A Smaller Room

The author proves that for certain numbers of people, the room doesn't need to be $n^2$ big. It only needs to be about $0.89 \times n^2$.

Think of it like this:

• Erdős's Prediction: "If you have 100 people, the room needs to be 10,000 units wide."
• The New Discovery: "Actually, in a high-dimensional room, you can fit those 100 people in a room that is only about 8,900 units wide, while still following the strict rules."

It's a small difference in percentage, but in the world of math, proving that a "perfect" lower bound is actually false is a huge deal. It means the geometry of high-dimensional space is much more flexible and "squishy" than we thought.

How Did They Do It? (The Magic Recipe)

The author didn't just guess; they built a specific machine to create these points:

1. The Ingredients: They used a prime number (a special type of integer) to create a mathematical "skeleton."
2. The Weighting: They assigned different "weights" (importance) to different directions in the high-dimensional space.
3. The Curve: They used a specific curve (related to the number $\pi$) to decide how far apart the distances should be.
4. The Squeeze: They stretched the whole arrangement just enough so that the smallest gap between distances became exactly 1 meter.

Because of the way the math works in high dimensions, this stretching didn't blow up the size of the room as much as Erdős predicted.

The "AI" Twist

There is a fascinating footnote in this paper. The author admits that AI helped discover the construction.

• An AI model (GPT-5.4 Pro) helped come up with the initial idea of how to arrange the points.
• Another AI (Harmonic Aristotle) helped write the code to prove it was correct in a computer language called Lean 4.
• The human author then double-checked everything to make sure the math was real and not just a hallucination by the AI.

The Bottom Line

This paper is a "spoiler alert" for a 50-year-old math puzzle. It tells us that while Paul Erdős's intuition was brilliant, the universe of high-dimensional geometry has a few more tricks up its sleeve. You can pack points with very specific, separated distances into a smaller space than anyone expected, provided you have enough dimensions to hide in.

In short: High-dimensional space is a better hiding spot than we thought. You can fit a lot of unique distances into a surprisingly small room.

Technical Summary

1. Problem Statement

The paper addresses a question posed by Paul Erdős regarding the geometric constraints of point sets in Euclidean space.

• The Conjecture: Erdős conjectured that for any set $C$ of $n$ points in Euclidean space where all $\binom{n}{2}$ pairwise distances are mutually distinct and separated by at least 1 (i.e., $||x-y| - |x'-y'|| \ge 1$ for distinct pairs), the diameter of the set must satisfy:
  $$\text{diam}(C) \ge (1 + o(1))n^2$$
  Crucially, this bound was proposed to be independent of the dimension of the space.
• The Goal: The author aims to disprove this conjecture in high dimensions by constructing a counterexample where the diameter is significantly smaller than $n^2$, specifically bounded by $c^* n^2$ where $c^* < 1$.

2. Methodology

The proof relies on an explicit construction using Singer difference sets and harmonic analysis (Fourier series) to control the distribution of distances.

A. Combinatorial Foundation: Singer Difference Sets

• Let $q$ be a prime power. Define $m = q^2 + q + 1$ and $n = q + 1$.
• By Singer's Theorem, there exists a cyclic $(m, n, 1)$-difference set $D \subset \mathbb{Z}/m\mathbb{Z}$.
• This set $D$ has the property that every non-zero residue in $\mathbb{Z}/m\mathbb{Z}$ can be uniquely represented as a difference $a - b$ with $a, b \in D$.
• Consequently, the $\binom{n}{2}$ unordered pairs from $D$ correspond bijectively to the cyclic separations $s \in \{1, \dots, N\}$, where $N = (m-1)/2 = \binom{n}{2}$.

B. Geometric Construction

• The author constructs a point set $Y_m$ in $\mathbb{R}^{2N} = \mathbb{R}^{m-1}$.
• Points are defined as vectors $v_t$ for $t \in D$, where each $v_t$ is a weighted product of regular $m$-gons. Specifically, the coordinates involve trigonometric functions weighted by coefficients $W_r$.
• The squared Euclidean distance between two points $v_t$ and $v_u$ with cyclic separation $s$ is given by:
  $$d_s^2 = \sum_{r=1}^N W_r \left( 1 - \cos\left(\frac{2\pi rs}{m}\right) \right)$$
• This formula allows the author to treat the set of pairwise distances as a function $G(\theta)$ evaluated at discrete points.

C. Weight Selection and Concavity

• The weights $W_r$ are constructed using a specific series of coefficients $c_j$ (where $c_1 = 7/8$ and $c_j = 1/j^2$ for odd $j \ge 3$).
• This choice leads to a distance profile function $H(\theta) \approx \frac{\pi \theta}{4} - \epsilon(1-\cos \theta)$.
• Key Insight: The author proves that the resulting distance function $G(\theta) = \sqrt{H(\theta)}$ is strictly increasing and strictly concave on $(0, \pi)$.
• Implication of Concavity: Because $G$ is concave, the gaps between consecutive distances ($d_{s+1} - d_s$) decrease as $s$ increases. Therefore, the smallest gap between any two distinct distances occurs at the largest separation ($d_N - d_{N-1}$).

D. Scaling

• The set is scaled by $\lambda_m = 1/(d_N - d_{N-1})$.
• Since the smallest gap is $d_N - d_{N-1}$, scaling by its reciprocal ensures that all pairwise distances in the final set $X_m$ are separated by at least 1.

3. Key Results

The paper establishes the following theorem:

Theorem 1: Let $c^* = 1 - \frac{1}{\pi^2} \approx 0.89867$. For infinitely many $n$ (specifically $n = q+1$ for prime powers $q$), there exists an $n$-point set $X_n \subset \mathbb{R}^{n^2-n}$ such that:

1. All pairwise distances are mutually separated by at least 1.
2. The diameter satisfies:
   $$\text{diam}(X_n) \le (c^* + o(1))n^2$$

Asymptotic Analysis:
Through the evaluation of the limit of the ratio $\frac{G(\pi)}{2\pi G'(\pi)}$, the author derives the constant $c^* = 1 - \frac{1}{\pi^2}$.

• This value is strictly less than 1, directly contradicting Erdős's conjecture that the diameter must be at least $(1+o(1))n^2$.
• The construction takes place in dimension $d = n^2 - n$, which grows quadratically with $n$.

4. Significance and Contributions

• Disproof of a Long-Standing Conjecture: The paper definitively shows that Erdős's lower bound for the diameter of separated-distance sets does not hold uniformly across all dimensions. It fails in high dimensions.
• Explicit Construction: Unlike non-constructive existence proofs, this paper provides an explicit algebraic and geometric construction based on Singer difference sets and harmonic analysis.
• Formal Verification: A notable feature of the paper is that the proof is fully formalized in Lean 4. The author acknowledges the use of AI tools (GPT-5.4 Pro and Harmonic Aristotle) to discover the construction and formalize the proof, though the mathematical arguments were independently verified by the author.
• Open Questions:
  • The result leaves open the question of whether the conjecture holds for fixed dimensions $d \ge 2$. The counterexample requires the dimension to grow with $n$.
  • The constant $c^* \approx 0.898$ might not be optimal. The author notes that numerical optimization of the coefficients suggests the constant could potentially be lowered to $\approx 0.854$.

5. Conclusion

Boon Suan Ho successfully refutes the dimension-free version of Erdős's diameter conjecture. By leveraging the properties of Singer difference sets to create a point configuration with a highly controlled, concave distance distribution, the author demonstrates that in sufficiently high dimensions, one can pack $n$ points with separated distances into a space with a diameter significantly smaller than $n^2$. This highlights a fundamental difference between the geometry of point sets in fixed dimensions versus high-dimensional spaces.