Few distance sets in $\ell_{p}$ spaces and $\ell_{p}$ product spaces

A classic exercise in linear algebra asks for the maximum number of points in $\mathbb{R}^{n}$ such that the pairwise distances take only two values. One can associate a polynomial to each point in the set such that the polynomials are linearly independent. Then, one can show that the polynomials all lie in a subspace of dimension $(n+1)(n+4)/2$. Since the number of linearly independent vectors cannot exceed the dimension of the subspace, the cardinality of the set is at most $(n+1)(n+4)/2$. This beautiful argument was found by Larman, Rogers, and Seidel [10] in 1977, illustrating the power of algebraic techniques in combinatorics.

We can ask the much more general question: “In a metric space $X$, what is the maximum number of points such that the pairwise distances take only $s$ values?” We use $e_{s}(X)$, or just $e(X)$ if $s=1$, to denote the answer to this question (by convention, we do not count $0$ as a distance). A set of points $S\subseteq X$ satisfying this question’s conditions, i.e., the cardinality of the set $\{d(x,y):x,y\in S,x\neq y\}$ is $s$, is called an $s$-distance set. A $1$-distance set is also known as an equilateral set. Also, we typically restrict the metric space to a normed space, so that the specific distances used do not matter. Thus, we will always assume that the largest of the $s$ distances is $1$.

The posed question has been studied on many different spaces. The most famous result would be the upper bound $\binom{n+s}{s}$ on an $s$-distance set in $n$-dimensional Euclidean space, found by Bannai, Bannai, and Stanton [3]. This result was also discovered independently by Blokhuis [4]. Another important case is when all points lie on the $n$-dimensional sphere. There is strong motivation for this problem as it has many applications in coding theory and design theory [6]. In particular, having tight upper bounds can help us find extremal configurations which satisfy unique properties.

Similar results have been obtained in the hyperbolic space [4], the Hamming space [12], and the Johnson space [12]. Not as much is known in an arbitrary finite-dimensional normed space, known as a Minkowski space, other than Petty’s [13] general bound of $e(X)\leq 2^{n}$, where $n=\dim X$. Swanepoel [17] then conjectured that $e_{s}(X)\leq(s+1)^{n}$ for a Minkowski space $X$ with dimension $n$ and proved it for the $n=2$ case. We should mention that equilateral sets in Minkowski spaces have been applied in differential geometry, where they are used to find minimal surfaces [11].

In our paper, we investigate this problem on $\mathbb{R}^{n}$ with the $\ell_{p}$ norm, as well as on the $\ell_{p}$ sum of Euclidean spaces. For a point $x=(x_{1},\ldots,x_{n})\in\mathbb{R}^{n}$ and a $p\geq 1$, the $\ell_{p}$ norm is defined to be

and the $\ell_{\infty}$ norm is defined to be

The $\ell_{1}$ norm is the well-known “taxicab” norm, and the $\ell_{2}$ norm is the standard Euclidean norm. Throughout the paper, we write $\left\lVert\cdot\right\rVert$ instead of $\left\lVert\cdot\right\rVert_{2}$ to emphasize that we are using the Euclidean norm. We also use $\mathbb{E}^{n}$ to emphasize that we are in $n$-dimensional Euclidean space.

For Euclidean spaces $\mathbb{E}^{a_{1}},\ldots,\mathbb{E}^{a_{n}}$, we define their $\ell_{p}$ sum as the product space $\mathbb{E}^{a_{1}}\times\cdots\times\mathbb{E}^{a_{n}}$ equipped with the norm

where $x_{i}\in\mathbb{E}^{a_{i}}$ for $i=1,\ldots,n$. When $p=\infty$, the norm is

Then, for any $p\in[1,\infty]$, we let the distance between two points $x$ and $y$ be $\left\lVert x-y\right\rVert_{p}$ and use $\mathbb{E}^{a_{1}}\oplus_{p}\cdots\oplus_{p}\mathbb{E}^{a_{n}}$ to describe this space.

Although our notation for the norm in $\ell_{p}$ spaces and in $\ell_{p}$ sums is the same, the norm being used should be clear from context.

We first study $s$-distance sets in $\mathbb{R}^{n}$ equipped with the $\ell_{p}$ norm. This space is denoted by $\ell_{p}^{n}=(\mathbb{R}^{n},\left\lVert\cdot\right\rVert_{p})$. The two most famous questions pertaining to this problem are Kusner’s [7] conjectures on equilateral sets.

For Conjecture 1, note that the set $\{\pm e_{i}:i=1,\ldots,n\}$, where $e_{i}$ is the $i$-th standard basis vector, is equilateral in $\ell_{1}^{n}$, so $e(\ell_{1}^{n})\geq 2n$. Currently, the best known upper bound is $e(\ell_{1}^{n})\leq cn\log n$ due to Alon and Pudlák [1]. It is also known that Conjecture 1 holds for $n=3$ (Bandelt, Chepoi, and Laurent [2]) and $n=4$ (Koolen, Laurent, and Schrijver [9]).

As for Conjecture 2, note that the set $\{e_{1},\ldots,e_{n},\lambda\sum_{i=1}^{n}e_{i}\}$ is equilateral for a suitable choice of $\lambda$, so $e(\ell_{p}^{n})\geq n+1$. For $1<p<2$ and $n$ large enough, Swanepoel [19] actually showed that $e(\ell_{p}^{n})>n+1$, disproving Conjecture 2 in this case. The first nontrivial upper bound of $e(\ell_{p}^{n})\leq c_{p}n^{(p+1)/(p-1)}$ was found by Smyth [15] using an approximation argument. This result was later improved by Alon and Pudlák [1] and is currently the best known upper bound on $e(\ell_{p}^{n})$ for arbitrary $n$ and $p$.

Our first result is an improvement of Theorem 1 when $p$ is large in terms of $n$. One can check that $c>2$, so Theorem 2 is indeed an improvement.

We should mention that when $p$ satisfies other special properties, Theorem 1 can be strengthened. If $p$ is an even integer, Swanepoel [19] used a linear independence argument to show that

If $p$ is an odd integer, Alon and Pudlák’s argument for $e(\ell_{1}^{n})$ extends to $e(\ell_{p}^{n})$, giving the bound $e(\ell_{p}^{n})<c_{p}n\log n$ in this case.

Our next result is a generalization of Theorem 1 to $s$-distance sets. As far as we know, the only literature on $s$-distance sets in $\ell_{p}^{n}$ is by Smyth [16]. Our theorem below is strictly stronger than Conjecture 5 in [16].

Our next three results are on equilateral sets in the $\ell_{p}$ sum of Euclidean spaces. As far as we know, this problem has not been well studied in this space. Swanepoel [20] showed that $e(X\oplus_{\infty}Y)\leq e(X)b_{f}(Y)$ for normed spaces $X$ and $Y$, where $b_{f}$ is the finite Borsuk number. However, explicit bounds are still unknown when $X$ and $Y$ are Euclidean spaces and when we take an $\ell_{p}$ sum instead of an $\ell_{\infty}$ sum. Our first result in this area almost completely resolves the problem for $\mathbb{E}^{a}\oplus_{\infty}\mathbb{E}^{b}$. Note that we have the obvious lower bound $e(\mathbb{E}^{a}\oplus_{\infty}\mathbb{E}^{b})\geq e(\mathbb{E}^{a})e(\mathbb{E}^{b})=(a+1)(b+1)$ by taking the Cartesian product of the two equilateral sets. This lower bound is known to meet the upper bound when $a=2,3$ [20].

Our second result in this area provides an upper bound when $p$ is even.

Finally, we extend Alon and Pudlák’s [1] result on equilateral sets in $\ell_{p}^{n}$ to certain $\ell_{p}$ product spaces. We present an upper bound on the $\ell_{p}$ sum of $n$ Euclidean spaces for any $1\leq p<\infty$. Observe that Theorem 1 is a special case of our theorem below when $a_{1}=\cdots=a_{n}=1$.

Our paper is structured as follows. In Section 2, we introduce two important tools used in our proofs. Then, we prove Theorems 2, 3, 4, 5, and 6 in Sections 3, 4, 5, 6, and 7 respectively.

We will frequently make use of the following corollary.

From Theorem 7, we can recover the following lemma. This lemma was first given and proved in [14] and later also transmitted in [18].

We will always assume that the polynomial $P$ in Lemma 2 is even and that $P(0)=0$. If $P$ is not even, we can take the even part of $P$. If $P(0)\neq 0$, we can take the polynomial $Q(x)=P(x)-P(0)$ as this only increases the error term by a factor of $2$.