Logo
All Random Solved Random Open
SOLVED
Is there some function $f(n)\to \infty$ as $n\to\infty$ such that there exist $n$ distinct points on the surface of a two-dimensional sphere with at least $f(n)n$ many pairs of points whose distances are the same?
See also [90]. This was solved by Erdős, Hickerson, and Pach [EHP89]. For $D>1$ and $n\geq 2$ let $u_D(n)$ be such that there is a set of $n$ points on the sphere in $\mathbb{R}^3$ with radius $D$ such that there are $u_D(n)$ many pairs which are distance $1$ apart (so that this problem asked for $u_D(n)\geq f(n)n$ for some $D$).

Erdős, Hickerson, and Pach [EHP89] proved that $u_{\sqrt{2}}(n)\asymp n^{4/3}$ and $u_D(n)\gg n\log^*n$ for all $D>1$ and $n\geq 2$ (where $\log^*$ is the iterated logarithm function).

This lower bound was improved by Swanepoel and Valtr [SwVa04] to $u_D(n) \gg n\sqrt{\log n}$. The best upper bound for general $D$ is $u_D(n)\ll n^{4/3}$.

Additional thanks to: Dmitrii Zakharov