Erdős #661 — bipartite distinct-distances o(n/√log n) question is OPEN ($50); the underlying two-set function D(m,n) is SOLVED up to a log factor (Elekes construction 1995/1999, matching lower bounds by Mathialagan 2019)

Statement

Erdős's own question (#661, erdosproblems.com, direct fetch 2026-07-02): 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 cross-distances $d(x_i,y_j)$ ($1\le i,j\le n$) is $$o\!\left(\frac{n}{\sqrt{\log n}}\right)?$$ (Also asked for points in $\mathbb{R}^3$.) This is the bipartite analogue of the ordinary Erdős distinct-distances problem Erdős #89 — distinct distances in the plane: instead of counting all $\binom{n}{2}$ pairwise distances within one $n$-point set, only the $n^2$ *cross*-distances between two labelled $n$-point sets are counted, and Erdős asks whether this relaxation lets you beat the single-set conjectured-optimal exponent.

The natural quantitative generalization that the literature actually attacks (Elekes 1995/1999; Mathialagan 2019): for $\mathcal P,\mathcal Q\subset\mathbb R^2$ with $|\mathcal P|=m\le|\mathcal Q|=n$, let $D(m,n)=\min |\{d(p,q):p\in\mathcal P,q\in\mathcal Q\}|$. Erdős's #661 is exactly the question of whether $D(n,n)=o(n/\sqrt{\log n})$ — i.e. whether the diagonal $m=n$ case can beat the grid-type upper bound that is conjectured (and, below the cube-root threshold, proven) to be optimal.

Facts

- Status per erdosproblems.com/661, verified by direct fetch 2026-07-02: OPEN, \$50 prize, "cannot be resolved with a finite computation." Sources listed on the page: [ErPa90], [Er92e], [Er97e], [Er97f]. - This is a genuinely open problem, not a solved one — flagging this explicitly since the natural reading of the slug's target ("bipartite distinct-distances variant, \$50 prize") could be mistaken for the *general* bipartite distinct-distances function $D(m,n)$, whose asymptotics (below) are essentially solved. Erdős's specific question is the sharper "can the symmetric $m=n$ upper bound be *beaten* (a little-o improvement)" question, which mirrors the still-open $\sqrt{\log n}$ gap in the parent problem Erdős #89 — distinct distances in the plane and is not resolved by the results below. - Sibling problem, same gap: Erdős #89 — distinct distances in the plane (the ordinary, non-bipartite distinct-distances problem, \$500 prize) asks the matching question for a single $n$-point set: is $D(n)=\Omega(n/\sqrt{\log n})$? Guth & Katz [GuKa15] nearly resolved it, proving $D(n)=\Omega(n/\log n)$ — off from the conjectured tight bound by exactly one factor of $\sqrt{\log n}$. The bipartite case #661 has the identical residual gap, for the identical reason (see Solution below): Mathialagan's extension of the Guth–Katz method gives $D(n,n)=\Omega(n/\log n)$ for the bipartite case too, leaving the same $\sqrt{\log n}$ unclosed. - The general two-parameter function $D(m,n)$ ($m\le n$) is essentially SOLVED, in two regimes: - Small-$m$ regime ($m\le n^{1/3}$): fully tight, $D(m,n)=\Theta(\sqrt{mn})$. Upper bound: Elekes's "circle grid" construction (G. Elekes, "Circle grids and bipartite graphs of distances," Combinatorica 15 (1995), 167–174) gives $D(m,n)=O(\sqrt{mn})$ by placing $\mathcal P$ on $m$ collinear points and $\mathcal Q$ at intersections of $m$ vertical lines with $\approx\sqrt{mn}$ concentric circles around each point of $\mathcal P$. Matching lower bound: Mathialagan (arXiv:1912.01883, "On Bipartite Distinct Distances in the Plane," submitted 4 Dec 2019) proved $D(m,n)=\Omega(\sqrt{mn})$ in this regime by adapting Székely's crossing-number argument — this closes the small-$m$ case completely, with no log loss at all. - Large-$m$ regime ($m\ge n^{1/3}$): tight up to a log factor. Upper bound: the same $O(n/\sqrt{\log n})$ integer-grid construction as the classical (non-bipartite) problem applies. Lower bound: Mathialagan proved $D(m,n)=\Omega(\sqrt{mn}/\log n)$ by extending the Guth–Katz polynomial-method / Elekes–Sharir analysis from the single-set to the two-set setting. At $m=n$ this specializes to $D(n,n)=\Omega(n/\log n)$ — the exact bipartite mirror of Guth–Katz's univariate result, and the reason #661's $\sqrt{\log n}$ gap is exactly as hard, and exactly as open, as Erdős #89 — distinct distances in the plane's. - A related, genuinely solved curiosity noted directly on the erdosproblems.com/661 page: in $\mathbb R^4$, Lenz observed that one can choose $x_1,\ldots,x_n,y_1,\ldots,y_n$ on two orthogonal circles such that $d(x_i,y_j)=1$ for every $i,j$ — i.e. the bipartite distance count can be trivially made $=1$ (not just small) once you go to 4 dimensions, because two circles in orthogonal 2-planes through a common center have all cross-distances equal by the Pythagorean theorem applied to the two radii. This is a fully elementary, completely solved fact — but it is a *degenerate* high-dimensional phenomenon that does not transfer back to $\mathbb R^2$ or $\mathbb R^3$ (both of which remain the genuinely open cases Erdős asked about). - Further open generalization noted on the page: if $F(2n)$ is the minimal number of bipartite cross-distances and $f(2n)$ is the minimal number of ordinary distinct distances among any $2n$ points in $\mathbb R^2$, is $F=o(f)$? — i.e. is the *relaxation* to bipartite-only distances provably easier in the strong little-o sense, for the optimal configuration of $2n$ points overall? This subsumes #661 and is likewise open. - Prior lower-bound work referenced by the "See also" chain: erdosproblems.com/89 cross-references #661 explicitly as the bipartite sibling, alongside Erdős #604 — pinned distinct-distances at a single point (pinned distances, strictly stronger single-set form, also open, \$500) and Erdős #1083 — distinct distances in R^d (d≥3) is OPEN; the solved d=2 case (#89, Guth–Katz) is the literal numerical input to every known partial bound, via Solymosi–Vu's dimension-reduction recursion (higher-dimensional generalization, open for all $d\ge3$).

Solution

What is actually proved (Mathialagan 2019), and the transferable technique — because this is the load-bearing "solved half" that any attack on #661 would need to either use directly or beat.

1. Split the problem by the ratio $m/n$ at the cube-root threshold $m=n^{1/3}$. This threshold is not arbitrary: it is exactly where Elekes's circle-grid upper-bound construction stops being the efficient one and the classical single-set integer-grid construction takes over as the better upper bound. Any lower-bound technique needs to match whichever construction is winning in a given regime, so the proof is naturally two separate arguments glued at this crossover.

2. Small-$m$ regime: adapt Székely's crossing-number method (the "cheap" incidence-geometry tool). Székely's 1997 crossing-number argument is the classical elementary route to incidence bounds: build an auxiliary graph (here, a bisector- or distance-indexed graph on the point sets), bound its number of edges via a distance-multiplicity argument, then invoke the crossing lemma (any graph drawn in the plane with $\ge4v$ edges has $\Omega(e^3/v^2)$ crossings) to force either few edges or a highly structured (hence countable) set of coincidences. Mathialagan reruns this argument in the two-set setting, and it turns out to be strong enough, in the regime where $m$ is small relative to $n$, to exactly match Elekes's construction — i.e. the crossing-number method alone (no polynomial method needed) already gives the *tight* answer $\Theta(\sqrt{mn})$ here. This is the key structural lesson: for the "easy" (unbalanced) regime, the older, more elementary crossing-number toolkit is already optimal — the heavy Guth-Katz machinery is not needed and would not improve the exponent.

3. Large-$m$ regime: extend the Guth–Katz polynomial method. For $m\ge n^{1/3}$ (including the fully symmetric $m=n$ case that Erdős's #661 is literally about), Mathialagan extends the Guth–Katz analysis of the classical problem Erdős #89 — distinct distances in the plane — the Elekes–Sharir reduction of planar distances to point-line incidences in $SE(2)$, followed by a polynomial-ham-sandwich cell decomposition and flecnode-polynomial/ruled-surface argument (see Polynomial method / slice rank (Croot-Lev-Pach, Ellenberg-Gijswijt) and Erdős #89 — distinct distances in the plane's Solution) — to the two-set setting, obtaining $D(m,n)=\Omega(\sqrt{mn}/\log n)$. This is the transferable move for open problems downstream of #661: the Guth–Katz polynomial method is not intrinsically tied to the single-set problem — it survives being generalized to an *asymmetric*, two-point-set incidence count, with the same $\log$-factor loss (not more) as the cost of the generalization. Any future attempt to close the $\sqrt{\log n}$ gap in Erdős #89 — distinct distances in the plane should be expected to transfer to #661 essentially for free by the same extension route, and conversely a bipartite-specific idea for closing #661's gap would be a natural thing to try porting back to Erdős #89 — distinct distances in the plane.

4. Why the residual gap (and hence #661 itself) survives untouched by this work. Both regimes' lower bounds match their respective upper-bound constructions up to constants in the small-$m$ case, but the large-$m$/diagonal case is only matched up to a $\log n$ factor — exactly mirroring the un-closed gap in Guth–Katz for the univariate problem. Mathialagan's contribution completely resolves the *shape* of $D(m,n)$ across the whole $(m,n)$ range (which regime dominates, and the polynomial exponent in each), but it makes zero progress on the specific finer question #661 asks: whether the log-factor itself can be beaten (a genuine $o(\cdot)$, not just a constant-factor, improvement). That finer question requires a fundamentally sharper incidence bound than anything the polynomial method has produced since 2015, in either the single-set or bipartite setting.

Bottom line for downstream use: the reusable export here is "Székely crossing-number method for the unbalanced/small-parameter regime, Guth–Katz polynomial method for the balanced/diagonal regime, glued at the natural threshold where the two competing constructions cross over" — a two-technique-by-regime template for asymmetric incidence problems. It fully pins down $D(m,n)$'s growth rate everywhere except the single $\log n$ factor at the diagonal, which is precisely Erdős's #661 and remains open for the same structural reason Erdős #89 — distinct distances in the plane itself remains open.

Related

- Erdős #89 — distinct distances in the plane — the ordinary (non-bipartite) distinct-distances problem, \$500 prize, open; Guth–Katz's $\Omega(n/\log n)$ bound is the direct technical ancestor of Mathialagan's large-$m$ bipartite bound, and shares the identical unclosed $\sqrt{\log n}$ gap that #661 asks about in the bipartite setting. - Erdős #604 — pinned distinct-distances at a single point — pinned distinct distances (single point sees $\gg n/\sqrt{\log n}$ distances), strictly stronger single-set form, \$500, open; the polynomial method has *not* been successfully transferred here either (stuck at the older Katz–Tardos $n^{0.8641}$ bound) — a useful contrast to #661, where the transfer to the bipartite setting *did* succeed (Mathialagan), just not far enough to close the log gap. - Erdős #1083 — distinct distances in R^d (d≥3) is OPEN; the solved d=2 case (#89, Guth–Katz) is the literal numerical input to every known partial bound, via Solymosi–Vu's dimension-reduction recursion — higher-dimensional generalization of the classical distinct-distances problem, open for all $d\ge3$; #661 itself is also explicitly asked for $\mathbb R^3$ on erdosproblems.com, unresolved. - Polynomial method / slice rank (Croot-Lev-Pach, Ellenberg-Gijswijt) — Guth–Katz's cell-decomposition technique (polynomial ham-sandwich + flecnode polynomial/ruled surfaces), the machinery Mathialagan extends to the bipartite large-$m$ regime; documented in full via Erdős #89 — distinct distances in the plane. - concept/crossing-number-method — Székely's classical crossing-lemma-based incidence technique, which Mathialagan shows is already *tight* (no further improvement possible or needed) for the small-$m$ bipartite regime $m\le n^{1/3}$; the "cheap tool wins in the unbalanced regime" lesson transferable to other asymmetric incidence problems. - Elekes–Sharir(–Guth–Katz) reduction: distinct distances → point-line incidences in SE(2) — the reduction of planar distance-counting to point-line incidences in $SE(2)$; the shared setup underlying both the univariate Guth–Katz proof and Mathialagan's bipartite extension.