On bipartite distinct distances in the plane (Q2665979): Difference between revisions

Let \(D(n)\) denote the minimum number of distinct distances among \(n\) points in the plane, for all possible choices of the points. The distinct distances conjecture of \textit{P. Erdős} [Am. Math. Mon. 53, 248--250 (1946; Zbl 0060.34805)] asserts that \( D(n)= \Omega(n /\sqrt{\log n})\). He showed that an \(\sqrt{n}\times \sqrt{n}\) grid has only \(O(n /\sqrt{\log n})\) distinct distances. A recent celebrated paper of \textit{L. Guth} and \textit{N. H. Katz} [Ann. Math. (2) 181, No. 1, 155--190 (2015; Zbl 1310.52019)] essentially solved the distinct distances conjecture proving that \(D(n)= \Omega(n /{\log n})\). The paper under review studies the bipartite version of the distinct distances problem, which was first proposed by \textit{G. Elekes} [Combinatorica 15, No. 2, 167--174 (1995; Zbl 0827.52010)]: given \(m+n\) points in the plane, \(m\) of them red and \(n\) of them blue, what is \(D(m,n)\), the minimum number of distances between red and blue points, for all possible choices of the points? For \(2\leq m\leq n^{1/3}\), Elekes [loc. cit.] showed that \(D(m,n)=O(\sqrt{mn})\). The paper under review shows \(D(m,n)=\Omega(\sqrt{mn})\) for the same range, thus settling the distinct distances problem there. The proof adapts \textit{L. A. Székely}'s earlier technique for the distinct distances problem [Comb. Probab. Comput. 6, No. 3, 353--358 (1997; Zbl 0882.52007)]. For \(n^{1/3}\leq m \leq n\), the paper under review shows \(D(m,n)=\Omega(\sqrt{mn}/\log n )\) by modifying and extending the cited work of Guth and Katz.