Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated Oct 8

Problem 661

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)?

Status. Open.

Source. erdosproblems.com/661, accessed 2026-09-04. Cite as: T. F. Bloom, Erdős Problem #661, https://www.erdosproblems.com/661.

Formalization. None recorded.

Current assessment

A literature check on 6 September 2026 covered the published bipartite paper, its arXiv record and author publication list, and searches for later general bipartite distance bounds. It located no exact-target resolution. This is a bounded currentness check, not a proof of openness.

A complete own-words reconstruction of Theorem 3, its balanced specialization and every essential local step is now supplied on the linked source result pages. It includes explicit overlap, rotation-convention and regulus repairs, and precisely stated external Guth--Katz premises. Its living verification record is Verified at the stated scope after independent source-based review, retained with the source as its final review; the external Guth--Katz proofs are not compiled or reviewed here. The lattice construction is separately Verified at the stated scope in that review, relative to its external counting premise, whose proof remains uncompiled. Theorem 4's separate unbalanced proof remains uncompiled in this account. These additions do not change the status of the little-o question.

Progress

The balanced bipartite question remains unresolved by the bounds below. Write $D(m,n)$ for the minimum number of distances between planar sets of $m$ and $n$ points, where $m\leq n$ . Mathialagan's published Theorem 3 gives

D(m,n)=\Omega\!\left(\frac{\sqrt{mn}}{\log n}\right) \qquad(n^{1/3}\leq m\leq n).

At $m=n$ this is $\Omega(n/\log n)$ . The logarithm is outside the radical: this lower bound is compatible with the requested $o(n/\sqrt{\log n})$ upper bound and does not disprove the question. See Mathialagan's Theorem 3 (published version, p. 3; proof on pp. 9--23).

Known Results

Mathialagan's p. 4, Table 1 and Question 5 retain a gap between the balanced lower bound and $D(n,n)=O(n/\sqrt{\log n})$ . The latter comes from the ordinary lattice construction applied to a set of $2n$ points, partitioned into two sets. The complete lattice construction and balanced partition are supplied relative to the counting premise cited by Erdős 1946. They supply big-O, not the requested little-o estimate.

The proof connects bipartite distance energy to incidences of lines in three dimensions through a modified Elekes--Sharir--Guth--Katz reduction. Theorem 4 also gives $D(m,n)=\Omega(\sqrt{mn})$ for $2\leq m\leq n^{1/3}$ , using the crossing lemma; that unbalanced range does not include the question's $m=n$ regime. See Mathialagan's paper (pp. 3--4, §§3--5).

Linked library material

These entries are derived from explicit links on library pages. They are navigation only and do not by themselves record mathematical progress.

Linked from (24)

Problem 89 Distance Problems On the Erdős distinct distance problem in the plane Theorem 1.2 (p. 156): N² lines in R³ with ≲ N in any plane or regulus have ≲ N³k⁻² points on k lines Theorem 4.5 (p. 176): k-rich points of L lines in R³ with at most B in a plane distance_problems/mathialagan_2021_bipartite_distinct_distances_plane Corollary 37: The one possible affine intersection exception External Guth--Katz incidence inputs for Theorem 3 Lemma 25: Point and plane caps Lemma 26: A regulus cap from few bipartite distances Lemma 34: The line and circle cases Proposition 19: Positive-distance energy Proposition 20: A proper motion from two nonzero segments Proposition 21: Translation energy Proposition 27: Rotation lines and their elementary properties Proposition 28: Horizontal lines of rotations Proposition 36: Affine transversals and the projective quadric Proposition 40: Circle reguli and both complete rulings Proposition 42: Line reguli and their horizontal ruling Theorem 1: The lattice upper bound and bipartite application Theorem 3: The bipartite lower bound and balanced specialization Theorem 4 (p. 3): the bipartite lower bound root mn for m at most the cube root of n distance_problems/sheffer_2014_distinct_distances_open_problems_current_bounds Problem 15 (p. 9): the asymptotic value of the bipartite distinct distances count D(m,n)

Graph