OpenAI Model Disproves a Core Conjecture in Discrete Geometry

00:00 02:38

Listen to the article

For nearly 80 years, mathematicians have been working on a question that appears deceptively simple: if you place $n$ points in the plane, what is the maximum number of pairs that are exactly distance $1$ apart?

This is the unit distance problem for the plane, first posed by Paul Erdős in 1946. It is one of the best-known problems in combinatorial geometry and is famous for being easy to state but extremely hard to solve. In Research Problems in Discrete Geometry by Brass, Moser, and Pach (2005), it is described as “perhaps the most famous and easiest to explain difficult problem in combinatorial geometry.” Noga Alon, a leading combinatorial mathematician at Princeton University, has called it “one of Erdős’s favorite problems.” Erdős himself even offered a prize for solving it.

Today, we are announcing a breakthrough on the unit distance problem. Since Erdős’s original work, the prevailing view has been that the “grid” construction shown below is essentially optimal for maximizing the number of unit-distance pairs. OpenAI’s internal model disproved this long-standing conjecture, giving an infinite family of examples with a polynomial improvement. The proof has been verified by an external group of mathematicians. They also wrote a companion paper explaining the argument and placing the result in context.

This result is especially notable for how it was discovered. The proof did not come from a model trained specifically for mathematics, nor from a system scaffolded for proof search, nor from a system tailored to the unit distance problem. Instead, it came from a general-purpose reasoning model. As part of a broader effort to evaluate whether frontier models can contribute to cutting-edge research, we tested it on a set of Erdős problems. In this case, the model produced a proof solving an open problem.

This proof is a major milestone for both the mathematics and AI communities. It marks the first significant open problem in mathematics solved autonomously by AI. It also shows the depth of reasoning that today’s systems can support. Mathematics is a particularly crisp test of reasoning: the problems are precisely defined, candidate proofs can be checked, and even a long argument only works if the reasoning is coherent from start to finish. The solution to this problem is also remarkable because it uses an unexpectedly sophisticated idea from algebraic number theory to attack a problem in elementary geometry.

Fields Medalist Tim Gowers described the result as “a milestone in AI mathematics” in the companion paper. Noted number theorist Arul Shankar said, “It appears to me that this paper shows that current AI models are no longer merely assistants to human mathematicians, but can generate original and ingenious ideas and implement them.”

Comments from mathematicians on the result

1 of 4

“This is one of Erdős’s favorite problems, and I heard him talk about it repeatedly in lectures. One can safely say that every mathematician working in combinatorial geometry has thought about it, and probably many mathematicians in other areas have thought about it at least a little… The OpenAI internal model’s solution of this problem strikes me as an outstanding achievement. It has solved a long-standing open problem. The fact that the correct answer is not $n 1 + o \left(\right. 1 \left.\right)$n 1+o(1) is surprising, and the construction and analysis make elegant and skillful use of rather sophisticated algebraic number theory tools.”

“There is no doubt that the solution of the unit distance problem is a milestone in AI mathematics. If this paper had been written by a human and submitted to Annals of Mathematics, and I were asked for a rushed opinion on whether it should be accepted, I would unhesitatingly recommend acceptance. I have not seen AI-generated proofs that come anywhere close to this standard.”

“The model’s chain of thought (CoT) is very interesting. In particular, what stands out is that the majority of the thinking is in the direction of constructing counterexamples to a widely believed upper bound, rather than trying to prove the upper bound. This shows that the model has good intuition and is willing to challenge approaches that the community believes are unlikely to succeed, and it tends to try construction first… It appears to me that this paper shows that current AI models are no longer merely assistants to human mathematicians, but can generate original and ingenious ideas and carry them out.”

“This is a very impressive piece of work, and I would accept it into any journal without hesitation. In fact, I worked on this problem briefly myself and tried to construct a counterexample, but made no progress… Even knowing the line of attack, this construction is just overwhelming difficult, let alone coming up with it yourself.”

Noga Alon
Tim Gowers
Arul Shankar
Jacob Tsimerman
Noga Alon
Tim Gowers
Arul Shankar
Jacob Tsimerman

The proof is available here (opens in a new window). A companion paper written by leading external mathematicians is here (opens in a new window). An excerpted version of the model’s chain of thought is available here (opens in a new window).

Image 1: A dense black network diagram, with connected nodes forming a square pattern.

The previously known construction with many unit distances from an expanded grid.

The unit distance problem

Let $u(n)$ denote the maximum number of unit-distance pairs among $n$ points in the plane. It is easy to construct examples with linear growth. If you place $n$ points on a single line, you get $n - 1$ pairs, and a square grid gives roughly $2n$ pairs. The best construction known until now came from expanded square grids and achieved considerably more. For a constant $C$, one can reach $n^{1 + C / log ⁡ log ⁡ \left(\right. n \left.\right)}$. Since $log ⁡ log ⁡ \left(\right. n \left.\right)$ diverges to infinity as $n$ grows, the extra term in the exponent tends to $0$. In other words, these constructions grow only slightly faster than linearly. For decades, this growth rate was widely believed to be nearly optimal.

OpenAI Model Upends a Core Conjecture in Discrete Geometry

OpenAI Model Disproves a Core Conjecture in Discrete Geometry

The unit distance problem