This winter, I worked on an AI-ideated resolution to the 659th problem posed by Paul Erdős. I had spent a good chunk of my holiday attempting to verify the model’s solution. My attitude was first dismissive, then uncertain, then excited. I shared the results with two of my professors1 for a second look then, on January 13th, submitted it to the Erdős forum.
Five hours later, about to go to bed, I checked the web forum. My heart started pounding. The problem page was now green, and I had two direct replies from Terence Tao. My write-up had been accepted.
The gap the model closed was much smaller than I initially realized. The novelty amounted to pointing out a minor case analysis no one had previously caught, but my note stands—to the very best of my knowledge—as the first complete solution to this problem.2
This post is part of a series on Erdős #659 and the broader field of AI-for-Math. I have a lot to say about the topic, but right now I’m only trying to present the problem in a clean, publicly accessible way. My hope is that anyone, even people who hate math, can read this and emerge feeling like they understand the problem.3
The Problem
Distinct Distances
This problem focuses on distances and points, and particularly the idea of “distinct distances” within a collection of points. We say that a set of points has “distinct distances” equal to the number of unique distances between points in the set.
For one example: the set of points [(0, 0), (2, 0), (0, 2), and (2, 2)] make a square with two “distinct distances:” the edge and the diagonal. But if we swap out the point (2, 0) for (3, 0), we now have five distinct distances:
This idea—the number of “distinct distances” in a set—is key to understanding the problem.
Problem #659
The problem I resolved with AI, as presented on the Erdős Problems forum, has three clauses.
Is there a set of n points in R2
This clause is simple: we need to choose a set of n points.
Instead of picking four specific points like we did above, we need to pick a set of points based on some rule —an equation— that tells us how to select these points (R2 is a fancy way of saying that these are your ordinary, (x, y) points).
This rule/equation could just be the set [(n, 1)] for every whole number n.4 If n = 6, the set is [(1, 1), (2, 1), (3, 1), (4, 1), (5, 1), (6, 1)].
So the first step is just to pick a set of points.
Such that every subset of 4 points determines at least 3 (distinct) distances
Now that I have a set, I need to be able to pick 4 points out of this set and know that these four points determines at least 3 distinct distances.
Think back to my square above. If the set contains the four points [(0, 0), (2, 0), (0, 2), and (2, 2)], it will fail this condition.
A valid set can contain [(0, 0), (3, 0), (0, 2), (2, 2)], as we showed above how this determines five distinct distances, but I can never add the point (2, 0). In fact, any set that contains a square will fail this condition.
At this point, you can hopefully kind of see how it might be easy to prove that a set fails this condition, but tricky to prove that a set satisfies it. If you understand that, you’re in a good place.
Yet the total number of distinct distances is « n/√(log n)
This final clause is a constraint on the total number of distinct distances in the set.5
What does this mean? The set [(0,1), (1,1), (2,1)] has 2 distinct distances. If I add (3,1) I have 3 distinct distances, and with (4,1) I now have 4.
More generally, the set [(n, 1)] will always have n - 1 distinct distances.
The notation « is a little confusing here. We can understand it as asking whether the number of distinct distances in our set is less than or “on the order of” some limiting value.6 This means that when we construct our set of n points, the constraint asks whether it contains a number of distinct distances on the order of some number. That number happens to be n/√(log n).
Don’t worry too much about the « notation or the value itself. What matters is that you understand how this constraint means that a set needs to have some limit on the number of distinct distances as n gets bigger.
That’s the problem! We need to be able to figure out a rule to construct a set that satisfies the two properties:
Every subset of 4 points determines at least 3 (distinct) distances, and
The total number of distinct distances is « n/√(log n)
Finding such a set resolves this problem.7
The Solution
The solution is to take a regular grid, and stretch it by √2.
Gemini 3.0 Pro, in an answer later refined by GPT-5.2 (extended thinking), found a set that satisfies those two conditions:8
This is written in a formal syntax, but it’s a fairly simple rule. The set of all positive points looks like this:
You can think of it as a rule and an explanation. The ‘rule’ is that we are including all (x, y) pairs to the set. The ‘explanation’ is that
x is between 0 and m - 1, and
y is also between 0 and m - 1.
In this case, m can be any number. Here is an example where m = 5.
How many items are in this set? We can count 25 points in this example, and this makes sense—the set contains 5 rows of 5.
In fact, the size of the set, the number of n points in it, is
The Squashed Lattice
Now back to the solution. There is only one difference here: instead of picking all x and y values, we pick all x values and all y values times the square root of two.
As the square root of two is about 1.4, the point (1, 1) would become (1, ~1.4) and (2, 2) → (2, ~2.8). This is what it looks like when m = 5:
It is sometimes informally called a ‘squashed lattice,’ because it’s a regular grid pattern that looks kind of squished.9
The Forbidden Shapes
Now, remember we need to show two things about this set. The first is
every subset of 4 points determines at least 3 (distinct) distances.
How can we show this?
The very first comment on the Erdős forum offers an approach. Desmond Weisenberg pointed out that there are only six ways—six shapes—that 4 points can fail this condition. These are the six:
With a little bit of searching, Gemini and GPT were able to find a source to prove it. This is great! We no longer need to worry about weird abstract theory; as long as we know that none of these shapes appear in the squashed lattice we can prove the first condition is true.
I don’t want to go through the proof in detail, but this is how the rest conceptually works:
Of the six forbidden configurations, four contain an equilateral triangle, so it is enough to show that equilateral triangles, squares, and the “regular-pentagon trapezoid”10 do not appear in the squashed lattice.11
This is not too difficult to prove: if all vertical sides are the length of a whole number, and all horizontal sides are a multiple of √2, then they can never possibly equal one another. This style of argument works for all three shapes, and we can therefore show that this squashed lattice satisfies the local constraint.
A Comment on Novelty
I mentioned above that the gap here was much smaller than I initially realized. That gap is nothing more than the inclusion of the Regular-Pentagon Trapezoid to the case analysis. The idea to stretch the lattice by an irrational number had been proposed, the five other shapes had been excluded, and the bound below had been proven.12
The Global Bound
The second thing we need to show is that
The total number of distinct distances is « n/√(log n).
This part is not intuitive.
At a high level, the approach is to manipulate the problem to resemble a pattern from number theory, then pluck out a theorem that completes the missing gap. Unlike with the forbidden shapes constraint above, there isn’t much to ‘get.’ Gemini drew from its extensive knowledge of math theorems, pattern-matched one that almost proved the constraint, and manipulated the problem to make it fit.
Manipulation
If you take any two points from the set and square the distance between them, it will look something like this:
This comes from the pythagorean theorem.13
Remember that
x is between 0 and m - 1, and
y is also between 0 and m - 1.
And since both x and y are less than m, the question becomes:
And so we know that all squared distances are less than 3m^2, but greater than 0.
Why is this helpful?
The problem is now about counting outputs from a formula. Instead of asking how many distances the set creates, we can ask how many numbers (up to 3m^2) can be written in the form
\(x^2+2y^2\)
where x and y are both whole numbers less than m. This turns the question from a counting problem into one from number theory, and there is a theorem here that deals with this exact question.14
Bernays’ Theorem (informal):
Numbers that can be written in the form
\(x^2+2y^2 < N\)get less and less common as the upper bound N gets larger, growing at the rate
\(\frac{N}{\sqrt{\log N}}.\)
We have our bound!
I’m skipping over a few steps, and simplifying it for the sake of the example, but honestly not by much. All of that manipulation above was to show that the theorem applies to this set and therefore satisfies the second condition.
The next post in this series will discuss my process and personal experience working on the problem. All commentary will be in that post; this is mostly written as a reference to help contextualize the problem (and hopefully provide a legible example). I want to make one point though:
Why Does This Matter?
As a standalone math result, it really doesn’t.
This is a very specific version of a series of problems in combinatorics15 which are already pretty niche. Adam Sheffer had already written about this problem and made the connection between the forbidden shapes and Bernay’s theorem. Prior work was only missing the regular pentagon trapezoid in the case analysis of the forbidden shapes.
I did write it up as an arXiv note, and feel reasonably confident that it’s worth adding there16 as a reference for problem, but this is far from a publishable result. It’s interesting as a case analysis of the kinds of problems AI can solve, and it’s worth clearing away the ‘low-hanging fruit’ of the Erdős problems, but this finding will not make waves.
It’s still pretty cool.
Shoutout to Professors Doyle and Winkler!
A team from DeepMind independently found an equivalent solution using a custom gemini-based agent. They published this result as part of a large survey of Erdos problems around a month after my submission.
If you instead like math and have a reasonably strong background in it, you might enjoy cross-referencing this post with the formal write-up.
Also known as a line.
I know n/√(log n) is ugly. We don’t actually work with it; if it helps, you can think of it as just Some Large Number.
For those who are a little more comfortable with the math, it’s the same as big O notation and/or multiplying by some scalar. f(n) « g(n) is the same as f(n) = O(g(n)) is the same as f(x) < C*(g(n)) for some C in R.
Proving that no such set exists would also resolve this problem, although this is impossible (as we now know such a set does exist).
I made some syntax changes (i→x, j→y, m→n) for this write up, but you can find it on both the Erdős comment thread and in my arXiv note.
More precisely, it’s an anisotropic lattice.
Or the isosceles trapezoid formed by four vertices of a regular pentagon.
Most people can look at the picture above and immediately see that no squares exist in the grid.
You can find all three in this blog post from NYU Professor Adam Sheffer.
The 2 multiplying y comes from squaring the √2.
I had never heard of it before, but Gemini and GPT (and Terry Tao) all knew it immediately.
It’s drawn from the family of problems of bounding distinct distances, constrained by drawing k points from a set with l distinct distances. This is the case where k = 4 and l = 3.
ArXiv is free and open, there are not many barriers to putting work on it. Math journals have much higher standards.