# Distinct Distances in $\mathbf{R}^{3}$
Between Quadratic and Orthogonal Curves††thanks: This work was done as part of
the 2021 Polymath Jr program, partially supported by NSF award DMS–2113535.

Toby Aldape, Jingyi Liu, Gregory Pylypovych, Adam Sheffer, Minh-Quan Vo
Department of Mathematics, University of Texas at Austin, TX, USA.
<EMAIL_ADDRESS>of Computer Science, Princeton University, NJ,
USA<EMAIL_ADDRESS>of Mathematics, Massachusetts Institute
of Technology, MA, USA<EMAIL_ADDRESS>of Mathematics, Baruch
College, City University of New York, NY, USA<EMAIL_ADDRESS>Supported by
NSF award DMS-1802059.Department of Mathematics and Computer Science,
University of Science, Vietnam National University, Ho Chi Minh City, Vietnam.
<EMAIL_ADDRESS>
###### Abstract

We study the minimum number of distinct distances between point sets on two
curves in $\mathbf{R}^{3}$. Assume that one curve contains $m$ points and the
other $n$ points. Our main results:

(a) When the curves are conic sections, we characterize all cases where the
number of distances is $O(m+n)$. This includes new constructions for points on
two parabolas, two ellipses, and one ellipse and one hyperbola. In all other
cases, the number of distances is
$\Omega(\min\\{m^{2/3}n^{2/3},m^{2},n^{2}\\})$.

(b) When the curves are not necessarily algebraic but smooth and contained in
perpendicular planes, we characterize all cases where the number of distances
is $O(m+n)$. This includes a surprising new construction of non-algebraic
curves that involve logarithms. In all other cases, the number of distances is
$\Omega(\min\\{m^{2/3}n^{2/3},m^{2},n^{2}\\})$.

##  1 Introduction

Erdős [7] introduced his distinct distances problem in 1946, which has
motivated significant mathematical developments in the fields of discrete
geometry and additive combinatorics. For a given $n$, the problem asks for the
minimum number of distinct distances spanned by $n$ points in
$\mathbf{R}^{2}$. Given a finite point set $\mathcal{P}$, we define
$D(\mathcal{P})$ as the number of distinct distances spanned by pairs of
$\mathcal{P}^{2}$. The distinct distances problem asks for $\min
D(\mathcal{P})$, where the minimum is over all sets
$\mathcal{P}\subset\mathbf{R}^{2}$ of $n$ points. Erdős discovered such a set
$\mathcal{P}$ that satisfies $D(\mathcal{P})=O(n/\sqrt{\log n}).$ The problem
was almost completely resolved by Guth and Katz [8], who proved that every set
$\mathcal{P}$ of $n$ points satisfies $D(\mathcal{P})=\Omega(n/\log n)$.

The above is one of many distinct distances problems, most of which were also
introduced by Erdős (for example, see Sheffer [14]). In a _bipartite_ distinct
distances problem, we have two point sets $\mathcal{P}_{1}$ and
$\mathcal{P}_{2}$ and are interested in the distinct distances spanned by the
pairs of $\mathcal{P}_{1}\times\mathcal{P}_{2}$. We denote this number as
$D(\mathcal{P}_{1},\mathcal{P}_{2})$. In one family of bipartite distinct
distances problems, we assume that there exist curves111Unless stated
otherwise, by _curves_ we refer to constant-complexity irreducible one-
dimensional varieties. See Section 2 for the technical definitions of these
concepts. $C_{1},C_{2}$, such that $\mathcal{P}_{1}\subset C_{1}$ and
$\mathcal{P}_{2}\subset C_{2}$. Purdy conjectured that, when
$|\mathcal{P}_{1}|=|\mathcal{P}_{2}|=n$ and $C_{1},C_{2}$ are lines that are
neither parallel nor orthogonal, $D(\mathcal{P}_{1},\mathcal{P}_{2})$ is
superlinear in $n$ (for example, see [4, Section 5.5]). Pach and de Zeeuw [13]
proved the following more general result.

######  Theorem 1.1.

Let $C_{1}$ and $C_{2}$ be curves in $\mathbf{R}^{2}$ that are not parallel
lines, orthogonal lines, or concentric circles. Let $\mathcal{P}_{1}$ be a set
of $m$ points in $C_{1}$ and let $\mathcal{P}_{2}$ be a set of $n$ points in
$C_{2}$. Then

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

When $C_{1}$ and $C_{2}$ are parallel lines, orthogonal lines, or concentric
circles, we can choose $\mathcal{P}_{1}$ and $\mathcal{P}_{2}$ so that
$D(\mathcal{P}_{1},\mathcal{P}_{2})=\Theta(m+n)$. It is conjectured that the
bound of Theorem 1.1 is not tight. Very recently, Solymosi and Zahl [20]
improved the bound for the case of two lines to
$\Omega(\min\\{m^{3/4}n^{3/4},m^{2},n^{2}\\})$.

We refer to a pair of curves $(C_{1},C_{2})$ as a _configuration_. A
configuration _spans many distances_ if every finite $\mathcal{P}_{1}\subset
C_{1}$ and $\mathcal{P}_{2}\subset C_{2}$ satisfy

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

Theorem 1.1 states that every configuration in $\mathbf{R}^{2}$ spans many
distances, unless it consists of parallel lines, orthogonal lines, or
concentric circles. We say that a configuration _spans few distances_ if for
every $m$ and $n$ there exist $\mathcal{P}_{1}\subset C_{1}$ and
$\mathcal{P}_{2}\subset C_{2}$ such that $|\mathcal{P}_{1}|=m$,
$|\mathcal{P}_{2}|=n$, and $D(\mathcal{P}_{1},\mathcal{P}_{2})=O(m+n)$. By the
above, every two curves in $\mathbf{R}^{2}$ span either few or many distances.
In other words, for any two curves that do not span many distances, there
exist point sets that span a linear number of distinct distances.

(a) Aligned circles.

(b) Perpendicular circles.

Figure 1: Pairs of circles that span few distances.

Mathialagan and Sheffer [12] studied the case where $C_{1}$ and $C_{2}$ are
circles in $\mathbf{R}^{3}$. The _axis_ of a circle $C\subset\mathbf{R}^{3}$
is the line passing through the center of $C$ and orthogonal to the plane that
contains $C$. Two circles are aligned if they share a common axis. See Figure
1(a). In some sense, the case of aligned circles in $\mathbf{R}^{3}$
generalizes the case of concentric circles in $\mathbf{R}^{2}$. In particular,
by adapting the construction for concentric circles in $\mathbf{R}^{2}$, we
get that aligned circles span few distances.

Surprisingly, there exists another configuration of circles in
$\mathbf{R}^{3}$ that spans few distances. Two planes in $\mathbf{R}^{3}$ are
_perpendicular_ if the angle between them is $\pi/2$. Let $H_{1}$ and $H_{2}$
be the planes that contain $C_{1}$ and $C_{2}$, respectively. We say that
circles $C_{1}$ and $C_{2}$ are _perpendicular_ if

  * •

$H_{1}$ contains the center of $C_{2}.$

  * •

$H_{2}$ contains the center of $C_{1}.$

  * •

The planes $H_{1}$ and $H_{2}$ are perpendicular.

See Figure 1(b). Mathialagan and Sheffer [12] proved the following theorem.

######  Theorem 1.2.

Let $C_{1}$ and $C_{2}$ be two circles in $\mathbf{R}^{3}$.
(a) Assume that $C_{1}$ and $C_{2}$ are aligned or perpendicular. Then there
exists a set $\mathcal{P}_{1}\subset C_{1}$ of $m$ points and
$\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(\min\\{m^{2/3}n^{2/3},m^{2},n^{2}\\}).$

Theorem 1.2 states that two circles in $\mathbf{R}^{3}$ span many distances,
unless they are aligned or perpendicular, in which case then they span few
distances.

Our first result: conics. Continuing where Mathialagan and Sheffer stopped, we
establish two new results for distinct distances between curves in
$\mathbf{R}^{3}$. Our first result generalizes Theorem 1.2 to all non-
degenerate conic sections. That is, each curve may now be a circle, a
parabola, a hyperbola, or an ellipse. To state this result, we first need to
define a few new configurations.

The _axis_ of a parabola is the line incident to both the vertex and focus of
that parabola. For example, see Figure 2(a). We say that parabolas
$C_{1},C_{2}$ in $\mathbf{R}^{3}$ are _congruent and perpendicularly opposite_
if they satisfy:

  * •

We can obtain $C_{2}$ by translating and rotating $C_{1}$.

  * •

The parabolas $C_{1}$ and $C_{2}$ have the same axis.

  * •

The planes that contain $C_{1}$ and $C_{2}$ are perpendicular.

  * •

For each parabola, consider the vector from its vertex to its focus. These two
vectors have opposite directions.

For example, see Figure 2(b). For short, we refer to such a pair of parabolas
as _CPO parabolas_.

(a) The axis of a parabola.

(b) CPO Parabolas.

Figure 2: Congruent and perpendicularly opposite (CPO) parabolas.

For $a,m>0$ and $b\neq 0$, such that $m\neq 1$, we consider the configuration

$\displaystyle C_{1}$ $\displaystyle=\left\\{(x,y,z)\in\mathbf{R}^{3}\ :\
mx^{2}+y^{2}=a,\ z=0\right\\}\quad\text{ and }$ (1) $\displaystyle C_{2}$
$\displaystyle=\left\\{(x,y,z)\in\mathbf{R}^{3}\ :\
\frac{m}{m-1}x^{2}+z^{2}=b,\ y=0\right\\}.$ (2)

We note that $C_{1}$ is an ellipse for every $m>0$. On the other hand, $C_{2}$
is an ellipse when $m>1$ and a hyperbola when $0<m<1$. We ignore the case
where $b<0$ and $m>1$, since then $C_{2}$ is empty. Two curves _match_ if they
are obtained by rotating and translating the configuration of (1) and (2), for
some values of $a,b,m$. That is, two ellipses may match (Figure 3(a)) and so
do one ellipse and one hyperbola (Figure 3(b)). We can scale (1) and (2) by
changing the values of $a,b,m$.

(a) Two Ellipses.

(b) Ellipse and Hyperbola.

Figure 3: Matching curves.

######  Theorem 1.3 (Few distances between conics).

Let $C_{1},C_{2}\subset\mathbf{R}^{3}$ be non-degenerate conic sections.
(a) Assume that $C_{1}$ and $C_{2}$ are either perpendicular circles, aligned
circles, CPO parabolas, or matching curves. Then $(C_{1},C_{2})$ spans few
distances.
(b) If $(C_{1},C_{2})$ is not one of the configurations from part (a), then
$(C_{1},C_{2})$ spans many distances.

We note that, as in the cases of $\mathbf{R}^{2}$ and circles in
$\mathbf{R}^{3}$, every conic configuration spans either few or many distinct
distances.

Theorem 1.3 does not include the case where at least one of the curves is a
line. This case is significantly simpler to study, as shown in the proof of
the following result. Throughout this work, the word _cylinder_ refers
specifically to right circular cylinders. That is, cylinders are the surfaces
that are obtained by translating, rotating, and scaling ${\bf
v}(x^{2}+y^{2}-1)$. The _axis_ of a cylinder $S$ is the common axis of all the
circles that are contained in $S$.

######  Lemma 1.4.

Let $\ell\subset\mathbf{R}^{3}$ be a line and let $C\subset\mathbf{R}^{3}$ be
a curve.
(a) If $C$ is contained in a plane orthogonal to $\ell$ or in a cylinder
centered around $\ell$, then $(C,\ell)$ spans few distances.
(b) If $(C,\ell)$ is not one of the configurations from part (a), then
$(C,\ell)$ spans many distances.

For another interesting variant where one point set is on a line, see Bruner
and Sharir [6].

Our second result: curves on perpendicular planes. We say that a curve in
$C\subset\mathbf{R}^{3}$ is _planar_ if there exists a plane that contains
$C$. Theorem 1.1 classifies the pairs of planar curves that span few
distances, when the containing planes are parallel. In particular, the only
configurations that span few distances in this case are parallel lines,
orthogonal lines, and aligned circles. See Lemma 3.1 below.

Our second result classifies all pairs of planar curves that span few
distances when the containing planes are perpendicular.

######  Theorem 1.5 (Few distances between perpendicular planes).

Let $C_{1}$ and $C_{2}$ be curves that are contained in perpendicular planes
in $\mathbf{R}^{3}$.
(a) Assume that $C_{1}$ and $C_{2}$ are one of the following:

  * •

a line $\ell$ and a curve contained in a plane orthogonal to $\ell$,

  * •

parallel lines,

  * •

a line $\ell$ and an ellipse contained in a cylinder centered around $\ell$,

  * •

CPO parabolas,

  * •

matching curves,

  * •

perpendicular circles.

Then $(C_{1},C_{2})$ spans few distances.
(b) If $(C_{1},C_{2})$ is not one of the configuration from part (a), then
$(C_{1},C_{2})$ spans many distances.

The proof of Theorem 1.5 starts by studying sets that are not necessarily
algebraic (see Theorem 6.1). This part of the proof leads to a surprising non-
algebraic configuration that spans few distances. We now describe this
configuration.

Figure 4: The log-circle $x^{2}+y^{2}=2+\ln|x+\frac{1}{2}|$.

For $A,B,D\in\mathbf{R}$, we consider the set in $\mathbf{R}^{3}$ that is
defined by

$x^{2}+y^{2}=D+A\ln|x-B|\quad\text{ and }\quad z=0.$ (3)

We define _log-circles_ to be the sets that are obtained by translating and
rotating the above set, with any $A,B,D\in\mathbf{R}$. For example, see Figure
4. By setting $A=0$, we see that the family of log-circles includes all
standard circles.

For $A,B,D,D^{\prime}\in\mathbf{R}$, consider the two log-circles

$\displaystyle\left\\{(x,y,0)\in\mathbf{R}^{3}\ :\
(x-B)^{2}+y^{2}=D+A\ln|x|\right\\},$
$\displaystyle\left\\{(x,0,z)\in\mathbf{R}^{3}\ :\
x^{2}+z^{2}=D^{\prime}+A\ln|x-B|\right\\}.$ (4)

Figure 5: Matching Log-Circles.

The first log-circle is contained in the $xy$-plane and the second is
contained in the $xz$-plane. That is, these are one-dimensional sets that are
contained in perpendicular planes. We say that two log-circles _match_ if they
can be obtained by rotating, translating, and scaling the above configuration,
for some $A,B,D,D^{\prime}\in\mathbf{R}$. See Figure 5. This is a non-
algebraic generalization of aligned circles.

######  Theorem 1.6.

Let $C_{1}$ and $C_{2}$ be matching log-circles. Then $(C_{1},C_{2})$ spans
few distances.

Our technique. Our analysis begins with the proof of Mathialagan and Sheffer
[12], but significantly generalizes this proof. We now briefly describe one of
the main tools of our analysis.

We say that a set $S\subset\mathbf{R}^{3}$ is an _arc_ if there exists a
smooth bijective map $\gamma:(0,1)\to S$. We also say that $\gamma$ is a
_parameterization_ of $S$. For more information, such as the definition of
smoothness, see Section 2. We extend the properties of spanning many distances
and spanning few distances to pairs of arcs in the straightforward way. That
is, instead of considering point sets of two curves, we consider point sets on
two arcs.

Consider arcs $A_{1},A_{2}\subset\mathbf{R}^{3}$ with respetive
parameterizations $\gamma_{1},\gamma_{2}$. For $s\in(0,1)$, we denote the
three coordinates of $\gamma_{i}(s)$ as $\gamma_{i,x}(s)$, $\gamma_{i,y}(s)$,
and $\gamma_{i,z}(s)$. The _distance function_ of $\gamma_{1}$ and
$\gamma_{2}$ 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}.$
(5)

The distance function receives a point from each arc, using the
parameterizations $\gamma_{1}$ and $\gamma_{2}$. The function returns the
square of the distance between those two points.

A function $f:\mathbf{R}^{2}\to\mathbf{R}$ _is of a special form_ if there
exist open intervals $I_{1},I_{2},I_{3}\subset\mathbf{R}$ and smooth functions
$\phi_{1}:I_{1}\to\mathbf{R},\phi_{2}:I_{2}\to\mathbf{R},\phi_{3}:I_{3}\to\mathbf{R}$
that satisfy the following: For every $s\in I_{1}$ and $t\in I_{2}$, we have
that $\phi_{1}(s)+\phi_{2}(t)\in I_{3}$ and that

$f(s,t)=\phi_{3}(\phi_{1}(s)+\phi_{2}(t)).$ (6)

The following lemma is a generalization of a lemma of Mathialagan and Sheffer
[12], which in turn adapts a result of Raz [15].

######  Lemma 1.7.

Let $A_{1},A_{2}\subset\mathbf{R}^{3}$ be arcs with respective
parametrizations $\gamma_{1},\gamma_{2}$. Let $\rho(s,t)$ be the distance
function of $\gamma_{1}$ and $\gamma_{2}$. Then at least one of the following
holds.
(a) The configuration $(A_{1},A_{2})$ spans many distances.
(b) The function $\rho(s,t)$ is of a special form.

After proving Lemma 1.7, it remains to study when the distance function
$\rho(s,t)$ is of a special form. To do that, we rely on the following
_derivative test_. Here $\rho_{s}$ and $\rho_{t}$ are the first partial
derivative of $\rho$ according to $s$ and $t$, respectively.

######  Lemma 1.8 (Derivative test).

Let $\rho:(0,1)^{2}\to\mathbf{R}$ be a smooth function of a special form, such
that $\rho_{s}\not\equiv 0$ and $\rho_{t}\not\equiv 0$ in every open
neighborhood in $\mathbf{R}^{2}$. Then there exists an open neighborhood in
$\mathbf{R}^{2}$ in which

$\frac{\partial^{2}(\ln|\rho_{s}/\rho_{t}|)}{\partial s\partial t}\equiv 0.$

In our proofs, we study the expression from Lemma 1.8, when $\rho(s,t)$ is the
distance fuction from (5). By using Wolfram Mathematica [18], we show that
this expression is not identically zero in any open neighborhood. Then the
contrapositive of Lemma 1.8 implies that $\rho(s,t)$ is not of a special form.
We must thus be in case (a) of Lemma 1.7.

We also derive the following useful result.

######  Theorem 1.9.

Every pair of curves in $\mathbf{R}^{3}$ spans either few or many distances.

Open problems. One main remaining open problem is to characterize all pairs of
curves in $\mathbf{R}^{3}$ that span few distances. With the above in mind, we
propose the following question:

> _True or false? If two planar curves in $\mathbf{R}^{3}$ span few distances,
> then the planes that contain the curves are either parallel or
> perpendicular._

If the above statement is true, then Theorem 1.5 and Lemma 3.1 characterize
all pairs of _planar_ curves in $\mathbf{R}^{3}$ that span few distances.

Recently, Solymosi and Zahl [20] improved the bound for the number of distinct
distances between two lines from
$\Omega(\min\\{m^{2/3}n^{2/3},m^{2},n^{2}\\})$ to
$\Omega(\min\\{m^{3/4}n^{3/4},m^{2},n^{2}\\})$. It seems plausible that the
bounds of Theorem 1.1, Theorem 1.2, and the current work could also be
improved in a similar way. Such a potential improvement would not replace the
proofs of the current work. Instead, it would be added on top of our proofs,
to amplify the bounds that are obtained.

We also suggest studying distinct distances in $\mathbf{R}^{3}$ between points
on two curves that are not necessarily algebraic. Theorem 6.1 states that,
when the two curves are contained in perpendicular planes, the only cases with
few distances and a curve that is not algebraic are

  * •

one of the curves is a line and the other is contained in a parallel or
perpendicular plane.

  * •

matching log-circles.

  * •

periodic functions that involve a sine or a cosine.

The third bullet point is not covered by Theorem 6.1, since a periodic curve
may not be the union of finitely many arcs and points. In other words, problem
is

> _Are there pairs of curves in $\mathbf{R}^{3}$ that span few distances, are
> not contained in perpendicular plane, not periodic, not lines, and at least
> one is not algebraic?._

Paper structure. Section 2 is a brief survey of basic real algebraic geometry
that is used throughout the paper. Section 3 contains two first distinct
distances results which are easy to prove. We rely on these results in the
following sections. In Section 4, we study functions of special form, which
are also used in the following sections. In Section 5, we study configurations
with few distinct distances. In Section 6, we prove Theorem 1.5. In Section 7,
we prove Theorem 1.3. Finally, in appendices A and B, we go over Mathematica
computations that are required for the proof of Theorem 1.3.

Acknowledgements. We are grateful to Surya Mathialagan for the helpful
conversations and support. We also wish to thank the mentors and staff of the
Polymath Jr program, for making this research project possible.

##  2 Real algebraic geometry preliminaries

In this section, we briefly survey notation and results from real algebraic
geometry. The reader might wish to skim this section and return to it as
necessary.

For references and more information, see for example [3, 9]. For polynomials
$f_{1},\ldots,f_{k}\in\mathbf{R}[x_{1},\ldots,x_{d}]$, the _variety_ defined
by $f_{1},\ldots,f_{k}$ is

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

We say that a set $U\subset\mathbf{R}^{d}$ is a variety if there exist
$f_{1},\ldots,f_{k}\in\mathbf{R}[x_{1},\ldots,x_{d}]$ such that $U={\bf
v}(f_{1},\ldots,f_{k})$. While not true over some other fields, in
$\mathbf{R}^{d}$ every variety can be defined using a single polynomial. A
variety $U$ is _irreducible_ if there do not exist two varieties
$U_{1},U_{2}\subsetneq U$ such that $U=U_{1}\cup U_{2}$. The _dimension_ of an
irreducible variety $U$, denoted $\dim U$, is the largest integer $d_{U}$ for
which there exist non-empty irreducible varieties
$U_{0},U_{1},\ldots,U_{d_{U}}$ such that

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

We now mention two classic results about intersections of varieties in
$\mathbf{R}^{d}$.

######  Theorem 2.1 (Bezout’s theorem).

Let $f$ and $g$ be polynomials in $\mathbf{R}[x,y]$ of degrees $k_{f}$ and
$k_{g}$, respectively. If $f$ and $g$ do not have common factors then
$\mathbf{V}(f)\cap\mathbf{V}(g)$ consists of at most $k_{f}\cdot k_{g}$
points.

######  Theorem 2.2 (Milnor–Thom [11, 21]).

Let $f_{1},...,f_{m}\in\mathbf{R}[x_{1},...,x_{d}]$ be of degree at most $k$.
Then the number of connected components of $\mathbf{V}(f_{1},...,f_{m})$ is at
most

$k(2k-1)^{d}.$

We observe the following simple corollary of Theorem 2.2.

######  Corollary 2.3.

Let $C\subset\mathbf{R}^{3}$ be a curve and let $U\subset\mathbf{R}^{3}$ be a
variety. If $C\cap X$ is infinite then $C\subset X$.

###### Proof.

We set $W=C\cap U$ and assume that $W$ is infinite. By definition, $W$ is a
variety. If $\dim W=0$, then this variety has infinitely many connected
components. Since this contradicts Theorem 2.2, we have that $\dim W\geq 1$.
Since $C$ is irreducible and one-dimensional, we conclude that $C=W\subset X$.
∎

Unlike in $\mathbf{C}^{d}$, there are several non-equivalent definitions for
the degree of a variety in $\mathbf{R}^{d}$. To avoid this issue, we say that
the _complexity_ of a variety $U\subset\mathbf{R}^{d}$ is the minimum integer
$D$ that satisfies the following: There exist $k\leq D$ polynomials
$f_{1},\ldots,f_{k}\in\mathbf{R}[x_{1},\ldots,x_{d}]$, each of degree at most
$D$, such that $U=\mathbf{V}(f_{1},\ldots,f_{k})$. In the past decade, the use
of complexity is becoming more common. For example, see [5, 19].

For the following result, see for example [17, Chapter 4]. In the
$O_{k,d}(\cdot)$-notation, the hidden constant may depend on $d$ and $k$.

######  Theorem 2.4.

Let $U\subset\mathbf{R}^{d}$ be a variety of complexity $k$. Then $U$ is the
union of $O_{k,d}(1)$ irreducible varieties.

We define a _curve_ to be an irreducible constant-complexity variety of
dimension one. In Theorem 1.3 and Theorem 1.5, we implicitly consider sets of
$m$ and $n$ points that determine
$\Omega(\min\\{m^{2/3}n^{2/3},m^{2},n^{2}\\})$ distinct distances. In this
context, the constant-complexity of the curves means that $m$ and $n$ may be
assumed to be arbitrarily large with respect to the complexities of the
curves. The hidden constant in the $\Omega(\cdot)$-notation may depend on the
complexities of the curves.

Let $S\subset\mathbf{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\mathbf{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\mathbf{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}$.

A _standard projection_ is a linear map $\pi:\mathbf{R}^{n}\to\mathbf{R}^{m}$
that keeps the first $m$ out of $n$ coordinates. While the projection of a
variety might not be a variety, it has other nice properties.

######  Theorem 2.5.

Let $U\subset\mathbf{R}^{n}$ be a variety of dimension $d$ and let
$\pi:\mathbf{R}^{n}\to\mathbf{R}^{m}$ be a standard projection. Then
(a) The projection $\pi(U)$ is a semi-algebraic set of dimension at most $d$.
(b) Let $d^{\prime}=\dim\pi(U)$. Then there exists a variety
$W\subset\mathbf{R}^{m}$ of dimension smaller than $d^{\prime}$ that satisfies
the following: For every $p\in\pi(U)\setminus W$, the set $\pi^{-1}(p)\cap U$
is semi-algebraic of dimension at most $d-d^{\prime}$.

For part (a), see for example [2, Section 11.3]. For part (b), see for example
[1, Section 7.1].

We say that a function $f:\mathbf{R}^{d}\to\mathbf{R}$ is _smooth_ if all its
partial derivative of all orders exist. We think of a function
$g:\mathbf{R}^{d}\to\mathbf{R}^{e}$ as $e$ separate functions from
$\mathbf{R}^{d}$ to $\mathbf{R}$ and say that $g$ is _smooth_ if each of these
$e$ separate components is smooth.

We recall that $S\subset\mathbf{R}^{3}$ is an _arc_ if there exists a smooth
map $\gamma:(0,1)\to S$. We say that $\gamma$ is a _parameterization_ of $S$.
For the following lemma, see for example [15].222We do not fully describe the
simple proof of this lemma, since it would require many additional
definitions. Briefly: $C$ has a finite number of singular points. After
removing these points, each connected component is diffeomorphic either to
$\mathbf{R}$ or to $S^{1}$. Similarly, an arc is more commonly known as a
connected one-dimensional smooth manifold.

######  Lemma 2.6.

Let $C\subset\mathbf{R}^{n}$ be a curve. Then $C$ is the union of finitely
many arcs and points.

##  3 First distinct distances bounds

In this section, we study two first distinct distances results. These have
shorter proofs and do not rely on involved tools such as Lemma 1.7.

######  Lemma 3.1.

Let $C_{1},C_{2}\subset\mathbf{R}^{3}$ be planar curves that are contained in
parallel planes.
(a) If $C_{1}$ and $C_{2}$ are parallel lines, orthogonal lines, or aligned
circles, then $(C_{1},C_{2})$ spans few distances.
(b) If $(C_{1},C_{2})$ is not one of the configurations from part (a), then
$(C_{1},C_{2})$ spans many distances.

###### Proof.

(a) To see that parallel lines, orthogonal lines, and aligned circles span few
distances, see for example [12].

(b) Let $H_{1}$ and $H_{2}$ be the planes that contain $C_{1}$ and $C_{2}$,
respectively. We rotate and translate $\mathbf{R}^{3}$ so that $H_{1}$ becomes
the plane $\mathbf{V}(z)$. Then there exists $d\in\mathbf{R}$ such that
$H_{2}=\mathbf{V}(z-d)$. Note that rotations and translations do not affect
distances.

We consider the points $a=(a_{x},a_{y},0)\in C_{1}$ and $b=(b_{x},b_{y},d)\in
C_{2}$. We also consider the standard projection $\pi(x,y,z)=(x,y)$. The
square of the distance between $a$ and $b$ equals to the square of the
distance between $\pi(a)$ and $\pi(b)$ plus $d^{2}$. Since the squares of all
the distances change by the same amount, we get that
$D(\mathcal{P}_{1},\mathcal{P}_{2})=D(\pi(\mathcal{P}_{1}),\pi(\mathcal{P}_{2}))$.

By Theorem 1.1, $(\pi(C_{1}),\pi(C_{2}))$ spans few distances if they are
parallel lines, orthogonal lines, or concentric circles. Otherwise,
$(\pi(C_{1}),\pi(C_{2}))$ spans many distances. If $\pi(C_{1})$ and
$\pi(C_{2})$ are parallel or orthogonal lines, so are $C_{1}$ and $C_{2}$. If
$\pi(C_{1})$ and $\pi(C_{2})$ are concentric circles then $C_{1}$ and $C_{2}$
are aligned circles. ∎

We next prove Lemma 1.4. We first recall the statement of this lemma.

Lemma 1.4. _Let $\ell\subset\mathbf{R}^{3}$ be a line and let
$C\subset\mathbf{R}^{3}$ be a curve.
(a) If $C$ is contained in a plane orthogonal to $\ell$ or in a cylinder
centered around $\ell$, then $(C,\ell)$ spans few distances.
(b) If $(C,\ell)$ is not one of the configurations from part (a), then
$(C,\ell)$ spans many distances._

###### Proof.

For part (a), see Lemmas 5.1 and 5.2 below. For part (b), we assume that $C$
is not contained in a plane orthogonal to $\ell$ or in a cylinder centered
around $\ell$. By rotating $\mathbf{R}^{3}$, we may assume that $\ell$ is the
$z$-axis, without changing any distances. We consider a polynomial
$f\in\mathbf{R}[x,y,z]$ such that $\mathbf{V}(f)=C$.

We consider a point $p\in\mathbf{R}^{3}$ and note that there is one circle
$C_{p}$ that contains $p$ and has axis $\ell$. Moving $p$ along $C_{p}$ does
not change the distances between $p$ and the points of $\ell$. In particular,
we may replace $p=(p_{x},p_{y},p_{z})$ with the point
$\left(\sqrt{p_{x}^{2}+p_{y}^{2}},0,p_{z}\right)$. Thus, the distances between
$\ell$ and $C$ are the same as the distances between $\ell$ and the set

$C^{\prime}=\\{(\sqrt{x^{2}+y^{2}},0,z)\ :\ f(x,y,z)=0\\}.$

Since $\ell$ and $C^{\prime}$ are contained in the plane $\mathbf{V}(y)$, we
wish to apply Theorem 1.1. However, $C^{\prime}$ may not be a curve.

We denote the coordinates of $\mathbf{R}^{4}$ as $X,Y,Z,W$ and consider the
variety

$U=\mathbf{V}(W^{2}-X^{2}-Y^{2},f(X,Y,Z))\subset\mathbf{R}^{4}.$

Since $f$ defines a curve in $\mathbf{R}^{3}$ and $X,Y$ determine $W$ up to a
sign, we get that $\dim U=1$.

We define the standard projection $\pi_{2}(X,Y,Z,W)=(Z,W)$. We note that a
point $(x,0,z)$ is in $C^{\prime}$ if and only if the points $(z,\pm x)$ are
in $\pi_{2}(U)$. Since $C$ is not contained in a plane orthogonal to $\ell$,
Corollary 2.3 implies that $C$ intersects such a plane in $O(1)$ points. Thus,
every point of $\pi_{2}(U)$ has $O(1)$ points of $U$ projected to it. Theorem
2.5 implies that $\overline{C^{\prime}}$ is a one-dimensional variety. Since
$\overline{C^{\prime}}$ may be reducible, it may not be a curve.

Since $C$ contains $O(1)$ points from every plane orthogonal to $\ell$, we get
that $\overline{C^{\prime}}$ does not contain lines that are orthogonal to
$\ell$. Since $C$ is not contained in cylinders that are centered at $\ell$,
Corollary 2.3 implies that $C$ intersects such a cylinder in $O(1)$ points.
This in turn implies that $\overline{C^{\prime}}$ does not contain lines that
are parallel to $\ell$.

Consider a set $\mathcal{P}$ of $n$ points on $C$. Let $\mathcal{P}^{\prime}$
be the set of points of $\mathcal{P}$ after taking them to $C^{\prime}$ as
described above. Since $O(1)$ points of $C$ are taken to the same point of
$C^{\prime}$, we have that $|\mathcal{P}^{\prime}|=\Theta(n)$. Theorem 2.4
implies that $C^{\prime}$ consists of finitely many components. Thus, there
exists an irreducible component of $C^{\prime}$ that contains $\Theta(n)$
points of $\mathcal{P}^{\prime}$. We complete the proof by separately applying
Theorem 1.1 with $\ell$ and each of the one-dimensional irreducible components
of $C^{\prime}$.

∎

##  4 Functions of a special form

In this section, we study functions of a special form, as defined in (6). We
begin by proving Lemma 1.8, which provides a test for checking whether a
function is not of a special form. We first recall the statement of this
lemma, where $\rho_{s}$ is the first partial derivative of $\rho$ with respect
to $s$.

Lemma 1.8. _Let $\rho:(0,1)^{2}\to\mathbf{R}$ be a smooth function of a
special form, such that $\rho_{s}\not\equiv 0$ and $\rho_{t}\not\equiv 0$ in
every open neighborhood in $\mathbf{R}^{2}$. Then there exists an open
neighborhood in $\mathbf{R}^{2}$ in which _

$\frac{\partial^{2}(\ln|\rho_{s}/\rho_{t}|)}{\partial s\partial t}\equiv 0.$

###### Proof.

By definition, there exist open intervals $I_{1},I_{2},I_{3}$ and smooth
$\phi_{1}:I_{1}\to\mathbf{R},\phi_{2}:I_{2}\to\mathbf{R}$,
$\phi_{3}:I_{3}\to\mathbf{R}$, such that every $(s,t)\in I_{1}\times I_{2}$
satisfies

$\rho(s,t)=\phi_{3}(\phi_{1}(s)+\phi_{2}(t)).$

By the assumptions on $\rho_{s}$ and $\rho_{t}$, there exists an open set
$U\subset I_{1}\times I_{2}$ in which $\rho_{s}$ and $\rho_{t}$ are never
zero. In $U$, we have that

$\displaystyle\rho_{s}$
$\displaystyle=\frac{\partial[\phi_{3}(\phi_{1}(s)+\phi_{2}(t))]}{\partial
s}=\phi_{3}^{\prime}(\phi_{1}(s)+\phi_{2}(t))\cdot\phi_{1}^{\prime}(s),$
$\displaystyle\rho_{t}$
$\displaystyle=\frac{\partial[\phi_{3}(\phi_{1}(s)+\phi_{2}(t))]}{\partial
t}=\phi_{3}^{\prime}(\phi_{1}(s)+\phi_{2}(t))\cdot\phi_{2}^{\prime}(t).$

With these equations, we get that

$\displaystyle\frac{\partial^{2}(\ln|\rho_{s}/\rho_{t}|)}{\partial s\partial
t}=\frac{\partial^{2}(\ln|\phi_{1}^{\prime}(s)/\phi_{2}^{\prime}(t)|)}{\partial
s\partial
t}=\frac{\partial^{2}(\ln|\phi_{1}^{\prime}(s)|-\ln|\phi_{2}^{\prime}(t)|)}{\partial
s\partial t}=0,$

for all $(s,t)\in U.$ ∎

We next use special forms to study configurations that span few distances.
Recall that the distance function of two arc parameterizations is defined in
(5).

######  Lemma 4.1 (Special form implies few distances).

Let $A_{1},A_{2}\subset\mathbf{R}^{3}$ be arcs and let $\gamma_{1},\gamma_{2}$
be parameterizations of those arcs, respectively. If the distance function of
$\gamma_{1}$ and $\gamma_{2}$ is of a special form then $(A_{1},A_{2})$ spans
few distances.

###### Proof.

Let $\rho(s,t)$ be the distance function of $\gamma_{1}$ and $\gamma_{2}$. Let
$I_{1},I_{2},I_{3}\subseteq(0,1)$ and $\phi_{1},\phi_{2},\phi_{3}$ be as in
the definition of $\rho(s,t)$ having a special form. By definition,
$\phi_{1}(I_{1})$ and $\phi(I_{2})$ are nonempty intervals in $\mathbf{R}$. We
first consider the case where $\phi_{1}(I_{1})$ is a single point. In this
case, the choice of point from $\gamma_{1}(I_{1})$ does not affect the
distance with any point of $\gamma_{2}(I_{2})$. Thus, the number of distinct
distances between $m$ points from $\gamma_{1}(I_{1})$ and $n$ points from
$\gamma_{2}(I_{2})$ is at most $n$. A symmetric argument shows that, when
$\phi_{2}(I_{2})$ is a single point, there are at most $m$ distances.

It remains to consider the case where both $\phi_{1}(I_{1})$ and
$\phi_{2}(I_{2})$ are intervals with infinitely many points. Let
$p\in\phi_{1}(I_{1})$ and $q\in\phi_{2}(I_{2})$ be interior points of those
intervals. Let ${\varepsilon}>0$ be sufficiently small, as described below.
For $1\leq i\leq m$, we set $x_{i}=p+i{\varepsilon}$. For $1\leq i\leq n$, we
set $x^{\prime}_{i}=q+i{\varepsilon}$. When ${\varepsilon}$ is sufficiently
small, we have that $x_{1},\ldots,x_{m}\in\phi_{1}(I_{1})$ and
$x^{\prime}_{1},\ldots,x^{\prime}_{n}\in\phi_{2}(I_{2})$. Let $s_{i}\in I_{1}$
satisfy $\phi_{1}(s_{i})=x_{i}$ and let $t_{j}\in I_{2}$ satisfy
$\phi_{2}(t_{j})=x^{\prime}_{j}$. Then

$\displaystyle\rho(s_{i},t_{j})=\phi_{3}(\phi_{1}(s_{i})_{+}\phi_{2}(t_{j}))=\phi_{3}(x_{i}+x^{\prime}_{j})=\phi_{3}((x+x^{\prime})+(i+j){\varepsilon}).$

We note that the expression $i+j$ has $m+n-1$ distinct values. This implies
that $\rho(s_{i},t_{j})$ has at most $m+n-1$ distinct values. We conclude that
the sets $\mathcal{P}_{1}=\\{x_{1},\ldots,x_{m}\\}\subset A_{1}$ and
$\mathcal{P}_{2}=\\{x_{1}^{\prime},\ldots,x_{n}^{\prime}\\}\subset A_{2}$ span
$O(m+n)$ distinct distances. ∎

The converse of Lemma 4.1 holds when the two arcs are contained in curves.

######  Lemma 4.2.

Let $A_{1},A_{2}\subset\mathbf{R}^{3}$ be arcs and let $\gamma_{1},\gamma_{2}$
be parameterizations of those arcs, respectively. Let $C_{1}$ and $C_{2}$ be
curves that contain $A_{1}$ and $A_{2}$, respectively. If the distance
function of $\gamma_{1}$ and $\gamma_{2}$ is not of a special form then
$(A_{1},A_{2})$ spans many distances.

To prove Lemma 4.2, we rely on the following result of Raz, Sharir, de Zeeuw
[16, Sections 2.1 and 2.3]. See also Raz [15, Lemma 2.4].

######  Theorem 4.3.

Let $F\in\mathbf{R}[x,y,z]$ be a constant-degree irreducible polynomial, such
that all first partial derivatives of $F$ are not identically zero. Then at
least one of the following two cases holds.
(i) For all $A,B\subset\mathbf{R}$ with $|A|=m$ and $|B|=n$, we have that

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

(ii) There exists a one-dimensional variety $Z^{*}\subset\mathbf{V}(F)$ of
degree $O(1)$ that satisfies the following. For every
$p\in\mathbf{V}(F)\setminus Z^{*}$, there exist open intervals
$I_{1},I_{2},I_{3}\subset\mathbf{R}$ and real-analytic functions
$\varphi_{1},\varphi_{2},\varphi_{3}$ with analytic inverses such that $p\in
I_{1}\times I_{2}\times I_{3}$ and for all $(x,y,z)\in I_{1}\times I_{2}\times
I_{3}$ we have

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

###### Proof of Lemma 4.2..

Assume that the distance function of $\gamma_{1}$ and $\gamma_{2}$ is not of a
special form. We rotate $\mathbf{R}^{3}$ so that $C_{1}$ and $C_{2}$ are not
contained in planes that are parallel to the $yz$-plane. A rotation does not
change distances in $\mathbf{R}^{3}$. This in turn implies that a rotation
does not change whether a distance function has a special form or not.

Since every variety in $\mathbf{R}^{d}$ is the zero set of a single
polynomial, there exist $f_{1},f_{2}\in\mathbf{R}[x,y,z]$ such that
$C_{1}=\mathbf{V}(f_{1})$ and $C_{2}=\mathbf{V}(f_{2})$. We 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\mathbf{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.$

When considering $p_{x},p_{y},p_{z},q_{x},q_{y},q_{z},\Delta$ as the
coordinates of a seven-dimensional space $\mathbf{R}^{7}$, the above system
defines a variety $U\subset\mathbf{R}^{7}$. Since $f_{1}$ defines a curve, the
first equation of the system defines a one-dimensional set of values for
$p_{x},p_{y},p_{z}$. Similarly, the second equation of the system defines a
one-dimensional set of values for $q_{x},q_{y},q_{z}$. When the values of
$p_{x},p_{y},p_{z},q_{x},q_{y},q_{z}$ are fixed, the third equation uniquely
defines $\Delta$. This implies that $\dim(U)=2$.

Let $\pi:\mathbf{R}^{7}\to\mathbf{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).$

We claim that every point of $U_{3}$ has $O(1)$ points of $U$ projected to it.
Indeed, recall that $C_{1}$ is not contained in planes parallel to the
$yz$-plane. Theorem 2.2 implies that $C_{1}$ intersects such a plane in $O(1)$
points. That is, the number of points on $C_{1}$ that have the same
$x$-coordinate is $O(1)$. A symmetric argument holds for $C_{2}$. Thus, every
triple $(p_{x},q_{x},\Delta)\in U_{3}$ corresponds to $O(1)$ points of $U$.
Since $\dim U=2$, Theorem 2.5 implies that $U_{3}$ is a semi-algebraic set of
dimension two. Let $F\in\mathbf{R}[p_{x},q_{x},\Delta]$ satisfy
$\mathbf{V}(F)=\overline{U_{3}}$.

Studying $F$. We now prove that $F$ involves all three variables
$p_{x},q_{x},\Delta$. Recall that a fixed $p_{x}$ corresponds to $O(1)$ points
$p\in C_{1}$ and a fixed $q_{x}$ corresponds to $O(1)$ points $q\in C_{2}$.
This implies that, for fixed $p_{x},q_{x}$, there are $O(1)$ values for
$\Delta$ that satisfy $(p_{x},q_{x},\Delta)\in U_{3}$. In other words, every
line that is parallel to the $\Delta$-axis intersects $U_{3}$ in $O(1)$
points. Thus, $\Delta$ appears in the definition of $F$.

If $C_{1}$ is a circle and $C_{2}$ is the axis of $C_{1}$ then $\rho(s,t)$
does not depend on $s$. This implies that $\rho(s,t)$ is of a special form.
The same happens when switching the roles of $C_{1}$ and $C_{2}$. Since the
distance function of $\gamma_{1}$ and $\gamma_{2}$ is not of a special form,
$C_{1}$ and $C_{2}$ are not a circle and its axis.

Consider fixed values for $p_{x}$ and $\Delta$, such that infinitely many
values of $q_{x}$ satisfy $(p_{x},q_{x},\Delta)\in U_{3}$. Since $p_{x}$
corresponds to $O(1)$ points $p\in C_{1}$, there exists such a point $p$ that
is at distance $\sqrt{\Delta}$ from infinitely many points $q\in C_{2}$. Let
$S$ be the sphere of radius $\sqrt{\Delta}$ centered at $p$. The above implies
that $C_{2}$ has an infinite intersection with $S$. Corollary 2.3 implies that
$C_{2}\subset S$. Assume that there exist
$(p_{x}^{\prime},\Delta^{\prime})\neq(p_{x},\Delta)$ such that infinitely many
values of $q_{x}$ satisfy $(p_{x}^{\prime},q_{x},\Delta^{\prime})\in U_{3}$.
Then there exists $p^{\prime}$ with $x$-coordinate $p_{x}^{\prime}$ such that
the sphere $S^{\prime}$ of radius $\sqrt{\Delta^{\prime}}$ centered at
$p^{\prime}$ contains $C_{2}$. We have that $p_{x}\neq p_{x}^{\prime}$, since
otherwise $S\cap S^{\prime}=\emptyset$. Thus, $C_{2}$ is the circle $S\cap
S^{\prime}$.

Continuing the preceding paragraph, we next assume that there exist infinitely
many pairs $(p_{x},\Delta)$, each having infinitely values of $q_{x}$ that
satisfy $(p_{x},q_{x},\Delta)\in U_{3}$. As before, that means that $C_{2}$ is
a circle and that every pair has $(p_{x},\Delta)$ has a distinct $p_{x}$. For
a corresponding point $p\in C_{1}$ to be equidistant from infinitely many
points of $C_{2}$, the point $p$ must be on the axis of $C_{2}$. That is,
infinitely many points of $C_{1}$ are on the axis of $C_{2}$. Corollary 2.3
implies that $C_{1}$ is the axis of $C_{2}$. This is contradicts the above
statement that $C_{1}$ and $C_{2}$ are not a circle and its axis. We conclude
that the number of pairs $(p_{x},\Delta)$ that satisfy the above is finite. In
other words, $U_{3}$ contains a $O(1)$ lines that are parallel to the
$q_{x}$-axis. Thus, $q_{x}$ appears in the definition of $F$. A symmetric
arguments holds for $p_{x}$.

Since all three coordinates participate in the definition of $F$, no first
partial derivative of $F$ is identically zero. We may thus apply Theorem 4.3
with $F$. We partition the remainder of the proof according to the case of the
theorem that holds.

Case (i). We first assume that case (i) of Theorem 4.3 holds. Let
$\mathcal{P}_{1}\subset A_{1}$ and $\mathcal{P}_{2}\subset A_{2}$ satisfy
$|\mathcal{P}_{1}|=m$ and $|\mathcal{P}_{2}|=n$. Let $\mathcal{P}_{1,x}$ and
$\mathcal{P}_{2,x}$ be sets of the $x$-coordinates of the points of
$\mathcal{P}_{1}$ and $\mathcal{P}_{2}$, respectively. We set

$\displaystyle Q$
$\displaystyle=\left\\{(a,a^{\prime},b,b^{\prime})\in\mathcal{P}_{1}^{2}\times\mathcal{P}_{2}^{2}\mid\exists\Delta\in\mathbf{R}:F(a_{x},b_{x},\Delta)=F(a_{x}^{\prime},b_{x}^{\prime},\Delta)=0\right\\},$
$\displaystyle Q_{x}$
$\displaystyle=\left\\{(a_{x},a_{x}^{\prime},b_{x},b_{x}^{\prime})\in\mathcal{P}_{1,x}^{2}\times\mathcal{P}_{2,x}^{2}\mid\exists\Delta\in\mathbf{R}:F(a_{x},b_{x},\Delta)=F(a_{x}^{\prime},b_{x}^{\prime},\Delta)=0\right\\}.$

Case (i) of Theorem 4.3 implies that

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

Since every $x$-coordinate appears $O(1)$ times in $C_{1}$ and $C_{2}$, a
quadruple $(a_{x},a_{x}^{\prime},b_{x},b_{x}^{\prime})\in Q_{x}$ corresponds
to $O(1)$ quadruples of $Q$. This in turn implies that

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

For $\delta\in\mathbf{R}$, let $m_{\delta}$ be the number of pairs in
$\mathcal{P}_{1}\times\mathcal{P}_{2}$ that span the distance $\delta$. The
number of quadruples $(a,a^{\prime},b,b^{\prime})\in Q$ that satisfy
$|ab|=|a^{\prime}b^{\prime}|=\delta$ is $m_{\delta}^{2}$. Thus
$|Q|=\sum_{\delta}m_{\delta}^{2}.$ We also note that every pair of
$\mathcal{P}_{1}\times\mathcal{P}_{2}$ contributes to exactly one
$m_{\delta}$. This implies that $\sum_{\delta}m_{\delta}=mn$. Combining these
observations with the Cauchy–Schwarz inequality leads to

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

Combining this with (7) 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).$

In other words, $A_{1}$ and $A_{2}$ span many distances.

Case (ii). We now assume that case (ii) of Theorem 4.3 holds. We set

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

By definition, $Z$ is contained in $U_{3}$. It is a continuous two-dimensional
semi-algebraic set. Intuitively, we can imagine $Z$ a patch of the surface
$U_{3}$.

Let $Z^{*}$ be as described in case (ii) of Theorem 4.3. We consider $v\in
Z\setminus Z^{*}$. Such a $v$ exists, since $Z$ is two-dimensional while
$Z^{*}$ is one-dimensional. By Theorem 4.3, there exist open intervals
$I_{1},I_{2},I_{3}\subset\mathbf{R}$ and real-analytic
$\phi_{1}:I_{1}\to\mathbf{R},$
$\phi_{2}:I_{2}\to\mathbf{R},\phi_{3}:I_{3}\to\mathbf{R}$ with analytic
inverses such that $v\in I_{1}\times I_{2}\times I_{3}$ and every
$(p_{x},q_{x},\Delta)\in I_{1}\times I_{2}\times I_{3}$ satisfies

$(p_{x},q_{x},\Delta)\in{\mathbf{V}}(F)\quad\text{ if and only if
}\quad\phi_{1}(p_{x})+\phi_{2}(q_{x})+\phi_{3}(\Delta)=0.$

Set $\phi_{1}^{\prime}(p_{x})=-\phi_{1}(p_{x})$ and
$\phi_{2}^{\prime}(q_{x})=-\phi_{2}(q_{x})$. Then, we can rearrange
$\phi_{1}(p_{x})+\phi_{2}(q_{x})+\phi_{3}(\Delta)=0$ as
$\Delta=\phi_{3}^{-1}(\phi_{1}^{\prime}(p_{x})+\phi_{2}^{\prime}(q_{x}))$.
Combining this with the above leads to

$(p_{x},q_{x},\Delta)\in{\mathbf{V}}(F)\quad\text{ if and only if
}\quad\Delta=\phi_{3}^{-1}(\phi_{1}^{\prime}(p_{x})+\phi_{2}^{\prime}(q_{x})).$
(8)

We write $v=(p_{x,0},q_{x,0},\Delta_{0})$. Since $v\in Z$, there exist
$s_{0},t_{0}\in(0,1)$ that satisfy

$(\gamma_{1,x}(s_{0}),\gamma_{2,x}(t_{0}),\rho(s_{0},t_{0}))=(p_{x,0},q_{x,0},\Delta_{0}).$

There exist open intervals $S\subset(0,1)$ and $T\subset(0,1)$ such that
$s_{0}\in S$, $t_{0}\in T$, $\gamma_{1,x}(S)\subset I_{1}$,
$\gamma_{2,x}(T)\subset I_{2}$, and $\rho(S,T)\subset I_{3}.$ Consider $s\in
S$ and $t\in T$ such that $\rho(s,t)=\Delta$. Then
$(\gamma_{1,x}(s),\gamma_{2,x}(t),\Delta)\in\mathbf{V}(F)$. Combining this
with (8) implies that

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

Since this holds for every $s\in S$ and $t\in T$, we conclude that $\rho(s,t)$
is of a special form. This contradiction implies that Case (ii) cannot occur.
∎

By combining Lemma 4.1 and Lemma 4.2, we obtain Theorem 1.9. We first recall
the statement of this theorem.

Theorem 1.9. _Every pair of curves in $\mathbf{R}^{3}$ spans either few or
many distances._

###### Proof.

Consider two curves $C_{1},C_{2}\subset\mathbf{R}^{3}$. By Lemma 2.6, each
curve is the union of $O(1)$ arcs and points. We first assume that there exist
two arcs, one from each curve, with parameterizations whose distance function
is of a special form. In this case, Lemma 4.1 states that the two arcs span
few distances. This in turn implies that $(C_{1},C_{2})$ spans few distances.

We next assume that no two arcs of $C_{1}$ and $C_{2}$ have a distance
function of a special form. 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. Since
$C_{1}$ is the union of $O(1)$ arcs and points, there exists an arc of
$A_{1}\subset C_{1}$ that contains $\Theta(m)$ points of $\mathcal{P}_{1}$.
Similarly, there exists an arc of $A_{2}\subset C_{2}$ that contains
$\Theta(n)$ points of $\mathcal{P}_{2}$. Lemma 1.7 states that

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

∎

##  5 Configurations that span few distances

In this section, we study configurations that span few distances. To show that
a configuration spans few distances, we show that the distance function is of
a special form and then apply Lemma 4.1. Recall that, in this work, we only
consider right circular cylinders.

######  Lemma 5.1.

Let $\ell\subset\mathbf{R}^{3}$ be a line in $\mathbf{R}^{3}$ and let $C$ be a
curve contained in a cylinder centered around $\ell$. Then $(\ell,C)$ spans
few distances.

###### Proof.

We translate and rotate the space so that $\ell$ becomes the $z$-axis. We then
perform a uniform scaling of $\mathbf{R}^{3}$ so that $C$ is contained in a
cylinder of radius one around $\ell$. These transformation do not change the
number of distances between point sets. We first assume that all points of $C$
have the same $z$-coordinate. In this case, $C$ it must be a circle contained
in a plane orthogonal to $\ell$. A fixed point of $\ell$ spans the same
distance with every point of $C$. Thus, the number of distinct distances
between $m$ points on $\ell$ and $n$ points on $C$ is at most $m$.

Next, we assume that $C$ is not a circle in a plane orthogonal to $\ell$. In
this case, the set of $z$-coordinates of points of $C$ is an infinite closed
interval $[z_{1},z_{2}]\subset\mathbf{R}$. As a parameterization of $\ell$, we
set $\gamma_{1}(s)=(0,0,s)$. For $t\in(z_{1},z_{2})$, the distance function
between the point $(0,0,s)$ and a point of $C$ with $z$-coordinate $t$ is

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

Let $A$ be an arc of $C$ that is parameterized by its $z$-coordinate. Since
$\rho(s,t)$ is of a special form, Lemma 4.1 implies that $A$ and $\ell$ span
few distances. ∎

In Lemma 5.1, it is not difficult to replace $C$ with any set that contains an
arc. That is, Lemma 5.1 can be extended to non-algebraic sets.

######  Lemma 5.2.

Let $L\subset\mathbf{R}^{3}$ be a line and let $C$ be a curve contained in a
plane orthogonal to $L$. Then $(L,C)$ spans few distances.

###### Proof.

We rotate and translate the space so that $\ell$ becomes the $z$-axis and $C$
is contained in the $xy$-plane. These transformations do not change distances
between points. We define the _radial coordinate_ of a point
$(x,y,z)\in\mathbf{R}^{3}$ as $\sqrt{x^{2}+y^{2}}$. If all the points of $C$
have the same radial coordinate then $C$ is a circle with axis $\ell$. This
case is covered by Lemma 5.1.

Next, we assume that the points of $C$ have more than one radial coordinate.
In this case, the set of radial coordinates is a closed infinite interval
$[r_{1},r_{2}]$. As a parameterization of $\ell$, we set
$\gamma_{1}(s)=(0,0,s)$. For $t\in(r_{1},r_{2})$, the distance function
between the point $(0,0,s)$ and a point of $C$ with radial coordinate $t$ is

$\rho(s,t)=s^{2}+t^{2}.$

Let $A$ be an arc of $C$ that is parameterized by its radial coordinate. Since
$\rho(s,t)$ is of a special form, Lemma 4.1 implies that $A$ and $\ell$ span
few distances. ∎

As with Lemma 5.1, it is not difficult to extend Lemma 5.2 to non-algebraic
sets.

######  Lemma 5.3.

Let $C_{1}$ and $C_{2}$ be aligned circles. Then $(C_{1},C_{2})$ spans few
distances.

###### Proof.

We translate, rotate, and scale $\mathbf{R}^{3}$ so that the axis of both
circles is the $z$-axis, $C_{1}$ is contained in the $xy$-plane, and $C_{2}$
is contained in the plane $\mathbf{V}(z-1)$. Such transformation do not change
the number of distances between two point sets. Then, $C_{1}$ can be
parameterized as $\gamma_{1}(s)=(r_{1}\cos 2\pi s,r_{1}\sin 2\pi s,0)$ and
$C_{2}$ as $\gamma_{2}(t)=(r_{2}\cos 2\pi t,r_{2}\sin 2\pi t,1)$, where
$s,t\in(0,1)$. The distance function of these parametrizations is

$\displaystyle\rho(s,t)$ $\displaystyle=(r_{1}\cos 2\pi s-r_{2}\cos 2\pi
t)^{2}+(r_{1}\sin 2\pi s-r_{2}\sin 2\pi t)^{2}+1$
$\displaystyle=r_{1}^{2}+r_{2}^{2}-2r_{1}r_{2}(\cos 2\pi s\cdot\cos 2\pi
t+\sin 2\pi s\cdot\sin 2\pi t)+1$
$\displaystyle=(1+r_{1}^{2}+r_{2}^{2})-2r_{1}r_{2}\cos 2\pi(s-t).$

Since $\rho(s,t)$ is of a special form, Lemma 4.1 implies that $C_{1}$ and
$C_{2}$ span few distances. ∎

The case of perpendicular circles is subsumed by the case of log-circles
below. For explicit constructions of point sets on aligned and perpendicular
circles, see Mathialagan and Sheffer [12].

######  Lemma 5.4.

Let $C_{1}$ and $C_{2}$ be CPO parabolas. Then $(C_{1},C_{2})$ spans few
distances.

###### Proof.

We translate, rotate, and perform a uniform scaling of $\mathbf{R}^{3}$ so
that $C_{1}$ becomes the parabola ${\mathbf{V}}(y-x^{2},z)$. Such
transformations do not affect the number of distinct distances between two
sets. Since these are CPO parabolas, there exists $q\in\mathbf{R}$ such that
$C_{2}={\mathbf{V}}(y-q+z^{2},x)$. We parameterize $C_{1}$ as
$\gamma_{1}(s)=(s,s^{2},0)$ and $C_{2}$ as $\gamma_{2}(t)=(0,q-t^{2},t)$.
Then, the distance function is

$\displaystyle\rho(s,t)=s^{2}+(s^{2}+t^{2}-q)^{2}+t^{2}=((s^{2}+t^{2})-q)^{2}+(s^{2}+t^{2}).$

Since $\rho(s,t)$ is of a special form, Lemma 4.1 implies that $C_{1}$ and
$C_{2}$ span few distances. ∎

The expression _matching curves_ refers to two ellipses or to an ellipse and a
hyperbola, as defined in (1) and (2). In particular, matching log-circles are
not curves by our definition.

######  Lemma 5.5.

Let $C_{1}$ and $C_{2}$ be matching curves. Then $(C_{1},C_{2})$ spans few
distances.

###### Proof.

By (1) and (2), we can parameterize $C_{1}$ with
$\gamma_{1}(s)=(s,\sqrt{a-ms^{2}},0)$ and $C_{2}$ with
$\gamma_{2}(t)=(t,0,\sqrt{b-mt^{2}/(m-1)})$. When $0<m<1$, the distance
function is

$\displaystyle\rho(s,t)$ $\displaystyle=(s-t)^{2}+(a-ms^{2})+(b-mt^{2}/(m-1))$
$\displaystyle=(a+b)+(1-m)s^{2}+\frac{1}{1-m}t^{2}-2st$
$\displaystyle=(a+b)+\left(\sqrt{1-m}\cdot s-\sqrt{\frac{1}{1-m}}\cdot
t\right)^{2}.$

When $m>1$, the last line of the above calculation becomes

$\rho(s,t)=(a+b)-\left(\sqrt{m-1}s+\sqrt{\frac{1}{m-1}}t\right)^{2}.$

In either case, $\rho(s,t)$ is of a special form. Thus, Lemma 4.1 implies that
$C_{1}$ and $C_{2}$ span few distances. ∎

Log-circles. Recall that log-circles are defined in (3). We define the
_positive arc_ of a log-circle to be the subset of the log-circle that is
defined by

$x^{2}+y^{2}=D+\ln(x-B).$

The _negative arc_ is the subset defined by

$x^{2}+y^{2}=\ln(B-x).$

Below we see that these are indeed arcs, since they have smooth
parameterizations. In Figure 6(a), the positive arc is the connected component
on the right and the negative arc is the component on the left. It is possible
for a log-circle to consist of only one arc. For example, the log-circle that
is defined by $x^{2}+y^{2}=2+5\cdot\log|x+1|$ has an empty negative arc
(Figure 6(b)).

(a) $x^{2}+y^{2}=2+5\cdot\log|x+1|$.

(b) $x^{2}+y^{2}=20+\log|x+1|$.

Figure 6: Different Types of Log Circles.

We now prove Theorem 1.6. We first recall the statement of this result.

Theorem 1.6. _Let $C_{1}$ and $C_{2}$ be matching log-circles. Then
$(C_{1},C_{2})$ spans few distances._

###### Proof.

By definition, we may rotate, translate, and scale $\mathbf{R}^{3}$ so that
$C_{1}$ and $C_{2}$ are defined as in (4). Such transformations do not change
the number of distances between two point sets. We first study the positive
arcs of $C_{1}$ and $C_{2}$. These arcs are defined by

$\displaystyle(x-B)^{2}+y^{2}$ $\displaystyle=D+A\cdot\ln(x)\quad\text{ and
}\quad z=0,$ $\displaystyle x^{2}+z^{2}$
$\displaystyle=D^{\prime}+A\cdot\ln(x-B)\quad\text{ and }\quad y=0.$

We parameterize the two arcs as

$\displaystyle\gamma_{1}(s)$
$\displaystyle=\left(s,\sqrt{D+A\cdot\ln(s)-(s-B)^{2}},0\right),$
$\displaystyle\gamma_{2}(t)$
$\displaystyle=\left(t+B,0,\sqrt{D^{\prime}+A\cdot\ln(t)-(t+B)^{2}}\right).$

The distance function of these parameterizations is

$\displaystyle\rho(s,t)$
$\displaystyle=(s-t-B)^{2}+\left(D+A\cdot\ln(s)-(s-B)^{2}\right)+\left(D^{\prime}+A\cdot\ln(t)-(t+B)^{2}\right)$
$\displaystyle=\left(s^{2}+t^{2}+B^{2}-2st-2sB+2tB\right)+\left(D+A\cdot\ln(s)-s^{2}+2sB-B^{2}\right)$
$\displaystyle\hskip
227.62204pt+\left(D^{\prime}+A\cdot\ln(t)-t^{2}-2tB-B^{2}\right)$
$\displaystyle=-B^{2}-2st+D+D^{\prime}+A\cdot\ln(s)+A\cdot\ln(t)=-B^{2}+D+D^{\prime}-2st+A\cdot\ln(st).$

Since $\rho(s,t)$ is of a special form, Lemma 4.1 implies that the two arcs
span few distances.

The other cases are handled similarly. When considering the negative arc of
$C_{1}$, we replace $\log(s)$ with $\log(-s)$. When considering the negative
arc of $C_{2}$, we replace $\log(t)$ with $\log(-t)$. In all cases, The
distance function $\rho(s,t)$ is of a special form. ∎

##  6 Few distances between curves on perpendicular planes

In this section, we prove Theorem 1.5. More precisely, we prove a more general
result about arcs in perpendicular planes.

######  Theorem 6.1.

Let $A_{1},A_{2}\subset\mathbf{R}^{3}$ be arcs that are contained in
perpendicular planes, with respective parametrizations
$\gamma_{1},\gamma_{2}$. Let the distance function $\rho(s,t)$ of $\gamma_{1}$
and $\gamma_{2}$ be of a special form. Then there exist nonempty open subsets
of $A_{1}$ and $A_{2}$ that are contained in one of the following pairs:

  1. (i)

a line $\ell$ and a curve contained in a plane orthogonal to $\ell$,

  2. (ii)

parallel lines,

  3. (iii)

a line $\ell$ and an ellipse contained in a cylinder centered around $\ell$,

  4. (iv)

CPO parabolas,

  5. (v)

matching curves,

  6. (vi)

matching log-circles.

Before proving Theorem 6.1, we observe that Theorem 1.5 is a corollary of
Theorem 6.1. We first recall the statement of that result.

Theorem 1.5. _Let $C_{1}$ and $C_{2}$ be curves that are contained in
perpendicular planes in $\mathbf{R}^{3}$.
(a) Assume that $C_{1}$ and $C_{2}$ are one of the following:_

  * •

_a line_ $\ell$ and a curve contained in a plane orthogonal to $\ell$,

  * •

_parallel lines,_

  * •

_a line_ $\ell$ and an ellipse contained in cylinder with axis $\ell$,

  * •

_CPO parabolas,_

  * •

_matching curves,_

  * •

_perpendicular circles._

_Then $(C_{1},C_{2})$ spans few distances.
(b) If $(C_{1},C_{2})$ is not one of the configuration from part (a), then
$(C_{1},C_{2})$ spans many distances._

###### Proof.

(a) Immediate from Theorem 1.6 and Lemmas 5.1, 5.2, 5.4, and 5.5.

(b) Consider a set of $m$ points $\mathcal{P}_{1}\subset C_{1}$ and a set of
$n$ points $\mathcal{P}_{2}\subset C_{2}$. By Lemma 2.6 there exist arcs
$A_{1}\subset C_{1}$ and $A_{2}\subset C_{2}$ such that $|\mathcal{P}_{1}\cap
A_{1}|=\Theta(m)$ and $|\mathcal{P}_{2}\cap A_{2}|=\Theta(n)$. Let
$\gamma_{1}(s)$ and $\gamma_{2}(t)$ be the respective parameterizations of
$A_{1}$ and $A_{2}$. Assume for contradiction that $(A_{1},A_{2})$ does not
span many distances. By Lemma 1.7, the distance function $\rho(s,t)$ of
$\gamma_{1}(s)$ and $\gamma_{2}(t)$ is of a special form.

By Theorem 6.1, there exist nonempty open subsets $A_{1}^{\prime}\subset
A_{1}$ and $A_{2}^{\prime}\subset A_{2}$ that are contained in a specific pair
of sets. The six possible pairs of sets are numbered (i)–(vi) in the statement
of Theorem 6.1. Assume that we are in one of cases (i)–(v), which describe
pairs of irreducible curves. Then each of $C_{1}$ and $C_{2}$ has an infinite
intersection with the corresponding curve. Theorem 2.2 implies that $C_{1}$
and $C_{2}$ share connected components with the respective curves. Since these
are irreducible curves, we conclude that $C_{1}$ and $C_{2}$ are the two
curves from Theorem 6.1. This is a contradiction, since the current theorem
assumes that $C_{1}$ and $C_{2}$ are none of these pair of curves.

It remains to consider case (vi) of Theorem 6.1. That is, the case where
$A_{1}$ and $A_{2}$ are contained in matching log-circles. Since log-circles
include a logarithm in their defining equations, we cannot use Theorem 6.1 as
in the preceding paragraph. However, a set that is defined as in (3) still has
a bounded intersection with a curve. For example, see Chapter 1 of Khovanskiĭ
[10]. The rest of the argument remains as in the preceding paragraph and leads
to a contradiction. ∎

The rest of this section is dedicated to proving Theorem 6.1. We first prove
three lemmas that are required for the proof of that theorem. The reader might
prefer to skim those lemmas and return to them later, if needed.

With Lemma 1.4 in mind, the following lemma studies ellipses that are
contained in a cylinder. The notation $\langle u,v\rangle$ denotes the
standard dot product of $u,v\in\mathbf{R}^{3}$.

######  Lemma 6.2.

For nonzero $\mu,D\in\mathbf{R}$, we consider the line

$\ell={\mathbf{V}}(x-\mu z,y)\subset\mathbf{R}^{3},$

and the ellipse

$C={\mathbf{V}}\left(\frac{x^{2}}{\mu^{2}+1}+y^{2}-D,z\right)\subset\mathbf{R}^{3}.$

Then $C$ is contained in a cylinder centered around $\ell$.

###### Proof.

We consider a unit vector in the direction of $\ell$:

$v=\left(\frac{\mu}{\sqrt{1+\mu^{2}}},0,\frac{1}{\sqrt{1+\mu^{2}}}\right).$

We also consider a point

$p=\left(p_{x},\sqrt{D-\frac{p_{x}^{2}}{\mu^{2}+1}},0\right)\in C.$

The orthogonal projection of $p$ on $\ell$ is

$\langle p,v\rangle\cdot v=p_{x}\cdot\frac{\mu}{\sqrt{1+\mu^{2}}}\cdot
v=\left(\frac{\mu^{2}p_{x}}{1+\mu^{2}},0,\frac{\mu p_{x}}{1+\mu^{2}}\right).$

We set $q=\langle p,v\rangle\cdot v$. The distance between $p$ and $\ell$ is
the distance between $p$ and $q$. The square of this distance is

$\displaystyle\left(p_{x}-\frac{\mu^{2}p_{x}}{1+\mu^{2}}\right)^{2}$
$\displaystyle+D-\frac{p_{x}^{2}}{\mu^{2}+1}+\left(\frac{\mu
p_{x}}{1+\mu^{2}}\right)^{2}$
$\displaystyle=D+p_{x}^{2}\cdot\frac{(1+\mu^{2})^{2}-2\mu^{2}(1+\mu^{2})+\mu^{4}-(1+\mu^{2})+\mu^{2}}{(1+\mu^{2})^{2}}=D.$

Since this holds for every $p\in C$, we conclude that $C$ is contained in a
cylinder of radius $\sqrt{D}$ around $\ell$. ∎

The following lemma characterizes when a distance function $\rho(s,t)$ does
not depend on $s$ or $t$. Recall that $\rho_{s}$ and $\rho_{t}$ are the first
partial derivatives of $\rho(s,t)$ according to $s$ and $t$, respectively.

######  Lemma 6.3.

Let $\gamma_{1}(s)$ and $\gamma_{2}(t)$ be parametrizations of arcs $A_{1}$
and $A_{2}$, respectively. Let $\rho(s,t)$ be the distance function of
$\gamma_{1}(s)$ and $\gamma_{2}(t)$. Assume that $\rho_{s}$ or $\rho_{t}$ is
identically zero. Then one of the two arcs is contained in a circle $C$ and
the other arc is contained in the axis of $C$.

###### Proof.

Without loss of generality, suppose that $\rho_{s}$ is identically zero. We
consider two points $p_{1},p_{2}\in A_{2}$. By the assumption on $\rho_{s}$,
the points of $A_{1}$ are equidistant from $p_{1}$. That is, $A_{1}$ is
contained in a sphere $S_{1}$ centered at $p_{1}$. Similarly, $A_{1}$ is
contained in a sphere $S_{2}$ centered at $p_{2}$. Since $S_{1}\cap S_{2}$ is
a circle, we get that $A_{1}$ is contained in a circle $C$. An arc of the
circle $C$ is equidistant from a point $p$ if and only if $p$ is on the axis
of $C$. Thus, $A_{2}$ is contained in the axis of $C$. ∎

We also require the following highly specialized result.

######  Lemma 6.4.

For nonempty open intervals $I_{1},I_{2}\subset\mathbf{R}$, consider smooth
functions $f:I_{1}\to\mathbf{R}$ and $g:I_{2}\to\mathbf{R}$, such that

$\displaystyle\sigma(s,t)$ $\displaystyle=(s-t)^{2}+f(s)^{2}+g(t)^{2}.$

If

$\frac{\partial^{2}(\ln|\sigma_{s}/\sigma_{t}|)}{\partial s\partial t}\equiv
0,$ (9)

then there exist $A_{1},A_{2},A_{3}\in\mathbf{R}$ that satisfy one of the
following cases:

  1. (i)

$f(s)f^{\prime}(s)=A_{1}+A_{2}s-s$, $A_{2}\neq 0$, and $\quad
g(t)g^{\prime}(t)=-A_{1}/A_{2}+t/A_{2}-t,$

  2. (ii)

$f(s)f^{\prime}(s)=\frac{A_{1}}{s+A_{2}}+A_{3}-s\quad$ and $\quad
g(t)g^{\prime}(t)=\frac{A_{1}}{t-A_{3}}-A_{2}-t.$

###### Proof.

We set $\mu(s)=s+f(s)f^{\prime}(s)$ and $\nu(t)=t+g(t)g^{\prime}(t)$. Then

$\displaystyle\sigma_{s}$
$\displaystyle=2(s-t)+2f(s)f^{\prime}(s)=2(\mu(s)-t),$
$\displaystyle\sigma_{t}$
$\displaystyle=2(t-s)+2g(t)g^{\prime}(t)=2(\nu(t)-s).$ (10)

Let $\sigma_{st}$ be the second derivative of $\sigma$ according to $s$ and
$t$ and note that $\sigma_{st}=-2$.

Studying $\mu(s)$ and $\nu(t)$. By splitting the quotient inside the log at
(9), we get that

$\frac{\partial^{2}\ln|\sigma_{s}|}{\partial s\partial
t}=\frac{\partial^{2}\ln|\sigma_{t}|}{\partial s\partial t}.$

Applying the derivative rule for logarithms leads to

$\frac{\partial(\sigma_{st}/\sigma_{s})}{\partial
s}=\frac{\partial(\sigma_{st}/\sigma_{t})}{\partial t}.$

Combining this with the above values for $\sigma_{s},\sigma_{t},\sigma_{st}$
leads to

$\frac{\partial(-2/(2(\mu(s)-t)))}{\partial
s}=\frac{\partial(-2/(2(\nu(t)-s)))}{\partial t},$

By computing the above derivatives, we get that

$\frac{\mu^{\prime}(s)}{(\mu(s)-t)^{2}}=\frac{\nu^{\prime}(t)}{(\nu(t)-s)^{2}}.$
(11)

The assumption (9) implies that $\sigma_{s}$ and $\sigma_{t}$ are never zero.
Combining this with (10) leads to $\mu(s)\neq t$ and $\nu(t)\neq s$. Thus, the
denominators in (11) are never zero.

For a fixed $t\in I_{2}$, we set $C_{1}=t$, $C_{2}=\nu^{\prime}(t)$, and
$C_{3}=\nu(t)$. Then, (11) becomes

$\frac{\mu^{\prime}(s)}{(\mu(s)-C_{1})^{2}}=\frac{C_{2}}{(C_{3}-s)^{2}}.$

Integrating both sides according to $s$ leads to

$\frac{1}{\mu(s)-C_{1}}=\frac{-C_{2}}{C_{3}-s}+C_{4}=\frac{C_{3}C_{4}-C_{4}s-C_{2}}{C_{3}-s},$

for some $C_{4}\in\mathbf{R}$. Since the left side of this equation is
nonzero, we have that $C_{3}C_{4}-C_{4}s-C_{2}\neq 0$. We may thus rearrange
this equation as

$\mu(s)=\frac{C_{3}-s}{C_{3}C_{4}-C_{4}s-C_{2}}-C_{4}$

When $C_{4}=0$, we can rewrite the above as $\mu(s)=B_{1}+B_{2}s$, for some
$B_{1},B_{2}\in\mathbf{R}$. When $C_{4}\neq 0$, we can rewrite the above as

$\mu(s)=\frac{B_{1}}{B_{2}+s}+B_{3}.$

We call the first form of $\mu(s)$ the _linear form_ and the second the
_rational form_. A symmetric argument with a fixed $s$ implies that either
$\nu(t)=B_{1}^{\prime}+B_{2}^{\prime}t$ or
$\nu(t)=\frac{B^{\prime}_{1}}{B^{\prime}_{2}+t}+B_{3}^{\prime}$.

We rewrite (11) as

$\mu^{\prime}(s)(\nu(t)-s)^{2}=\nu^{\prime}(t)(\mu(s)-t)^{2}.$ (12)

The case of two linear forms. We first assume that both $\mu(s)$ and $\nu(t)$
have a linear form. Plugging these forms into (12) gives

$\displaystyle B_{2}(B_{1}^{\prime}+B_{2}^{\prime}t-s)^{2}$
$\displaystyle=B_{2}^{\prime}(B_{1}+B_{2}s-t)^{2},\quad\text{ or
equivalently}$ $\displaystyle B_{2}(B_{1}^{\prime 2}+B_{2}^{\prime
2}t^{2}+s^{2}+2B_{1}^{\prime}B_{2}^{\prime}t-2B_{1}^{\prime}s-2B_{2}^{\prime}st)$
$\displaystyle=B_{2}^{\prime}(B_{1}^{2}+B_{2}^{2}s^{2}+t^{2}+2B_{1}B_{2}s-2B_{1}t-2B_{2}st).$

Cancelling the identical last term on both sides leads to

$B_{2}(B_{1}^{\prime 2}+B_{2}^{\prime
2}t^{2}+s^{2}+2B_{1}^{\prime}B_{2}^{\prime}t-2B_{1}^{\prime}s)=B_{2}^{\prime}(B_{1}^{2}+B_{2}^{2}s^{2}+t^{2}+2B_{1}B_{2}s-2B_{1}t)$
(13)

By comparing the coefficients of $s^{2}$ on both sides, we obtain that
$B_{2}=B_{2}^{2}B_{2}^{\prime}$. The coefficients of $t^{2}$ imply that
$B_{2}^{\prime}=B_{2}(B_{2}^{\prime})^{2}$. Combining these two observations
implies either $B_{2}=B_{2}^{\prime}=0$ or $B_{2}B_{2}^{\prime}=1$. When
$B_{2}=B_{2}^{\prime}=0$, both $\mu(s)$ and $\nu(t)$ are constant functions,
so we are in case (ii) of the lemma with $A_{1}=0$. When
$B_{2}B_{2}^{\prime}=1$, comparing the coefficients of $t$ in (13) implies
that $B_{1}^{\prime}=-B_{1}B_{2}^{\prime}$. We can rephrase this as
$B_{1}^{\prime}=-B_{1}/B_{2}$, which leads to $\nu(t)=-B_{1}/B_{2}+t/B_{2}$.
This is case (i).

The case of one linear form. We next consider the case where $\mu(s)$ has a
linear form and $\nu(t)$ has a rational form. In this case, (12) becomes

$B_{2}\left(\frac{B_{1}^{\prime}}{B_{2}^{\prime}+t}+B_{3}^{\prime}-s\right)^{2}=\frac{-B_{1}^{\prime}}{(B_{2}^{\prime}+t)^{2}}(B_{1}+B_{2}s-t)^{2}.$

Multiplying both sides by $(B_{2}^{\prime}+t)^{2}$ leads to

$B_{2}(B_{1}^{\prime}+(B_{3}^{\prime}-s)(B_{2}^{\prime}+t))^{2}=-B_{1}^{\prime}(B_{1}+B_{2}s-t)^{2}.$

Comparing the coefficients of $s^{2}t^{2}$ on both sides implies that
$B_{2}=0$. This turns the above equation to $0=B_{1}^{\prime}(B_{1}-t)^{2}$,
which in turn implies that $B_{1}^{\prime}=0$. Once again, $\mu(s)$ and
$\nu(t)$ are constants, so we are in case (ii) with $A_{1}=0$.

The case where $\mu(s)$ has a rational form and $\nu(t)$ has a linear form is
handled symmetrically.

The case of two rational forms. We consider the case where both $\mu(s)$ and
$\nu(t)$ have a rational form. In this case, (12) becomes

$\frac{B_{1}}{(B_{2}+s)^{2}}\left(\frac{B_{1}^{\prime}}{B_{2}^{\prime}+t}+B_{3}^{\prime}-s\right)^{2}=\frac{B_{1}^{\prime}}{(B_{2}^{\prime}+t)^{2}}\left(\frac{B_{1}}{B_{2}+s}+B_{3}-t\right)^{2}.$

Multiplying by $(B_{2}+s)^{2}(B_{2}^{\prime}+t)^{2}$ leads to

$B_{1}(B_{1}^{\prime}+(B_{3}^{\prime}-s)(B_{2}^{\prime}+t))^{2}=B_{1}^{\prime}(B_{1}+(B_{3}-t)(B_{2}+s))^{2}.$

Comparing the coefficients of $s^{2}t^{2}$ implies that
$B_{1}=B_{1}^{\prime}.$ If $B_{1}=B_{1}^{\prime}=0$ then $\mu(s)$ and $\nu(t)$
are constants and we are in case (ii) with $A_{1}=0$. Otherwise, the above
equation becomes

$\displaystyle(B_{1}+(B_{3}^{\prime}-s)(B_{2}^{\prime}+t))^{2}$
$\displaystyle=(B_{1}+(B_{3}-t)(B_{2}+s))^{2},\quad\text{ or equivalently}$
$\displaystyle B_{1}+(B_{3}^{\prime}-s)(B_{2}^{\prime}+t)$
$\displaystyle=\pm(B_{1}+(B_{3}-t)(B_{2}+s)).$

The $\pm$ symbol must be replaced with a plus, since otherwise the
coefficients of $st$ do not match. Comparing the coefficients of $s$ implies
that $B_{2}^{\prime}=-B_{3}$. Comparing the coefficients of $t$ implies that
$B_{3}^{\prime}=-B_{2}$. We conclude that
$\nu(t)=\frac{B_{1}}{-B_{3}+t}-B_{2}$, which is case (ii). ∎

We are finally ready to prove Theorem 6.1.

###### Proof of Theorem 6.1..

By rotating and translating $\mathbf{R}^{3}$, we may assume that $A_{1}$ is
contained in the $xy$-plane and $A_{2}$ is contained in the $xz$-plane. That
is, both $\gamma_{1,z}(s)$ and $\gamma_{2,y}(t)$ are identically zero. If the
$x$-coordinate of $\gamma_{1}$ is constant on an interval in $(0,1)$, then
$A_{1}$ contains a line segment parallel to the $y$-axis. This implies that we
are in case (i). A symmetric argument holds when $\gamma_{2}$ has constant
$x$-coordinate in an interval of $(0,1)$. We may thus assume that
$\gamma_{1,x}$ and $\gamma_{2,x}$ are not constant in any interval.

We next consider the case where $\rho_{s}\equiv 0$ or $\rho_{t}\equiv 0$ in a
nonempty neighborhood of $(0,1)^{2}$. By defining $A_{1}^{\prime}$ and
$A^{\prime}_{2}$ as the corresponding subarcs, Lemma 6.3 implies that we are
in case (i). We may thus assume that $\rho_{s}\not\equiv 0$ and
$\rho_{t}\not\equiv 0$ in every neighborhood. By Lemma 1.8, there exist
nonempty open intervals $I_{1},I_{2}\subset(0,1)$ such that

$\frac{\partial^{2}\ln|\rho_{s}/\rho_{t}|}{\partial s\partial t}\equiv
0\quad\text{in}\ I_{1}\times I_{2}.$

Since $\gamma_{1,x}$ and $\gamma_{2,x}$ are not constant in any interval,
there exist $s_{0}\in I_{1}$ and $t_{0}\in I_{2}$ such that
$\gamma_{1,x}^{\prime}(s_{0})\neq 0$ and $\gamma_{2,x}^{\prime}(t_{0})\neq 0.$
By the inverse function theorem, there exist a neighborhood
$J_{1}\subset\mathbf{R}$ of $\gamma_{1,x}(s_{0})$ and a neighborhood
$J_{2}\subset\mathbf{R}$ of $\gamma_{2,x}(t_{0})$ in which $\gamma_{1,x}^{-1}$
and $\gamma_{2,x}^{-1}$ are well-defined and smooth. We consider the
parameterizations $\widetilde{\gamma}_{1}(s)=\gamma_{1}\circ\gamma_{1,x}^{-1}$
and $\widetilde{\gamma}_{2}(t)=\gamma_{2}\circ\gamma_{2,x}^{-1}(t)$. Note that
$\widetilde{\gamma}_{1}(s)$ parameterizes a subarc of $A_{1}$, when restricted
to $J_{1}$. Similarly, $\widetilde{\gamma}_{2}(t)$ parameterizes a subarc of
$A_{2}$, when restricted to $J_{2}$.

Let $\widetilde{\rho}(s,t)$ be the distance function of
$\widetilde{\gamma}_{1}(s)$ and $\widetilde{\gamma}_{2}(t)$. This is a slight
abuse of notation, since the domain of this distance function is $J_{1}\times
J_{2}$ rather than $(0,1)^{2}$. We also set $f(s)=\widetilde{\gamma}_{1,y}(s)$
and $g(t)=\widetilde{\gamma}_{2,z}(t)$. Since
$\widetilde{\gamma}_{1,x}(s)=\gamma_{1,x}((\gamma_{1,x}^{-1}(s))=s$ and
$\widetilde{\gamma}_{2,x}(t)=\gamma_{2,x}(\gamma_{2,x}^{-1}(t))=t$, we have
that

$\displaystyle\widetilde{\rho}(s,t)$
$\displaystyle=(\widetilde{\gamma}_{1,x}(s)-\widetilde{\gamma}_{1,x}(t))^{2}+\widetilde{\gamma}_{1,y}(s)^{2}+\widetilde{\gamma}_{2,z}(t)^{2}$
$\displaystyle=(s-t)^{2}+f(s)^{2}+g(t)^{2}.$

Since $\widetilde{\rho}(s,t)=\rho(\gamma_{1,x}^{-1}(s),\gamma_{2,x}^{-1}(t))$,
we have that

$\frac{\partial^{2}\ln|\widetilde{\rho}_{s}/\widetilde{\rho}_{t}|}{\partial
s\partial t}\equiv 0\quad\text{in}\ J_{1}\times J_{2}.$

To complete the proof, it suffices to show that there exist continuous open
subsets of $\widetilde{\gamma}_{1}(J_{1})$ and $\widetilde{\gamma}_{2}(J_{2})$
that are contained in one of the pairs from the statement of the theorem. By
the above, we may apply Lemma 6.4 with $\widetilde{\rho}(s,t)$. This lemma
implies that there exist $A_{1},A_{2},A_{3}\in\mathbf{R}$ that satisfy one of
the following cases:

  1. (a)

$f(s)f^{\prime}(s)=A_{1}+A_{2}s-s$, $A_{2}\neq 0$, and $\quad
g(t)g^{\prime}(t)=-A_{1}/A_{2}+t/A_{2}-t,$

  2. (b)

$f(s)f^{\prime}(s)=\frac{A_{1}}{s+A_{2}}+A_{3}-s\quad$ and $\quad
g(t)g^{\prime}(t)=\frac{A_{1}}{t-A_{3}}-A_{2}-t.$

We note that

$(f(s)^{2})^{\prime}=2f(s)f^{\prime}(s)\qquad\text{ and
}\qquad(g(t)^{2})^{\prime}=2g(t)g^{\prime}(t).$

This in turn implies that

$f(s)^{2}=2\int f(s)f^{\prime}(s)\,ds\qquad\text{ and }\qquad g(t)^{2}=2\int
g(t)g^{\prime}(t)\,dt.$ (14)

Case (a). We first assume that we are in case (a). Then there exist
$A_{4},A_{5}\in\mathbf{R}$ such that (14) becomes

$\displaystyle f(s)^{2}$ $\displaystyle=2A_{1}s+s^{2}(A_{2}-1)+A_{4},$
$\displaystyle g(t)^{2}$
$\displaystyle=-2A_{1}t/A_{2}+t^{2}(1/A_{2}-1)+A_{5}.$ (15)

When $A_{1}=0$ and $A_{2}=1$, both $f(s)$ and $g(t)$ are constant functions.
Then, $\widetilde{\gamma}_{1}(J_{1})$ and $\widetilde{\gamma}_{2}(J_{2})$ are
line segments parallel to the $x$-axis. We are thus in case (ii) of the
theorem.

When $A_{1}\neq 0$ and $A_{2}=1$, we get that

$\displaystyle\widetilde{\gamma}_{1}(J_{1})$
$\displaystyle=\\{(s,\sqrt{2A_{1}s+A_{4}},0):s\in J_{1}\\},$
$\displaystyle\widetilde{\gamma}_{2}(J_{2})$
$\displaystyle=\\{(t,0,\sqrt{A_{5}-2A_{1}t}):t\in J_{2}\\}.$

We note that $\widetilde{\gamma}_{1}(J_{1})$ is a segment of the parabola
${\mathbf{V}}(z,x-(y^{2}-A_{4})/2A_{1})$. Similarly,
$\widetilde{\gamma}_{2}(J_{2})$ is a segment of the parabola
${\mathbf{V}}(y,x+(z^{2}-A_{5})/2A_{1})$. It is not difficult to verify that
these are CPO parabolas. In particular, the axis of both parabolas is the
$x$-axis of $\mathbf{R}^{3}$. We are thus in Case (iv).

It remains to consider the case where $A_{2}\neq 1$. In this case, there exist
$A_{4}^{\prime},A_{5}^{\prime}\in\mathbf{R}$ such that we can rewrite (15) as

$\displaystyle f(s)^{2}$
$\displaystyle=2A_{1}s+s^{2}(A_{2}-1)+A_{4}=(A_{2}-1)\left(s+\frac{A_{1}}{A_{2}-1}\right)^{2}+A^{\prime}_{4},$
$\displaystyle g(t)^{2}$
$\displaystyle=-2A_{1}t/A_{2}+t^{2}(1/A_{2}-1)+A_{5}=\frac{1-A_{2}}{A_{2}}\left(t+\frac{A_{1}}{A_{2}-1}\right)^{2}+A_{5}^{\prime}.$

Imitating the above analysis that led to the CPO parabolas, we obtain that

$\displaystyle\widetilde{\gamma}_{1}(J_{1})$
$\displaystyle\subset{\mathbf{V}}\left(z,y^{2}-(A_{2}-1)\left(x+\frac{A_{1}}{A_{2}-1}\right)^{2}-A_{4}^{\prime}\right),$
$\displaystyle\widetilde{\gamma}_{2}(J_{2})$
$\displaystyle\subset{\mathbf{V}}\left(y,z^{2}-\frac{1-A_{2}}{A_{2}}\left(x+\frac{A_{1}}{A_{2}-1}\right)^{2}-A_{5}^{\prime}\right).$

We translate $\mathbf{R}^{3}$ a distance of $-A_{1}/(A_{2}-1)$ in the
$x$-direction. We set $m=1-A_{2}$ and note that $m/(m-1)=(A_{2}-1)/A_{2}$. By
the assumption of this case, $A_{2}\neq 0$, so $m\neq 1$. Then, the above
becomes

$\displaystyle\widetilde{\gamma}_{1}(J_{1})$
$\displaystyle\subset{\mathbf{V}}\left(z,y^{2}+mx^{2}-A_{4}^{\prime}\right),$
$\displaystyle\widetilde{\gamma}_{2}(J_{2})$
$\displaystyle\subset{\mathbf{V}}\left(y,z^{2}+\frac{m}{m-1}x^{2}-A_{5}^{\prime}\right).$

We set $k=m/(m-1)$ and note that $m=k/(k-1)$. This leads to a symmetry between
$\widetilde{\gamma}_{1}(J_{1})$ and $\widetilde{\gamma}_{2}(J_{2})$: To switch
between the two curves, we switch $m$ and $k$, and the $y$ and $z$ axes. If
$m<0$ then $k>0$. Thus, by possibly switching $\widetilde{\gamma}_{1}(J_{1})$
and $\widetilde{\gamma}_{2}(J_{2})$, we may assume that $m>0$. This implies
that $A_{4}^{\prime}>0$, since otherwise $\widetilde{\gamma}_{1}(J_{1})$
consists of at most one point. When $A_{5}^{\prime}\neq 0$, the above is a
matching pair, so we are in Case (v).

It remains to consider the case where $A_{5}^{\prime}=0$. We have that
$0<m<1$, since otherwise $\widetilde{\gamma}_{2}(J_{2})$ consists of at most
one point. We rewrite the above as

$x=\pm z\cdot\sqrt{\frac{1-m}{m}}.$

We conclude that $\widetilde{\gamma}_{2}(J_{2})$ is contained in the union of
two lines. By the definition of $\widetilde{\gamma}_{2}(J_{2})$, it is a
segment of one of these two lines $\ell$.

Setting the slope of $\ell$ as $\mu=\pm\sqrt{\frac{1-m}{m}}$, we note that
$1/(\mu^{2}+1)=m$. We may thus apply Lemma 6.2 with $\ell$ and the ellipse
that contains $\widetilde{\gamma}_{1}(J_{1})$. The lemma states that the
ellipse is contained in a cylinder centered around $\ell$. This is Case (iii).

Case (b). We now assume that we are in case (b). Then there exist
$A_{4},A_{5}\in\mathbf{R}$ such that (14) becomes

$\displaystyle f(s)^{2}$
$\displaystyle=2A_{1}\ln|s+A_{2}|+2A_{3}s-s^{2}+A_{4},$ $\displaystyle
g(t)^{2}$ $\displaystyle=2A_{1}\ln|t-A_{3}|-2A_{2}t-t^{2}+A_{5}.$

Repeating the analysis of Case (a) leads to333We abuse the notation
${\mathbf{V}}(\cdot)$ by placing a function that is not a polynomial in it.

$\displaystyle\widetilde{\gamma}_{1}(J_{1})$
$\displaystyle\subset{\mathbf{V}}\left(z,x^{2}+y^{2}-2A_{1}\ln|x+A_{2}|-2A_{3}x-A_{4}\right),$
$\displaystyle\widetilde{\gamma}_{2}(J_{2})$
$\displaystyle\subset{\mathbf{V}}\left(y,x^{2}+z^{2}-2A_{1}\ln|x-A_{3}|+2A_{2}x-A_{5}\right).$

After rearranging, we get that there exist
$A_{4}^{\prime},A_{5}^{\prime}\subset\mathbf{R}$, such that

$\displaystyle\widetilde{\gamma}_{1}(J_{1})$
$\displaystyle\subset{\mathbf{V}}\left(z,(x-A_{3})^{2}+y^{2}-2A_{1}\ln|x+A_{2}|-A^{\prime}_{4}\right),$
$\displaystyle\widetilde{\gamma}_{2}(J_{2})$
$\displaystyle\subset{\mathbf{V}}\left(y,(x+A_{2})^{2}+z^{2}-2A_{1}\ln|x-A_{3}|-A^{\prime}_{5}\right).$

The above sets are matching log-circles. Indeed, consider the sets after
translating $\mathbf{R}^{3}$ a distance of $A_{2}$ in the $x$-direction. This
is Case (vi). ∎

##  7 Few distances between conics

In this section, we prove Theorem 1.3. This theorem is a corollary of the
results of Section 5 and of following lemma.

######  Lemma 7.1.

In the following, all curves are in $\mathbf{R}^{3}$.
(a) Two circles that are neither aligned nor perpendicular span many
distances.
(b) A circle and hyperbola span many distances.
(c) Two parabolas that are not CPO span many distances.
(d) A parabola and an ellipse span many distances.
(e) A parabola and a hyperbola span many distances.
(f) Two hyperbolas span many distances.
(g) A hyperbola and an ellipse that do not match span many distances.
(h) Two ellipses that do not match and are not aligned circles span many
distances.

###### Proof.

Part (a) is proved in [12], so it remains to consider cases (b)–(h). Since the
different proofs are almost identical, we present them together. We denote the
two curves as $C_{1}$ and $C_{2}$. We first perform a rotation, translation,
and uniform scaling of $\mathbf{R}^{3}$ to obtain the following.

  * •

If $C_{1}$ is a parabola then $C_{1}={\bf v}(y-x^{2},z)$.

  * •

If $C_{1}$ is a hyperbola then $C_{1}={\bf v}(x^{2}-\frac{y^{2}}{c^{2}}-1,z)$.

  * •

If $C_{1}$ is an ellipse then $C_{1}={\bf v}(x^{2}+\frac{y^{2}}{c^{2}}-1,z)$.

Such transformations do not change the number of distances between two sets of
points.

After the above transformations, we have a nice parameterization
$\gamma_{1}(s)$ of $C_{1}$, possibly excluding a single point:

  * •

If $C_{1}$ is a parabola then $\gamma_{1}(s)=(s,s^{2},0)$.

  * •

If $C_{1}$ is a hyperbola then
$\gamma_{1}(s)=\left(\frac{s^{2}+1}{2s},c\cdot\frac{1-s^{2}}{2s},0\right)$.

  * •

If $C_{1}$ is an ellipse then
$\gamma_{1}(s)=\left(\frac{1-s^{2}}{1+s^{2}},c\cdot\frac{2s}{1+s^{2}},0\right)$.

After fixing $C_{1}$, we cannot transform $\mathbf{R}^{3}$ to also give
$C_{2}$ a simple parameterization. To parameterize $C_{2}$, we use a point
$(p,q,r)\in\mathbf{R}^{3}$ and orthogonal vectors
$\mathbf{v}_{1},\mathbf{v}_{2}\in\mathbf{R}^{3}$:

  * •

If $C_{2}$ is a parabola then
$\gamma_{2}(t)=(p,q,r)+t\cdot\mathbf{v}_{1}+t^{2}\cdot\mathbf{v}_{2}$.

  * •

If $C_{2}$ is a hyperbola then
$\gamma_{2}(t)=(p,q,r)+\frac{t^{2}+1}{2t}\cdot\mathbf{v}_{1}+\frac{t^{2}-1}{2t}\cdot\mathbf{v}_{2}$.

  * •

If $C_{2}$ is an ellipse then
$\gamma_{2}(t)=(p,q,r)+\frac{t^{2}-1}{t^{2}+1}\mathbf{v}_{1}+\frac{2t}{t^{2}+1}\mathbf{v}_{2}$.

As before, these parameterizations might exclude a single point of $C_{2}$.

Let $\rho(s,t)$ be the distance function of $\gamma_{1}(s)$ and
$\gamma_{2}(t)$, as defined in (5). By Lemma 1.7, either $\rho(s,t)$ is of a
special form or $(C_{1},C_{2})$ spans many distances. We assume that we are in
the case where $\rho(s,t)$ is of a special form. If $\rho_{s}$ or $\rho_{t}$
is identically zero in an open neighborhood, then Lemma 6.3 implies that
$C_{1}$ or $C_{2}$ is a line. Since this contradicts the assumption of the
theorem, $\rho_{s}$ and $\rho_{t}$ are not identically zero in any open
neighborhood.

By the above, we may apply Lemma 1.8 with $\rho(s,t)$. The lemma implies that
there exists an open neighborhood in $\mathbf{R}^{2}$ in which

$\frac{\partial^{2}(\ln|\rho_{s}/\rho_{t}|)}{\partial s\partial t}\equiv 0.$
(16)

A careful reader might complain that Lemma 1.8 is defined for
pararmeterizations with the domain $(0,1)$, while the above parameterizations
assume $s,t\in\mathbf{R}$. It is easy to address this technicality. For
example, we can obtain half of the curve by composing the above
parameterization with $h(r)=1/r$, where $r\in(0,1)$. The other half is
obtained by composing the parameterization with $h(r)=-1/r$. By observing (6),
we note that having a special form is invariant under replacing $s$ with $\pm
1/s$ and $t$ with $\pm 1/t$.

The left side of (16) is a rational function. To see that, we set
$h(s,t)=\rho_{s}/\rho_{t}$. 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)$, with $c\in\\{-1,1\\}$. In either
case,

$\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)}.$

We write $\mathbf{v}_{1}=(x_{1},y_{1},z_{1})$ and
$\mathbf{v}_{2}=(x_{2},y_{2},z_{2})$. Then the left side of (16) is a rational
function in $s$ and $t$ whose coefficients are rational functions in
$c,p,q,r,x_{1},x_{2},y_{1},y_{2},z_{1},z_{2}$. We denote the numerator of this
rational function as $\rho_{N}(s,t)$.

By (16), the polynomial $\rho_{N}(s,t)$ is identically zero in an open
neighborhood of $\mathbf{R}^{2}$. That is, all the coefficients of
$\rho_{N}(s,t)$ are zero. We use Wolfram Mathematica to compute
$\rho_{N}(s,t)$. We then show that, when we are not in one of the special
configurations that span few distances, it is impossible for all the
coefficients of $\rho_{N}(s,t)$ to be zero simultaneously. This contradiction
implies that $(C_{1},C_{2})$ spans many distances, as asserted. For the
Mathematica computations, see Appendices A and B. ∎

We are now ready to prove Theorem 1.3. We first recall the statement of this
result.

Theorem 1.3 (Few distances between conics) _Let
$C_{1},C_{2}\subset\mathbf{R}^{3}$ be non-degenerate conic sections.
(a) Assume that $C_{1}$ and $C_{2}$ are either perpendicular circles, aligned
circles, CPO parabolas, or matching curves. Then $(C_{1},C_{2})$ spans few
distances.
(b) If $(C_{1},C_{2})$ is not one of the configurations from part (a), then
$(C_{1},C_{2})$ spans many distances._

###### Proof.

Part (a) is immediate by combining Lemmas 3.1, 5.3, 5.4, and 5.5. Part (b) is
immediate from Lemma 7.1. ∎

## References

  * [1] S. Bardwell–Evans and A. Sheffer, A Reduction for the Distinct Distances Problem in $\mathbf{R}^{d}$, _J. Combinat. Theory A_ 166 (2019), 171–225.
  * [2] S. Basu, R. Pollack, and M.-F. Coste–Roy, _Algorithms in real algebraic geometry_ , Springer Science & Business Media, 2007.
  * [3] J. Bochnak, M. Coste, and M. Roy, _Real Algebraic Geometry_ , Springer-Verlag, Berlin, 1998.
  * [4] P. Brass, W. Moser, and J. Pach, Research Problems in Discrete Geometry, Springer–Verlag, New York, 2005.
  * [5] E. Breuillard, B. Green, and T. Tao, Approximate subgroups of linear groups, _Geom. Funct. Anal._ 21 (2011), 774.
  * [6] A. Bruner and M. Sharir, Distinct distances between a collinear set and an arbitrary set of points, _Discrete Math._ 341 (2018), 261–265.
  * [7] P. Erdős, On sets of distances of $n$ points, _Amer. Math. Monthly_ 53 (1946), 248–250.
  * [8] L. Guth and N. H. Katz, On the Erdős distinct distances problem in the plane, Annals Math. 181 (2015), 155–190.
  * [9] J. Harris, _Algebraic geometry: a first course_ , Springer, New York, 1992.
  * [10] A. G. Khovanskiĭ, _Fewnomials_ , Vol. 88. American Mathematical Soc., 1991.
  * [11] J. Milnor, On the Betti numbers of real varieties, _Proc. Amer. Math. Soc._ 15 (1964), 275–280.
  * [12] S. Mathialagan and A. Sheffer, Distinct distances on non-ruled surfaces and between circles, _Discrete Comput. Geom._ 69 (2023), 422–452.
  * [13] J. Pach and F. de Zeeuw, Distinct distances on algebraic curves in the plane, _Comb. Probab. Comp._ 26 (2017), 99–117.
  * [14] A. Sheffer, Distinct Distances: Open Problems and Current Bounds, arXiv:1406.1949.
  * [15] O. E. Raz, A note on distinct distances, _Combinat. Probab. Comput._ 29 (2020), 650–663.
  * [16] 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.
  * [17] A. Sheffer, Polynomial Methods and Incidence Theory, Cambridge University Press, 2022.
  * [18] Wolfram Research, Inc., Mathematica, Version 13.0, Champaign, IL (2021).
  * [19] J. Solymosi and T. Tao, An incidence theorem in higher dimensions, _Discrete Comput. Geom._ 48 (2012), 255–280.
  * [20] J. Solymosi and J. Zahl, Improved Elekes–Szabó type estimates using proximity, arXiv:2211.13294.
  * [21] R. Thom, Sur l’homologie des variétés algebriques réelles, in: S.S. Cairns (ed.), _Differential and Combinatorial Topology_ , Princeton University Press, Princeton, NJ, 1965, 255–265.

##  Appendix A Mathematica computations: the case of two ellipses

In this appendix, we complete the proof of Lemma 7.1 for ellipses, by using
Wolfram Mathematica. In particular, we assume that all coefficients of
$\rho_{N}(s,t)$ are zero, and show that this can only happen when the ellipses
match. The case of two ellipses is the most complicated one, by far. This case
includes all ideas that are used in the other cases. In Appendix B, we see
that the case of two hyperbolas is orders of magnitude simpler.

Final preparations. Before getting to the code, we further simplify the
situation. Every ellipse centered at the origin in $\mathbf{R}^{2}$ can be
defined as ${\mathbf{V}}(ax^{2}+bxy+cy^{2}-1)$ for some $a,b,c\in\mathbf{R}$.
Conversely, ${\mathbf{V}}(ax^{2}+bxy+cy^{2}-1)$ is an ellipse when $a,c>0$ and
$b^{2}-ac<0$. An ellipse is _standard_ if it is centered at the origin and its
axes are also the axes of $\mathbf{R}^{2}$. Equivalently, an ellipse is
standard if $b=0$ in its defining equation.

######  Lemma A.1.

(a) Consider an ellipse $E\subset\mathbf{R}^{2}$ centered at the origin. Let
$p$ be the point with the smallest $y$-coordinate on $E$. Then there exist
$\mathbf{v}_{1},\mathbf{v}_{2}\in\mathbf{R}^{2}$ such that $\mathbf{v}_{1}$ is
on the $x$-axis and

$E\setminus\\{p\\}=\left\\{\frac{1-s^{2}}{1+s^{2}}\cdot\mathbf{v}_{1}+\frac{2s}{1+s^{2}}\cdot\mathbf{v}_{2}\
:\ s\in\mathbf{R}\right\\}.$

(b) Let $\Pi\subset\mathbf{R}^{3}$ be a plane that contains the origin and let
$E\subset\mathbf{R}^{3}$ be an ellipse centered at the origin. Then there
exist $p\in E$, $\mathbf{v}_{1}\in\Pi$, and $\mathbf{v}_{2}\in\mathbf{R}^{3}$
such that

$E\setminus\\{p\\}=\left\\{\frac{1-s^{2}}{1+s^{2}}\cdot\mathbf{v}_{1}+\frac{2s}{1+s^{2}}\cdot\mathbf{v}_{2}\
:\ s\in\mathbf{R}\right\\}.$

###### Proof.

(a) We write $E={\mathbf{V}}(ax^{2}+bxy+cy^{2}-1)$ and consider the
transformation $T(x,y)=(x+by/2a,y)$. A point $(x,y)$ is on $T(E)$ if and only
if

$\displaystyle 1$
$\displaystyle=a\left(x-\frac{b}{2a}y\right)^{2}+b\left(x-\frac{b}{2a}y\right)y+cy^{2}$
$\displaystyle=a\left(x^{2}-\frac{b}{a}xy+\frac{b^{2}}{4a^{2}}y^{2}\right)+bxy-\frac{b^{2}}{2a}y^{2}+cy^{2}=ax^{2}+\left(-\frac{b^{2}}{4a}+c\right)y^{2}.$

Since $b^{2}-ac<0$, the coefficient of $y^{2}$ is positive, so $T(E)$ is a
standard ellipse. We set $E^{\prime}=T(E)$ and let $p^{\prime}$ be the point
with the smallest $y$-coordinate on $E^{\prime}$. Since $E^{\prime}$ is
standard, there exist axis-parallel vectors
$\mathbf{v}^{\prime}_{1},\mathbf{v}^{\prime}_{2}\in\mathbf{R}^{2}$ such that

$E^{\prime}\setminus\\{p^{\prime}\\}=\left\\{\frac{1-s^{2}}{1+s^{2}}\cdot\mathbf{v}^{\prime}_{1}+\frac{2s}{1+s^{2}}\cdot\mathbf{v}^{\prime}_{2}\
:\ s\in\mathbf{R}\right\\}.$

We note that $T(\cdot)$ does not change $y$-coordinates. Since
$E^{\prime}=T(E)$, we obtain the assertion of the lemma by setting
$\mathbf{v}_{1}=T^{-1}(\mathbf{v}_{1}^{\prime})$ and
$\mathbf{v}_{2}=T^{-1}(\mathbf{v}_{2}^{\prime})$.

(b) Let $\Pi^{\prime}$ be the plane that contains $C$. We may assume that
$\Pi\neq\Pi^{\prime}$, since otherwise we are done. Since both planes contain
the origin, their intersection is a line $\ell$. We move to work inside of
$\Pi^{\prime}$ and change the axes so that $\ell$ is the $x$-axis. Then, part
(a) of the current lemma completes the proof of part (b). ∎

We follow the parameterizations from the proof of Lemma 7.1 in Section 7.
However, instead of asking the vectors ${\bf v}_{1},{\bf v}_{2}$ to be
orthogonal, we apply Lemma A.1(b) to have the third coordinate of ${\bf
v}_{2}$ be 0. (That is, we apply Lemma A.1(b) after a translation taking the
center of $C_{2}$ to be the origin.) Then, there exist $c>0$ and vectors
$\mathbf{v}_{1}=(x_{1},y_{1},z_{1}),\mathbf{v}_{2}=(x_{2},y_{2},0)$ such that

$\displaystyle\gamma_{1}(s)$
$\displaystyle=\left(\frac{1-s^{2}}{1+s^{2}},c\cdot\frac{2s}{1+s^{2}},0\right),$
$\displaystyle\gamma_{2}(t)$
$\displaystyle=(p,q,r)+\frac{t^{2}-1}{t^{2}+1}\mathbf{v}_{1}+\frac{2t}{t^{2}+1}\mathbf{v}_{2}.$
(17)

If both $C_{1}$ and $C_{2}$ are circles, then we are done by Theorem 1.2.
Thus, without loss of generality, we may assume that $C_{1}$ is not a circle.
In other words, $c\neq 1$. By Lemma 3.1, we may assume that $C_{2}$ is not
contained in a plane parallel to the $xy$-plane. This in turn implies that
$z_{1}\neq 0$.

Let $\rho(s,t)$ be the distance function of $\gamma_{1}(s)$ and
$\gamma_{2}(t)$, as defined in (5). As in Section 7, we set $\rho_{N}(s,t)$ to
be the numerator of $\frac{\partial^{2}(\ln|\rho_{s}/\rho_{t}|)}{\partial
s\partial t}$. We recall that $\rho_{N}(s,t)$ is a polynomial in $s$ and $t$,
where the coefficients of the monomials depend on
$c,x_{1},y_{1},z_{1},x_{2},y_{2},p,q,r$. To complete the proof, we assume that
all these coefficients equal zero and show that this only happens when $C_{1}$
and $C_{2}$ are matching ellipses. We denote the coefficient of $s^{a}t^{b}$
in $\rho_{N}(s,t)$ as $\textit{coeff}\hskip 2.0pt[s^{a}t^{b}]$.

The case analysis. We are now ready to present the computational part of our
analysis, which is partitioned into cases. We start with the most general case
and gradually branch into more specialized cases. We include figures with the
code of the first four Mathematica calculations. Since the code is very
similar for all cases, we believe that four figures suffice. For readability,
in the code we denote $\gamma_{1}$ and $\gamma_{2}$ as $c1$ and $c2$,
respectively. The function _dist[s,t]_ represents $\rho(s,t)$. The variable
_RhoTest_ represents $\rho_{N}(s,t)$.

The case where $p=q=r=0$ is addressed separately below, under the heading “The
case of two ellipses centered at the origin.” We first assume that $C_{2}$ is
not centered at the origin. Since matching ellipses have the same center, we
cannot have matching ellipses in this case. Figure 7 may be helpful while
reading the case analysis.

Figure 7: A roadmap of the case analysis when the second ellipse is not
centered at the origin.

  1. (A1)

The general case. For our first step, we compute

$\textit{coeff}\hskip 2.0pt[st]-\textit{coeff}\hskip
2.0pt[s^{9}t]=-192c^{2}(-2+c^{2})x_{2}(qx_{1}-py_{1})y_{2}.$

See Figure 8. Since each coefficient of $\rho_{N}(s,t)$ equals zero, so does
the difference of two coefficients. Since $c>0$, we have that $x_{2}=0$, or
$y_{2}=0$, or $c=\sqrt{2}$, or $qx_{1}=py_{1}$.

Figure 8: The Mathematica code of Case (A1).

If $y_{2}=0$ then we swap the $x$ and $y$ axes, to again reach the case where
$x_{2}=0$. In this case $y_{2}\neq 0$, since $v_{2}\neq(0,0,0)$. Case (A2)
assumes that $x_{2}=0$ and $y_{2}\neq 0$. Case (A13) assumes that
$x_{2},y_{2}\neq 0$, $qx_{1}=py_{1}$, and $x_{1}\neq 0$. Case (A9) assumes
that $x_{2},y_{2}\neq 0$, $qx_{1}=py_{1}$, and $x_{1}=y_{1}=0$. Case (A12)
assumes that $x_{2},y_{2}\neq 0$, $x_{1}=0$, $y_{1}\neq 0$, and $p=0$. Case
(A23) assumes that $x_{2},y_{2}\neq 0$, $qx_{1}\neq py_{1}$, and $c=\sqrt{2}$.
These cases cover all possible options.

  2. (A2)

The case where $x_{2}=0$ and $y_{2}\neq 0$. As shown in Figure 9, we compute

$\textit{coeff}\hskip 2.0pt[s^{3}t]-\textit{coeff}\hskip
2.0pt[s^{5}t]/2=384(-1+c)c^{2}(1+c)x_{1}y_{2}^{2}.$

Since each coefficient is equal to 0, so does this difference. Since $c>0$ and
$c\neq 1$, we conclude that $x_{1}=0$.

Figure 9: The Mathematica code of the first part of Case (A2).

Next, as shown in Figure 10, we compute

$\textit{coeff}\hskip 2.0pt[s^{3}t]+\textit{coeff}\hskip
2.0pt[s^{3}t^{9}]=256c^{2}py_{2}^{2}(3qy_{1}+rz_{1}).$

Since $c,y_{2}\neq 0$, either $p=0$ or $3qy_{1}+rz_{1}=0$. Case (A3) assumes
that $p=0$. Case (A4) assumes that $p\neq 0$ and $3qy_{1}+rz_{1}=0$. Since
$z_{1}\neq 0$, we may rewrite $3qy_{1}+rz_{1}=0$ as $r=-3qy_{1}/z_{1}$.

Figure 10: The Mathematica code of the second part of Case (A2).

  3. (A3)

The case where $x_{1}=x_{2}=p=0$ and $y_{2}\neq 0$. As shown in Figure 11, we
compute

$\displaystyle 10(\textit{coeff}\hskip 2.0pt[s]-\textit{coeff}\hskip
2.0pt[st^{10}])+\textit{coeff}\hskip 2.0pt[st^{6}]+\textit{coeff}\hskip
2.0pt[s^{5}t^{4}]$ $\displaystyle=-384(-1+c)c^{2}(1+c)qy_{2}z_{1}^{2},$
$\displaystyle\textit{coeff}\hskip 2.0pt[s]+\textit{coeff}\hskip
2.0pt[st^{10}]$ $\displaystyle=-32(-1+c)c^{2}(1+c)y_{2}z_{1}(qr+y_{1}z_{1}).$

Since $c>0$, $c\neq 1$, and $y_{2},z_{1}\neq 0$, the first expression above
implies that $q=0$. The second expression leads to $qr+y_{1}z_{1}=0$. Since
$q=0$ and $z_{1}\neq 0$, we conclude that $y_{1}=0$.

Figure 11: The Mathematica code of Case (A3).

Next, we compute $\textit{coeff}\hskip
2.0pt[st^{3}]=-8(-1+c)c^{2}(1+c)ry_{2}^{2}z_{1}$. Since $c>0$, $c>1$, and
$y_{2}\neq 0$, we get that $r=0$. This contradicts the assumption that $C_{2}$
is not centered at the origin, so the current case cannot occur.

  4. (A4)

The case where $x_{1}=x_{2}=0$, $y_{2},p\neq 0$, and $r=-3qy_{1}/z_{1}$. In
this case, we compute $\textit{coeff}\hskip
2.0pt[s^{3}t^{5}]+\textit{coeff}\hskip
2.0pt[s^{7}t^{5}]=-4096c^{2}pqy_{1}^{3}$. Since $c,p\neq 0$, either $q=0$ or
$y_{1}=0$. Case (A5) assumes that $q=0$. Case (A8) assumes that $q\neq 0$ and
$y_{1}=0$. In both cases, the assumption $r=-3qy_{1}/z_{1}$ becomes $r=0$.

  5. (A5)

The case where $x_{1}=x_{2}=q=r=0$ and $y_{2},p\neq 0$. In this case, we
compute $\textit{coeff}\hskip
2.0pt[s^{5}]=-32c^{2}py_{1}y_{2}(2y_{2}-z_{1})(2y_{2}+z_{1})$. Since
$c,p,y_{2}\neq 0$, we get that $y_{1}=0$ or $z_{1}=\pm 2y_{2}$. Case (A6)
assumes that $y_{1}=0$. Case (A7) assumes that $y_{1}\neq 0$ and
$z_{1}=2y_{2}$. If $z_{1}=-2y_{2}$, then we perform a reflection of
$\mathbf{R}^{3}$ about the $xz$-plane. This leads to $z_{1}=2y_{2}$ and does
not affect anything else. Thus, Case (A7) also covers $z_{1}=-2y_{2}$.

  6. (A6)

The case where $x_{1}=x_{2}=y_{1}=q=r=0$ and $y_{2},p\neq 0$. In this case, we
compute $\textit{coeff}\hskip
2.0pt[s^{3}t]=-8c^{2}py_{2}^{2}(y_{2}-z_{1})(y_{2}+z_{1})$. Since
$c,p,y_{2}\neq 0$, we get that $y_{2}=\pm z_{1}$. Without loss of generality,
we assume that $y_{2}=z_{1}$. If $y_{2}=-z_{1}$, we reflect $\mathbf{R}^{3}$
about the $xz$-plane.

We next compute $3\textit{coeff}\hskip 2.0pt[1]+\textit{coeff}\hskip
2.0pt[s^{2}]=6cpz_{1}$. Since $c,p,z_{1}\neq 0$, this coefficient is nonzero.
This contradiction implies that the current case cannot occur.

  7. (A7)

The case where $x_{1}=x_{2}=q=r=0$, $y_{1},y_{2},p\neq 0$, and $z_{1}=2y_{2}$.
We compute $\textit{coeff}\hskip
2.0pt[s^{3}t]=384c^{2}py_{2}^{2}(y_{1}^{2}+y_{2}^{2})$. Since
$c,p,y_{1},y_{2}\neq 0$, this coefficient cannot be zero. This contradiction
implies that the current case cannot occur.

  8. (A8)

The case where $x_{1}=x_{2}=y_{1}=r=0$ and $y_{2},p,q\neq 0$. In this case, we
compute $\textit{coeff}\hskip
2.0pt[s^{5}t^{5}]=256c^{2}py_{2}^{2}(y_{2}-z_{1})(y_{2}+z_{1})$. Since this
coefficient equals zero and $c,p,y_{2}\neq 0$, we have that $y_{2}=\pm z_{1}$.
As before, it suffices to consider the case of $y_{2}=z_{1}$. The other case
is identical after a reflection across the $xz$-plane.

We next compute $3\textit{coeff}\hskip 2.0pt[1]+\textit{coeff}\hskip
2.0pt[s^{2}]=24cpz_{1}$. Since $c,p,z_{1}\neq 0$, the above expression is
nonzero. This contradiction implies that the current case cannot occur.

  9. (A9)

The case where $x_{1}=y_{1}=0$ and $x_{2},y_{2}\neq 0$. We compute

$\displaystyle\textit{coeff}\hskip 2.0pt[st^{5}]-\textit{coeff}\hskip
2.0pt[s^{9}t^{5}]$ $\displaystyle=-512(-1+c)c^{2}(1+c)ry_{2}^{2}z_{1},$
$\displaystyle\textit{coeff}\hskip 2.0pt[st^{9}]$
$\displaystyle=-96c^{2}qx_{2}y_{2}(x_{2}^{2}+y_{2}^{2}+rz_{1}-z_{1}^{2}).$

Since $c>0$, $c\neq 1$, and $y_{2},z_{1}\neq 0$, the first computation above
leads to $r=0$. This leads to $\textit{coeff}\hskip
2.0pt[st^{9}]=-96c^{2}qx_{2}y_{2}(x_{2}^{2}+y_{2}^{2}-z_{1}^{2})$. Since this
equals zero, $z_{1}^{2}=x_{2}^{2}+y_{2}^{2}$ or $q=0$. We rewrite the former
as $z_{1}=\pm\sqrt{x_{2}^{2}+y_{2}^{2}}$. As usual, we may assume that
$z_{1}=\sqrt{x_{2}^{2}+y_{2}^{2}}$, since the other option is symmetric after
a reflection about the $xy$-plane. Case (A10) assumes that
$z_{1}=\sqrt{x_{2}^{2}+y_{2}^{2}}$. Case (A11) assumes that $q=0$.

  10. (A10)

The case where $x_{1}=y_{1}=r=0$, $x_{2},y_{2}\neq 0$, and
$z_{1}=\sqrt{x_{2}^{2}+y_{2}^{2}}$. We compute $\textit{coeff}\hskip
2.0pt[s^{3}]=32(-1+c)(1+c)x_{2}$. Since $c>0$, $c\neq 1$, and $x_{2}\neq 0$,
this coefficient is nonzero. This contradiction implies that the current case
cannot occur.

  11. (A11)

The case where $x_{1}=y_{1}=r=q=0$ and $x_{2},y_{2}\neq 0$. We compute

$\displaystyle\textit{coeff}\hskip 2.0pt[st^{6}]-\textit{coeff}\hskip
2.0pt[s^{9}]$ $\displaystyle=-8c^{2}(-1+c^{2}-p^{2})x_{2}y_{2}^{2},$
$\displaystyle\textit{coeff}\hskip 2.0pt[st^{6}]+\textit{coeff}\hskip
2.0pt[s^{9}]$ $\displaystyle=8c^{2}(-2+c^{2})px_{2}y_{2}^{2}.$

Since $c,x_{2},y_{2}\neq 0$, the first computation leads to $p^{2}=c^{2}-1$.
Since $c\neq\pm 1$, we get that $p\neq 0$. Since the second computation equals
zero, we obtain that $c=\sqrt{2}$. Plugging this into $p^{2}=c^{2}-1$ gives
$p=\pm 1$. If $p=-1$ then we reflect $\mathbf{R}^{3}$ about the $yz$-plane. We
may thus assume that $p=1$, without loss of generality.

We next compute $\textit{coeff}\hskip 2.0pt[s^{5}]=16x_{2}y_{2}^{2}$. Since
$x_{2},y_{2}\neq 0$, this coefficient is nonzero. This contradiction implies
that the current case cannot occur.

  12. (A12)

The case where $x_{1}=p=0$ and $y_{1},x_{2},y_{2}\neq 0$. We compute

$\textit{coeff}\hskip 2.0pt[st]-\textit{coeff}\hskip
2.0pt[st^{9}]+(\textit{coeff}\hskip 2.0pt[st^{3}]-\textit{coeff}\hskip
2.0pt[st^{7}])/2=-384c^{2}rx_{2}y_{1}y_{2}z_{1}.$

Since $c,y_{1},z_{1},x_{2},y_{2}\neq 0$, we get that $r=0$. Since we assume
that $C_{2}$ is not centered at the origin, this implies that $q\neq 0$.

We next compute

$\textit{coeff}\hskip 2.0pt[st^{9}]-\textit{coeff}\hskip
2.0pt[s^{9}t]=-192c^{2}qx_{2}y_{2}(x_{2}^{2}-3y_{1}^{2}+y_{2}^{2}-z_{1}^{2}).$

Since the above equals zero, we have that
$z_{1}=\pm\sqrt{x_{2}^{2}-3y_{1}^{2}+y_{2}^{2}}$. After possibly reflecting
$\mathbf{R}^{3}$ about the $xy$-plane, we may assume that
$z_{1}=\sqrt{x_{2}^{2}-3y_{1}^{2}+y_{2}^{2}}$. We then compute
$\textit{coeff}\hskip 2.0pt[s^{3}t^{9}]-\textit{coeff}\hskip
2.0pt[s^{7}t]=256qx_{2}y_{1}^{2}y_{2}$. Since $q,x_{2},y_{1},y_{2}\neq 0$,
this expression is nonzero. This contradiction implies that the current case
cannot occur.

  13. (A13)

The case where $x_{1},x_{2},y_{2}\neq 0$ and $qx_{1}=py_{1}$. Since $x_{1}\neq
0$, we may rewrite $qx_{1}=py_{1}$ as $q=py_{1}/x_{1}$. We then compute

$\textit{coeff}\hskip 2.0pt[st]-\textit{coeff}\hskip
2.0pt[st^{9}]=-192c^{2}x_{1}^{3}x_{2}y_{1}(px_{1}x_{2}y_{1}+2px_{1}^{2}y_{2}-px_{2}^{2}y_{2}+3py_{1}^{2}y_{2}-py_{2}^{3}+rx_{1}y_{2}z_{1}+py_{2}z_{1}^{2}).$

For this to equal zero, either $y_{1}=0$ or
$r=p(-x_{1}x_{2}y_{1}-2x_{1}^{2}y_{2}+x_{2}^{2}y_{2}-3y_{1}^{2}y_{2}+y_{2}^{3}-y_{2}z_{1}^{2})/(x_{1}y_{2}z_{1})$.
When $y_{1}=0$, the assumption $q=py_{1}/x_{1}$ implies that $q=0$. Case (A14)
assumes that $y_{1}=q=0$. Case (A15) assumes that $y_{1}\neq 0$ and
$r=p(-x_{1}x_{2}y_{1}-2x_{1}^{2}y_{2}+x_{2}^{2}y_{2}-3y_{1}^{2}y_{2}+y_{2}^{3}-y_{2}z_{1}^{2})/(x_{1}y_{2}z_{1})$.

  14. (A14)

The case where $x_{1},x_{2},y_{2}\neq 0$ and $y_{1}=q=0$. We compute

$\displaystyle\textit{coeff}\hskip 2.0pt[s]+\textit{coeff}\hskip
2.0pt[st^{10}]+\textit{coeff}\hskip 2.0pt[s^{9}]+\textit{coeff}\hskip
2.0pt[s^{9}t^{10}]$ $\displaystyle=-32c^{2}px_{1}x_{2}y_{2}^{2},$
$\displaystyle\textit{coeff}\hskip 2.0pt[s]+\textit{coeff}\hskip
2.0pt[st^{10}]-\textit{coeff}\hskip 2.0pt[s^{9}]-\textit{coeff}\hskip
2.0pt[s^{9}t^{10}]$ $\displaystyle=-16c^{2}(-2+c^{2})x_{1}x_{2}y_{2}^{2}.$

Since $x_{1},x_{2},y_{2},c\neq 0$, the first expression leads to $p=0$ and the
second to $c=\sqrt{2}$.

We next compute $\textit{coeff}\hskip 2.0pt[st^{2}]+\textit{coeff}\hskip
2.0pt[s^{9}t^{8}]=-96rx_{2}y_{2}^{2}z_{1}$. Since this equals zero, we get
that $r=0$. This is impossible, since we assume that $C_{2}$ is not centered
at the origin. Thus, this case cannot occur.

  15. (A15)

The case where $x_{1},x_{2},y_{1},y_{2}\neq 0$, $q=py_{1}/x_{1}$, and
$r=p(-x_{1}x_{2}y_{1}-2x_{1}^{2}y_{2}+x_{2}^{2}y_{2}-3y_{1}^{2}y_{2}+y_{2}^{3}-y_{2}z_{1}^{2})/(x_{1}y_{2}z_{1})$.
We compute

$\textit{coeff}\hskip 2.0pt[s^{3}t]-\textit{coeff}\hskip
2.0pt[s^{3}t^{9}]=-256px_{1}^{3}y_{2}(-x_{2}y_{1}+x_{1}y_{2})(c^{2}x_{1}x_{2}-y_{1}y_{2})(x_{1}x_{2}+y_{1}y_{2}).$

For this expression to be zero, either $p=0$, or $x_{2}y_{1}=x_{1}y_{2}$, or
$c^{2}x_{1}x_{2}=y_{1}y_{2}$, or $x_{1}x_{2}=-y_{1}y_{2}$. When $p=0$, the
assumptions imply that $q=r=0$. This is impossible, since we assume that
$C_{2}$ is not centered at the origin. Case (A16) assumes that
$c^{2}x_{1}x_{2}=y_{1}y_{2}$. Case (A19) assumes that
$x_{1}x_{2}=-y_{1}y_{2}$. Case (A22) assumes that $p\neq 0$ and
$x_{2}y_{1}=x_{1}y_{2}$.

  16. (A16)

The case where $x_{1},x_{2},y_{1},y_{2}\neq 0$, $q=py_{1}/x_{1}$,
$c^{2}x_{1}x_{2}=y_{1}y_{2}$, and
$r=p(-x_{1}x_{2}y_{1}-2x_{1}^{2}y_{2}+x_{2}^{2}y_{2}-3y_{1}^{2}y_{2}+y_{2}^{3}-y_{2}z_{1}^{2})/(x_{1}y_{2}z_{1})$.
We rewrite $c^{2}x_{1}x_{2}=y_{1}y_{2}$ as $y_{1}=c^{2}x_{1}x_{2}/y_{2}$. We
then compute

$\displaystyle\textit{coeff}\hskip 2.0pt[st]=48c^{4}x_{1}x_{2}^{2}y_{2}^{4}($
$\displaystyle
c^{2}p^{2}x_{1}^{2}x_{2}^{2}+3c^{4}p^{2}x_{1}^{2}x_{2}^{2}-c^{2}x_{1}^{4}x_{2}^{2}-3c^{4}x_{1}^{4}x_{2}^{2}+2x_{1}^{2}y_{2}^{2}-2c^{2}x_{1}^{2}y_{2}^{2}+2p^{2}x_{1}^{2}y_{2}^{2}$
$\displaystyle-2x_{1}^{4}y_{2}^{2}-2p^{2}x_{2}^{2}y_{2}^{2}+2x_{1}^{2}x_{2}^{2}y_{2}^{2}-2p^{2}y_{2}^{4}+2x_{1}^{2}y_{2}^{4}+2p^{2}y_{2}^{2}z_{1}^{2}-2x_{1}^{2}y_{2}^{2}z_{1}^{2}).$

Since $c,x_{1},x_{2},y_{2}\neq 0$, the expression in the parentheses equals
zero. We rewrite this expression as

$\displaystyle
2y_{2}^{2}z_{1}^{2}(x_{1}^{2}-p^{2})=c^{2}p^{2}x_{1}^{2}x_{2}^{2}$
$\displaystyle+3c^{4}p^{2}x_{1}^{2}x_{2}^{2}-c^{2}x_{1}^{4}x_{2}^{2}-3c^{4}x_{1}^{4}x_{2}^{2}+2x_{1}^{2}y_{2}^{2}-2c^{2}x_{1}^{2}y_{2}^{2}$
$\displaystyle+2p^{2}x_{1}^{2}y_{2}^{2}-2x_{1}^{4}y_{2}^{2}-2p^{2}x_{2}^{2}y_{2}^{2}+2x_{1}^{2}x_{2}^{2}y_{2}^{2}-2p^{2}y_{2}^{4}+2x_{1}^{2}y_{2}^{4}.$
(18)

We denote the right-hand side of the above equation as $G$. Case (A17) assumes
that $x_{1}=p$. In that case, $G=0$ and the assumption $q=py_{1}/x_{1}$
implies that $q=y_{1}$. We do not require the assumption on $r$ in case (A17),
so we ignore it. If $x_{1}=-p$ then we negate ${\bf v}_{1}$, to again obtain
that $x_{1}=p$. This does not change anything else in the current situation,
so $x_{1}=-p$ is also covered by Case (A17).

When $x_{1}\neq\pm p$, Equation (18) leads to
$z_{1}=\pm\sqrt{G/(2y_{2}^{2}(x_{1}^{2}-p^{2}))}$. By potentially reflecting
$\mathbf{R}^{3}$ about the $xy$-plane, we may assume that
$z_{1}=\sqrt{G/(2y_{2}^{2}(x_{1}^{2}-p^{2}))}$. This scenario is studied in
Case (A18).

  17. (A17)

The case where $x_{1},x_{2},y_{1},y_{2}\neq 0$, $p=x_{1}$, and
$q=y_{1}=c^{2}x_{1}x_{2}/y_{2}$. We compute $\textit{coeff}\hskip
2.0pt[t^{10}]=-(-1+c)c(1+c)x_{2}^{2}y_{2}^{7}$. Since $c>0$, $c\neq 1$ and
$x_{2},y_{2}\neq 0$, this coefficient is nonzero. This contradiction implies
that the current case cannot occur.

  18. (A18)

The case where $x_{1},x_{2},y_{1},y_{2}\neq 0$, $q=py_{1}/x_{1}$,
$y_{1}=c^{2}x_{1}x_{2}/y_{2}$, $x_{1}\neq\pm p$,
$z_{1}=\sqrt{G/(2y_{2}^{2}(x_{1}^{2}-p^{2}))}$, and
$r=p(-x_{1}x_{2}y_{1}-2x_{1}^{2}y_{2}+x_{2}^{2}y_{2}-3y_{1}^{2}y_{2}+y_{2}^{3}-y_{2}z_{1}^{2})/(x_{1}y_{2}z_{1})$.
We compute $\textit{coeff}\hskip
2.0pt[s^{3}t]=320(-1+c)c^{4}(1+c)(p-x_{1})^{2}x_{1}(p+x_{1})^{2}x_{2}^{2}y_{2}^{6}$.
Since $c>0$, $c\neq 1$, $x_{1}\neq\pm p$, and $x_{1},x_{2},y_{2}\neq 0$, this
coefficient is nonzero. This contradiction implies that the current case
cannot occur.

  19. (A19)

The case where $x_{1},x_{2},y_{1},y_{2}\neq 0$, $q=py_{1}/x_{1}$,
$x_{1}x_{2}=-y_{1}y_{2}$, and
$r=p(-x_{1}x_{2}y_{1}-2x_{1}^{2}y_{2}+x_{2}^{2}y_{2}-3y_{1}^{2}y_{2}+y_{2}^{3}-y_{2}z_{1}^{2})/(x_{1}y_{2}z_{1})$.
Since $x_{2}\neq 0$, we may rewrite $x_{1}x_{2}=-y_{1}y_{2}$ as
$x_{1}=-y_{1}y_{2}/x_{2}$. We compute

$\displaystyle\textit{coeff}\hskip
2.0pt[st]=-96c^{2}x_{2}^{5}y_{1}y_{2}^{3}(p^{2}x_{2}^{6}$
$\displaystyle-p^{2}x_{2}^{4}y_{1}^{2}+p^{2}x_{2}^{4}y_{2}^{2}-x_{2}^{2}y_{1}^{2}y_{2}^{2}+c^{2}x_{2}^{2}y_{1}^{2}y_{2}^{2}-p^{2}x_{2}^{2}y_{1}^{2}y_{2}^{2}$
$\displaystyle-
x_{2}^{4}y_{1}^{2}y_{2}^{2}+x_{2}^{2}y_{1}^{4}y_{2}^{2}-x_{2}^{2}y_{1}^{2}y_{2}^{4}+y_{1}^{4}y_{2}^{4}-p^{2}x_{2}^{4}z_{1}^{2}+x_{2}^{2}y_{1}^{2}y_{2}^{2}z_{1}^{2}).$

Since $c,x_{2},y_{1},y_{2}\neq 0$, the expression in the parentheses equals
zero. We rewrite this as

$\displaystyle
z_{1}^{2}x_{2}^{2}(p^{2}x_{2}^{2}-y_{1}^{2}y_{2}^{2})=p^{2}x_{2}^{6}-p^{2}x_{2}^{4}y_{1}^{2}$
$\displaystyle+p^{2}x_{2}^{4}y_{2}^{2}-x_{2}^{2}y_{1}^{2}y_{2}^{2}+c^{2}x_{2}^{2}y_{1}^{2}y_{2}^{2}$
$\displaystyle-p^{2}x_{2}^{2}y_{1}^{2}y_{2}^{2}-x_{2}^{4}y_{1}^{2}y_{2}^{2}+x_{2}^{2}y_{1}^{4}y_{2}^{2}-x_{2}^{2}y_{1}^{2}y_{2}^{4}+y_{1}^{4}y_{2}^{4}.$

We denote the right-hand side of the above equation as $H$. Case (A20) assumes
that $px_{2}=y_{1}y_{2}$, so $H=0$. We do not require the assumption on $r$ in
case (A20), so we ignore it. The case where $px_{2}=-y_{1}y_{2}$ reduces to
case (A20) after negating $\mathbf{v}_{1}$. Case (A21) assumes that
$px_{2}\neq\pm y_{1}y_{2}$. This implies that
$z_{1}=\sqrt{H/(x_{2}^{2}(p^{2}x_{2}^{2}-y_{1}^{2}y_{2}^{2}))}$, possibly
after a reflection of $\mathbf{R}^{3}$ about the $xy$-plane.

  20. (A20)

The case where $x_{1},x_{2},y_{1},y_{2}\neq 0$, $q=py_{1}/x_{1}$,
$x_{1}=-y_{1}y_{2}/x_{2}$, and $px_{2}=y_{1}y_{2}$. Since $x_{2}\neq 0$, we
may rewrite $px_{2}\neq\pm y_{1}y_{2}$ as $p=y_{1}y_{2}/x_{2}$. We compute

$\textit{coeff}\hskip 2.0pt[st]=-24(-1+c)c^{2}(1+c)x_{2}^{7}y_{1}y_{2}.$

Since $c>0$, $c\neq 1$, and $x_{2},y_{1},y_{2}\neq 0$, this coefficient is
nonzero. This contradiction implies that the current case cannot occur.

  21. (A21)

The case where $x_{1},x_{2},y_{1},y_{2}\neq 0$, $q=py_{1}/x_{1}$,
$x_{1}=-y_{1}y_{2}/x_{2}$,
$r=p(-x_{1}x_{2}y_{1}-2x_{1}^{2}y_{2}+x_{2}^{2}y_{2}-3y_{1}^{2}y_{2}+y_{2}^{3}-y_{2}z_{1}^{2})/(x_{1}y_{2}z_{1})$,
$z_{1}=\sqrt{H/(x_{2}^{2}(p^{2}x_{2}^{2}-y_{1}^{2}y_{2}^{2}))}$, and
$px_{2}\neq\pm y_{1}y_{2}$. We compute

$\textit{coeff}\hskip
2.0pt[s^{3}t]=64(-1+c)(1+c)(1+6c^{2})x_{2}^{5}y_{1}y_{2}^{3}(px_{2}-y_{1}y_{2})^{2}(px_{2}+y_{1}y_{2})^{2}.$

Since $c>0$, $c\neq 1$, $x_{2},y_{1},y_{2}\neq 0$, and $px_{2}\neq\pm
y_{1}y_{2}$, this coefficient is nonzero. This contradiction implies that the
current case cannot occur.

  22. (A22)

The case where $x_{1},x_{2},y_{1},y_{2},p\neq 0$, $q=py_{1}/x_{1}$,
$x_{2}y_{1}=x_{1}y_{2}$, and
$r=p(-x_{1}x_{2}y_{1}-2x_{1}^{2}y_{2}+x_{2}^{2}y_{2}-3y_{1}^{2}y_{2}+y_{2}^{3}-y_{2}z_{1}^{2})/(x_{1}y_{2}z_{1})$.
Since $y_{2}\neq 0$, we may rewrite $x_{2}y_{1}=x_{1}y_{2}$ as
$x_{1}=x_{2}y_{1}/y_{2}$. We compute

$\textit{coeff}\hskip 2.0pt[t]+\textit{coeff}\hskip
2.0pt[s^{10}t^{9}]=32(-1+c)c(1+c)px_{2}^{4}y_{1}y_{2}^{8}(x_{2}^{2}+y_{2}^{2}-z_{1}^{2}).$

Since $c>0$, $c\neq 1$, and $p,x_{2},y_{1},y_{2}\neq 0$, we conclude that
$z_{1}=\pm\sqrt{x_{2}^{2}+y_{2}^{2}}$. We may assume that
$z_{1}=\sqrt{x_{2}^{2}+y_{2}^{2}}$, possibly after a reflection of
$\mathbf{R}^{3}$ about the $xy$-plane.

We next compute

$\textit{coeff}\hskip 2.0pt[t^{5}]+\textit{coeff}\hskip
2.0pt[s^{10}t^{5}]=-512(-1+c)c(1+c)px_{2}^{4}y_{1}^{3}y_{2}^{4}(x_{2}^{2}+y_{2}^{2}).$

Since $c>0$, $c\neq 1$, $p,x_{2},y_{1},y_{2}\neq 0$, the above coefficient is
nonzero. This contradiction implies that the current case cannot occur.

  23. (A23)

The case where $x_{2},y_{2}\neq 0$, $qx_{1}\neq py_{1}$, and $c=\sqrt{2}$. We
compute

$\textit{coeff}\hskip 2.0pt[s^{3}t]-\textit{coeff}\hskip
2.0pt[s^{7}t]=2304x_{2}(qx_{1}-py_{1})y_{2}.$

By the assumptions of this case, the above expression is nonzero. This
contradiction implies that the current case cannot occur.

The case of two ellipses centered at the origin. It remains to consider the
case where $p=q=r=0$. That is, the case where both ellipses are centered at
the origin. In the case, we switch to a different parameterization of $C_{2}$.
By Lemma A.1(b), there exist
$\mathbf{v}_{1}=(x_{1},y_{1},z_{1}),\mathbf{v}_{2}=(x_{2},0,z_{2})$ such that

$\displaystyle\gamma_{1}(s)$
$\displaystyle=\left(\frac{1-s^{2}}{1+s^{2}},c\cdot\frac{2s}{1+s^{2}},0\right),$
$\displaystyle\gamma_{2}(t)$
$\displaystyle=\frac{t^{2}-1}{t^{2}+1}\mathbf{v}_{1}+\frac{2t}{t^{2}+1}\mathbf{v}_{2}.$
(19)

  1. (B1)

The general case. We compute $\textit{coeff}\hskip
2.0pt[st]=-48c^{2}x_{2}y_{1}^{2}(x_{1}x_{2}+z_{1}z_{2})$. Since this
coefficient equals zero, we have that $x_{2}=0$, or $y_{1}=0$, or
$x_{1}x_{2}=-z_{1}z_{2}$. Case (B2) assumes that $x_{2}=0$. Case (B5) assumes
that $y_{1}=0$. Case (B6) assumes that $x_{2},y_{1}\neq 0$ and
$x_{1}x_{2}=-z_{1}z_{2}$.

  2. (B2)

The case where $x_{2}=0$. Since $\mathbf{v}_{2}\neq 0$, we have that
$z_{2}\neq 0$. We compute

$\textit{coeff}\hskip 2.0pt[t]=-8(-1+c)c(1+c)y_{1}z_{1}^{2}z_{2}^{2}.$

For this coefficient to equal zero, either $y_{1}=0$ or $z_{1}=0$. Case (B3)
assumes that $y_{1}=0$. Case (B4) assumes that $y_{1}\neq 0$ and $z_{1}=0$.

  3. (B3)

The case where $y_{1}=x_{2}=0$ and $z_{2}\neq 0$. Since $\mathbf{v}_{1}$ and
$\mathbf{v}_{2}$ span a plane, we have that $x_{1}\neq 0$. We compute
$\textit{coeff}\hskip 2.0pt[st]=16(-1+c)(1+c)x_{1}z_{1}^{2}z_{2}^{2}$. Since
$x_{1},z_{2}\neq 0$ and $c\neq\pm 1$, we get that $z_{1}=0$.

We next compute

$2\textit{coeff}\hskip 2.0pt[st]+\textit{coeff}\hskip
2.0pt[st^{3}]=-64(-1+c)(1+c)x_{1}(c^{2}x_{1}^{2}+z_{2}^{2}-c^{2}z_{2}^{2}).$

For this to equal zero, we must have that
$c^{2}x_{1}^{2}+z_{2}^{2}-c^{2}z_{2}^{2}=0$. We rewrite this as
$z_{2}^{2}=c^{2}x_{1}^{2}/(c^{2}-1)$.

We claim that, in this case, $C_{1}$ and $C_{2}$ are matching ellipses.
Indeed, with (19) in mind, we obtain (1) with $m=a=c^{2}$. By the assumptions
of this case, we get that
$\gamma_{2}(t)=\frac{t^{2}-1}{t^{2}+1}(x_{1},0,0)+\frac{2t}{t^{2}+1}(0,0,z_{2})$.
Combining this with $z_{2}^{2}=c^{2}x_{1}^{2}/(c^{2}-1)$ leads to (2) with
$m=c^{2}$ and $b=z_{2}^{2}$.

  4. (B4)

The case where $z_{1}=x_{2}=0$ and $y_{1}\neq 0$. We compute

$2\textit{coeff}\hskip 2.0pt[st]+\textit{coeff}\hskip
2.0pt[st^{3}]=-128(-1+c)c^{2}(1+c)x_{1}y_{1}^{2}.$

Since this equals zero, we have that $x_{1}=0$. We then compute

$2\textit{coeff}\hskip 2.0pt[s^{2}t]+\textit{coeff}\hskip
2.0pt[s^{2}t^{3}]=-128(-1+c)c(1+c)y_{1}(y_{1}^{2}-z_{2}^{2}+c^{2}z_{2}^{2}).$

Since this equals zero, we get that $y_{1}^{2}-z_{2}^{2}+c^{2}z_{2}^{2}=0$. We
rewrite this as $z_{2}^{2}=-y_{1}^{2}/(c^{2}-1)$.

We claim that, in this case, $C_{1}$ and $C_{2}$ are matching ellipses.
Indeed, we switch the $x$ and $y$ axes and set $m=1/c^{2}$. Then, with (19) in
mind, we obtain (1) with $a=1$ (after switching the axes). By the assumptions
of this case, we get that
$\gamma_{2}(t)=\frac{t^{2}-1}{t^{2}+1}(0,y_{1},0)+\frac{2t}{t^{2}+1}(0,0,z_{2})$.
Combining this with $z_{2}^{2}=-y_{1}^{2}/(c^{2}-1)$ leads to (2) with
$b=y_{2}^{2}$ (after switching the axes).

  5. (B5)

The case where $y_{1}=0$. Since we also have that $y_{2}=0$, the ellipse
$C_{2}$ is contained in the $xz$-plane. We may set
$\mathbf{v}_{2}=(x_{2},0,z_{2})$ in (19) that is orthogonal to
$\mathbf{v}_{1}=(x_{1},0,z_{1})$. After this change, there exists a nonzero
$r\in\mathbf{R}$ such that $\mathbf{v}_{2}=r\cdot(-z_{1},0,x_{1})$. We compute

$2\textit{coeff}\hskip 2.0pt[st]-\textit{coeff}\hskip
2.0pt[s^{3}t]=-192(-1+c)(1+c)r^{2}x_{1}z_{1}^{2}.$

Since the above equals zero, $x_{1}=0$ or $z_{1}=0$. By possibly switching the
$x$ and $z$ axes, we may assume that $z_{1}=0$. Then,
$\mathbf{v}_{1}=(x_{1},0,0)$ and $\mathbf{v}_{2}=(0,0,z_{2})$, where
$x_{1},z_{2}\neq 0$. We compute

$2\textit{coeff}\hskip 2.0pt[st]+\textit{coeff}\hskip
2.0pt[st^{3}]=-64(-1+c)(1+c)x_{1}(c^{2}x_{1}^{2}+z_{2}^{2}-c^{2}z_{2}^{2}).$

Since $c>0$ and $x_{1},c\neq 1$, we obtain that
$c^{2}x_{1}^{2}+z_{2}^{2}-c^{2}z_{2}^{2}=0$. This is the same situation as in
the middle of Case (B3). By repeating the same analysis as in (B3), we obtain
matching ellipses.

  6. (B6)

The case where $x_{1}x_{2}=-z_{1}z_{2}$ and $x_{2},y_{1}\neq 0$. We rewrite
$x_{1}x_{2}=-z_{1}z_{2}$ as $x_{1}=-z_{1}z_{2}/x_{2}$. We compute
$\textit{coeff}\hskip 2.0pt[1]=4cx_{2}^{7}y_{1}(-x_{2}+cy_{1})(x_{2}+cy_{1})$.
Since this equals zero, we get that $x_{2}=\pm cy_{1}$. By potentially
reflecting $\mathbf{R}^{3}$ about the $yz$-plane, we may assume that
$x_{2}=cy_{1}$.

We swap the positions of $\frac{t^{2}-1}{t^{2}+1}$ and $\frac{2t}{t^{2}+1}$ in
(19). This only changes the single point that is not parameterized by (19).
Equivalently, we may switch the roles of $\mathbf{v}_{1}$ and $\mathbf{v}_{2}$
in (19). After this switch, we compute $\textit{coeff}\hskip
2.0pt[1]+\textit{coeff}\hskip
2.0pt[t^{10}]=2c^{6}y_{1}^{6}z_{1}^{2}z_{2}^{2}$. Since this expression equals
zero and $c,y_{1}\neq 0$, we have that $z_{1}=0$ or $z_{2}=0$. In either case,
the assumption $x_{1}x_{2}=-z_{1}z_{2}$ turns to $x_{1}=0$. Case (B7) assumes
that $z_{1}=0$. Case (B8) assumes that $z_{2}=0$.

  7. (B7)

The case where $x_{1}=z_{1}=0$, $x_{2}=cy_{1}$, and $x_{2},y_{1}\neq 0$.
Instead of the switched $\mathbf{v}_{1}$ and $\mathbf{v}_{2}$ from case (B6),
we return to original vectors. We compute

$2\textit{coeff}\hskip 2.0pt[s]-\textit{coeff}\hskip
2.0pt[t]=-24(-1+c)c^{3}(1+c)y_{1}^{3}.$

This is nonzero, since $y_{1}\neq 0$, $c>0$, and $c\neq 1$. This contradiction
implies that the current case cannot occur.

  8. (B8)

The case where $x_{1}=z_{2}=0$, $x_{2}=cy_{1}$, and $x_{2},y_{1}\neq 0$. As in
Case (B6), we switch the roles of $\mathbf{v}_{1}$ and $\mathbf{v}_{2}$. We
then compute

$4\textit{coeff}\hskip 2.0pt[st^{3}]+\textit{coeff}\hskip
2.0pt[st^{5}]=48(-1+c)c^{3}(1+c)y_{1}^{3}.$

This is nonzero, since $y_{1}\neq 0$, $c>0$, and $c\neq 1$. This contradiction
implies that the current case cannot occur.

In all cases, we obtained either matching ellipses or a contradiction. Thus,
two ellipses span many distances unless they are matching or aligned circles.

##  Appendix B Mathematica computations: the case of two hyperbolas

In this appendix, we complete the proof of Lemma 7.1 for two hyperbolas, by
using Wolfram Mathematica. In particular, we assume that all coefficients of
$\rho_{N}(s,t)$ are zero, and show that this implies that the hyperbolas span
many distances. As explained in Section 7, there exist $c>0$,
$p,q,r\in\mathbf{R}$, and vectors
$\mathbf{v}_{1}=(x_{1},y_{1},z_{1}),\mathbf{v}_{2}=(x_{2},y_{2},z_{2})$, such
that

$\displaystyle\gamma_{1}(s)$
$\displaystyle=\left(\frac{s^{2}+1}{2s},c\cdot\frac{1-s^{2}}{2s},0\right),$
$\displaystyle\gamma_{2}(t)$
$\displaystyle=(p,q,r)+\frac{t^{2}+1}{2t}\cdot\mathbf{v}_{1}+\frac{t^{2}-1}{2t}\cdot\mathbf{v}_{2}.$

We now perform a case analysis, as in Appendix A. Figure 12 includes the code
for the beginning of Case (C1).

Figure 12: The Mathematica code of Case (C1).

  1. (C1)

The general case. For our first step, we compute

$\displaystyle\textit{coeff}\hskip 2.0pt[s^{10}t^{8}]+$
$\displaystyle\textit{coeff}\hskip 2.0pt[s^{10}t^{2}]+\textit{coeff}\hskip
2.0pt[s^{10}t^{4}]/3+\textit{coeff}\hskip 2.0pt[s^{10}t^{6}]/3=$
$\displaystyle 4(1+c^{2})(c\cdot y_{2}-x_{2})\left((c\cdot
x_{1}+y_{1})^{2}+(c\cdot
x_{2}+y_{2})^{2}+(z_{1}^{2}+z_{2}^{2})(1+c^{2})\right),$
$\displaystyle\textit{coeff}\hskip 2.0pt[s^{10}t^{8}]-$
$\displaystyle\textit{coeff}\hskip 2.0pt[s^{10}t^{2}]+\textit{coeff}\hskip
2.0pt[s^{10}t^{4}]/3-\textit{coeff}\hskip 2.0pt[s^{10}t^{6}]/3=$
$\displaystyle 4(1+c^{2})(c\cdot y_{1}-x_{1})\left((c\cdot
x_{1}+y_{1})^{2}+(c\cdot
x_{2}+y_{2})^{2}+(z_{1}^{2}+z_{2}^{2})(1+c^{2})\right).$

Since the above expressions equal zero, either
$(cx_{1}+y_{1})^{2}+(cx_{2}+y_{2})^{2}+(z_{1}^{2}+z_{2}^{2})(1+c^{2})=0$ or
$x_{1}=c\cdot y_{1}$ and $x_{2}=c\cdot y_{2}$. We first assume that
$(cx_{1}+y_{1})^{2}+(cx_{2}+y_{2})^{2}+(z_{1}^{2}+z_{2}^{2})(1+c^{2})=0$,
which implies that $z_{1}=z_{2}=0$. This in turn implies that the hyperbola
$C_{2}$ is contained in a plane parallel to the $xy$-plane. By Lemma 3.1, the
two hyperbolas span many distances.

It remains to consider the case where $x_{1}=c\cdot y_{1}$ and $x_{2}=c\cdot
y_{2}$. In this case, we compute

$\textit{coeff}\hskip 2.0pt[t^{5}]=16c(1+c^{2})^{2}r(y_{2}z_{1}-y_{1}z_{2}).$

Since the above coefficient equals zero, either $r=0$ or
$y_{2}z_{1}=y_{1}z_{2}$. Case (C2) assumes that $y_{2}z_{1}=y_{1}z_{2}$. Case
(C3) assumes that $y_{2}z_{1}\neq y_{1}z_{2}$ and $r=0$.

  2. (C2)

The case where $x_{1}=cy_{1}$, $x_{2}=cy_{2}$, and $y_{2}z_{1}=y_{1}z_{2}$. We
first assume that $y_{1}=0$. The assumption $x_{1}=cy_{1}$ implies that
$x_{1}=0$. Since ${\bf v}_{1}$ is non-zero, we get that $z_{1}\neq 0$. Since
${\bf v}_{1}$ and ${\bf v}_{2}$ are independent, we have that $y_{2}\neq 0$
(note that $y_{2}=0$ also implies that $x_{2}=0$). This contradicts
$y_{2}z_{1}=y_{1}z_{2}$, so $y_{1}\neq 0$.

We set $z_{2}=y_{2}z_{1}/y_{1}$ and compute

$\textit{coeff}\hskip 2.0pt[t^{2}]-\textit{coeff}\hskip
2.0pt[t^{4}]=-4c(1+c^{2})y_{1}^{3}\left(y_{1}^{2}\cdot(1-c^{2})^{2}+z_{1}^{2}(1+c^{2})\right).$

Since this expression equals zero, we have that
$y_{1}^{2}\cdot(1-c^{2})^{2}+z_{1}^{2}(1+c^{2})=0$. However,
$y_{1}^{2}\cdot(1-c^{2})^{2}\geq 0$ and $z_{1}^{2}(1+c^{2})>0$. This
contradiction implies that the current case cannot occur.

  3. (C3)

The case where $x_{1}=cy_{1}$, $x_{2}=cy_{2}$, $y_{2}z_{1}\neq y_{1}z_{2}$,
and $r=0$. We compute

$\textit{coeff}\hskip
2.0pt[st^{5}]=128c^{2}(1+c^{2})(y_{1}z_{2}-y_{2}z_{1})(y_{1}z_{1}-y_{2}z_{2}).$

Since this coefficient equals zero, we have that $y_{1}z_{1}=y_{2}z_{2}$. Case
(C4) assumes that $y_{1}=0$. Case (C5) assumes that $y_{1}\neq 0$.

  4. (C4)

The case where $x_{1}=cy_{1}$, $x_{2}=cy_{2}$, $y_{2}z_{1}\neq y_{1}z_{2}$,
$y_{1}z_{1}=y_{2}z_{2}$, and $y_{1}=r=0$. By the assumption $x_{1}=cy_{1}$, we
have that $x_{1}=0$. Since ${\bf v}_{1}$ is non-zero, we have that $z_{1}\neq
0$. We also have that $y_{2}\neq 0$, since otherwise the above argument would
imply that ${\bf v}_{1}$ and ${\bf v}_{2}$ are parallel. Then,
$y_{1}z_{1}=y_{2}z_{2}$ leads to $z_{2}=0$.

We compute

$\textit{coeff}\hskip
2.0pt[s^{6}]=-6c(1+c^{2})y_{2}(y_{2}^{2}(1+c^{2})+z_{1}^{2})^{2}.$

Since $y_{2}\neq 0$ and $c\neq 0$, the above coefficient is nonzero. This
contradiction implies that the current case cannot occur.

  5. (C5)

The case where $x_{1}=cy_{1}$, $x_{2}=cy_{2}$, $y_{2}z_{1}\neq y_{1}z_{2}$,
$r=0$, $y_{1}z_{1}=y_{2}z_{2}$, and $y_{1}\neq 0$. In this case, we may write
$y_{1}z_{1}=y_{2}z_{2}$ as $z_{1}=y_{2}z_{2}/y_{1}$. Assume that $z_{2}=0$.
Then $z_{1}=y_{2}z_{2}/y_{1}=0$, which implies that the hyperbola $C_{2}$ is
contained in the $xy$-plane. In this case, Theorem 1.1 implies that the two
hyperbolas span many distances.

It remains to consider the case where $z_{2}\neq 0$. We compute

$\textit{coeff}\hskip
2.0pt[s^{2}]=2c(y_{1}-y_{2})^{3}\left(y_{1}^{2}(1+c^{2})+z_{2}^{2}\right)\left(y_{1}(1-c^{2})^{2}+z_{2}^{2}(1+c^{2})\right).$

Since the above coefficient equals zero and $y_{2},z_{2}\neq 0$, we get that
$y_{1}=y_{2}$. This in turn implies that
$y_{2}z_{1}=y_{1}z_{1}=y_{2}z_{2}=y_{1}z_{2}$. This contradiction to the
assumption $y_{2}z_{1}\neq y_{1}z_{2}$ implies that the current case cannot
occur.

The above analysis covers all possible cases, so two hyperbolas always span
many distances.