Distinct distances for points lying on curves in ${\mathbb{R}}^d$ -- the bipartite case

Abstract

Let ${\gamma }_1,{\gamma }_2$ be a pair of constant-degree irreducible algebraic curves in ${\mathbb{R}}^d$. Assume that ${\gamma }_i$ is neither contained in a hyperplane nor in a quadric surface in ${\mathbb{R}}^d$, for each $i=1,2$. We show that for every pair of $n$-point sets $P_1\subset {\gamma }_1$ and $P_2\subset {\gamma }_2$, the number of distinct distances spanned by $P_1\times P_2$ is $\Omega (n^{3/2})$, with a constant of proportionality that depends on $\mathrm{deg}{\gamma }_1$, $\mathrm{deg}{\gamma }_2$, and $d$. This extends earlier results of Charalambides [Char], Pach and De Zeeuw [PdZ], and Raz [Ra] to the bipartite version. For the proof we use rigidity theory, and in particular the description of Bolker and Roth [BR80] for realizations in ${\mathbb{R}}^d$ of the complete bipartite graph $K_{m,n}$ that are not infinitesimally rigid.