Problem 89 — Visual explainer (undergrad)
=========================================

Problem statement
---------------
Does every set of $n$ distinct points in $\mathbb{R}^2$ determine $\gg n/\sqrt{\log n}$ many distinct distances?

Picture
-------
Plane picture:

y ^
  |    o      o
  |        o
  | o
  +-----------------> x

Question: what to look at
------------------------
- Restate the problem as: given the constraint, what asymptotic bound or
  structure must follow?
- Use the comments as benchmarks (best known bounds / constructions).

Context
-------
Area hint: incidence geometry / combinatorial geometry.

Notation (if it appears above)
-----------------------------
- `\gg` / `>>` means "at least a constant times" (for large parameters).

Benchmarks / known results (from comments)
----------------------------------------
- A $\sqrt{n}\times\sqrt{n}$ integer grid shows that this would be the best
  possible.
- Nearly solved by Guth and Katz who proved that there are always $\gg n/\log
  n$ many distinct distances.
- A stronger form (see [604]) may be true: is there a single point which
  determines $\gg n/\sqrt{\log n}$ distinct distances, or even $\gg n$ many
  such points, or even that this is true averaged over all points - for
  example, if $d(x)$ counts the number of distinct distances from $x$ then in
  Erd\H{o}s conjectured\[\sum_{x\in A}d(x) \gg \frac{n^2}{\sqrt{\log
  n}},\]where $A\subset \mathbb{R}^2$ is any set of $n$ points.