Erdős Problems

Tags Prizes

OPEN - $500

Let $f(n)$ be maximal such that there exists a set $A$ of $n$ points in $\mathbb{R}^2$ in which every $x\in A$ has at least $f(n)$ points in $A$ equidistant from $x$.

Is it true that $f(n)\leq n^{o(1)}$? Or even $f(n) < n^{c/\log\log n}$ for some constant $c>0$?

#92: [Er94b][Er95][Er97c]

geometry, distances

This is a stronger form of the unit distance conjecture (see [90]).

The set of lattice points imply $f(n) > n^{c/\log\log n}$ for some constant $c>0$. Erdős offered \$500 for a proof that $f(n) \leq n^{o(1)}$ but only \$100 for a counterexample.

It is trivial that $f(n) \ll n^{1/2}$. A result of Pach and Sharir implies $f(n) \ll n^{2/5}$.

Fishburn (personal communication to Erdős) proved that $6$ is the smallest $n$ such that $f(n)=3$ and $8$ is the smallest $n$ such that $f(n)=4$, and suggested that the lattice points may not be best example.