My most striking contribution to geometry is, no doubt, my problem on the number of distinct distances. This can be found in many of my papers on combinatorial and geometric problems.

-Paul Erdős, On Some of My Favorite Theorems, 1996.

Erdős is one of the greatest mathematicians from history, and he considered this problem one of his greatest contributions. Let’s dive into what it is and what is known.

There are few popular problems in math that can be explained easily and have current research across many disciplines.

Something like the Hodge Conjecture cannot be explained easily, but there is a lot of active research. Something like finding an odd perfect number can be explained easily, but no one seriously works on that.

The Erdős Distance Problem has a lot of ongoing research. Tools from many disparate branches of math like combinatorial geometry and optimization are developed specifically to try to solve this problem.

Roughly, it asks: how many distances must be made from n points? Sounds simple enough!

The Problem

We’ll start by considering things only in “the plane” (ℝ²).

If we only have one point, then there is only one distance that can be made: the zero distance. We’re always going to count the zero distance because it doesn’t change the problem and it makes some formulas nicer.

If we have two points, then there are only two distances we can make:

The distance between them, d, and the 0 distance.

If we go up to three points, there are two extremes:

If the three points form an equilateral triangle, then there are only 2 distances among the points: the side length and 0. If the three points form a scalene triangle, then all three sides have different lengths, so we can form 4 distances: 0, a, b, c.

As we add points, we’re going to get more and more combinations of possible distances. But for the problem we’re going to discuss, we only need to wonder about the minimum number.

If we know the minimum number, then we know that n points must always make at least that many distances.

The maximum number isn’t that interesting, because it’s just where every combination of points determines a different distance and given by a well-known formula: (n(n-1)/2)+1.

To help us make a guess at the minimum, let’s just think about perfect square numbers of points.

We’ll try to make the minimum number of distances out of 4 and 9 points by arranging them in the most symmetrical way we can think of, a grid:

The minimum for 4 points is 3 distances and the minimum for 9 points is 6 distances. We’ll come back to these grids in a moment, but for now, we can try to define the Erdős Distance Problem:

How does the minimum number of distances grow as n, the number of points, gets larger?

The Conjecture

Formulating Erdős’s original conjecture rigorously is a bit technical. That’s why we did some examples at first.

Roughly speaking, the conjecture is that the number of distances grows like n. In fact, Erdős worked out that if n was a perfect square, then the grid we made with 4 and 9 points would give n/√(log n). This means we can’t ever do better than that.

We know it can’t be exactly, n, because we did some examples where it is less (4 points can be arranged to make 3 distances). This means we need a definition that gives wiggle room.

Let’s define d(n) to be the minimum number of distances that can be made out of n points.

So, d(1)=1, d(2)=2, d(3)=2, d(4)=3, d(9)=6, and so on. If we plot these points, we want to understand the rate at which it trends upward for large n.

What we mean by “d(n) grows like n for large n” is that we can find constants A and B, so that if we plot y=Ax and y=Bx, the graph will stay between these two after a certain point:

One of the key things to notice is that we only care after a finite number of points, so the first few might not be between. But after those initial points, all the points stay between.

Again, the formulation you will find in a paper or book on this subject will be more technical (and later on, we’ll see that the way I’ve phrased it above is actually incorrect!). But this should give you a better understanding of what it might mean for d(n) to “grow like n.”

Erdős originally proved that d(n) must grow faster than √n. In other words, d(n)>C√n for all large n.

This is the bottom line on the graph (which is the important part since it tells us how many distances n points must make at the very least). From now on, we’re only going to care about this bottom curve so that we can get actual results.

Let’s see how he did this.

Erdős’s Proof for √n

Erdős gave this argument in 1946. I’ll warn you that this proof is extremely clever, so it might take some thought to grasp each step.

Suppose we have a collection of n points.

Pick any one you like and call it p. Now draw a circle through each of the remaining points centered at p. Note that the radius of each circle is the distance from p to the point on that circle:

Now we’ll denote the number of radii by t. The above picture has t=3.

In the above picture, the inner circle has 1 point on it, the middle circle has 2, and the outer circle has 2.

Claim: One of the circles must have at least n/t points on it.

Proof: This is known as the Pigeonhole Principle, but it can be seen simply by noting that if every circle had less than n/t, then the total number of points would be less than adding this number t times:

n < n/t+n/t+…+n/t = n.

A contradiction. Therefore, they can’t all have less than n/t, which is the claim.

Notice: In the example picture, n=6 and t=3, so indeed, the middle and outer circles have 6/3=2 points on it.

Now draw a line through p that doesn’t intersect any point:

Since the line doesn’t go through any points, there will be a side that contains at least half of the n/t points, and so there is a circle with at least n/(2t) points all on the same side.

In the above, the middle circle is divided into a part with 2 and a part with 0. The outer circle is divided into a part with 1 and a part with 1. It doesn’t matter which we use, I’m just explaining what is meant when we do this process.

Pick a circle with at least n/(2t) points on one side of the line. If we draw lines from one of the points to all the others this gives us n/(2t) different distances.

Thus, the number of distinct distances made by these n points is greater than max{t, n/(2t)}, the maximum among t and n/(2t).

Case 1: t≥√n. Then we’re done. This was what we wanted to show.

Case 2: t<√n.

In this case, we can just plug in that inequality.

d(n) > n/(2t) > n/(2√n)=(1/2)√n.

This finishes the proof because we just needed it to be bigger than a constant multiple of √n. We’ve shown that d(n)≥(1/2)√n for all n.

In other words, n points must make at least (1/2)√n distances.

More Results

First, I’ve been using the notation √n because it’s easier to write on Medium, but as an exponent: √n=n^(1/2).

The history of this problem is really interesting and vastly new methods and techniques had to be invented to get better and better exponents on n(sometimes called the Erdős exponent). As these exponents get closer and closer to 1, we get closer and closer to proving the initial conjecture.

In 1952, Moser proved the result for n^(2/3). The proof uses similar ideas to Erdős, but it constructs more sophisticated counting techniques.

It took all the way until 1997 for the next major step in the exponent. Székely proved the result for n^(4/5). This proof brought in a lot more and hinges on some results in graph theory and convex geometry.

In 2001, Solymosi and Tóth got the result for n^(6/7).

The result has continued to improve and the techniques have gotten very surprising, coming from number theory, vector spaces over finite fields, analytic methods, and even algebraic geometry.

Finally, in a 2015 Annals paper (one of the highest regarded math journals in the world), Guth and Katz got the exponent down to 1 by proving d(n)>Cn/(log n).

Higher Dimensions

We’ve been working in ℝ² this whole time. But we could just as easily ask this question in any number of dimensions.

You might want to try some small examples to see how strange things get. How many distances must 4 points make in 3-dimensional space?

Erdős conjectured that in d-dimensional space, n points must make at least n^(2/d) distances (up to the same wiggle room described at the beginning).

It would be beyond the scope of this overview to go into much more depth here.

If you’re interested in any part of this problem, the book The Erdős Distance Problem by Garibaldi, Iosevich, and Senger is excellent and served as the main reference for this article.