Suresh Venkatasubramanian
OpenAI just announced that ChatGPT has disproved a conjecture about one of Erdos's most famous problems: the unit distance problem. openai.com/index/model-... This problem is personal to me: I spent time during my Ph.D mulling over it, and it hooked me into computational geometry. A thread: 1/n

An OpenAI model has disproved ...
An OpenAI model has disproved a central conjecture in discrete geometry

An OpenAI model solved the 80-year-old unit distance problem, disproving a major conjecture in discrete geometry and marking a milestone in AI-driven mathematics.

OpenAI
May 20 at 9:56pmWeb
Show threadSuresh Venkatasubramanian 5d ago
A complete post is here: blog.geomblog.org/2026/05/the-... The unit distance problem: Let P be a set of n points in the plane (amen). What is the maximum number of unit distances that can be achieved? (the amen is a running joke in my old field of computational geometry) 2/n

The unit distances problem
The unit distances problem

 OpenAI just announced that ChatGPT has disproved a conjecture about one of Erdos's most famous problems: the unit distance problem. This p...

Show threadSuresh Venkatasubramanian 5d ago
Note that this is really about duplicate distances (because if you get a bunch of pairs of points at distance d, you can scale the point set so that d = 1). It's also trivial to see that the maximum is at least n-1 (points evenly spaced on the line), and that the number is at most n-choose-2. 3/n
Show threadSuresh Venkatasubramanian 5d ago
So what's the answer? Erdos showed using a fairly complicated construction that you can get a set of points that has $n^{1 + 1/\log\log n}$ unit distances. On the other hand, a famous result from 1983 by Spencer, Szemederi and Trotter showed that you can't get more than $O(n^{4/3})$ distances. 4/n
Show threadSuresh Venkatasubramanian 5d ago
Erdos himself used a really elegant but weaker argument to show that you can't get more than $O(n^{3/2})$ distances. And the argument was cool and deceptive (in retrospect). To get a distance pair of 1, a circle of size 1 around a point must touch another point (and vice versa). 5/n
Show threadSuresh Venkatasubramanian 5d ago
Draw an edge between those two points when this happens. So here's a fun fact: you can't create a situation where two points are connected by edges to each of three other points. Formally you can't create a situation where there's a $K_{2,3}$ bipartite graph hidden inside the set of edges. 6/n
Show threadSuresh Venkatasubramanian 5d ago
By a well known result in graph theory this means this graph can't have too many edges in it (because if it did you'd eventually find one of these special graphs): specifically no more than $O(n^{3/2})$ edges. 7/n
Show threadSuresh Venkatasubramanian 5d ago
So there's a limit. But what's the real limit? A long standing conjecture was that you could NOT get anything nontrivially more than n pairs. Specifically that you couldn't get $\Omega(n^{1 + \epsilon})$ pairs for any $\epsilon$. This is sad because the gap between this, and $n^{4/3}$ is huge. 8/n
Show threadSuresh Venkatasubramanian 5d ago
This conjecture is wrong. ChatGPT proved it by building a complicated generalization of Erdos's construction that is indeed of size $\Omega(n^{1 + \epsilon})$ for some $\epsilon > 0$. This was a tantalizing, infuriating, and beautiful problem that has resisted progress for a very long time. 9/n
Show threadSuresh Venkatasubramanian 5d ago
It's really impressive that an AI system has provided a proof for it. For more on the significance of the result and some interpretation of the proof technique, check out the companion article. cdn.openai.com/pdf/74c24085... 10/n,n=10

cdn.openai.com/pdf/74c24085-1...
Show threadSuresh Venkatasubramanian 5d ago
The problem, like