Bipartite distinct distances: can n red and n blue planar points span o(n/√log n) cross distances? (Erdős #661)
Statement
Are there, for all large $n$, 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)$ — distances measured only between points of the two different classes — is $$o\left(\frac{n}{\sqrt{\log n}}\right)?$$
Acceptance. FULLY RESOLVES: an explicit infinite family of configurations $X_n,Y_n\subset\mathbb{R}^2$ with $|X_n|=|Y_n|=n$ together with a proof that the number of distinct cross-class distances $d(x_i,y_j)$ is $o(n/\sqrt{\log n})$; OR a proof that every such bipartite configuration determines $\gg n/\sqrt{\log n}$ distinct cross-class distances. Machine-checkable (Lean/Coq) proofs preferred; else complete written proofs. ADVANCES: a proof of the comparative statement $F(2n)=o(f(2n))$ or its negation $F\gg f$ (as defined in the background); a resolution of the $\mathbb{R}^3$ analogue in either direction; or record small-$n$ bipartite configurations minimising the number of distinct cross distances, given by rational or algebraic coordinates with machine-verified exact counts and the search code included. Deliver the construction plus its count proof, the proof file, or the search code with certified records.
Background
A bipartite variant of Erdős's distinct distances problem, posed by Erdős and Pach [ErPa90] and repeated in [Er92e], [Er97e], [Er97f]; Erdős offered \$50 for a solution. Listed as open on erdosproblems.com/661 (fetched 2026-07-13, status 'open', tagged 'geometry | distances'; page last edited 11 January 2026). Context: the $\sqrt{n}\times\sqrt{n}$ integer grid determines only $O(n/\sqrt{\log n})$ distinct distances (Erdős, 1946), and splitting a grid into two classes gives the same $O(n/\sqrt{\log n})$ bipartite count — so the question is whether bipartite structure allows asymptotically fewer distances than the best known unrestricted examples. The Guth–Katz lower bound $\gg N/\log N$ for all-pairs distinct distances does not apply, since only cross-class pairs are counted here. The problem also makes sense (and is open) in $\mathbb{R}^3$, while in $\mathbb{R}^4$ it collapses entirely: Lenz observed that placing the $x_i$ and the $y_j$ on two orthogonal circles makes every cross distance equal to the same value — a single distinct distance. Erdős also asked a comparative form: if $F(2n)$ is the minimal number of distinct cross-class distances and $f(2n)$ the minimal number of distinct distances among any $2n$ planar points, is $F=o(f)$? Related problems: the distinct distances problem, Erdős #89 (erdosproblems.com/89), and its pinned variant, Erdős #604 (erdosproblems.com/604). The attacker's tool: explicit constructions — lattice pieces, families of concentric or intersecting circles, points on low-degree algebraic curves engineered so that cross distances coincide — with proven asymptotic counts; or Elekes-style incidence-geometry lower bounds to rule bipartite savings out; small-$n$ optimisation can hint at whether bipartite savings exist at all.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #661 (T. F. Bloom) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.