erdős #89 · Erdős distance problem

← #88 · #90 → (packet.json; erdosproblems.com)

Does every set of $n$ distinct points in $R^{2}$ determine $≫ n / lo g n$ many distinct distances?

Worked, still open.

geometry · open · prize $500 · formalized (Lean) · 0 attempts

machinery: geometric,distinct-distances,polynomial-method,incidence-geometry,Guth-Katz,Elekes-Sharir,prime-distribution

use this record

vela registry pull vfr_37aec80d874a0239

vela reproduce examples/erdos-problems

evidence

unverified AI candidates (2)

gpt-erdos · GPT-5.2 Pro + Deep Research · unverified

This is basically the remaining gap in the **Erdős distinct distances problem**. Erdős showed that a (\sqrt n \times \sqrt n) integer grid can have only about [ \Theta!\left(\frac{n}{\sqrt{\log n}}\right) ] distinct distances, so you cannot hope for a general lower bound bigger than this (up to constants). ([MIT OpenCo…

candidate solution ↗

llm-hunter · codex 5.2 extra high, gpt 5.2, gpt pro 5.2 · unverified

3 LLM attack(s) recorded (codex 5.2 extra high, gpt 5.2, gpt pro 5.2); unverified.

candidate solution ↗

formal

AMS 52 · open (literature)

theorem erdos_89 :
    (fun (n : ℕ) => n/(n : ℝ).log.sqrt) =O[atTop] (fun n => (minimalDistinctDistances n : ℝ))

formal-conjectures/89.lean ↗

oeis

A131628 — Maximal size of an n-distance set in the plane.1,3,5,7,9,12,13 A186704 — The minimum number of distinct distances determined by n points in the Euclidean plane.0,1,1,2,2,3,3,4,4,5,5,5,6

links

#91Let

n

be a sufficiently large integer. Suppose

A \subset R^{2}

has

∣ A ∣ = n

and minimises the number of distinct distances between points in

A

. Prove that there are at least two (and probably many) such

A

which are non-similar.A186704 #1083Let

d \geq 3

, and let

f_{d} (n)

be the minimal

m

such that every set of

n

points in

R^{d}

determines at least

m

distinct distances. Estimate

f_{d} (n)

- in particular, is it true that

f_{d} (n) = n^{\frac{2}{d} - o (1)} ?

A186704

status