Problem #135: Let $A\subset \mathbb{R}^2$ be a set of $n$ points such...

---

Progress

A problem of Erdős and Gyárfás. Erdős could not even prove that the number of distances is at least $f(n)n$ where $f(n)\to \infty$. Erdős [Er97b] also makes the even stronger conjecture that $A$ must contain $\gg n$ many points such that all pairwise distances are distinct.

Answered in the negative by Tao [Ta24c], who proved that for any large $n$ there exists a set of $n$ points in $\mathbb{R}^2$ such that any four points determine at least five distinct distances, yet there are $\ll n^2/\sqrt{\log n}$ distinct distances in total. Tao discusses his solution in a blog post.

More generally, one can ask how many distances $A$ must determine if every set of $p$ points determines at least $q$ distances.

See also [136] and [657].