한
Problem workshop

One great problem, three kinds of immersion

From a story to your own conjecture

Problem stories open curiosity. The problem workshop is the next place, where curiosity becomes a testable idea.

  1. 1 · DiscoverMeet the questionLearn when it appeared and why it still holds people’s attention.
  2. 2 · ChallengeTest one caseMake your first observation in five minutes with a drawing, calculation, or colors.
  3. 3 · DevelopYou are hereBuild on ideasPublish an observation and grow it through comparisons, conjectures, and counterexamples.
Week 22 · ErdősResolved
Primary source

Erdős Distinct Distances — How Many Distinct Distances Among nn Points?

Intermediate· Posed 1946

Problem

For nn points in the plane, what is the minimum number of distinct distances g(n)g(n) they can determine? Erdős (1946) conjectured g(n)=Ω(n/log⁡n)g(n) = \Omega(n/\sqrt{\log n}).

Why it matters

nn points on a line give n−1n-1 distinct distances; a n×n\sqrt{n}\times\sqrt{n} integer grid gives ∼n/log⁡n\sim n/\sqrt{\log n} (related to the Landau-Ramanujan constant). Erdős conjectured the grid is essentially optimal.

Progress so far

Guth-Katz (2010, Annals 2015) proved g(n)≥c⋅n/log⁡ng(n) \ge c \cdot n/\log n using polynomial partitioning and ruled-surface analysis. The gap from the conjectured n/log⁡nn/\sqrt{\log n} is only a log⁡n\sqrt{\log n} factor. Won the 2010 Pólya Prize.

Further reading

💡 Explore together, one line at a time(0 contributions)

Contributions are not ranked by popularity. Curator feedback names what is clear or reproducible, and peer signals mean someone understood or actually reproduced it.

What did you notice?

You do not need a complete proof. A small observation can open the next path.

Markdown + KaTeX supported (`$x^2$` inline, `$$\sum_{k=1}^n k$$` display)
0 / 3000 characters

moderation policy. Sign in after submitting if you want to edit or delete this attempt from another device.

Loading…

Related concepts

Related mathematicians