Wiki
Wiki

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

Updated


Statement. Write D(m,n)D(m,n) for the least number of distinct distances ∣p−q∣|p-q|, p∈Pp\in\mathcal P, q∈Qq\in\mathcal Q, over planar sets P,Q\mathcal P,\mathcal Q of sizes mm and nn, where m≤nm\leq n (p. 3). The printed theorem reads: "For 2⩽m⩽n1/32 \leqslant m \leqslant n^{1/3}, we have that D(m,n)=Ω(mn)D(m, n) = \Omega(\sqrt{mn})." (p. 3).

So there is an absolute constant c>0c>0 such that any two planar sets of mm and nn points with 2≤m≤n1/32\leq m\leq n^{1/3} determine at least cmnc\sqrt{mn} distinct distances between them. With Proposition 6 it gives D(m,n)=Θ(mn)D(m,n)=\Theta(\sqrt{mn}) in this range, the paper's Table 1 (p. 4).

Source. Surya Mathialagan, On Bipartite Distinct Distances in the Plane, Electronic Journal of Combinatorics 28(4) (2021), P4.33, DOI 10.37236/9687: Theorem 4 on p. 3, proved in Section 3, pp. 6--9. The copy read is identified on the source card.

Proof pointer. The paper derives Theorem 4 from the stronger Theorem 14 (p. 7): some single point of P\mathcal P already determines Ω(mn)\Omega(\sqrt{mn}) distances to Q\mathcal Q, and D(P,Q)D(\mathcal P,\mathcal Q) is at least the number of distances from any one point of P\mathcal P. The deduction is stated on p. 9.

Read depth. Claims checked: the statement, its range and the deduction from Theorem 14 were read on the published PDF. The proof of Theorem 14 is recorded at the depth stated on its page. This page is outside the independently reviewed Theorem 3 record on this card.

Bears on. Problem 661: the problem page records this theorem beside Theorem 3. Its range 2≤m≤n1/32\leq m\leq n^{1/3} excludes the question's balanced case m=nm=n, so it gives no bound there.