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

Problem statement
---------------
Does every set of $n$ distinct points in $\mathbb{R}^2$ contain at most $n^{1+O(1/\log\log n)}$ many pairs which are distance 1 apart?

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)
-----------------------------
- `O(g(n))` means "at most a constant times g(n)" for large n.

Benchmarks / known results (from comments)
----------------------------------------
- In Erd\H{o}s dates this conjecture to 1946.
- In he offers \$300 for the upper bound $n^{1+o(1)}$.
- This would be the best possible, as is shown by a set of lattice points.
- It is easy to show that there are $O(n^{3/2})$ many such pairs.