Equilateral dimension
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 -dimensional Euclidean space is , achieved by a regular simplex, and the equilateral dimension of a -dimensional vector space with the Chebyshev distance ( norm) is , achieved by a hypercube. However, the equilateral dimension of a space with the Manhattan distance ( norm) is not known. Kusner's conjecture, named after Robert B. Kusner, states that it is exactly , achieved by a cross polytope.[2]
Lebesgue spaces[edit]
The equilateral dimension has been particularly studied for Lebesgue spaces, finite-dimensional normed vector spaces with the norm
The equilateral dimension of spaces of dimension behaves differently depending on the value of :
How many equidistant points exist in spaces with Manhattan distance?
- For , the norm gives rise to Manhattan distance. In this case, it is possible to find equidistant points, the vertices of an axis-aligned cross polytope. The equilateral dimension is known to be exactly for ,[3] and to be upper bounded by for all .[4] Robert B. Kusner suggested in 1983 that the equilateral dimension for this case should be exactly ;[5] this suggestion (together with a related suggestion for the equilateral dimension when ) has come to be known as Kusner's conjecture.
- For , the equilateral dimension is at least where is a constant that depends on .[6]
- For , the norm is the familiar Euclidean distance. The equilateral dimension of -dimensional Euclidean space is : the 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 , the equilateral dimension is at least : for instance the basis vectors of the vector space together with another vector of the form for a suitable choice of form an equilateral set. Kusner's conjecture states that in these cases the equilateral dimension is exactly . Kusner's conjecture has been proven for the special case that .[6] When is an odd integer the equilateral dimension is upper bounded by .[4]
- For (the limiting case of the norm for finite values of , in the limit as grows to infinity) the norm becomes the Chebyshev distance, the maximum absolute value of the differences of the coordinates. For a -dimensional vector space with the Chebyshev distance, the equilateral dimension is : the vertices of an axis-aligned hypercube are at equal distances from each other, and no larger equilateral set is possible.[5]
Normed vector spaces[edit]
Equilateral dimension has also been considered for normed vector spaces with norms other than the 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 , the equilateral dimension is at most ; that is, the norm has the highest equilateral dimension among all normed spaces.[7] Petty (1971) asked whether every normed vector space of dimension has equilateral dimension at least , 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 norm, Petty's question has a positive answer: the equilateral dimension is at least .[8]
It is not possible for high-dimensional spaces to have bounded equilateral dimension: for any integer , all normed vector spaces of sufficiently high dimension have equilateral dimension at least .[9] more specifically, according to a variation of Dvoretzky's theorem by Alon & Milman (1983), every -dimensional normed space has a -dimensional subspace that is close either to a Euclidean space or to a Chebyshev space, where
Riemannian manifolds[edit]
For any -dimensional Riemannian manifold the equilateral dimension is at least .[5] For a -dimensional sphere, the equilateral dimension is , 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[edit]
- ^ a b Deza & Deza (2009)
- ^ Guy (1983); Koolen, Laurent & Schrijver (2000).
- ^ Bandelt, Chepoi & Laurent (1998); Koolen, Laurent & Schrijver (2000).
- ^ a b Alon & Pudlák (2003).
- ^ a b c d e f Guy (1983).
- ^ a b Swanepoel (2004).
- ^ a b Petty (1971).
- ^ a b Swanepoel & Villa (2008).
- ^ Braß (1999); Swanepoel & Villa (2008).
References[edit]
- Alon, N.; Milman, V. D. (1983), "Embedding of 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 ", 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.