A set of N points in the plane determines at least cN/log N distinct distances

You need to know: Euclidean plane ${\mathbb R}^2$ , Euclidean distance $d(A,B)$ between points $A \in {\mathbb R}^2$ and $B \in {\mathbb R}^2$ .

Background: Let S be a finite set of points on the plane. Let $D(S)$ be the set of distinct real numbers $t>0$ such that $t=d(A,B)$ for some $A\in S$ and $B\in S$ . Let $|D(S)|$ be the number of elements in set $D(S)$ .

The Theorem: On 17th November 2010, Larry Guth and Nets Katz submitted to arxiv a paper in which they proved the existence of constant $c>0$ , such that $|D(S)| \geq c\frac{N}{\log N}$ for every set S of $N\geq 2$ points on the plane.

Short context: In 1946, Erdős posed the question what is the smallest number of distinct distances that can be determined by N points in the plane. Erdös checked that if the points are arranged in a square grid, then the number of distinct distances is proportional to $\frac{N}{\sqrt{\log N}}$ , and conjectured that this is optimal up to a constant factor. Many authors proved better and better lower bounds, with best before 2010 was $|D(S)| \geq cN^{0.8641}$ . The Theorem proves a much better lower bound, which almost matches the Erdős prediction.