Erdős Problem #661

The question

Are there, for all large $n$, some points $x_1,\dots ,x_n,y_1,\dots ,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)?$$

We require all $2n$ points to be distinct; without any distinctness one could take all points equal and get a single distance. Writing $F(n)$ for the minimal number of such distances (minimalCrossDistances ℝ² n), the question asks whether $F(n)=o(n/\sqrt{\log n})$. This is equivalent to the existence, for all large $n$, of configurations whose count is at most $g(n)$ for some fixed $g(n)=o(n/\sqrt{\log n})$, since the infimum is attained.

The source adds that one can also ask this for points in ${\mathbb{R}}^3$. Taken literally, the question is easy there, since a cubic grid of $2n$ points determines only $O(n^{2/3})$ distinct distances, so we do not state it.

Formal statement (Lean 4)

From Formal Conjectures, module FormalConjectures.ErdosProblems.«661».

theorem erdos_661 :
    (fun n => (minimalCrossDistances ℝ² n : ℝ)) =o[atTop]
      (fun (n : ℕ) => (n : ℝ) / (n : ℝ).log.sqrt)

What counts as progress

• A Lean proof of the pinned statement (or of its negation, for a yes/no question) — checked by the Lean kernel against the upstream statement; a curator confirms before the problem is marked resolved.
• Partial results: special cases, weaker bounds, reductions — as verified claims.
• Computations and numerical evidence with published code (reproducible).
• Literature: the problem may have been solved or partly solved already — check erdosproblems.com/661. Report it as a literature claim.
• A precise flaw in the formal statement (a misformalisation) — report it upstream too.

Variants

• erdos_661.variants.little_o_distinct_distances — Let F(2n) be the minimal number of distinct distances d(x_i, y_j) for 2n distinct points x_1,…,x_n,y_1,…,y_n∈ ℝ^2, and f(2n) the minimal number of distinct…

References

• erdosproblems.com/661
• [ErPa90] Erdős, P. and Pach, J., Variations on the theme of repeated distances. Combinatorica (1990), 261--269.
• [Er92e] Erdős, Pál, Some Unsolved problems in Geometry, Number Theory and Combinatorics. Eureka (1992), 44-48.
• [Er97e] Erdős, Paul, Some of my favourite unsolved problems. Math. Japon. (1997), 527-537.
• [Er97f] Erdős, Paul, Some unsolved problems. Combinatorics, geometry and probability (Cambridge, 1993) (1997), 1-10.
• [Er46] Erdős, Paul, On sets of distances of $n$ points. Amer. Math. Monthly 53 (1946), 248--250.

Source and licence

Imported from Formal Conjectures (Erdős problems), commit 2f91d251c07f. Statements and descriptions © The Formal Conjectures Authors, Apache License 2.0; reformatted for this page.