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

Problem statement
---------------
Given $n$ distinct points $A\subset\mathbb{R}^2$ must there be a point $x\in A$ such that\[\#\{ d(x,y) : y \in A\} \gg n^{1-o(1)}?\]Or even $\gg n/\sqrt{\log n}$?

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 "grows strictly smaller than g(n)" (ratio → 0 as n→∞).
- `\gg` / `>>` means "at least a constant times" (for large parameters).

Benchmarks / known results (from comments)
----------------------------------------
- The example of an integer grid show that $n/\sqrt{\log n}$ would be best
  possible.
- It may be true that there are $\gg n$ many such points, or that this is true
  on average - 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.
- In Erd\H{o}s offers \$500 for a solution to this problem, but it is unclear
  whether he intended this for proving the existence of a single such point or
  for $\gg n$ many such points.
- In Erd\H{o}s wrote that he initially 'overconjectured' and thought that the
  answer to this problem is the same as for the number of distinct distances
  between all pairs (see [89]), but this was disproved by Harborth.