👁 Logo

Forum Inbox Favourites Tags

Forum

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], [657], and [659].

View the LaTeX source

This page was last edited 16 January 2026. View history

External data from the database - you can help update this
Formalised statement? No (Create a formalisation here)
Related OEIS sequences: Possible

Likes this problem	None
Interested in collaborating	None
Currently working on this problem	None
This problem looks difficult	None
This problem looks tractable	None
The results on this problem could be formalisable	None
I am working on formalising the results on this problem	None