Bounds on two-distance sets in Euclidean space and Unit Sphere
Wei-Chun Chen, Wei-Hsuan Yu · 2025
Read Bounds on two-distance sets in Euclidean space and Unit Sphere by Wei-Chun Chen, Wei-Hsuan Yu (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-00858.txt.
Introduction
Wei-Chun Chen and one co-author, Wei-Hsuan Yu, establish upper bounds for two-distance sets, point sets in Euclidean space or on a sphere whose points use only two distinct distances. Bounding the largest such set is a classic problem in discrete geometry.
Their main recipe is the spectral method: they construct Seidel matrices, matrices that encode the distance relations between points, and apply eigenvalue analysis to derive explicit bounds. For Euclidean space, they bound the cardinality in terms of dimension and the ratio of the two distances. For spherical sets, two bounds are given depending on the sign of a sum of inner products, and one coincides with the relative bound for equiangular lines in one higher dimension.
Catalog record
| CREATOR | Wei-Chun Chen, Wei-Hsuan Yu |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 42 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-00858
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Bounds on two-distance sets in Euclidean space and Unit Sphere Wei-Chun Chen, Wei-Hsuan Yu Abstract Abstract We establish upper bounds for the size of two-distance sets in Euclidean space and spherical two-distance sets. The main recipe for obtaining upper bounds is the spectral method. We construct Seidel matrices to encode the distance relations and apply eigenvalue analysis to obtain explicit bounds. For Euclidean space, we have the upper bounds for the cardinality n of a two-distance set. n\leq\dfrac{(d+1)\left(\left(\frac{1+\delta^{2}}{1-\delta^{2}}\right)^{2}-1\right)}{\left(\frac{1+\delta^{2}}{1-\delta^{2}}\right)^{2}-(d+1)}+1. if the two distances are 1 and \delta in \mathbb{R}^{d} . For spherical two-distance sets with n points and inner products a,b on \mathbb{S}^{d-1} , we will have the following: \begin{cases}n\leq\dfrac{d\left(\left(\dfrac{a+b-2}{b-a}\right)^{2}-1\right)}{\left(\dfrac{a+b-2}{b-a}\right)^{2}-d},&a+b\geq 0;\\ n\leq\dfrac{(d+1)\left(\left(\dfrac{a+b-2}{b-a}\right)^{2}-1\right)}{\left(\dfrac{a+b-2}{b-a}\right)^{2}-(d+1)},&a+b<0.\end{cases} Notice that the second bound (for a+b<0 ) is the same as the relative bound for the equiangular lines in one higher dimension. 1. Introduction Let \mathbb{R}^{d} be the d -dimensional Euclidean space. A set X in \mathbb{R}^{d} is called a two-distance set if the distance between any pair of points in X takes only one of two possible values. The fundamental problem in this area is to determine the maximal cardinality of a two-distance set in \mathbb{R}^{d} . Let g(d) denote the maximum cardinality of a two-distance set in \mathbb{R}^{d} . For the general dimension d , a well-known construction provides two-distance sets with \binom{d+1}{2} points in \mathbb{R}^{d} , consisting of the midpoints of the edges of a regular simplex. For the upper bounds, Bannai, Bannai, and Stanton [ 1 ] proved that g(d)\leq\binom{d+2}{2} . Therefore, in general people only know that \binom{d+1}{2}\leq g(d)\leq\binom{d+2}{2} . In this paper, we show that if the ratio of the two distances are given, we can have smaller upper bounds for the size of a two-distance set. Larman, Rogers, and Seidel [ 9 ] proved that any two-distance set X in \mathbb{R}^{d} with |X|>2d+3 have squared distance ratio \delta^{2}=(k-1)/k for some integer k satisfying 2\leq k\leq\frac{1+\sqrt{2d}}{2}. The condition |X|>2d+3 was later improved to |X|>2d+1 by Neumaier [ 12 ] , who also showed the existence of (2d+1) -point two-distance sets whose \delta^{2} cannot be expressed in the form (k-1)/k , for some k\in\mathbb{N} . The maximum cardinalities of two-distance sets were determined for d\leq 8 [ 2 , 8 , 11 ] . d 1 2 3 4 5 6 7 8 g(d) 2 5 6 9 10 12 29 45 Table 1: The maximum cardinalities of two-distance sets for d\leq 8 A two-distance set X is called spherical if it lies on the unit sphere \mathbb{S}^{d-1} . For spherical two-distance sets, Delsarte, Goethals and Seidel [ 3 ] proved that the cardinality of a spherical two-distance set S is bounded above by \frac{1}{2}d(d+3) and the equality holds for dimensions d=2,6,22 . Glazyrin and Yu [ 6 ] determined the maximum cardinalities of spherical two-distance sets in \mathbb{R}^{d} , M(d) , for all dimensions with possible exceptions d=(2k+1)^{2}-3 where k\in\mathbb{N} : M(d)=\frac{d(d+1)}{2},\quad\forall d\geq 7\text{ except }d=(2k+1)^{2}-3,\;k\in\mathbb{N}. 1.1. Summary of results We begin by considering the Cayley-Menger matrix associated with a two-distance set, and then construct a corresponding Seidel matrix by appropriately adding a carefully designed auxiliary matrix. We then determine the spectrum of this Seidel matrix using Weyl’s inequality. Finally, we exploit the structural properties of Seidel matrices combined with the Cauchy-Schwarz inequality to establish the following upper bounds. Theorem A. Let X be an n -point two-distance set in \mathbb{R}^{d} with distances 1 ans \delta . Then n\leq\dfrac{(d+1)\left(\left(\dfrac{1+\delta^{2}}{1-\delta^{2}}\right)^{2}-1\right)}{\left(\dfrac{1+\delta^{2}}{1-\delta^{2}}\right)^{2}-(d+1)}+1. Using spectral properties, we establish that certain parameters is odd integers and derive bounds for all possible cases, reproducing the result of Larman, Rogers, and Seidel [ 9 ] through a similar approach to that of Lemmens and Seidel [ 10 ] . For spherical two-distance sets, we apply the same framework starting with Gram matrices. The sign of the sum of inner products a+b affects the spectral structure, leading to two distinct cases. Theorem B. Let X be an n -point spherical two-distance set in \mathbb{S}^{d-1} with inner products a,b . If a+b\geq 0 , then n\leq\dfrac{d\left(\left(\dfrac{a+b-2}{b-a}\right)^{2}-1\right)}{\left(\dfrac{a+b-2}{b-a}\right)^{2}-d}. This result extends the classical bound for equiangular line systems [ 10 ] to the more general case where a+b\geq 0 , with the equiangular case corresponding to a+b=0 . Theorem C. There exists a bijective correspondence between n points equiangular line systems in \mathbb{R}^{d+1} with common angle \alpha and families of n points spherical two-distance sets in \mathbb{S}^{d-1} with inner products a,b satisfying a+b<0 and \frac{a-b}{a+b-2}=\alpha . Similar integrality conditions hold for spherical cases. When a+b<0 , we establish a connection to equiangular line systems, providing a new spectral proof of classical results from Delsarte, Goethals, and Seidel [ 3 ] . Finally, we show that these upper bounds are attainable if the corresponding Seidel matrices have exactly two distinct eigenvalues, which occurs precisely when there exists an associated Equiangular Tight Frame. This provides a complete characterization of when our bounds are tight. 1.2. Outline The objective of this research is to improve upper bounds on |X| by exploiting the spectral properties of associated matrices when the ratio of the distances is specified. In Section 2, we transform the two-distance set into a Seidel matrices, which encode the distance relations and enable spectral analysis. In Section 3, we derive upper bounds on the cardinality of two-distance sets using spectral techniques and matrix theory. In Section 4, we focus on spherical two-distance sets, encode the distance relations and enable spectral analysis. In Section 5, we discuss bounds on spherical two-distance sets when the sum of inner products is nonnegative. In Section 6, we analyze the case when the sum of inner products is negative. In Section 7, we establish the connection between the existence of ETFs (Equiangular Tight Frames) and the attainability of the upper bounds derived in the preceding sections. 2. Construction of Seidel matrix Lisoněk [ 11 ] introduce the following theorem. Theorem 2.1 ( [ 11 ] ) . Let (c_{ij}) be a real symmetric n\times n matrix with zero diagonal. There exist n points P_{1},P_{2},\dots,P_{n}\in\mathbb{R}^{d} such that c_{ij}=\|P_{i}-P_{j}\| if and only if the matrix ( i,j=1,\dots,n-1 ) M_{n-1}=(c_{i,n}^{2}+c_{j,n}^{2}-c_{i,j}^{2})_{ij} is positive semidefinite and has rank at most d . M is also called the Cayley-Menger matrix. For any two-distance set, without loss of generality, we can rescale the set so that the two distinct distances are 1 and \delta>1 . Suppose the distances from P_{1},P_{2},\dots,P_{h} to P_{n} are 1 , and those from the remaining points to P_{n} are \delta . Let M be defined as follows: M=\begin{bmatrix}2&&2-\delta_{i}^{2}&&&&&\\ &2&&&&\delta_{i}^{2}&&\\ 2-\delta_{i}^{2}&&\ddots&&&\\ &&&2&&&&\\ &&&&2\delta^{2}&&2\delta^{2}-\delta_{i}^{2}&\\ &\delta_{i}^{2}&&&&2\delta^{2}&&\\ &&&&2\delta^{2}-\delta_{i}^{2}&&\ddots&\\ &&&&&&&2\delta^{2}\\ \end{bmatrix}_{(n-1)}, where \delta_{i}\in\{1,\delta\} . To facilitate analysis of two-distance sets, we transform the Cayley-Menger matrix into a form Seidel matrix by constructing a block matrix D . Definition 2.1 . Let X be a two-distance set with n points in \mathbb{R}^{d} , where the two distances are 1 and \delta . Let M=M(X) be the Cayley-Menger matrix. Define the Seidel matrix S by S_{n-1}=\frac{2M_{n-1}+D_{n-1}-(1+\delta^{2})\cdot I_{n-1}}{\delta^{2}-1} where D_{n-1}=\begin{bmatrix}(-3+\delta^{2})J_{h}&-(1+\delta^{2})J_{h,n-h-1}\\ -(1+\delta^{2})J_{n-h-1,k}&(1-3\delta^{2})J_{n-h-1}\\ \end{bmatrix}_{n-1}. where J_{p,q} is a p\times q all-ones matrix. Remark . Notice that upper left block of 2M has non-diagnal entries 2 or 2(2-\delta^{2}) . We subtract the middle value of them, and normalize it. So D_{n-1} is the negative middle value. Lemma 2.2 . The matrix S defined