How many different distances must occur in higher dimensions

← All digests

Family 166 · Combinatorics
Importance 5/5 · Provisional editorial rating
Sources consulted 2026-10-11

1. The question

Place $n$ distinct points in Euclidean space and measure all distances between them. Many pairs may have equal lengths: a square, for example, has six unordered pairs but only two distances. How small can the number of different distances be?

In dimensions three and above, the natural prediction is of order $n^{2/d}$, where $d$ is the dimension. An integer grid shows why this exponent cannot generally be improved. The manuscript in family 166 claims a matching lower bound for every point configuration, with a positive constant depending only on the fixed dimension.

The word “every” includes highly clustered points, points on algebraic surfaces, and sets with no spacing assumptions. The result is about the collection of all pairwise distances; it does not require all the distances to be visible from one chosen point.

2. Background and essential definitions

For a finite point set $P\subset\mathbb R^d$, define

$$\Delta(P)=\{\|p-q\|:p,q\in P,\ p\ne q\}.$$

This is a set of positive real numbers, so repeated distances appear only once. Its size $|\Delta(P)|$ is the statistic being minimized. Squaring every distance does not change that size because squaring is one-to-one on positive numbers.

Why the grid suggests the exponent

Take the grid $P=\{1,\ldots,t\}^d$, which has $n=t^d$ points. Every squared distance is an integer between one and $d(t-1)^2$. Hence

$$|\Delta(P)|\le d(t-1)^2=O_d(n^{2/d}).$$

The subscript in $O_d$ means the multiplicative constant may depend on dimension. This is an upper bound for a specific construction, so it shows that no universal lower bound with a larger power of $n$ can hold.

In three dimensions the predicted scale is $n^{2/3}$; in four it is $n^{1/2}$. Increasing the ambient dimension gives more freedom to repeat lengths, although the constants need not be uniform as the dimension grows.

Repetitions as an energy count

Let $m_\rho$ count ordered distinct point pairs at distance $\rho$. Then

$$\sum_{\rho\in\Delta(P)}m_\rho=n(n-1).$$

By the elementary Cauchy–Schwarz inequality,

$$\sum_\rho m_\rho^2 \ge\frac{n^2(n-1)^2}{|\Delta(P)|}.$$

The left side counts pairs of ordered segments having equal length. If there are few distinct distances, equal-length coincidences must be abundant. The geometric problem can therefore be attacked by bounding how many such coincidences a configuration permits.

3. Development history and previous partial results

Erdős introduced the distinct-distances problem in 1946. Incidence geometry supplied early approaches: one counts how points lie on circles or spheres, or how often a fixed length can recur. In three dimensions, increasingly refined incidence estimates improved the exponent toward the conjectured $2/3$.

Solymosi and Vu developed recursive comparisons between dimensions, obtaining substantially improved general bounds. Those recurrences distinguish total distances from distances pinned at one point. Mixing the two versions would give misleading comparisons, so M1 uses the total-distance statements when tracing its predecessors.

A different approach represents equal-length segments through rigid motions. Elekes and Sharir developed this viewpoint in the plane. Guth and Katz combined it with polynomial methods and ruled-surface geometry to prove a planar lower bound of order $n/\log n$. Their method converts a distance problem into a problem about intersections of geometric objects in a larger parameter space.

Bardwell-Evans and Sheffer extended the rigid-motion reduction to higher dimensions. The resulting objects are higher-dimensional affine flats, and their possible concentration inside algebraic varieties becomes a major obstacle.

A recent paper by Tidor, Yu and Zakharov gives $n^{2/3-o(1)}$ distinct distances in three dimensions. The new manuscript identifies that work’s motion geometry and degree-sensitive estimates as close antecedents. It claims both a constant-factor three-dimensional bound and the optimal exponent with constant factor in every higher fixed dimension.

The planar problem has a different conjectured order: the square grid supplies roughly $n/\sqrt{\log n}$ distances. Thus simply inserting $d=2$ into the new $n^{2/d}$ formula would make a false prediction. The theorem explicitly starts at dimension three.

4. What the new manuscripts claim

M1’s Theorem 1.1 states that for every integer $d\ge3$, there is a constant $c_d>0$ such that every set of $n\ge2$ distinct points in $\mathbb R^d$ satisfies

$$|\Delta(P)|\ge c_d n^{2/d}.$$

The constant is independent of $n$, the coordinates, the spacing and any concentration of points on lower-dimensional sets. Dimension is fixed before the estimate is applied.

Together with the grid construction, this determines the minimum possible order of growth up to dimension-dependent constant factors. It does not identify the optimal constant or classify all nearly extremal point sets.

A bound $n^{2/d-o(1)}$ would be weaker. For example, a hypothetical value $n^{2/d}/\log n$ has that exponent form but has ratio to $n^{2/d}$ tending to zero. The source’s claim excludes even arbitrarily slow decay of this ratio.

The statement is global: it counts the union of distances over all pairs. It does not assert that one point determines $c_dn^{2/d}$ distances, much less that every point does. Pinned questions are treated separately in the collection, including the planar results in family 167.

5. Why the advance matters

Importance: 5/5. The claimed theorem resolves a central extremal question in discrete geometry across all higher fixed dimensions. Its simple conclusion is sharp in order and makes no generic-position assumptions.

The constant factor is a substantive part of the advance. Getting arbitrarily close to an exponent can still leave an unbounded multiplicative gap. Closing that gap requires an argument sensitive to concentration at scales too subtle for a single fixed power-saving estimate.

The proposed method also develops connections among distances, rigid motions, polynomial interpolation and algebraic concentration. These tools address a recurring geometric difficulty: a configuration may hide most of its complexity on a special surface, so an argument must understand that concentration rather than assume it away.

6. The main idea

Assume too few distances in the first failing dimension

The source argues by considering the smallest dimension where the conclusion could fail. Along a hypothetical sequence of counterexamples, set

$$B=n^{1/d},\qquad A=B^2=n^{2/d}, \qquad M=1+|\Delta(P)|.$$

Failure means $M/A\to0$. Lower-dimensional results limit how many points can lie in proper affine subspaces, but more general algebraic varieties still need attention.

The argument examines displacement directions from each point. It selects a positive fraction of point pairs so that, at each endpoint, low-degree polynomials can independently distinguish the retained directions. This is an interpolation property: prescribed values at those directions can be realized by suitable polynomials.

The selection must be symmetric. Keeping a pair from one endpoint but discarding it from the other would break the later equal-distance correspondence.

Rule out concentration at many degree scales

The main obstruction is that most directions might lie on a small collection of low-degree curves, producing sparse cones from their centers. Such concentration would make polynomial evaluations dependent.

M1 analyzes the point set through successive polynomial equations, recording when each equation lowers the dimension of the containing variety. Hilbert functions measure how many independent polynomial restrictions remain; Bézout-type bounds control intersections through the degrees of the equations.

Rather than choosing one degree scale, the source compares several windows of degrees. This multiscale analysis is designed to handle $M/A$ tending to zero at any rate. Special limiting configurations require separate endpoint arguments, since a loss by even a slowly growing factor would spoil the claimed constant bound.

Encode equal distances as intersections of flats

Take a generically rotated copy of the point set. Pairs consisting of one original point and one copied point define affine flats in a parameter space for rigid-motion data. Equal distances between the corresponding segments translate into intersections of these flats.

The earlier energy calculation supplies many such intersections when distances are few. The direction-selection property prevents the local intersections from becoming indistinguishable to low-degree polynomials. Additional estimates control families associated with motions matching unusually many points.

Finally, the manuscript randomly selects a small fraction of the flats. Global polynomial-dimension estimates provide a polynomial vanishing on the selected family but not on every retained flat. Yet each retained flat meets so many selected neighbors that local concentration estimates force the polynomial to vanish there too. The incompatible conclusions rule out the assumed deficit.

This is the familiar polynomial-method tension in a refined setting: there are enough coefficients to impose selected zeros, but geometry forces more zeros than a nonzero polynomial can sustain.

7. Scope, limitations, and open questions

The estimate holds for fixed dimension at least three. It makes no claim of uniform constants or useful bounds when dimension increases with the number of points.

The exact minimum number of distances, the best constants and the classification of extremal configurations remain separate questions. Matching the grid’s order does not imply that every nearly optimal configuration resembles a grid.

The result concerns ordinary Euclidean distance over the real numbers. Finite-field distance problems and distances induced by other norms have different algebraic features and require separate hypotheses.

The planar sharp-order problem is not settled by this theorem, and pinned conclusions cannot be inferred merely by taking the union of distances. These distinctions identify where the claim fits among the surrounding distance questions.

8. Sources and further reading

M1’s Theorem 1.1 states the constant-factor result. Sections 1.2–1.3 explain why the constant matters and outline the four stages. Section 2 assembles the argument; later sections establish the multiscale geometry, rich-motion estimates and polynomial concentration inputs.

The primary papers linked in Section 3 develop the planar method, higher-dimensional reduction and recent three-dimensional estimate. Wikipedia’s Erdős distinct distances problem is optional background for the grid examples.

Source manuscripts

• M1. OpenAI, The higher-dimensional Erdős distinct-distances conjecture (September 23, 2026).

Sources consulted on 11 October 2026 at repository revision fd4aeeb. Download the manuscript citations.