Unit and distinct distances in typical norms

Noga Alon, Matija Bucić, Lisa SauermannGeometric 2023 · arXiv

TL;DR

This paper tackles fundamental problems in discrete geometry concerning the number of unit distances and distinct distances determined by points in Euclidean space, but with a twist: it considers these problems in the context of arbitrary norms, not just the standard Euclidean norm. The authors provide nearly tight answers for "typical" norms, showing that for most norms, the number of unit distances is surprisingly low, while the number of distinct distances is surprisingly high.

What Problem Does This Paper Address?

The Erdős unit distance problem asks for the maximum number of pairs of points at distance 1 among $n$ points in the plane. The Erdős distinct distances problem asks for the minimum number of distinct distances determined by $n$ points. These problems are classical in Euclidean geometry. This paper extends these questions to general $d$-dimensional normed spaces. The key challenge is that the geometry of norms can be very different from the familiar Euclidean geometry, leading to potentially different behaviors. The authors aim to understand how these problems behave for "most" norms, not just specific ones like the Euclidean norm. They also address the Hadwiger-Nelson problem (coloring points such that points at distance 1 have different colors) for general norms.

Methods

The paper employs a sophisticated blend of techniques from combinatorics, discrete geometry, topology, and algebraic geometry. A core strategy involves analyzing linear dependencies among unit vectors. For upper bounds, they show that if a norm allows for many unit distances, there must be many rational linear dependencies between the corresponding unit vectors. They then prove that "typical" norms lack such extensive linear dependencies. For lower bounds, they construct specific point configurations using Minkowski sums and geometric arguments. The notion of "typical" norms is formalized using Baire category theory, where a property holds for "most" norms if it holds outside a "meagre set" (a countable union of nowhere-dense sets) in the space of norms.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • "Typical" Norms Behave Differently: The most striking insight is that most norms exhibit behavior opposite to what might be expected from the Euclidean case. For most norms, the number of unit distances is significantly smaller than for the Euclidean norm, while the number of distinct distances is larger.
  • Linear Dependencies as a Geometric Constraint: The paper leverages the idea that the number of linear dependencies among unit vectors associated with distances provides a powerful constraint on the geometric structure induced by a norm.
  • Baire Category for "Typicality": The use of Baire category theory provides a rigorous framework for defining and proving results for "most" norms, allowing them to characterize the behavior of a vast majority of norms.
  • Bridging Combinatorics and Geometry: The proofs ingeniously combine combinatorial counting arguments with geometric constructions and algebraic tools, demonstrating the power of interdisciplinary approaches in discrete geometry.

Key Results

  • Unit Distances: For "most" $d$-norms, any set of $n$ points determines at most $O(d \cdot n \log n)$ unit distances. This is shown to be asymptotically tight by a lower bound of $\Omega(d \cdot n \log n)$ for all $d$-norms.
  • Distinct Distances: For "most" $d$-norms, any set of $n$ points determines at least $(1 - o(1))n$ distinct distances. This is tight up to the $o(1)$ term.
  • Hadwiger-Nelson Problem: For "most" 2-norms, the chromatic number of the unit distance graph is 4. This is particularly interesting because the Euclidean norm requires at least 5 colors, disproving a conjecture.

Limitations and Future Work

The authors acknowledge that their results for the distinct distances problem are tight up to an $o(1)$ term, and for the unit distances problem, there's a constant factor gap between the upper bound for typical norms and the lower bound for all norms. They suggest that closing this gap might require new ideas. They also pose an open question about the existence of a zero-one law for typical $d$-norms regarding graph embeddings in their unit distance graphs. Additionally, they highlight the difficulty in characterizing all graphs that can be subgraphs of the unit distance graph of any $d$-norm. The paper also touches upon Petty's conjecture regarding equilateral sets and its connection to the number of distinct distances.

Summary updated

Abstract

Erdős' unit distance problem and Erdős' distinct distances problem are among the most classical and well-known open problems in discrete mathematics. They ask for the maximum number of unit distances, or the minimum number of distinct distances, respectively, determined by $n$ points in the Euclidean plane. The question of what happens in these problems if one considers normed spaces other than the Euclidean plane has been raised in the 1980s by Ulam and Erdős and attracted a lot of attention over the years. We give an essentially tight answer to both questions for almost all norms on $\mathbb{R}^d$, in a certain Baire categoric sense. For the unit distance problem we prove that for almost all norms $\|.\|$ on $\mathbb{R}^d$, any set of $n$ points defines at most $\frac{1}{2} d \cdot n \log_2 n$ unit distances according to $\|.\|$. We also show that this is essentially tight, by proving that for every norm $\|.\|$ on $\mathbb{R}^d$, for any large $n$, we can find $n$ points defining at least $\frac{1}{2}(d-1-o(1))\cdot n \log_2 n$ unit distances according to $\|.\|$. For the distinct distances problem, we prove that for almost all norms $\|.\|$ on $\mathbb{R}^d$ any set of $n$ points defines at least $(1-o(1))n$ distinct distances according to $\|.\|$. This is clearly tight up to the $o(1)$ term. We also answer the famous Hadwiger--Nelson problem for almost all norms on $\mathbb{R}^2$, showing that their unit distance graph has chromatic number $4$. Our results settle, in a strong and somewhat surprising form, problems and conjectures of Brass, Matoušek, Brass-Moser-Pach, Chilakamarri, and Robertson. The proofs combine combinatorial and geometric ideas with tools from Linear Algebra, Topology and Algebraic Geometry.
BibTeX
@inproceedings{alon2023unit,
  author = {Noga Alon and Matija Bucić and Lisa Sauermann},
  title = {{Unit and distinct distances in typical norms}},
  booktitle = {Geometric},
  year = {2023},
}
Figure