On the distribution of distances: Quo vadis?

17^th March 2026, 13:00 Ashton Lecture Theatre
János Pach
Alfréd Rényi Institute

Abstract

In 1946, Paul Erdős raised two different problems for the distribution of distances among n points in the plane: (1) What is the minimum number of distinct distances determined by n points in R^2? (2) What is the maximum number of times the same distance can occur among n points in R^2? The first problem was almost solved by Guth and Katz in 2015 (up to a logarithmic factor). Regarding the second problem, Spencer, Szemerédi, and Trotter proved in 1983 that the maximum is O(n^{4/3}). Over the past 40 years, several new proofs have been found for this bound, but no improvement has been made. After giving a whirlwind survey of the known results and their applications in number theory and computer science, we describe an approach to the second problem, based on graph rigidity. Joint work with O. Raz and J. Solymosi.