An official website of the United States government
Abstract The three-distance theorem (also known as the three-gap theorem or Steinhaus problem) states that, for any given real number $$\alpha $$ and integer $$N$$, there are at most three values for the distances between consecutive elements of the Kronecker sequence $$\alpha , 2\alpha ,\ldots , N\alpha $$ mod 1. In this paper, we consider a natural generalization of the three-distance theorem to the higher-dimensional Kronecker sequence $$\vec \alpha , 2\vec \alpha ,\ldots , N\vec \alpha $$ modulo an integer lattice. We prove that in 2D, there are at most five values that can arise as a distance between nearest neighbors, for all choices of $$\vec \alpha $$ and $$N$$. Furthermore, for almost every $$\vec \alpha $$, five distinct distances indeed appear for infinitely many $$N$$ and hence five is the best possible general upper bound. In higher dimensions, we have similar explicit, but less precise, upper bounds. For instance, in 3D, our bound is 13, though we conjecture the truth to be 9. We furthermore study the number of possible distances from a point to its nearest neighbor in a restricted cone of directions. This may be viewed as a generalization of the gap length in 1D. For large cone angles, we use geometric arguments to produce explicit bounds directly analogous to the three-distance theorem. For small cone angles, we use ergodic theory of homogeneous flows in the space of unimodular lattices to show that the number of distinct lengths is (1) unbounded for almost all $$\vec \alpha $$ and (2) bounded for $$\vec \alpha $$ that satisfy certain Diophantine conditions.
more »
« less
Higher-dimensional gap theorems for the maximum metric
Recently, the first author together with Jens Marklof studied generalizations of the classical three distance theorem to higher-dimensional toral rotations, giving upper bounds in all dimensions for the corresponding numbers of distances with respect to any flat Riemannian metric. In dimension two they proved a five distance theorem, which is best possible. In this paper, we establish analogous bounds, in all dimensions, for the maximum metric. We also show that in dimensions two and three our bounds are best possible.
more »
« less
- Award ID(s):
- 2001248
- PAR ID:
- 10218051
- Date Published:
- Journal Name:
- International Journal of Number Theory
- ISSN:
- 1793-0421
- Page Range / eLocation ID:
- 1 to 6
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
We study the problem of representing all distances between n points in Rd, with arbitrarily small distortion, using as few bits as possible. We give asymptotically tight bounds for this problem, for Euclidean metrics, for ℓ1 (a.k.a.~Manhattan) metrics, and for general metrics. Our bounds for Euclidean metrics mark the first improvement over compression schemes based on discretizing the classical dimensionality reduction theorem of Johnson and Lindenstrauss (Contemp.~Math.~1984). Since it is known that no better dimension reduction is possible, our results establish that Euclidean metric compression is possible beyond dimension reduction.more » « less
-
We consider a social choice setting in which agents and alternatives are represented by points in a metric space, and the cost of an agent for an alternative is the distance between the corresponding points in the space. The goal is to choose a single alternative to (approximately) minimize the social cost (cost of all agents) or the maximum cost of any agent, when only limited information about the preferences of the agents is given. Previous work has shown that the best possible distortion one can hope to achieve is 3 when access to the ordinal preferences of the agents is given, even when the distances between alternatives in the metric space are known. We improve upon this bound of 3 by designing deterministic mechanisms that exploit a bit of cardinal information. We show that it is possible to achieve distortion 1+sqrt(2) by using the ordinal preferences of the agents, the distances between alternatives, and a threshold approval set per agent that contains all alternatives for whom her cost is within an appropriately chosen factor of her cost for her most-preferred alternative. We show that this bound is the best possible for any deterministic mechanism in general metric spaces, and also provide improved bounds for the fundamental case of a line metric.more » « less
-
Metric embeddings traditionally study how to map n items to a target metric space such that distance lengths are not heavily distorted. However, what if we are only interested in preserving the relative order of the distances, rather than their exact lengths? In this paper, we explore the fundamental question: given triplet comparisons of the form “item i is closer to item j than to item k,” can we find low-dimensional Euclidean representations for the n items that respect those distance comparisons? Such order-preserving embeddings naturally arise in important applications—such as recommendations, ranking, crowdsourcing, psychometrics, and nearest-neighbor search—and have been studied since the 1950s under the name of ordinal or non-metric embeddings. Our main results include: Nearly-Tight Bounds on Triplet Dimension: We introduce the concept of triplet dimension of a dataset and show, surprisingly, that in order for an ordinal embedding to be triplet-preserving, its dimension needs to grow as n^2 in the worst case. This is nearly optimal, as n−1 dimensions always suffice. Tradeoffs for Dimension vs (Ordinal) Relaxation: We relax the requirement that every triplet must be exactly preserved and present almost tight lower bounds for the maximum ratio between distances whose relative order was inverted by the embedding. This ratio is known as (ordinal) relaxation in the literature and serves as a counterpart to (metric) distortion. New Bounds on Terminal and Top-k-NNs Embeddings: Moving beyond triplets, we study two well-motivated scenarios where we care about preserving specific sets of distances (not necessarily triplets). The first scenario is Terminal Ordinal Embeddings where we aim to preserve relative distance orders to k given items (the “terminals”), and for that, we present matching upper and lower bounds. The second scenario is top-k-NNs Ordinal Embeddings, where for each item we aim to preserve the relative order of its k nearest neighbors, for which we present lower bounds. To the best of our knowledge, these are some of the first tradeoffs on triplet-preserving ordinal embeddings and the first study of Terminal and Top-k-NNs Ordinal Embeddings.more » « less
-
Abstract In the synthetic geometric setting introduced by Kunzinger and Sämann, we present an analogue of Toponogov’s Globalisation Theorem which applies to Lorentzian length spaces with lower (timelike) curvature bounds. Our approach utilises a “cat’s cradle” construction akin to that which appears in several proofs in the metric setting. On the road to our main result, we also provide a lemma regarding the subdivision of triangles in spaces with a local lower curvature bound and a synthetic Lorentzian version of the Lebesgue Number Lemma. Several properties of time functions and the null distance on globally hyperbolic Lorentzian length spaces are also highlighted. We conclude by presenting several applications of our results, including versions of the Bonnet–Myers Theorem and the Splitting Theorem for Lorentzian length spaces with local lower curvature bounds, as well as discussion of stability of curvature bounds under Gromov–Hausdorff convergence.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1142/S1793042121500548
