OctoInformBeta

Planar distinct distances and unit-distance bounds

For a point xx of a finite set P⊂ℝ2P\subset\mathbb{R}^2, the set of distinct nonzero Euclidean distances from the pin xx to the other points of PP is Dx(P)={‖y−x‖:y∈P\{x}}D_x(P)=\{\lVert y-x\rVert : y\in P\setminus\{x\}\}. The distinct-distance problem asks for the least size of the union ⋃x∈PDx(P)\bigcup_{x\in P}D_x(P) over all nn-point sets P⊂ℝ2P\subset\mathbb{R}^2. The pinned problem asks for distances with a common source: a lower bound on max⁡x∈P|Dx(P)|\max_{x\in P}|D_x(P)| over all nn-point sets P⊂ℝ2P\subset\mathbb{R}^2. The weak pinned Erdős distinct-distance conjecture asserts that for every ε>0\varepsilon>0, every sufficiently large nn-point set P⊂ℝ2P\subset\mathbb{R}^2 has a pin xx with |Dx(P)|≥n1−ε|D_x(P)|\ge n^{1-\varepsilon}.

Erdős initiated the planar distinct-distance problem in 1946. In that work he showed that the square lattice gives nn-point sets PP for which |⋃x∈PDx(P)|\bigl|\bigcup_{x\in P}D_x(P)\bigr| is at most a constant multiple of n/log⁡nn/\sqrt{\log n}. Guth and Katz proved that every nn-point set in the plane determines at least a constant multiple of n/log⁡nn/\log n distinct distances. For pinned distances, Erdős stated the question of the weak pinned conjecture explicitly in 1957. Solymosi and Tóth proved that every nn-point planar set PP has a pin xx with |Dx(P)||D_x(P)| at least of order n6/7n^{6/7}. Tardos improved the exponent 6/76/7. Katz and Tardos then obtained the pinned lower bound for every exponent below (48−14e)/(55−16e)=0.864137…(48-14e)/(55-16e)=0.864137\ldots. The sharper pinned conjecture, recalled in the introduction of Lund and Petridis, asks for a pin xx with |Dx(P)||D_x(P)| of order n/log⁡nn/\sqrt{\log n}. The weak pinned conjecture appears under its present name, for example, as Conjecture 4.7 of Dewar, Frankl, Mansfield, Nixon, Passant and Warren.

For distinct points x,y∈Px,y\in P, the distance fiber size is kP(x,y)=|{z∈P\{x}:‖z−x‖=‖y−x‖}|k_P(x,y)=|\{z\in P\setminus\{x\} : \lVert z-x\rVert=\lVert y-x\rVert\}|. For n≥2n\ge2 and s>0s>0, let Fn(s)=sup⁡P|{(x,y)∈P2:x≠y,kP(x,y)≥ns}|/(n(n−1))F_n(s)=\sup_P|\{(x,y)\in P^2 : x\ne y,\ k_P(x,y)\ge n^s\}|/(n(n-1)), the supremum taken over all nn-point sets P⊂ℝ2P\subset\mathbb{R}^2. The preprint proves the theorem that Fn(s)→0F_n(s)\to0 as n→∞n\to\infty for every fixed s>0s>0. As a corollary, for every ε>0\varepsilon>0, the largest fraction of pins xx with |Dx(P)|<n1−ε|D_x(P)|<n^{1-\varepsilon} among the points of an nn-point set P⊂ℝ2P\subset\mathbb{R}^2 tends to 00 as n→∞n\to\infty. This proves the weak pinned conjecture.

The Lean library PinnedDistances proves the theorem and the corollary, with no hypothesis beyond s>0s>0 and ε>0\varepsilon>0. Lean has checked every result of the Lean library, so the Lean library is the reference. Each result on these pages is the Lean library’s, stated as the Lean library states it and linked to the Lean declaration behind it. Where the preprint states a result differently, the page gives the Lean library’s statement, with the preprint’s beside it. The preprint is a guide only: it gives the results their order and their names.

The Lean library: PinnedDistances

PinnedDistances is a Lean library: 19 items, in seven groups. Each has a page written by OctoInform, listed below.

§1. Introduction 3 items
  1. §1 (setting): distance sets, fiber sizes and F_n(s) Rich pairs and bad pins of planar point sets. §1
  2. Theorem 1.1 [Uniform vanishing of large distance fibers] Rich pinned distance pairs are rare in large planar sets. §1
  3. Corollary 1.2 [Weak pinned distance conjecture] Most pins of a large planar set determine many distances. §1
§2. A graph of large distance classes 4 items
  1. §2 (setting): Θ, the critical exponent and the fixed parameters Rich pair fractions never increase, and a counterexample fixes exponents. §2
  2. Lemma 2.1 [Uniform tail at a continuity point] Uniform tail bounds for the maximal rich pair fraction. §2
  3. §2 (setting): fiber systems and their sampling laws Fiber systems and two ways to sample an edge. §2
  4. Proposition 2.2 [The prepared graph] Failure of the weak pinned distances statement gives prepared graphs. §2
§3. Arithmetic and nested partitions 5 items
  1. §3 (setting): two coordinates, raw depths and the product formula The product formula and raw depths in a number field. §3
  2. §3 (setting): random nested grids and depths Random nested dyadic grids and the depth of a pair. §3
  3. Lemma 3.1 [Grid error] The grid error has a universal mean and an exponential tail. §3
  4. Lemma 3.2 [Depth identity] Ultrametric depths split into giant, overlap and potential terms. §3
  5. §3 (setting): the additive overlap identity and the scales W₂, A, W Pair overlaps split into a constant and two potentials. §3
§4. Small cells and fiber mass 2 items
  1. Lemma 4.1 [Small fiber slices] A bound on the cell mass of small fiber slices. §4
  2. §4 (proof): small cells carry o(W+1) of the overlap Small cells carry o(W+1)o(W+1) of the pair overlap. §4
§5. Variance from off-diagonal sampling 1 item
  1. Lemma 5.1 [Variance bound] Variance bound for sampling cells by uniform laws. §5
§6. The case of unbounded overlap scale 2 items
  1. Lemma 6.1 [Tree distance fluctuations] Balanced laminar cuts bound cut distance fluctuations from below. §6
  2. §6 (proof): the unbounded case is impossible Prepared arithmetic models cannot have overlap scales tending to infinity. §6
§7. Bounded scale and a limiting fiber map 2 items
  1. Lemma 7.1 [Nonatomic Möbius obstruction] An obstruction to pushing nonatomic laws through random Möbius maps. §7
  2. §7 (proof): the bounded case is impossible, and Theorem 1.1 Prepared arithmetic models cannot grow with vanishing error. §7

No item matches.