Distinct distances at the higher-dimensional lattice scale

Source and verification

This article explains family 166 of the October 6, 2026 OpenAI collection. Research conclusions are attributed to its manuscripts. The review covers statements, introductions, and selected proof mechanisms; it is not an independent verification of the complete proofs.

🏷️ Distinct distances and the lattice benchmark

For a finite set $P\subset {\mathbb{R}}^d$, let

$$\begin{array}{c}\Delta (P)\\ =\{\Vert x-y\Vert :x,y\in P,x\ne y\}\end{array}$$

be the set of positive distances it determines. Repeated occurrences of the same distance are counted once.

Manuscript claim

For every fixed integer $d\ge 3$, there is $c_d>0$ such that every set of $n\ge 2$ distinct points in ${\mathbb{R}}^d$ satisfies

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

The constant is independent of the positions of the points. (OpenAI, 2026)

The exponent has a simple optimality example. Take $P=\{1,\dots ,t{\}}^d$, so $n=t^d$. Every squared distance is an integer between one and $d(t-1{)}^2$, giving at most $d(t-1{)}^2=O_d(n^{2/d})$ possibilities. Thus the asserted exponent cannot be increased for arbitrary point sets.

This is a bound on all distances together, not on the distances from a specified point. The theorem is stated for $d\ge 3$ and should not be imported into the planar case. It also gives a fixed positive constant at the exact exponent, which is stronger than a bound of the form $n^{2/d-o(1)}$.

🏷️ Equal distances and a second-moment count

Suppose $P$ has $N$ points and only $M$ distinct positive distances. Partition its ordered distinct pairs by their lengths, and let $a_j$ be the size of the $j$th class. Since ${\sum }_j{a}_j=N(N-1)$, Cauchy–Schwarz gives

$$\sum _{j=1}^M{a}_j^2\ge \frac{N^2(N-1{)}^2}{M}.$$

Thus few distances force many equal-distance pairings. The challenge is turning these repeated lengths into geometric incidences while controlling concentrated exceptional configurations.

The manuscript argues by a least-dimensional counterexample sequence. It sets $B=N^{1/d}$ and $A=B^2$, and supposes that $(1+|\Delta (P)|)/A$ tends to zero. This ratio may tend to zero arbitrarily slowly. A proof that requires a fixed power saving at the outset would not establish the constant-factor theorem.

🏷️ Directions and rigid-motion parameters

The first major reduction retains a positive proportion of pairs, symmetrically at both endpoints, whose direction data satisfy an interpolation independence condition at degree comparable to $A$. Informally, too many retained directions cannot all lie in a small collection of low-complexity geometric cones.

Such concentration would defeat a polynomial incidence argument, so it must be excluded before polynomial sampling begins. The manuscript uses multiscale profiles, projections from endpoints, and proper lower-dimensional cuts to rule it out. The scales are selected in a window around $B$ without losing the constant needed at the final exponent. These are substantive geometric lemmas; this article treats their exact role as an interface rather than developing the excluded algebraic-geometric machinery.

For ordered points $p,q$, let $F_{pq}$ be the affine set of pairs $(Z,c)$ with $Z^{\mathsf{T}}=-Z$ satisfying

$$Z\frac{p+q}{2}+c=\frac{p-q}{2}.$$

This parametrizes a chart of rigid-motion matching data. If one motion sends $p$ to $q$ and another point to its corresponding partner, the displacement vectors $u,w$ satisfy

$$Z(u+w)=u-w.$$

Taking the scalar product with $u+w$ shows $\Vert u{\Vert }^2-\Vert w{\Vert }^2=0$, since a skew-symmetric matrix has $v\cdot Zv=0$. Equal lengths are therefore the compatibility condition for these affine incidence constraints.

🏷️ Removing rich exceptional motions

The second-moment count supplies many links between the pair-flats. Some links may concentrate at motions that match an unusually large portion of one point set to another. Such rich motions must be handled separately.

In dimension three, the source proves a bound at scale $O(N^4/A)$ for the relevant squared matching counts. It removes exceptional contributions in both orientations of the pair data. Since the supposed counterexample has $M/A\to 0$, this error is negligible compared with the useful $N^4/M$ links. Higher dimensions require their own size estimates after the least-dimension reduction.

Keeping both orientations is important: removing a bad set only at the first endpoint can leave the same concentration hidden at the second endpoint. The symmetric retention established earlier is designed to make the final incidence structure usable from either side.

🏷️ The polynomial contradiction

After pruning, each retained flat has far more than $A^{d-1}$ relevant neighbors. A local interpolation lemma says that a polynomial of degree comparable to $A$, if not identically zero on one retained flat, can vanish on only $O(A^{d-1})$ of its permitted neighboring flats.

The proof now chooses one random sample that serves two purposes simultaneously. It is small enough that the global space of polynomials retains a nontrivial degree of freedom, yet it meets enough neighbors of every flat to exceed the local vanishing bound. Separate samples for the two requirements would not give the needed polynomial.

A polynomial vanishing on the sample but nonzero on an appropriate retained flat then contradicts the local estimate. This closes the argument only because the earlier concentration exclusions, rich-motion removal, and sampling estimates retain fixed constants at the scale $A=N^{2/d}$.

🏷️ Key steps and proof outlines

Keep independent directions at both endpoints

Set $M=1+|\Delta (P)|$, $A=N^{2/d}$, and suppose $M/A\to 0$ along a counterexample sequence. The source first obtains a dense undirected set of physical pairs with a useful rank property: for any subset $S$ of partners of a fixed point, the rank of their degree-$\lfloor A\rfloor$ direction evaluations is at least $c_1|S|$, for a fixed $c_1>0$. The geometric concentration arguments establish this input. (OpenAI, 2026)

Here is the subsequent finite-dimensional selection argument. Take a maximal edge subset whose evaluations are independent at both endpoints. Every omitted edge is blocked at at least one endpoint, meaning its direction evaluation is in the span of the selected directions there. Charge it to one such endpoint. If the selected degree at $p$ is $s_p$, the charged vectors have rank at most $s_p$, so the rank property bounds their number by $s_p/c_1$. Summing gives

$$\#\{\text{omitted edges}\}\le \frac{2}{c_1}\#\{\text{selected edges}\}.$$

A fixed positive fraction survives. Moreover, independence means one can interpolate a polynomial that equals one on any chosen direction and zero on the others. These separators persist under later deletions. Selecting separately at the two endpoints would not automatically give one dense symmetric pair set.

Convert repeated lengths into a high-degree graph

Rotate a second copy $Q$ of $P$ generically. The new graph has vertices $(p,q)\in P\times Q$; two vertices are adjacent when both underlying physical pairs were selected and have equal length. If $s_{\rho }$ counts selected unordered pairs of length $\rho$, its edge count is $2{\sum }_{\rho }{s}_{\rho }^2$, hence at least $c{N}^4/M$ by Cauchy–Schwarz.

In dimension three, delete links belonging to exceptionally rich rigid motions. The source’s squared match-count bound makes their total contribution $O(N^4/A)=o(N^4/M)$. Both orientations of isometries are included. In all dimensions, repeatedly remove vertices of degree below $E_0/(2N^2)$, where $E_0$ is the edge count before this pruning. Fewer than $N^2$ removals delete less than $E_0/2$ edges, so a nonempty graph survives with

$$\delta \ge c{N}^2/M,\frac{\delta }{A^{d-1}}\ge c\frac{A}{M}⟶\infty .$$

The identity $N^2=A^d$ explains the scale. No fixed power saving in $M/A$ is needed.

A local incidence equation identifies the dangerous concentration

Inside the flat associated with $(p,q)$, a neighbor with displacements $u=p^{\prime }-p$ and $w=q^{\prime }-q$ imposes $Z(u+w)=u-w$. Equal lengths imply $(u+w)\cdot (u-w)=0$, as required for skew-symmetric $Z$.

If a collection of local parameters lies in the source’s exceptional linear configuration, polarization gives $u_i\cdot u_j=w_i\cdot w_j$. Equal Gram matrices imply that $u_i\mapsto w_i$ defines an isometry on their real spans: any linear relation has squared norm zero after transport. Extend that isometry to the ambient space. All those neighbors are therefore matches of one rigid motion. The rich-motion deletion handles precisely this obstruction in dimension three; for $d\ge 4$, the trivial cap $N=A^{d/2}\le A^{d-2}$ already has the required size.

The manuscript’s concentration theorem then supplies two interfaces. Globally, the degree-$D$ restriction space on $m$ retained pair-flats has dimension at least $c_{4}m{A}^{s_0}$, where $D=\lfloor A\rfloor$ and $s_0=d(d-1)/2$ is the flat dimension. Locally, a nonzero polynomial of degree at most $A$ on one flat can vanish on at most $C{A}^{d-1}$ of its neighbor flats. These are the substantive geometric inputs; their internal algebraic-geometric proofs are outside this post’s prerequisites.

One sample must satisfy both requirements

Sample each retained flat independently with a small fixed probability $\theta$. Markov’s inequality gives probability at least one half that at most $2\theta m$ flats are sampled. Their restriction rank is at most

$$2\theta m\left(\genfrac{}{}{0ex}{}{D+s_0}{s_0}\right)\le C_4\theta m{A}^{s_0}.$$

Choose $\theta$ so this is below the global rank lower bound. Meanwhile, a Chernoff bound shows that each flat has at least $\theta \delta /2$ sampled neighbors except with probability $e^{-c\theta \delta }$. A union bound over at most $N^2$ flats makes this hold everywhere with probability tending to one. Both events therefore hold for the same sample.

The rank gap produces a degree-$D$ polynomial vanishing on every sampled flat but not identically on some retained flat $F$. Its restriction to $F$ vanishes on more than $C{A}^{d-1}$ distinct sampled neighbor flats, contradicting the local bound. This closes the constant-factor contradiction at the exact lattice exponent.

See Also

• Planar distance fibers treats the different phenomena of almost-all pinned distances and repeated unit lengths in dimension two.
• Complete-graph crossing numbers also combines a finite-dimensional polynomial space with geometric constraints on its evaluations.

🏷️ Manuscripts and verification scope

• The higher-dimensional Erdős distinct-distances conjecture — pinned manuscript and companion source.

No family scope page was present at lean/docs/166.md in the pinned snapshot. This does not establish that all related formalization code is absent. No Lean build, axiom audit, or manuscript-to-formal-statement equivalence check was performed for these notes.

OpenAI collection provides prerequisites and the reading sequence; coverage register records completed and pending families.

🐻  OpenAI 2026. The higher-dimensional Erdős distinct-distances conjecture.