Logo
All Random Solved Random Open
SOLVED
What is the size of the largest $A\subseteq \mathbb{R}^n$ such that there are only two distinct distances between elements of $A$? That is, \[\# \{ \lvert x-y\rvert : x\neq y\in A\} = 2.\]
Asked to Erdős by Coxeter. Erdős thought he could show that $\lvert A\rvert \leq n^{O(1)}$, but later discovered a mistake in his proof, and his proof only gave $\leq \exp(n^{1-o(1)})$.

Bannai, Bannai, and Stanton [BBS83] have proved that \[\lvert A\rvert \leq \binom{n+2}{2}.\] A simple proof of this upper bound was given by Petrov and Pohoata [PePo21].

Shengtong Zhang has observed that a simple lower bound of $\binom{n}{2}$ is given by considering all points with exactly two coordinates equal to $1$ and all others equal to $0$.

Additional thanks to: Ryan Alweiss, Jordan Ellenberg, Shengtong Zhang