#  Only quadrics have pseudo-caustics
–
on caustics of Riemannian, pseudo-Euclidean and projective billiards in higher
dimensions

Corentin Fierobe  Institute of Science and Technology Austria, Am Campus 1,
3400 Klosterneuburg, Austria<EMAIL_ADDRESS>
###### Abstract.

This papers studies properties of caustics of different billiard models in
dimension $d$ at least $3$, namely of billiards in $\mathbb{R}^{d}$ whose law
of reflection is defined by 1) a Riemannian metric projectively equivalent to
the Euclidean one; 2) a constant non-degenerate quadratic form (pseudo-
Euclidean billiards); 3) a smooth field of transverse lines to the boundary
defining a law of reflection (projective billiards). Case 1) and 2) are
particular cases of 3). The paper gives a necessary and sufficient condition
so that if such billiards have a caustic then the latter is a quadric. In the
case of pseudo-Euclidean billiards, we even show that the only billiards
having a caustic are the quadrics, for which the caustics are pseudo-confocal
quadrics.

###### Contents

  1. 1 Introduction
  2. 2 Riemannian, pseudo-Euclidean and projective billiards
  3. 3 Admissible hyperplanes
  4. 4 Proof of Theorem 17
  5. 5 Only quadrics have pseudo-caustics

## 1 Introduction

The study of the light’s behaviour in a homogeneous environment bounded with
mirrors is of great interest and has fundamental applications, for example in
optical engineering or in fundamental physics, e.g. to control laser beams of
particles, or to study the existence of regions with no light, but also the
opposite phenomenon, the so-called caustics, which are spots along curves with
an intense concentration of light.

These systems can be modelized by mathematical billiards, as domains in which
one can imagine a ray of light evolving by either going straight forward when
no obstacles are on its way, or bouncing on such an obstacle according to a
certain law of reflection, for example the classical law of optics angle of
incidence = angle of reflection.

This law of reflection takes various expressions, depending on which physical
phenomenon one decides to study. One can for example consider that the mirrors
are not perfect anymore, or that the environment is inhomogeneous which would
give a twisted version of the classical law of reflection. One can also study,
instead of the trajectory of a ray of light, the behaviour of an electron
submitted to a magnetic field.

The object of interest of this paper are billiard models with a generalized
law of reflection, the so-called projective billiards. They unify various
laws, including the classical one in a Euclidean or Riemannian metric whose
geodesics are lines. The former models were introduced and studied by Sergey
Tabachnikov [30, 32]. They roughly consist of a domain endowed with a smooth
field of lines tranverse to the boundary: the latter defines at each point on
the boundary a law of reflection passing through this point. We investigate
particular fields of transverse line $L$, for which a domain is what is called
$L$-symmetric (defined below, see Definition 16).

The paper studies these projective billiard models in dimension $d\geq 3$ and
focuses on the existence and properties of caustics, i.e. hypersurfaces to
which any light trajectory remains tangent after successive reflections. It
questions for which billiards a caustic has to be a quadric, and relates the
answer to the class of $L$-symmetric billiards which we mentionned above. More
precisely we prove the following

######  Theorem 1.

Let $\Omega$ be a strictly convex domain in $\mathbb{R}^{d}$ with $d\geq 3$,
whose boundary is endowed with a smooth field of transve lines $L$. Assume
that the corresponding projective billiard has a caustic $\Gamma$. Then
$\Gamma$ is a quadric if and only if $\partial\Omega$ is $L$-symmetric.

Interestingly, projective billiards contain the class of ususal Euclidean
billiards, but more generally billiards in $\mathbb{R}^{d}$ endowed with a
metric whose geodesics are lines, and also pseudo-Euclidean or Finsler
billiards (to see this, one can associate to a domain its field of orthogonal
lines for the corresponding notion of "metric"). Pseudo-Euclidean billiards
are billiard for which the law of reflection is defined by a constant non-
degenerate quadratic form. For Finsler billiards, the law is defined by a
Finsler metric which does not depend on the fiber. Hence Theorem 1 applies to
all of these billiards:

######  Theorem 2.

Theorem 1 applies to ususal Euclidean billiards, to billiards in
$\mathbb{R}^{d}$ endowed with a metric whose geodesics are lines, to pseudo-
Euclidean billiards and to Finsler billiards.

For pseudo-Euclidean billiards, Theorem 1 can be made more precise, since 1)
it can be shown that any such billiard is $L$-symmetric and 2) it is known
that for two quadrics $Q_{1},Q_{2}$ of some pencil of quadrics called pseudo-
confocal, one is a caustic of the other one for the pseudo-Euclidean law of
reflection. We will explain in more details these arguments (see Section 5),
which allow to prove the

######  Theorem 3.

Let $\Omega$ be a pseudo-Euclidean billiard in $\mathbb{R}^{d}$ with $d\geq 3$
whose field of normal line to the boundary is transverse to it. If $\Omega$
has a caustic $\Gamma$, then both $\Gamma$ and $\Omega$ are pseudo-confocal
quadrics.

Theorems 1, 2 and 3 are described more precisely in Section 2.

The study of caustics, and more generally of invariant curves, in billiards is
an intense subsject of research. A famous example is the billiard in the
ellipse (resp. ellipsoid) for which it is known [31] that smaller confocal
ellipses (resp. ellipsoids) are caustics. Applying a KAM scheme, Lazutkin [28]
showed that if the boundary of a planar Euclidean billiard is striclty convex
and sufficiently smooth, then there exists a large set of caustics
accumulating to the boundary. Mather [29] proved that in a planar Euclidean
billiard if the curvature of the boundary vanishes, then the latter has no
caustics. Gutkin and Katok [18] gave effective conditions in such billiards
for which there exists caustics-free regions. These results were extended to
the $2$-sphere and hyperbolic plane by Florentin, Ostrover and Rosen [17]. Let
us mention the famous Birkhoff-Poritzky’s conjecture:

Conjecture (Birkhoff-Poritzky). If a convex domain contains an open set of
invariant curves then it is an ellipse.

The conjecture is still open, although some partial positive answers have been
given, see for example [3, 5, 6, 7, 8, 20, 21, 22, 23, 25, 27].

For a billiard in dimension at least $3$, having a caustic is a more rigid
property. Berger [4] proved that if such a Euclidean billiard has a caustic,
then both are confocal quadrics. This result was later extended by Glutsyuk to
billiards in spaces of constant curvature [24]. Billiards in pseudo-Euclidean
spaces and Minkowski metrics have been intensively studied by Dragović and
Radnović [1, 9, 10, 11]. More generally, projective billiards have been
studied in any dimensions [16, 13, 15, 14, 22, 23, 32, 30]. The results which
can be found here extend previously known results [16] found by the author.

Plan of the article. More precise definitions of Riemannian billiards, pseudo-
Euclidean billiards and projective billiards are given in Section 2, as well
as the statements of the results, namely Theorems 9, 10 and 17. In Section 3,
the reader can find a precise study of the so-called admissible hyperplanes,
allowing to view à la Berger any cone of lines tangent to a caustic as an
integral subsmanifold of a certain distribution. In Section 4 we prove Theorem
17, from which we deduce Theorem 9 and a part of Theorem 10. We complete the
proof of Theorem 10 in Section 5.

## 2 Riemannian, pseudo-Euclidean and projective billiards

A classical billiard on a manifold $M$ of dimension $d\geq 2$ given with a
complete Riemannian metric $g$ is a domain $\Omega\subset M$ with piecewise
smooth boundary. The reflection law at a smooth point $p$ of the boundary is
defined as follows, where $\gamma$ is an oriented geodesic inside $\Omega$
hitting the boundary at $p$ with velocity $v\in T_{p}M$:

######  Definition 4 (Riemannian billiard law of reflection).

We define the reflected geodesic from $\gamma$ at $p$ as the oriented geodesic
$\tilde{\gamma}$ passing through $p$ with velocity $\tilde{v}\in T_{p}M$ such
that $\tilde{v}$ is obtained from $v$ by the linear orthogonal symmetry of
$T_{p}M$ with respect to $T_{p}\Omega$ \- that is the only linear non-trivial
involution which preserves the hyperplane $T_{p}\partial\Omega$ and its
$g$-orthogonal line.

This defines a billiard flow $\varphi^{t}$ for $t\in\mathbb{R}$: given any
point $p\in\Omega$ and a non-zero vector $v\in T_{p}M$, the billiard flow
$\varphi^{t}(p,v)$ is obtain by following the geodesic with initial conditions
$(p,v)$ until it eventually reflects on the boundary, and continue its
trajectory, etc. It might eventually be not defined for all $t$.

######  Example 5 ($d$-dimensional sphere).

Consider a domain $\Omega$ on the $d$-dimensional sphere
$\SS^{d}\subset\mathbb{R}^{d+1}$ equipped with the classical spherical metric
$g$: the billiard flow inside $\Omega$ follow a trajectory along broken pieces
of great circles - ie intersection of hyperplanes of $\mathbb{R}^{d+1}$ with
$\SS^{d}$. Note that the canocical projection
$\pi:\mathbb{R}^{d+1}\setminus\\{0\\}\to\mathbb{R}P^{d}$ restricts as
diffeomorphism between a halph-sphere $\SS^{d}_{+}$ and a standard affine
chart $\mathbb{R}^{d}\subset\mathbb{R}P^{d}$ which sends geodesics of
$\SS^{d}$ to lines of $\mathbb{R}^{d}$. However the pushforward $\pi_{\ast}g$
of $g$ to $\mathbb{R}^{d}$ is not the Euclidean metric, and for any hyperplane
$H\subset\mathbb{R}^{d}$, its $\pi_{\ast}g$-orthogonal line differs from its
Euclidean orthogonal line.

######  Example 6 (Metrics on $\mathbb{R}^{d}$ projectively equivalent to the
Euclidean one).

A metric $g$ on $\mathbb{R}^{d}$ is said to be projectively equivalent to the
Euclidean metric if the geodesics of $g$ are supported by straight lines. For
example, the metric $\pi_{\ast}g$ obtained in Example 5 is projectively
equivalent to the Euclidean metric. We can therefore define a billiard flow
inside an domain $\Omega\subset\mathbb{R}^{d}$ for the metric $g$ which
follows broken lines. Note that in this case also, the $g$-orthogonal line of
an hyperplane $H\subset\mathbb{R}^{d}$ may differ from its Euclidean
orthogonal.

In this paper we study the property of so-called caustics of a billiard. They
can be defined as follows:

######  Definition 7.

Let $\Omega$ be a billiard in a Riemannian manifold $(M,g)$. A caustic is a
smooth hypersurface $\Gamma\subset\Omega$ such that if the billiard flow in
$\Omega$ is once tangent to $\Gamma$, then it remains tangent to it after
successive reflections (as long as it is defined).

We will define two other types of billiards, namely the pseudo-Euclidean and
projective billiards for which this notion is relevant, and will state each of
our result for this different models.

In the following we consider the space $\mathbb{R}^{d}$, $d\geq 2$ endowed
with its Euclidean metric
$\left\langle\,\cdot\left|\,\cdot\right.\right\rangle$. Let
$S\subset\mathbb{R}^{d}$ be a $\mathcal{C}^{2}$-smooth hypersurface. We fix
$n:\partial\Omega\to\mathbb{R}^{d}$ be a field of Euclidean unit normal
vectors to $S$.

Riemannian billiards

To state our first result, we need another definition. Let
$\nu:S\to\mathbb{R}^{d}$ be the field of $g$-orthogonal vectors to $S$ such
that $\left\langle\,\nu\left|\,n\right.\right\rangle\equiv 1$.

######  Definition 8.

We say that $S$ is $g$-symmetric at $p\in S$ if for any $u,v\in T_{p}S$, we
have

(1)
$\left\langle\,dn_{p}(u)\left|\,d\nu_{p}(v)\right.\right\rangle=\left\langle\,dn_{p}(v)\left|\,d\nu_{p}(u)\right.\right\rangle.$

We simply say that $S$ is $g$-symmetric if the latter holds for all $p\in S$.

######  Theorem 9.

Let $d\geq 3$ and $g$ be a Riemannian metric on $\mathbb{R}^{d}$ whose
geodesics are supported by lines. Let $\Omega\subset\mathbb{R}^{d}$ be a
$\mathcal{C}^{2}$-smooth domain such that $\Omega$ has a caustic $\Gamma$.
Then the following statements are equivalent:
(i) $\Gamma$ is a quadric;
(ii) $\partial\Omega\subset\mathbb{R}^{d}$ is $g$-symmetric.

In fact Theorem 9 has a analogous versions for so-called pseudo-Euclidean and
projective billiards which we are going to define.

Pseudo-Euclidean billiards

Let $Q$ be a non-degenerate bilinear form on $\mathbb{R}^{d}$. Let
$\Omega\subset\mathbb{R}^{d}$ be a domain with piecewise smooth boundary. We
define the pseudo-Euclidean reflection of oriented lines with respect to $Q$
at point $p\in\partial\Omega$ as in Definition 4, where
(i) the geodesics are replaced by oriented lines;
(ii) the notion of $g$-orthogonality is replaced by the notion of $Q$
orthogonality: since $Q$ is non-degenerate, the $Q$-orthogonal line $L_{p}$ to
$T_{p}\partial\Omega$ in $T_{p}\mathbb{R}^{d}$ is well-defined. Hence if
$L_{p}\nsubseteq T_{p}\Omega$, there is a unique non-trivial linear involution
of $T_{p}\mathbb{R}^{d}$ preserving $T_{p}\Omega$ and $L_{p}$, and the latter
defines the pseudo-Euclidean reflection at $p$ with respect to $T_{p}\Omega$
as in Definition 4. When $L_{p}\subset T_{p}\Omega$, the reflection is not
defined.

######  Theorem 10.

Let $d\geq 3$ and $Q$ be a non-degenerate quadratic form on $\mathbb{R}^{d}$.
Let $\Omega\subset\mathbb{R}^{d}$ be a domain whose boundary is a
$\mathcal{C}^{2}$-smooth space-time hypersurface. Then $\Omega$ has a caustic
$\Gamma$ if and only if $\Omega$ and $\Gamma$ are quadrics, which are pseudo-
confocal.

######  Remark 11.

The notion of pseudo-confocal quadrics extends the usual notion of confocal
quadrics as a specific pencil of quadrics depending on the quadratic form
associated to the space (see [16] for more details). For example if the space
is endowed with the quadratic form

$dx_{1}^{2}+\ldots+dx_{r}^{2}-dx_{r+1}^{2}-\ldots-dx_{d}^{2}$

then the family of quadrics depending on a parameter $\lambda$ and defined by
the equations

$\mathcal{Q}_{\lambda}:\quad\frac{x_{1}^{2}}{a_{1}-\lambda}+\ldots+\frac{x_{r}^{2}}{a_{r}-\lambda}+\frac{x_{r+1}^{2}}{a_{r+1}+\lambda}+\ldots+\frac{x_{d}^{2}}{a_{d}+\lambda}=1$

where $a_{1},\ldots,a_{d}\in\mathbb{R}$ is a pseudo-confocal pencil of
quadrics.

Projective billiards

The two previous billiard models lead to a more general definition of
billiard, called projective billiards, introduced and studied by Tabachnikov
[30, 32]. Note that given an oriented line $\ell$ passing through a point
$p\in\mathbb{R}^{d}$ can be seen as a geodesic, hence one can associates to it
its unit velocity vector $v\in T_{p}\mathbb{R}^{d}$.

######  Definition 12 (Projective billiards and projective law of reflection).

A projective billiard is a domain $\Omega\subset\mathbb{R}^{d}$ with piecewise
smooth boundary, equipped with a field of transverse line $L$: that is for any
smooth point $p$ of $\partial\Omega$, $L_{p}$ defines a line passing through
$p$ and transverse to $\partial\Omega$ at $p$. We denote it by the pair
$(\Omega,L)$.

Let $\ell$ be an oriented line $\ell$ hitting the boundary transversally at a
point $p$ with unit velocity $v\in T_{p}\mathbb{R}^{d}$. The line $\ell$ is
said to be reflected into the oriented line $\ell^{\prime}$ by the projective
law of reflection at $p$ if
(i) $\ell^{\prime}$ contains $p$;
(ii) Let $w$ be the unit velocity of $L_{p}$. The unit velocity vectors
$v^{\prime}$ of $\ell^{\prime}$ is obtained as the image of the unit velocity
vector $v$ of $\ell$ by the only non-trivial linear involution of
$T_{p}\mathbb{R}^{d}$ which preserves $T_{p}\partial\Omega$ and $\mathbb{R}w$.

This defines, as in the case of the usual billiards, a projective billiard
flow in $\Omega$.

######  Remark 13.

The projective law of reflection 12 is equivalent to the following items:
(i) the lines $\ell$, $\ell^{\prime}$ and $L_{p}$ are contained in a
$2$-dimensional plane $\mathcal{P}$ transverse to $T_{p}{\Omega}$;
(ii) if $T$ is the line $T_{p}\cap\mathcal{P}$, then the quadruple of lines
$(\ell,\ell^{\prime};T,L_{p})$ are in involution (meaning that it is a
harmonic quadruple of points in the space of lines contained in $\mathcal{P}$
and passing through the point $p$, identified with $\mathbb{R}P^{1}$: their
cross-ratio in this order is $-1$).

######  Remark 14.

Let $g$ be a metric projectively equivalent to the Euclidean one,
$\Omega\subset\mathbb{R}^{d}$ a domain with piecewise smooth boundary, and
$L_{p}$ the $g$ orthogonal line to $T_{p}\partial\Omega$ passing through $p$.
Then by definition the billiard flow for $g$ in $\Omega$ corresponds to the
projective billiard flow in $(\Omega,L)$. The same statement hold for pseudo-
Euclidean billiards with space-time boundary.

Let a smooth domain $\Omega\subset\mathbb{R}^{d}$, with $d\geq 3$, equipped
with a smooth field of transverse lines to the boundary $L$. We assume that
the corresponding porjective billiard $(\Omega,L)$ has a caustic $\Gamma$.

We observe [4] that we can study the problem locally by considering an open
subset $S\subset\partial\Omega$ of the boundary and two open subsets
$U,V\subset\Gamma$ of the caustic such that there is at least an oriented line
tangent to $U$ and reflected on $S$ into an oriented line tangent to $V$. Note
that here we consider the same projective law of reflection induced by the
restriction of $L$ to $S$. Denote this structure by $(S,L)$ and call it line-
framed hypersurface. This leads to the

######  Definition 15.

Let $S,U,V\subset\mathbb{R}^{d}$ be embedded hypersurfaces of $\mathbb{R}^{d}$
and $L$ be a field of transverse lines to $S$. We say that the pair $(U,V)$ is
a piece of caustic for the projective billiard $(S,L)$ if the set of oriented
lines tangent to $U$, intersecting $S$ transversally and reflected to oriented
lines tangent to $V$ by the projective law of reflection on $(S,L)$ is a non-
empty open subset of the set of lines tangent to $U$.

Let $S\subset\mathbb{R}^{d}$ be a hypersurface endowed with a smooth field of
transverse line $L$. As in the Riemannian case, we define
$\nu:S\to\mathbb{R}^{d}$ be a field of vectors such that
$\left\langle\,\nu\left|\,n\right.\right\rangle\equiv 1$ and $\nu_{p}$ as the
same direction as $L_{p}$.

######  Definition 16.

We say that $S$ is $L$-symmetric at $p\in S$, if for any $u,v\in T_{p}S$, we
have

(2)
$\left\langle\,dn_{p}(u)\left|\,d\nu_{p}(v)\right.\right\rangle=\left\langle\,dn_{p}(v)\left|\,d\nu_{p}(u)\right.\right\rangle.$

We simply say that $S$ is $L$-symmetric if the latter holds for all $p\in S$.

######  Theorem 17.

Let $d\geq 3$, $S\subset\mathbb{R}^{d}$ be a $\mathcal{C}^{2}$-smooth embedded
hypersurface with non-degenerate second fundamental form, and endowed with a
field of transverse lines $L$. Then the following statements are equivalent:
(i) $U$ and $V$ are open subsets of quadrics;
(ii) $\partial\Omega\subset\mathbb{R}^{d}$ is $L$-symmetric.
If (i) or (ii) is satisfied, then $U$ and $V$ are contained in the same
quadric.

Comments on the previous results

As explained, billiards in Riemannian metric projectively equivalent to the
Euclidean one and pseudo-Euclidean billiards are particular cases of
projective billiards: given $\Omega$, one of the two former billiards, the
corresponding field of normal lines - either for the Riemannian metric or for
the pseudo-Euclidean structure - defines a ŝmooth field of lines $L_{p}$ on
$\partial\Omega$. Moreover it is transverse to $\partial\Omega$ in the
Riemannian case, and also in the pseudo-Euclidean case when $\partial\Omega$
is space-time.

Therefore, Theorem 9 and 10 in these two cases will be corollaries of Theorem
17 in the projective case: Theorem 9 is just the translation of Theorem 17 in
a Riemannian metric, and Theorem 10 will use the additional result that
caustics of pseudo-Euclidean billiards in quadrics are well understood.

I strongly believe that Theorem 17 applies to Minkowski billiards: the latter
can be seen as projective billiard wich are symmetric in the sense of
Definition 16. The result is in preparation. For more details about Minkowski
billiards and billiards in Finsler metrics see [2, 19].

To go beyond the results presented here, I am thinking about two interesting
and relevant question. The first is to ask whether a projective billiard which
is not $L$ symmetric can have a caustic. The negative answer to this question
would allow to conclude that if a projective billiard has a caustic, then the
latter is a quadric. The positive answer would provide interesting examples of
billiards with a caustic.

For the second question, note that, in the plane, given a convex domain
$\Omega^{\prime}$ nested in another one $\Omega$, one can endow $\Omega$ with
a field of transverse lines such that $\partial\Omega^{\prime}$ is a caustic
for the induced projective billiard in $\Omega$. This is true in particular in
the case when $\Omega^{\prime}$ is bounded by a conic. Hence if a projective
billiard has a conic as a caustic, then itself can be something else than a
conic. This construction is however more delicate in dimension greater than
$2$. However, following Definition 16 and Theorem 17, a natural question
arises: if a projective billiard is $L$-symmetric and has a quadric as a
caustic, is it a quadric itself? Answering this question is probably
difficult, and the study of billiards in quadrics for different billiard
structures might help, as it does for pseudo-Euclidean billiards.

## 3 Admissible hyperplanes

Having a caustic $\Gamma$ for a projective billiard $(\Omega,L)$ is a very
strong property, which has important geometric consequences on the cones of
lines tangent to $\Gamma$ and intersecting $\partial\Omega$ at a same point
$q$: they are integrable surfaces of a certain distribution of hyperplanes of
$T_{p}\partial\Omega$ (see [4] for the case of Euclidean billiards). This
observation still holds for projective billiards, as we will show in
Proposition 20.

We consider the following important situation. Let a line framed-hypersurface
$(S,L)$ having a piece of caustic $(U,V)$. Fix a triple of points $(p,q,r)\in
U\times S\times V$ such that $p$ is the tangency point of an oriented line
reflected on $(S,L)$ at the point $q$ into an oriented line tangent to $V$ at
$r$. The hyperplanes $T_{p}U$ and $T_{r}V$ intersects $T_{q}S$ into a
hyperplane $H$ of $T_{q}S$ (a linear subspace of codimension $1$).

Hence we can do the following trivial remark: any smooth path
$(p(t),q(t),r(t))\in U\times S\times V$ passing through $(p,q,r)$ at $0$ is
such that $p^{\prime}(0)$ belongs to the hyperplane $T_{p}U$, generated by $H$
and the direction of the line $pq$, and an analogous statement for
$r^{\prime}(0)$. This remark is of high importance when we don’t assume the
existence of a piece of caustic. This leads to the following

######  Definition 18.

Let $(S,L)$ be a line-framed hypersurface, $\ell$ an oriented line
intersecting $S$ transversally at a point $q\in S$ and $H$ a hyperplane of
$T_{q}S$. We say that $H$ is $\ell$-admissible if the orthogonal projection of
$\ell$ to $T_{q}S$ is transverse to $H$, and for any smooth path $\ell(t)$
passing through $\ell$ at $0$ and intersecting $S$ transversally at $q(t)$,
there exists a curve $(p(t),q(t))$ satisfying the following:
(i) $p(0)\in\ell$ and the points $p(t),q(t),r(t)$ are not colinear;
(ii) $\ell(t)$ is reflected into the oriented line from $q(t)$ to $r(t)$ by
the projective law of reflection on $(S,L)$;
(iii) $p^{\prime}(0)$ belongs to the hyperplane containing the line $\ell$ and
$H$;
(iv) $q^{\prime}(0)$ belongs to the hyperplane containing the line $q(0)r(0)$
and $H$.

As discussed, in the situation when $(S,L)$ admits a piece of caustic $(U,V)$,
we have the

######  Proposition 19.

Suppose that $(S,L)$ admits a piece of caustic $(U,V)$. Then the intersection
$H$ of the tangent space $T_{q}S$ with $T_{p}U$ or with $T_{r}V$, such that
the line $pq$ is tangent to $U$, is $pq$-admissible.

The main result of this section is described by the next proposition. We say
that a line $\ell$ intersecting $S$ at $q$ is above a vector $\xi\in T_{q}S$
if it projects orthogonally to $T_{q}S$ in a line containing $\xi$.

######  Proposition 20.

Suppose $S$ has a non-degenerate second fundamental form at $q$. Then for all
line $\ell$ intersecting $S$ transversally at $q$ and above a vector $\xi\in
T_{q}S$, the number of $\ell$-admissible hyperplanes $H\subset T_{q}S$ is at
most $d-1$.

In order to prove Proposition 20, we first show that admissible hyperplanes
satisfies a certain linear equation, see Lemma 21.

Notations. We endow $\mathbb{R}^{d}$ with its usual Riemannian metric: we
denote by $x\cdot y=\left\langle\,x\left|\,y\right.\right\rangle$ the
canonical scalar product between two vectors $x,y$ of $\mathbb{R}^{d}$.

There is a one-to-one correspondance (up to a sign) between hyperplanes
$H\subset T_{q}S$ and their unit normal vectors $\pm\eta\in T_{q}S$, so that
we will write $\eta_{H}$ or $H_{\eta}$ for vectors and hyperplanes
corresponding to eachother.

Let $n:S\to\mathbb{R}$ be a smooth field of normal unit vector to $S$, and
$\nu:S\to\mathbb{R}^{d}$ be a smooth field of vectors such that
$n\cot\nu\equiv 1$ and $L_{p}$ is directed by $\nu(p)$ for any $p\in S$.

Denote by $II_{q}:T_{q}S\times T_{q}S\to\mathbb{R}$ the second fundamental
form of $S$ at $q$.

######  Lemma 21.

Let $\ell$ be a line intersecting $S$ transversally at $q$ and $H$ a
hyperplane of $T_{q}S$. Denote by $\xi$ the vector of $T_{q}$ above $\ell$
such that $\xi+\nu(q)$ gives the direction of $\ell$. Then if $H$ is
$\ell$-admissible, then $\xi\notin H$ and for any $x\in T_{q}S$ we have

(3)
$\left\langle\,d\nu_{q}(x)\left|\,\eta_{H}\right.\right\rangle+\left\langle\,\eta_{H}\left|\,\nu\right.\right\rangle
II_{q}(\nu,x)+\left\langle\,\eta_{H}\left|\,\xi\right.\right\rangle
II_{q}(\xi,x)=\alpha\left\langle\,\eta_{H}\left|\,x\right.\right\rangle$

where $\alpha\in\mathbb{R}$ depends on the problem, and in the expression
$II_{q}(\nu,x)$, $\nu$ stands for its orthogonal projection to $T_{q}S$.

######  Remark 22.

The proof will imply that

$\alpha=-\frac{1}{2}\left(\frac{\|\nu(q)+\xi\|}{pq}+\frac{\|\nu(q)-\xi\|}{qr}\right)\in\mathbb{R}$

is related to the distances $pq$ and $qr$ between the points $p=p(0)$,
$q=q(0)$ and $r=r(0)$ of Definition 18.

###### Proof of Lemma 21.

The idea of the proof is similar to the one which can be found in [4], yet a
bit more general. Let $H,\ell,\xi,\eta=\eta_{H}$ be as in the statement and
suppose that $H$ is $\ell$-admissible. The idea consists of choosing in
Definition 18 curves $q_{i}(t)$ on $S$ tangent to the principal direction of
$S$ at $q$.

Let $\underline{u}=(u_{1},\ldots,u_{d-1})$ be an orthonormal basis of $T_{q}S$
in which $II_{q}$ is diagonal (the principal directions of $S$ at $q$). Fix an
integer $i$ between $1$ and $d-1$. Consider a curve $q(t)$ contained in a
plane transverse to $S$ such that $q^{\prime}(0)=u_{i}$ and
$u_{i}(t):=q^{\prime}(t)$ has unit norm. In the following, when we omit the
’$(t)$’, it implies that $t=0$.

If $\xi=\sum_{k=1}^{d-1}\xi_{k}u_{k}$ is the expansion of $\xi$ in
$\underline{u}$, define $\xi(t)=\sum_{k=1}^{d-1}\xi_{k}u_{k}(t)$, where for
each $k\neq i$ the vector $u_{k}(t)\in T_{q(t)}S$ is obtained from $u_{k}$ by
parallel transport along $q(t)$.

This defines a curve of lines $\ell(t)$ passing through $q(t)$ of direction
$e(t):=\nu(q(t))+\xi(t)$. Since $H$ is $\ell$-admissible, there is a curve
$(p(t),q(t))$ satisfying items (i)-(iv).

Now write $\overline{e}(t)=\nu(t)-\xi(t)$ directing the line
$\ell^{\prime}(t)$ reflected from $\ell$ at $q(t)$ and oriented to the same
side of $T_{q(t)}S$ as $e(t)$. We can find real number of same sign (say
positive) $a(t),c(t)>0$ such that $p(t)=q(t)+a(t)e(t)$ and
$r(t)=q(t)+c(t)\overline{e}(t)$. The expressions

$n_{p}:=\left\langle\,\eta\left|\,e\right.\right\rangle
n(q)-\left\langle\,n(q)\left|\,e\right.\right\rangle\eta=\left\langle\,\eta\left|\,e\right.\right\rangle
n(q)-\eta$ $n_{r}:=\left\langle\,\eta\left|\,\overline{e}\right.\right\rangle
n(q)-\left\langle\,n(q)\left|\,\overline{e}\right.\right\rangle\eta=\left\langle\,\eta\left|\,\overline{e}\right.\right\rangle
n(q)-\eta$

defines normal vectors to the hyperplanes of $\mathbb{R}^{d}$ generated
respectively by $H$ and $e$, and by $H$ and $\overline{e}$.

By items (iii)-(iv), $p^{\prime}$ and $r^{\prime}$ are orthogonal respectively
to $n_{p}$ and $n_{r}$, which implies that

(4)
$\frac{\left\langle\,p^{\prime}\left|\,n_{p}\right.\right\rangle}{a}+\frac{\left\langle\,r^{\prime}\left|\,n_{r}\right.\right\rangle}{c}=0.$

The first term can be computed as
$\left\langle\,p^{\prime}\left|\,n_{p}\right.\right\rangle=\left\langle\,q^{\prime}\left|\,n_{p}\right.\right\rangle+a\left\langle\,e^{\prime}\left|\,n_{p}\right.\right\rangle$
since $e$ is orthogonal to $n_{p}$. Hence

$\left\langle\,p^{\prime}\left|\,n_{p}\right.\right\rangle=-\left\langle\,u_{i}\left|\,\eta\right.\right\rangle+a\left\langle\,d\nu(u_{i})+\xi^{\prime}\left|\,n_{p}\right.\right\rangle.$

Similarly
$\left\langle\,r^{\prime}\left|\,n_{r}\right.\right\rangle=-\left\langle\,u_{i}\left|\,\eta\right.\right\rangle+c\left\langle\,d\nu(u_{i})-\xi^{\prime}\left|\,n_{r}\right.\right\rangle$.
Hence Equation (4) can be rewritten as

$-\left(\frac{1}{a}+\frac{1}{c}\right)\left\langle\,u_{i}\left|\,\eta\right.\right\rangle+\left\langle\,d\nu(u_{i})\left|\,n_{p}+n_{r}\right.\right\rangle+\left\langle\,\xi^{\prime}\left|\,n_{p}-n_{r}\right.\right\rangle=0.$

The sums $n_{p}+n_{r}$ and $n_{p}-n_{r}$ can be computed as

$n_{p}+n_{r}=2\left\langle\,\nu(q)\left|\,\eta\right.\right\rangle
n(q)-2\eta\qquad\text{and}\qquad
n_{p}-n_{r}=2\left\langle\,\xi\left|\,\eta\right.\right\rangle n(q)$

hence Equation (4) rewrites as

(5)
$-\left(\frac{1}{a}+\frac{1}{c}\right)\left\langle\,u_{i}\left|\,\eta\right.\right\rangle+2\left\langle\,d\nu(u_{i})\left|\,n(q)\right.\right\rangle\left\langle\,\nu(q)\left|\,\eta\right.\right\rangle-2\left\langle\,d\nu(u_{i})\left|\,\eta\right.\right\rangle\\\
+2\left\langle\,\eta\left|\,\xi\right.\right\rangle\left\langle\,n(q)\left|\,\xi^{\prime}\right.\right\rangle=0.$

Finally derivative $\xi^{\prime}$ is such that
$\left\langle\,\xi^{\prime}\left|\,n(q)\right.\right\rangle=-k_{i}\ell_{i}=-II_{q}(\xi,u_{i})$.
Moreover, since $\left\langle\,n\left|\,\nu\right.\right\rangle\equiv 1$ we
derive
$\left\langle\,d\nu(u_{i})\left|\,n(q)\right.\right\rangle=-II_{q}(\nu(q),u_{i})$.
Hence Equation (4) is equivalent to

(6)
$-\left(\frac{1}{a}+\frac{1}{c}\right)\left\langle\,u_{i}\left|\,\eta\right.\right\rangle=2\left\langle\,\nu(q)\left|\,\eta\right.\right\rangle
II_{q}(\nu(q),u_{i})+2\left\langle\,d\nu(u_{i})\left|\,\eta\right.\right\rangle\\\
-2\left\langle\,\eta\left|\,\xi\right.\right\rangle II_{q}(\xi,u_{i}).$

Equation (6) gives the result by replacing $u_{i}$ by any
$x=\sum_{k=1}^{d-1}x_{k}u_{k}$. ∎

We can now prove Proposition 20.

###### Proof of Proposition 20.

Fix a line $\ell$ intersecting $S$ transversally at $q$, $\xi\in T_{p}S$ be
the vector such that $\xi+\nu$ gives the direction of $\ell$. Suppose that we
are given an $\ell$-admissible hyperplane $H$ of normal vector
$\eta=\eta_{H}$.

Denote by $d\nu^{\ast}$ and $N$ the endomorphisms of $T_{q}S$ satisfying for
any $x,y\in T_{q}S$

$\left\langle\,d\nu(x)\left|\,y\right.\right\rangle=\left\langle\,x\left|\,d\nu^{\ast}(y)\right.\right\rangle\qquad\text{and}\qquad
II_{q}(x,y)=\left\langle\,N(x)\left|\,y\right.\right\rangle.$

Consider the endomorphisms $f,g$ of $T_{p}S$ defined for all $x\in T_{p}S$ by

$f(x)=d\nu^{\ast}(\eta)+\left\langle\,x\left|\,\nu\right.\right\rangle
N(\nu)+\left\langle\,x\left|\,\xi\right.\right\rangle N(\xi)$
$g(x)=d\nu^{\ast}(\eta)+\left\langle\,x\left|\,\nu\right.\right\rangle
N(\nu).$

Note that for any $x\in T_{q}S$ they satisfy

(7) $f(x)=g(x)+\left\langle\,x\left|\,\xi\right.\right\rangle N(\xi).$

By Lemma 21, if $H$ is $\ell$-admissible, there is a certain
$\alpha\in\mathbb{R}$ such that $\eta$ satisfyies $f(\eta)=\alpha\eta$. This
is equivalent to say that $\eta$ is an eigenvector of $f$ associated to the
eigenvalue $\alpha$. Consider any such eigenvector $x$, satisfying
$f(x)=\alpha x$ by definition. From (7) we get

$g(x)-\alpha x=-\left\langle\,x\left|\,\xi\right.\right\rangle N(\xi).$

Consider first the case when $\alpha$ is not a (real) eigenvalue of $g$. This
means that the operator $g-\alpha\text{Id}\,$ is invertible and

$x=-\left\langle\,x\left|\,\nu\right.\right\rangle(g-\alpha\text{Id}\,)^{-1}N(\nu)\in\mathbb{R}(g-\alpha\text{Id}\,)^{-1}N(\nu).$

Hence the set of eigenvectors of $f$ associated to the eigenvalue $\alpha$ has
dimension at most $1$.

In the case when $\alpha$ is also an eigenvalue of $g$, we have $g(x)=\alpha
x$. Hence we deduce from (7) that

$\left\langle\,x\left|\,\xi\right.\right\rangle N(\xi)=0.$

Since $II_{q}$ is non degenerate, this implies
$\left\langle\,x\left|\,\xi\right.\right\rangle=0$.

Conclusion the eigenspace of $f$ associated to $\alpha$ has either dimension
$\leq 1$ or contains only vectors orthogonal to $\xi$. For $\eta$, the second
possibility is not possible (otherwise $\xi\in H$). This implies the result. ∎

## 4 Proof of Theorem 17

To prove Theorem 17, we notice that we can assume $d=3$. This idea can be
found in [4] and is based on the following argument: an embedded hypersurface
$\Gamma\subset\mathbb{R}^{d}$ is a quadric if and only if for any
$3$-dimensional vector space $V\subset\mathbb{R}^{d}$, the intersection
$V\cap\Gamma$ is a quadric of $V$.

Hence it is enough to prove Theorem 17 for $d=3$. Let $(S,L)$ be a line-framed
hypersurface of $\mathbb{R}^{3}$ which admits a piece of caustics $(U,V)$.
Given a point $q\in S$, we are interested in the set of lines tangent to $U$
and reflected to $V$ by the projective law of reflection on $S$ at $q$. We say
that such a set is a piece of quadratic cone if it lies on a cone whose
sections by planes are conics. The following proposition will be enough to
conclude:

######  Proposition 23.

Suppose that $q\in S$ and the second fundamental form of $S$ at $q$ is non-
degenerate. Then the following statements are equivalent:
(i) The set of lines tangent to $U$ and reflected to $V$ by the projective law
of reflection on $S$ at $q$ is a piece of quadratic cone;
(ii) $S$ is $L$-symmetric at $q$. In this case, the set of lines tangent to
$V$ and containing $q$ are contained in the same cone.

###### Proof of Theorem 17 using Proposition 23.

It is an immediate consequence of the fact that $U$ is an open set of a
quadric if and only if the piece of quadratic cone tangent to $U$ are
quadratic. This result can be shown by duality as it is presented in [4]. ∎

It remains to show that Proposition 23 holds. The proof will be given in a
succession of lemmae all along this section. We will refer to the set of lines
in item (i) of Proposition 23 as partial cone at $q$.

The first lemma gives a differential equation satisfied by the curve obtained
by intersecting the partial cone at $q$ with an affine plane of direction
$T_{q}S$.

Setting. Let $q\in S$ be a point such that the second fundamental form of $S$
at $q$ is non-degenerate. By an affine change of variables, we can find a set
of coordinates $(x,y,z)$ on $\mathbb{R}^{3}$ such that
\- $q$ is the origin of $\mathbb{R}^{3}$;
\- $T_{q}S$ is given by the equation $z=0$;
\- the principal directions of $S$ at $B$ are given by the vectors
$u_{1}=(1,0,0)$ ad $u_{2}=(0,1,0)$ with principal curvatures
$k_{1},k_{2}\in\mathbb{R}^{\ast}$.

Let $(U,V)$ be a piece of caustics of $S$ and consider the smooth family of
lines $\ell(t)$ containing $q$ and tangent to $U$. Let
$p_{0}(t)=(x(t),y(t),1)$ be the point of intersection of $\ell(t)$ with the
plane of equation $z=1$.

######  Lemma 24.

Write $\nu(q)=(\nu_{1},\nu_{2},1)$, $d\nu(u_{1})+k_{1}\nu_{1}\nu=(a,b,0)$ and
$d\nu(u_{2})+k_{2}\nu_{2}\nu=(c,d,0)$. Then The map
$t\mapsto(X(t),Y(t)):=(x(t)-\nu_{1},y(t)-\nu_{2})$ satisfies the following
differential equation

(8)
$\left(d-a+k_{2}Y^{2}-k_{1}X^{2}\right)X^{\prime}Y^{\prime}+(b+k_{1}XY)X^{\prime
2}-(c+k_{2}XY)Y^{\prime 2}=0.$

###### Proof.

The differential equation is a direct computation from Lemma 21. Indeed,
consider $M$ and $N$ two by two real matrices such that for any $u,v\in
T_{q}S$ writen in the basis $(u_{1},u_{2})$ we have

$\left\langle\,d\nu(u)\left|\,v\right.\right\rangle=\left\langle\,Mu\left|\,v\right.\right\rangle\qquad\text{and}\qquad
II_{q}(u,v)=\left\langle\,Nu\left|\,v\right.\right\rangle.$

Here $N$ is the diagonal matrix whose entries are $k_{1}$ and $k_{2}$, and $M$
will be computed later. Lemma 21 implies that $\eta$ is an eigenvalue of the
linear map

$f:\eta\mapsto M\eta+\left\langle\,\nu\left|\,\eta\right.\right\rangle
N\nu+\left\langle\,\xi\left|\,\eta\right.\right\rangle N\xi.$

Its matrix $\mathcal{M}(f)$ in the basis $(u_{1},u_{2})$ can be easily
computed using the fact that $\xi=(x(t),y(t),0)$ and the different expressions
for $\nu$ and $d\nu$:

(9) $\mathcal{M}(f)=\left(\begin{matrix}a+k_{1}X^{2}&b+k_{1}XY\\\
c+k_{2}XY&d+k_{2}Y^{2}\end{matrix}\right).$

Consider $H(t)$ the hyperplane of $T_{q}S$ obtained by the intersection of
$T_{q}S$ and the tangent plane $T_{p(t)}U$, where $p(t)$ is the point of
tangency of $\ell(t)$ with $U$. By Proposition 19, $H(t)$ is admissible. A
normal vector to $H(t)$ is given by

$\eta(t)=(Y^{\prime}(t),-X^{\prime}(t),0).$

Indeed, the vector $p_{0}^{\prime}(t)=(X^{\prime}(t),Y^{\prime}(t),0)$ is
tangent at $p_{0}(t)$ to the cone $\mathcal{C}_{U,q}$ of lines tangent to $U$,
and contained in a horizontal plane. Hence it is contained in
$T_{p}U=T_{p_{0}}\mathcal{C}_{U,q}$ and $T_{q}S$ hence in $H(t)$.

Now by Proposition 20, $\eta(t)$ is an eigenvalue of $f$, in particular

$\det(\eta,\mathcal{M}(f)\eta)=0.$

Expanding the previous equation leads to the result. ∎

Let us assume for the rest of the section that $k_{1},k_{2}>0$, the other
cases being similar. To simplify Equation (8), we can do a change of variables
according to the following obvious result.

######  Lemma 25.

Suppose $k_{2},k_{1}>0$. Write ${X}_{1}=\sqrt{k_{1}}X$ and
${Y}_{1}=\sqrt{k_{2}}Y.$ Then $(X,Y)$ is a solution of Equation (8) if and
only if $({X}_{1},{Y}_{1})$ satisfies the differential equation

(10)
$\left(d_{1}-a_{1}+y^{2}-x^{2}\right)x^{\prime}y^{\prime}+(b_{1}+xy)x^{\prime
2}-(c_{1}+xy)y^{\prime 2}=0$

where $a_{1}=a$, $d_{1}=d$, $b_{1}=b\sqrt{k_{2}/k_{1}}$, and
$c_{1}=c\sqrt{k_{1}/k_{2}}.$

The rest of the section is devoted to the study of the set of solutions of
Equation (10). Note that we cannot apply Cauchy-Lipschitz theorem due to the
form of the equation. And in fact, given a point
$(x_{0},y_{0})\in\mathbb{R}^{2}$, there is not a unique solution of Equation
(10) with initial condition $(x_{0},y_{0})$. We prove the

######  Lemma 26.

There exist a strict algebraic subset $V\subset\mathbb{R}^{2}$ such that for
any $(x_{0},y_{0})\in\mathbb{R}^{2}\setminus V$ Equation (10) has exactly two
solutions with initial conditions $(x_{0},y_{0})$, up to reparametrization.
Moreover, if $b_{1}=c_{1}$ then $V$ is the union of two conics.

###### Proof.

We can prove the result for Equation (8) instead of (10). Then the result
comes from the observation that solutions $\gamma=(x,y)$ of Equation (8) are
tangent to eigenspaces of the matrix
$\mathcal{N}(f)=R^{{}^{-}1}\mathcal{M}(f)R$ defined in (9), where $R$ is the
rotation by $\pi/2$ in a given orientation. The latter depends on $(x,y)$.

Let $V$ be the set of points $(x,y)$ such that $\mathcal{N}(f)$ has only one
eigenvalue. This set is given by the point $(x,y)$ for which the discriminant
$\Delta(x,y)$ of the characteristic polynomial of $\mathcal{N}(f)$ vanishes.
From (9), we compute that $\Delta$ is a non-zero polynomial given by

$\Delta(x,y)=(d-a+k_{2}y^{2}-k_{1}x^{2})^{2}+4(b+k_{1}xy)(c+k_{2}xy),$

hence $V$ is a strict algebraic subset of $\mathbb{R}^{2}$. The condition
$b_{1}=c_{1}$ is the same as $k_{2}b=k_{1}c$, and in this case $\Delta$ can be
written

$\Delta(x,y)=(d-a+k_{2}y^{2}-k_{1}x^{2})^{2}+4\frac{k_{1}}{k_{2}}(c+k_{2}xy)^{2},$

Hence $\Delta(x,y)=0$ is given by the union of two conics defined by equations

$d-a+k_{2}y^{2}-k_{1}x^{2}=0\qquad\text{and}\qquad c+k_{2}xy=0.$

Now if $(x_{0},y_{0})\notin V$, $\mathcal{N}(f)$ has two distinct eigenvalues
which depend smoothly on the coefficients of $\mathcal{N}(f)$, hence on
$(x,y)$ in a neighborhood $U$ of $(x,y)$. Moreover, for $(x,y)$ close to
$(x_{0},y_{0})$, on can find two distinct non-zero eingenvectors $W_{1}(x,y)$
and $W_{2}(x,y)$ of $\mathcal{N}(f)(x,y)$ associated to its distinct
eigenvalues, and depending smoothly on $(x,y)$. By definition, any solution
$\gamma(t)=(x(t),y(t))\in U$ is such that $\gamma^{\prime}(t)$ is colinear to
$W_{i}(\gamma(t))$ for a certain $i$. Now two such solutions (for a fixed $i$)
coincide up to reparametrization. ∎

It is now enough to understand under which conditions the solutions of the
differential equation (10) are supported by conics. The following lemma gives
the result:

######  Lemma 27.

The following statements are equivalent:
(i) $b_{1}=c_{1}$;
(ii) Equation (10) admits at least one solution which is supported by a conic.
In this case, all solutions are supported on conics.

###### Proof.

The proof will follow directly from a computation. We apologize in advance by
readers who would like to see a more algebraic approach. We will indeed
consider maps $x(t)$ and $y(t)$ given for all $t\in\mathbb{R}$ by

(11) $x(t)=r_{1}\cos(t)\qquad\text{and}\qquad y(t)=r_{2}\cos(t+\varphi)$

where $r_{1},r_{2}\in\mathbb{R}$ are non-zero and
$\varphi\in\mathbb{R}\setminus\pi\mathbb{Z}$ in the case of ellipses, and by

(12) $x(t)=r_{1}\cosh(t)\qquad\text{and}\qquad y(t)=r_{2}\cosh(t+\varphi)$

where $r_{1},r_{2},\varphi\in\mathbb{R}$ are non-zero in the case of
hyperbolae.

Suppose first that $(x,y)$ is given by (11). Since Equation (10) is invariant
by the transformtion $(x,y)\mapsto(-x,-y)$, any possible solution lying on a
conic is of the form $t\mapsto(x(\omega(t)),y(\omega(t)))$, where $\omega$ is
a strictly monotone smooth function. Moreover, since Equation (10) is
homogenous in the derivatives, we can assume that $\omega(t)=t$. Thus it
admits solutions supported on conics if and only if one can find such a pair
$(x,y)$ solution of Equation (10).

Consider such a pair $(x,y)$ and write

$E=\left(e+y^{2}-x^{2}\right)x^{\prime}y^{\prime}+(b+xy)x^{\prime
2}-(c+xy)y^{\prime 2}$

where for simplicity we omit the index $1$ and we replaced $d_{1}-a_{1}$ by
$e$. Substituting and factorizing, we obtain

(13)
$E=er_{1}r_{2}\sin(t)\sin(t+\varphi)+br_{1}^{2}\sin(t)^{2}-cr_{2}^{2}\sin(t+\varphi)^{2}\\\
+r_{1}^{3}r_{2}\sin(\varphi)\cos(t)\sin(t)+r_{1}r_{2}^{3}\sin(\varphi)\cos(t+\varphi)\sin(t+\varphi).$

We will now write $E$ as a linear combination of the three independant maps
$\sin^{2}$, $\cos^{2}$, $\sin\cos$. To do that, replacein $E$ the maps
$\cos(t+\varphi)$ and $\sin(t+\varphi)$ by their expansions

$\cos(t+\varphi)=\cos(t)\cos(\varphi)-\sin(t)\sin(\varphi),$
$\sin(t+\varphi)=\sin(t)\cos(\varphi)+\cos(t)\sin(\varphi).$

We obtain

$E=-K_{1}\cos(t)^{2}+K_{2}\sin(t)^{2}+K_{3}\cos(t)\sin(t)$

where

$\begin{array}[]{ccl}K_{1}&=&r_{1}r_{2}^{3}\sin(\varphi)^{2}\cos(\varphi)+cr_{2}^{2}\sin(\varphi)^{2}\\\
K_{2}&=&br_{1}^{2}+er_{1}r_{2}\cos(\varphi)-cr_{2}^{2}\cos(\varphi)^{2}+r_{1}r_{2}^{3}\sin(\varphi)^{2}\cos(\varphi)\\\
K_{3}&=&er_{1}r_{2}\sin(\varphi)-r_{1}^{3}r_{2}\sin(\varphi)-2cr_{2}^{2}\sin(\varphi)\cos(\varphi)\\\
&&\qquad\qquad\qquad\qquad-
r_{1}r_{2}^{3}\sin(\varphi)(\cos(\varphi)^{2}-\sin(\varphi)^{2})\end{array}$

Hence the equation $E\equiv 0$ is equivalent to $K_{1}=K_{2}=K_{3}=0$. This
system is not difficult to solve. Indeed, since $r_{1},r_{2}\neq 0$ and
$\varphi$ is not an integer multiple of $\pi$, we first notice that

$K_{1}=0\qquad\Leftrightarrow\qquad c=-r_{1}r_{2}\cos(\varphi).$

Now in equation $K_{3}=0$, divide by $r_{2}\sin(\varphi)$ and replace the
occurence of $c$ by $-r_{1}r_{2}\cos(\varphi)$ to obtain

$\left\\{\begin{array}[]{ccl}K_{1}&=&0\\\
K_{3}&=&0\end{array}\right.\Leftrightarrow\left\\{\begin{array}[]{ccl}c&=&-r_{1}r_{2}\cos(\varphi)\\\
e&=&r_{1}^{2}-r_{2}^{2}\end{array}\right..$

In $K_{2}$, replace the two occurences of $r_{1}r_{2}\cos(\varphi)$ by $-c$ to
get $K_{2}=br_{1}^{2}-cr_{2}^{2}-ec$, and use $e=r_{1}^{2}-r_{2}^{2}$ to
obtain the following equivalence

(14) $\left\\{\begin{array}[]{ccl}K_{1}&=&0\\\ K_{2}&=&0\\\
K_{3}&=&0\end{array}\right.\Leftrightarrow\left\\{\begin{array}[]{ccl}c&=&-r_{1}r_{2}\cos(\varphi)\\\
e&=&r_{1}^{2}-r_{2}^{2}\\\ 0&=&(b-c)(r_{2}^{2}+e)\end{array}\right..$

We deduce from the system (14), that if $b\neq c$, then
$r_{2}^{2}+e=r_{1}^{2}=0$ which contradicts our assumptions. Otherwise, if
$b=c$, all solutions of the form $t\mapsto(x(t),y(t))$ with

$\left\\{\begin{array}[]{ccl}c&=&-r_{1}r_{2}\cos(\varphi)\\\
e&=&r_{1}^{2}-r_{2}^{2}\end{array}\right.$

are solution of Equation (10).

The case when $(x,y)$ is given by (12) can be treated in the same way, with
the same conclusion. Hence if Equation (10) admits a solution which is
supported by a conic (an ellipse or a hyperbola), then previous computations
show that $b_{1}=c_{1}$.

Conversely, assume $b_{1}=c_{1}$ and choose a point $(x_{0},y_{0})$ in
$\mathbb{R}^{2}$ for which one can find a solution $\gamma(t)=(x(t),y(t))$ of
Equation (10). Consider the set $V$ of Lemma 26. Then in the case when
$(x_{0},y_{0})$ doesn’t lie in $V$, there are exactly two solutions to
Equation (10) up to reparametrization, and by previous computations one
parametrizes an ellipse, the other one a hyperbola; hence so does $\gamma$.
Now if $(x_{0},y_{0})$ lies in $V$, but $\gamma$ is not contained in $V$, we
can use previous argument. Finally if $\gamma$ is contained in $V$, then since
$V$ is the union of conics the result holds. ∎

###### Proof of Proposition 23.

It is a direct reformulation of Lemma 27. First, note that $b_{1}=c_{1}$ is
equivalent to $k_{2}b=k_{1}c$ (see Equation (10)), hence

$k_{2}\left\langle\,d\nu(u_{1})\left|\,u_{2}\right.\right\rangle=k_{1}\left\langle\,d\nu(u_{2})\left|\,u_{1}\right.\right\rangle$

where $(u_{1},u_{2})$ are the principal direction of $S$ at $q$. This gives
exactly the $L$-symmetry assumption.

Now, a piece of cone is quadratic if and only its transverse section by a
plane is an open set of a conic.

Finally, the fact that the set of lines tangent to $V$ and containing $q$ is
included in the same cone as the one tangent to $U$ comes from the proof of
Lemma 27: let a plane $P$ parallel to $T_{q}S$, and intersecting the cone of
lines tangent to $U$ transversally. We proved that this intersection is a
conic $C$ which is centraly-symmetric with respect to the point of
intersection of $P$ with the line $L_{q}$ defining the projective structure of
$(S,L)$ at $q$. Hence the line tangent to $V$ and passing through $q$ $-$
which are reflected from the ones tangent to $U$ $-$ intersect $P$ on $C$, and
the result follows.

Hence we showed that Proposition 23 is equivalent to Lemma 27, which gives the
result. ∎

## 5 Only quadrics have pseudo-caustics

This Section is devoted to the proof of Theorem 10. It comes from the
projective structure that one can endow on pseudo-Euclidean billiards.

Consider $Q$ a (constant) non-degenerate quadratic form on $\mathbb{R}^{d}$,
$d\geq 3$, and $S\subset\mathbb{R}^{d}$ an embedded hypersurface. For each
$q\in S$, consider the line $L_{q}$ containing $q$ and orthogonal to $T_{q}S$
for the quadratic form $Q$. In the case when $L_{q}$ is transverse to $S$ for
all $q$ (ie $S$ is what we call a space-time hypersurface), then $(S,L)$ is a
line-framed hypersurface on which the projective law of reflection corresponds
to the reflection of lines with respect to the quadratic form $Q$.

######  Lemma 28.

The hypersurface $S$ is $L$-symmetric.

###### Proof.

Let $n:S\to\mathbb{R}^{3}$ be a field of unit normal vector to $S$ for the
Euclidean structure. Consider the $d$-dimensional invertible real matrix $M$
such that $M^{T}=M$ and for any $x,y\in\mathbb{R}^{d}$ we have
$Q(x,y)=\left\langle\,M^{-1}x\left|\,y\right.\right\rangle$. For $q\in S$
define

$\nu(q)=\frac{1}{\left\langle\,Mn(q)\left|\,n(q)\right.\right\rangle}Mn(q).$

The reader can check that $\nu(q)$ gives the direction of $L_{q}$ and
satisfies $\left\langle\,\nu(q)\left|\,n(q)\right.\right\rangle=1$. A simple
computation shows that for any $x,y\in T_{q}S$

(15)
$\left\langle\,d\nu_{q}(x)\left|\,dn_{q}(y)\right.\right\rangle=\lambda(q)\left\langle\,Mdn_{q}(x)\left|\,dn_{q}(y)\right.\right\rangle\\\
-\lambda(q)^{2}\left\langle\,Mn(q)\left|\,dn_{q}(x)\right.\right\rangle\left\langle\,Mn(q)\left|\,dn_{q}(y)\right.\right\rangle,$

from which we deduce

$\left\langle\,d\nu_{q}(x)\left|\,dn_{q}(y)\right.\right\rangle=\left\langle\,d\nu_{q}(y)\left|\,dn_{q}(x)\right.\right\rangle.$

∎

We can now prove Theorem 10. Let $S$ be an embedded space-time hypersurface
together with its field of $Q$-orhtogonal lines $L$. Assume that $S$ admits a
piece of caustics $(U,V)$ for the pseudo-Euclidean law of reflection, which
amounts to say that $(U,V)$ is a piece of caustics for the projective law of
reflection induced by $L$ on $S$.

By Lemma 28, $S$ is $L$-symmetric. Hence by Theorem 17, $U,V$ are open sets of
one and the same quadric $\mathcal{Q}$, and any line tangent to $\mathcal{Q}$
intersecting $S$ transversally is reflected into a line tangent to
$\mathcal{Q}$.

Let us construct now a distribution of hyperplanes on an open set of points
containing $S$. For $q\in\mathbb{R}^{d}$ sufficiently close to $S$, one can
define the cone $\mathcal{C}_{q}$ of lines containing $q$ and tangent to
$\mathcal{Q}$ such that the cone $\mathcal{C}_{q}$ is not contained in an
affine hyperplane of $\mathbb{R}^{d}$. There exists only one pair
$(L_{0}(q),H(q))$ where $L_{0}(q)$ is a line containing $q$ which is
$Q$-orthogonal to the hyperplane $H_{0}(q)$ and such that any line of
$\mathcal{C}_{q}$ is reflected into a line in $\mathcal{C}_{q}$ by the
reflection of lines on $H(q)$ with respect to the pseudo-Euclidean metric. We
then consider the distribution $q\mapsto H(q)$ defined in a neighborhood of
$S$.

It satisfies by construction $H(q)=T_{q}S$ and $L_{0}(q)=L_{q}$ for $q\in S$,
hence $S$ is an integral hypersurface of $H$. Yet the integral hypersurfaces
of this distribution are quadrics which are pseudo-confocal to $\mathcal{Q}$.
Indeed, by [26] quadrics in pseudo-confocal pencil of quadrics are caustics of
one another. We deduce that $S$ is an open subset of a quadric which is
pseudo-confocal to $\mathcal{Q}$. For a definition of a pencil of pseudo-
confocal quadrics, see [16] Section 2.1.

## References

  * [1] A.K. Adabrah, V. Dragović, M. Radnović, Periodic billiards within conics in the Minkowski plane and Akhiezer polynomials, Regul. Chaotic Dyn. 24 (2019), 464–501.
  * [2] S. Artstein-Avidan, D. I. Florentin, Y. Ostrover and D. Rosen, Duality of Caustics in Minkowski Billiards, preprint arXiv:1707.04007.
  * [3] A. Avila, J. De Simoi and V. Kaloshin, An integrable deformation of an ellipse of small eccentricity is an ellipse, Ann. of Math. 184, 2016, 527–558.
  * [4] M. Berger, Seules les quadriques admettent des caustiques, _Bull. Soc. math. France_ 123 (1995), 107–116.
  * [5] M. Bialy  Convex billiards and a theorem by E. Hopf.  Math. Z. 124 (1): 147–154, 1993.
  * [6] M. Bialy  Hopf rigidity for convex billiards on the hemisphere and hyperbolic plane.  Discrete Contin. Dyn. Syst. 33 (9): 3903–3913, 2013.
  * [7] M. Bialy and A. Mironov.  Angular Billiard and Algebraic Birkhoff conjecture.  Adv. in Math. 313: 102–126, 2017.
  * [8] M. Bialy and A. Mironov.  The Birkhoff-Poritsky conjecture for centrally-symmetric billiard tables  Annals of Mathematics, 196 (1): 389–413, 2022
  * [9] V. Dragović, M. Radnović, Bicentennial of the Great Poncelet Theorem (1813-2013): Current Advances, Bulletin of the American Mathematical Society 51 (2013), No. 3, 373–445.
  * [10] V. Dragović, M. Radnović, _Poncelet Porisms and Beyond_ , Springer Basel, 2011.
  * [11] V. Dragović, M. Radnović, Ellipsoidal billiards in pseudo-Euclidean spaces and relativistic quadrics, Advances in Mathematics 231 (2012), 1173–1201.
  * [12] C. Fierobe, Complex and projective billiards, periodic orbits and Pfaffian systems, PhD thesis manuscript, 2021.
  * [13] C. Fierobe, Complex Caustics of the Elliptic Billiard, Arnold Math. J. 7 (2021), 1–30. https://doi.org/10.1007/s40598-020-00152-w
  * [14] C. Fierobe, Examples of reflective projective billiards, preprint 2002.09845.pdf
  * [15] C. Fierobe, On projective billiards with open subsets of triangular orbits, to appear in Israel Journal of Mathematics.
  * [16] C. Fierobe, Complex and projective billiards, periodic orbits and Pfaffian systems, thesis manuscript, https://www.theses.fr/230153860.
  * [17] D.I. Florentin, Y. Ostrover and D. Rosen, Caustic-Free Regions for Billiards on Surfaces of Constant Curvature, preprint, arXiv:2102:04914.
  * [18] E. Gutkin and A. Katok, Caustics for Inner and Outer Billiards, Commun. Math. Phys., 173, 1995, 101–133.
  * [19] E. Gutkin and S. Tabachnikov, Billiards in Finsler and Minkowski geometries, Journal of Geom. and Physics, 40 (2002) 277–301.
  * [20] A. A. Glutsyuk, On Two-Dimensional Polynomially Integrable Billiards on Surfaces of Constant Curvature, Dokl. Math. 98 (2018), 382–385.
  * [21] A. A. Glutsyuk, On polynomially integrable Birkhoff billiards on surfaces of constant curvature, J. Eur. Math. Soc. https://www.ems-ph.org/journals/of_article.php?jrn=jems&doi=1027
  * [22] A. A. Glutsyuk, On rationally integrable planar dual multibilliards and piecewise smooth projective billiards, preprint, arXiv:2112.07056.
  * [23] A. A. Glutsyuk, On rationally integrable planar dual multibilliards and piecewise smooth projective billiards, preprint, arXiv:2112.07056.
  * [24] A. A. Glutsyuk, On commuting billiards in higher-dimensional spaces of constant curvature, Pacific Journal of Mathematics, Vol. 305, No. 2, 577–595, 2020.
  * [25] V. Kaloshin and A. Sorrentino, On the local Birkhoff conjecture for convex billiards, Ann. of Math. Vol. 188 (2018), 315–380.
  * [26] B. Khesin, S. Tabachnikov, Pseudo-Riemannian geodesics and billiards, Advances in Mathematics 221 (2009), 1364–1396.
  * [27] I. Koval, Local strong Birkhoff conjecture and local spectral rigidity of almost every ellipse, preprint, arXiv:2111.12171.
  * [28] V. F. Lazutkin, The existence of caustics for a billiard problem in a convex domain, Math. USSR Izv. 7, 1973.
  * [29] J. N. Mather, Glancing billiards, Ergodic Theory Dynam. Systems 2 (3–4), 1982, 397–403.
  * [30] S. Tabachnikov, Exact transverse line fields and projective billiards in a ball, _GAFA Geom. funct. anal._ 7 (1997), 594–608.
  * [31] S. Tabachnikov, Geometry and Billiards, American Mathematical Sociecty, 2005.
  * [32] S. Tabachnikov, Introducing projective billiards, _Ergodic Theory and Dynamical Systems_ 17 (1997), 957–976.


# BioKlustering: a web app for semi-supervised learning of maximally
imbalanced genomic data

Samuel Ozminkowski
Department of Statistics
University of Wisconsin-Madison Yuke Wu∗
Department of Computer Science
University of Wisconsin-Madison Liule Yang
Department of Computer Science
University of Wisconsin-Madison Zhiwen Xu
Department of Statistics
University of Wisconsin-Madison Luke Selberg
Department of Electrical and Computer Engineering
University of Wisconsin-Madison Chunrong Huang
Department of Computer-Science
University of Wisconsin-Madison Claudia Solís-Lemus
Wisconsin Institute for Discovery
Department of Plant Pathology
University of Wisconsin-Madison Joint first authors with equal
contributionCorresponding author<EMAIL_ADDRESS>
###### Abstract

Summary: Accurate phenotype prediction from genomic sequences is a highly
coveted task in biological and medical research. While machine-learning holds
the key to accurate prediction in a variety of fields, the complexity of
biological data can render many methodologies inapplicable. We introduce
BioKlustering, a user-friendly open-source and publicly available web app for
unsupervised and semi-supervised learning specialized for cases when sequence
alignment and/or experimental phenotyping of all classes are not possible.
Among its main advantages, BioKlustering 1) allows for maximally imbalanced
settings of partially observed labels including cases when only one class is
observed, which is currently prohibited in most semi-supervised methods, 2)
takes unaligned sequences as input and thus, allows learning for widely
diverse sequences (impossible to align) such as virus and bacteria, 3) is easy
to use for anyone with little or no programming expertise, and 4) works well
with small sample sizes.

Availability and Implementation: BioKlustering
(https://bioklustering.wid.wisc.edu) is a freely available web app implemented
with Django, a Python-based framework, with all major browsers supported. The
web app does not need any installation, and it is publicly available and open-
source (https://github.com/solislemuslab/bioklustering)

Contact<EMAIL_ADDRESS>
_K_ eywords Supervised learning $\cdot$ Unsupervised learning $\cdot$ Kmers
$\cdot$ Unaligned sequences $\cdot$ Clustering

##  1 Introduction

Background. The accurate prediction of biological features from genomic data
is paramount for precision medicine, sustainable agriculture and climate
change research. Yet some characteristics of big biological data render most
out-of-the-box methodologies inaccurate or inapplicable. In particular, here
we focus on 1) the high complexity (and sometimes impossibility) to align
genomic sequences for certain organisms, and 2) the difficulty to obtain
labeled samples to use in supervised learning.

First, while the growing interest of the biological community in machine-
learning methods is undeniable, many existing methods [1, 2, 3, 4, 5, 6, e.g.]
need DNA or RNA alignments as input. Fast evolving organisms like virus or
bacteria – especially when big sample sizes are needed – muddle the alignment
process with their heterogeneity and genomic diversity to the point that
aligning the sequences becomes extremely challenging or impossible [7, 8].

Second, supervised learning models are the most accurate options for phenotype
prediction. However, these methods rely on large samples of labeled data. In
reality, many biological experiments produce partially observed labels given
the money and time constraints to phenotype organisms or strains. One example
that motivated our work is the case of mycovirus. Mycoviruses infect fungi and
can be used as biocontrol of crop pests given that they induce hypovirulence
on plant fungal pathogens. Not all mycoviruses cause hypovirulence in the
fungal host, and thus, a standard mycovirus dataset will be partially labeled
with some labeled sequences that have been tested in planta for their
hypovirulence potential, and many more unlabeled sequences that have never
been tested in laboratory, and thus, have unknown hypovirulence potential.

Semi-supervised methods [9, 10] allow for partially observed labels, but
existing methods require that we observe labels for all classes – albeit in
smaller frequencies than the unobserved labels. This condition is not met in
the mycovirus dataset, for example, where negative controls (class of
mycoviruses that do not cause host hypovirulence) are not available as
observed labels only correspond to mycoviruses tested in the lab for their
hypovirulence-induced potential. Thus, the use of most semi-supervised methods
is prohibited for this maximally imbalanced dataset.

Main contributions. We present BioKlustering
(https://bioklustering.wid.wisc.edu) a user-friendly open-source web app to
cluster unaligned genomic sequences based on maximally imbalanced partially
observed labels. Unlike most semi-supervised learning methods, our web app
does not require all classes to be observed or has any requirements on class
balance. Also, unlike most machine-learning methods, our web app does not
require large sample sizes. While designed for a semi-supervised setup, our
web app can also be used when no labels are measured (unsupervised case).

One of the main purposes of our web app is to allow easy and fast clustering
of sequences that could inform future biological experiments. Indeed, we see
our web app as a hypothesis-generating tool that will allow biological users,
for example, to identify clusters of mycovirus sequences that could be either
negative controls (from the unobserved class of mycovirus that do not serve as
biocontrol and that have never been tested in planta) or new mycovirus
sequences that could serve as biocontrol for further experimentation.

We highlight that even when our work is visualization-driven, not inferential,
we believe that it fills a important gap for biological scientists who need to
identify similar sequences for experiments when sequence alignment is
prohibited and when in vitro or in planta phenotyping of all labels is not
possible.

##  2 Methods

Input data. Sequences are input as FASTA files and are internally converted to
kmer counts. For example, if a sequence is “ACTGG", then its 3-mers are
[“ACT", “CTG", “TGG"]. The user can select the length of the kmer and
sequences can be aligned or unaligned. Labels are input as an optional
separate csv file. The matching is done by assuming that the rows in both
files are in the same order. The labels file should assign a value of $-1$ to
the sequences of unknown label.

Models. We implement three unsupervised clustering methods which are extended
to the case of partially observed labels by internally optimizing the kmer
length and other parameters until we reach maximum consensus with the observed
labels.

K-means clustering. The algorithm [11] groups the data into $K$ clusters each
formed around a centroid. Each data point is assigned to the nearest centroid,
and these centroids are formed by minimizing the squared Euclidian distances
within each cluster. The mean shift algorithm is used to identity locations of
high density within the kmer space of the data, and then the unsupervised
k-means model is run with these locations as the initial centroid coordinates.
Parameters of this model include the minimum and maximum kmer length, the
random seed, and the number of clusters. Since the mean-shift algorithm does
not allow an input number of clusters, when the number of clusters predicted
by mean-shift exceeds the number of clusters requested, Algorithm 1 (Appendix)
is used to assign output labels.

The unsupervised k-means model can incorporate known labels to create an
effective semi-supervised model. The mean shift algorithm is again used to
identity locations of high density within the kmer space of the data, and then
the unsupervised k-means model is run with these locations as the initial
centroid coordinates. Known labels are then compared against predicted labels
and these clusters are reassigned into groups that minimize the prediction
error.

Gaussian Mixture Model. The algorithm fits a probabilistic model [12] that
estimates the underlying multiple Gaussian distributions that best describe
the clusters in the data. Starting with a random initialization model
parameters, the Expectation-Maximization algorithm runs iteratively until
convergence. Parameters of this model include the minimum and maximum kmer
length, the random seed, the number of classes, and the covariance type (which
determines the shape of the clusters).

The semi-supervised GMM differs from a unsupervised one in the initialization
and parameter selection process. A semi-supervised GMM starts with
initializing means of the known data by their actual means and the rest with
random numbers. A parameter selection process is implemented to compare models
with different parameter combinations (kmer length and four covariance types),
and the model with high accuracy calculated from known labels will be
returned. Finally, for the semi-supervised case only, we use Algorithm 2
(Appendix) to assign output labels from running the GMM to the input labels.

Spectral clustering. This algorithm [13] exploits the potential of eigenvalues
of the matrix derived from the input data. In spectral clustering, the input
data will be treated as a graph, and each sequence will represent a vertex in
the graph. Then, the vertices in the graph will be partitioned based on their
similarities. Parameters of this model are the minimum and maximum kmer
length, the random seed, the number of classes, and the manner in which we
assign labels when the input is projected to a lower dimension space (denoted
label assignment option).

The semi-supervised version of spectral clustering will find the optimal
parameter values (kmer length and label assignment option) that maximizes the
predictive accuracy of the observed labels. We again use Algorithm 2
(Appendix) to assign output labels from running the spectral clustering
algorithm to the input labels.

For all three algorithms, the predicted labels and embedded kmer data can be
used to visualize the clusters using principle component analysis (PCA) or
t-distributed stochastic neighbor embedding (t-SNE).

##  3 Validation with Influenza data

We test our three semi-supervised algorithms with Influenza data from two
classes: bats and cats [14]. We run four settings: totally unsupervised, semi-
supervised with 50% of observed labels (both classes observed), semi-
supervised with 10% observed labels (both classes observed) and semi-
supervised with 10% observed labels (only one class observed). Table 1 shows
the prediction accuracy of the three learning algorithms in BioKlustering. See
the Supplementary Material for clustering figures and more information about
the data.

| k-means | GMM | Spectral
---|---|---|---
Unsupervised | 71.3 | 75.3 | 75.8
Semi-supervised (50%) | 82.6 | 93.8 | 87.1
Semi-supervised (10%) | 73.6 | 90.4 | 75.3
Semi-supervised (10% 0’s) | 71.3 | 51.1 | 70.2

Table 1: Prediction accuracy (%) of the three learning algorithms in
BioKlustering on the Influenza unaligned genome data for two classes (bats and
cats) with respect to all the true labels.

##  4 Web app interface

BioKlustering is an open-source web application developed with Django, a
Python-based framework (Figure 1). The users will be able to predict clusters
in genomic data by 1) uploading FASTA files with (aligned/unaligned) genome
sequences, 2) selecting a clustering algorithm, and 3) choosing in its
corresponding parameters.

BioKlustering provides semi-supervised and unsupervised options depending on
the presence of known labels. For each algorithm, the web app presents a
description to aid users in the choice of parameters. The selected algorithm
will generate prediction results which include an interactive plot (built with
Plotly Dashboard [15]) and a table with predicted labels. Users can download a
static version of the plot, the table, and the parameter information in a zip
file which can also be sent via email.

Open-source code. All of our code is open source in the following GitHub
repository https://github.com/solislemuslab/bioklustering.

Acknowledgements. This work was supported by the Department of Energy [DE-
SC0021016 to CSL]. We thank Dr. Aurelie Rakotondrafara and Helena Jaramillo
Mesa for the motivation on the mycovirus data. We also want to thank Ben
Huebner from the WID IT team who helped with the public deployment of the web
app. Finally, we acknowledge the work in [16] which helped us improve the
scientific writing of this manuscript.

## References

  * [1] Vishal Agarwal, N Jayanth Kumar Reddy, and Ashish Anand.  Unsupervised representation learning of DNA sequences.  arXiv, (1906.03087), June 2019.
  * [2] Wenjie Pei and David M J Tax.  Unsupervised learning of sequence representations by autoencoders.  April 2018.
  * [3] Kamil Wnuk, Jeremi Sudol, Kevin B Givechian, Patrick Soon-Shiong, Shahrooz Rabizadeh, Christopher Szeto, and Charles Vaske.  Predicting dna accessibility in the pan-cancer tumor genome using rna-seq, wgs, and deep learning.  bioRxiv, page 229385, 2018.
  * [4] Peyton Greenside, Tyler Shimko, Polly Fordyce, and Anshul Kundaje.  Discovering epistatic feature interactions from neural network models of regulatory dna sequences.  Bioinformatics, 34(17):i629–i637, 2018.
  * [5] Yi Zhang, Xinan Liu, James N MacLeod, and Jinze Liu.  Deepsplice: Deep classification of novel splice junctions revealed by rna-seq.  In 2016 IEEE international conference on bioinformatics and biomedicine (BIBM), pages 330–333. IEEE, 2016.
  * [6] Hai Thanh Nguyen, Toan Bao Tran, Huong Hoang Luong, Trung Phuoc Le, Nghi C. Tran, and Quoc-Dinh Truong.  K-means clustering for features arrangement in metagenomic data visualization.  In Marcin Hernes, Krystian Wojtkiewicz, and Edward Szczerbicki, editors, Advances in Computational Collective Intelligence, pages 74–86, Cham, 2020. Springer International Publishing.
  * [7] Jie Ren, Xin Bai, Yang Young Lu, Kujin Tang, Ying Wang, Gesine Reinert, and Fengzhu Sun.  Alignment-free sequence analysis and applications.  Annual Review of Biomedical Data Science, 1:93–114, 2018.
  * [8] Julie D Thompson, Benjamin Linard, Odile Lecompte, and Olivier Poch.  A comprehensive benchmark study of multiple sequence alignment methods: current challenges and future perspectives.  PloS one, 6(3):e18093, 2011.
  * [9] Abolfazl Doostparast Torshizi and Linda R Petzold.  Graph-based semi-supervised learning with genomic data integration using condition-responsive genes applied to phenotype classification.  Journal of the American Medical Informatics Association, 25(1):99–108, 2018.
  * [10] Nitin Bhardwaj, Mark Gerstein, and Hui Lu.  Genome-wide sequence-based prediction of peripheral proteins using a novel semi-supervised learning technique.  BMC bioinformatics, 11(1):1–8, 2010.
  * [11] James MacQueen et al.  Some methods for classification and analysis of multivariate observations.  In Proceedings of the fifth Berkeley symposium on mathematical statistics and probability, volume 1, pages 281–297. Oakland, CA, USA, 1967\.
  * [12] Lars Buitinck, Gilles Louppe, Mathieu Blondel, Fabian Pedregosa, Andreas Mueller, Olivier Grisel, Vlad Niculae, Peter Prettenhofer, Alexandre Gramfort, Jaques Grobler, Robert Layton, Jake Vanderplas, Arnaud Joly, Brian Holt, and Gaël Varoquaux.  API design for machine learning software: experiences from the scikit-learn project.  arXiv, (1309.0238), 2013.
  * [13] William Pentney and Marina Meila.  Spectral clustering of biological sequence data.  In AAAI, volume 5, pages 845–850, 2005.
  * [14] https://www.ncbi.nlm.nih.gov/genomes/FLU/Database/.  Influenza virus database.  2020 (accessed July 24, 2020).
  * [15] Mark Gibbs.  django-plotly-dash 1.5.0 https://pypi.org/project/django-plotly-dash/, Date accessed: December 2020\.
  * [16] Scott Hotaling.  Simple rules for concise scientific writing.  Limnology and Oceanography Letters, 5(6):379–383, 2020.

Figure 1: Top: The Upload File section contains two file upload boxes, one for
sequence file and one for label file. The uploaded files will be saved to the
file list. Middle: The Predict section contains a drop-down menu that displays
the three clustering algorithms at the left-hand side and a parameter form at
the right-hand side. Bottom: The Result page contains an interactive plot
built with Plotly Dashboard and a table with predicted labels. All output
files can be downloaded or sent via email.

##  5 Supplementary Material

###  5.1 Algorithms

Result: Labeled data

if  _number of clusters predicted $\geq$ number of clusters requested_ then

N $\leftarrow$ number of clusters requested;

Sort clusters by size;

for  _i $\in\mathbb{Z}$, i $\leq$ number of clusters predicted _ do

if  _ $i\leq$ number of clusters requested_ then

assign label $i$ to points in sorted cluster $i$ ;

else

assign label N to points in sorted cluster $i$;

Algorithm 1 K-Means Cluster Label Assignment

Result: Labeled data

MAX_VALUE $\leftarrow$ $\max$(labels input) + 1

GIVEN_LABELS_CT $\leftarrow$ dictionary: {given label $\to$ #{given labels}},
sorted by value

PRED_LABELS_CT $\leftarrow$ dictionary: {predicted label $\to$ #{predicted
labels}}, sorted by value

UNSELECTED_PRED $\leftarrow$ PRED_LABELS_CT

map_predict_to_actual $\leftarrow$ empty dictionary

for  _given_label $\in$ GIVEN_LABELS_CT _ do

pred_results $\leftarrow$ predicted labels whose true label matches
given_label

unique_predicted $\leftarrow$ unique(pred_results) $\cap$ UNSELECTED_PRED

if  _unique_predicted $=\emptyset$ _ then

continue

predicted_labels_ct $\leftarrow$ dictionary: {unique_predicted $\to$
#{unique_predicted = pred_results}}

map_predict_to_actual[$\max$ (unique_predicted)] $\leftarrow$ given_label

remove $\max$ (unique_predicted) from UNSELECTED_PRED

for  _unique_predicted_label_unselected $\in$ UNSELECTED_PRED_ do

map_predict_to_actual[unique_predicted_label] $\leftarrow$ MAX_VALUE

MAX_VALUE $\leftarrow$ MAX_VALUE + 1

output $\leftarrow$ []

for  _i $\in$ {0,…,#predictions}_ do

if  _no label was input for index i_ then

output[i] $\leftarrow$ map_predict_to_actual[predicted label i]

else

output[i] $\leftarrow$ input[i]

Algorithm 2 Cluster Label Assignment

###  5.2 Validation with Influenza data

We downloaded 64 unaligned nucleotide sequences for bat Influenza virus with
lengths between 844 and 2339 bp and 114 unaligned nucleotide sequences for cat
Influenza virus with lengths between 538 and 2341 bp from the NCBI database
[14]. We use the whole dataset as training given the small sample size.

For this data, we have the labels for all sequences, but we run our learning
algorithms under four settings: 1) unsupervised (ignored all labels), 2) semi-
supervised with 50% of observed labels randomly selected, 3) semi-supervised
with 10% of observed labels randomly selected, and 4) semi-supervised with 10%
of observed labels from one class only. Out of the 50% observed labels, 36% of
them correspond to the class of bats and 64% to the class of cats. Out of the
10% observed labels, 41% of them correspond to the class of bats and 59% to
the class of cats when both classes are observed, and 100% correspond to the
class of bats when only one class is observed.

Table 1 (main text) shows the prediction accuracy of the three methods in
BioKlustering: k-means, GMM and spectral clustering.

For the k-means method, the chosen parameters that maximize the agreement with
the observed labels are $k_{min}=5,k_{max}=7$ in all four cases.

For the GMM method, the chosen parameters that maximize the agreement with the
observed labels are

  * •

$k_{min}=2,k_{max}=6$ with covariance type as “full" for the unsupervised
case,

  * •

$k_{min}=4,k_{max}=5$ with covariance type as “diagonal" for the semi-
supervised case with 10% labels observed (both classes),

  * •

$k_{min}=2,k_{max}=5$ with covariance type as “full" for semi-supervised case
with 10% observed labels (only 0’s),

  * •

$k_{min}=3,k_{max}=4$ with covariance type as "tied" for the semi-supervised
case with 50% labels observed.

For the spectral clustering, the chosen parameters that maximize the agreement
with the observed labels are

  * •

$k_{min}=2,k_{max}=3$ with k-means label assign option for the unsupervised
case,

  * •

$k_{min}=k_{max}=3$ with discretize label assign option for the semi-
supervised case with 10% labels observed (both classes),

  * •

$k_{min}=k_{max}=2$ and label assign option as discretize for when only 0’s
are observed,

  * •

there were two setups with the same accuracy for the semi-supervised case with
50% observed labels: $k_{min}=k_{max}=2$ with k-means label assign option and
$k_{min}=3,k_{max}=5$ with discretize label assign option.

In all cases, the true number of classes is selected (2) and we do not test
the performance when the number of clusters is not known in advance.

Table 2 shows the prediction accuracy of the three clustering methods
comparing only the observed labels. Even when we always return the observed
labels, they are used internally to modify the parameters to maximize
agreement between predicted labels and observed labels.

| k-means | GMM | Spectral
---|---|---|---
Semi-supervised (50%) | 77.5 | 100 | 74.2
Semi-supervised (10%) | 76.5 | 100 | 76.5
Semi-supervised (10% 0’s) | 100 | 100 | 100

Table 2: Prediction accuracy (%) of the three learning algorithms in
BioKlustering on the Influenza unaligned genome data for two classes (bats and
cats) with respect to the observed labels.

Finally, Figure 2 shows the clustering visualization via PCA of the spectral
clustering (top), the k-means clustering (middle), and the GMM clustering
(bottom).

Figure 2: Clustering visualization of bats and cats Influenza data for the
three methods in BioKlustering. Top: spectral clustering. Middle: k-means
clustering. Bottom: GMM clustering. There are three settings per method:
unsupervised (no labels observed), semi-supervised with 10% labels observed
(both classes or only one class observed) and semi-supervised with 50% labels
observed. Color represents predicted labels: green for bats (label 0) and blue
for cats (label 1). Point shapes represent true labels: circle for bats (label
0) and triangle for cats (label 1). Green circles or blue triangles correspond
to correctly predicted labels, while green triangles and blue circles
correspond to wrongly estimated labels.