AI Proved What?

Episode 166, October 2026

Erdős distances in 3D and up?

A preprint claims that n points in three or more dimensions always determine at least a constant times n2/d different distances, the order of the integer grid

Covers result 166 in OpenAI’s catalog: its one paper. See its connections to other results and the work it cites.

Play Episode 166: Erdős distances in 3D and up? A 3 by 3 by 3 grid of points with the segments from one corner coloured by their nine lengths (our drawing).

5:48. English captions available. The video loads from YouTube when you press play.

Chapters

  1. 0:00The problem
  2. 1:32The claim
  3. 2:44How the proof goes
  4. 5:02Where it stands

The claim, in plain words

Put n points in space and list the distances between pairs. Random points give all different distances; a grid repeats them heavily. The grid of td points in d dimensions has squared distances that are whole numbers from 1 to d(t − 1)2, so fewer than d·n2/d distances. “Erdős introduced the problem in 1946.” In the plane the square grid gives about n/√log n, and Guth and Katz, building on Elekes and Sharir, proved at least a constant times n/log n, so “the planar problem consequently has a different conjectural order”. In three or more dimensions the conjecture predicts a constant multiple of n2/d. As the paper recounts, the bounds in three dimensions climbed from the square-root scale (Clarkson, Edelsbrunner, Guibas, Sharir and Welzl) through 77/141 (Aronov, Pach, Sharir and Tardos), 0.5643 (Solymosi and Vu) and 3/5 (Guth–Katz with Solymosi–Vu) to n2/3 − o(1) by Tidor, Yu and Zakharov in August 2026, whose methods the paper credits as close antecedents along with Bardwell-Evans and Sheffer. In four and five dimensions that gave n8/17 − o(1) and n3/8 − o(1), short of 1/2 and 2/5, and the exponents fell short in every higher dimension too. A 2020 manuscript by Aksoy Yazici claimed the full result but “was withdrawn by the author because the proof of its Theorem 1.2 is not correct”.

Result 166 is a single OpenAI preprint, The higher-dimensional Erdős distinct-distances conjecture (103 pages, dated September 23, 2026). Theorem 1.1: “For every integer d ≥ 3, there is a constant cd > 0 such that every finite set P ⊂ ℝd of n ≥ 2 distinct points satisfies |∆(P)| ≥ cd n2/d.” “This resolves the higher-dimensional Erdős distinct-distances conjecture positively.” The constant factor is the point: “An estimate |∆(P)| ≥ n2/d−o(1) does not by itself imply Theorem 1.1”, since the ratio to n2/d could still sink to zero slowly.

What it doesn’t claim

No value of cd: the proof argues by contradiction along sequences, with parameters that grow “sufficiently slowly”. Nothing new about the plane; the Guth–Katz bound is re-proved in an appendix because the induction on dimension uses it. No pinned version, where a single point sees that many distances, and nothing about which sets come closest to the minimum, unit distances, other norms or other fields. As our own illustration of why the best constant is open, three shapes of about 7,000 points give different ratios of distances to n2/3: 1.64 for the 19 × 19 × 19 cube, 1.28 for a ball of grid points and 1.12 for a ball of the face-centred lattice.

Where it stands

Posted as a preprint
OpenAI, 103 pages, dated September 23, 2026
Peer reviewed
Not yet
Checked in Lean
None listed; one uncatalogued file covers small ingredients, not the theorem

Last checked October 19, 2026. The preprint has not been revised since it was added to the repository in its initial commit on October 6, 2026. The release catalog lists no Lean formalization for this result, and none appears in the repository’s formalization list. The repository does contain one file, not linked from the catalog, PolynomialIsolation.lean (392 lines, using only Mathlib), which proves small ingredients: the separating polynomials, the Cauchy–Schwarz count of equal-length pairs, the reformulation of a failure as a sequence, and an elementary bound n ≤ (2|∆| + 1)d, which gives only about half the d-th root of n distances. By our scan it has no unproved steps, and we have not rebuilt it. Theorem 1.1 is not formalized. The paper is not among those OSVerify reviewed, and we have seen no expert review.

How the proof goes

  1. Suppose it failed. Take point sets whose distance count divided by n2/d tends to zero, in the lowest dimension where this happens. Lower dimensions then limit how many points can lie on a line, a circle, a plane or any smaller flat (Lemma 2.1).
  2. Many repeats. By Cauchy–Schwarz, few distances force many ordered pairs of equal-length segments: at least the number of segments squared divided by the number of lengths, counting a segment paired with itself. A product of one factor per distance gives a polynomial of degree 2|∆| that is 1 at a chosen point and 0 at every other point.
  3. Crossing flats. Two segments of equal length are matched by a rigid motion. In suitable coordinates the motions taking p to q form a flat Fp,q, the complexified point-pair flats of Bardwell-Evans and Sheffer, and Fp,q meets Fp′,q′ exactly when |p − p′| = |q − q′|. Few distances produce a huge web of crossing flats.
  4. Sparse cones. The central part of the paper (Theorem 6.1) shows that the directions from each point cannot crowd onto cones of small total degree, so polynomials of degree about n2/d can tell them apart. This yields global and local bounds on how the flats concentrate; in three dimensions a separate section (Theorem 7.1) limits motions that match very many points.
  5. One random sample. Keep each flat with a fixed small probability. Comparing ranks, a polynomial of degree about n2/d vanishes on every kept flat but not on all flats. A flat where it is not zero is crossed by more kept flats than the local bound allows, and on it the polynomial cannot vanish at all the crossings. No constant depends on how fast the ratio falls, which gives a fixed cd.

The numbers in the video

  • Our grids: 3 × 3 × 3 has 27 points, 351 pairs and 9 distances; 10 × 10 × 10 has 1,000 points, 499,500 pairs and 144 distances. Distances divided by n2/d: 1.44 at 103 and 1.98 at 1003; 246 distances for 104 points in four dimensions and 331 for 105 in five.
  • Our 200 random points: 19,900 pairs, all different distances.
  • Our planar grids: the ratio to n/√ln n stays near 1.11 from 900 to a million points (299,230 distances at n = 106).
  • Our Cauchy–Schwarz check on the 103 grid: 3,396,220,944 ordered pairs of equal-length segments, against the bound 499,5002/144 ≈ 1.73 × 109.
  • Our separating polynomial on the unit cube: degree 6, value 1 at one corner and 0 at the other seven, 15/128 at the centre.
  • Our check of the flat equation: a skew solution exists exactly when the two segments have equal length, in 1,000 of 1,000 random cases.
  • Our shapes of about 7,000 points: ratios 1.64, 1.28 and 1.12. The Lean elementary bound for the 103 grid: 4.5 against the actual 144.

Read the source

The paper

OpenAI groups related papers into one result; this one has a single paper.

Transcript

Read the full script

0:00The problem

Put n points in space and measure the distance between every pair. How few different distances can there be? Erdős introduced this question in 1946. Scatter the points at random, and every distance differs: in our check, 200 random points gave 19,900 pairs and as many distances. A grid does much better. A 3 by 3 by 3 cube has 27 points and 351 pairs, but only 9 distances. A 10 by 10 by 10 cube has 1,000 points, nearly half a million pairs, and only 144 distances, because every squared distance is a whole number of limited size. In d dimensions, a grid of n points has fewer than d times n^(2/d) distances. The plane is different: there the square grid has about n over the square root of log n distances, only a slowly growing factor below n, and, as the paper recounts, Guth and Katz proved a lower bound of order n over log n. In three or more dimensions the prediction is that nothing beats the grid by more than a constant factor. As the paper recounts, lower bounds crept upward over the years, from about the square root of n in three dimensions, and an August 2026 preprint by Tidor, Yu and Zakharov reached n^(2/3) in three dimensions, up to a loss smaller than any power of n. In four dimensions and up, the best exponents still fell short. A 2020 manuscript that claimed the full result was withdrawn by its author.

1:32The claim

Result 166 is a 103-page OpenAI preprint, dated September 23. Its theorem: for every dimension d of at least three, there is a constant c_d, greater than zero, such that every set of n points in d-dimensional space, with n at least two, determines at least c_d times n^(2/d) distinct distances. That matches the grid up to a constant factor. The paper stresses that a bound whose exponent falls short of 2/d by an amount shrinking to zero would not be enough: the ratio could still sink to zero, slowly, and the proof has to rule that out. In three dimensions, what is new is removing that vanishing loss; from four dimensions up, the exponent itself is new. The paper gives no value for the constant: the proof argues by contradiction, along sequences, and never computes one. It says nothing new about the plane, it does not find a single point that sees that many distances, and it says nothing about which sets come closest. The grid fixes the order, not the constant: in our check with about seven thousand points, a ball of lattice points has noticeably fewer distances than a cube.

2:44How the proof goes

Suppose the theorem failed: point sets whose distance counts fall ever further below the grid’s. Take the lowest dimension where this happens. Then lower dimensions behave, so no line, circle, plane or smaller flat can hold too many of the points. Few distances force many repeats: by the Cauchy-Schwarz inequality, if about n squared over two segments share only M lengths, then, counting ordered pairs and letting a segment pair with itself, at least that number squared over M pairs of segments have equal length. And few distances give low-degree polynomials that separate points: multiplying one factor per distance gives a polynomial that is one at a chosen point and zero at all the others. Two segments of equal length are matched by a rigid motion. For each point p and each point q of a rotated copy, the motions taking p to q form, in suitable coordinates, a flat in a space of motions, and two of these flats meet exactly when the corresponding segments have equal length; we checked this algebra numerically. So few distances produce a huge web of crossing flats. This rigid-motion picture goes back to Elekes and Sharir, and Guth and Katz, in the plane; the paper’s flats are a complex version of Bardwell-Evans and Sheffer’s, and it credits the Tidor, Yu and Zakharov preprint for several ingredients. The central part of the paper, the sparse-cones theorem, rules out a way to escape: the directions from each point lying on cones of unusually small total degree, which would stop polynomials of degree about n^(2/d) from telling them apart. In three dimensions, a separate section limits the motions that match very many points. The knockout is a random sample. Keep a small fixed fraction of the flats. Comparing ranks, using a global bound on how many flats a low-degree surface can contain, gives a polynomial of degree about n^(2/d) that vanishes on every kept flat but not on all of them. On a flat where it is not zero, so many kept flats cross that, by a local version of that bound, it cannot vanish at all those crossings. That contradiction, with constants that never depend on how fast the counts fall, gives a fixed constant c_d in each dimension.

5:02Where it stands

The paper is not peer reviewed and has not been revised. There is no Lean formalization of the theorem. The repository contains one uncatalogued Lean file of about 400 lines, which we did not run, covering small ingredients: the separating polynomials, the Cauchy-Schwarz count of equal-length pairs, the reformulation as a sequence, and an elementary bound of only about half the d-th root of n. The paper is not among those OSVerify reviewed, and we have seen no expert review. If it holds, in three dimensions and up, grids are within a constant factor of the fewest distances possible, though the constant is unknown, and the plane keeps its own gap.

Spot a mistake?

This episode simplifies on purpose, but it shouldn’t be wrong. If something is, open an issue on GitHub or leave a comment on YouTube. Corrections are noted here with a date.