Math Conjectures

Erdős Distinct-Distances Conjecture

OPENLandmarkConjectureProposed 1946 · Standard version

Canonical statement

Let
g(n)=min⁡P⊂R2∣P∣=n∣{ ∥x−y∥2:x,y∈P, x≠y }∣. g(n)=\min_{\substack{P\subset\mathbb R^2\\|P|=n}} \bigl|\{\,\|x-y\|_2:x,y\in P,\ x\ne y\,\}\bigr|.
There is an absolute constant c>0c>0 such that, for all n≥2n\geq2,
g(n)≥c nlog⁡n. g(n)\geq c\,\frac{n}{\sqrt{\log n}}.
View source LaTeX
Let
\[
  g(n)=\min_{\substack{P\subset\mathbb R^2\\|P|=n}}
    \bigl|\{\,\|x-y\|_2:x,y\in P,\ x\ne y\,\}\bigr|.
\]
There is an absolute constant \(c>0\) such that, for all \(n\geq2\),
\[
  g(n)\geq c\,\frac{n}{\sqrt{\log n}}.
\]
DG-002:[Erdos1946Distances][GuthKatz2015Distances][Sheffer2026Distances]
Discrete geometryCombinatorics

Notes

In his 1946 paper on sets of distances, Erdős asked how few distinct distances a set of nn points in the plane can determine, and conjectured that the minimum g(n)g(n) satisfies g(n)≥c n/log⁡ng(n)\ge c\,n/\sqrt{\log n} for an absolute constant c>0c>0 [Erdos1946Distances]. A n×n\sqrt n\times\sqrt n section of the integer lattice determines only O(n/log⁡n)O(n/\sqrt{\log n}) distances, by the classical count of integers representable as sums of two squares, so the conjectured bound would be sharp up to the constant.

After decades of incremental improvements to the exponent, Guth and Katz proved g(n)=Ω(n/log⁡n)g(n)=\Omega(n/\log n), converting the problem into an incidence question about lines in R3\mathbb R^3 and resolving it with the polynomial method [GuthKatz2015Distances]; the technique and its aftermath are surveyed by Sheffer [Sheffer2026Distances].

The Guth–Katz bound matches the conjecture up to a factor of order log⁡n\sqrt{\log n}. It remains open to remove this last factor, or more finely to determine the precise asymptotics of g(n)g(n).

References (3)

The boxed statement is the canonical open formulation — not a stronger variant or a related research program. The status reflects the catalog's last review; do your own literature search before investing serious effort.