Home » Discrete Geometry » Equilateral sets in normed spaces: upper bounds

# Equilateral sets in normed spaces: upper bounds

A set $S$ in a normed space $X$ is equilateral if any two points of $S$ are at the same distance:

There exists $\rho>0$ such that $\|x-y\|=\rho$ for all distinct $x,y\in S$.

From now on we fix $\rho=1$ by scaling.

If $X$ is $n$-dimensional, then an equilateral set has at most $2^n$ elements (Petty 1971, Soltan 1975). The following is a very simple proof. Let $P$ be the convex hull of $S$. Then the homothets $x+\frac12(P-x), x\in S$, are all contained in $P$, and have pairwise disjoint interiors. This follows from the triangle inequality. Now use the fact that the Lebesgue measure of each homothet is $(1/2)^n$ times that of $P$.

The next proof is by Füredi, Lagarias and Morgan (1993). Let $A=\bigcup_{x\in S} B(x,\frac12)$, the union of all balls of radius $\frac12$ centered at the points in $S$. Then $A$ has diameter 2. Now, by the isodiametric inequality (Busemann 1947, Mel’nikov 1963), the unit ball is the set of diameter 2 of largest Lebesgue volume. Again comparing volumes gives the upper bound.

The isodiametric inequality has a simple proof from the Brunn-Minkowski inequality, so it is not surprising that there is also a proof using the latter inequality. Again consider the set $A$. Since it has diameter 2, its central symmetral $A-A:=\{x-y : x,y\in A\}$ is contained in a ball of radius 2. By the Brunn-Minkowski inequality, $\mu(A-A)^{1/n}\geq\mu(A)^{1/n}+\mu(-A)^{1/n}$, and the $2^n$ upper bound follows.

### References

1. H. Busemann, Intrinsic area, Ann. Math. 48 (1947), 234-267. [It is quite a challenge to find the isodiametric inequality in this paper. It’s equation (2.2) on p. 241.]
2. Z. Füredi, J. C. Lagarias, and F. Morgan, Singularities of minimal surfaces and networks and related extremal problems in Minkowski space, Discrete and computational geometry (New Brunswick, NJ, 1989/1990), DIMACS Ser. Discrete Math. Theoret. Comput. Sci., vol. 6, Amer. Math. Soc., Providence, RI, 1991. pp. 95-109.
3. M. S. Mel’nikov, Dependence of volume and diameter of sets in an n-dimensional Banach space (Russian), Uspehi Mat. Nauk 18 (1963), 165-170.
4. C. M. Petty, Equilateral sets in Minkowski spaces, Proc. Amer. Math. Soc. 29 (1971), 369-374.
5. P. S. Soltan, Analogues of regular simplexes in normed spaces (Russian), Dokl. Akad. Nauk SSSR 222 (1975), 1303-1305. English translation: Soviet Math. Dokl. 16 (1975), 787-789.

## 5 thoughts on “Equilateral sets in normed spaces: upper bounds”

1. Somehow i missed the point. Probably lost in translation 🙂 Anyway … nice blog to visit.

cheers, Correspond!

2. Hi, Correspond,

Thank you. The point is just to review three proofs that there are at most $2^n$ equidistant points in an $n$-dimensional normed space.

3. dsp says:

What do you think of the following approach to proving Kusner’s conjecture that an upper bound for the size of an equilateral set in $\ell_1^n$ is $2n$?

Let $v_2 : \mathbb{Q} \longrightarrow \mathbb{Z} \cup \{\infty\}$ denote the 2-adic valuation, $R = \{a \in \mathbb{Q} : v_2(a) \geq 0\}$ the corresponding local ring, $M = \{a \in \mathbb{Q} : v_2(a) > 0\}$ its unique maximal ideal and $\underline{a} \in \mathbb{F}_2$ the reduction of $a \in R$ modulo $M$. One can prove that there are no equilateral sets with respect to the $\ell_1$ norm with $\rho = 1$ in $R^n$ as follows:
Since $R/M = \mathbb{F}_2$, $\underline{a} = \underline{-a}$ and hence $\underline{a} = \underline{|a|}$ for any $a \in R$. Therefore, if $(a_1,\dots,a_n),(b_1\dots,b_n) \in R^n$ are points in an equilateral subset of $R^n$, the image modulo $M$ of $a_1-b_1 + \dots + a_n-b_n$ equals the image modulo $M$ of $|a_1-b_1| + \dots + |a_n-b_n|$, which equals $1$ when $(a_1,\dots,a_n)$ and $(b_1\dots,b_n)$ are distinct, and $0$ otherwise.
Therefore, if $(a_{1,1},\dots,a_{1,n}),\dots,(a_{m,1}\dots,a_{m,n}) \in R^n$ are the points in an equilateral set of size $m$ in $R^n$, then the $m \times m$-matrix $\sum_{1 \leq i \leq n}((\underline{a_{1,i}},\dots,\underline{a_{m,i}})^T (1,\dots,1) - (1,\dots,1)^T (\underline{a_{1,i}},\dots,\underline{a_{m,i}}))$
has $(i,j)$-entry $\underline{a_{i,1}}-\underline{a_{j,1}} + \dots+ \underline{a_{i,n}}-\underline{a_{j,n}}$ and is hence equal to the matrix with main diagonal entries all equal to $0$ and all other entries equal to $1$. Since this matrix has rank $m$ and is equal to the sum of the $2n$ rank-$1$-matrices $(\underline{a_{1,i}},\dots,\underline{a_{m,i}})^T (1,\dots,1), - (1,\dots,1)^T (\underline{a_{1,i}},\dots,\underline{a_{m,i}})$, we have that $m \leq 2n$.

For a proof by contradiction of Kusner’s conjecture, it would therefore suffice to show that the existence of an equilateral set (with respect to the $\ell_1$ norm) of size $m$ in $\mathbb{R}^n$ implies the existence of an equilateral set (with respect to the $\ell_1$ norm) of size $m$ in $R^n$. This sounds like the sort of thing tropical geometry was invented for, but I don’t understand much tropical geometry, so I’m sort of stuck here. I apologize for dumping this text on you, but I’m just a math-obsessed pupil and not (yet) a professional mathematician, so I just don’t know what to do with this observation.