On Few-Distance Sets in the Plane

Basic Information

• Paper ID: 2510.09800
• Title: On Few-Distance Sets in the Plane
• Author: Lucas Wang
• Classification: math.MG (Metric Geometry), math.CO (Combinatorics)
• Submission Date: October 10, 2025 to arXiv
• Paper Link: https://arxiv.org/abs/2510.09800

Abstract

This paper investigates the maximum cardinality of point sets in the plane that determine at most k distances. Let $g(k)$ denote the maximum size of a planar point set determining at most k distances. The author proves: $\frac{\pi}{3}C(\Lambda_{hex}) k\sqrt{\log k} (1+o(1)) \leq g(k) \leq C k\log k$

This establishes the growth rate $g(k) \asymp k\sqrt{\log k}$ and provides explicit constants derived from the hexagonal lattice. For arbitrary arithmetic lattices $\Lambda$, the author further proves: $g_\Lambda(k) \geq \frac{\pi}{4} S^*(\Lambda) k\sqrt{\log k} (1+o(1))$

Additionally, the paper provides quantitative stability results: unless the point set X is line-heavy or admits two popular non-parallel translations, either almost all ordered pairs lie below the upper quantile of the distance multiset (near-central localization), or a constant proportion of X∩W lies in a single residue class modulo 2Λ.

Research Background and Motivation

Problem Context

This research originates from the inverse problem of the classical Erdős distance problem. The original problem was resolved by Guth-Katz, proving that n points in the plane determine at least $\Omega(n/\log n)$ distinct distances. This paper studies the inverse problem: given at most k distances, what is the maximum number of points a planar point set can contain?

Problem Significance

1. Theoretical Importance: This is a fundamental problem in combinatorial geometry, connecting metric geometry, number theory, and additive combinatorics
2. Technical Challenges: Requires integrating lattice theory, incidence geometry, and additive energy methods
3. Applied Value: Related to coding theory, discrete geometric optimization, and other fields

Limitations of Existing Methods

• The Guth-Katz upper bound $g(k) \lesssim k\log k$ lacks precision
• Lattice window constructions only yield the lower bound $g(k) \gtrsim k\sqrt{\log k}$
• Absence of explicit constants and quantitative stability analysis

Research Motivation

To determine the precise growth rate of $g(k)$, provide explicit constants, and understand the structural characteristics of extremal constructions.

Core Contributions

1. Determined Precise Growth Rate: Proves $g(k) \asymp k\sqrt{\log k}$, closing the logarithmic factor gap between upper and lower bounds
2. Explicit Constants: Provides explicit Bernays constants $C(\Lambda_{hex})$ for the hexagonal lattice
3. Unified Lower Bounds for Lattice Families: Establishes unified lower bound formulas for all arithmetic lattices $\Lambda$
4. Quantitative Stability Theorem: Characterizes structural features of near-optimal constructions
5. Technical Innovations: Develops new techniques in lattice window analysis and additive energy methods

Methodology Details

Problem Formulation

Given a positive integer k, solve: $g(k) := \max\{|X| : X \subset \mathbb{R}^2, |D(X)| \leq k\}$ where $D(X) = \{|x-y| : x \neq y \in X\}$ is the set of distances determined by point set X.

Main Technical Framework

1. Lower Bound Construction: Lattice Window Method

For arithmetic lattice $\Lambda = \mathbb{Z}v_1 \oplus \mathbb{Z}v_2$, consider a disk window: $W_R = (\tau + \Lambda) \cap B(z, R)$

By the Bernays-Landau asymptotic formula, the number of distances is: $|D(W_R)| = \frac{C(\Lambda)}{s(\Lambda)} \frac{4R^2}{\sqrt{\log(4R^2/s(\Lambda))}}(1 + o(1))$

2. Upper Bound: Incidence Geometry Method

Using the Guth-Katz result, any n-point planar set determines at least $c n/\log n$ distinct distances, thus: $g(k) \leq C k \log k$

3. Key Lemma: Ordered Pair Counting

Define ordered distance counting: $Q_{ord}(X) := \sum_{t \in D(X)} m_t^2$ where $m_t = \#\{(p,q) \in X^2 : p \neq q, |p-q| = t\}$.

By Cauchy-Schwarz inequality: $Q_{ord}(X) \geq \frac{n^2(n-1)^2}{k}$

Technical Innovations

1. Explicit Lattice Parameters

Introduce normalized parameters: $S^*(\Lambda) := \frac{s(\Lambda)}{A(\Lambda)C(\Lambda)}$ where $s(\Lambda)$ is the proportionality constant, $A(\Lambda)$ is the covolume, and $C(\Lambda)$ is the Bernays constant.

2. Inner-Regular Window Theory

Define the concept of inner-regular windows, establishing precise control of distance realization in lattice windows:

Lemma 2.11: For lattice $\Lambda$ and covering radius $\mu(\Lambda)$, when $R > \mu(\Lambda)$: $\{\lambda \in \Lambda : |\lambda| \leq 2R - 2\mu(\Lambda)\} \subseteq \{x-y : x,y \in (\tau + \Lambda) \cap B(0,R)\}$

3. Additive Energy Analysis

Analyze point set structure through additive energy $E_+(X) = \sum_v r_X(v)^2$: $Q_{ord}(X) \leq E_+(X) + C n^3 \log n + O(n^2)$

Experimental Setup

Theoretical Verification Framework

This is primarily theoretical work, verified through:

1. Asymptotic Analysis: Verification of Bernays-Landau formula applications
2. Constant Computation: Computing specific parameters for the hexagonal lattice
3. Boundary Case Verification: Validating known results for small k values

Key Parameters

• Hexagonal lattice: $s(\Lambda_{hex}) = 2/\sqrt{3}$
• Computation of covering radius and lattice constants
• Selection of stability parameters

Experimental Results

Main Theorem Results

Theorem 3.4 (Precise Bounds for Arithmetic Lattices): For normalized arithmetic lattices $\Lambda$ ($\lambda_1(\Lambda) = 1$), there exists $k_0(\Lambda)$ such that for all $k \geq k_0(\Lambda)$: $\frac{\pi}{4} S^*(\Lambda) k\sqrt{\log k} (1 + o_\Lambda(1)) \leq g_\Lambda(k) \leq C k \log k$

Theorem 7.1 (Global Result): $\frac{\pi}{3} C(\Lambda_{hex}) k\sqrt{\log k} (1 + o(1)) \leq g(k) \leq C k \log k$

Stability Results

Theorem 7.3 (Quantitative Stability): For point set $X \subset \mathbb{R}^2$, $|X| = n$, $|D(X)| \leq k$, $k \leq C n/\log n$, one of the following must hold:

1. Some line contains at least $cn$ points
2. There exist non-parallel vectors $v_1, v_2$ and a lattice rectangle $W$ with large corresponding overlap
3. There exists $z \in X$ such that $|X \cap B(z, t_*)|$ is close to $n$

Key Estimates

By Proposition 5.1, the number of distances in inner-regular window $W_R$ satisfies: $\frac{C(\Lambda)}{s(\Lambda)} \frac{4(1-c)^2R^2}{\sqrt{\log(4R^2/s(\Lambda))}}(1 + o(1)) \leq |D(W_R)| \leq \frac{C(\Lambda)}{s(\Lambda)} \frac{4R^2}{\sqrt{\log(4R^2/s(\Lambda))}}(1 + o(1))$

Related Work

History of Distance Problems

1. Erdős Distance Problem: Guth-Katz (2015) proved $m(n) \gtrsim n/\log n$
2. Small k Cases: Erdős-Fishburn determined exact values for $k \leq 5$
3. Lattice Constructions: Lower bounds obtained via Bernays-Landau asymptotics

Related Techniques

1. Incidence Geometry: Elekes-Sharir reduction and Guth-Katz methods
2. Additive Combinatorics: Balog-Szemerédi-Gowers theorem and Freiman theorem
3. Lattice Theory: Quadratic form representation theory and covering properties

Advantages of This Work

• First determination of precise growth rate $k\sqrt{\log k}$
• Provides explicit constants and unified framework
• Develops new stability theory

Conclusions and Discussion

Main Conclusions

1. Established precise growth rate $g(k) \asymp k\sqrt{\log k}$
2. Hexagonal lattice provides optimal lower bound construction
3. Near-optimal constructions exhibit specific structural features

Limitations

1. Exact constant values remain improvable
2. Stability results show strong parameter dependence
3. Analysis of non-arithmetic cases is incomplete

Future Directions

1. Improve explicit constants
2. Extend to higher dimensions
3. Study analogous problems under other geometric constraints

In-Depth Evaluation

Strengths

1. Theoretical Depth: Resolves a long-standing open problem, determining precise growth rate
2. Technical Innovation: Skillfully combines lattice theory, additive combinatorics, and incidence geometry
3. Result Completeness: Provides not only asymptotic results but also explicit constants and stability analysis
4. Method Uniformity: Establishes unified framework for all arithmetic lattices

Weaknesses

1. Computational Complexity: Explicit constant computation is intricate
2. Scope of Application: Primarily limited to arithmetic lattice cases
3. Stability Parameters: Quantitative stability involves many parameter dependencies

Impact

1. Academic Value: Resolves fundamental problem in combinatorial geometry
2. Methodological Contribution: Developed techniques applicable to related problems
3. Theoretical Completeness: Provides important supplement to distance problem theory

Applicable Scenarios

1. Discrete geometric optimization
2. Distance set construction in coding theory
3. Quadratic form representation in number theory
4. Structure analysis in additive combinatorics

References

Key references in the paper include:

1. P. Erdős and P. C. Fishburn, "Maximum planar sets that determine k distances"
2. L. Guth and N. H. Katz, "On the Erdős distinct distances problem in the plane"
3. G. Elekes and M. Sharir, "Incidences in three dimensions and distinct distances in the plane"
4. Classical Bernays-Landau asymptotic theory literature
5. Related literature on BSG theorem and Freiman theorem in additive combinatorics

Through elegant mathematical analysis, this paper resolves an important extremal problem in planar geometry, with its technical methods and theoretical results holding significant value for the combinatorial geometry field.