text:
\section*{Appendix: Additional proofs, examples and data}

This paper is concerned with finding special surfaces in 3--manifolds. To keep the paper short, we mainly considered the case of finding a closed essential surface in a knot exterior in $S^3,$ and have introduced the bare minimum of the new theory and algorithms required for this application. The most natural generalisation of our results and algorithms is to the setting of compact 3--manifolds with boundary consisting of a finite union of tori. These manifolds are related to the Geometrisation Theorem of Thurston and Perelman, as they are key building blocks in the so-called JSJ decomposition of a closed, irreducible, orientable 3--manifold into geometric pieces.

\section{General definitions}

In this first appendix, we give more technical definitions of knot and link manifolds, essential surfaces, triangulations and normal surfaces.

\subsection{Knots and 3--manifolds}

Suppose $M$ is an orientable 3--manifold (possibly with boundary). There
are two key properties that are often required of $M$ in geometric
topology. The first is that every embedded 2--sphere in $M$ bounds a ball to at
least one side; in this case $M$ is \emph{irreducible}. The second is
that for each boundary component $B$ of $M,$ the inclusion homomorphism
$\pi_1(B)\to \pi_1(M)$ is injective; in this case $M$ is
$\partial$--irreducible. (A geometric interpretation of this algebraic
property is given in the next section.) For instance, the 3--sphere
$S^3$ is irreducible, and if $K$ is an embedding of $S^1$ in $S^3,$
called a \emph{knot}, then the \emph{knot exterior} $M= S^3\setminus
N(K),$ where $N(K)$ is a small open neighbourhood of $K,$ is also
irreducible, and it is $\partial$--irreducible if and only if $K$ is
non-trivial.
The \emph{knot complement} $S^3\setminus K$ is homeomorphic
to the interior of the knot exterior $S^3\setminus N(K),$ and it is
sometimes useful to switch between the complement (a non-compact
manifold) and the exterior (a manifold-with-boundary).

\subsection{Surfaces in 3-manifolds}
\label{subsec:essential}

The following definition of an essential surface, along with an extensive discussion of their properties, can be found in Shalen \cite{shalen02-representations}, \S1.5.

\begin{defn}[Essential surface]
A properly embedded surface $S$ in the compact, irreducible, orientable 3--manifold $M$ is \emph{essential} if it has the following properties:
\begin{enumerate}
\item $S$ is bicollared;
\item the inclusion homomorphism $\pi_1(S_i)\to \pi_1(M)$ is injective for each component $S_i$ of $S$;
\item no component of $S$ is a 2--sphere;
\item no component of $S$ is boundary parallel; and
\item $S$ is non-empty.
\end{enumerate}
\end{defn}

Of interest to this paper is the following geometric interpretation of the second property, see Shalen \cite{shalen02-representations} for more details. A \emph{compression disc} for the surface $S$ is a disc $D\subset M$ such that $D \cap S = \partial D$ and $\partial D$ is homotopically non-trivial in $S$ (i.e. does not bound a disc on $S$). In particular, if $S$ has a compression disc, then $\pi_1(S_i)\to \pi_1(M)$ is not injective for some component of $S.$ It follows from classical work of Papakyriakopoulos that the converse is also true. Detecting compression discs is the topic of Section~\ref{sec:Detecting compressing discs}.

If the surface $S$ has non-empty boundary and is properly embedded in a 3--manifold with boundary, there is an additional requirement that one has in order for $S$ to be topologically significant; namely that it be \emph{$\partial$--incompressible}. In the case of interest for this paper, where all boundary components of $M$ are tori, it turns out that incompressible implies $\partial$--incompressible. This is one reason why our algorithms most naturally generalise to the class of link complements.

\subsection{Triangulations}
\label{subsec:Triangulations}

The notation of \cite{jaco03-0-efficiency} and \cite{tillmann08-finite} will be used in this paper. A \emph{triangulation}, $\mathcal{T},$ of a compact 3--manifold $M$ consists of a union of pairwise disjoint 3--simplices, $\widetilde{\Delta} = \{ \sigma_1, \ldots, \sigma_t\},$ a set of face pairings, $\Phi,$ and a natural quotient map $p\colon\thinspace \widetilde{\Delta} \to \widetilde{\Delta} / \Phi = M.$ Since the quotient map is injective on the interior of each 3--simplex, we will refer to the image of a 3--simplex in $M$ as a \emph{tetrahedron} and to \emph{its} faces, edges and vertices with respect to the pre-image. Similarly for images of 2--, 1-- and 0--simplices, which will be referred to as \emph{faces}, \emph{edges} and \emph{vertices} in $M$ respectively.
If an edge is contained in $\partial M,$ then it is termed a \emph{boundary edge}; otherwise it is an \emph{interior edge}.

If $M$ is the interior of a compact manifold with non-empty boundary, an \emph{ideal triangulation}, $\mathcal{T},$ of $M$ consists of a union of pairwise disjoint 3--simplices, $\widetilde{\Delta},$ a set of face pairings, $\Phi,$ and a natural quotient map $p\colon\thinspace \widetilde{\Delta} \to \widetilde{\Delta} / \Phi = P,$ such that $M = P \setminus P^{(0)}$ is the complement of the 0--skeleton. The quotient space $P$ is usually called a \emph{pseudo-manifold}.

For brevity, we will refer to a 3--manifold $M$ imbued with a (possibly ideal) triangulation $\mathcal{T}=(\widetilde{\Delta}, \Phi, p)$ as a
\emph{triangulated 3--manifold}. Throughout, we will assume that $M$ is \emph{oriented}, that all tetrahedra in $M$ are oriented coherently and the tetrahedra in $\widetilde{\Delta}$ are given the induced orientation.

\subsection{Normal surfaces}

A \emph{normal corner} is an interior point of a 1--simplex. A \emph{normal arc} is a properly embedded straight line segment on a 2--simplex with boundary consisting of normal corners. A \emph{normal disc} is a properly embedded disc in a 3--simplex whose boundary consists of normal arcs no two of which are contained on the same face of the 3--simplex; moreover, the normal disc is the cone over its boundary with cone point the barycentre of its normal corners. It follows that the boundary of a normal disc consists of either three or four normal arcs, and it is accordingly called a \emph{normal triangle} or a \emph{normal quadrilateral}. Moreover, a normal disc is uniquely determined by its intersection with the 1--skeleton.

A \emph{normal isotopy} is an isotopy of $M$ that leaves all simplices invariant. Up to normal isotopy, there are 7 types of normal discs in each tetrahedron. We denote $\square$ the set of all isotopy classes of normal quadrilaterals in $\widetilde{\Delta},$ and identify this with the set of all isotopy classes of normal quadrilaterals in $M$ via $p.$ Following Haken, we will connect topology to linear programming via certain functions $x\colon\thinspace \square \to \mathbb{R}^{3t}.$

A \emph{normal surface} $S$ in a triangulated 3--manifold is a properly embedded surface which intersects each 3--simplex in a union of pairwise disjoint normal discs; such a surface is often termed a \emph{spun-normal} surface if one of its connected components contains infinitely many normal discs.

\subsection{Standard coordinates}

In classical normal surface theory one only considers normal surfaces where each tetrahedron contains at most finitely many disjoint normal disks. The number of parallel copies each type of normal disk specifies the normal surface, and in this way normal surfaces may be studied via $7t$-dimensional vectors with positive integer coordinates, where $t$ is the number of tetrahedra in the triangulation under consideration. These surfaces can be described by a set of linear equations arising from the fact that the normal discs in one tetrahedron have to match up with normal discs in each adjacent tetrahedron across their common face. If $\Delta$ denotes the set of all normal isotopy classes of normal triangles, then the natural coordinate projection $\mathbb{R}^{\Delta \cup \square} \to \mathbb{R}^\square$ takes the standard coordinate of a normal surface to its $Q$--coordinate.

\begin{figure}[h!]
\centering
\includegraphics[width=0.15\textwidth]{trianglefixed}
\caption{The intersection of a normal surface with a typical face of
the 2-skeleton.} \label{3arcst}
\end{figure}

Consider a face of the 2-skeleton of
the triangulation of $M$. Any normal surface in $M$ must intersect
this triangle in \emph{normal arcs}, that is arcs which start and
end on different edges.
There are three types of normal arc in any face of the 2-skeleton,
as shown in Figure \ref{3arcst}. Each of these represents an edge of
a normal disc on each side. These normal discs must match up, as
shown in Figure \ref{matchup}. Note that on each side of a triangle
of the 2-skeleton, there are only two possible types of normal disc,
one triangle and one quadrilateral, which can give rise to each type of
normal arc.

\begin{figure}[h!]
\centering
\includegraphics[width=0.4\textwidth]{addup}
\caption{The normal discs must match up on the common face of two
adjacent tetrahedra.} \label{matchup}
\end{figure}

Let $t_1,$ $q_1$ be the normal triangle and quadrilateral types in one tetrahedron, sharing the same normal arc type with the normal triangle and quadrilateral types $t_2$ and $q_2$ in an adjacent tetrahedron. We then obtain the linear equation
$$
t_1 + q_1 = t_2 + q_2,
$$
with three such equations for each internal face of the triangulation. The space of all non-negative solutions to these equations in $\mathbb{R}^{\Delta \cup \square}$ is the usual normal surface cone.

\section{Example: The figure-eight knot}
\label{app:fig8}

\begin{figure}[h]
  \begin{center}
      \subfigure[The figure 8 knot spans a Klein bottle]{
      \includegraphics[scale=0.6]{fig8socg}}
      \qquad\qquad
    \subfigure[Thurston's ideal triangulation of the complement]{
      \includegraphics[scale=0.9]{fig8_tri}}
  \end{center}
 \caption{The figure eight knot}
    \label{fig:fig8_tets}
\end{figure}

Let $M$ denote the complement of the figure eight knot, which is shown in Figure \ref{fig:fig8_tets}(a). An oriented, ideal triangulation of $M$ is encoded in Figure \ref{fig:fig8_tets}(b). Since $M$ is oriented, we may compute the $Q$--matching equations from the figure. To simplify notation, we use the dual labelling scheme of \cite{tillmann08-finite}, and denote the quadrilateral types dual to the edges labelled $w^{(k)}$ and $z^{(k)}$ by $p^{(k)}$ and $q^{(k)}$ respectively. The $Q$--matching equations for the two edges are equivalent, and one has:
\begin{equation*}
0 = p + p' - 2 p''+q + q' - 2 q''.
\end{equation*}
This implies that the cone $Q(\mathcal{T} )$ is five--dimensional.
A direct calculation reveals that $Q (\mathcal{T} )$ has four admissible extremal  rays; all have minimal representative a once--punctured Klein bottle; such a Klein bottle is shown in Figure \ref{fig:fig8_tets}(a).
Their normal $Q$--coordinates and boundary slopes are listed in Table \ref{tab:surfaces fig8}. This calculation in particular shows that no spun-normal surface is a Seifert surface for the knot.

\begin{table}[h]
\begin{center}
\begin{tabular}{ c | r | r | r}
solution & $\nu (\mu )$  & $\nu (\lambda )$ & slope \\
\hline
(2,0,0,0,0,1) & 1 &4  &        --4  \\
(0,2,0,0,0,1) & --1 & 4  &       4   \\
(0,0,1,2,0,0) & --1 & --4  & --4 \\
(0,0,1,0,2,0) &  1&  --4  &     4 \\
\end{tabular}
\end{center}
\caption{Normal surface in the figure eight knot complement}
\label{tab:surfaces fig8}
\end{table}

The induced triangulation of a vertex linking torus, $T,$ is shown in Figure \ref{fig:torus triang fig8}.
The dual labelling allows us to read off the linear functional $\nu(\gamma)$ for the path $\gamma$ that is transverse to the 1--skeleton on $T.$ If the path $\gamma$ on $T$ exits a triangle across the edge opposite the vertex with label $w^{(k)},$ then in $\nu(\gamma),$ we record $-p^{(k)},$ and if it enters a triangle across the edge opposite the vertex labelled $w^{(k)},$ then in $\nu(\gamma),$ we record $+p^{(k)}.$ Similarly for the labels $z^{(k)}.$

\begin{figure}[h!]
\begin{center}
  \includegraphics{fig8_torustriang}
\end{center}
    \caption{The induced triangulation of the vertex linking torus, where the sides of the rectangle are identified by translations parallel to its sides and triangle $i$ is dual to vertex $i$ in Figure~\ref{fig:fig8_tets}. The shown elementary curves are the standard meridian $\mu$ (solid) and longitude $\lambda$ (dashed).}
    \label{fig:torus triang fig8}
\end{figure}

In this fashion (and using the $Q$--matching equation to simplify the expressions), we determine the linear functionals associated to the standard peripheral curves:
\begin{align*}
\nu (\lambda ) &=  2 p +2 p' - 4 p'',\\
\nu (\mu ) &= -p'+p''-q+q''.
\end{align*}
One can now verify that $Q_0(\mathcal{T} )=\{0\}.$ Whence any closed embedded normal surface is a union of vertex linking tori.

\section{Proof of Theorem~\ref{thm:some extremal is closed essential}}
\label{app:Jaco-Oertel}

In this appendix, we prove Theorem~\ref{thm:some extremal is closed essential} in the more general setting of a 3--manifold with boundary consisting of a union of tori. The definition of the boundary map and of $Q_0(\mathcal{T})$ is generalised to the case of multiple boundary components as follows. For each vertex linking torus $T_k,$ we obtain a well-defined homomorphism $\nu_{k,x}\colon\thinspace H_1(T_k; \mathbb{R}) \to \mathbb{R},$ and we define $\nu_x = \oplus_k\; \nu_{k,x},$ where the sum is taken over all ideal vertices. The surface in Theorem~\ref{thm:admissible integer solution gives normal} is closed if and only if $\nu_x =0$ (see \cite{tillmann08-finite}, Proposition 3.3). We then define $Q_0(\mathcal{T}) = Q(\mathcal{T}) \cap \{ x \mid \nu_x=0\},$  and call a 2--sided, connected normal, surface $F$ with $Q(F)$ on an extremal ray of $Q_0(\mathcal{T})$ a \emph{$Q_0$--vertex surface.}

The weight of the normal surface $F$ is the cardinality of its intersection with the 1--skeleton,  $\wt(F) = |F \cap M^{(1)}|.$ If $F$ is closed, then its weight is finite.

\begin{figure}[h]
\begin{center}
  \subfigure[]{
      \includegraphics[height=5cm]{Q_reg_exch2}
    }
    \quad
\subfigure[]{
      \includegraphics[height=5cm]{Q_reg_exch1}
    }
    \quad
\subfigure[]{
      \includegraphics[height=5cm]{Q_reg_exch3}
    }
    \quad
\subfigure[]{
      \includegraphics[height=5cm]{Q_reg_exch4}
    }
\end{center}
    \caption{Regular exchange of normal discs}
     \label{fig:regular exchange of discs}
\end{figure}

Two normal surfaces are \emph{compatible} if they do not meet a tetrahedron in quadrilateral discs of different types. In this case, the sum of their normal coordinates is the coordinate of a normal surface.
Suppose $F_1$ and $F_2$ are normal surfaces that are compatible, not vertex linking surfaces, and in general position.
Then $x(F_1)+x(F_2)$ is an admissible solution to the $Q$--matching equations, and hence represented by a unique normal surface without vertex linking components; denote this surface $F.$ The surface $F$ is obtained geometrically as follows. At each component of $F_1 \cap F_2,$ there is a natural choice of \emph{regular switch} between normal discs, such that the result is again a normal surface. See Figure~\ref{fig:regular exchange of discs} for some possible configurations involving only two discs. Denote $N(F_1 \cap F_2)$ a small, open, tubular neighbourhood of $F_1 \cap F_2.$
The connected components of $(F_1 \cup F_2) \setminus N(F_1 \cap F_2)$ are termed \emph{patches}.

Deleting any vertex linking tori that arise gives the surface $F,$ and we write $F + \Sigma = F_1 + F_2,$ where $\Sigma$ is (possibly empty or a possibly infinite) union of vertex linking tori. This is called the \emph{Haken sum} of $F_1$ and $F_2.$
Both weight and Euler characteristic are additive under this sum. So we have
\begin{align*}
\wt(F_1) + \wt(F_2) &=\wt(F) + \wt(\Sigma),\\
\chi(F_1) + \chi(F_2) &=\chi(F),
\end{align*}
since $\chi(\Sigma)=0.$

The sum $F+\Sigma=F_1 + F_2$ is said to be in \emph{reduced form} if there is no Haken sum $F+\Sigma'=F'_1 + F'_2,$ where $F'_i$ is isotopic to $F_i$ in $M,$
 $F'_1 \cap F'_2$ has fewer components than $F_1 \cap F_2$ and $\Sigma'$ is a union of vertex linking tori.
  It should
be noted that in these two sums, the embedding of $F$ in $M$ is the same
(these are not equalities up to isotopy), and that any sum can be
changed to a sum in reduced form.

\begin{reptheorem}{thm:some extremal is closed essential}
Suppose $M$ is the interior of a compact, irreducible and $\partial$--irreducible manifold with boundary consisting of a union of tori, and let $\mathcal{T}$ be an ideal triangulation of $M.$ If $M$ contains a closed, essential surface $S,$ then there is a normal, closed essential surface $F$ with the property that $x(F)$ lies on an extremal ray of $Q_0(\mathcal{T}).$ Moreover, if $\chi(S)<0,$ then there is such $F$ with $\chi(F)<0.$
\end{reptheorem}

\begin{proof}
Suppose $M$ contains a closed, essential surface. It follows from a standard argument (see, for instance, \cite{jaco84-haken} and \cite{jaco03-0-efficiency}) that there is a closed, essential, normal surface $S$ in $M.$ It remains to show that $S$ may be chosen such that $S$ is a $Q_0$--vertex surface. Replace $S$ by a normal surface that has least weight amongst all normal surfaces isotopic (but not necessarily normally isotopic) to $S.$ Denote this least weight surface $S$ again.

Suppose $S$ is not a $Q_0$--vertex surface. Then $$n x(S) = \sum n_i x(V_i),$$ where $n, n_i \in \mathbb{N}$ and either $V_i$ or $2V_i$ is a $Q_0$--vertex surface for each $i.$ The two cases arise from the fact that we require a $Q_0$--vertex surface to be 2--sided and connected: If $V$ corresponds to the first integer lattice point on an admissible extremal ray of $Q_0(\mathcal{T})$ and $V$ is 1--sided, then the corresponding $Q_0$--vertex surface is $2V,$ obtained by taking the boundary of a regular neighbourhood of $V.$

We denote $nS$ the normal surface obtained by taking $n$ parallel copies of $S.$ Clearly, $x(nS) = nx(S),$ and since $S$ has least weight normal surface in its isotopy class, so does $nS$ because $S$ is 2--sided. To sum up, $nS$ is a closed, essential, normal surface which has least weight amongst all normal surfaces in its isotopy class.

For any $i,$ either $V_i$ or $2V_i$ is a $Q_0$--vertex surface. In the first case, we can write
$$nS + \Sigma = V + W,$$
where  $V = V_i$ and $x(W) =  -x(V_i) + \sum n_i x(V_i).$ Now $nS$ is 2--sided and of least weight, so Kang~\cite{kang05-spun}, Theorem 5.4 (which is an adaptation of the proof of \cite{jaco84-haken}, Theorem 2.2, to this context), shows that if one writes $nS + \Sigma = V' + W'$ in reduced form, then $V'$ is incompressible. Now $V'$ is isotopic in $M$ to $V,$ and hence $V$ is also incompressible. If $2V_i$ is a $Q_0$--vertex surface, then we apply the above argument to $2nS,$ writing $2nS + \Sigma = V + W,$ where $x(V)=2x(V_i)$ and
$x(W) =  -x(V) + 2\sum n_i x(V_i).$ In either case, we obtain an incompressible $Q_0$--vertex surface $V.$ Since Euler characteristic is additive and $S$ is not a sphere, there is some $V_i$ with $\chi(V_i)\le 0.$ If $\chi(V_i)<0,$ then $V$ is essential, and if $\chi(V_i)=0,$ then $V$ may be essential or boundary-parallel. Hence if $\chi(S)<0,$ the proof of the theorem is complete.

Hence assume $\chi(S)=0,$ and finish the proof with an argument from the proof of Proposition 6.3.21 from \cite{matveev03-algms}. For the sake of a contradiction, suppose that some $V_i$ is a boundary parallel torus that is not vertex linking. Write  $nS + \Sigma = V + W,$ where $V$ is a boundary parallel torus that is not vertex linking, and suppose that the sum is in reduced form. As in \cite{jaco84-haken}, Lemma 2.1, it follows that each patch is incompressible and not a disc. Denote $M_2$ a component of $M \setminus V$ that is homeomorphic to $V \times (0,1).$ If $W \cap M_2\neq \emptyset,$ then it consists of a pairwise disjoint union of annuli. Choosing an innermost annulus $A \subseteq W \cap M_2,$ there is an annulus $A' \subseteq V$ such that $\partial A' = \partial A,$ and there is an isotopy from $A$ to $A'$ keeping the boundaries fixed. But this implies that $V + W$ is not in reduced form, giving a contradiction.
\end{proof}

\begin{remark}
The statement of Theorem~\ref{thm:some extremal is closed essential} considerably strengthens the statement of Theorem~5.5 in \cite{kang05-spun}, and our proof fills a gap in its proof.
\end{remark}

\section{Proof of Theorem~\ref{thm-incompressible}} \label{app-incompressible}

Here we give a full proof of correctness for
Algorithm~\ref{alg-incompressible}.  Recall that this algorithm takes
a closed two-sided normal surface $S$ of genus $g$ within an ideal
triangulation $\mathcal{T}$ of a knot complement in $S^3$, and tests whether
this surface is incompressible.

\begin{reptheorem}{thm-incompressible}
    Algorithm~\ref{alg-incompressible} terminates, and its output is correct.
\end{reptheorem}

\begin{proof}
    As noted in the main body of the paper, termination is
    straightforward: each time we loop back to step~\ref{en-alg-simplify}
    we have strictly fewer tetrahedra than before.  We now devote
    ourselves to proving the many claims that are made throughout the
    statement of Algorithm~\ref{alg-incompressible}.

    Before proceeding, however, we make a brief note regarding
    irreducibility.
    Since the underlying knot is embedded in $S^3$,
    every sphere in the complement $M$ must bound a ball; that is,
    $M$ is irreducible.  As a result, the two manifolds $M_1$ and $M_2$
    are likewise irreducible, with the following possible exception:
    it might be the case that $M_2$ has an embedded sphere that
    separates the genus $g$ boundary $B_2$ on one side from the
    torus boundary $B_v$ on the other.  However, in this case (by
    reattaching $M_1$) we find that $S$ is contained in a 3-ball within
    the complement $M$; in particular, $S$ has a compressing disc within
    $M_1$.

    We proceed now with proofs of the various claims made in
    Algorithm~\ref{alg-incompressible}.

    \begin{itemize}
        \item \emph{In step~\ref{en-alg-truncate} we claim that cutting along
        $S$ yields two compact manifolds}.

        This is because $S$ is a closed surface embedded in a knot
        complement, which itself is a submanifold of the 3-sphere.
        Since every closed surface in the 3-sphere is separating, the
        claim follows.

        \item \emph{In step~\ref{en-alg-nodisc} we claim that, if the surface
        $E$ cannot be found in $\mathcal{T}_1$ \emph{and} it cannot be found in
        $\mathcal{T}_2$, then the original surface $S$ must be incompressible.}

        Suppose that $S$ were compressible, with a compression disc
        in some $M_i$.  If this $M_i$ is irreducible,
        then by a result of Jaco and Oertel \cite[Lemma~4.1]{jaco84-haken}
        there is a \emph{normal} compressing disc in $\mathcal{T}_i$.
        Since the underlying knot is non-trivial, this compressing disc
        must meet the genus $g$ boundary $B_i$ (not the torus
        boundary $B_v$), and so it is a surface of the type we are
        searching for.
        If $M_i$ is reducible then (from earlier) we have $i=2$, there
        is a compressing disc within the irreducible manifold $M_1$, and
        by the argument above the surface $E$ can be found within $\mathcal{T}_1$.

        \item \emph{In step~\ref{en-alg-crush} we claim that
        the new triangulation $\mathcal{T}'_i$ has strictly fewer tetrahedra
        than $\mathcal{T}_i$.}

        This is because $E$ is connected but not a vertex link, and
        therefore contains at least one normal quadrilateral.
        As noted in Section~\ref{subsec:Crushing},
        this means that at least one tetrahedron of $\mathcal{T}_i$ is deleted
        in the Jaco-Rubinstein crushing process.

        \item \emph{In step~\ref{en-alg-crush} we claim that
        if $\mathcal{T}'_i$ has a component with the same genus boundary
        (or boundaries) as $\mathcal{T}_i$ then this component represents the same
        manifold $M_i$, and if not then $S$ is compressible.}

        Since the surface $E$ that we crush is connected with positive
        Euler characteristic and can be embedded within a knot complement
        (and hence the 3-sphere), it follows that $E$ is either a sphere
        or a disc.
        From Section~\ref{subsec:Crushing}, this means that when we crush $E$
        in the triangulation $\mathcal{T}_i$, the resulting manifold is obtained
        from $M_i$ by zero or more of the following operations:
        \begin{itemize}
            \item undoing connected sums;
            \item cutting open along properly embedded discs;
            \item filling boundary spheres with 3-balls;
            \item deleting 3-ball, 3-sphere, $\mathbb{R} P^3$, $L_{3,1}$ or
            $S^2 \times S^1$ components.
        \end{itemize}

        We first note that, since all of the manifolds we consider can
        be expressed as submanifolds of $S^3$, we will never create or
        delete an $\mathbb{R} P^3$, $L_{3,1}$ or $S^2 \times S^1$ component.

        Suppose that $M_i$ is irreducible.  Then undoing a connected sum
        simply has the effect of creating an extra 3-sphere component.
        If we ever cut along a properly embedded disc that is \emph{not}
        a compressing disc, then likewise this just creates an extra
        3-ball component.  If we cut along a compressing disc, then
        this yields one or two pieces with strictly smaller total
        boundary genus than before; moreover, since the underlying knot
        is non-trivial, the first such compression must take place along
        the genus $g$ boundary $B_g$ (not $B_v$) and so $S$ must be
        compressible.  Together these observations establish the full
        claim above.

        If $M_i$ is not irreducible, then as noted above $i=2$, and
        $M_2$ must contain a sphere that separates the boundary component
        $B_2$ from $B_v$.  Here there is an extra complication:
        either undoing a connected sum or cutting along a non-compressing disc
        might have the effect of splitting the manifold into two
        components, one with the single boundary $B_2$ and the other
        with the single boundary $B_v$.  In this case there will no
        longer be a component in $\mathcal{T}_2'$ with the same genus boundaries
        as $\mathcal{T}_2$; however, as noted earlier $S$ is compressible on
        the side of $M_1$, and so the claim above remains correct.
        \qedhere
    \end{itemize}
\end{proof}

\section{Proof of Theorem~\ref{thm-large}} \label{app-large}

Our final proof is of the correctness of Algorithm~\ref{alg-large},
the full algorithm for testing whether a non-trivial knot $K$ in $S^3$ is
large.

\begin{reptheorem}{thm-large}
    Algorithm~\ref{alg-large} terminates, and its output is correct.
\end{reptheorem}

\begin{proof}
    As noted in the main body of the paper, it is clear that the
    algorithm terminates since there is no looping.  All that remains is
    to prove that its output is correct.

    Throughout this proof we
    implicitly use Theorem~\ref{thm-incompressible} to verify that
    all calls to Algorithm~\ref{alg-incompressible} are themselves correct.
    We note that, since the knot $K$ is non-trivial, the complement
    is irreducible and $\partial$--irreducible and so the conditions of
    Theorem~\ref{thm:some extremal is closed essential} apply.
    We also note that all closed surfaces embedded in a knot complement
    in $S^3$ must be orientable, and so we implicitly treat all closed surfaces
    as orientable from here onwards.

    From Theorem~\ref{thm:some extremal is closed essential},
    the knot $K$ is large if and only if one of the closed normal
    surfaces $S_i$ in our list (excluding spheres) is essential.
    We note that each genus $\geq 2$ surface in the list is essential
    if and only if it is incompressible (since such a surface cannot be
    boundary parallel),
    and each torus in the list is essential if and only if it is
    (i)~incompressible and (ii)~not boundary parallel.

    Steps~\ref{en-test-essential} and \ref{en-test-special} of
    Algorithm~\ref{alg-large} test precisely these conditions, and so
    the algorithm is correct.  The only reason for the complex logic in
    these steps is so that we can use Algorithm~\ref{alg-incompressible}
    exclusively if possible, and only fall through to the more expensive
    Jaco-Tollefson algorithm when absolutely necessary.
\end{proof}

\section{Tables of large knots} \label{app-knots}

We finish with the detailed results of running
Algorithm~\ref{alg-large} over all $2977$ knots in the census of
non-trivial prime knots with $\leq 12$ crossings.
The following list presents all $1019$ knots in this census
that are large.  The knots are identified using
their names in the {\emph{KnotInfo}} database \cite{www-knotinfo}.

\input{largetable.tex}

\section{Closed normal surfaces in $Q$--space}
\label{sec:closed}

In this section we introduce the linear \emph{boundary equations},
with which we restrict the normal surface solution space to
closed surfaces only.

Let our knot complement be $M = S^3\setminus K.$ The ideal triangulation $\mathcal{T}$ of $M$ has one ideal vertex, and its link is a torus. We view this torus $T$ as made up of normal triangles, one near each corner of each ideal tetrahedron. Let $\gamma \in H_1(T; \mathbb{R}).$ We now describe an associated linear functional $\nu(\gamma) \colon\thinspace \mathbb{R}^{\square}\to \mathbb{R},$ which measures the behaviour along $\gamma$ of a normal surface near the ideal vertex. The idea is similar to the intuitive description of the $Q$--matching equations. As one goes along $\gamma$ and looks down into the manifold, normal quadrilaterals will (as Jeff Weeks puts it) \emph{come up from below} or \emph{drop down out of sight}. If the total number coming up minus the total number dropping down is non-zero, then the surface spirals towards the knot in the cross section $\gamma \times [0, \infty) \subset T \times [0, \infty)$ and the sign indicates the direction, see Figure~\ref{fig:spinning}(b). If this number is zero, then after a suitable isotopy the surface meets the cross section in a (possibly empty or infinite) union of circles, see Figure~\ref{fig:spinning}(c).

The torus $T$ has an induced triangulation consisting of normal triangles. Represent $\gamma$ by an oriented path on $T,$ which is disjoint from the 0--skeleton and meets the 1--skeleton transversely. Each edge of a triangle in $T$ is a normal arc. Give the edges of each triangle in $T$ transverse orientations pointing into the triangle and labelled by the quadrilateral types sharing the normal arc with the triangle; see Figure~\ref{fig:quad coods}. We then define $\nu(\gamma)$ as follows. Choosing any starting point on $\gamma,$ we read off a formal linear combination of quadrilateral types $q$ by taking $+q$ each time the corresponding edge is crossed with the transverse orientation, and $-q$ each time it is crossed against the transverse orientation (where each edge in $T$ is counted twice---using the two adjacent triangles).

\begin{figure}[h]
    \centering
    \includegraphics[scale=1.1]{quad_torus}
    \caption{Coming up and dropping down}
    \label{fig:quad coods}
\end{figure}

Evaluating $\nu(\gamma)$ at some $x\in \mathbb{R}^{\square}$ gives a real number $\nu_{x}(\gamma).$ For example, taking a small loop around a vertex in $T$ and setting this equal to zero gives the $Q$--matching equation of the corresponding edge in $M;$ see Figure~\ref{fig:spinning}(a). For each $x\in Q(\mathcal{T}),$ the resulting map $\nu_{x}\colon\thinspace H_1(T ; \mathbb{R}) \to \mathbb{R}$ is a well-defined homomorphism, which has the property that the surface in Theorem~\ref{thm:admissible integer solution gives normal} is closed if and only if $\nu_x = 0$ (see \cite{tillmann08-finite}, Proposition~3.3). Since $\nu_{x}\colon\thinspace H_1(T; \mathbb{R}) \to \mathbb{R}$ is a homomorphism, it is trivial if and only if we have $\nu_{x}(\alpha) = 0 = \nu_{x}(\beta)$ for any basis $\{\alpha, \beta\}$ of $H_1(T; \mathbb{R}).$

\begin{figure}[h]
  \begin{center}
    \subfigure[$0=\nu_x(\gamma) = \sum_{i=1}^{k} (-1)^i x(q_i)$ is the $Q$--matching equation]{
      \includegraphics[scale=1]{Q_paths}}
    \qquad
    \subfigure[spun $\Longleftrightarrow$ $\nu_x\neq 0$]{
      \includegraphics[scale=0.9]{spun}}
    \subfigure[not spun $\Longleftrightarrow$ $\nu_x= 0$]{
      \includegraphics[scale=0.9]{notspun}}
  \end{center}
  \caption{Boundary map determines $Q$--matching equations and spinning}
  \label{fig:spinning}
\end{figure}

We define $Q_0(\mathcal{T}) = Q(\mathcal{T}) \cap \{ x \mid \nu_x=0\},$ and call a two-sided, connected normal surface $F$ with $x(F)$ on an extremal ray of $Q_0(\mathcal{T})$ a \emph{$Q_0$--vertex surface.} The following result is based on the seminal work of  Jaco and Oertel~\cite{jaco84-haken}:

\begin{theorem}\label{thm:some extremal is closed essential}
Suppose $M$ is the complement of a non-trivial knot in $S^3.$ If $M$ contains a closed essential surface $S,$ then there is a normal, closed essential surface $F$ with the property that $x(F)$ lies on an extremal ray of $Q_0(\mathcal{T}).$ Moreover, if $\chi(S)<0,$ then there is such $F$ with $\chi(F)<0.$
\end{theorem}

\begin{proof}[Sketch of proof] A complete proof of a more
general statement is given in Appendix~\ref{app:Jaco-Oertel}. The key ideas are as follows. Given a closed essential surface in $M,$
a standard argument shows that there is a \emph{normal} closed
essential surface in $M.$ Amongst all normal surfaces isotopic (but
not necessarily normally isotopic) to this, choose one that has
minimal number of intersections with the 1--skeleton (this is the PL
analogue of a minimal surface).  Denote this surface $S$.

If $S$ is not a vertex surface,
one can write it using a so-called \emph{Haken sum} of vertex surfaces,
which is a geometric realisation of the sum of $Q$--coordinate
vectors. However, a complication arises, since only a multiple of $S$ is
a Haken sum of vertex surfaces, and only up to
vertex linking tori; that is,
$nS + \Sigma = \sum n_iV_i = V + W,$ where $V$ is a
vertex surface, $\Sigma$ is vertex linking,
and all other terms are combined into the surface $W.$
Building on Jaco and Oertel~\cite{jaco84-haken},
Kang~\cite[Theorem~5.4]{kang05-spun} shows that $V$ and $W$ are
incompressible. Since Euler characteristic is additive under Haken sum,
the result follows if $\chi(S)<0.$ If $\chi(S)=0,$ additional work
is required to show that an essential torus cannot be written as a Haken
sum of boundary parallel tori.
\end{proof}

\section{Algorithms}
\label{sec:Detecting compressing discs}

Here we describe the new algorithm to test whether a knot is large or small
(i.e., whether its complement contains a closed essential surface).
In this extended abstract we restrict our attention to the common setting
of knots in the 3-sphere $S^3$.
See the full version of this paper
for an extension to the more general setting of links in arbitrary
closed orientable 3-manifolds, as well as searching for essential
surfaces in arbitrary closed orientable 3-manifolds (without knots or links).

We present the algorithm in two stages below.
Algorithm~\ref{alg-incompressible} describes a subroutine to test
whether a given closed surface is incompressible.
Algorithm~\ref{alg-large} is the main algorithm: it uses the results
of Section~\ref{sec:closed} to identify candidate essential surfaces, and
runs Algorithm~\ref{alg-incompressible} over each.

These algorithms contain a number of high-level and often intricate
procedures, many of which are described in separate papers.
For each algorithm, we discuss these procedures in further detail after
presenting the overall algorithm structure.

\begin{algorithm}[Testing for incompressibility]
\label{alg-incompressible}
Let $\mathcal{T}$ be an ideal triangulation of a non-compact 3-manifold $M$
that is the complement of a non-trivial knot in $S^3.$
Let $S$ be a closed two-sided normal surface of genus $g \geq 1$
within $\mathcal{T}$.  To test whether $S$ is incompressible in $M$:
\begin{enumerate}
    \item
    \label{en-alg-truncate}
    Truncate the ideal vertex of $\mathcal{T}$ to obtain a compact manifold
    with boundary, cut $\mathcal{T}$ open along the surface $S$, and retriangulate.
    The result is a pair of triangulations $\mathcal{T}_1,\mathcal{T}_2$ representing
    two compact manifolds with boundary $M_1,M_2$ (one on each side of
    $S$ in $M$).

    Let $B_1,B_2$ be the genus $g$ boundary components of $\mathcal{T}_1$ and
    $\mathcal{T}_2$ respectively that correspond to the surface $S$.
    Without loss of generality, suppose that the truncated
    ideal vertex was on the side of $M_2$; therefore $\mathcal{T}_2$ has an
    additional boundary torus, which we denote $B_v$.

    \item
    For each $i=1,2$:
    \begin{enumerate}
        \item \label{en-alg-simplify}
        Simplify $\mathcal{T}_i$ into a triangulation with no internal
        vertices and only one vertex on each boundary component,
        without increasing the number of tetrahedra.
        Let the resulting number of tetrahedra in $\mathcal{T}_i$ be $n$.

        \item \label{en-alg-search}
        Search for a connected normal surface $E$ in $\mathcal{T}_i$
        that is not a vertex link, has positive Euler
        characteristic, and (for the case $i=2$) does not
        meet the torus boundary $B_v$.

        \item \label{en-alg-nodisc}
        If no such $E$ exists, then there is no compressing disc
        for $S$ in $M_i$.  If $i=1$ then try $i=2$ instead, and if $i=2$
        then terminate with the result that $S$ is incompressible.

        \item \label{en-alg-crush}
        Otherwise, crush the surface $E$
        as explained in Section~\ref{subsec:Crushing}
        to obtain a new triangulation $\mathcal{T}'_i$ (possibly disconnected,
        or possibly empty) with strictly fewer than
        $n$ tetrahedra.  If some component of $\mathcal{T}'_i$ has the same
        genus boundary (or boundaries) as $\mathcal{T}_i$ then it
        represents the same manifold $M_i$, and we return to
        step~\ref{en-alg-simplify} using this component of $\mathcal{T}'_i$ instead.
        Otherwise we terminate with the result that $S$ is not incompressible.
    \end{enumerate}
\end{enumerate}
\end{algorithm}

\noindent
Regarding the individual steps of this algorithm:
\begin{itemize}
    \item Step~\ref{en-alg-truncate} requires us to truncate an ideal
    vertex and cut a triangulation open along a normal surface.
    These are standard (though intricate) procedures.
    To truncate a vertex we subdivide tetrahedra and then remove the
    immediate neighbourhood of the vertex.
    To cut along a normal surface, see \cite{burton12-ws} for a
    description of a manageable implementation.

    \item Step~\ref{en-alg-simplify} requires us to simplify
    a triangulation to use the fewest possible vertices, without
    increasing the number of tetrahedra.
    For this we begin with the rich polynomial-time simplification
    heuristics described in \cite{burton12-regina}.  In practice, for all
    $2979$ knots that we consider in Section~\ref{s-results},
    this is sufficient to reduce the triangulation
    to the desired number of vertices.

    If there are still extraneous vertices, we can remove these using
    the crushing techniques of Jaco and Rubinstein
    \cite[Section~5.2]{jaco03-0-efficiency}.  This might
    fail, but only if  $\partial M_i$ has  a compressing disc,
    or two boundary components of $M_i$ are separated by a sphere;
    both cases immediately certify that the surface $S$
    is compressible, and we can terminate immediately.

    \item Step~\ref{en-alg-search} requires us to locate a connected
    normal surface $E$ in $\mathcal{T}_i$ that is not a vertex link, has
    positive Euler characteristic, and does not meet the torus
    boundary $B_v$.
    For this we use the recent method of
    \cite[Algorithm~11]{burton12-unknot}, which draws on
    combinatorial optimisation techniques:
    in essence we run a sequence of linear programs over a combinatorial
    search tree, and prune this tree using tailored branch-and-bound
    methods.  See \cite{burton12-unknot} for details.

    We note that this search is the bottleneck of
    Algorithm~\ref{alg-incompressible}:
    the search is worst-case exponential time, though in practice it
    often runs much faster \cite{burton12-unknot}.
    The exposition in \cite{burton12-unknot} works in the setting where
    the underlying triangulation is a knot complement, but the
    methods work equally well in our setting here.
    To avoid the boundary component $B_v$, we simply remove all normal
    discs that touch $B_v$ from our coordinate system.

    %

\end{itemize}

\begin{theorem} \label{thm-incompressible}
    Algorithm~\ref{alg-incompressible} terminates, and its output is correct.
\end{theorem}

\begin{proof}
    The algorithm terminates because each time we loop
    back to step~\ref{en-alg-simplify} we have fewer tetrahedra
    than before.  Correctness is more interesting: there are many claims
    in the algorithm statement that require proof.
    Full proofs are given in Appendix~\ref{app-incompressible};
    the key ideas are as follows.
    \begin{itemize}
        \item In step~\ref{en-alg-truncate} we claim that cutting along
        $S$ yields two (disconnected) compact manifolds.
        This follows from the fact that
        every closed surface embedded in the 3-sphere is separating.

        \item In step~\ref{en-alg-nodisc} we claim that, if the surface
        $E$ cannot be found in $\mathcal{T}_1$ \emph{and} it cannot be found in
        $\mathcal{T}_2$, then the original surface $S$ must be incompressible.
        This is because otherwise, by results of Jaco and Oertel
        \cite{jaco84-haken},
        there must be a \emph{normal} compressing disc on one side of $S$.

        \item In step~\ref{en-alg-crush} we make several claims.
        First, the new triangulation $\mathcal{T}'_i$ has strictly fewer tetrahedra
        because $E$ is not a vertex link.
        Second, we claim that if $\mathcal{T}'_i$ has a component with the
        same genus boundary (or boundaries) as $\mathcal{T}_i$ then it represents
        the same manifold $M_i$, and otherwise $S$ is compressible;
        this is because the ``destructive'' side-effects of
        the crushing process reduce the boundary genus by cutting
        along compressing discs for $S$.
    \end{itemize}
    There are additional complications involving irreducibility;
    again see Appendix~\ref{app-incompressible} for details.
\end{proof}

\begin{algorithm}[Testing whether a knot is large or small] \label{alg-large}
    Let $K$ be a non-trivial knot in $S^3$.
    To test whether $K$ is large or small:
    \begin{enumerate}
        \item \label{en-test-ideal}
        Build an ideal triangulation $\mathcal{T}$ of the complement of $K$ in $S^3$.

        \item \label{en-test-enumerate}
        Enumerate all extremal rays of $Q_0(\mathcal{T})$;
        denote these $\mathbf{e}_1,\ldots,\mathbf{e}_k$.
        For each extreme ray $\mathbf{e}_i$,
        let $S_i$ be the unique connected two-sided normal
        surface for which $x(S_i)$ lies on $\mathbf{e}_i$.
        Ignore all surfaces $S_i$ that are spheres.

        \item \label{en-test-essential}
        For each remaining surface $S_i$,
        use algorithm~\ref{alg-incompressible} to test whether $S_i$
        is incompressible in $\mathcal{T}$.
        If any $S_i$ is incompressible and is not a torus, then terminate
        with the result that $K$ is large.
        If no $S_i$ is incompressible, then terminate with the result that
        $K$ is small.

        \item \label{en-test-special}

        Otherwise the only incompressible surfaces in our list
        are tori.  For each incompressible torus $S_i$, test whether
        $S_i$ is boundary parallel by (i)~cutting $\mathcal{T}$ open along $S_i$,
        and then (ii)~using the Jaco-Tollefson algorithm
        \cite[Algorithm~9.7]{jaco95-algorithms-decomposition}
        to test whether one of the resulting components is the product
        space $(\textrm{Torus}) \times [0,1]$.  If all incompressible tori are
        found to be boundary parallel then $K$ is small,
        and otherwise $K$ is large.
    \end{enumerate}
\end{algorithm}

\noindent
Regarding the individual steps:
\begin{itemize}
    \item Step~\ref{en-test-ideal} requires us to triangulate the
    complement of $K$.  Hass et~al.\ \cite{hass99-knotnp}
    show how to build a compact triangulation
    (with boundary triangles).  To make this an ideal
    triangulation we cone over the boundary, and retriangulate
    to remove internal (non-ideal) vertices.

    \item Step~\ref{en-test-enumerate} requires us to enumerate all
    extremal rays of $Q_0(\mathcal{T})$.  This is an expensive procedure
    (which is unavoidable, since there is a worst-case exponential
    number of extremal rays).
    For this we use the recent state-of-the-art tree traversal method
    \cite{burton10-tree}, which is tailored to the constraints and
    pathologies of normal surface theory and is found to be highly
    effective for larger problems.
    The tree traversal method works in the
    larger cone $Q(\mathcal{T})$, but it is a simple matter to insert the
    two additional linear equations corresponding to $\nu_x=0$.

    We also note that it is simple to identify the unique
    closed two-sided normal surface for which $Q(S)$ lies on the
    extremal ray $\mathbf{e}$.  Specifically, $Q(S)$ is either
    the smallest integer vector on $\mathbf{e}$ or, if that vector
    yields a one-sided surface, then its double.

    \item If we do not reach a conclusive result in
    step~\ref{en-test-essential}, then step~\ref{en-test-special} requires
    us to run the Jaco-Tollefson algorithm to test whether any
    incompressible torus is boundary-parallel.
    This algorithm is expensive: it requires us to work in a larger
    normal coordinate system, solve difficult enumeration
    problems, and perform intricate geometric operations.

    However, it is rare that we should reach this situation, and indeed
    for all $2979$ knots that we consider in Section~\ref{s-results},
    this scenario never occurs.  For some knots (e.g., satellite
    knots) it cannot be avoided, but there are additional fast methods
    for avoiding the Jaco-Tollefson algorithm even in these settings,
    which we describe in the full version of this paper.
\end{itemize}

\begin{theorem} \label{thm-large}
    Algorithm~\ref{alg-large} terminates, and its output is correct.
\end{theorem}

\begin{proof}
    It is clear that the algorithm terminates (there is no
    looping), and the correctness follows immediately from
    Theorems~\ref{thm:some extremal is closed essential} and
    \ref{thm-incompressible}.
    For details see Appendix~\ref{app-large}.
\end{proof}

\section{Introduction}

In the study of 3--manifolds, essential surfaces have been of central
importance since Haken's seminal work in the 1960s.
An essential surface may be regarded as `topologically minimal', and there has since been extensive research  into 3-manifolds, called \emph{Haken 3-manifolds}, that contain an essential surface. The existence of such a surface has
profound consequences for both the topology and geometry of a 3--manifold
\cite{haken68-overview, jaco79-jsj-book,
johannson79-book, johannson79-mapping,
thurston86-deformation, waldhausen68-large}.

Given any closed 3-manifold,
specified by a triangulation, it is a theorem of Jaco and Oertel
\cite{jaco84-haken} from 1984 that one may algorithmically test for the
existence of a closed essential surface. However, their algorithm
has significant intricacies and is of double-exponential complexity in terms of the input size,
putting it well beyond the scope of a practical implementation.

In this paper we present for the first time a practical algorithm that
can systematically test a significant class of 3-manifolds
for the existence of a closed essential surface, and which is both
efficient in practice and always conclusive.
To illustrate its power, we run this algorithm over a comprehensive
body of input data, yielding computer proofs of new mathematical
results.

The 3-manifolds we examine in this
paper are the motivating spaces for 3-manifold theory: knot complements.
These are the spaces that arise by removing a knotted curve from
3-dimensional space, although our methods can be extended to apply
to a far wider class of 3-manifolds. See the full version of this paper
for  generalisations.  In this paper we work with two collections
of input data.  First, for
each of the 2977 non-trivial prime knots that can be drawn with a diagram of at most 12
crossings, we determine whether its complement contains a closed essential
surface. If there is no such surface, the knot is called \emph{small},
otherwise we call it \emph{large}.  Second, we apply our algorithm to
resolve, in the affirmative, a question of Michel Boileau
\cite{boileau12-dodec} who enquired whether two special 20-crossing knots called
\emph{dodecahedral knots} contain a closed essential surface in their
complements. This question was recently also independently resolved by Jessica
Banks \cite{banks12-dodec} using non-computational techniques.

The algorithm presented here is theoretically significant because it is
the first algorithm in the literature for testing largeness of arbitrary
knots.  However, more important is its practical significance: this is the
first conclusive algorithm of this type that is implemented and fast enough
for real-world use.  The prior state-of-the-art algorithm for detecting
essential surfaces was used to prove that the Weber-Seifert
dodecahedral space is Haken \cite{burton12-ws}; however, although it resolved a
long-standing open problem, this prior algorithm relies on heuristic
methods that only work for certain triangulations, and are only
conclusive if no essential surface exists.  In contrast, the algorithm
described here can work with arbitrary triangulations of knot
complements, and is found to be effective regardless of the final result.

Our methods can be applied to related invariants of knots and 3-manifolds.
For instance,
the smallest genus $g$ of a closed essential surface is an important
knot invariant about which little is known for the case $g \geq 2$,
and our algorithm opens the door to formulating and testing new hypotheses.
These methods may also be extended to test a wide variety of
3-manifolds for Haken-ness and related properties.
More broadly, iterated
exponential complexity algorithms arise frequently in 3-manifold theory,
and our methods give an outline for how such problems, like the
recognition problem for knots and 3-manifolds, may one day be within the
realm of a practical implementation.

We base our work on the framework of the Jaco-Oertel algorithm for
testing for closed incompressible surfaces.  This uses
\emph{normal surfaces}, which allow us to translate topological
questions about surfaces into the setting of integer and linear programming.
The framework consists of two stages: the first constructs a finite list of
candidate essential surfaces, and the second tests each surface in the
list to see if it is essential. A key difficulty with this framework,
which our algorithm also inherits,
is that both stages have running times that are
worst-case exponential in their respective input sizes, and
combining them in any obvious way leads to a double-exponential
complexity solution.

Despite this significant hurdle, we introduce several innovations that cut
down the running time enormously for both stages. Our optimisation for the
first stage involves a combination of established techniques that, though well
understood individually, require new ideas and theory in order to
work harmoniously together.
For the second stage we combine branch-and-bound techniques from
integer programming with the Jaco-Rubinstein procedure for crushing
surfaces within triangulations.
In more detail:

\begin{itemize}
\item
For the {first stage} (enumerating candidate essential surfaces),
we combine several techniques.
First, we wish to create a triangulation for
each knot complement that contains as few tetrahedra as possible. If one
uses classical triangulations one needs as many as $50$ tetrahedra for
some knots in the 12-crossing tables, a size for which enumerating candidate
surfaces is thoroughly infeasible even for modern high-performance machines.
We therefore use \emph{ideal triangulations} for knot
complements, which are decompositions of these spaces into tetrahedra
with their vertices removed. These introduce some significant
theoretical difficulties, but they are much smaller with roughly half as
many tetrahedra.

Second, we use a variant of normal surface theory based on
\emph{quadrilateral coordinates}.
The appeal is that this brings the dimension of the underlying integer
and linear programming problems down from $7t$ in the classical setting
to $3t$, where $t$ is the number tetrahedra in the input 3-manifold.
These coordinates were known to Thurston and Jaco
in the 1980s, and first appeared in print in work of
Tollefson~\cite{tollefson98-quadspace}.

A theoretical difficulty arises when combining ideal triangulations with
quadrilateral coordinates: this introduces objects called
\emph{spun-normal surfaces}, which are properly embedded non-compact surfaces
(essentially built from infinitely many pieces).  We counter this
by introducing extra linear constraints called \emph{boundary equations}
which, with the development of appropriate theory, restrict the solution space
in question to closed surfaces only.  In particular,
using an extension of the work of Jaco and Oertel~\cite{jaco84-haken} from
compact manifolds to non-compact manifolds by Kang~\cite{kang05-spun},
we show in Theorem~\ref{thm:some extremal is closed essential}
that for each manifold under consideration, there is
a finite, constructible set of normal surfaces with the property that if
the manifold in question contains a closed essential surface, then one
must exist in this set.

\item
For the {second stage} (testing whether a candidate surface is essential),
the Jaco-Oertel approach cuts along each candidate surface and
inspects the boundary of the resulting 3-manifold to see if it admits a
\emph{compression disc} (such a disc certifies that a surface is non-essential).
The key difficulty is that one requires a new triangulation for the cut-open
3-manifold: since the candidate surface may be very complicated,
any natural scheme for cutting and re-triangulating yields a new triangulation
with exponentially many tetrahedra in the worst case, taking us far
beyond the realm in which normal surface theory has traditionally been
feasible in practice.
Since these new triangulations are the input for stage two,
which is itself exponential time, we now see where the double
exponential arises, and why the Jaco-Oertel framework has long been
considered far from practical.

We resolve this significant problem using a blend of techniques.
First, we use strong simplification heuristics to reduce the number of
tetrahedra.  Next, we replace the traditional (and very expensive)
enumeration-based search for compression discs with an
\emph{optimisation} process that maximises Euler characteristic.
This uses the branch-and-bound techniques of \cite{burton12-unknot},
and allows us to quickly focus on a single
candidate compression disc.  We employ the crushing techniques
of Jaco and Rubinstein \cite{jaco03-0-efficiency} to quickly test
whether this is indeed a compression disc, and (crucially) to reduce the
size of the triangulation if it is not.

More generally, this issue of iterated-exponential complexity, coming from
cutting and re-triangulating, arises with ubiquity when considering objects
called \emph{normal hierarchies}.  These hierarchies are key when solving
more difficult problems such as the recognition problem for knots and
3-manifolds. Our approach to stage two is both fast in practice and
theoretically correct, making it a substantial breakthrough that
indicates that a practical implementation of these more difficult
algorithms might indeed be possible.
\end{itemize}

\section{Preliminaries}

\subsection{Knots, surfaces and triangulations}

A 3-manifold is a mathematical object that locally looks like
3-dimensional Euclidean space. Because every topological 3-manifold admits
precisely one piecewise-linear structure (up to PL-homeo\-morph\-ism)
\cite{moise52-triang},
in practice this means that 3-manifolds may be studied via
triangulations. A \emph{triangulation} of a compact 3-manifold $M$ is a
description of $M$ as the disjoint union of a finite collection of
3-simplices with their faces identified in pairs, as shown in
Figure~\ref{glueth}.

\begin{figure}[h!]
\centering
\includegraphics[scale=1]{gluetog}
\caption{A 3-manifold may be specified by a triangulation.} \label{glueth}
\end{figure}

A triangulation $\mathcal{T}$ for a 3-manifold $M$ gives rise to
\emph{vertices}, \emph{edges}, \emph{faces} and \emph{tetrahedra} in
$M$. Edges whose
interior lies in the interior of $M$ are called \emph{interior
edges}, and edges that lie entirely on the boundary of $M$ are called
\emph{boundary edges}. In practice, a tetrahedron in $M$ might not be
embedded; for instance, we even allow two faces of a tetrahedron to be
identified in $M.$ For a precise description of our set-up, please see
\S\ref{subsec:Triangulations}; and for an example, see Appendix~\ref{app:fig8}.

Such a triangulation can only specify a compact
3-manifold. If instead of identifying the faces of tetrahedra, we
identify the faces of a finite collection of tetrahedra minus their
vertices, this constitutes an \emph{ideal triangulation} for the
resulting non-compact quotient space.

The 3--manifolds we study in this paper are \emph{knot complements}.
These are 3-manifolds obtained by removing a \emph{knot}, which is
knotted closed curve in $\mathbb{R}^3$, from 3--dimensional Euclidean space. In
practice it is convenient to compactify $\mathbb{R}^3$ with a point at infinity,
yielding a compact 3-manifold called the \emph{3-sphere}, denoted $S^3.$
One then removes the knot from $S^3$ instead. For a knot $K$
we call the resulting non-compact 3-manifold $S^3 \backslash K$ the
\emph{complement of $K$}.
Knot complements always have ideal triangulations
\cite[Proposition~1.2]{tillmann08-finite}.

If instead we remove from $S^3$ a small
open neighborhood of a knot $K$
we obtain a compact 3-manifold called the
\emph{exterior of $K$}. Since they are compact, knot exteriors may be
specified by triangulations. There are well established techniques for
translating between an ideal triangulation for a knot complement and a
triangulation for the corresponding knot exterior.

A knot $K$ is called \emph{non-trivial} if it is not the boundary of an
embedded disc in $S^3.$

In this paper we are interested in \emph{closed essential surfaces} in knot
complements. We define these now. Let $K$ be a knot, and let $M$ be the
complement of $K$. A connected two-sided closed surface with
positive genus $S$, embedded in $M$, is a \emph{closed essential surface
in $M$} if  the following properties hold: (i)~the surface $S$ is
\emph{incompressible} (as defined below); and (ii)~the surface $S$ is not
\emph{boundary parallel}, that is, not ambient isotopic to a small tube
running around $K.$

The definition of incompressible is as follows. A \emph{compression
disc} for an embedded surface $S$ in a 3-manifold $M$ is an embedded
disc $D\subset M$ for which (i)~$D \cap S$ equals the boundary of $D$
(denoted $\partial D$); and (ii)~$\partial D$ is a non-trivial curve in $S$ (meaning $\partial D$ does not bound a disc in $S$). If the surface $S$ admits
a compression disc, then we say $S$ is \emph{compressible},
otherwise $S$ is \emph{incompressible}.  An equivalent, algebraic
criterion can be found in \S\ref{subsec:essential}.

\subsection{Quadrilateral coordinates and $Q$--matching equations}

We use normal surface theory to search for essential
surfaces. A \emph{normal surface} in a (possibly ideal) triangulation
$\mathcal{T}$ is a properly embedded surface which intersects each
tetrahedron of $\mathcal{T}$ in a disjoint collection of
\emph{triangles} and \emph{quadrilaterals}, as shown in Figure
\ref{normaldiscs}. These triangles and quadrilaterals are called
\emph{normal discs}. In an ideal triangulation of a non-compact
3--manifold, a normal surface may contain infinitely many triangles;
such a surface is called \emph{spun-normal}.

\begin{figure}[h!]
\centering
\includegraphics[scale=0.7]{normaldiscs}
\caption{The seven types of normal disc in a tetrahedron.}
\label{normaldiscs}
\end{figure}

We now describe an algebraic approach to normal surfaces.
The key observation is that each normal surface contains
finitely many quadrilateral discs, and is uniquely determined
(up to normal isotopy) by these quadrilateral discs. Here a \emph{normal
isotopy} of $M$ is an isotopy that keeps all simplices of all dimensions
fixed. Let $\square$ denote the set of all normal isotopy classes,
or \emph{types}, of normal quadrilateral discs,
so that $|\square| = 3t$ where $t$ is the number of tetrahedra in $\mathcal{T}$.
We identify $\mathbb{R}^\square$ with $\mathbb{R}^{3t}.$
Given a normal surface $S,$ let $x(S) \in \mathbb{R}^\square = \mathbb{R}^{3t}$
denote the integer vector for which each coordinate $x(S)(q)$
counts the number of quadrilateral discs in $S$ of type $q \in \square$.
This \emph{normal $Q$--coordinate} $x(S)$ satisfies the
following two algebraic conditions.

First, $x(S)$ is admissible.
A vector $x \in \mathbb{R}^\square$ is \emph{admissible} if
$x \ge 0$, and for each tetrahedron $x$ is non-zero
on at most one of its three quadrilateral types.
This reflects the fact that an embedded surface cannot contain
two different types of quadrilateral in the same tetrahedron.

Second, $x(S)$ satisfies a linear equation for each interior
edge in $M,$ termed a \emph{$Q$--matching equation}.
Intuitively, these equations arise from the fact that as one
circumnavigates the earth, one crosses the equator from north to south
as often as one crosses it from south to north.
We now give the precise form of these equations.
To simplify the discussion,
we assume that $M$ is oriented and all tetrahedra are given
the induced orientation; see \cite[Section~2.9]{tillmann08-finite} for
details.

\begin{figure}[h]
    \centering
    \subfigure[The abstract neighbourhood $B(e)$]{%
        \label{fig:matchingquadbdry}%
        \includegraphics[scale=1]{matchingquadbdry}}
    \qquad
    \subfigure[Positive slope]{%
        \label{fig:matchingquadpos}%
        \includegraphics[scale=1]{matchingquadpos}}
    \qquad
    \subfigure[Negative slope]{%
        \label{fig:matchingquadneg}%
        \includegraphics[scale=1]{matchingquadneg}}
    \caption{Slopes of quadrilaterals}
    \label{fig:slopes}
\end{figure}

Consider the collection $\mathcal{C}$ of all (ideal) tetrahedra meeting
at an edge $e$ in $M$ (including $k$ copies of tetrahedron $\sigma$ if $e$ occurs
$k$ times as an edge in $\sigma$).  We form the \emph{abstract
neighbourhood $B(e)$} of $e$ by pairwise identifying faces of tetrahedra
in $\mathcal{C}$ such that there is a well defined quotient map from
$B(e)$ to the neighbourhood of $e$ in $M$; see
Figure~\ref{fig:matchingquadbdry} for an illustration.  Then  $B(e)$ is a ball
(possibly with finitely many points missing on its boundary).  We think
of the (ideal) endpoints of $e$ as the poles of its boundary sphere, and
the remaining points as positioned on the equator.

Let $\sigma$ be a
tetrahedron in $\mathcal{C}$. The boundary square of a normal
quadrilateral of type $q$ in $\sigma$ meets the equator of $\partial
B(e)$ if and only it has a vertex on $e$. In this case, it has a slope
of a well--defined sign on $\partial B(e)$ which is independent of the
orientation of $e$. Refer to Figures~\ref{fig:matchingquadpos} and
\ref{fig:matchingquadneg}, which show quadrilaterals with
\emph{positive} and \emph{negative slopes} respectively.

Given a quadrilateral type $q$ and an edge $e,$ there is a
\emph{total weight} $\wt_e(q)$ of $q$ at $e,$ which records the sum of
all slopes of $q$ at $e$ (we sum because $q$ might meet $e$ more than
once, if $e$ appears as multiple edges of the same tetrahedron).
If $q$ has no corner on $e,$ then we set
$\wt_e(q)=0.$ Given edge $e$ in $M,$ the $Q$--matching equation of $e$
is then defined by $0 = \sum_{q\in \square}\; \wt_e(q)\;x(q)$.

\begin{theorem}\label{thm:admissible integer solution gives normal}
For each $x\in \mathbb{R}^\square$ with the properties that $x$ has integral coordinates, $x$ is admissible and
$x$ satisfies the $Q$--matching equations, there is a (possibly
non-compact) normal surface $S$ such that $x = x(S).$ Moreover, $S$ is
unique up to normal isotopy and adding or removing vertex linking surfaces, i.e.
normal surfaces consisting entirely of normal triangles.
\end{theorem}

For a proof of Theorem \ref{thm:admissible integer solution gives normal} see Theorem 2.1 of \cite{kang05-spun} or Theorem 2.4 of
\cite{tillmann08-finite}.

The set of all $x\in \mathbb{R}^{\square}$ with the property that
(i)~$x\ge 0$ and (ii)~$x$ satisfies the $Q$--matching equations is denoted
$Q(\mathcal{T}).$ This
naturally is a polyhedral cone.
Note however that the set of all admissible $x\in \mathbb{R}^{\square}$
typically meets $Q(\mathcal{T})$ in a non-convex set.

\subsection{Crushing triangulations}
\label{subsec:Crushing}

The crushing process of Jaco and Rubinstein
\cite{jaco03-0-efficiency} plays an important role in our
algorithms, and we informally outline this process here.
For the formal details we refer the reader to
\cite{jaco03-0-efficiency}.

Let $S$ be a two-sided normal surface in a triangulation $\mathcal{T}$ of a compact
orientable 3-manifold $M$.  To \emph{crush} $S$ in $\mathcal{T}$, we
(i)~cut $\mathcal{T}$ open along $S$, which splits each tetrahedron
into a number of (typically non-tetrahedral) pieces;
(ii)~crush each resulting copy of $S$ on the boundary to a point,
which converts these pieces into tetrahedra, footballs and/or pillows
as shown in Figure~\ref{fig:jrpieces};
(iii)~flatten each football or pillow to an edge or triangle
respectively, as shown in Figure~\ref{fig:jrflatten}.

\begin{figure}[ht]
    \centering
    \subfigure[Pieces after crushing $S$ to a point]{%
        \label{fig:jrpieces}%
        \includegraphics[scale=0.5]{jrpieces}}
    \\
    \subfigure[Flattening footballs and pillows]{%
        \label{fig:jrflatten}%
        \includegraphics[scale=0.833]{jr3football}\quad
        \includegraphics[scale=0.833]{jr4football}\quad
        \includegraphics[scale=0.833]{jrpurse}}
    \caption{Steps in the Jaco-Rubinstein crushing process}
    \label{fig-jrcrush}
\end{figure}

The result is a new collection of tetrahedra with a new set of face
identifications.  We emphasise that we \emph{only} keep track of face
identifications between tetrahedra:
any ``pinched'' edges or vertices fall apart, and any
lower-dimensional components with no tetrahedra at all simply disappear.
The resulting structure might not represent a 3-manifold
triangulation, and even if it does the flattening operations might have
changed the underlying 3-manifold in ways that we did not intend.

Although crushing can cause a myriad of problems in general,
Jaco and Rubinstein show that in some cases the operation behaves
extremely well \cite{jaco03-0-efficiency}.  In particular, if
$S$ is a normal sphere or disc, then after crushing we always obtain a
triangulation of some 3-manifold $M'$ (possibly disconnected, and
possibly empty) that is obtained from the original
$M$ by zero or more of the following operations:
\begin{itemize}
\item cutting manifolds open along spheres and filling the resulting boundary spheres with
3-balls;
\item cutting manifolds open along properly embedded discs;
\item capping boundary spheres of manifolds with 3-balls;
\item deleting entire connected components that are any of the 3-ball, the
3-sphere,
projective space $\mathbb{R} P^3,$ the lens space $L(3,1)$ or the product space $S^2 \times S^1.$
\end{itemize}

An important observation is that the number of tetrahedra that remain
after crushing
is precisely the number of tetrahedra that do not contain quadrilaterals of $S$.

\section{Computational results} \label{s-results}

Here we describe the results of running the algorithms of
Section~\ref{sec:Detecting compressing discs} over
significant collections of input knots.
These computational results emphasise that the new largeness testing
algorithm is both feasible to implement, and fast enough to be practical
for non-trivial inputs---both features that distinguish it from many of
its peers in algorithmic low-dimensional topology.

The algorithms were implemented in
C\nolinebreak\hspace{-.05em}\raisebox{.4ex}{\tiny\bf +}%
 \nolinebreak\hspace{-.10em}\raisebox{.4ex}{\tiny\bf +}
using the software package {\emph{Regina}} \cite{burton04-regina,regina}.
The code is available from
\url{http://www.maths.uq.edu.au/~bab/code/}, and works with the
forthcoming {\emph{Regina}} version~4.94.
Supporting data for the computations described here, including
triangulations of the knot complements and the corresponding
lists of admissible extreme rays of $Q_0(\mathcal{T})$,
can be downloaded from this same location.

All running times reported here are measured on a single
2.93~GHz Intel Core~i7 CPU.

\subsection{The census of knots up to 12 crossings}

Our first data set is the census of all $2977$ non-trivial prime knots
that can be represented with $\leq 12$ crossings.
Ideal triangulations of the knot complements were extracted from
the {\emph{SnapPy}} census tables \cite{snappy}, and then further
simplified where possible using {\emph{Regina}}'s greedy heuristics
\cite{burton12-regina} to yield a final set of input triangulations
ranging from 2--26 tetrahedra in size.

The algorithms ran successfully over all $2977$ triangulations,
yielding the following results:

\begin{theorem}
    Of the $2977$ distinct non-trivial prime knots with up to $12$ crossings,
    $1019$ are large and $1958$ are small.
\end{theorem}

A full list of all $1019$ large knots
can be found in Appendix~\ref{app-knots}.
Regarding performance:
\begin{itemize}
    \item
    The enumeration of extremal rays of $Q_0(\mathcal{T})$ was extremely fast,
    with a maximum time of $47$~seconds, and a median time of just
    $0.08$~seconds.  This is a clear illustration of the benefits we
    obtain from Theorem~\ref{thm:some extremal is closed essential},
    which allows us to work in the restricted cone $Q_0(\mathcal{T})$ instead
    of the (typically much larger) cone $Q(\mathcal{T})$.

    The number of extremal rays of $Q_0(\mathcal{T})$ ranged from
    $0$ (for the figure~eight knot complement) up to $509$
    (for one of the 26-tetrahedron triangulations), with a median of $33$.

    \item
    Testing whether each candidate surface was essential was also
    extremely fast in most (but not all) cases.
    For each knot complement, we can sum the times required to process
    all candidate surfaces: the median time over all $2977$ knots was
    $\sim3.6$ seconds, and all but three of the knots had a processing time
    of under $12$~minutes.

    The remaining three knots, however, were significantly slower to
    process.  One required $\sim 3.9$~hours, one required $\sim 12.2$~hours,
    and one (the knot $12\mathrm{a}_{0779}$) was still running after $6$~days.
    However, in a striking illustration of how the algorithms depend
    strongly upon the underlying triangulations, when the code was
    run with a different random seed (which affected the simplification
    heuristics, and hence the triangulations obtained after slicing along
    surfaces), this worst-case knot $12\mathrm{a}_{0779}$ was fully processed
    in under $4$~minutes.
\end{itemize}

\subsection{The dodecahedral knots}

We now turn our attention to the dodecahedral knots
$D_f$ and $D_s$ as described by Aitchison and Rubinstein
\cite{aitchison92-cubings}.  These two knots exhibit remarkable
properties \cite{aitchison97-geodesic,neumann92-arithmetic},
and each can be represented with 20 crossings \cite{aitchison97-geodesic}.
Running our algorithms over them yields the following results:

\begin{theorem}
    The two dodecahedral knots $D_f$ and $D_s$ are both large.
    In particular, their complements contain
    closed essential surfaces of genus $3$.
\end{theorem}

We work with ideal triangulations of the knots $D_f$ and $D_s$ with
$46$ and $47$ tetrahedra respectively, which were kindly provided by Craig Hodgson.
These are significantly larger
than the knots from the 12-crossing census; indeed, triangulations of
this size are typically considered well outside the range of feasibility
for normal normal surface theory.  Happily our algorithms now prove otherwise:
\begin{itemize}
    \item This time the enumeration of extremal rays of $Q_0(\mathcal{T})$
    was the bottleneck: for $D_f$ and $D_s$ this enumeration took
    roughly $2.8$ and $2.4$ days respectively.
    The number of admissible extremal rays was $72272$ and $73609$
    respectively.

    \item To test whether candidate surfaces were essential,
    the knot $D_s$ was completely processed in under $3$~minutes;
    in contrast, $D_f$ required roughly $4.4$~hours.
    Once again, we see that this part of the algorithm depends heavily
    upon the underlying triangulation: when running with a different random
    seed, $D_f$ was likewise processed in just a few minutes.
\end{itemize}

redpajama_set_name: RedPajamaArXiv


text:
Municipio de Macon puede referirse a alguno de los siguientes lugares en Estados Unidos:

 Municipio de Macon (condado de Bureau, Illinois), un municipio ubicado en el condado de Bureau.
 Municipio de Macon (condado de Harvey, Kansas), un municipio ubicado en el condado de Harvey.
 Municipio de Macon (condado de Lenawee, Míchigan), un municipio ubicado en el condado de Lenawee.
 Municipio de Macon (condado de Franklin, Nebraska), un municipio ubicado en el condado de Franklin.

redpajama_set_name: RedPajamaWikipedia


text:
HUGO RIFKIND
We should try to care about Assange's fate
The Wikileaks founder is unlikeable for many reasons but that doesn't excuse this American assault on free speech
Monday February 24 2020, 5.00pm, The Times
There are problems with Julian Assange and high among them is the matter of his friends. A bunch of them gathered in London this weekend to protest about the hearing, which began yesterday, into whether the Wikileaks founder should be extradited to the United States.
Without wishing to cast aspersions on those public figures present — Roger Waters, Vivienne Westwood, Yanis Varoufakis and so on — the vibe was very much that of a Facebook group that Jeremy Corbyn eventually has to petulantly apologise for being a part of. According to John McDonnell, Assange's woes represent "the Dreyfus case of our age". The great Labour statesman Richard Burgon has weighed in too, despite probably thinking that The Dreyfus Affair was about a shark. All in,

redpajama_set_name: RedPajamaCommonCrawl


text:
'A great way to start a ketogenic diet': Italian restaurant offers healthy banana loaf
By JOE HENRYThe Italian restaurant The Spicy Bar has made headlines around the world after its customers were given a banana bread that contained a high concentration of healthy carbs, including fiber.
"You can't put something on the market that's so healthy it's good for you, but that's what The Spicys banana bread is," owner Maria del Ponte said.
The restaurant's owner says that while the bread was "healthy and tasty", it's not the type of healthy bread that people are craving.
"It's not for the faint of heart, it's for those who want to get into the ketogenic keto diet," she said.
"We made it with a low carb, moderate protein diet and we're a little bit stricter on the carbs than many other places, but we're not limiting anything, we're only restricting a small amount."
Del Ponte says she's never met anyone who's struggled with keto, and the bread is not a keto-specific recipe, but it's a good start for anyone interested in starting a ketotic diet.
The menu at The Spiced Bar has a few healthy options, including a salad made with spinach, a bread in spanias, a loaf with a baked tomato and avocado, and a bread made with rice and peas.
The Italian food chain is hoping that people who have tried other healthy-sounding ketogenic recipes will be able to give it a try.
"People will be surprised at how well this one is going to work," del Ponta said.
"It's a low-carb, moderate-protein diet and it's just a very tasty bread."
The Spicy Bakery in Melbourne has been serving healthy banana-breads for years.
Owner Mark Smith says the banana breads are popular with his customers.
"If you have a craving for something that's going to be healthy for you and you want to go down a different path, this is a great way of starting that journey," Smith said.
Smith said his customers love the banana-like consistency of the bread, and have enjoyed it so much that they are giving it a second chance.
"This one has been out for a while now, it has become the staple in our family," he said.
Topics:food-and-beverage,health,healthy-foods,globe-and/orlando,melbourne-3000,vic,australiaMore stories from Victoria
Next: Bread without yeast: How to make healthy banana bread without the yeast
Next: This yeast bread is perfect for a gluten-free diet!
How to Make A Real Life Superhero in the Style of David Tennant
Why this recipe is worth the effort
How to make a pumpkin bread and wonder bread recipe: How to bake pumpkin bread with Wonder Bread recipe
What you need to know about the world's first gluten-free burger