# Distinct distances on non-ruled surfaces and between circles††thanks: This
research project was done as part of the 2019 CUNY Combinatorics REU,
supported by NSF awards DMS-1802059 and DMS-1851420.

Surya Mathialagan Department of Electrical Engineering and Computer Science,
MIT, MA, USA<EMAIL_ADDRESS>This research was completed while the author was
at Caltech. Supported by Caltech’s Summer Undergraduate Research Fellowships
(SURF) Program and the Olga Taussky-Todd Award. Adam Sheffer Department of
Mathematics, Baruch College, City University of New York, NY, USA.
<EMAIL_ADDRESS>Supported by NSF award DMS-1802059.

###### Abstract

We improve the current best bound for distinct distances on non-ruled
algebraic surfaces in $\mathbb{R}^{3}$. In particular, we show that $n$ points
on such a surface span $\Omega\left(n^{32/39-{\varepsilon}}\right)$ distinct
distances, for any ${\varepsilon}>0$. Our proof adapts the proof of Székely
for the planar case, which is based on the crossing lemma.

As part of our proof for distinct distances on surfaces, we also obtain new
results for distinct distances between circles in $\mathbb{R}^{3}$. Consider
two point sets of respective sizes $m$ and $n$, such that each set lies on a
distinct circle in $\mathbb{R}^{3}$. We characterize the cases when the number
of distinct distances between the two sets can be $O(m+n)$. This includes a
new configuration with a small number of distances. In any other case, we
prove that the number of distinct distances is
$\Omega\left(\min\left\\{m^{2/3}n^{2/3},m^{2},n^{2}\right\\}\right)$.

##  1 Introduction

Erdős introduced the family of _distinct distances problems_ in 1946 and
considered it to be his “most striking contribution to geometry” [8]. For over
50 years, he regularly added more conjectures and problems to this family. For
a finite point set $\mathcal{P}\subset\mathbb{R}^{d}$, let
$\Delta(\mathcal{P})$ be the set of distances spanned by pairs of points from
$\mathcal{P}$. In his first seminal paper on the subject, Erdős [9] asked for
the asymptotic value of
$D(\mathcal{P})=\min_{|\mathcal{P}|=n}|\Delta(\mathcal{P})|$. In other words,
the problem asks for the minimum number of distances that could be spanned by
$n$ points in $\mathbb{R}^{d}$.

The answer to the above problem depends on $d$. In $\mathbb{R}^{2}$, Erdős
presented a set of $n$ points that spans $\Theta(n/\sqrt{\log n})$ distinct
distances and conjectured that this was asymptotically optimal. Over the
decades, a large number of works have been dedicated to this problem (such as
[6, 25, 26, 28]). Recently, Guth and Katz [10] almost completely settled
Erdős’s conjecture, proving that $D(\mathcal{P})=\Omega(n/\log n)$ for any set
$\mathcal{P}\subset\mathbb{R}^{2}$ of $n$ points.

Distinct distances on non-ruled surfaces. When the breakthrough of Guth and
Katz first appeared in 2010, the community was optimistic about using a
similar technique to solve the distinct distances problem in every dimension.
This turned out to be more difficult than expected, and so far no progress has
been made even in $\mathbb{R}^{3}$. One step towards solving the problem in
$\mathbb{R}^{3}$ may be to consider the problem on an algebraic surface. That
is, we consider the number of distinct distances spanned by $n$ points on a
specific surface in $\mathbb{R}^{3}$.

The case of $n$ points on a plane in $\mathbb{R}^{3}$ is equivalent to the
distinct distances problem in $\mathbb{R}^{2}$. Tao [27] showed that the Guth-
Katz result can be extended in the following way.

######  Theorem 1.1.

Let $U\subset\mathbb{R}^{3}$ be a sphere or a hyperboloid of two sheets. Then
any set $\mathcal{P}$ of $n$ points on $U$ satisfies

$D(\mathcal{P})=\Omega\left(n/\log n\right).$

No known constructions of $n$ points on an algebraic surface in
$\mathbb{R}^{3}$ span a sublinear number of distinct distances (with the
obvious exception of points on a plane). On the other hand, there are
unrestricted point sets $\mathcal{P}\subset\mathbb{R}^{3}$ that satisfy
$D(\mathcal{P})=\Theta(n^{2/3})$. (It is conjectured that no set in
$\mathbb{R}^{3}$ spans an asymptotically smaller number of distinct
distances.)

Sharir and Solomon [21] proved the following distinct distances result on
surfaces in $\mathbb{R}^{3}$. (The definition of an irreducible two-
dimensional variety of degree $k$ can be found in Section 2.)

######  Theorem 1.2.

Let $U\subset\mathbb{R}^{3}$ be an irreducible two-dimensional variety of
degree $k$. Let $\mathcal{P}$ be a set of $n$ points on $U$. Then for any
${\varepsilon}>0$, we have

$D(\mathcal{P})=\Omega_{k}\left(n^{7/9-{\varepsilon}}\right).$

In another work, Sharir and Solomon [22] replace the extra ${\varepsilon}$ in
the exponent with a polylogarithmic factor. These bounds can be thought of as
adaptations of Chung’s bound for distinct distances in the plane [6]. These
results reveal that the three-dimensional distinct distances problem behaves
differently when restricting the point set to a surface.

We improve Theorem 1.2 for non-ruled surfaces. A surface
$U\subset\mathbb{R}^{3}$ is _ruled_ if for every point $p\in U$ there exists a
line that is contained in $U$ and incident to $p$. For example, cylindrical
and conical surfaces are ruled.

######  Theorem 1.3.

Let $U\subset\mathbb{R}^{3}$ be an irreducible non-ruled two-dimensional
variety of degree $k$. Let $\mathcal{P}$ be a set of $n$ points on $U$. Then
for any ${\varepsilon}>0$, we have

$D(\mathcal{P})=\Omega_{k}\left(n^{32/39-{\varepsilon}}\right).$

The first step of our proof extends Székely’s technique for distinct distances
in the plane [26]. By combining this technique with incidence bounds for
curves, we obtain the bound $\Omega(n^{4/5-{\varepsilon}})$. We further
improve this bound by studying perpendicular bisectors of points on surfaces
in $\mathbb{R}^{3}$. We prove Theorem 1.3 in Section 3.

While Sharir and Solomon do not state this, their proof of Theorem 1.2 also
implies that there exists a point $p\in\mathcal{P}$ that spans
$\Omega_{k}(n^{7/9-\epsilon})$ distances with $\mathcal{P}\setminus\\{p\\}$.
While this is also the case for Székely’s proof in $\mathbb{R}^{2}$, our proof
of Theorem 1.3 does not immediately show the existence of such a point. Some
of the new components that extend Székely’s proof to $\mathbb{R}^{3}$ do not
easily extend in this direction.

Distinct distances between two circles in $\mathbb{R}^{3}$. As part of the
proof of Theorem 1.3, we derive a bound on the number of distinct distances
between points on two circles in $\mathbb{R}^{3}$. We believe that this result
is also intrinsically interesting, and not just with respect to Theorem 1.3.

Consider two finite sets
$\mathcal{P}_{1},\mathcal{P}_{2}\subset\mathbb{R}^{d}$. We denote by
$D(\mathcal{P}_{1},\mathcal{P}_{2})$ the number of distinct distances spanned
by pairs in $\mathcal{P}_{1}\times\mathcal{P}_{2}$. In other words, we ignore
distances between pairs of points from the same set. Many such bipartite
distinct distances problems have been studied (for example, see [7, 16, 19]).
We are interested in the case where there exist circles $C_{1}$ and $C_{2}$
such that $\mathcal{P}_{1}\subset C_{1}$ and $\mathcal{P}_{2}\subset C_{2}$.

Figure 1: The case of two concentric circles.

We begin with the case where $C_{1}$ and $C_{2}$ are concentric circles in
$\mathbb{R}^{2}$. Let $\mathcal{P}_{1}$ be the set of vertices of a regular
$n$-gon lying on $C_{1}$. Let $\mathcal{P}_{2}$ be a uniform scaling of
$\mathcal{P}_{1}$ around the center of the circles, such that
$\mathcal{P}_{2}\subset C_{2}$. The case of $n=8$ is depicted in Figure 1.
Arbitrarily fix a point $p\in\mathcal{P}_{1}$. By symmetry, we have that

$D(\mathcal{P}_{1},\mathcal{P}_{2})=D(\\{p\\},\mathcal{P}_{2})=\Theta(n).$

It is not difficult to generalize the above construction to the case where
$\mathcal{P}_{1}$ and $\mathcal{P}_{2}$ are not necessarily of the same size.
When $|\mathcal{P}_{1}|=m$ and $|\mathcal{P}_{2}|=n$, we obtain
$D(\mathcal{P}_{1},\mathcal{P}_{2})=\Theta(m+n)$. On the other hand, Pach and
de Zeeuw [16] proved that when $C_{1}$ and $C_{2}$ are not concentric, we have

$D(\mathcal{P}_{1},\mathcal{P}_{2})=\Omega\left(\min\left\\{m^{2/3}n^{2/3},m^{2},n^{2}\right\\}\right).$

In the current work, we consider the case where $C_{1}$ and $C_{2}$ are in
$\mathbb{R}^{3}$. We define the _axis_ of a circle $C$ in $\mathbb{R}^{3}$ to
be the line incident to the center of $C$ and orthogonal to the plane
containing $C$. Note that every point on the axis of $C$ is equidistant from
all the points of $C$. On the other hand, a point not on the axis of $C$
cannot be equidistant from three points of $C$ (every sphere centered at this
point intersects $C$ in at most two points). We say that two circles $C_{1}$
and $C_{2}$ in $\mathbb{R}^{3}$ are _aligned_ if they have the same line as
their axis. An example is depicted in Figure 2(a). Note that the planes that
contain aligned circles are parallel.

The above example of concentric circles in $\mathbb{R}^{2}$ can be easily
extended to the case of aligned circles in $\mathbb{R}^{3}$. Thus, when
$C_{1}$ and $C_{2}$ are aligned, one can find $\mathcal{P}_{1}$ and
$\mathcal{P}_{2}$ such that $D(\mathcal{P}_{1},\mathcal{P}_{2})=\Theta(m+n)$.
Surprisingly, we also discovered a less intuitive family of constructions with
a linear number of distances between two circles. Let $H_{1}$ be the plane
containing $C_{1}$ and let $H_{2}$ be the plane containing $C_{2}$. We say
that $C_{1}$ and $C_{2}$ are _perpendicular_ if all the following hold:

  1. (1)

The planes $H_{1}$ and $H_{2}$ are perpendicular (that is, the angle between
the two planes is $\pi/2$).

  2. (2)

The center of $C_{1}$ lies on $H_{2}$.

  3. (3)

The center of $C_{2}$ lies on $H_{1}$.

An example is depicted in Figure 2(b).

(a) Aligned circles.

(b) Perpendicular circles.

Figure 2: Pairs of circles that may lead to a small number of distinct
distances.

The following is our main contribution to distinct distances between two
circles.

######  Theorem 1.4.

Let $C_{1}$ and $C_{2}$ be two circles in $\mathbb{R}^{3}$.
(a) Assume that $C_{1}$ and $C_{2}$ are aligned or perpendicular. Then there
exist a set $\mathcal{P}_{1}\subset C_{1}$ of $m$ points and a set
$\mathcal{P}_{2}\subset C_{2}$ of $n$ points, such that

$D(\mathcal{P}_{1},\mathcal{P}_{2})=\Theta(m+n).$

(b) Assume that $C_{1}$ and $C_{2}$ are neither aligned nor perpendicular. Let
$\mathcal{P}_{1}\subset C_{1}$ be a set of $m$ points and let
$\mathcal{P}_{2}\subset C_{2}$ be a set of $n$ points. Then

$D(\mathcal{P}_{1},\mathcal{P}_{2})=\Omega\left(\min\left\\{m^{2/3}n^{2/3},m^{2},n^{2}\right\\}\right).$

The proof of Theorem 1.4(b) relies on Elekes-Szabó type expanding polynomials,
similar to an argument of Raz [17]. This argument is combined with a new layer
of computer calculations. Part (a) of Theorem 1.4 is proved in Section 4. Part
(b) is proved in Section 5.

Future directions. The main issue of Theorem 1.3 is that it does not hold for
ruled surfaces. It seems plausible that our proof could be extended to also
hold for ruled surfaces. This could be an interesting direction for future
work.

Another direction to explore is distinct distances between two circles in
$\mathbb{R}^{4}$. In this case, there exists a simple construction with only
one distance between two circles (see [14]). We wonder what other surprises
might exist in $\mathbb{R}^{4}$.

Acknowledgements. We are grateful to Frank de Zeeuw for many useful
discussions, including help with Theorem 5.2 and with the circle
constructions. We thank Toby Aldape, Jingyi (Rose) Liu, Minh-Quan Vo, and the
anonymous referees for helping to improve this paper. We also thank Sara Fish
for inspirational support. The first author would like to thank everyone
involved in the 2019 CUNY REU for motivating her with their passion and
engaging with her in many helpful discussions.

##  2 Preliminaries

We now introduce various definitions and tools that are used in the proofs in
the following sections.

We briefly survey notation and results from real algebraic geometry. For
references and more information, see for example [4, 11].

For polynomials $f_{1},\ldots,f_{k}\in\mathbb{R}[x_{1},\ldots,x_{d}]$, the
_variety_ defined by $f_{1},\ldots,f_{k}$ is

${\bf V}(f_{1},\ldots,f_{k})=\left\\{p\in\mathbb{R}^{d}\ :\
f_{1}(p)=f_{2}(p)=\cdots=f_{k}(p)=0\right\\}.$

We say that a set $U\subset\mathbb{R}^{d}$ is a variety if there exist
$f_{1},\ldots,f_{k}\in\mathbb{R}[x_{1},\ldots,x_{d}]$ such that $U={\bf
V}(f_{1},\ldots,f_{k})$. While not true over some other fields, in
$\mathbb{R}^{d}$ every variety can be defined using a single polynomial.

A variety $U$ is _irreducible_ if there do not exist two nonempty varieties
$U_{1},U_{2}\subset U$ such that $U=U_{1}\cup U_{2}$, $U_{1}\neq U$, and
$U_{2}\neq U$. The _dimension_ of an irreducible variety $U$ is the largest
integer $d_{U}$ for which there exist non-empty irreducible varieties
$U_{0},U_{1},\ldots,U_{d_{U}-1}$ such that

$U_{0}\subsetneq U_{1}\subsetneq\ldots\subsetneq U_{d_{U}-1}\subsetneq U.$

The dimension of a reducible variety $W$ is the maximum dimension of an
irreducible component of $W$. We define a _curve_ to be an irreducible variety
of dimension one. A _surface_ is an irreducible variety of dimension two.

The _ideal_ of a variety $U\subseteq\mathbb{R}^{d}$, denoted ${\bf I}(U)$, is
the set of polynomials in $\mathbb{R}[x_{1},\ldots,x_{d}]$ that vanish on
every point of $U$. We say that a set of polynomials
$f_{1},\ldots,f_{\ell}\in\mathbb{R}[x_{1},\ldots,x_{d}]$ _generate_ ${\bf
I}(U)$ if every element of ${\bf I}(U)$ can be written as
$\sum_{j=1}^{\ell}f_{j}g_{j}$ for some
$g_{1},\ldots,g_{\ell}\in\mathbb{R}[x_{1},\ldots,x_{d}]$. The _Jacobian
matrix_ of the polynomials
$f_{1},\ldots,f_{k}\in\mathbb{R}[x_{1},\ldots,x_{d}]$ is

${\bf J}_{f_{1},\ldots,f_{k}}=\left(\begin{array}[]{cccc}\frac{\partial
f_{1}}{\partial x_{1}}&\frac{\partial f_{1}}{\partial
x_{2}}&\cdots&\frac{\partial f_{1}}{\partial x_{d}}\\\\[5.69054pt]
\frac{\partial f_{2}}{\partial x_{1}}&\frac{\partial f_{2}}{\partial
x_{2}}&\cdots&\frac{\partial f_{2}}{\partial x_{d}}\\\\[5.69054pt]
\cdots&\cdots&\cdots&\cdots\\\\[5.69054pt] \frac{\partial f_{k}}{\partial
x_{1}}&\frac{\partial f_{k}}{\partial x_{2}}&\cdots&\frac{\partial
f_{k}}{\partial x_{d}}\end{array}\right)$

Consider a variety $U\subset\mathbb{R}^{d}$ of dimension $k$, and polynomials
$f_{1},\ldots,f_{\ell}\in\mathbb{R}[x_{1},\ldots,x_{d}]$ that generate ${\bf
I}(U)$. We say that $p\in U$ is a _singular_ point of $U$ if
$\mathrm{rank\,}{\bf J}_{f_{1},\ldots,f_{k}}(p)<d-k$. A point of $U$ that is
not singular is said to be a _regular_ point of $U$. We denote the set of
regular points of a variety $U\subset\mathbb{R}^{d}$ as $U_{\text{reg}}$.

We define the _degree_ of a surface $U\subset\mathbb{R}^{3}$ as the minimum
degree of a polynomial $f\in\mathbb{R}[x,y,z]$ that satisfies ${\bf V}(f)=U$.
There are several non-equivalent definitions for the degree of a variety in
$\mathbb{R}^{3}$ that is not a surface. To avoid this issue, we say that the
_complexity_ of a variety $U$ is the minimum integer $D$ that satisfies the
following. There exist $k\leq D$ polynomials
$f_{1},\ldots,f_{k}\in\mathbb{R}[x_{1},\ldots,x_{d}]$, each of degree at most
$D$, such that $U={\bf V}(f_{1},\ldots,f_{k})$. In the past decade, the use of
complexity is becoming more common. For example, see [5, 24].

######  Theorem 2.1.

Let $U\subset\mathbb{R}^{d}$ be a variety of complexity $D$.
(a) The number of irreducible components of $U$ is $O_{d,D}(1)$.
(b) The number of connected components of $U$ is $O_{d,D}(1)$.

For the following quantitative variant of Theorem 2.1(b), see Solymosi and Tao
[24] (see also Barone and Basu [2]).

######  Theorem 2.2.

Let $U\subset\mathbb{R}^{d}$ be a variety of dimension $k$ and complexity $C$.
Let $f\in\mathbb{R}[x_{1},\ldots,x_{d}]$ be a polynomial of degree $D$. Then
the number of connected components of $U\setminus{\bf V}(f)$ is
$O_{C,D,d,k}(D^{k})$.

For more information about the following lemma, see for example [4, Section
3.3].

######  Lemma 2.3.

Let $U\subset\mathbb{R}^{3}$ be a variety of complexity $D$ and dimension
$d>0$. Then the set of singular points of $U$ is a variety of dimension at
most $d-1$ and complexity $O_{D}(1)$.

Let $S\subset\mathbb{R}^{d}$. The _Zariski closure_ of $S$, denoted
$\overline{S}$, is the smallest variety that contains $S$. Specifically, every
variety that contains $S$ also contains $\overline{S}$. A set
$S\subset\mathbb{R}^{d}$ is _semi-algebraic_ if there exists a boolean
function $\Phi(y_{1},\ldots,y_{t})$ and polynomials
$f_{1},\ldots,f_{t}\in\mathbb{R}[x_{1},\ldots,x_{d}]$ such that

$p\in S\qquad\text{if and only if }\qquad\Phi(f_{1}(p)\geq
0,\ldots,f_{t}(p)\geq 0)=1.$

The dimension of $S$ is $\dim\overline{S}$. The _complexity_ of $S$ is the
minimum $t$ such that $S$ can be described with at most $t$ polynomials of
degree at most $t$. The projection of a real variety may not be a variety.
However, it must be semi-algebraic.

######  Lemma 2.4.

Let $U\subset\mathbb{R}^{d}$ be a variety of complexity $k$ and of dimension
$d^{\prime}$. Let $\pi:\mathbb{R}^{d}\to\mathbb{R}^{e}$ be a standard
projection: a linear map that keeps $e$ out of the $d$ coordinates of a point
in $\mathbb{R}^{d}$. Then $\pi(U)$ is a semi-algebraic set of dimension at
most $d^{\prime}$ and of complexity $O_{k,d}(1)$.

For more details about Lemma 2.4, see for example [3, Section 14.2]. A
projection is equivalent to adding an existential quantifier to some of the
variables. The above reference discusses how to then eliminate such
quantifiers.

For more information about the following lemma, see for example [3, Section
16.4].

######  Lemma 2.5.

Let $S\subset\mathbb{R}^{d}$ be a semi-algebraic set of complexity $t$. Then
the number of connected components of $S$ is $O_{d,t}(1)$.

Distinct distances: first bounds. We state a couple of simple observations
involving distinct distances in $\mathbb{R}^{3}$. For a point
$p\in\mathbb{R}^{3}$ and $r>0$, we denote by $S(p,r)$ the sphere of radius $r$
centered at $p$.

######  Lemma 2.6.

Let $\gamma$ be a one-dimensional variety of complexity $O(1)$ in
$\mathbb{R}^{3}$. Let $\mathcal{P}$ be a set of $n$ points on $\gamma$. Then
$D(\mathcal{P})=\Omega(n)$.

###### Proof.

By Theorem 2.1, $\gamma$ can be partitioned to $O(1)$ irreducible components.
By the pigeonhole principle, there exists an irreducible one-dimensional
component $\gamma^{\prime}$ of $\gamma$ that contains $\Theta(n)$ points of
$\mathcal{P}$. Set $\mathcal{P}^{\prime}=\mathcal{P}\cap\gamma^{\prime}$.

Let $p$ be an arbitrary point of $\mathcal{P}^{\prime}$. Fix $r>0$, and note
that the sphere $S(p,r)$ cannot contain $\gamma^{\prime}$. Since
$\gamma^{\prime}$ is irreducible, the intersection $S(p,r)\cap\gamma^{\prime}$
is of dimension zero (or empty). By Theorem 2.1, this intersection consists of
$O(1)$ points. That is, the number of points of $\mathcal{P}^{\prime}$ at
distance $r$ from $p$ is $O(1)$. This implies that

$D(\mathcal{P})\geq D(\mathcal{P}^{\prime})\geq
D(\\{p\\},\mathcal{P}^{\prime}\setminus\\{p\\})=\Omega(n).$

∎

Given two points $a,b\in\mathbb{R}^{d}$, we denote the distance between $a$
and $b$ as $|ab|$.

######  Lemma 2.7.

Let $H_{1}$ be the $xy$-plane in $\mathbb{R}^{3}$ and let $H_{2}$ be a plane
parallel to $H_{1}$ (possibly $H_{1}=H_{2}$). Let $\mathcal{P}_{1}\subset
H_{1}$ and $\mathcal{P}_{2}\subset H_{2}$ be finite point sets. Let
$\pi:\mathbb{R}^{3}\to H_{1}$ be the projection obtained by setting the
$z$-coordinate to zero. Then

$D(\mathcal{P}_{1},\mathcal{P}_{2})=D(\mathcal{P}_{1},\pi(\mathcal{P}_{2})).$

###### Proof.

The plane $H_{2}$ is defined by an equation of the form $z=c$. The distance
between points $(a_{x},a_{y},0)\in H_{1}$ and $(b_{x},b_{y},c)\in H_{2}$ is

$\sqrt{(a_{x}-b_{x})^{2}+(a_{y}-b_{y})^{2}+c^{2}}.$

The distance between $(a_{x},a_{y},0)\in H_{1}$ and
$\pi(b_{x},b_{y},c)=(b_{x},b_{y},0)$ is

$\sqrt{(a_{x}-b_{x})^{2}+(a_{y}-b_{y})^{2}}.$

Let $a,a^{\prime}\in\mathcal{P}_{1}$ and $b,b^{\prime}\in\mathcal{P}_{2}$. By
the above, we note that $|ab|=|a^{\prime}b^{\prime}|$ if and only if
$|a\pi(b)|=|a\pi(b^{\prime})|$. Indeed, the square of both distances changes
by $c^{2}$. We conclude that
$D(\mathcal{P}_{1},\mathcal{P}_{2})=D(\mathcal{P}_{1},\pi(\mathcal{P}_{2}))$.
∎

##  3 Distinct distances on non-ruled surfaces

In this section we prove Theorem 1.3. We first present some additional
preliminaries in Section 3.1. In Section 3.2, we study some properties of
surfaces in $\mathbb{R}^{3}$. Finally, we prove Theorem 1.3 in Sections 3.3
and 3.4.

###  3.1 Additional preliminaries

Incidences. Let $\mathcal{P}$ be a set of points and let $\mathcal{V}$ be a
set of varieties, both in $\mathbb{R}^{d}$. An incidence is a pair
$(p,U)\in\mathcal{P}\times\mathcal{V}$ such that the point $p$ lies on the
variety $U$. We denote the number of incidences in
$\mathcal{P}\times\mathcal{V}$ as $I(\mathcal{P},\mathcal{V})$.

A polynomial in $\mathbb{R}[x,y]$ of degree at most $k$ has at most
$\binom{k+2}{2}$ monomials. We can thus define every such polynomial by a set
of $\binom{k+2}{2}$ real coefficients. This leads to a bijection between the
set of such polynomials and $\mathbb{R}^{\binom{k+2}{2}}$. Since we are only
interested in the zero sets of the polynomials, we think of two polynomials
that differ by a constant factor as identical. Therefore, we can think of the
space of polynomials as the projective space
$\mathbb{P}\mathbb{R}^{\binom{k+2}{2}}$.

A family of curves in $\mathbb{R}^{2}$ is $s$_-dimensional_ if it corresponds
to a variety $\mathcal{F}\subseteq\mathbb{P}\mathbb{R}^{\binom{D+2}{2}}$ of a
constant complexity and dimension $s$. For example, the set of circles in
$\mathbb{R}^{2}$ is a 3-dimensional family and the set of circles of radius 1
is a 2-dimensional family. The following is a result of Sharir and Zahl [23].

######  Theorem 3.1.

Let $\mathcal{P}$ be a set of $m$ points and let $\mathcal{C}$ be a set of $n$
algebraic curves from an $s$-dimensional family, each of degree at most $k$.
Assume that no two curves of $\mathcal{C}$ share a common one-dimensional
component. Then for every ${\varepsilon}>0$ we have

$I(\mathcal{P},\mathcal{C})=O_{k,s,{\varepsilon}}\left(m^{\frac{2s}{5s-4}+{\varepsilon}}n^{\frac{5s-6}{5s-4}}+m^{2/3}n^{2/3}+m+n\right).$

Let $\mathcal{P}$ be a set of points in $\mathbb{R}^{2}$ and let $r\geq 2$ be
an integer. We say that a variety $\gamma\subset\mathbb{R}^{2}$ is $r$-_rich_
if it contains at least $r$ points of $\mathcal{P}$. The following can be
easily obtained from Theorem 3.1 using a standard incidence argument.

######  Corollary 3.2.

Let $\mathcal{P}$ be a set of $m$ points and let $r$ be larger than some
sufficiently large constant. Consider an $s$-dimensional family $\mathcal{F}$
of algebraic curves of degree at most $k$ in $\mathbb{R}^{2}$. For every
${\varepsilon}>0$, the maximum number of $r$-rich curves in the family with no
two sharing a one-dimensional component is

$O_{k,s,{\varepsilon}}\left(\frac{m^{s+{\varepsilon}}}{r^{(5s-4)/2}}+\frac{m^{2}}{r^{3}}+\frac{m}{r}\right).$

Monotone patches. Let $U\subset\mathbb{R}^{3}$ be a surface of degree $D$. We
define a _monotone patch_ of $U$ to be a connected two-dimensional
open222Whenever we refer to open sets, we mean open according to the Euclidean
topology (rather than the Zariski toplogy). semi-algebraic subset of
$U_{\text{reg}}$ whose projection on the $xy$-plane is injective. In other
words, every line parallel to the $z$-axis intersects the patch at most once.

######  Theorem 3.3.

Let $U\subset\mathbb{R}^{3}$ be a surface of degree $D$ that does not contain
lines parallel to the $z$-axis. Then $U$ can be partitioned into a variety
$U_{0}$ of dimension at most one and a set of monotone patches
$U_{1},\ldots,U_{M}$, with the following properties. The sets
$U_{0},U_{1},\ldots,U_{M}$ are pairwise disjoint and their union is $U$. The
complexity of $U_{0}$ is $O_{D}(1)$ and the number of patches is $M=O_{D}(1)$.

Theorem 3.3 is a special case of _cylindrical decomposition_. Thus, the proof
follows from the proof of the cylindrical decomposition theorem For example,
see [3, Section 5.1].

Crossing numbers. The _crossing number_ of a graph $G=(V,E)$, denoted
$\mathrm{cr}(G)$, is the smallest integer $k$ such that we can draw $G$ in the
plane with $k$ edge crossings. The well-known crossing lemma [1, 13] provides
a lower bound for the crossing number of graphs with many edges.

######  Lemma 3.4 (The crossing lemma).

Let $G=(V,E)$ be a graph with $|E|\geq 4|V|$. Then
$\mathrm{cr}(G)=\Omega\left(|E|^{3}/|V|^{2}\right)$.

Lemma 3.4 assumes no parallel edges. The following is a crossing lemma for
graphs with parallel edges (for example, see [26]). The _multiplicity_ of an
edge $e$ is the number of edges that have the same endpoints as $e$ (including
$e$ itself).

######  Lemma 3.5.

Let $G=(V,E)$ be a multigraph with $|E|\geq 5\mu|V|$. Assume that every edge
has multiplicity at most $\mu$. Then

$\mathrm{cr}(G)=\Omega\left(\frac{|E|^{3}}{\mu|V|^{2}}\right).$

Let $G$ be a graph and let $U$ be a monotone patch of a surface in
$\mathbb{R}^{3}$. Since $U$ is homeomorphic to any connected open subset of
the plane, the crossing number of $G$ does not change when considering
drawings of $G$ on $U$. That is, $G$ can be drawn on $U$ with $\mathrm{cr}(G)$
crossings, but not with a smaller number of crossings.

###  3.2 Properties of surfaces in $\mathbb{R}^{3}$

We now derive several lemmas that are used in the proof of Theorem 1.3. These
lemmas study properties of surfaces in $\mathbb{R}^{3}$. The reader may safely
skip these lemmas, returning to them as required when going over the proof of
Theorem 1.3. Recall that we define a surface as an irreducible variety of
dimension two.

Surfaces of revolution. A surface $U\subset\mathbb{R}^{3}$ is a _surface of
revolution_ if there exists a line $\ell$ such that every rotation around
$\ell$ is a symmetry of $U$. We refer to $\ell$ as the _axis_ of $U$. Note
that $U$ is a union of disjoint circles with axis $\ell$. Planes and spheres
are surfaces of revolution with infinitely many axes.

######  Lemma 3.6.

Excluding planes and sphere, every surface of revolution has exactly one axis.

###### Proof sketch..

Assume that $U$ is a surface of revolution that has distinct axes $\ell$ and
$\ell^{\prime}$. If $\ell$ and $\ell^{\prime}$ are parallel then $U$ is a
plane orthogonal to both lines. We may thus assume that $\ell$ and
$\ell^{\prime}$ are not parallel.

Since $\ell$ is an axis of $U$, we have that $U$ is a union of circles with
axis $\ell$. As we rotate $\mathbb{R}^{3}$ around $\ell^{\prime}$, the line
$\ell$ has infinitely many distinct directions. Since $U$ remains unchanged by
such rotations and $\ell$ remains an axis of $U$, there are infinitely many
directions $v$ such that $U$ is the union of circles orthogonal to $v$. Thus,
every point of $U$ is incident to infinitely many circles that are contained
in $U$. Only planes and spheres have this property (for example, see [20]). ∎

######  Lemma 3.7.

For every integer $k$ there exists a constant $\delta_{k}=O_{k}(1)$ that
satisfies the following. Let $U\subset\mathbb{R}^{3}$ be a surface of degree
$k$. For a line $\ell\subset\mathbb{R}^{3}$, let $\Gamma_{\ell}$ be the set of
circles with axis $\ell$ that are contained in $U$. If
$|\Gamma_{\ell}|>\delta_{k}$ then $U$ is a surface of revolution with axis
$\ell$.

###### Proof.

By rotating and translating $\mathbb{R}^{3}$, we may assume that $\ell$ is the
$z$-axis. Then, every circle of $\Gamma_{\ell}$ can be defined using two
parameters $h,r$ as

$C_{h,r}=\left\\{\left(r\cdot\frac{2t}{1+t^{2}},r\cdot\frac{1-t^{2}}{1+t^{2}},h\right)\
:\ t\in\mathbb{R}\right\\}.$

(One point of the circle is missing in this parametrization: $(0,-r,h)$.)

Let $f\in\mathbb{R}[x,y,z]$ be a degree $k$ polynomial satisfying ${\bf
V}(f)=U$ (after the above transformation). Then $C_{h,r}\subset U$ if and only
if

$f\left(r\cdot\frac{2t}{1+t^{2}},r\cdot\frac{1-t^{2}}{1+t^{2}},h\right)$

is identically zero. This expression is a rational function in $t$, which may
not be a polynomial. We define

$g(t)=f\left(r\cdot\frac{2t}{1+t^{2}},r\cdot\frac{1-t^{2}}{1+t^{2}},h\right)\cdot(1+t^{2})^{k}.$

Note that $g(t)$ is a polynomial in $t$ of degree at most $2k$. In addition,
$C_{h,r}\subset U$ if and only if $g(t)$ is identically zero. That is, all the
coefficients of $g(t)$ are zero. Each such coefficient is a polynomial in $h$
and $r$.

Consider another plane $\mathbb{R}^{2}$ with coordinates $h$ and $r$. Let $W$
be the set of points $(h,r)\in\mathbb{R}^{2}$ that satisfy $C_{h,r}\subset U$.
By the preceding paragraph, $W$ is a variety of complexity $O_{k}(1)$. Indeed,
$W$ is defined by asking each of the coefficients of $g(t)$ to vanish. By
Theorem 2.1, there exists $\delta_{k}$ such that $W$ consists of at most
$\delta_{k}$ components. By assumption $|\Gamma_{\ell}|>\delta_{k}$, so $W$ is
not zero-dimensional. That is, $\Gamma_{\ell}$ is a one-dimensional family of
circles with axis $\ell$.

For $0\leq\alpha<2\pi$, let $R_{\alpha}:\mathbb{R}^{3}\to\mathbb{R}^{3}$ be a
rotation of angle $\alpha$ around $\ell$. Set $U_{\alpha}=U\cap
R_{\alpha}(U)$. In other words, $U_{\alpha}$ is the set of points of $U$ that
remain in $U$ after a rotation of angle $2\pi-\alpha$ around $\ell$. Note that
$U_{\alpha}={\bf V}(f,f\circ R_{2\pi-\alpha})$, so it is a variety. Since
$\Gamma_{\ell}$ is an infinite family of disjoint circles with axis $\ell$, we
get that $U_{\alpha}$ is two-dimensional. Since $U$ is irreducible and
$U_{\alpha}\subseteq U$, we conclude that $U=U_{\alpha}$.

The preceding paragraph holds for every $0\leq\alpha<2\pi$. That is, every
rotation around $\ell$ is a symmetry of $U$. In other words, $U$ is a surface
of revolution with axis $\ell$. ∎

Recall that we defined aligned and perpendicular circles in the introduction.

######  Lemma 3.8.

Let $U\subset\mathbb{R}^{3}$ be a surface of degree $k$. Let $\Gamma$ be a set
of circles that are contained in $U$, such that every two circles of $\Gamma$
are either aligned or perpendicular.
(a) If $U$ is not a surface of revolution then $|\Gamma|=O_{k}(1)$.
(b) Assume that $U\subset\mathbb{R}^{3}$ is a surface revolution with a unique
axis $\ell$. If no circle of $\Gamma$ has axis $\ell$ then
$|\Gamma|=O_{k}(1)$.

###### Proof.

(a) For a plane $H\subset\mathbb{R}^{3}$, let $\Gamma_{H}$ be the set of
circles of $\Gamma$ that are contained in $H$. Since circles in the same plane
cannot be perpendicular, every two circles of $\Gamma_{H}$ are aligned. That
is, every two circles of $\Gamma_{H}$ are concentric. Since $U$ is not a
plane, $\gamma=U\cap H$ is a variety of dimension at most one and complexity
$O_{k}(1)$. Let $\ell$ be a line contained in $H$ and incident to the center
of the circles of $\Gamma_{H}$. Then $\ell$ intersects every circle of
$\Gamma_{H}$ in two distinct points. By Theorem 2.1, when $|\Gamma_{H}|$ is
sufficiently large, the intersection $\ell\cap\gamma$ cannot be zero
dimensional. That is, we obtain that $\ell\subset\gamma$. Since this holds for
every such line $\ell$, we get that $\gamma=H$. This implies that $U=H$,
contradicting the assumption that $U$ is not a surface of revolution. We
conclude that $|\Gamma_{H}|=O_{k}(1)$.

Let $\ell\subset\mathbb{R}^{3}$ be a line and let $\Gamma_{\ell}$ be the set
of circles of $\Gamma$ that have $\ell$ as their axis. By Lemma 3.7, we have
that $|\Gamma_{\ell}|=O_{k}(1)$. That is, the maximum number of circles of
$\Gamma$ that have a common axis is $O_{k}(1)$.

Assume that $\Gamma$ contains two aligned circles $C_{1}$ and $C_{2}$ that do
not lie in the same plane. No circle can be perpendicular to both $C_{1}$ and
$C_{2}$, since the center of such a circle would need to lie on two parallel
planes. Thus, all the circles in $\Gamma$ are aligned. By the preceding
paragraph, in this case $|\Gamma|=O_{k}(1)$.

No four planes in $\mathbb{R}^{3}$ are pairwise perpendicular. This implies
that no four circles in $\mathbb{R}^{3}$ are pairwise perpendicular. Thus,
$\Gamma$ contains at most three pairwise perpendicular circles. By the above,
the plane of each of these circles contains $O_{k}(1)$ circles of $\Gamma$. We
conclude that, if $\Gamma$ contains perpendicular circles then
$|\Gamma|=O_{k}(1)$

We handled the case where $\Gamma$ contains two aligned circles that are not
coplanar. We also handled the case where $\Gamma$ contains two perpendicular
circles. These complete the proof, since no other case remains.

(b) We claim that the proof of part (a) also holds for part (b). In that
proof, we only used $U$ not being a surface of revolution when applying Lemma
3.7. Due to the assumption that the circles of $\Gamma$ do not have axis
$\ell$, we may apply Lemma 3.7 as before. ∎

######  Lemma 3.9.

Let $U\subset\mathbb{R}^{3}$ be a surface of degree $k$. Let $R$ be a rotation
around a line $\ell$ that is a symmetry of $U$. If the angle of $R$ is smaller
than a constant depending only on $k$, then $U$ is a surface of revolution
with axis $\ell$.

###### Proof.

Consider a point $p\in U$ and let $H$ be the plane orthogonal to $\ell$ and
incident to $p$. Let $C$ be the circle in $H$ that is incident to $p$ and with
axis $\ell$. By applying $R$ to $p$, we obtain additional points of $U$ that
are in $C$. Taking the angle of $R$ to be sufficiently small, we may assume
that $U\cap C$ is arbitrarily large. Then, Theorem 2.1 implies that the
intersection $U\cap C$ is not zero-dimensional. This implies that $C\subset
U$.

We may assume that $U$ is not a plane, since otherwise we are done. Then $U$
intersects infinitely many planes orthogonal to $\ell$. By the preceding
paragraph, $U$ contains a circle with axis $\ell$ in each of those planes. By
Lemma 3.7, we conclude that $U$ is a surface of revolution with axis $\ell$. ∎

Ruled surfaces. Let $U$ be a surface in $\mathbb{R}^{3}$. As stated in the
introduction, $U$ is _ruled_ if for every point $p\in U$ there exists a line
that is contained in $U$ and incident to $p$. We only require one basic
property of non-ruled surfaces. For more details, see for example [10,
Corollary 3.3].

######  Lemma 3.10.

A non-ruled surface of degree $D$ in $\mathbb{R}^{3}$ contains $O_{D}(1)$
lines.

Cylindrical surfaces. A surface $U\subset\mathbb{R}^{3}$ is a _cylindrical
surface_ if there exists a curve $\gamma$ that satisfies the following. The
curve $\gamma$ is contained in a plane $H\subset\mathbb{R}^{3}$ with normal
$\vec{v}$. The surface $U$ is the union of the lines in $\mathbb{R}^{3}$ of
direction $\vec{v}$ that are incident to a point of $\gamma$. Equivalently,
$U$ is the union of the translations of $\gamma$ in direction $\vec{v}$. Note
that a plane is a cylindrical surface and that every cylindrical surface is
also a ruled surface.

######  Lemma 3.11.

Let $U\subset\mathbb{R}^{3}$ be a surface with reflectional symmetries about
the distinct planes $H_{1}$ and $H_{2}$. If $H_{1}$ and $H_{2}$ are parallel
then $U$ is a cylindrical surface.

###### Proof.

Let $\delta$ denote the distance between $H_{1}$ and $H_{2}$. Let $\vec{v}$ be
a vector in the direction orthogonal to $H_{1}$ and $H_{2}$. It is not
difficult to verify that composing the two reflections leads to a translation
$T$ of distance $\delta$ in direction $\pm\vec{v}$. By definition, $T$ is also
a symmetry of $U$.

Let $p$ be a point of $U$. Let $\ell\subset\mathbb{R}^{3}$ be the line
incident to $p$ and of direction $\vec{v}$. By repeatedly applying $T$ on $p$,
we obtain that $\ell$ contains infinitely many points of $U$. By Theorem 2.1,
the intersection $U\cap\ell$ is not zero-dimensional. This implies that
$\ell\subseteq U$. In other words, for every $p\in U$ there exists a line
$\ell\subset U$ incident to $p$ and of direction $\vec{v}$. We conclude that
$U$ is a cylindrical surface. ∎

###  3.3 Proof of Theorem 1.3

We are now ready to prove our main result. We first recall the statement of
this theorem.

Theorem 1.3. _Let $U\subset\mathbb{R}^{3}$ be a non-ruled surface of degree
$k$. Let $\mathcal{P}$ be a set of $n$ points on $U$. Then for any
${\varepsilon}>0$, we have _

$D(\mathcal{P})=\Omega_{k}\left(n^{32/39-{\varepsilon}}\right).$

###### Proof.

Since $U$ is non-ruled, it is not a plane. By Theorem 1.1, we may also assume
that $U$ is not a sphere. (We may also assume that $U$ is not a hyperboloid of
two sheet, but this is not necessary for our proof.)

By Lemma 3.10, the surface $U$ contains $O_{k}(1)$ lines. If one of these
lines contains $\Omega(n/\log n)$ points of $\mathcal{P}$, then these points
span $\Omega(n/\log n)$ distinct distances. We may thus assume that each of
these lines contains $O(n/\log n)$ points of $\mathcal{P}$. We discard from
$\mathcal{P}$ all points that lie on a line contained in $U$. After a generic
rotation around the origin, we may also assume that $U$ does not contain lines
that are parallel to the $z$-axis.

We apply Theorem 3.3, to obtain a variety $U_{0}$ and monotone patches
$U_{1},\ldots,U_{M}$. By definition, $U_{0}$ is of dimension at most one and
complexity $O_{k}(1)$. We may assume that $U_{0}$ contains $O(n/\log n)$
points of $\mathcal{P}$. Otherwise, Lemma 2.6 implies a result stronger than
required. Since $M=O_{k}(1)$, by the pigeonhole principle there exists a
monotone patch $U_{j}$ that contains $\Theta_{k}(n)$ points of $\mathcal{P}$.
We discard from $\mathcal{P}$ the points that are not on $U_{j}$. Abusing
notation, we refer to the set of remaining points as $\mathcal{P}$ and to
$U_{j}$ as $U$.

Constructing a multigraph. Recall that, for a point $p\in\mathbb{R}^{3}$ and
$r>0$, we denote by $S(p,r)$ the sphere of radius $r$ centered at $p$. We
define the _level set_

$L(p,r)=U\cap S(p,r).$

That is, $L(p,r)$ is the set of points on $U$ at distance $r$ from $p$. Since
$U$ is not a patch of a sphere, every level set is a semi-algebraic set of
dimension at most one and complexity $O_{k}(1)$.

Let $\mathcal{S}$ be the set of level sets $L(p,r)$ that are incident to at
least one point of $\mathcal{P}$ and with $p\in\mathcal{P}$. For every level
set $L(p,r)$ from $\mathcal{S}$, we discard the zero-dimensional components
and the singular points of $L(p,r)$. By Lemma 2.3, this removes $O_{k}(1)$
points from each level set. We discard empty sets from $\mathcal{S}$. Each
remaining set is a semi-algebraic set of complexity $O_{k}(1)$. We partition
every remaining element of $\mathcal{S}$ to its connected components. By Lemma
2.5, each such set consists of $O_{k}(1)$ connected components.

After the above process, $\mathcal{S}$ consists of segments of curves with no
singular points. Some of those may also be closed. Since the level sets are
contained in spheres, all segments are bounded. We discard from $\mathcal{S}$
segments that contain at most one point of $\mathcal{P}$.

Following Székely’s technique [26] for the planar case, we construct a graph
$G=(V,E)$ as follows. We place a vertex in $V$ for each point of
$\mathcal{P}$. We go over the segments of $\mathcal{S}$ and connect every two
vertices that are consecutive along such a segment. By “consecutive” we mean
that, when traveling along the segment, there are no other points of
$\mathcal{P}$ between the two vertices. Since the segments do not contain
singular points, no segment intersects itself. This means that the process of
travelling along a segment is well-defined. For an example of how edges are
added, see Figure 3. Since segments from the same level set are disjoint, such
segments cannot lead to parallel edges. Thus, an edge $(u,v)$ has multiplicity
$r$ when $u$ and $v$ are consecutive along segments from level sets of $r$
distinct points of $\mathcal{P}$.

$z$$y$$x$$w$$v$$u$ (a) Example of two level sets and the points on them.

$z$$y$$x$$w$$v$$u$ (b) Graph edges corresponding to the two level sets.

Figure 3: Example of edges corresponding to two level sets. There are two
edges between vertices $x$ and $y$ since they are consecutive along both level
sets.

We claim that the number of edges in $G$ is $\Theta(n^{2})$. In particular,
for each $p\in\mathcal{P}$, the level sets of $p$ contribute $\Theta(n)$ edges
to $G$. Indeed, fix $p\in\mathcal{P}$. The level sets of $p$ contain all
points of $\mathcal{P}$. We may assume that
$D(\\{p\\},\mathcal{P}\setminus\\{p\\})=O(n/\log n)$, since otherwise we are
done. In other words, the number of level sets $L(p,r)$ that contain at least
one point of $\mathcal{P}$ is $O(n/\log n)$. By Theorem 2.1, when discarding
zero-dimensional components from the level sets, we lose $O_{k}(n/\log n)$
points of $\mathcal{P}$. For the same reasons, the level sets of $p$
contribute $O_{k}(n/\log n)$ segments to $\mathcal{S}$. These segments are
disjoint, since they do not contain singular points.

By the above, the level sets of a fixed $p\in\mathcal{P}$ correspond to
$O(n/\log n)$ disjoint segments of $\mathcal{S}$ that contain $\Theta(n)$
points of $\mathcal{P}$. A closed segment that contains $r$ points of
$\mathcal{P}$ contributes $r$ edges to $E$. An open segment that contains $r$
points of $\mathcal{P}$ contributes $r-1$ edges. We conclude that the level
sets of $p$ contribute $\Theta(n)$ edges to $E$, which in turn implies that
$|E|=\Theta(n^{2})$.

The crossing number. The proof of the theorem is based on double counting
$\mathrm{cr}(G)$. Recall that crossing numbers do not change when switching
between the plane and a monotone patch. First, we draw $G$ on $U$ according to
its geometric representation. That is, every vertex of $V$ is placed at the
corresponding point of $\mathcal{P}$. Every edge of $E$ is drawn as the arc of
the level set that led to it. These edges are disjoint from the boundary of
$U$.

The intersection of two level sets $L(p_{1},r_{1})$ and $L(p_{2},r_{2})$ is
$U\cap S(p_{1},r_{1})\cap S(p_{2},r_{2})$. Set $C=S(p_{1},r_{1})\cap
S(p_{2},r_{2})$ and note that $C$ is either a circle, a single point, or an
empty set. By Theorem 2.1, either $C\subset U$ or $|C\cap U|=O_{k}(1)$. That
is, the intersection of two level sets is either empty, a set of $O_{k}(1)$
points, or a circle.

When two level sets intersect at a circle $C$, this may lead to two parallel
edges of $E$ that are drawn as the same arc of $C$. In this case, we slightly
move the drawing of one of the edges, so that the two edges no longer
intersect in their interiors. We obtain that the interiors of every two edges
of $E$ intersect in $O_{k}(1)$ points.

Set $t=D(\mathcal{P})$. For every $p\in\mathcal{P}$, the number of level sets
of $p$ that contain at least one point of $\mathcal{P}$ is at most $t$. Thus,
there are $O(nt)$ level sets that contain at least one point of $\mathcal{P}$.
By the above, the number of intersections between the edges that originate
from two different level sets is $O_{k}(1)$. Slightly moving identical edges
may increase the number of intersections, but not by more than a constant
factor. We conclude that

$\mathrm{cr}(G)=O_{k}(n^{2}t^{2}).$ (1)

We would like to apply Lemma 3.5 to obtain a lower bound for $\mathrm{cr}(G)$.
However, the multiplicity of some edges might be high, which makes the lemma
inefficient. To address this issue, we rely on the following lemma. Recall
that the _perpendicular bisector_ of two points $p,q\in\mathbb{R}^{3}$ is the
set of all points $a\in\mathbb{R}^{3}$ that satisfy $|pa|=|qa|$. Equivalently,
it is the plane incident to the midpoint of $p$ and $q$ and orthogonal to the
vector $\overrightarrow{p-q}$.

######  Lemma 3.12.

For an integer $r\geq 2$, let $T_{r}$ be the set of pairs $(H,e)$ such that
$e=(u,v)\in E$, the plane $H\subset\mathbb{R}^{3}$ is the perpendicular
bisector of $u$ and $v$, and $H$ is incident to at least $r$ points of
$\mathcal{P}$. If $e$ and $e^{\prime}$ are parallel edges, then $(H,e)$ and
$(H,e^{\prime})$ represent two distinct pairs in $T_{r}$. Then,

$|T_{r}|=O_{k}\left(\frac{n^{3+{\varepsilon}}t^{3/4}}{r^{9/2}}+\frac{n^{2}t^{3/4}}{r^{2}}+nt\log
n\right).$

If vertices $u,v\in V$ have more than $r$ edges between them, then they are
consecutive on more than $r$ level sets. This in turn implies that the
perpendicular bisector of $u$ and $v$ is $r$-rich. We remove from $G$ all
edges with multiplicity at least $r=\Theta(n^{2/9+{\varepsilon}}t^{1/6})$. By
Lemma 3.12 and recalling that $t=O(n/\log n)$, we get that
$|T_{r}|=O_{k}(n^{2-{\varepsilon}})$. Thus, we still have $|E|=\Theta(n^{2})$.

After the above edge removal, every edge in $E$ has multiplicity
$O(n^{2/9+{\varepsilon}}t^{1/6})$. Lemma 3.5 implies

$\mathrm{cr}(G)=\Omega_{k}\left(\frac{|E|^{3}}{n^{2/9+{\varepsilon}}t^{1/6}|V|^{2}}\right)=\Omega_{k}\left(\frac{n^{34/9-{\varepsilon}}}{t^{1/6}}\right).$

Combining this bound with (1) yields $t=\Omega_{k}(n^{32/39-{\varepsilon}})$,
as required. To complete the proof, it remains to prove Lemma 3.12. We do so
in the following section.

###  3.4 Proof of Lemma 3.12

Rich bisectors. By performing a generic rotation of $\mathbb{R}^{3}$ around
the origin at the beginning of the proof of Theorem 1.3, we may assume the
following. For every pair of distinct points $(p,q)\in\mathcal{P}^{2}$, the
normal to the perpendicular bisector of $p$ and $q$ does not have a zero
$z$-coordinate. In other words, every such bisector can be written as
$ax+by+z=c$ for some $a,b,c\in\mathbb{R}$.

Consider the family of planes in $\mathbb{R}^{3}$ defined as $ax+by+z=c$ with
parameters $a,b,c\in\mathbb{R}$. Taking the intersection of every such plane
with $U$ leads to a family $\mathcal{F}$ of varieties of dimension at most one
and complexity $O_{k}(1)$. An element in this family is defined by the three
parameters $a,b,c$. Since every two planes are either disjoint or intersect at
a line, every two elements of $\mathcal{F}$ intersect either in $O_{k}(1)$
collinear points or in a line.

For a line $\ell$ contained in the original surface $U$, let
$\mathcal{F}_{\ell}$ be the set of varieties of $\mathcal{F}$ that contain
$\ell$. Since these varieties are intersections of planes with $U$, the
intersection of every two varieties of $\mathcal{F}_{\ell}$ is $\ell$.
Recalling that no point of $\mathcal{P}$ is on $\ell$, we observe that every
point of $\mathcal{P}$ is incident to at most one element of
$\mathcal{F}_{\ell}$. In other words, $I(\mathcal{P},\mathcal{F}_{\ell})\leq
n$.

Let $\mathcal{F}_{\text{line}}$ be the set of elements of $\mathcal{F}$ that
contain at least one line that is contained in $U$. Let $\mathcal{F}^{\prime}$
be the set of elements of $\mathcal{F}$ that do not contain any line that is
in $U$. That is,
$\mathcal{F}^{\prime}=\mathcal{F}\setminus\mathcal{F}_{\text{line}}$. By Lemma
3.10, the original surface $U$ contains $O_{k}(1)$ lines. By combining this
with the preceding paragraph, we obtain that
$I(\mathcal{P},\mathcal{F}_{\text{line}})=O_{k}(n)$. This implies that the
number of $r^{\prime}$-rich elements of $\mathcal{F}_{\text{line}}$ is
$O_{k}(n/r^{\prime})$.

We now study $I(\mathcal{P},\mathcal{F}^{\prime})$. Since the elements of
$\mathcal{F}^{\prime}$ contain no lines, every two intersect in $O_{k}(1)$
points. We consider a projection of $\mathcal{P}$ and $\mathcal{F}^{\prime}$
onto a generic plane $\Pi$. Let $\mathcal{P}^{*}$ be the set of projections of
the points of $\mathcal{P}$ on $\Pi$. Let $\mathcal{F}^{*}$ be the set of
Zariski closures of the projections of the elements of $\mathcal{F}^{\prime}$.
By Lemma 2.4, the set $\mathcal{F}^{*}$ consists of varieties of dimension at
most one and complexity $O_{k}(1)$. Since $\Pi$ is chosen generically, we may
assume that no two points of $\mathcal{P}$ are projected into the same point,
that every two elements of $\mathcal{F}^{\prime}$ intersect in $O_{k}(1)$
points, and that
$I(\mathcal{P},\mathcal{F}^{\prime})=I(\mathcal{P}^{*},\mathcal{F}^{*})$.

Recall that $\mathcal{F}$ is contained in a 3-parameter family. This means
that $\mathcal{F}^{*}$ is also contained in a 3-parameter family. By thinking
of $\Pi$ as $\mathbb{R}^{2}$, we may apply Corollary 3.2 with
$\mathcal{F}^{*}$. By applying the corollary with ${\varepsilon}$, $s=3$, and
$\Theta(n)$ points, the number of $r^{\prime}$-rich elements of
$\mathcal{F}^{\prime}$ is

$O_{k}\left(\frac{n^{3+{\varepsilon}}}{(r^{\prime})^{11/2}}+\frac{n^{2}}{(r^{\prime})^{3}}+\frac{n}{r^{\prime}}\right).$
(2)

Since the number of $r$-rich elements of $\mathcal{F}_{\text{line}}$ is
$O(n/r^{\prime})$, we get that (2) is also a bound for the number of
$r^{\prime}$-rich elements in $\mathcal{F}$.

Bounding $|T_{r}|$. Let $H$ be a plane incident to $r^{\prime}$ points of
$\mathcal{P}$. Each of these $r^{\prime}$ points defines at most $t$ level
sets that contain at least one point of $\mathcal{P}$. By Theorem 2.1, such a
level set has $O_{k}(1)$ intersection points with $H$ (ignoring circles fully
contained in $H$). Since each such intersection point leads to at most one
pair $(H,e)\in T_{r}$, we get that $H$ participates in $O_{k}(r^{\prime}t)$
such pairs.

In the following, all logarithms have base 2. For $j>\log\log n$, we consider
planes that are $2^{j}$-rich with respect to $\mathcal{P}$ but not
$2^{j+1}$-rich. We refer to such a plane as $2^{j}$-_fixed_. Below we prove
that, excluding $O_{k}(n/2^{j})$ planes, every $2^{j}$-fixed plane $H$ forms a
pair $(H,e)\in T_{r}$ with $O_{k}(2^{j}t^{3/4})$ edges $e\in E$. We refer to
the excluded planes as _exceptional planes_. We first assume that this claim
holds and derive the assertion of the lemma. Afterwards, we prove this claim.

For a positive integer $j$, let $\Pi_{j}$ be the set of planes that are
$2^{j}$-fixed. Setting $r^{\prime}=2^{j}$ in (2) leads to an upper bound for
$|\Pi_{j}|$. Combining the above and assuming that $r>\log n$ gives

$\displaystyle|T_{r}|$ $\displaystyle\leq\sum_{j=\log r}^{\log
n}\left(|\Pi_{j}|\cdot O\left(2^{j}\cdot
t^{3/4}\right)+O_{k}\left(\frac{n}{2^{j}}\cdot
2^{j}t\right)\right)=\sum_{j=\log r}^{\log
n}O_{k}\left(\frac{n^{3+{\varepsilon}}t^{3/4}}{2^{9j/2}}+\frac{n^{2}t^{3/4}}{2^{2j}}+nt\right)$
$\displaystyle\hskip 156.49014pt=\sum_{j=\log r}^{0.5\log
n}O_{k}\left(\frac{n^{3+{\varepsilon}}t^{3/4}}{2^{9j/2}}+\frac{n^{2}t^{3/4}}{2^{2j}}\right)+\sum_{j=0.5\log
n}^{\log n}O_{k}\left(nt\right)$ $\displaystyle\hskip
156.49014pt=O_{k}\left(\frac{n^{3+{\varepsilon}}t^{3/4}}{r^{9/2}}+\frac{n^{2}t^{3/4}}{r^{2}}+nt\log
n\right).$

It remains to prove the above claim about the non-exceptional planes.

Non-exceptional planes. Let us recall the details of what we need to prove.
For $j>\log\log n$, we need to show that, excluding $O_{k}(n/2^{j})$
exceptional planes, every $2^{j}$-fixed plane $H$ forms a pair $(H,e)\in
T_{r}$ with $O_{k}(2^{j}t^{3/4})$ edges $e\in E$.

Let $H$ be a $2^{j}$-fixed plane. For a point $p\in\mathbb{R}^{3}$, let $H(p)$
be the reflection of $p$ about $H$. Let $\mathcal{P}_{H}$ be the set of points
participating in an edge that forms a pair with $H$. Note that
$\mathcal{P}_{H}$ is contained in $U\cap H(U)$. We define the _type_ of $H$
according to the reflection that it induces.

  * •

The plane $H$ is _Type 1_ if $U=H(U)$ (that is, if $H(\cdot)$ is a symmetry of
$U$).

  * •

The plane $H$ is _Type 2_ if $U\cap H(U)$ contains $O_{k}(t^{3/4})$ points of
$\mathcal{P}$.

  * •

The plane $H$ is _Type 3_ if a circle in $U\cap H(U)$ contains
$\Omega_{k}(t^{3/4})$ points of $\mathcal{P}$.

  * •

The plane $H$ is _Type 4_ if a non-circle component of $U\cap H(U)$ contains
$\Omega_{k}(t^{3/4})$ points of $\mathcal{P}$.

Since $U\cap H(U)$ consists of $O_{k}(1)$ components, $H$ must have one of the
four types. If $H$ satisfies the conditions of more than one case, then the
type of $H$ is the first case satisfied. For example, if the reflection
$H(\cdot)$ is a symmetry of $U$ and $U\cap H(U)$ contains a circle with
$\Omega_{k}(t^{3/4})$ points of $\mathcal{P}$, then $H$ is Type 1 rather than
Type 3. We study the number of planes of each type separately.

Type 1 planes. We begin with the special case where $U$ is a surface of
revolution. Since $U$ is neither a plane nor a sphere, Lemma 3.6 implies that
$U$ has a unique axis $\ell$. Any Type 1 plane is either orthogonal to $\ell$
or contains $\ell$. Since $U$ is not ruled, it is not a cylindrical surface.
By Lemma 3.11, at most one Type 1 plane is orthogonal to $\ell$. The
intersection of any two planes that contain $\ell$ is $\ell$. Since
$|\ell\cap\mathcal{P}|=O_{k}(1)$ and $j>\log\log n$, the number of
$2^{j}$-fixed planes that contain $\ell$ is $O(n/2^{j})$. We conclude that the
number of exceptional planes of Type 1 is $O(n/2^{j})$.

Next, consider the case where $U$ is not a surface of revolution. Let $H_{1}$
and $H_{2}$ be distinct planes that correspond to reflectional symmetries of
$U$. By Lemma 3.11, the planes $H_{1}$ and $H_{2}$ are not parallel. Assume
that the angle between $H_{1}$ and $H_{2}$ is smaller than some sufficiently
small constant $\alpha$. Then $H_{1}\circ H_{2}$ is a rotation of sufficiently
small angle. Lemma 3.9 implies that $U$ is a surface of revolution. This
contradiction implies that the angle between $H_{1}$ and $H_{2}$ is at least
$\alpha$.

Let $\Pi$ be a set of planes in $\mathbb{R}^{3}$, such that no two are
parallel and no two form an angle smaller than $\alpha$. We claim that
$|\Pi|=O_{k}(1)$. Indeed, let $S\subset\mathbb{R}^{3}$ be the unit sphere
centered at the origin. For every plane $H\in\Pi$, we place a point $p_{H}$ on
$S$ so that the vector from the origin to $p_{H}$ has the same direction as
the normal of $H$. By the above, there exists a minimum distance $\alpha$
between any two points on $S$. In other words, when placing an open surface
patch of radius $\alpha/2$ centered at each point, no two patches intersect.
Since the surface area of $S$ is constant and the surface area of each patch
is constant, there could be $O_{k}(1)$ such patches. We conclude that
$|\Pi|=O_{k}(1)$. That is, in this case the number of Type 1 planes is
$O_{k}(1)$.

Type 2 planes. Let $e=(u,v)$ be an edge satisfying $(H,e)\in T_{r}$. Then
$H(u)=v$ and $H(v)=u$. Since each point on $H$ leads to at most one level set
containing both $u$ and $v$, there are $O(2^{j})$ edges parallel to $e$. We
conclude that the number of edges that form a pair with $H$ in $T_{r}$ is
$O(|\mathcal{P}_{H}|2^{j})$. In particular, if $H$ is Type 2 then $H$
participates in $O_{k}(2^{j}t^{3/4})$ pairs $(H,e)\in T_{r}$. That is, Type 2
planes are not exceptional.

Type 3 planes. By Theorem 1.4, if there exist two $\Omega_{k}(t^{3/4})$-rich
circles that are neither perpendicular nor aligned, then $D(\mathcal{P})>t$.
Since this is a contradiction to the definition of $t$, we may assume that no
two such circles exist.

We simultaneously handle the case where $U$ is a surface of revolution and the
case where it is not. In the former case, we first ignore circles that have
the same axis as $U$. By Lemma 3.8, the number of other circles that are
$\Omega_{k}(t^{3/4})$-rich is $O_{k}(1)$. We refer to those as _exceptional
circles_. After concluding our study of the exceptional circles we return to
the ignored circles.

For every pair of distinct exceptional circles $(C_{1},C_{2})$, at most one
reflection of $\mathbb{R}^{3}$ takes $C_{1}$ to $C_{2}$. Thus, distinct pairs
of exceptional circles lead to $O_{k}(1)$ exceptional planes. However, there
may also exist exceptional planes that take an exceptional circle to itself.

Consider an exceptional circle $C$ and let $\ell$ be the axis of $C$. Then all
planes that takes $C$ to itself contain $\ell$ (we may ignore the plane that
contains $C$). Since $|\ell\cap\mathcal{P}|=O_{k}(1)$ and $j>\log\log n$, the
number of $2^{j}$-fixed planes that contain $\ell$ is $O(n/2^{j})$. By summing
this over all $O_{k}(1)$ exceptional circles, we obtain $O_{k}(n/2^{j})$
exceptional planes.

We now consider the circles that were ignored above. To distinguish such
circles from the above exceptional circles, we refer to them as _ignored
circles_. That is, we are in the case where $U$ is a surface of revolution
with axis $\ell$ and consider $\Omega(t^{3/4})$-rich circles with axis $\ell$.

Every plane that maps an ignored circle to itself also contains $\ell$. By
repeating the above argument, we get $O_{k}(n/2^{j})$ such $2^{j}$-fixed
planes. Every plane that maps one ignored circle to another is orthogonal to
$\ell$. Since such planes are disjoint, there are $O(n/2^{j})$ such
$2^{j}$-fixed planes.

It remains to consider planes that map an ignored circle to an exceptional
circle. By Theorem 1.4, we may assume that all exceptional circles are
perpendicular to all ignored circles. If there is more than one ignored
circle, then no circle is perpendicular to both. If there is a single ignored
circle, then $O_{k}(1)$ planes take it to exceptional circles.

Type 4 planes. To analyse this case, we rely on the following special case of
a theorem by Raz [17].

######  Theorem 3.13.

Let $\gamma\subset\mathbb{R}^{3}$ be an irreducible variety of dimension one
and constant complexity that is neither a line nor a circle. Let
$\mathcal{P}\subset\gamma$ be a set of $n$ points. Then
$D(\mathcal{P})=\Omega(n^{4/3})$.

Assume that there exists a plane $H$ of Type 4. By Theorem 3.13, the points on
$U\cap H(U)$ determine $\Omega_{k}(t)$ distinct distances. Taking a
sufficiently large constant in the definition of Type 4, we obtain that the
number of distances is larger than $t$. This contradiction implies that no
plane is of Type 4.

By considering all the above cases, we conclude that the total number of
exceptional planes is $O_{k}(n/2^{j})$. This completes the proof of Lemma
3.12, which in turn completes the proof of Theorem 1.3. ∎

##  4 Few distinct distances between two circles

We now present constructions that have few distinct distances between two
circles. These constructions are based on the notions of aligned and
perpendicular circles, as defined in the introduction.

Theorem 1.4(a). _Let $C_{1}$ and $C_{2}$ be two circles in $\mathbb{R}^{3}$
that are either aligned or perpendicular. Then there exist a set
$\mathcal{P}_{1}\subset C_{1}$ of $m$ points and a set $\mathcal{P}_{2}\subset
C_{2}$ of $n$ points, such that_

$D(\mathcal{P}_{1},\mathcal{P}_{2})=\Theta(m+n).$

###### Proof.

Without loss of generality, assume that $n\geq m$. Since rotations,
translations, and uniform scalings of $\mathbb{R}^{3}$ do not affect the size
of $D(\mathcal{P}_{1},\mathcal{P}_{2})$, we may assume that $C_{1}$ is the
unit circle centered at the origin and contained in the $xy$-plane. We
parametrize $C_{1}$ as

$\left\\{(t,\pm\sqrt{1-t^{2}},0)\ :\ -1\leq t\leq 1\right\\}.$ (3)

The aligned case.  We first consider the case where $C_{1}$ and $C_{2}$ are
aligned. In this case, after the above transformations, $C_{2}$ is contained
in a plane of the form $z=c$ and centered at $(0,0,c)$. If $z=0$ then, to be
aligned, the circles must be concentric. We may then use the construction
presented in the introduction, obtaining
$D(\mathcal{P}_{1},\mathcal{P}_{2})=\Theta(m+n)$. For $z\neq 0$, when
projecting $C_{2}$ onto the $xy$-plane, we get two concentric circles. By
Lemma 2.7, we may again use the construction from the introduction (with the
appropriate $z$-coordinates).

The perpendicular case.  We now consider the case where $C_{1}$ and $C_{2}$
are perpendicular. In this case, the plane containing $C_{2}$ is incident to
the origin and the center of $C_{2}$ is incident to the $xy$-plane. By
rotating around the $z$-axis, we may assume that $C_{2}$ is contained in the
$xz$-plane. Note that the center of $C_{2}$ is on the $x$-axis, and denote
this center as $(-a,0,0)$. Let $r$ denote the radius of $C_{2}$ (after the
above scaling). We parametrize $C_{2}$ as

$\left\\{\left(rs-a,0,\pm r\sqrt{1-s^{2}}\right)\ :\ -1\leq s\leq 1\right\\}.$
(4)

We arbitrarily choose $b\in(a,a+\min\\{1,r\\})$ and $\beta\in((a/b)^{1/n},1)$.
We then consider the point sets

$\displaystyle\mathcal{P}_{1}$
$\displaystyle=\left\\{\left(b\cdot\beta^{j}-a,\sqrt{1-(b\cdot\beta^{j}-a)^{2}},0\right)\
:\ 0\leq j\leq m-1\right\\},$ $\displaystyle\mathcal{P}_{2}$
$\displaystyle=\left\\{\left(-b\cdot\beta^{k},0,r\sqrt{1-\left(\frac{a-b\cdot\beta^{k}}{r}\right)^{2}}\right)\
:\ 0\leq k\leq n-1\right\\}.$

To see that the points of $\mathcal{P}_{1}$ lie on $C_{1}$, set
$t=b\cdot\beta^{j}-a$ in (3). Since $n\geq m$, we have that
$\beta\in((a/b)^{1/m},1)$, which implies that $t>0$. Since $b<a+1$, we get
that $t<1$. Similarly, to see that the points of $\mathcal{P}_{2}$ lie on
$C_{2}$, set $s=\frac{a-b\cdot\beta^{k}}{r}$ in (4). Since
$\beta\in((a/b)^{1/n},1)$, we have that $s<0$. Since $b<a+r$, we have that
$s>-1$.

The square of the distance between a point of $\mathcal{P}_{1}$ and a point of
$\mathcal{P}_{2}$ is

$\displaystyle(b\cdot\beta^{j}-a+b\cdot\beta^{k})^{2}+$
$\displaystyle\left(1-(b\cdot\beta^{j}-a)^{2}\right)+\left(r^{2}-r^{2}\left(\frac{a-b\cdot\beta^{k}}{r}\right)^{2}\right)$
$\displaystyle=b^{2}\beta^{2j}+a^{2}+b^{2}\beta^{2k}-2ab\beta^{j}-2ab\beta^{k}+2b^{2}\beta^{j+k}$
$\displaystyle\hskip
62.59605pt+1-b^{2}\beta^{2j}-a^{2}+2b\beta^{j}a+r^{2}-a^{2}-b^{2}\beta^{2k}+2ab\beta^{k}$
$\displaystyle=2b^{2}\beta^{j+k}+1+r^{2}-a^{2}.$ (5)

The only part of the above expression that depends on the choice of $j$ and
$k$ is $\beta^{j+k}$. Thus, there are exactly $m+n-1$ distinct differences in
$\mathcal{P}_{1}\times\mathcal{P}_{2}$. This completes the proof of part (a)
of Theorem 1.4. ∎

##  5 Many distances between two circles

We now study distinct distances between circles that are neither aligned nor
perpendicular.

Theorem 1.4(b). _Let $C_{1}$ and $C_{2}$ be two circles in $\mathbb{R}^{3}$
that are neither aligned nor perpendicular. Let $\mathcal{P}_{1}\subset C_{1}$
be a set of $m$ points and let $\mathcal{P}_{2}\subset C_{2}$ be a set of $n$
points. Then_

$D(\mathcal{P}_{1},\mathcal{P}_{2})=\Omega\left(\min\left\\{m^{2/3}n^{2/3},m^{2},n^{2}\right\\}\right).$

###### Proof.

Since rotations, translations, and uniform scalings of $\mathbb{R}^{3}$ do not
affect $D(\mathcal{P}_{1},\mathcal{P}_{2})$, we may assume that $C_{1}$ is the
unit circle centered at the origin and contained in the $xy$-plane. Since a
rotation around the $z$-axis takes $C_{1}$ to itself, we may further assume
that the $y$-coordinate of the center of $C_{2}$ is 0.

We now assume that the plane containing $C_{2}$ is not parallel to the
$xy$-plane and to the $xz$-plane. Throughout the proof we ignore several other
special cases. These special cases are handled after the general case, in
Appendix B.

Parametrizing the circles. We parametrize $C_{1}$ as

$\gamma_{1}(s)=\left\\{\left(\frac{2s}{1+s^{2}},\frac{1-s^{2}}{1+s^{2}},0\right)\
:\ s\in\mathbb{R}\right\\}.$ (6)

This parametrization overlooks one point of $C_{1}$, corresponding to the case
where $s\to\infty$. If this missing point is in $\mathcal{P}_{1}$, then we
remove it from $\mathcal{P}_{1}$.

Let $c=(p,0,q)$ be the center of $C_{2}$ and let $r$ be the radius of $C_{2}$.
Let $H$ be the plane containing $C_{2}$ and let $H_{0}$ be the translation of
$H$ that contains the origin. For any two orthogonal unit vectors $V_{1}$ and
$V_{2}$ that span $H_{0}$ (in other words, orthogonal vectors that span the
set of directions of $H$), we can parametrize $C_{2}$ as

$\\{c+r\cdot V_{1}\cdot\cos\theta+r\cdot V_{2}\cdot\sin\theta\ :\
\theta\in[0,2\pi)\\}.$

Let $V^{\prime}_{1}$ be a unit vector contained in the intersection of $H_{0}$
and the $xz$-plane. Similarly, let $V^{\prime}_{2}$ be a unit vector contained
in the intersection of $H_{0}$ and the $xy$-plane. We assume that $H$ does not
contain lines parallel to the $x$-axis. This implies that $V^{\prime}_{1}\neq
V^{\prime}_{2}$. There exist $0<\alpha,\beta<\pi$ such that

$V^{\prime}_{1}=\left(\cos\alpha,0,\sin\alpha\right)\quad\text{ and }\quad
V^{\prime}_{2}=\left(\cos\beta,\sin\beta,0\right)$ (7)

Note that $\beta$ is the angle between the $x$-axis and the line
$H_{0}\cap{\bf V}(z)$ (both lines are in the $xy$-plane). Similarly, $\alpha$
is the angle between the $x$-axis and the line $H_{0}\cap{\bf V}(y)$. The unit
vectors $V^{\prime}_{1}$ and $V^{\prime}_{2}$ span $H_{0}$, but they might not
be orthogonal. The following replaces $V^{\prime}_{2}$ with a unit vector in
$H_{0}$ that is orthogonal to $V^{\prime}_{1}$. First consider

$\vec{n}=V^{\prime}_{1}\times V^{\prime}_{2}=\left(-\sin\alpha\cdot\sin\beta,\
\sin\alpha\cdot\cos\beta,\ \cos\alpha\cdot\sin\beta\right).$

Note that $\vec{n}$ is orthogonal to $H_{0}$.

We next consider

$V^{\prime\prime}_{2}=\vec{n}\times
V^{\prime}_{1}=\left(\sin^{2}\alpha\cdot\cos\beta,\ \sin\beta,\
-\sin\alpha\cdot\cos\alpha\cdot\cos\beta\right).$

We rename $V^{\prime}_{1}$ and $V^{\prime\prime}_{2}$ as $V_{1}$ and $V_{2}$,
respectively. While $V_{2}$ is contained in $H_{0}$ and orthogonal to $V_{1}$,
it might not be a unit vector. To normalize $V_{2}$, we find

$\displaystyle\|V_{2}\|=\big{(}\sin^{4}\alpha\cdot\cos^{2}\beta+\sin^{2}\beta$
$\displaystyle+\sin^{2}\alpha\cdot\cos^{2}\alpha\cdot\cos^{2}\beta\big{)}^{1/2}=\left(\sin^{2}\alpha\cdot\cos^{2}\beta+\sin^{2}\beta\right)^{1/2}.$

Combining the above leads to

$\displaystyle C_{2}$ $\displaystyle=\left\\{c+r\cdot\cos\theta\cdot
V_{1}+r\cdot\sin\theta\cdot\frac{V_{2}}{\|V_{2}\|}\ :\
0\leq\theta<2\pi\right\\}$

As with $C_{1}$, we parametrize $C_{2}$ as

$\gamma_{2}(t)=\left\\{c+r\cdot\frac{1-t^{2}}{1+t^{2}}\cdot
V_{1}+r\cdot\frac{2t}{1+t^{2}}\cdot\frac{V_{2}}{\|V_{2}\|}\ :\
t\in\mathbb{R}\right\\}.$ (8)

As before, the parametrization overlooks one point of $C_{2}$, corresponding
to the case where $t\to\infty$. If this point is in $\mathcal{P}_{2}$, then we
remove it from $\mathcal{P}_{2}$.

Studying the distance function. To recap, in (6) and (8) we parametrized the
two circles, possibly excluding one point from $\mathcal{P}_{1}$ and another
from $\mathcal{P}_{2}$. We denote by $\gamma_{i,x}(s)$ the $x$-coordinate of
$\gamma_{i}(s)$, and similarly for $\gamma_{i,y}(s)$ and $\gamma_{i,z}(s)$.
Let $\rho(s,t)$ be the square of the distance between $\gamma_{1}(s)$ and
$\gamma_{2}(t)$. That is,

$\rho(s,t)=(\gamma_{1,x}(s)-\gamma_{2,x}(t))^{2}+(\gamma_{1,y}(s)-\gamma_{2,y}(t))^{2}+(\gamma_{1,z}(s)-\gamma_{2,z}(t))^{2}.$

The following is a bipartite variant of a result of Raz [17]. The proof can be
seen as a simple variant of the one in [17]. Recall that a real function is
_analytic_ if it has derivatives of every order and agrees with its Taylor
series in a neighborhood of every point.

######  Lemma 5.1.

With the above definitions, at least one of the following holds:

  * •

$D(\mathcal{P}_{1},\mathcal{P}_{2})=\Omega\left(\min\left\\{m^{2/3}n^{2/3},m^{2},n^{2}\right\\}\right)$.

  * •

For $j\in\\{1,2,3\\}$, there exist an open interval $I_{j}\subset\mathbb{R}$
and an analytic function $\varphi_{j}:I_{j}\to\mathbb{R}$ with an analytic
inverse, that satisfy the following. For every $s\in I_{1}$ and $t\in I_{2}$,
we have that $\rho(s,t)=\varphi_{1}(\varphi_{2}(s)+\varphi_{3}(t))$.

Note that (5) is an example of
$\rho(s,t)=\varphi_{1}(\varphi_{2}(s)+\varphi_{3}(t))$ in the perpendicular
case.

###### Proof of Lemma 5.1..

The proof is based on the following result from Raz, Sharir, de Zeeuw [18,
Sections 2.1 and 2.3]. See also Raz [17, Lemma 2.4].

######  Theorem 5.2.

Let $F\in\mathbb{R}[x,y,z]$ be a constant-degree irreducible polynomial, such
that none of the three first partial derivatives of $F$ is identically zero.
Then at least one of the following two cases holds.

  1. (i)

For all $A,B\subset\mathbb{R}$ with $|A|=m$ and $|B|=n$, we have

$\displaystyle\big{|}\big{\\{}(a,a^{\prime},b,b^{\prime})\in A^{2}\times
B^{2}\ :\ \text{ exists }c\in\mathbb{R}\text{ such that }F(a$
$\displaystyle,b,c)=F(a^{\prime},b^{\prime},c)=0\big{\\}}\big{|}$
$\displaystyle=O\left(m^{4/3}n^{4/3}+m^{2}+n^{2}\right).$

  2. (ii)

There exists a one-dimensional subvariety $Z^{*}\subset{\bf V}(F)$ of
complexity $O(1)$ such that every $p\in{\bf V}(F)\setminus Z^{*}$ satisfies
the following: For each $j\in\\{1,2,3\\}$ there exist an open interval
$I_{j}^{p}\subset\mathbb{R}$ and a real analytic function
$\psi_{j}^{p}:I_{j}^{p}\to\mathbb{R}$ with an analytic inverse such that $p\in
I_{1}^{p}\times I_{2}^{p}\times I_{3}^{p}$ and for all $(x,y,z)\in
I_{1}^{p}\times I_{2}^{p}\times I_{3}^{p}$ we have

$(x,y,z)\in{\bf V}(F)\quad\text{ if and only if
}\quad\psi_{1}^{p}(x)+\psi_{2}^{p}(y)+\psi_{3}^{p}(z)=0.$

We now briefly sketch the remainder of the proof of Lemma 5.1. We first
construct a variety $U\subset\mathbb{R}^{3}$ that in some way describes the
distances between $C_{1}$ and $C_{2}$. We then apply Theorem 5.2 on the
polynomial $f\in\mathbb{R}[x,y,z]$ that generates ${\bf I}(f)$. We show that,
when we are in case (i) of the theorem, $D(\mathcal{P}_{1},\mathcal{P}_{2})$
is large. Finally, we show that case (ii) of the theorem implies
$\rho(s,t)=\varphi_{1}(\varphi_{2}(s)+\varphi_{3}(t))$ as in the statement of
Lemma 5.1.

It is not difficult to show that any circle in $\mathbb{R}^{3}$ is the zero-
set of a polynomial of degree four. Let $f_{1},f_{2}\in\mathbb{R}[x,y,z]$ be
polynomials of degree four that satisfy $C_{1}={\bf V}(f_{1})$ and $C_{2}={\bf
V}(f_{2})$. Consider points $p=(p_{x},p_{y},p_{z})\in C_{1}$ and
$q=(q_{x},q_{y},q_{z})\in C_{2}$ at a distance of $\delta\in\mathbb{R}$ from
each other. Setting $\Delta=\delta^{2}$ leads to

$\displaystyle f_{1}(p_{x},p_{y},p_{z})$ $\displaystyle=0,$ $\displaystyle
f_{2}(q_{x},q_{y},q_{z})$ $\displaystyle=0,$
$\displaystyle(p_{x}-q_{x})^{2}+(p_{y}-q_{y})^{2}$
$\displaystyle+(p_{z}-q_{z})^{2}=\Delta.$

Considering $p_{x},p_{y},p_{z},q_{x},q_{y},q_{z},\Delta$ as variables, the
above system defines a variety $U\in\mathbb{R}^{7}$ of complexity at most
four. At most two points $p\in C_{1}$ are contained in the axis of $C_{2}$.
For every other point $p\in C_{1}$ and squared distance $\Delta$, there are at
most two values of $q$ that satisfy the above system. This implies that $\dim
U\leq 2$. Since $U$ is the union of infinitely many disjoint one-dimensional
varieties (one for every $p\in C_{1}$), we conclude that $\dim U=2$.

Let $\pi:\mathbb{R}^{7}\to\mathbb{R}^{3}$ be the projection defined as

$\pi(p_{x},p_{y},p_{z},q_{x},q_{y},q_{z},\Delta)=(p_{x},q_{x},\Delta).$

Set $U_{3}=\pi(U)$. By Lemma 2.4, this is a semi-algebraic set of dimension at
most two and of complexity $O(1)$. Since $C_{1}$ is a circle in the
$xy$-plane, no three points on $C_{1}$ have the same $x$-coordinate. The same
holds for $C_{2}$, since it is a circle not contained in a plane parallel to
the $yz$-plane. Thus, the preimage of every point of $\pi(U)$ consists of at
most four points of $U$. This implies that $\dim U_{3}=2$.

Consider the set

$Z=\left\\{(\gamma_{1,x}(s),\gamma_{2,x}(t),\rho(s,t))\ :\
s,t\in\mathbb{R}\right\\}.$

Note that $Z$ is equivalent to $U_{3}$ up to the two points that are not
covered by the parametrizations $\gamma_{1}(s)$ and $\gamma_{2}(t)$. These two
missing points yield a one-dimensional constant-complexity semi-algebraic set
$Z_{0}\subset U_{3}$ such that $U_{3}=Z\cup Z_{0}$.

Let $F\in\mathbb{R}[x,y,z]$ be a constant-degree polynomial satisfying
$\overline{U_{3}}={\bf V}(F)$. We claim that no first partial derivative of
$F$ is identically zero. Indeed, from the definition of $Z$ we note that $F$
must depend on all three coordinates. We may thus apply Theorem 5.2 with $F$.
We partition the remainder of the proof of Lemma 5.1 according to the case of
the theorem that holds.

The quadruples case. First assume that the first case of Theorem 5.2 holds
(the case involving the number of quadruples). Define

$Q=\big{\\{}(a,a^{\prime},b,^{\prime}b)\in\mathcal{P}_{1}^{2}\times\mathcal{P}_{2}^{2}\
:\ \text{ exists }c\in\mathbb{R}\text{ such that
}F(a,b,c)=F(a^{\prime},b^{\prime},c)=0\big{\\}}.$

By Theorem 5.2, we have that

$|Q|=O\left(m^{4/3}n^{4/3}+m^{2}+n^{2}\right).$

For $\delta\in\mathbb{R}$, set
$m_{\delta}=|\\{(a,b)\in\mathcal{P}_{1}\times\mathcal{P}_{2}\ :\
|ab|=\delta\\}|$. In other words, $m_{\delta}$ is the number of pairs in
$\mathcal{P}_{1}\times\mathcal{P}_{2}$ at distance $\delta$. Since every pair
of $\mathcal{P}_{1}\times\mathcal{P}_{2}$ contributes to one $m_{\delta}$, we
get that $\sum_{\delta}m_{\delta}=\Theta(mn)$. The number of quadruples in $Q$
that satisfy $|ab|=|a^{\prime}b^{\prime}|=\delta$ is $m_{\delta}^{2}$.
Combining this observation with the Cauchy–Schwarz inequality gives us

$|Q|=\sum_{\delta}m_{\delta}^{2}\geq\frac{(\sum_{\delta}m_{\delta})^{2}}{D(\mathcal{P}_{1},\mathcal{P}_{2})}=\Theta\left(\frac{m^{2}n^{2}}{D(\mathcal{P}_{1},\mathcal{P}_{2})}\right).$

Combining the two above bounds for $|Q|$ gives

$\frac{m^{2}n^{2}}{D(\mathcal{P}_{1},\mathcal{P}_{2})}=O\left(m^{4/3}n^{4/3}+m^{2}+n^{2}\right),\quad\text{
or }\quad
D(\mathcal{P}_{1},\mathcal{P}_{2})=\Omega\left(\min\left\\{m^{2/3}n^{2/3},m^{2},n^{2}\right\\}\right).$

This completes the first case of the proof of Lemma 5.1.

The case where $F$ has a special form. We now consider the second case of
Theorem 5.2 (the case stating that $F$ has a special form in an open
neighborhood of most points). As in the statement of the theorem, the
exceptional set $Z_{0}^{*}$ is a variety of dimension one and complexity
$O(1)$. We consider a point $v=(x_{0},y_{0},\Delta_{0})\in
Z\setminus(Z_{0}\cup Z^{*})$. Then for $j\in\\{1,2,3\\}$ there exist an open
interval $I_{j}\subset\mathbb{R}$ and a real-analytic function
$\psi_{j}:I_{j}\to\mathbb{R}$ with an analytic inverse that satisfy the
following. We have that $(x_{0},y_{0},\Delta_{0})\in I_{1}\times I_{2}\times
I_{3}$. Every $(x,y,\Delta)\in I_{1}\times I_{2}\times I_{3}$ satisfies

$(x,y,\Delta)\in{\bf V}(F)\quad\text{ if and only if
}\quad\psi_{1}(x)+\psi_{2}(y)+\psi_{3}(\Delta)=0.$ (9)

Set $\psi^{\prime}_{1}(x)=-\psi_{1}(x)$ and
$\psi^{\prime}_{2}(y)=-\psi_{2}(y)$. We rewrite (9) as

$(x,y,\Delta)\in{\bf V}(F)\quad\text{ if and only if
}\quad\Delta=\psi_{3}^{-1}\left(\psi^{\prime}_{1}(x)+\psi^{\prime}_{2}(y)\right).$

Recall that $\rho(s,t)=\Delta$, where we use the point parametrizations
$\gamma_{1}(s)$ and $\gamma_{2}(t)$. Thus, there exist open intervals
$S,T\subset\mathbb{R}$, such that for every $s\in S$ and $t\in T$ we have

$\rho(s,t)=\Delta\quad\text{ if and only if
}\quad\Delta=\psi_{3}^{-1}\big{(}\psi^{\prime}_{1}(\gamma_{1,x}(s))+\psi^{\prime}_{2}(\gamma_{2,x}(t))\big{)}.$

That is, there exists an open neighborhood where

$\rho(s,t)=\psi_{3}^{-1}\big{(}\psi^{\prime}_{1}(\gamma_{1,x}(s))+\psi^{\prime}_{2}(\gamma_{2,x}(t))\big{)}.$

Since $\gamma_{1,x}(s)$ and $\gamma_{2,x}(t)$ are rational functions in $t$
and $s$, they are analytic. By inspecting the definitions in (6) and (8), we
note that their inverses are solutions to quadratic equations. Thus, in a
sufficiently small open neighborhood, we may remove the $\pm$ from the
quadratic formula, to obtain analytic inverses. This in turn implies that
$\psi^{\prime}_{1}\circ\gamma_{1,x}(s)$ and
$\psi^{\prime}_{2}\circ\gamma_{2,x}(t)$ are analytic with analytic inverses.
Setting $\varphi_{1}=\psi_{3}^{-1}$,
$\varphi_{2}=\psi^{\prime}_{1}\circ\gamma_{1,x}(s)$, and
$\varphi_{3}=\psi^{\prime}_{2}\circ\gamma_{2,x}(t)$ concludes the second case
of Lemma 5.1. ∎

To complete the proof of Theorem 1.4(b), it remains to show that we cannot be
in the second case of Lemma 5.1. For this, we rely on the following
_derivative test_ (see for example [29]). For a function $f$, we write
$f_{x}=\frac{\partial f}{\partial x}$.

######  Lemma 5.3.

Let $f\in\mathbb{R}[x,y]$ be twice differentiable with $f_{y}\not\equiv 0$.
Let $N$ be an open neighborhood in $\mathbb{R}^{2}$. If there are
differentiable $\varphi_{1},\varphi_{2},\varphi_{3}\in\mathbb{R}[z]$
satisfying

$f(x,y)=\varphi_{1}(\varphi_{2}(x)+\varphi_{3}(y))\ \text{ for every }(x,y)\in
N$

then

$\frac{\partial^{2}(\log|f_{x}/f_{y}|)}{\partial x\partial y}\quad\text{is
identically zero in $N$.}$

###### Proof.

Assume that there exist $\varphi_{1},\varphi_{2},\varphi_{3}\in\mathbb{R}[z]$
as stated in the lemma. Then

$\displaystyle f_{x}(x,y)=\frac{\partial\varphi_{1}}{\partial
x}(x,y)\cdot\frac{\partial\varphi_{2}}{\partial x}(x)\quad\text{ and }\quad
f_{y}(x,y)=\frac{\partial\varphi_{1}}{\partial
y}(x,y)\cdot\frac{\partial\varphi_{3}}{\partial y}(y).$

Combining the above gives

$\log\left|f_{x}/f_{y}\right|=\log\left|\frac{\partial\varphi_{2}}{\partial
x}(x)/\frac{\partial\varphi_{3}}{\partial
y}(y)\right|=\log\left|\frac{\partial\varphi_{2}}{\partial
x}(x)\right|-\log\left|\frac{\partial\varphi_{3}}{\partial y}(y)\right|.$

Differentiating with respect to both $x$ and $y$ gives 0, which completes the
proof. ∎

Recall that our goal is to show that the second case of Lemma 5.1 cannot
happen. By Lemma 5.3, it suffices to show that

$g(s,t)=\frac{\partial^{2}(\log|\rho_{t}/\rho_{s}|)}{\partial s\partial t}$
(10)

is not identically zero in any open neighborhood of $\mathbb{R}^{2}$. Since
$\rho(s,t)$ is a rational function in $s$ and $t$, so is $g(s,t)$. Thus, the
$g(s,t)$ is identically zero everywhere if and only if the numerator is
identically zero everywhere. That is, if every coefficient in the numerator is
0.

Since (10) includes a logarithm and an absolute value, how can we say that
$g(s,t)$ is rational? To see that, we set $h(s,t)=\rho_{t}/\rho_{s}$. Since
$\rho(s,t)$ is a rational function in $s$ and $t$, so is $h(s,t)$. For each
point $(s,t)$ that satisifies $\rho_{s}(s,t)\neq 0$ and $\rho_{t}(s,t)\neq 0$,
there exists an open neighbourhood where $|h(s,t)|=c\cdot h(s,t)$, where
$c\in\\{-1,1\\}$. In either case, we have that

$\frac{\partial}{\partial t}\log|h(s,t)|=\frac{1}{c\cdot
h(s,t)}\cdot\frac{\partial}{\partial t}(c\cdot
h(s,t))=\frac{h_{t}(s,t)}{h(s,t)}.$

This implies that, at any point where both $\rho_{t}$ and $\rho_{s}$ are
nonzero, we have that $g(s,t)=\frac{\partial}{\partial
s}\left(\frac{h_{t}(s,t)}{h(s,t)}\right)$. This is indeed a rational function.

Since $\rho(s,t)$ depends on parameters $p,q,r,\alpha$ and $\beta$, the
expression $g(s,t)$ is too large to compute by hand. Instead, we used
Mathematica [15] to compute it. Our code can be found in Appendix A. Since
$g(s,t)$ is a rational function, it suffices to determine the parameters
$p,q,r,\alpha$ and $\beta$ for which the coefficients of some of the monomials
in the numerator do not simultaneously vanish. We do so in Appendix B. In the
same appendix, we also address the special cases that were ignored in the
above analysis. ∎

## References

  * [1] M. Ajtai, V. Chvátal, M. M. Newborn, and E. Szemerédi, Crossing-free subgraphs, _Annals Discrete Math._ 12 (1982), 9–12.
  * [2] S. Barone, and S. Basu, Refined bounds on the number of connected components of sign conditions on a variety, _Discrete Comput. Geom._ 47 (2012), 577–597.
  * [3] S. Basu, R. Pollack, and M. F. Roy, _Algorithms in real algebraic geometry_ , Springer, 2006.
  * [4] J. Bochnak, M. Coste, and M. Roy, _Real Algebraic Geometry_ , Springer-Verlag, Berlin, 1998.
  * [5] E. Breuillard, B. Green, and T. Tao, Approximate subgroups of linear groups, _Geom. Funct. Anal._ 21 (2011), 774.
  * [6] F. Chung, The number of different distances determined by n points in the plane, _J. Comb. Theory Ser. A._ 36 (1984), 342–354.
  * [7] G. Elekes, Circle grids and bipartite graphs of distances, _Combinatorica_ 15 (1995), 167–174.
  * [8] P. Erdős, On some of my favourite theorems, Combinatorics, Paul Erdős is Eighty, Vol. 2 (D. Miklós et al., eds.), Bolyai Society Mathematical Studies 2, Budapest, 1996, 97–132.
  * [9] P. Erdős, On sets of distances of $n$ points, _Amer. Math. Monthly_ 53 (1946), 248–250.
  * [10] L. Guth and N.H. Katz, On the Erdős distinct distances problem in the plane, Annals Math. 181 (2015), 155–190.
  * [11] J. Harris, _Algebraic geometry: a first course_ , Springer, New York, 1992.
  * [12] J. Kollár, Szemerédi–Trotter-type theorems in dimension 3, _Advances Math._ 271 (2015), 30–61.
  * [13] F. T. Leighton, _Complexity issues in VLSI: optimal layouts for the shuffle-exchange graph and other networks_ , MIT press, 1983.
  * [14] H. Lenz, Zur Zerlegung von Punktmengen in solche kleineren Durchmessers, _Arch. Math._ 5 (1955), 413–416.
  * [15] Wolfram Research, Inc., Mathematica, Version 12.0, Champaign, IL (2019).
  * [16] J. Pach and F. de Zeeuw, Distinct distances on algebraic curves in the plane, _Comb. Probab. Comp_ 26 (2017): 99–117.
  * [17] O. E. Raz, A note on distinct distances, _Combinat. Probab. Comput._ , to appear.
  * [18] O. E. Raz, M. Sharir, and F. De Zeeuw, Polynomials vanishing on Cartesian products: The Elekes–Szabó theorem revisited, _Duke Math. J._ 165 (2016): 3517–3566.
  * [19] M. Sharir, A. Sheffer, and J. Solymosi, Distinct distances on two lines, _J. Comb. Theory Ser. A._ 120 (2013), 1732–1736.
  * [20] M. Sharir, A. Sheffer, and J. Zahl, Improved bounds for incidences between points and circles, _Combinat. Probab. Comput._ 24 (2015), 490–520.
  * [21] M. Sharir and N. Solomon, Incidences with curves and surfaces in three dimensions, with applications to distinct and repeated distances, _Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms_ (SODA), Society for Industrial and Applied Mathematics, 2017.
  * [22] M. Sharir and N. Solomon, Distinct and Repeated Distances on a Surface and Incidences between points and spheres, arXiv:1604.01502.
  * [23] M. Sharir and J. Zahl, Cutting algebraic curves into pseudo-segments and applications, _J. Comb. Theory Ser. A._ 150 (2017), 1–35.
  * [24] J. Solymosi and T. Tao, An incidence theorem in higher dimensions, _Discrete Comput. Geom._ 48 (2012), 255–280.
  * [25] J. Solymosi and C. D. Tóth, Distinct distances in the plane, _Discrete Comput. Geom._ 25 (2001), 629–634.
  * [26] L. Székely, Crossing numbers and hard Erdős problems in discrete geometry, _Combinat. Probab. Comput._ 6 (1997), 353–358.
  * [27] T. Tao, Lines in the Euclidean group SE(2), blog post, https://terrytao.wordpress.com/2011/03/05/lines-in-the-euclidean-group-se2/
  * [28] G. Tardos, On distinct sums and distinct distances, _Advances Math._ 180 (2003), 275–289.
  * [29] F. de Zeeuw, A survey of Elekes-Rónyai-type problems, In _New Trends in Intuitive Geometry_ , Springer, Berlin, Heidelberg, 2018, 95–124.

##  Appendix A The Mathematica code

In this appendix, we describe the Mathematica program that was used in the
proof of Theorem 1.4(b). Listing 1 contains the code that is used for the
general case of the proof. Lines 1–7 define the parametrizations described in
(6) and (8). Lines 8–9 define the function $\rho(s,t)$. Line 10 is the
derivative test of Lemma 5.3. Finally, line 11 shows the coefficient of a
specific term.

Listing 1: The Mathematica code.

⬇

1v1 = {Cos[$\displaystyle\alpha$], 0, Sin[$\displaystyle\alpha$]};

2v2 = {Cos[$\displaystyle\beta$] Sin[$\displaystyle\alpha$]2,
Sin[$\displaystyle\beta$], -Cos[$\displaystyle\alpha$]
Cos[$\displaystyle\beta$] Sin[$\displaystyle\alpha$]};

3v2norm = Sqrt[(v2[[1]]2 + v2[[2]]2 + v2[[3]]2)];

4c1 = {2 s/(1 + s2), (1 - s2)/(1 + s2), 0};

5c2 = {p + r (1 - t2) v1[[1]]/(1 + t2) + 2 r t v2[[1]]/((1 + t2) v2norm),

6 r (1 - t2) v1[[2]]/(1 + t2) + 2 r t v2[[2]]/((1 + t2) v2norm),

7 q + r (1 - t2) v1[[3]]/(1 + t2) + 2 r t v2[[3]]/((1 + t2) v2norm)};

8dist[s_, t_] :=

9 Together[Expand[(c1[[1]] - c2[[1]])2 + (c1[[2]] -c2[[2]])2 + (c1[[3]] -
c2[[3]])2]];

10RhoTest = Numerator[Together[D[D[Log[D[dist[s, t], s]/D[dist[s, t], t]], s],
t]]];

11Coefficient[RhoTest, s5 t] // Factor

The code of Listing 1 leads to expressions somewhat more involved than the
ones stated in Section 5. For example, the coefficient of $s^{5}t$ produced by
Mathematica is

$\displaystyle 96r(p+r\cos\alpha)\cos\beta\sin^{2}\alpha(-r$
$\displaystyle+p\cos\alpha+r\cos^{2}\alpha+q\sin\alpha+r\sin^{2}\alpha)$
$\displaystyle\cdot\sin\beta(\cos^{2}\alpha\cos^{2}\beta\sin^{2}\alpha+\cos^{2}\beta\sin^{4}\alpha+\sin^{2}\beta)$

The above expression can be simplified by noting that

$\displaystyle-r+p\cos\alpha+r\cos^{2}\alpha+q\sin\alpha+r\sin^{2}\alpha$
$\displaystyle=p\cos\alpha+q\sin\alpha,\text{ and }$
$\displaystyle\cos^{2}\alpha\cos^{2}\beta\sin^{2}\alpha+\cos^{2}\beta\sin^{4}\alpha+\sin^{2}\beta$
$\displaystyle=\cos^{2}\beta\sin^{2}\alpha+\sin^{2}\beta.$

Looking at Lemma 5.3, it may seem as if we forgot to include the absolute
value in Listing 1. For some $f\in\mathbb{R}[x]$, consider

$\frac{\partial}{\partial x}\log|f(x)|=\begin{cases}\frac{\partial}{\partial
x}\log f(x)\qquad&\text{ if }f(x)>0,\\\ \frac{\partial}{\partial
x}\log\left(-f(x)\right)\qquad&\text{ if }f(x)<0.\end{cases}$

In either case the derivative is $f^{\prime}(x)/f(x)$. We may thus ignore the
absolute value in Lemma 5.3.

The special cases at the end of Section 5 require minor changes in the code
from Listing 1. For example, the case of $\cos\beta=0$ is obtained by changing
lines 2–3 to $v_{2}=(0,1,0)$. The case of $C_{2}$ being centered at the origin
is obtained by removing “p+” for line 5 and “q+” from line 7.

##  Appendix B Analysis of the derivative test

In this appendix, we complete the proof of Theorem 1.4(b) by showing that
$g(s,t)$ as defined in (10) cannot vanish everywhere, and also address the
special cases. To do so, we note that $g(s,t)$ is a rational function, and it
suffices to show that there exist monomials in the numerator whose
coefficients cannot simultaneously vanish. We consider several such monomials:

  * •

The coefficient of $s^{5}t$ is

$96r(p+r\cos\alpha)\cos\beta\sin^{2}\alpha(p\cos\alpha+q\sin\alpha)\sin\beta(\cos^{2}\beta\sin^{2}\alpha+\sin^{2}\beta).$

  * •

The coefficient of $s^{5}t^{9}$ is

$96r(p-r\cos\alpha)\cos\beta\sin^{2}\alpha(p\cos\alpha+q\sin\alpha)\sin\beta(\cos^{2}\beta\sin^{2}\alpha+\sin^{2}\beta).$

  * •

The coefficient of $s^{3}t^{9}$ is

$\displaystyle 64r$
$\displaystyle(p-r\cos\alpha)\cos\beta\sin\alpha\sin\beta(\cos^{2}\beta\sin^{2}\alpha+\sin^{2}\beta)$
$\displaystyle\hskip
170.71652pt\cdot(-2q\cos^{2}\alpha+p\cos\alpha\sin\alpha-q\sin^{2}\alpha).$

  * •

The coefficient of $s^{3}t$ is

$\displaystyle 64r$
$\displaystyle(p+r\cos\alpha)\cos\beta\sin\alpha\sin\beta(\cos^{2}\beta\sin^{2}\alpha+\sin^{2}\beta)$
$\displaystyle\hskip
170.71652pt\cdot(-2q\cos^{2}\alpha+p\cos\alpha\sin\alpha-q\sin^{2}\alpha).$

By definition, $r\neq 0$. Recall that $H$ (the plane containing $C_{2}$) is
not parallel to the $xy$-plane or the $xz$-plane. Since we also assumed $H$
does not contain lines parallel to the $x$-axis, we have that $\sin\alpha\neq
0$ and $\sin\beta\neq 0$. Indeed, this is easy to see when recalling that
$V^{\prime}_{1}$ and $V^{\prime}_{2}$ from (7) span the directions of $H$.
This implies that $(\cos^{2}\beta\sin^{2}\alpha+\sin^{2}\beta)\neq 0$. Since
we assume that $H$ is not parallel to the $xz$-plane, we have that
$\sin\beta\neq 0$. We now also assume that the center of $C_{2}$ is not the
origin, that $\cos\alpha\neq 0$, and that $\cos\beta\neq 0$. These special
cases are addressed after completing the general cases.

Since $\cos\alpha\neq 0$, it is not possible for $(p-r\cos\alpha)$ and
$(p+r\cos\alpha)$ to be zero simultaneously. Thus, the only way for all of the
four above coefficients to equal zero is to have both

$p\cos\alpha+q\sin\alpha=0\quad\text{ and
}\quad-2q\cos^{2}\alpha+p\cos\alpha\sin\alpha-q\sin^{2}\alpha=0.$

We rearrange the first equation as $p\cos\alpha=-q\sin\alpha$. Plugging this
into the second equation gives

$0=-2q\cos^{2}\alpha+p\cos\alpha\sin\alpha-q\sin^{2}\alpha=-2q\cos^{2}\alpha-2q\sin^{2}\alpha=-2q.$

That is, $q=0$. We then have $p\cos\alpha=-q\sin\alpha=0$, or $p=0$. This
contradicts the assumption that $C_{2}$ is not centered at the origin.

By the above, it is impossible for the four above coefficients to be zero
simultaneously. This implies that $g(s,t)$ is not identically zero in any open
neighborhood $N\subset\mathbb{R}^{2}$. By Lemma 5.3, we get that $\rho(s,t)$
cannot be rewritten as $\varphi_{1}(\varphi_{2}(s)+\varphi_{3}(t))$ for every
$(x,y)\in N$. Then, Lemma 5.1 implies the assertion of the theorem.

The special cases. In the above proof, we assume:

  * •

The plane $H$ is not parallel to the $xy$-plane, to the $xz$-plane, or to the
$yz$-plane.

  * •

$H$ does not contain lines parallel to the $x$-axis.

  * •

The center of $C_{2}$ is not the origin.

  * •

$\cos\beta\neq 0$.

  * •

$\cos\alpha\neq 0$.

We now address each of these special cases, in the above order.

We first consider the case where $H$ is parallel to the $xy$-plane. As
discussed in the introduction, if $H$ is the $xy$-plane and $C_{1}$ and
$C_{2}$ are not concentric, then
$D(\mathcal{P}_{1},\mathcal{P}_{2})=\Omega\left(\min\left\\{m^{2/3}n^{2/3},m^{2},n^{2}\right\\}\right)$.
When $H$ is parallel to the $xy$-plane, we can combine the above with Lemma
2.7, to obtain the following. If $C_{1}$ and $C_{2}$ are not aligned then
$D(\mathcal{P}_{1},\mathcal{P}_{2})=\Omega\left(\min\left\\{m^{2/3}n^{2/3},m^{2},n^{2}\right\\}\right)$.

Next consider the case where $H$ is parallel to the $xz$-plane. In this case,
we can rewrite $V_{1}=(1,0,0)$ and $V_{2}=(0,0,1)$, which significantly
simplifies (8). The Mathematica program then implies that the numerator of
$g(s,t)$ is $4q(1+t^{2})(-1+s^{2})$. This expression is not identically zero
unless $q=0$. If $q=0$ then the center of $C_{2}$ is on the $x$-axis and $H$
contains the origin. That is, if $q=0$ then $C_{1}$ and $C_{2}$ are
perpendicular. We conclude that either
$D(\mathcal{P}_{1},\mathcal{P}_{2})=\Omega\left(\min\left\\{m^{2/3}n^{2/3},m^{2},n^{2}\right\\}\right)$
or the circles are perpendicular.

We move to the case where $H$ is parallel to the $yz$-plane. We rewrite
$V_{1}=(0,1,0)$ and $V_{2}=(0,0,1)$. In this case, the coefficient of $s^{2}$
in the numerator of $g(s,t)$ is $4pr$. The coefficient of $s^{3}t^{4}$ is
$16q(3p^{2}-8r^{2})$. For both of these coefficients to be zero, we must have
$p=q=0$, implying that the two circles are perpendicular. Once again, either
$D(\mathcal{P}_{1},\mathcal{P}_{2})=\Omega\left(\min\left\\{m^{2/3}n^{2/3},m^{2},n^{2}\right\\}\right)$
or the circles are perpendicular.

We next assume that $H$ contains lines parallel to the $x$-axis. In this case,
we can write $V_{1}=(1,0,0)$ and $V_{2}=(0,\cos\gamma,\sin\gamma)$. Since $H$
is not parallel to the $xy$-plane and $xz$-plane, we have that $\sin\gamma\neq
0$ and $\cos\gamma\neq 0$. We consider the following coefficients of $g(s,t)$:

  * •

The coefficient of $s$ (with no $t$) is $-8p(p+r)^{2}\cos\gamma$.

  * •

The coefficient of $st^{6}$ is $-8p(p-r)^{2}\cos\gamma$.

  * •

The coefficient of $s^{3}t^{5}$ is $-128q(p-r)r\cos\gamma\sin\gamma$.

Since $p+r$ and $p-r$ cannot simultaneously be zero, the first two
coefficients imply that $p=0$. Since $r>0$, we get that $p-r\neq 0$. Then, the
third coefficient implies that $q=0$. That is, we are in the special case
where $V_{1}=(1,0,0)$, $V_{2}=(0,\cos\gamma,\sin\gamma)$, and $p=q=0$. In this
case, the coefficient of $s^{6}t^{2}$ is $-4\cos\gamma\sin^{2}\gamma$. This
coefficient is never zero, which completes the case of lines parallel to the
$x$-axis.

Note that $\sin\alpha\neq 0$, since otherwise $H$ is parallel to the
$xy$-plane. Similarly, $\sin\beta\neq 0$, since otherwise $H$ is parallel to
the $xz$-plane. We next consider the case where $C_{2}$ is centered at the
origin. That is, we set $p=q=0$. In this case the coefficient of $t^{3}$ (with
no $s$ factor) in the numerator of $g(s,t)$ is

$-32\cos^{2}\alpha\cos\beta\sin^{2}\alpha\sin\beta(\cos^{2}\beta\sin^{2}\alpha+\sin^{2}\beta).$

For this expression to be zero, we must have either $\cos\alpha=0$ or
$\cos\beta=0$. If $\cos\alpha=0$, then $H$ is perpendicular to the $xy$-plane,
so the two circles are perpendicular. If $\cos\beta=0$, then $V_{2}=(0,1,0)$.
Running the program once again gives that the coefficient of $s^{6}t^{6}$ is
$-8\cos\alpha\sin^{2}\alpha$. For this coefficient to vanish, we again require
$\cos\alpha=0$, so the circles are again perpendicular.

Consider the case where $\cos\beta=0$. In this case $\sin\beta=1$, so
$V_{2}=(0,1,0)$. As before, we run the Mathematica program to find
coefficients in the numerator of $g(s,t)$. The coefficient of $s^{5}t^{3}$ is
$-128pr\cos\alpha$. For this coefficient to vanish, we require either $p=0$ or
$\cos\alpha=0$. Consider the case where $\cos\alpha=0$. In this case, the
coefficient of $t^{10}$ (and no factor of $s$) is $-4pr\sin^{2}\alpha$. Since
$\sin\alpha=1$, we get that $p=0$. That is, in either case we have that $p=0$.

We continue the case where $\cos\beta=0$ and $p=0$. We may assume that $q\neq
0$, since we already handled the case where the center of $C_{2}$ is the
origin. The coefficient of $t^{9}$ is $-16r^{2}q\cos\alpha\sin\alpha$. This
coefficient vanishes if and only if $\cos\alpha=0$. In this case
$V_{1}=(0,0,1)$ and running the program again leads to the numerator being
$8q(1+t^{2})s$. Since $q\neq 0$, this numerator does not vanish identically.

Finally, we assume that $\cos\alpha=0$. In this case, $V_{1}=(0,0,1)$, so $H$
is perpendicular to the $xy$-plane. We may assume that $\cos\beta\neq 0$,
since this is the case where $H$ is parallel to the $yz$-plane. As usual, we
consider coefficients of terms in the numerator of $g(s,t)$. The coefficient
of $s^{3}t^{3}$ is $-384pqr\cos\beta\sin\beta$. For this coefficient to
vanish, we require either $p=0$ or $q=0$. When $p=0$, the numerator becomes
$4q(1+t^{2})(-\cos\beta+s^{2}\cos\beta+2s\sin\alpha)$. When $q=0$, the
numerator becomes $-4pr(-1+t^{2})(1+s^{2})\sin\beta$. In either case, the
numerators is zero if and only if $p=q=0$, which is a case we already handled.