Number of Distances Separating Points Has a New Bound

Scatter three points in a plane, then measure the distances between every pair of them. In all likelihood, you’ll find three different distances. But if you arrange the points in an equilateral triangle, then every distance is the same. In a plane, this is impossible to do with four points. The smallest number of distances you can engineer is 2 — the edges and diagonals of a square.

But if you lift one of the points up off the plane to create a pyramid, each of whose sides is an equilateral triangle, you’ll have a set of four points that are separated by a single unique distance — the length of one side of the triangle.

If you have lots of points, these patterns grow even more pronounced. A hundred randomly scattered points in a plane are likely to define 4,950 distinct pairwise distances. But if you arrange 100 points in a flat, square grid, any pair of points will be separated by one of just 50 possible distances. Lift the points into a three-dimensional grid, and you can reduce that number even further.

Answering questions about the number of distances between points might sound like an esoteric exercise. But in the decades-long quest to solve such problems, mathematicians have developed tools that have a wide range of other applications, from number theory to physics.

“When people tried to solve the problem,” said Pablo Shmerkin of the University of British Columbia, “they started discovering connections that were surprising and unexpected.”

The latest development came late last year, when a collaboration of four mathematicians proved a new relationship between the geometry of sets of points and the distances between them.

The list of different distances determined by a set of points is called its distance set; count how many numbers are in that list, and you get the distance set’s size. In 1946, the prolific mathematician Paul Erdős conjectured that for large numbers of points, the distance set cannot be smaller than what you get when you arrange the points into a grid. The problem, though simple on its face, turned out to be extremely deep and difficult. Even in two dimensions, it still hasn’t been fully proved, though in 2010, two mathematicians got so close that it’s now considered effectively settled; it remains open in higher dimensions.

Meanwhile, mathematicians also formulated new versions of the conjecture. One of the most important of these arose in a 1985 paper by Kenneth Falconer, a mathematician at the University of St. Andrews in Scotland. Falconer wondered what can be said about the distinct distances among an infinite number of points.

If you have infinitely many points, simply counting is no longer very useful. But mathematicians have other ways of defining size. Falconer’s conjecture posits a relationship between the geometry of the set of points — characterized by a number called the fractal dimension — and the size of the distance set, characterized by a number called the measure.

The fractal dimension aligns with ordinary intuition about dimensions. Just as with the more familiar concept of dimension, a line segment has a fractal dimension of 1, while a square (with its interior filled in) has a fractal dimension of 2. But if a collection of points forms a more complicated fractal pattern — like a curve where microscopic twists and turns keep appearing no matter how far you zoom in — its fractal dimension might not be a whole number. For example, the Koch snowflake curve shown below, which has an endless series of ever-smaller triangular bumps, has a dimension of about 1.26.

In general, an infinite collection of points has a fractal dimension that roughly depends on how dispersed it is. If it’s spread around the plane, its fractal dimension will be close to 2. If it looks more like a line, its fractal dimension will be close to 1. The same kinds of structures can be defined for sets of points in three-dimensional space, or in even higher dimensions.

On the other side of Falconer’s conjecture is the measure of the distance set. Measure is a sort of mathematical generalization of the notion of length. A single number, which can be represented as a point on a number line, has zero measure. But even infinite sets can have zero measure. For example, the integers are so thinly scattered among the real numbers that they have no collective “length,” and so form a set of measure zero. On the other hand, the real numbers between, say, 3/4 and 1 have measure 1/4, because that’s how long the interval is.

The measure gives a way to characterize the size of the set of distinct distances among infinitely many points. If the number of distances is “small,” that means the distance set will have measure zero: There are a lot of duplicated distances. If, on the other hand, the distance set has a measure that’s bigger than zero, that means there are many different distances.

In two dimensions, Falconer proved that any set of points with fractal dimension greater than 1.5 has a distance set with nonzero measure. But mathematicians quickly came to believe that this was true for all sets with a fractal dimension greater than 1. “We’re trying to resolve this 1/2 gap,” said Yumeng Ou of the University of Pennsylvania, one of the co-authors of the new paper. Moreover, Falconer’s conjecture extends into three or more dimensions: For points scattered in a d-dimensional space, it states that if the points’ fractal dimension is more than d/2, then the measure of the distance set must be greater than 0.

In 2018, Ou, together with colleagues, showed that the conjecture holds in two dimensions for all sets with fractal dimension greater than 5/4. Now Ou — along with Xiumin Du of Northwestern University, Ruixiang Zhang of the University of California, Berkeley, and Kevin Ren of Princeton University — have proved that in higher dimensions, the threshold for ensuring a distance set with nonzero measure is a little smaller than d/2 + 1/4. “The bounds in higher dimensions, in this paper, for the first time ever, are better than in dimension 2,” Shmerkin said. (In two dimensions, the threshold is precisely d/2 + 1/4.)

This latest result is just one in a wave of recent advances on Falconer’s conjecture. The proof refined techniques in harmonic analysis — a seemingly distant area of math that deals with representing arbitrarily complicated functions in terms of simple waves — to strengthen the bound. But some of those techniques were first developed in order to tackle this very same problem.

This question about distances between points “has served as a playground for some of the biggest ideas in harmonic analysis,” said Alex Iosevich of the University of Rochester.

Though they’ve closed only half of the gap left by Falconer in his 1985 paper, mathematicians see the recent spate of work as evidence that the full conjecture may finally be within reach. In the meantime, they’ll continue to use the problem as a testing ground for their most sophisticated tools.