Kusner's conjecture: Exact values and linear bounds

Abstract

In 1983, Kusner conjectured that the largest equilateral set in ${\mathbb{R}}^n$ with metric ${\ell }_p$ has cardinality $n+1$ when $1<p<\infty$ and $2n$ when $p=1.$ This conjecture was proved only in the isolated cases $p=2$ and $p=4$, and was disproved when $1<p<2$. The best general upper bound $O_p(n^{\frac{2p+2}{2p-1}})$ is due to the celebrated work of Alon and Pudlák~[GAFA, 2003]. Our main contributions include: (1) We prove Kusner's conjecture for every dimension $n\ge 1$ when $2\le p\le 4$. More generally, for every integer $k\ge 0$ and every $p\in [4k+2,4k+4]$, every equilateral set in \(\mathbb{R}^{n}\) with metric ${\ell }_p$ has cardinality at most $(2k+1)n+1$. On the complementary intervals $p\in (4k,4k+2)$ with $p\ge 1$, we obtain the almost linear bound $O_p(n\log n)$. (2) We also consider the analogous problem on the torus ${\mathbb{T}}^n$, recently initiated by Alon, where the cyclic distance makes the problem substantially more delicate than in ${\mathbb{R}}^n$. We prove the almost linear bound $O_p(n\log n)$ for $1\le p\le 2$ and $O_p(n^{\frac{3}{2}-\frac{1}{p}})$ for every fixed real $p>2$, improving Alon's bounds $O_p(n^{2+\frac{2}{\lfloor p\rfloor }})$ for all finite $p\ge 1$.

47 pages