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\H{o}s offered \$500 for a proof that $f(n) \leq n^{o(1)}$ but only \$100 for a counterexample. This latter prize is downgraded to \$50 in \cite{ErFi97}.

It is trivial that $f(n) \ll n^{1/2}$. A result of Pach and Sharir (Theorem 4 of \cite{PaSh92}) implies $f(n) \ll n^{2/5}$. Hunter has observed that the circle-point incidence bound of Janzer, Janzer, Methuku, and Tardos \cite{JJMT24} implies\[f(n) \ll n^{4/11}.\]Fishburn (personal communication to Erd\H{o}s, later published in \cite{ErFi97}) 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.

See also [754].



References


[ErFi97] Erd\H{o}s, Paul and Fishburn, Peter, Minimum planar sets with maximum equidistance counts. Comput. Geom. (1997), 207--218.

[JJMT24] B. Janzer, O. Janzer, A. Methuku, and G. Tardos, Tight bounds for intersection-reverse sequences, edge-ordered graphs
and applications. arXiv:2411.07188 (2024).

[PaSh92] Pach, J\'anos and Sharir, Micha, Repeated angles in the plane and related problems. J. Combin. Theory Ser. A (1992), 12--22.