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

Problem statement
---------------
Are there, for all large $n$, some points $x_1,\ldots,x_n,y_1,\ldots,y_n\in \mathbb{R}^2$ such that the number of distinct distances $d(x_i,y_j)$ is\[o\left(\frac{n}{\sqrt{\log n}}\right)?\]

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→∞).

Benchmarks / known results (from comments)
----------------------------------------
- One can also ask this for points in $\mathbb{R}^3$.
- In $\mathbb{R}^4$ Lenz observed that there are
  $x_1,\ldots,x_n,y_1,\ldots,y_n\in \mathbb{R}^4$ such that $d(x_i,y_j)=1$ for
  all $i,j$, taking the points on two orthogonal circles.
- More generally, if $F(2n)$ is the minimal number of such distances, and
  $f(2n)$ is minimal number of distinct distances between any $2n$ points in
  $\mathbb{R}^2$, then is $F =o(f)$?