We thank C. Gordon, W. Metzler, E. Pervova, C. Petronio, and S. Zentner for helpful discussions.
The final version of the paper has been written by the second author during his stay at MPIM Bonn. He thanks the institute for hospitality and financial support.
2 Moves, roots, and complexity
We introduce several moves on 3manifolds. In this paper all 3manifolds are assumed to be orientable.

1.
$S$
move (compression along a 2sphere). Let
$S$
be a 2sphere in a 3manifold
$M$
. Then we cut
$M$
along
$S$
and fill the two spheres arising in this way with two 3balls.

2.
$D$
move (compression along a disc). Let
$D$
be a proper disc in
$M$
. Then we cut
$M$
along
$D$
.

3.
$A$
move (compression along an annulus). Let
$A$
be an annulus in
$M$
such that its boundary circles lie in different components of
$\partial M$
. Then we cut
$M$
along
$A$
and attach two plates
${D}_{1}^{2}\times I,{D}_{2}^{2}\times I$
by identifying their base annuli
$\partial {D}_{1}^{2}\times I,\partial {D}_{2}^{2}\times I$
with the two copies of
$A$
, which appear under cutting.
Definition 1.
Let
$F$
be a proper surface in a 3manifold
$M$
such that
$F$
is either a sphere, or a disc, or an annulus.
Then
$F$
is called essential, if one of the following holds:

1.
$F$
is a sphere not bounding a ball;

2.
$F$
is a disc such that the circle
$\partial D$
is nontrivial in
$\partial M$
;

3.
$F$
is an incompressible annulus having boundary circles in different components of
$\partial M$
.
If
$F$
is essential, then the corresponding
$F$
move (i.e. the compression of
$M$
along
$F$
) is also called essential.
Remark 1.
Later on under essential surface we will understand either an essential sphere, or an essential disc, or an essential annulus. The condition that the boundary circles of any essential annulus
$A$
must lie in different components of
$\partial M$
guarantees us that
$A$
is boundary incompressible.
2.1 Roots and complexity
Definition 2.
Let
$M$
be a 3manifold. Then a 3manifold
$N$
is called a root of
$M$
, if

1.
$N$
can be obtained from
$M$
by essential compressions along spheres, discs, and annuli.

2.
$N$
admits no further essential compressions.
Theorem 1.
For any compact 3manifold
$M$
the root of
$M$
exists and is unique up to homeomorphism and removing disjoint 3spheres and balls.
We postpone the proof of the theorem to Section 3 . Note that the condition on boundary circles of compression annuli to lie in different components of
$\partial M$
is essential. Below we present an example of a 3manifold
$M$
with two incompressible boundary incompressible annuli
$A,B\subset M$
such that
$\partial M$
is connected and compressions of
$M$
along
$A$
and along
$B$
lead us to two different 3manifolds admitting no further essential compression, i.e. to two different “roots”.
Example. Let
$Q$
be the complement space of the figure eight knot. We assume that the torus
$\partial Q$
is equipped with a coordinate system such that the slope of the meridian is (1,0). Choose two pairs
$(p,q)$
,
$(m,n)$
of coprime integers such that
$\leftq\right,\leftn\right\ge 2$
and
$\leftp\right\ne \leftm\right$
.
Let
$a$
and
$b$
be corresponding curves in
$\partial Q$
. Then the manifolds
${Q}_{p,q}$
and
${Q}_{m,n}$
obtained by Dehn filling of
$Q$
are not homeomorphic. By [Th], they are hyperbolic.
Consider the thick torus
$X={S}^{1}\times {S}^{1}\times I$
and locate its exterior meridian
$\mu ={S}^{1}\times \{*\}\times \left\{1\right\}$
and interior longitude
$\lambda =\{*\}\times {S}^{1}\times \left\{0\right\}$
. Then we attach to
$X$
two copies
${Q}^{\prime},{Q}^{\prime \prime}$
of
$Q$
as follows.
The first copy
${Q}^{\prime}$
is attached to
$X$
by identifying an annular regular neighborhood
$N\left(a\right)$
of
$a$
in
$\partial Q$
with an annular regular neighborhood
$N\left(\mu \right)$
of
$\mu $
in
$\partial X$
. The second copy
${Q}^{\prime \prime}$
is attached by identifying
$N\left(b\right)$
with
$N\left(\lambda \right)$
. Denote by
$M$
the resulting manifold
${Q}^{\prime}\cup X\cup {Q}^{\prime \prime}$
.
Since
$Q$
is hyperbolic,
$M$
contains only two incompressible boundary incompressible annuli
$A$
and
$B$
, where
$A$
is the common image of
$N\left(a\right)$
and
$N\left(\mu \right)$
, and
$B$
is the common image of
$N\left(b\right)$
and
$N\left(\lambda \right)$
. It is easy to see that compression of
$M$
along
$A$
gives us a disjoint union of a punctured
${Q}_{p,q}^{\prime}$
and a punctured
${Q}^{\prime \prime}$
while the compression along
$B$
leaves us with a punctured
${Q}^{\prime}$
and a punctured
${Q}_{m,n}^{\prime \prime}$
. After filling the punctures (by compressions along spheres surrounding them), we get two different manifolds, homeomorphic to
${Q}_{p,q}\cup Q$
and
${Q}_{m,n}\cup Q$
.
Since their connected components (i.e.
${Q}_{p,q},{Q}_{m,n},Q$
) are hyperbolic, they are irreducible, boundary irreducible and contain no essential annuli. Hence
${Q}_{p,q}\cup Q$
and
${Q}_{m,n}\cup Q$
are different roots of
$M$
.
Let
$M$
be a compact 3manifold. Let us apply to it essential
$S$
moves as long as possible. It follows from Kneser finiteness theorem [
3]
that the number of possible moves is bounded by a constant depending on
$M$
only. Denote by
$s\left(M\right)$
the maximum of these numbers taken over all chains of essential
$S$
moves.
The following notion will be the main inductive parameter in our proofs.
Definition 3.
Let
$M$
be a 3manifold. Then the complexity
$\mathbf{c}\left(M\right)$
of
$M$
is the pair
$\left({g}^{\left(2\right)}\right(\partial M),s(M\left)\right)$
, where
${g}^{\left(2\right)}\left(M\right)={\sum}_{i}{g}^{2}\left({F}_{i}\right)$
,
$g\left({F}_{i}\right)$
is the genus of a component
${F}_{i}\subset \partial M$
, and the sum is taken over all components of
$\partial M$
. The pairs are considered in lexicographical order.
The use of complexity as an inductive parameter is justified by the following fact.
Lemma 1.
Each essential
$S,D,A$
move strictly decreases
$\mathbf{c}\left(M\right)$
.

Proof.
If an essential
$D$
move cuts
$\partial M$
along a nonseparating curve
$\ell $
on some component
$F$
of
$\partial M$
, then it strictly decreases
$g\left(F\right)$
and hence
$c\left(M\right)$
. If the move turns
$F$
into two components
${F}^{\prime},{F}^{\prime \prime}$
, then
$g\left(F\right)=g\left({F}^{\prime}\right)+g\left({F}^{\prime \prime}\right)$
and, since
$\ell $
is nontrivial and thus
$g\left({F}^{\prime}\right)$
,
$g\left({F}^{\prime \prime}\right)\ne 0$
, we have
${g}^{2}\left(F\right)>{g}^{2}\left({F}^{\prime}\right)+{g}^{2}\left({F}^{\prime \prime}\right)$
. This implies that
$c\left(M\right)$
is decreased again. The case of the
$A$
move is similar.
As follows from the definition of
$s\left(M\right)$
, each essential
$S$
move strictly decreases
$s\left(M\right)$
. The boundary of
$M$
remains the same, hence so does
${g}^{\left(2\right)}\left(M\right)$
.
Remark 2.
It is easy to show that inessential
$S$
and
$D$
moves preserve the complexity. However, an inessential
$A$
move can increase it, but only at the expense of
$s\left(M\right)$
(
${g}^{\left(2\right)}\left(M\right)$
cannot increase). For example, if an annulus
$A$
cuts off a
${D}^{2}\times I$
from
$M$
, then the corresponding move results in the appearing of an additional component of the type
${S}^{2}\times I$
.
2.2 Equivalence of essential surfaces
Throughout this section, surface means sphere or disc or annulus.
Definition 4.
Let
$M$
be a 3manifold and
$F,G$
be two essential surfaces in
$M$
. Then
$F,G$
are equivalent (we write
$F\sim G$
) if there exists a finite sequence of essential surfaces
${X}_{1},{X}_{2},...,{X}_{n}$
such that the following holds:

1.
$F={X}_{1}$
and
${X}_{n}=G$
;

2.
For each
$i,1\le i<n,$
the surfaces
${X}_{i}$
and
${X}_{i+1}$
are disjoint.
Lemma 2.
Let
$M$
be a 3manifold not homeomorphic to
${S}^{1}\times {S}^{1}\times I$
. Then any two essential surfaces in
$M$
are equivalent.

Proof.
Let
$F,G$
be two essential surfaces in
$M$
in general position.
Then the number of curves (circles and arcs) in the intersection of
$F$
and
$G$
will be denoted by
$\#(F\cap G)$
. Arguing by induction, we may assume that any two essential surfaces
$F,G$
with
$\#(F\cap G)<n$
are equivalent. The base of the induction is evident: if
$\#(F\cap G)=0$
, then
$F\sim G$
by definition. Let
$F,G$
be two essential surfaces such that
$\#(F\cap G)=n$
.
Case 1. Suppose that
$F\cap G$
contains a circle
$s$
which is trivial in
$F$
. By an innermost circle argument we may assume that
$s$
bounds a disc
$D\subset F$
such that
$D\cap G=s$
. Compressing
$G$
along
$D$
, we get a twocomponent surface
${G}^{\prime}$
such that one component is a sphere, the other is homeomorphic to
$G$
, and
$\#(F\cap {G}^{\prime})=n1$
. Since
$G$
is an interior connected sum of the components of
${G}^{\prime}$
, at least one of them (denote it by
$X$
) is essential and thus
$F\sim X$
by the inductive assumption. On the other hand,
$X$
can be shifted away from
$G$
by a small isotopy. It follows that
$X\sim G$
and thus
$F\sim G$
.
Case 2. Suppose that
$F\cap G$
does not contain trivial circles, but contains an arc
$a$
which is trivial in
$F$
. By an outermost arc argument we may assume that
$a$
cuts off a disc
$D\subset F$
from
$F$
such that
$D\cap G=a$
. Compressing
$G$
along
$D$
, we get a twocomponent surfaces
${G}^{\prime}$
such that one component is a proper disc, the other is homeomorphic to
$G$
, and
$\#(F\cap {G}^{\prime})=n1$
. Since
$G$
is an interior boundary connected sum of the components of
${G}^{\prime}$
, at least one of them (denote it by
$X$
) is essential and thus equivalent to
$F$
by the inductive assumption. On the other hand,
$X$
can be shifted away from
$G$
by a small isotopy. It follows that
$G\sim X$
and thus
$F\sim G$
.
Case 3. Suppose that
$F$
and
$G$
are annuli such that
$F\cap G$
consists of circles parallel to the core circles of
$F$
and
$G$
. Then one can find two different components
$A,B$
of
$\partial M$
such that a circle of
$\partial F$
is in
$A$
and a circle of
$\partial G$
is in
$B$
. Denote by
$s$
the first circle of
$F\cap G$
we meet at our radial way along
$F$
from the circle
$\partial F\cap A$
to the other boundary circle of
$F$
. Let
${F}^{\prime}$
be the subannulus of
$F$
bounded by
$\partial F\cap A$
and
$s$
, and
${G}^{\prime}$
the subannulus of
$G$
bounded by
$s$
and
$\partial G\cap B$
. Then the annulus
${F}^{\prime}\cup {G}^{\prime}$
is essential and is isotopic to an annulus
$X$
such that
$\#(X\cap F)<n$
and
$\#(X\cap G)=0$
, see Fig. 1 (to get a real picture, multiply by
${S}^{1}$
). It follows that
$F\sim G$
.
Case 4. Let
$F$
and
$G$
be annuli such that
$F\cap G$
consists of more than one radial segments, each having endpoints in different components of
$\partial F$
and different components of
$\partial G$
.
Case 4.1. Suppose that there are two neighboring segments
${s}_{1},{s}_{2}\subset F\cap G\subset F$
such that
$G$
crosses
$F$
at
${s}_{1},{s}_{2}$
in opposite directions. Denote by
$D$
the quadrilateral part of
$F$
between them.
Then we cut
$G$
along
${s}_{1},{s}_{2}$
and attach to it two parallel copies of
$D$
lying on different sides of
$F$
. We get a new surface
${G}^{\prime}$
consisting of two disjoint annuli, at least one of which (denote it by
$X$
) is essential, see Fig. 2 to the left. Since
$\#(X\cap F)=n2$
and, after a small isotopy of
$X$
,
$\#(X\cap G)=\varnothing $
, we get
$F\sim X\sim G$
.
Case 4.2. Suppose that at all segments
$G$
crosses
$F$
in the same direction (say, from the left to the right). Let
${s}_{1},{s}_{2}$
be two neighboring segments spanned by a quadrilateral part
$D\subset F$
between them. Then
${s}_{1},{s}_{2}$
decompose
$G$
into two strips
${L}_{1},{L}_{2}$
such that
${L}_{1}$
approaches
${s}_{1}$
from the left side of
$F$
and
${s}_{2}$
from the right side.
Then the annulus
${L}_{1}\cup D$
is isotopic to an annulus
$X$
such that
$\#(X\cap F)\le n1$
and
$\#(X\cap G)=1$
, see Fig. 2 to the right. Since
$X$
crosses
$F$
one or more times in the same direction, it is essential.
Therefore,
$F\sim X\sim G$
.
Case 5. This is the last logical possibility. Suppose that
$F$
and
$G$
are annuli such that
$F\cap G$
consists of one radial segment. Denote by
${G}^{\prime}$
the relative boundary
${\partial}_{rel}\left(N\right)=\text{Cl}(N\cap \text{Int}M)$
of a regular neighborhood
$N$
of
$F\cup G$
in
$M$
. Then
${G}^{\prime}$
is an annulus having boundary circles in different components of
$\partial M$
.
Case 5.1. If
${G}^{\prime}$
is incompressible, then we put
$X={G}^{\prime}$
.
Case 5.2. If
${G}^{\prime}$
admits a compressing disc
$D$
, then the relative boundary of a regular neighborhood
$N$
of
${G}^{\prime}\cup D$
consists of a parallel copy of
${G}^{\prime}$
and two proper discs
${D}_{1},{D}_{2}$
. If at least one of these discs (say,
${D}_{1}$
) is essential, then we put
$X={D}_{1}$
.
Case 5.3. Suppose that discs
${D}_{1},{D}_{2}$
are not essential. Then the circles
$\partial {D}_{1},\partial {D}_{2}$
bound discs
${D}_{1}^{\prime},{D}_{2}^{\prime}$
contained in the corresponding components of
$\partial M$
. We claim that at least one of the spheres
${S}_{1}={D}_{1}\cup {D}_{1}^{\prime},{S}_{2}={D}_{2}\cup {D}_{2}^{\prime}$
(denote it by
$X$
) must be essential. Indeed, if both bound balls, then
$M$
is homeomorphic to
${S}^{1}\times {S}^{1}\times I$
, contrary to our assumption.
In all three cases 5.15.3
$X$
is disjoint to
$F$
as well as to
$G$
.
Therefore,
$F\sim X\sim G$
.
3 Proof of the main theorem
Let
$F$
be a sphere, a disc or an annulus in a 3manifold
$M$
. It is convenient to denote by
${C}_{F}\left(M\right)$
the result of the
$F$
move, i.e. the manifold obtained by compressing
$M$
along
$F$
.
Lemma 3.
If
$F$
is a sphere or a disc or an essential annulus, then any root of
${M}_{F}={C}_{F}\left(M\right)$
is a root of
$M$
. If
$F$
is an inessential annulus, then
${M}_{F}$
and
$M$
have at least one common root.

Proof.
It is convenient to decompose the proof into four steps.

(1)
If
$F$
is essential, then any root of
${M}_{F}$
is a root of
$M$
by definition of the root.

(2)
If
$F$
is an inessential sphere, then
${M}_{F}$
is a union of
$M$
and a disjoint 3sphere. Therefore, all roots of
$M$
and
${M}_{F}$
are the same.

(3)
Let
$F$
be an inessential disc. Then its boundary circle bounds a disc
$D\subset \partial M$
. Choose a 2sphere
$S$
inside
$M$
which is parallel to the 2sphere
$F\cup D$
. Then the manifold
${M}_{F}$
is obtained from the manifold
${M}_{S}={C}_{S}\left(M\right)$
by puncturing (cutting off a ball
$V\subset {M}_{S}$
). We claim that any root
$R$
of
${M}_{F}={M}_{S}\backslash \text{Int}V\subset {M}_{S}$
, which can be obtained from
${M}_{F}$
by successive compressions along essential subsurfaces, is a root of
${M}_{S}$
. Indeed, we simply compress
${M}_{S}$
along the same surfaces and get either
$R$
(if one of those subsurfaces is a sphere surrounding
$V$
) or a punctured
$R$
(if the puncture survives all compressions). One more compression along a sphere surrounding the puncture is sufficient to convert the punctured
$R$
to
$R$
(modulo disjoint 3spheres and balls, which are irrelevant). It follows from (1), (2), and (3) that any root of
${M}_{F}$
is a root of
$M$
.

(4)
Let
$F$
be an inessential (i.e. compressible) annulus and
$D$
a compressing disc for
$F$
such that
$D\cap F=\partial D$
is a core circle of
$F$
. Denote by
$N$
a regular neighborhood of
$F\cup D$
in
$M$
.
Then the relative boundary
${\partial}_{rel}N=\text{Cl}(\partial N\cap \text{Int}M)$
consists of a parallel copy of
$F$
and two proper discs
${D}^{\prime},{D}^{\prime \prime}$
. Denote by
$S$
a 2sphere in
${C}_{F}\left(M\right)$
composed from a copy of
$D$
and a core disc of one of the attached plates, see Fig. 3 . Then the manifolds
${C}_{{D}^{\prime \prime}}\left({C}_{{D}^{\prime}}\right(M\left)\right)$
and
${C}_{S}\left({C}_{F}\right(M\left)\right)$
are homeomorphic.
Applying (1) (3), we conclude that any root of the manifold
${C}_{{D}^{\prime \prime}}\left({C}_{{D}^{\prime}}\right(M\left)\right)={C}_{S}\left({C}_{F}\right(M\left)\right)$
is a root of both
$M$
and
${C}_{F}\left(M\right)$
.
Proof of Theorem 1. Existence. Let us apply to
$M$
essential
$S,D,A$
moves in arbitrary order as long as possible. By Lemma 1 , each move strictly decreases the complexity. Since every set of pairs of nonnegative integers has a minimal pair, the process stops and we get a root.
Uniqueness. Assume the converse: suppose that there is a 3manifold having two different roots. Among all such manifolds we choose a manifold
$M$
having minimal complexity. Then there exist two sequences of essential moves producing two different roots.
Denote by
${C}_{F}$
and
${C}_{G}$
the first moves of the sequences, where
$F,G$
are essential surfaces in
$M$
. By Lemma 2 , there are essential surfaces
${X}_{1},{X}_{2},...,{X}_{n}$
such that
$F={X}_{1}$
,
${X}_{n}=G$
, and that the surfaces
${X}_{i}$
and
${X}_{i+1}$
are disjoint for all
$i,1\le i<n$
. We may begin the construction of a root starting with the compression along any of them. Evidently, for at least two neighboring surfaces
${X}_{k},{X}_{k+1}$
the roots thus obtained are different. For convenience, we rename
${X}_{k},{X}_{k+1}$
by
$F,G$
thus getting two disjoint surfaces such that
${C}_{F}\left(M\right)$
and
${C}_{G}\left(M\right)$
have different roots. Then
$F$
is a subsurface of
$M$
and of
${M}_{G}={C}_{G}\left(M\right)$
while
$G$
is a subsurface of
$M$
and of
${C}_{F}\left(M\right)$
.
Denote by
$N$
the manifold, obtained from
$M$
by compressions along both surfaces
$F,G$
. Of course, it coincides with
${C}_{G}\left({C}_{F}\right(M\left)\right)$
and
${C}_{F}\left({C}_{G}\right(M\left)\right)$
.
We claim that the complexity of
$N$
is strictly less than the one of
$M$
. Indeed, if
$F$
is either a sphere or a disc, then
$c\left(N\right)\le c\left({M}_{G}\right)$
(since compression along a sphere or a disc does not increase complexity) while
$c\left({M}_{G}\right)<c\left(M\right)$
by Lemma 1 . Suppose that
$F$
is an annulus. Then
${g}^{\left(2\right)}(\partial N)$
is no greater than
${g}^{\left(2\right)}(\partial {M}_{F})$
, since no compression move increases the genus of the boundary. On the other hand, since
$F$
is essential, then
${g}^{\left(2\right)}(\partial {M}_{F})<{g}^{\left(2\right)}(\partial M)$
, which implies
$c\left(N\right)<c\left(M\right)$
.
Using the inductive assumption, we may conclude that
$N$
has a unique root. The same is true for
${M}_{F}$
and
${M}_{G}$
, since by Lemma 1 their complexities are also smaller than
$c\left(M\right)$
. Now we have:

1.
${M}_{F}$
and
$N$
have the same root (since they have a common root by Lemma 3 ).

2.
${M}_{G}$
and
$N$
have the same root (same reason);

3.
Hence
${M}_{F}$
and
${M}_{G}$
have the same root, which is a contradiction.
4 Other roots
Roots of cobordisms. Recall that a 3cobordism is a triple
$(M,{\partial}_{}M,{\partial}_{+}M)$
, where
$M$
is a compact 3manifold and
${\partial}_{}M$
,
${\partial}_{+}M$
are unions of connected components of
$\partial M$
such that
${\partial}_{}M\cap {\partial}_{+}M=\varnothing $
and
${\partial}_{}M\cup {\partial}_{+}M=\partial M$
. One can define
$S$
and
$D$
moves on cobordisms just in the same way as for manifolds. The
$A$
move on cobordisms differs from the one for manifolds only in that one boundary circle of
$A$
must lie in
${\partial}_{}M$
while the other in
${\partial}_{+}M$
.
Theorem 2.
For any compact 3cobordism
$(M,{\partial}_{}M,{\partial}_{+}M)$
its root exists and is unique up to homeomorphisms of cobordisms and removing disjoint 3spheres and balls.
The proof of this theorem is the same as the proof of Theorem 1 .
$S$
Roots of manifolds. We define an
$S$
root of
$M$
as a manifold which can be obtained from
$M$
by essential
$S$
moves and does not admit any further essential
$S$
moves.
Theorem 3.
For any compact 3manifold
$M$
, its
$S$
root exists and is unique up to homeomorphism and removing disjoint 3spheres.
This theorem is actually equivalent to the theorem on the unique decomposition into a connected sum of prime factors. Indeed, the
$S$
root of
$M$
coincides with the union of the irreducible prime factors of
$M$
.
$(S,D)$
Roots of manifolds. An
$(S,D)$
root of
$M$
is a manifold which can be obtained from
$M$
by essential
$S$
and
$D$
moves and does not admit any further essential
$S$
moves and
$D$
moves.
Theorem 4.
For any compact 3manifold
$M$
its
$(S,D)$
root exists and is unique up to homeomorphism and removing disjoint 3spheres and balls.
For irreducible manifolds this theorem can be deduced from the theorem of F. Bonahon [1] on characteristic compression bodies as well as from [4] , where
$D$
roots of irreducible manifolds had been considered under the name cores.
Our way for proving Theorem
1 works also for
$S$
and
$(S,D)$
roots.
All we need is to forget about discs and annuli in the first case and about annuli in the second. This makes the proof significantly shorter.
References

F. Bonahon, Cobordism of automorphisms of surfaces, Ann. Éc. Norm. Sup. 83 (1983), 237270.

S. Gadgil, On the AndrewsCurtis conjecture and algorithms from topology, arXiv:math.GT/0108116.

H. Kneser, Geschlossene Flächen in dreidimensionalen Mannigfaltigkeiten. Jahresbericht der Deut. Math. Verein, 28:248260, 1929.

S. Matveev Algorithmic topology and classification of 3manifolds, Springer ACMmonographs, V. 9 (2003), 480 pp.