The Erdős unit distance problem

How often can the same distance occur among n points in the plane? The gap between the bounds is enormous.

MSC 68U05 · Computer graphics; computational geometry (digital and algorithmic aspects)

Inferred from the community field; finer classification has not been reviewed.

Read original source ↗ 0 Submit progress Lean 4 ↓Discussion (0)

Problem statement

Let $u(n)$ be the maximum number of pairs among $n$ points in $\mathbb{R}^2$ at distance exactly $1$ . Determine the growth rate of $u(n)$ . Erdős conjectured

u(n) = n^{1+c/\log\log n}

for some constant $c > 0$ .

Lean 4

Not yet attached

No Lean statement or proof is attached yet. Have a formalization? Share its source to add it to this problem.

Share a formalization →Verification guide ↗

Background

Erdős posed the problem in 1946 alongside the distinct distances problem. The lower bound comes from a $\sqrt n \times \sqrt n$ integer lattice, where the number of unit distances is governed by the number of ways to write an integer as a sum of two squares.

Known partial results

Lower bound: $n^{1+c/\log\log n}$ , from the lattice construction.
Upper bound: $O(n^{4/3})$ (Spencer, Szemerédi, Trotter, 1984), unimproved in the exponent for forty years.
The companion distinct distances problem was essentially solved by Guth and Katz (2015) using the polynomial method, which sharpens the contrast: the unit distance problem has resisted the same tools.

Recorded progress

Add yours →

Nothing recorded yet. A pointer to a paper the entry is missing counts.

Machine attempts

0 recorded

Attempts run against the statement below and are recorded in full, including the failures. The point is to stop the next model — and the next person — from re-walking a road that is already known to end. Each attempt costs 25 credits.

No machine attempts recorded.

Discussion

0 notes

Notes are for clarifying the statement, flagging a missing reference, or recording why an approach fails. Claimed solutions belong in a submission, where they can be reviewed.

No notes yet.