Given n points in the plane, what is the minimum number of distinct distances between pairs of points? A deceptively simple question with deep connections to algebraic geometry.
Let g(n) be the minimum number of distinct distances determined
by n points in the plane. Erdős conjectured:
g(n) = Ω(n / √log n)
The best known lower bound is g(n) = Ω(n / log n), proved using algebraic methods.
Place n points anywhere in the plane. Now measure the distance between every pair of points. The distinct distances problem asks: what's the minimum number of different distances you can achieve?
With 3 points, you have 3 pairs. An equilateral triangle gives only 1 distinct distance (all sides equal). But can you always achieve so few? For larger n, minimizing distinct distances becomes much harder.
Click to place points. Watch how the number of distinct distances changes!
Some point arrangements are especially good at minimizing distinct distances. The √n × √n grid is the classic example that achieves near-optimal bounds.
A √n × √n integer lattice achieves about cn / √log n distinct distances — exactly what Erdős conjectured as the minimum! This suggests the conjecture might be tight.
The gap between n / log n and n / √log n might seem small, but closing it has resisted all attempts. The algebraic methods that achieved the current bound seem to have reached their limits.
New ideas — perhaps from combinatorics, number theory, or algebraic geometry — will be needed to fully resolve Erdős's conjecture.
The distinct distances problem connects to: