---
tag: 4H31EM5T0C
kind: problem
name: Erdős distinct distances problem
msc: [52C10, 52C45]
uses: [0NPPGHQNXQ]
about: [0NPPGHQNXQ]
sources:
  - url: https://en.wikipedia.org/wiki/Erd%C5%91s_distinct_distances_problem
same_as:
  wikidata: Q3406261
  wikipedia: Erdős distinct distances problem
history:
  posed_by: "Paul Erdős"
  first_stated: "1946"
---

## Problem

Let $n \ge 2$ be an integer.
For a set $S$ of $n$ points in the plane $\R^2$, consider the [[Euclidean distances|0NPPGHQNXQ]] $\norm{p - q}$ with $p, q \in S$ and $p \ne q$.
Let $g(n)$ be the least number of distinct values of these distances, over all such sets $S$.
Find the order of growth of $g(n)$ as $n \to \infty$.
Erdős conjectured that the square grid is essentially optimal.
A weaker form of his conjecture says that $g(n) \ge n^{1 - \varepsilon}$ for every $\varepsilon > 0$ and all large enough $n$.

## Remarks

Erdős posed the problem in 1946 and proved the lower bound $g(n) = \Omega(\sqrt{n})$.
A $\sqrt{n} \times \sqrt{n}$ piece of the integer lattice determines only $O(n / \sqrt{\log n})$ distinct distances, so $g(n) = O(n / \sqrt{\log n})$.
Guth and Katz proved the lower bound $g(n) = \Omega(n / \log n)$.
This settles the weaker conjecture $g(n) \ge n^{1 - \varepsilon}$.
The exact order of $g(n)$ is still open: the known bounds differ by a factor of order $\sqrt{\log n}$.
The analogous questions in higher dimensions are also studied.

## Explanations

### L1 human

Put $n$ dots in the plane and list all the distances between pairs of dots.
How few different values can this list contain?
If the dots are spread at random, almost all distances differ.
A square grid does much better, because many pairs of dots have the same distance.
The problem asks whether one can do much better than a grid, and the answer is essentially no.