Equilateral dimension

Regular simplexes of dimensions 0 through 3. The vertices of these shapes give the largest possible equally-spaced point sets for the Euclidean distances in those dimensions

In mathematics, the equilateral dimension of a metric space is the maximum size of any subset of the space whose points are all at equal distances to each other. ^[1] Equilateral dimension has also been called "metric dimension", but the term "metric dimension" also has many other inequivalent usages. ^[1] The equilateral dimension of ${\displaystyle d}$-dimensional Euclidean space is ${\displaystyle d+1}$, achieved by the vertices of a regular simplex, and the equilateral dimension of a ${\displaystyle d}$-dimensional vector space with the Chebyshev distance (${\displaystyle L^{\infty }}$ norm) is ${\displaystyle 2^{d}}$, achieved by the vertices of a hypercube. However, the equilateral dimension of a space with the Manhattan distance (${\displaystyle L^{1}}$ norm) is not known. Kusner's conjecture, named after Robert B. Kusner, states that it is exactly ${\displaystyle 2d}$, achieved by the vertices of a cross polytope. ^[2]

Lebesgue spaces

The equilateral dimension has been particularly studied for Lebesgue spaces, finite-dimensional normed vector spaces with the ${\displaystyle L^{p}}$ norm $${\displaystyle \ \|x\|_{p}={\bigl (}|x_{1}|^{p}+|x_{2}|^{p}+\cdots +|x_{d}|^{p}{\bigr )}^{1/p}.}$$

The equilateral dimension of ${\displaystyle L^{p}}$ spaces of dimension ${\displaystyle d}$ behaves differently depending on the value of ${\displaystyle p}$:

Unsolved problem in mathematics:

How many equidistant points exist in spaces with Manhattan distance?

(more unsolved problems in mathematics)

• For ${\displaystyle p=1}$, the ${\displaystyle L^{p}}$ norm gives rise to Manhattan distance. In this case, it is possible to find ${\displaystyle 2d}$ equidistant points, the vertices of an axis-aligned cross polytope. The equilateral dimension is known to be exactly ${\displaystyle 2d}$ for ${\displaystyle d\leq 4}$, ^[3] and to be upper bounded by ${\displaystyle O(d\log d)}$ for all ${\displaystyle d}$. ^[4] Robert B. Kusner suggested in 1983 that the equilateral dimension for this case should be exactly ${\displaystyle 2d}$; ^[5] this suggestion (together with a related suggestion for the equilateral dimension when ${\displaystyle p>2}$) has come to be known as Kusner's conjecture.
• For ${\displaystyle 1<p<2}$, the equilateral dimension is at least ${\displaystyle (1+\varepsilon )d}$ where ${\displaystyle \varepsilon }$ is a constant that depends on ${\displaystyle p}$. ^[6]
• For ${\displaystyle p=2}$, the ${\displaystyle L^{p}}$ norm is the familiar Euclidean distance. The equilateral dimension of ${\displaystyle d}$-dimensional Euclidean space is ${\displaystyle d+1}$: the ${\displaystyle d+1}$ vertices of an equilateral triangle, regular tetrahedron, or higher-dimensional regular simplex form an equilateral set, and every equilateral set must have this form. ^[5]
• For ${\displaystyle 2<p<\infty }$, the equilateral dimension is at least ${\displaystyle d+1}$: for instance the ${\displaystyle d}$ basis vectors of the vector space together with another vector of the form ${\displaystyle (-x,-x,\dots )}$ for a suitable choice of ${\displaystyle x}$ form an equilateral set. Kusner's conjecture states that in these cases the equilateral dimension is exactly ${\displaystyle d+1}$. Kusner's conjecture has been proven for the special case that ${\displaystyle p=4}$. ^[6] When ${\displaystyle p}$ is an odd integer the equilateral dimension is upper bounded by ${\displaystyle O(d\log d)}$. ^[4]
• For ${\displaystyle p=\infty }$ (the limiting case of the ${\displaystyle L^{p}}$ norm for finite values of ${\displaystyle p}$, in the limit as ${\displaystyle p}$ grows to infinity) the ${\displaystyle L^{p}}$ norm becomes the Chebyshev distance, the maximum absolute value of the differences of the coordinates. For a ${\displaystyle d}$-dimensional vector space with the Chebyshev distance, the equilateral dimension is ${\displaystyle 2^{d}}$: the ${\displaystyle 2^{d}}$ vertices of an axis-aligned hypercube are at equal distances from each other, and no larger equilateral set is possible. ^[5]

Normed vector spaces

Equilateral dimension has also been considered for normed vector spaces with norms other than the ${\displaystyle L^{p}}$ norms. The problem of determining the equilateral dimension for a given norm is closely related to the kissing number problem: the kissing number in a normed space is the maximum number of disjoint translates of a unit ball that can all touch a single central ball, whereas the equilateral dimension is the maximum number of disjoint translates that can all touch each other.

For a normed vector space of dimension ${\displaystyle d}$, the equilateral dimension is at most ${\displaystyle 2^{d}}$; that is, the ${\displaystyle L^{\infty }}$ norm has the highest equilateral dimension among all normed spaces. ^[7] Petty (1971) asked whether every normed vector space of dimension ${\displaystyle d}$ has equilateral dimension at least ${\displaystyle d+1}$, but this remains unknown. There exist normed spaces in any dimension for which certain sets of four equilateral points cannot be extended to any larger equilateral set ^[7] but these spaces may have larger equilateral sets that do not include these four points. For norms that are sufficiently close in Banach–Mazur distance to an ${\displaystyle L^{p}}$ norm, Petty's question has a positive answer: the equilateral dimension is at least ${\displaystyle d+1}$. ^[8]

It is not possible for high-dimensional spaces to have bounded equilateral dimension: for any integer ${\displaystyle k}$, all normed vector spaces of sufficiently high dimension have equilateral dimension at least ${\displaystyle k}$. ^[9] more specifically, according to a variation of Dvoretzky's theorem by Alon & Milman (1983), every ${\displaystyle d}$-dimensional normed space has a ${\displaystyle k}$-dimensional subspace that is close either to a Euclidean space or to a Chebyshev space, where $${\displaystyle k\geq \exp(c{\sqrt {\log d}})}$$ for some constant ${\displaystyle c}$. Because it is close to a Lebesgue space, this subspace and therefore also the whole space contains an equilateral set of at least ${\displaystyle k+1}$ points. Therefore, the same superlogarithmic dependence on ${\displaystyle d}$ holds for the lower bound on the equilateral dimension of ${\displaystyle d}$-dimensional space. ^[8]

Riemannian manifolds

For any ${\displaystyle d}$-dimensional Riemannian manifold the equilateral dimension is at least ${\displaystyle d+1}$. ^[5] For a ${\displaystyle d}$-dimensional sphere, the equilateral dimension is ${\displaystyle d+2}$, the same as for a Euclidean space of one higher dimension into which the sphere can be embedded. ^[5] At the same time as he posed Kusner's conjecture, Kusner asked whether there exist Riemannian metrics with bounded dimension as a manifold but arbitrarily high equilateral dimension. ^[5]

Notes

1. Deza & Deza (2009)
2. Guy (1983); Koolen, Laurent & Schrijver (2000).
3. Bandelt, Chepoi & Laurent (1998); Koolen, Laurent & Schrijver (2000).
4. Alon & Pudlák (2003).
5. Guy (1983).
6. Swanepoel (2004).
7. Petty (1971).
8. Swanepoel & Villa (2008).
9. Braß (1999); Swanepoel & Villa (2008).

References

• Alon, N.; Milman, V. D. (1983), "Embedding of ${\displaystyle l_{\infty }^{k}}$ in finite-dimensional Banach spaces", Israel Journal of Mathematics , 45 (4): 265–280, doi:10.1007/BF02804012, MR   0720303 .
• Alon, Noga; Pudlák, Pavel (2003), "Equilateral sets in ${\displaystyle l_{p}^{n}}$", Geometric and Functional Analysis , 13 (3): 467–482, doi:10.1007/s00039-003-0418-7, MR   1995795 .
• Bandelt, Hans-Jürgen; Chepoi, Victor; Laurent, Monique (1998), "Embedding into rectilinear spaces" (PDF), Discrete & Computational Geometry , 19 (4): 595–604, doi: 10.1007/PL00009370 , MR   1620076 .
• Braß, Peter (1999), "On equilateral simplices in normed spaces", Contributions to Algebra and Geometry, 40 (2): 303–307, MR   1720106 .
• Deza, Michel Marie; Deza, Elena (2009), Encyclopedia of Distances, Springer-Verlag, p. 20.
• Guy, Richard K. (1983), "An olla-podrida of open problems, often oddly posed", American Mathematical Monthly , 90 (3): 196–200, doi:10.2307/2975549, JSTOR   2975549, MR   1540158 .
• Koolen, Jack; Laurent, Monique; Schrijver, Alexander (2000), "Equilateral dimension of the rectilinear space", Designs, Codes and Cryptography, 21 (1): 149–164, doi:10.1023/A:1008391712305, MR   1801196 .
• Petty, Clinton M. (1971), "Equilateral sets in Minkowski spaces", Proceedings of the American Mathematical Society , 29 (2): 369–374, doi: 10.1090/S0002-9939-1971-0275294-8 , MR   0275294 .
• Swanepoel, Konrad J. (2004), "A problem of Kusner on equilateral sets", Archiv der Mathematik , 83 (2): 164–170, arXiv: math/0309317 , doi:10.1007/s00013-003-4840-8, MR   2104945 .
• Swanepoel, Konrad J.; Villa, Rafael (2008), "A lower bound for the equilateral number of normed spaces", Proceedings of the American Mathematical Society , 136 (1): 127–131, arXiv: math/0603614 , doi:10.1090/S0002-9939-07-08916-2, MR   2350397 .