Abstract
The three gap theorem states that for any and , the number of different gaps between consecutive for is at most 3. Biringer and Schmidt (2008) instead considered the distance from each point to its nearest neighbor, generalizing to higher dimensions. We denote the maximum number of distances in using the p-norm by so that . Haynes and Marklof (2021) showed that each example with arbitrary α and N gives a generic lower bound, and that and where σd is the kissing number. They gave an example showing . Our examples that show and also and . Haynes and Ramirez (2021) showed that and that this is sharp for . We provide a numerical example to show , and a proof that in general. Results for and σd imply that depends on p for and we conjecture this for . For we expect that for respectively, independent of p. For d = 1 this is trivial, for d = 2 we show that and for d = 3 we provide numerical examples suggesting that .
1 Introduction
What is the maximum local complexity for equally spaced points on a torus (defined in Section 2)? Equally spaced refers to the set for fixed . Local complexity refers to the number of different neighborhoods of each of the points, suitably defined; see for example [Citation5]. The three gap theorem states that if d = 1 and the local complexity refers to the smallest distance to a point on the right, that is, gap distances between consecutive points, the maximum local complexity is three. It was proved by Sós [Citation8, Citation9] and independently by Swierczkowski [Citation10] and has many alternative proofs and generalizations.
Biringer and Schmidt [Citation1] noted that a slightly weaker version, the three distance theorem, applies if the gap (distance to the right) is replaced by the nearest neighbor distance, and that this has a natural generalization to higher dimensions. They then considered Riemannian manifolds, where the equally spaced points could generalize to isometries of the manifold, or equally spaced points on a geodesic. In our case (the torus) they give an upper bound , where distance is induced from the usual Euclidean metric. We use the notation (with () for the maximum number of distinct distances for the p-norm on and for the number of distinct distances for a particular α and N. See Section 2 for the precise definitions. Note that Biringer and Schmidt start their sequences from zero rather than one, so their N values (denoted n in their paper) are one smaller.
Haynes and Marklof [Citation3] proved that and where σd is the kissing number, the maximum number of equal radius balls that can touch a single ball in d dimensions. In the dimensions considered in our examples, it is known that and [Citation2, Citation6]. See also Lemma 3.
Haynes and Marklof also showed in their Theorem 2 that (1) (1) for all α, all non-degenerate lattices Λ and , all subexponential sequences and almost all . Thus an example for (based on the cubic lattice ) with arbitrary α and N gives a generic lower bound for tori based on all lattices.
This theorem in Ref. [Citation3] uses the Euclidean norm. However, its proof relies on showing that there is an open set of lattices which obtain the upper bound on the number of distances. This is a topological property of the space and the functions involved and it is not hard to see from this point of view that the same proof will work, with only minor modifications, for any norm which induces the same topology, including the maximum norm and other p-norms (Alan Haynes and Jens Marklof, private communication).
Our numerical methods for finding these examples and hence lower bounds on are as follows:
Random search We sample about 1012 values of α uniformly in and find most of the examples presented here.
Rational search We can exhaustively search α with denominator up to some limit, around 2000 for d = 3 and 200 for d = 6.
Lattice search Searching near a known solution extended the number of distances for p = 2, d = 6 from 13 to 14. In addition, evaluating the number of distances on a lattice in α in the vicinity of a solution is used to estimate the d-volume of the domain of that solution.
Mathematica was used to verify solutions; see the Appendix. It was also used to find the area of the pentagonal region of the example for , d = 2. In addition, rigorous constructions of solutions were used in the proofs of Theorems 2 and 5. Both the rational search and the Mathematica verification may be considered rigorous claims, conditional on the software being free of bugs that materially affect the results. The author’s own code was written in C++, in some cases extended to GPU code by Mark Pearson (see the Acknowledgments).
For the Euclidean norm, we provide new examples for that were obtained numerically, hence improving the lower bounds for . We also note that any example in a given dimension d is also an example for any larger dimension, that is, is a non-decreasing function of d. In summary:
Theorem 1.
(2) (2)
Remark
s:
The examples for were found using Mark Pearson’s code (see the Acknowledgments).
Whilst a significant improvement on the previous bound for these dimensions, there is still some distance between these and the upper bound .
Since all lattices can be used for finding examples, it is possible to consider lattices of higher symmetry. We have tried the F4 lattice for d = 4, that is, the lattice with an extra point at the center of every 4-cube. However this does not seem to be more efficient in finding examples.
The case of few distances has also been studied: Weiß [Citation11] found for d = 2, 3 for which for infinitely many N.
Haynes and Ramirez [Citation4] consider instead the maximum metric, that is, based on the -norm. These authors give an upper bound for the equivalent maximum number of distances and show it is sharp for d = 2, 3 (as well as d = 1). They did not find any examples to show . We can improve this as follows, using a numerical example for d = 4 and a general construction for :
Theorem 2.
(3) (3)
Now we obtain a closed form bound on the kissing number
Lemma 3.
(4) (4)
This is not a particularly tight bound or difficult to prove, but we include it here as the bounds we found in the literature involved integrals or special functions, so it may be of independent interest.
Combining Theorem 2 and Lemma 3 we show
Theorem 4.
(5) (5)
Remark
s:
For the dimensions in which Theorem 4 holds, this shows that depends on p.
We conjecture that Theorem 4 holds for . For d < 4, see below.
The new lower bounds on and together with previously known upper bounds are illustrated in .
Finally, we consider general p-norms in low dimension and can show
Theorem 5.
For all p-norms with .
Remark:
We also have examples (presented in Section 8) giving numerical evidence that for all p. We conjecture that and , independent of p, in contrast to higher dimensions.
In Section 2 we define the torus and its norms and metrics. We also recall the calculation of the number of distances from Ref. [Citation3]. In Section 3 we give examples for the Euclidean norm for , including those needed to prove Theorem 1, as well as some others of minimal length and/or denominator. In Section 4 we give examples for the maximum metric. In Section 5 we prove Theorem 1, then, in Section 6 we provide the example and proof for Theorem 2. Section 7 provides the proofs of Lemma 3 and Theorem 4. Finally, for general p-norms, Theorem 5 for d = 2 is proved, and the examples for d = 3 are presented in Section 8.
2 Preliminaries
The torus is the d-dimensional Euclidean space, identifying each point with its lattice translates . It is easy to see for and that nx, x + y and x–y are well defined under this identification.
The p-norm on for , denoted , is defined as (6) (6)
For p = 2 this is the Euclidean norm, whilst for it is the maximum norm.
This induces the following norm on : (7) (7)
that in turn induces the metric (8) (8) giving our notion of distance on the torus. When d = 1 and when considering a single component in higher dimensions, all the norms and distances are equivalent, so the p will be omitted from the notation. When d = 2, the “disk” of fixed radius for p = 1 and for is a square, and these correspond to the same metric in different lattices, thus .
We also define to be the distance to the nearest integer (that is, the norm on ) of , where αj is the jth component of α, so that (9) (9)
We are interested in the distance (according to ) from the point to its nearest neighbor where , that is (10) (10)
the number of distinct nearest neighbor distances (11) (11)
and its maximum value (12) (12)
Given that it is easy to see (and noted in Ref. [Citation3]) that this is (13) (13) where . Now, as i ranges from 1 to N, has its largest value for and decreases as n is increased to N–1. The number of distinct nearest neighbor distances is thus: (14) (14)
All but one of the minimum distances occur for , which implies that (15) (15)
for all α. For examples where this bound is sharp, see Sections 3.7 and 4.5.
Where possible, we seek the simplest examples, which are hopefully also the most illustrative. So, for each d, we seek the largest , then the smallest N, then the α with the smallest denominator. Symmetry allows us to permute the coordinates and to replace αi by so each solution belongs to an equivalence class of solutions (or fewer if it has symmetry). Henceforth we assume without loss of generality that .
3 Examples for the Euclidean norm
3.1 d = 1
We have as previously reported and can achieve N = 5, the minimum possible value from Equationequation (15)(15) (15) . The only possible decreasing sequence of distances is which yields easily the solution set of size (ignoring the region as noted above). The simplest rational example is (found by exhaustive rational search, numerically or manually) for which for , respectively, with the relevant distances in bold. A plot of and example with three distances is shown in . There are no examples with smaller denominator but higher length N.
3.2 d = 2
As noted in Ref. [Citation3], we have , and can achieve N = 9 with (see their ). Again, this is the minimum possible N according to Equationequation (15)(15) (15) . Numerically, this example is in the only region where this N exists (modulo symmetry), a roughly triangular region with area about ; see . The solution with minimal denominator for this length is: which has a decimal approximation . For this example we find , for , with the relevant distances in bold. The boundary of the region occurs when any of the inequalities is broken. Here, is much smaller than , so that the boundaries of the region are the circular arcs defined by and . See .
A rational solution with minimal denominator (but not length) is with .
A solution where the region is a (curvilinear) quadrilateral rather than a triangle is with or . In this case, the boundary curves are . So, the longest of the five distances is either or for different parts of the solution region.
3.3 d = 3
The following example is new (though its discovery was noted in Ref. [Citation3]): with or a close point with minimal denominator . There are no other (longer) orbits with smaller denominators than this. The descending sequence of norms is with and all other norms larger for . This set of solutions lies in a roughly tetrahedral region of volume close to bounded by the surfaces , and . Symmetry gives copies of this set, so it requires close to 1011 random vectors to find. Note that the upper bound for is . However we conjecture that this example is tight, that is, .
3.4 d = 4
The following example is new: with . The descending sequence of norms is with . The 4-volume of the relevant region is about .
3.5 d = 5
The example is with . The descending sequence is with . The 5-volume of the relevant region is about . That this region was found within about 1012 sample size, even taking into account the symmetry factor suggests that there are many similar regions.
3.6 d = 6
The random algorithm discovered a solution with , but searching (using a cubic lattice) in the vicinity of this solution improved it to with . The descending sequence is with . The 6-volume of the relevant region is about .
3.7 Minimal length solutions
We have from Equationequation (15)(15) (15) that . However, the above examples with have much larger N. gives examples we have found where this bound is sharp using the exhaustive rational search method with . It is open whether solutions exist for higher than presented here. The example for N = 3 has a shortest distance of zero between the first and third points; if a positive distance is desired, provides the minimal denominator example for this case.
4 Examples for the maximum norm
4.1 d = 1
This case is identical to the Euclidean norm, Section 3.1.
4.2 d = 2
Ref. [Citation4] shows that and gives the solution for N = 11. In contrast to the Euclidean case, numerical simulations strongly suggest that this is the minimum N. The maximum norm is in some ways simpler than the Euclidean norm as the solution regions are polytopes; see and which shows a non-convex pentagonal region for this value of N. A rational solution with minimal denominator (at this length) is
For this example we find for with relevant norms in bold. As with the roughly triangular example in Section 3.2, the boundaries of this region occur where one of the relevant inequalities is broken. The maximum norm is, according to Equationequation (9)(9) (9) ,
(16) See the lower right panel of . The part of the boundary where corresponds to two components, and , and similarly corresponds to two components and . Finally, the other relevant component is corresponding to . Unlike the p = 2 norm, each of these components is a straight line segment, yielding exact rational values for the locations of the vertices of the pentagon, clockwise from the upper left:
The area can be calculated exactly (using Mathematica) to be
A rational solution with minimal denominator (but not length) is with .
4.3 d = 3
Ref. [Citation4] shows that and gives a solution equivalent to for . We have found the slightly simpler solution with or with minimal denominator for this length,
The descending sequence of norms for the latter is
with . The volume of this region is around
A rational solution with minimal denominator (but not length) is with .
4.4 d = 4
We have the found the following example, of much greater length and distances than others: with . The descending sequence of norms is with . The 4-volume of this region is around .
4.5 Minimal length solutions
As in Section 3.7 we seek solutions where the bound in Equationequation (15)(15) (15) is sharp. For the maximum norm, the example in the proof of Theorem 2 shows that these exist for arbitrary . gives results from the exhaustive integer search, which suggests that this is close to the best that can be obtained; the examples with have .
5 Proof of Theorem 1
Proof.
For this theorem, we have p = 2 (Euclidean norm). We verify the examples in Section 3 computationally using exact arithmetic, and apply the result in Equationequation (4)(4) (4) . Mathematica code and an example (d = 3 in the Euclidean metric) are given in Appendix A. □
6 Proof of Theorem 2
For this theorem, we have (maximum norm). For d = 4, the example in Section 4.4 is verified using the Mathematica code in Appendix A.
For (and for lower d, but in this case the bound is not optimal) we have the example with . In the following, as just before Equationequation (9)(9) (9) , a subscript indicates vector component. If n is odd, then . If n is even but not a multiple of 4, then and in general, if n is a multiple of but not for then the d–k component of is . For ϵ sufficiently small, this will be the component with the largest distance, and hence give the -norm. As ϵ is increased, the first violation occurs for when which has norm greater than for , hence the above bound on ϵ. Finally, for , all components are . Thus (17) (17)
which decreases monotonically, and so choosing gives distances as needed. □
Remark
s:
1. Choosing the maximum value of ϵ gives a rational solution with denominator .
2. Choosing odd gives a solution with distances, so that Equationequation (15)(15) (15) is sharp.
7 Proof of Lemma 3 and Theorem 4
We use the bound on σd given in Equationeq. 2(2) (2) of Ref. [Citation7], noting that the kissing number corresponds to spherical caps of radius corresponding to in that paper. (18) (18)
For this can be simplified using and for comparing two concave functions with linear functions between their end points: and . This leads to Lemma 3: (19) (19)
Now and also for . So by induction, for all . Thus for all . Also, we note that for by known bounds for these dimensions [Citation2, Citation6].
Thus for all we have where the first inequality is from Theorem 2 and the last from Ref. [Citation3]. This concludes the proof of Theorem 4. □
8 General p-norms
8.1 d = 1
This case is identical to Section 3.1.
8.2 d = 2: Proof of Theorem 5
We now prove Theorem 5, by giving an example with 5 distances in d = 2, valid for all .
More precisely, we will show that for all p we can define and so that when there exists so that , where α depends on θ and ϵ. Specifically, and where . For , we define these to take their limiting values, namely and . In all cases so is strictly monotonic.
To show that the interval in θ is well defined, note that (20) (20)
Now consider for , in particular (21) (21)
For ϵ = 0 these four p-norms are equal: (22) (22)
Furthermore, denoting the distance to the nearest integer of the components of as (see Equationequation (9)(9) (9) ), we note that for n = 1 we have and for and . Thus for ϵ = 0 and these n, the p-norm is strictly greater than for for all . This remains true for all sufficiently small positive ϵ.
For small positive ϵ, the for will differ, and following the analysis in Section 2, in order to obtain five distances, the minimum distance needs to decrease four times in the range , that is, we need (23) (23)
Now, we have two cases. First, consider . For the first inequality we write in full, to first order in powers of ϵ: (24) (24)
The constant terms cancel. We divide by and neglect higher order terms in ϵ. Also, recall that . In this way we obtain (25) (25) and hence . By a similar calculation, is satisfied if and is satisfied if or . For this last inequality we have for : (26) (26) since the numerator is positive for all s, and the denominator is also positive when s < 13∕16. Thus, the inequality is always satisfied when .
To summarize, for the inequalities at first order in ϵ are satisfied, and we can take sufficiently small ϵ to ensure that the higher order terms can be neglected.
The second case is . Here we can write explicitly that and . The inequalities, Equationequation (23)(23) (23) are satisfied for , which is again . □
Remark:
It is an open question whether there are any α and N giving five distances for all p. The above proof shows that solutions are in a small neighborhood of the point , but the intervals in θ have no intersection: For p = 1 we need whilst for we need .
8.3 d = 3
We have numerical evidence that for all , there exist α and N such that . Our examples interpolate between the values of p for the four given in , covering the entire domain in p. The regions in α vary slightly with p.
A code to verify solutions
The following Mathematica code was used to verify all the examples given in this paper. Mathematica does arbitrary precision arithmetic and exact comparisons of expressions involving non-integer powers, so it can be used for all values of p, entered as 13/10 rather than 1.3, for example. Following the code, we present the output for three examples, found in sections 3.3, 4.4 and 8.3. Equivalent code can be written in computer languages using fixed precision integers for integer or infinite p, and denominators not too large.
Mathematica 11.0.1 for Linux x86 (64-bit)
Copyright 1988-2016 Wolfram Research, Inc.
In[Citation1]:=! cat dists.m
Print["p-metric distances for exact p> =1 or Infinity"]
qreduce[a_,q_]:=Abs[a-q*Floor[a/q + 0.5]]
distlist[alist_,q_,Nmax_]:=If[p==Infinity,
Table[Max[Table[qreduce[n*alist[[i]],q],{i,Length[alist]}]],{n,Nmax}],
Table[Sum[qreduce[n*alist[[i]],q]^p,{i,Length[alist]}],{n,Nmax}]]
dists[alist_,q_,Nmax_]:=(Print["p="< >ToString[p]< >", N="< >ToString[Nmax]< >","];/
Print["alpha="< >ToString[alist]< >"/"< >ToString[q]];/
dl = distlist[alist,q,Nmax];min = Infinity;count = 1;/
For[i = 1,i< =Nmax-1,i++,If[dl[[i]]<min,min = dl[[i]];/
Print[ToString[i]< >" "< >ToString[InputForm[dl[[i]]]]];If[i > Nmax/2,count++]]];/
Print["Distances="< >ToString[count]])
In[Citation2]:= ≪ dists.m
p-metric distances for exact p> =1 or Infinity
In[Citation3]:= p = 2
Out[Citation3] = 2
In[Citation4]:= dists[{27,97,514},1334,58]
p = 2, N = 58,
alpha = {27, 97, 514}/1334
1 274334
2 134188
13 128674
39 128218
41 125054
42 104720
44 95916
52 92468
54 91544
55 88338
57 81774
Distances = 9
In[Citation5]:= p = Infinity
Out[Citation5]= Infinity
In[Citation6]:= dists[{142160,309579,400742,428570},1000000,1548]
p = Infinity, N = 1548,
alpha = {142160, 309579, 400742, 428570}/1000000
1 428570
2 380842
7 194806
35 164735
77 162417
210 155820
317 143310
866 141620
901 141570
908 141560
943 141510
1118 141260
1153 141210
1160 141200
1195 141150
1253 129726
1260 121600
1295 97200
1470 90740
1512 83448
1547 81287
Distances = 15
In[Citation7]:= p = 13/10
13
Out[Citation7]=–
10
In[Citation8]:= dists[{16903,17700,21090},100000,148]
p = 13
–
10, N = 148,
alpha = {16903, 17700, 21090}/100000
1 17700*10^(3/5)*177^(3/10) + 16903*16903^(3/10) + 21090*21090^(3/10)
5 11500*2^(3/5)*5^(9/10)*23^(3/10) + 5450*5^(3/5)*218^(3/10) + 15485*15485^(3/10)
90 7000*7^(3/10)*10^(9/10) + 1900*10^(3/5)*19^(3/10) + 21270*21270^(3/10)
95 18500*2^(3/5)*5^(9/10)*37^(3/10) + 3550*5^(3/5)*142^(3/10) + 5785*5785^(3/10)
113 100*10^(3/5) + 16830*3^(3/5)*1870^(3/10) + 10039*10039^(3/10)
118 11400*2^(9/10)*5^(3/5)*57^(3/10) + 11380*2^(3/5)*2845^(3/10) + 5446*5446^(3/10)
119 6300*7^(3/10)*30^(3/5) + 11457*3^(3/5)*1273^(3/10) + 9710*9710^(3/10)
124 10400*2^(1/5)*5^(3/5)*13^(3/10) + 4028*2^(3/5)*1007^(3/10) + 15160*2^(9/10)*1895^(3/10)
142 13400*2^(9/10)*5^(3/5)*67^(3/10) + 5220*6^(3/5)*145^(3/10) + 226*226^(3/10)
147 1900*10^(3/5)*19^(3/10) + 230*230^(3/10) + 15259*15259^(3/10)
Distances = 9
Acknowledgments
The author thanks Mark Pearson for extending the code for uniform random search to GPU processors, and running it. This led to the solutions for p = 2 and presented here. The author also thanks Alon Agin, Henry Cohn, Alan Haynes, and Jens Marklof for helpful discussions. This work was carried out using the computational facilities of the Advanced Computing Research Center, University of Bristol—http://www.bristol.ac.uk/acrc/
Declaration of interests
No potential competing interest was reported by the author.
References
- Biringer, I., Schmidt, B. (2008). The three gap theorem and Riemannian geometry. Geom. Dedicata 136: 175–190. 10.1007/s10711-008-9283-8
- de Laat, D., Leijenhorst, N. (2022). Solving clustered low-rank semidefinite programs arising from polynomial optimization. ArXiv preprint arXiv:2202.12077.
- Haynes, A., Marklof, J. (2022). A five distance theorem for Kronecker sequences. Int. Math. Res. Not. 2022(24): 19747–19789. 10.1093/imrn/rnab205
- Haynes, A., Ramirez, J. J. (2021). Higher-dimensional gap theorems for the maximum metric. Int. J. Number Theory 17: 1665–1670. 10.1142/S1793042121500548
- Kellendonk, J., Lenz, D., Savinien, J. (2015). Mathematics of Aperiodic Order, Vol. 309. Basel: Springer.
- Machado, F. C., de Oliveira Filho, F. M. (2018). Improving the semidefinite programming bound for the kissing number by exploiting polynomial symmetry. Exp. Math. 27: 362–369. 10.1080/10586458.2017.1286273
- Rankin, R. A. (1955). The closest packing of spherical caps in n dimensions. Glasgow Math. J. 2: 139–144. 10.1017/S2040618500033219
- Sós, V. T. (1957). On the theory of Diophantine approximations. I 1 (on a problem of A. Ostrowski). Acta Math. Hungarica 8: 461–472. 10.1007/BF02020329
- Sós, V. T. (1958). On the distribution mod 1 of the sequence nα. Ann. Univ. Sci. Budapest, Eötvös Sect. Math. 1: 127–134.
- Świerczkowski, S. (1958). On successive settings of an arc on the circumference of a circle. Fundamenta Math. 46: 187–189. 10.4064/fm-46-2-187-189
- Weiß, C. (2022). Multi-dimensional Kronecker sequences with a small number of gap lengths. Discrete Math. Appl. 32: 69–74. 10.1515/dma-2022-0006