11institutetext:  Jae-Seok Huh 22institutetext: Computational Mathematics
Group, Computer Science and Mathematics Division, Oak Ridge National
Laboratory, Oak Ridge, TN 37831
Tel.: 1-865-574-3133
Fax: 1-865-241-4811
22email<EMAIL_ADDRESS>
# An Accurate and Quadrature-Free Evaluation of Multipole Expansion of
Functions Represented by Multiwavelets

Jae-Seok Huh

(Received: date / Accepted: date)

###### Abstract

We present formulae for accurate numerical conversion between functions
represented by multiwavelets and their multipole/local expansions with respect
to the kernel of the form, $e^{-\lambda r}/r$ (cf. GH02 ). The conversion is
essential for the application of fast multipole methods for functions
represented by multiwavelets. The corresponding separated kernels exhibit
near-singular behaviors at large $\lambda$. Moreover, a multiwavelet basis
function oscillates more wildly as its degree increases. These characteristics
in combination render any brute-force approach based on numerical quadratures
impractical. Our approach utilizes the series expansions of the modified
spherical Bessel functions and the Cartesian expansions of solid harmonics so
that the multipole–multiwavelet conversion matrix can be evaluated like a
special function. The result is a quadrature-free, fast, reliable, and machine
precision accurate scheme to compute the conversion matrix with predictable
sparsity patterns.

###### Keywords:

Multipole expansion Multiwavelet Screened Coulomb Potential

##  1 Introduction

Multiwavelets A90 ; ABGV02  developed originally by Alpert generalize Haar
wavelets with piecewise polynomial scale functions up to any given degree,
hence, enjoy higher order of accuracy in the representation of sufficiently
smooth functions. A detailed discussion on the sparse representation of
differential operators and exponential operators for evolution equations can
be found in ABGV02 . Recent advances in multi-resolution algorithms for
integral operators can be found in various articles including BM04 ; HFYGB04 ;
YFGHB04 ; YFGHB04b , which are based on the dimensional kernel separation via
representation of kernels by weighted sum of Gaussians, thus, applicable to a
variety of kernels in arbitrary dimensions.

In this paper, we focus ourselves on a more traditional, but very popular and
well-studied fast convolution algorithm – the fast multipole method. Our goal
is to establish the connection between multiwavelet representation and the
fast multipole method. The problem can be reduced to finding the multipole
expansion of multiwavelet basis functions.

Following one of the most recent version of the fast multipole algorithm
presented in GH02 , we begin with the kernel,

$G({\bm{x}},{\bm{y}})=\frac{e^{-\lambda\|{\bm{x}}-{\bm{y}}\|}}{\|{\bm{x}}-{\bm{y}}\|}$
(1)

where $\lambda$ is a non-negative real number. This kernel is the fundamental
solution of the linear differential operator,

$\Delta-\lambda^{2},$ (2)

which appears in various applications involving damped Coulomb forces. The
resulting potential is also known as Yukawa potential in nuclear physics. In
the derivation of the scheme, we rely on the multipole expansion formula for
strictly positive $\lambda$. However, it turns out that the first term of the
series representation of multipole expansion (with $\lambda>0$) corresponds to
the case of $\lambda=0$. Hence, readers can assume that our scheme can be
applied to _the_ Laplacian kernel also.

##  2 The Multipole Expansion of Multiwavelet Basis Functions

###  2.1 The Multipole Expansion

Denote by ${\langle{\cdot,\cdot}\rangle}$ the $L^{2}$ inner product of complex
functions on a bounded domain in ${\mathbb{R}}^{3}$. Let $\phi$ be a scalar
_source_ function supported on the domain. The potential generated by $\phi$
(outside of its support) is given by the following multipole series,

$\displaystyle\Phi({\bm{x}})$
$\displaystyle={\langle{G({\bm{x}},{\bm{y}}),\phi({\bm{y}})}\rangle}$ (3)
$\displaystyle=\sum_{p=0}^{\infty}\sum_{q=-p}^{p}M_{p}^{q}\,k_{p}(\lambda\|{\bm{x}}\|)\,Y_{p}^{q}({\widehat{\bm{x}}})$
(4)

where ${\widehat{\bm{x}}}={\bm{x}}/\|{\bm{x}}\|$ is identified to a point on
$S^{2}$. The multipole coefficients $M_{p}^{q}$ are given by

$M_{p}^{q}=8\,\lambda\,{\langle{i_{p}(\lambda\|{\bm{y}}\|)Y_{p}^{q}({\widehat{\bm{y}}}),\phi({\bm{y}})}\rangle}.$
(5)

The functions $i_{p}$ and $k_{p}$ are the modified spherical Bessel and Hankel
functions,

$\displaystyle i_{p}(r)$ $\displaystyle=\sqrt{\frac{\pi}{2r}}\,I_{p+1/2}(r)$
(6) $\displaystyle k_{p}(r)$
$\displaystyle=\sqrt{\frac{\pi}{2r}}\,K_{p+1/2}(r).$ (7)

Since $i_{p}(r)$ and $k_{p}(r)$ exhibit exponential growth and decay
respectively, an algorithm based on the above formula is likely to experience
an overflow/underflow. To avoid the issue, as suggested in GH02 , we replace
$i_{p}$ and $k_{p}$ in the formula by their scaled forms,

$\displaystyle{\widehat{i}^{\lambda_{0}}}_{p}(\lambda\,r)$
$\displaystyle=i(\lambda\,r)/\lambda_{0}^{p}$ (8)
$\displaystyle{\widehat{k}^{\lambda_{0}}}_{p}(\lambda\,r)$
$\displaystyle=k(\lambda\,r)\cdot\lambda_{0}^{p}.$ (9)

Assuming $O(r)=1$ by appropriate geometric scaling, the appropriate choice of
$\lambda_{0}$ is $\lambda$ itself, however, in order to maintain the
generality, we keep clear notational distinction between them.

###### Remark 1

To avoid any confusion, the normalization of spherical harmonics $Y_{p}^{q}$
used in this paper needs to be clearly stated before we begin any formulation.
We utilize exactly the same form presented in GH02 , that is,

$Y_{p}^{q}({\widehat{\bm{y}}})=\sqrt{\frac{2p+1}{4\pi}}\sqrt{\frac{(p-|q|)!}{(p+|q|)!}}\,P_{p}^{|q|}(\cos\theta)\,e^{i\,q\,\phi}.$
(10)

An obvious advantage of using this form is that
$Y_{p}^{-q}=\overline{Y_{p}^{q}}$, hence, in (5), $Y_{p}^{q}$ appears without
minus sign in front of $q$. We can observe, later in this paper, that this
property provides us with a better symmetry/sparsity pattern of the multipole
expansion matrix.

###  2.2 Symmetries

The key equation in the above formula is the multipole expansion (5). For
notational simplicity, in this paper, we omit the constant $8\,\lambda$, which
can be multiplied afterward. We denote the product of
${\widehat{i}^{\lambda_{0}}}_{p}$ and $Y_{p}^{q}$ in (5) by $Q_{p}^{q}$;

$Q_{p}^{q}(\lambda,{\bm{y}})\equiv{\widehat{i}^{\lambda_{0}}}_{p}(\lambda\|{\bm{y}}\|)\,Y_{p}^{q}({\widehat{\bm{y}}})$
(11)

The function $Q_{p}^{q}$ should be replaced with the regular solid harmonics
when $\lambda=0$. In the following section, we can observe that the first term
of the series representation of $Q_{p}^{q}$ is the regular solid harmonics. It
is obvious that

$Q_{p}^{q}(\lambda,\alpha\,{\bm{y}})=Q_{p}^{q}(\alpha\,\lambda,{\bm{y}}).$
(12)

The function $Q_{p}^{q}$ enjoys two useful symmetries: firstly, from the
normalization of $Y_{p}^{q}$ employed in this paper, it follows that

$Q_{p}^{-q}=\overline{Q_{p}^{q}}.$ (13)

Secondly, by change of variables $\phi\rightarrow\pi/2-\phi$ in $Y_{p}^{q}$,
we can obtain

$Q_{p}^{q}(\lambda,y_{2},y_{1},y_{3})=i^{q}\overline{Q_{p}^{q}}(\lambda,y_{1},y_{2},y_{3}).$
(14)

As a result, a multipole expansion matrix presented in this paper possesses
similar symmetries, which we utilize to reduce the number of elements we have
to compute.

###  2.3 Multiwavelet Basis Functions

In this section, we briefly introduce multiwavelet representation of
functions. A detailed discussion on the subject can be found in ABGV02 .
Denote by ${\bm{k}}$ non-negative multi-indices and by $\phi^{\bm{k}}$ multi-
dimensional orthonormal polynomials of degree $k_{i}$ in $i$th dimension. We
further assume that the generating functions $\phi^{\bm{k}}$ are constructed
by the Cartesian product of 1-d orthonormal polynomials on $[-1,1]$,

$\phi^{\bm{k}}({\bm{y}})=\sum_{i=1}^{d}\,\phi^{k_{i}}(y_{i}).$ (15)

The above $\phi^{\bm{k}}$ generate the orthonormal multiwavelet basis
functions at arbitrary level $n=0,1,\ldots$, and translation characterized by
multi-indices ${\bm{l}}=(l_{1},\ldots,\l_{d})$ with $l_{i}=0,\ldots,2^{n}-1$
by formula,

$\phi^{\bm{k}}_{n,{\bm{l}}}({\bm{x}})=\begin{cases}\sqrt{2}^{d(n+1)}\phi^{\bm{k}}(2\,(2^{n}{\bm{x}}-{\bm{l}})-1)&\text{on
$b_{(n,{\bm{l}})}$}\\\ 0&\text{elsewhere}\end{cases}$ (16)

where $b_{(n,{\bm{l}})}=\prod_{i=1}^{d}[2^{-n}l_{i},2^{-n}(l_{i}+1)]$. In this
paper, we take $[0,1]^{d}$ ($=b_{0}$ by definition) as the computational
domain. Beware that we assume that the 1-d generating functions $\phi^{k_{i}}$
are orthogonal polynomials defined on $[-1,1]$ (not on $[0,1]$). This choice
of _unshifted_ orthogonal polynomials as the generating functions is to
simplify the notations in multipole related formulae; we have to evaluate
multipole expansions with respect to the center of each $b_{(n,{\bm{l}})}$.

###### Remark 2

The term _orthogonal polynomials_ can be a source of confusion, which we need
to clarify before we present any related formula. By the term, we mean a
sequence of polynomials $\phi^{k}$ of degree $k$ orthogonal to each other with
respect to an underlying weighting function (as in “orthogonal polynomials and
quadratures”). Since a non-trivial weighting function loses its meaning under
scaling, readers may think $\phi^{k}$ a synonym of (normalized) Legendre
polynomial of degree $k$. This limitation of generating functions to
orthogonal polynomials greatly simplifies the resulting formulae and makes the
conversion matrix more sparse.

###### Remark 3

There can be different choices of polynomial basis which are mutually
orthogonal such as the _interpolating basis_ presented in ABGV02 . Conversion
between them and Legendre-generated basis is not complicated. The advantage
(by symmetry and sparsity) of using orthogonal polynomials exceeds the
additional cost of basis conversion.

###  2.4 The Multipole Expansion of $\phi^{\bm{k}}_{(n,{\bm{l}})}$

For any $p=0,1,\ldots$ and $q=-p,\ldots,p$, define
$E^{(p,q)}_{\bm{k}}(n,\lambda)$ by

$E^{(p,q)}_{\bm{k}}(n,\lambda)={\langle{Q_{p}^{q}(\lambda,{\bm{y}}-{\bm{c}}_{(n,{\bm{l}})}),\phi^{\bm{k}}_{(n,{\bm{l}})}({\bm{y}})}\rangle}_{b_{(n,{\bm{l}})}}$
(17)

where ${\bm{c}}_{(n,{\bm{l}})}$ is the center of $b_{(n,{\bm{l}})}$. The above
equation gives the multipole coefficient $M_{p}^{q}$ (without $8\,\lambda$) of
(5) with respect to the center, ${\bm{c}}_{(n,{\bm{l}})}$. The inner product
can be scaled and translated to the standard domain $[-1,1]^{3}$,

$\displaystyle E^{(p,q)}_{\bm{k}}(n,\lambda)$
$\displaystyle=\frac{1}{\sqrt{2}^{3(n+1)}}\,{\langle{Q_{p}^{q}(\lambda,2^{-(n+1)}{\bm{y}}),\phi^{\bm{k}}({\bm{y}})}\rangle}$
(18)
$\displaystyle=\frac{1}{\sqrt{2}^{3n}}\,E^{(p,q)}_{\bm{k}}(0,\lambda/2^{n})$
(19)

where

$E^{(p,q)}_{\bm{k}}(0,\lambda_{n})=\frac{1}{\sqrt{2}^{3}}\,{\langle{Q_{p}^{q}(\lambda_{n}/2,\cdot),\phi^{\bm{k}}}\rangle}.$
(20)

Thus, we are required to evaluate (20) for arbitrary $\lambda_{n}$ which
depends on $\lambda$ and the level, $n$. Viewing $(p,q)$ as a row multi-index
and ${\bm{k}}$ as a column multi-index, $E^{(p,q)}_{\bm{k}}$ acts as the
conversion (multipole expansion) matrix for multiwavelet represented
functions; let $s^{\bm{k}}_{(n,{\bm{l}})}$ be multiwavelet coefficients for a
fixed $(n,{\bm{l}})$. The multipole expansion centered at
${\bm{c}}_{(n,{\bm{l}})}$ of the function
$\sum_{\bm{k}}s^{\bm{k}}_{(n,l)}\,\phi^{\bm{k}}_{(n,{\bm{l}})}$ is given by
the matrix-vector multiplication,

$\sum_{\bm{k}}E^{(p,q)}_{\bm{k}}(n,\lambda)\,s^{\bm{k}}_{(n,{\bm{l}})}.$

The same matrix can be used for the conversion from a local expansion to its
multiwavelet representation. Consider a local expansion with the coefficients
$L_{p}^{q}$,

$\Phi({\bm{x}})=\sum_{p=0}^{\infty}\sum_{q=-p}^{p}\,L_{p}^{q}\,Q_{p}^{q}(\lambda,{\bm{x}}).$
(21)

The projection of $\Phi$ on to the span of the multiwavelet basis is, from the
orthonormality, given by

$s^{\bm{k}}_{(n,{\bm{l}})}={\langle{\overline{\Phi},\phi^{\bm{k}}_{(n,{\bm{l}})}}\rangle}=\sum_{(p,q)}\,\overline{E^{(p,q)}_{\bm{k}}}(n,\lambda)\,L_{p}^{q},$
(22)

i.e., by the multiplication with the conjugate transpose of
$E^{(p,q)}_{\bm{k}}$.

###  2.5 Symmetries

Recall the symmetries of $Q_{p}^{q}$. The following two conditions are the
immediate consequences of (13) and (14).

$E^{(p,-q)}_{\bm{k}}(n,\lambda)=\overline{E^{(p,q)}_{\bm{k}}}(n,\lambda)$ (23)

and

$E^{(p,q)}_{(k_{2},k_{1},k_{3})}(n,\lambda)=(-i)^{q}\,\overline{E^{(p,q)}_{(k_{1},k_{2},k_{3})}}(n,\lambda).$
(24)

In a later section, we will show that, depending on $(p,q,{\bm{k}})$, (1)
$E^{(p,q)}_{\bm{k}}$ is either real or pure imaginary and (2) has pre-
determined sparsity patterns. Combined with the above symmetries, we recommend
the following storage for the multipole expansion matrices. For each level
$n$, we compute $E^{(p,q)}_{\bm{k}}$ for $q\geq 0$ and $k_{2}>k_{1}$, and
store non-negative $q$ portion of the matrices in two sparse matrices, one for
real and the other for imaginary. Separated storage is simple and advantageous
in the implementation; (i) since each element is either real or imaginary, the
two sparse matrices have disjoint index sets; it does not require any
additional storage or computation cost due to duplicated indices. (ii) For
rows with $q<0$, the multiplication can be omitted; for a complex vector
$s^{\bm{k}}_{(n,{\bm{l}})}$,

$\sum_{{\bm{k}}}E^{(p,-q)}_{{\bm{k}},\Re/\Im}\,s^{\bm{k}}_{(n,{\bm{l}})}=\pm\sum_{{\bm{k}}}E^{(p,q)}_{{\bm{k}},\Re/\Im}\,s^{\bm{k}}_{(n,{\bm{l}})}$

with the negative sign for imaginary matrix.

###  2.6 Numerical Issues

There are three major numerical issues which make the evaluation of
$E^{(p,q)}_{\bm{k}}(n,\lambda)$ non-trivial.

  1. (1)

Non-homogeneity of $\bm{Q_{p}^{q}(\lambda,\cdot)}$: Unlike regular solid
harmonics, $Q_{p}^{q}$ are not homogeneous. Since we cannot extract $\lambda$
out of the integral, we have to build different
$E^{(p,q)}_{\bm{k}}(n,\lambda)$ depending on $\lambda$ and $n$, which rules
out the possibility of utilizing a precomputed table. Since they are not even
polynomials, there is no simple quadrature which produces the exact integral.
Any naive approach using adaptive quadrature becomes impractical for the
following reasons.

  2. (2)

Rapid growth of $\bm{Q_{p}^{q}(\lambda,\cdot)}$: The function
$i_{p}(\lambda\,r)$ grows exponentially. Scaling by using
${\widehat{i}^{\lambda_{0}}}_{p}(\lambda\,r)$ helps preventing overflow.
However, the function still exhibits near singularity for large $\lambda$.

  3. (3)

Oscillating behavior of $\bm{\phi^{\bm{k}}}$: Although they are polynomials,
$\phi^{k}$ have all their zeros on $(-1,1)$. Hence, for large $k$, an adaptive
integrator will encounter with highly oscillating integrands.

From the above characteristics, any adaptive integration requires a large
amount of computation, or simply it fails to converge especially for highly
oscillating cases. Beware that, to build $N$ conversion matrices (up to depth
level $N-1$) for the multipole expansion (up to degree $P$) of functions
represented by multiwavelets (of degree up to $K$), we have to compute
$O(N\times P^{2}\times K^{3})$ elements!

Our approach begins with rewriting the $Q_{p}^{q}$ in a series form. Each term
in the resulting power series involves a regular solid harmonics weighted by
an even power of $\|{\bm{x}}\|$, hence, a homogeneous polynomial in
${\mathbb{R}}^{3}$. The Cartesian expansion of this polynomial can be
explicitly written and its projection on multiwavelet basis can be obtained
exactly without using any numerical quadrature.

##  3 The Series Form

In this section, we present a series representation of the multipole expansion
matrix, $E^{(p,q)}_{\bm{k}}(n,\lambda)$. We begin with the identity,

$I_{\alpha}(r)=\sum_{m=0}^{\infty}\frac{1}{m!\,\Gamma(m+\alpha+1)}\left(\frac{r}{2}\right)^{2m+\alpha}.$
(25)

Utilizing $\Gamma(m+1/2)=\sqrt{\pi}\,(2m)!/(4^{m}\,m!)$, we obtain

${\widehat{i}^{\lambda_{0}}}_{p}(\lambda\,r)=r^{p}\left(\frac{\lambda}{\lambda_{0}}\right)^{p}\sum_{m=0}^{\infty}\frac{1}{m!\,(2m+2p+1)!!}\,\left(\frac{\lambda\,r}{\sqrt{2}}\right)^{2m}.$
(26)

Therefore $Q_{p}^{q}$ can be written in power series given by

$Q_{p}^{q}(\lambda,{\bm{x}})=\left(\frac{\lambda}{\lambda_{0}}\right)^{p}\sum_{m=0}^{\infty}\frac{1}{m!\,(2m+2p+1)!!}\,\left(\frac{\lambda^{2}}{2}\right)^{m}\|{\bm{x}}\|^{2m+p}\,Y_{p}^{q}({\widehat{\bm{x}}}).$
(27)

Define $R_{p,m}^{q}$ by

$R_{p,m}^{q}({\bm{x}})={C_{Y}}(p,q)^{-1}\,\|{\bm{x}}\|^{2m+p}\,Y_{p}^{q}({\widehat{\bm{x}}})$
(28)

where

${C_{Y}}(p,q)=\sqrt{\frac{2p+1}{4\pi}}\,\sqrt{\frac{(p-|q|)!}{(p+|q|)!}},$
(29)

Notice that the function $R_{p,m}^{q}$ is a regular solid harmonics multiplied
by $\|{\bm{x}}\|^{2m}$, hence, a homogeneous polynomial of degree $(2m+p)$.
The factor ${C_{Y}}(p,q)^{-1}$ simplifies the Cartesian expansion of
$R_{p,m}^{q}$, which we introduced in the following section.

From the above series representation, $E^{(p,q)}_{\bm{k}}(0,\lambda_{n})$ is
given by

$\displaystyle E^{(p,q)}_{\bm{k}}(0,\lambda_{n})$
$\displaystyle=\frac{1}{\sqrt{2}^{3}}{\langle{Q_{p}^{q}(\lambda_{n}/2,\cdot),\phi^{\bm{k}}}\rangle}$
$\displaystyle={C_{E}}(\lambda_{n}/\lambda_{0},p,q)\sum_{m=0}^{\infty}A_{m}(p)\,\left(\frac{\lambda_{n}^{2}}{8}\right)^{m}I_{m}(p,q,{\bm{k}})$
(30)

where

${C_{E}}(\lambda_{n}/\lambda_{0},p,q)=\frac{{C_{Y}}(p,q)}{\sqrt{2}^{3}\,(2p+1)!!}\left(\frac{\lambda_{n}}{\lambda_{0}}\right)^{p},$
(31)

$A_{m}(p)=\frac{(2p+1)!!}{m!\,(2m+2p+1)!!},$ (32)
$I_{m}(p,q,{\bm{k}})=\int_{[-1,1]^{3}}\overline{R_{p,m}^{q}}({\bm{x}})\,\phi^{\bm{k}}({\bm{x}})\,d{\bm{x}}.$
(33)

The factor $(2p+1)!!$ in $A_{m}(p)$ is added for the normalization,
$A_{0}(p)=1$.

In (30), $\lambda_{n}$ is now taken out of the integral. We will observe that
the $\lambda$-independent term, $I_{m}(p,q,{\bm{k}})$, can be further reduced
to a finite sum of products of 1-d integrals with two integer parameters,
namely, ${\widehat{I}}_{k}^{l}$. We can construct ${\widehat{I}}_{k}^{l}$
exactly without using any numerical quadrature via the recurrence relation of
orthogonal polynomials. Our strategy is to tabulate ${\widehat{I}}_{k}^{l}$
and use the table to evaluate the series (30) for various $\lambda$, $n$, $p$,
$q$, and ${\bm{k}}$.

###  3.1 Properties of $I_{m}$ and the Convergence Criterion

Most of the properties of $I_{m}$ presented in this section will be explained
in detail in §4. For a more comprehensive presentation, we think it would be
more appropriate to discuss the behavior of (30) prior to the presentation of
detailed formulae for $I_{m}$. Followings are the summary of the relevant
properties:

  1. 1.

$I_{m}(p,q,{\bm{k}})$ is either real or pure imaginary depending only on
${\bm{k}}$.

  2. 2.

$I_{m}(p,q,{\bm{k}})=0$ if $2m<k_{x}+k_{y}+k_{z}-p$.

  3. 3.

Sign of $I_{m}(p,q,{\bm{k}})$ is determined by $q$ only and is independent of
$m$.

  4. 4.

$|I_{m}(p,q,{\bm{k}})|$ is monotonically increasing as $m$ increases.

  5. 5.

$I_{m+1}(p,q,{\bm{k}})/I_{m}(p,q,{\bm{k}})\rightarrow 3$ as
$m\rightarrow\infty$.

###### Remark 4

Property (5) can be supported by the following estimate: Since
$|{C_{Y}}^{-1}\overline{Y_{p}^{q}}|=|P_{p}^{|q|}(\cos\theta)\,e^{i\,q\,\phi}|\leq
1$,

$\displaystyle|I_{m}(p,q,{\bm{k}})|$
$\displaystyle\leq\|\phi^{\bm{k}}\|_{\infty}\,\int_{[-1,1]^{3}}\|{\bm{x}}\|^{2m+p}d{\bm{x}}$
$\displaystyle<4\pi\,\|\phi^{\bm{k}}\|_{\infty}\,\int_{0}^{\sqrt{3}}r^{2m+p+2}dr=\frac{12\pi\,\sqrt{3}^{p}\,3^{m}}{(2m+p+3)}\,\|\phi^{\bm{k}}\|_{\infty}$

Thus, the series consists of two parts: $A_{m}$ decreasing factorially and
$(\lambda^{2}/8)^{m}\,I_{m}$ which behaves asymptotically
$\sim(3\lambda^{2}/8)^{m}$. Their product
$C_{m}=A_{m}(\lambda^{2}/8)^{m}I_{m}$ has a fixed sign for a fixed
$(p,q,{\bm{k}})$ independently of $m$. Hence, the partial sum of the series
increases (decreases) monotonically to the upper (lower) bound which is
potentially huge in the absolute sense. The non-alternating feature of the
series suppresses any necessity of considerations of cancellation errors, and
suggest the following simple convergence criterion: for given absolute and
relative tolerances $\epsilon_{a}$ and $\epsilon_{r}$, stop the summation if

$|C_{M}|<\epsilon_{a}\quad\text{or}\quad|C_{M}|<\epsilon_{r}\,\left|\sum_{m=0}^{M}C_{m}\right|.$
(34)

We can numerically observe that the number of terms to convergence $M$ is
$O(\lambda)$ in a conservative estimation. For example, for
$\epsilon_{r}=10^{-16}$, $M\sim\lambda$ and slightly smaller if $\lambda$ is
large; e.g., when $\lambda\sim 300$, $M\sim 200$. The condition (2) combined
with the convergence criterion provides us with additional sparsity of
$E^{(p,q)}_{\bm{k}}$; if $2M<k_{x}+k_{y}+k_{z}-p$, the corresponding
$E^{(p,q)}_{\bm{k}}$ can be considered to be zero.

###### Remark 5

We represent $E^{(p,q)}_{\bm{k}}$ like a special function of $\lambda$ with
exponential growth. The number of terms $M$ can grow indefinitely as $\lambda$
increases. Although, in many practical applications, $\lambda$ are quite
limited and $\lambda_{n}=\lambda/2^{n}$ decreases as the depth of the
multiwavelet representation increases, a more complete algorithm requires an
asymptotic expansion of $E^{(p,q)}_{\bm{k}}$ with respect to $\lambda$. Yet,
we haven’t found a closed formula for the asymptotic expansion, which is an
on-going work.

##  4 The Formula for $I_{m}$ and the Sparsity Pattern

In this section, we present an explicit Cartesian expansion form of
$\overline{R_{p,m}^{q}}$ in $I_{m}$. Each term can be written as a product of
1-d integrals which can be evaluated exactly by the recurrence relations of
the orthogonal polynomials $\phi^{k}$. We begin with the series form of the
spherical harmonics. With the Rodrigues’ formula, the associated Legendre
functions $P_{p}^{|q|}$ in $Y_{p}^{q}$ can be written as

$\displaystyle P_{p}^{|q|}(z)$
$\displaystyle=\frac{(-1)^{|q|}}{2^{p}\,p!}\,(1-z^{2})^{{|q|}/2}\,\frac{d^{p+{|q|}}}{dz^{p+{|q|}}}\,(z^{2}-1)^{p}$
$\displaystyle=\frac{(-1)^{|q|}}{2^{p}}\,(1-z^{2})^{{|q|}/2}\,\sum_{\nu=0}^{\lfloor\frac{p-{|q|}}{2}\rfloor}\,\frac{(-1)^{\nu}(2p-2\nu)!}{\nu!\,(p-\nu)!\,(p-{|q|}-2\nu)!}\,z^{(p-{|q|}-2\nu)}.$
(35)

Hence, using notations ${\bm{x}}=(x,y,z)$, $r=\|{\bm{x}}\|$, and
$s={\operatorname{sign}}(q)$,

$\overline{R_{p,m}^{q}}({\bm{x}})=r^{2m+p}P_{p}^{|q|}(z/r)\left(\frac{x-s\,i\,y}{\sqrt{r^{2}-z^{2}}}\right)^{|q|}\\\
=\frac{(-1)^{|q|}}{2^{p}}\,(x-s\,i\,y)^{|q|}\sum_{\nu=0}^{\lfloor\frac{p-{|q|}}{2}\rfloor}\frac{(-1)^{\nu}(2p-2\nu)!}{\nu!\,(p-\nu)!\,(p-{|q|}-2\nu)!}\,r^{2(m+\nu)}\,z^{(p-{|q|}-2\nu)}$
(36)

By expanding $(x-s\,i\,y)^{|q|}$ and $r^{2(m+\nu)}$, we obtain

$=(s\,i)^{|q|}\\\
\sum_{\mu=0}^{|q|}(s\,i)^{\mu}a_{\mu}\sum_{\nu=0}^{\lfloor\frac{p-{|q|}}{2}\rfloor}b_{\nu}\sum_{\alpha=0}^{m+\nu}c_{\nu\alpha}\,z^{(p-{|q|}+2m-2\alpha)}\sum_{\beta=0}^{\alpha}d_{\alpha\beta}\,y^{({|q|}+2\beta-\mu)}\,x^{(2\alpha-2\beta+\mu)}$
(37)

where the coefficients are given by

$\displaystyle a_{\mu}$ $\displaystyle=\begin{pmatrix}q\\\ \mu\end{pmatrix}$
(38) $\displaystyle b_{\nu}$
$\displaystyle=\frac{(-1)^{\nu}}{2^{\nu}}\frac{(2p-2\nu-1)!!}{\nu!\,(p-q-2\nu)!}$
(39) $\displaystyle c_{\nu\alpha}$ $\displaystyle=\begin{pmatrix}m+\nu\\\
\alpha\end{pmatrix}$ (40) $\displaystyle d_{\alpha\beta}$
$\displaystyle=\begin{pmatrix}\alpha\\\ \beta\end{pmatrix}$ (41)

where we use the definition, $(-1)!!=0!!=1$.

###  4.1 The Formula

From (37), we obtain our final formula for $I_{m}$:

$I_{m}(p,q,{\bm{k}})=(s\,i)^{|q|}\,I_{m}^{(1)}(p,q,{\bm{k}})+(s\,i)^{{|q|}+1}\,I_{m}^{(2)}(p,q,{\bm{k}})$
(42)

where

$I_{m}^{(1)}(p,q,{\bm{k}})=\sum_{\mu=0}^{\lfloor\frac{{|q|}}{2}\rfloor}(-1)^{\mu}a_{2\mu}\sum_{\nu=0}^{\lfloor\frac{p-{|q|}}{2}\rfloor}b_{\nu}\\\
\cdot\sum_{\alpha=0}^{m+\nu}c_{\nu\alpha}\,{\widehat{I}}_{k_{z}}^{(p-{|q|}+2m-2\alpha)}\sum_{\beta=0}^{\alpha}d_{\alpha\beta}\,{\widehat{I}}_{k_{y}}^{({|q|}+2\beta-2\mu)}\,{\widehat{I}}_{k_{x}}^{(2\alpha-2\beta+2\mu)},$
(43)
$I_{m}^{(2)}(p,q,{\bm{k}})=\sum_{\mu=0}^{\lfloor\frac{{|q|}-1}{2}\rfloor}(-1)^{\mu}a_{2\mu+1}\sum_{\nu=0}^{\lfloor\frac{p-{|q|}}{2}\rfloor}b_{\nu}\\\
\cdot\sum_{\alpha=0}^{m+\nu}c_{\nu\alpha}\,{\widehat{I}}_{k_{z}}^{(p-{|q|}+2m-2\alpha)}\sum_{\beta=0}^{\alpha}d_{\alpha\beta}\,{\widehat{I}}_{k_{y}}^{({|q|}+2\beta-2\mu-1)}\,{\widehat{I}}_{k_{x}}^{(2\alpha-2\beta+2\mu+1)},$
(44)

and

${\widehat{I}}_{k}^{l}=\int_{-1}^{1}\zeta^{l}\phi^{k}(\zeta)d\zeta.$ (45)

Note that $I_{m}^{(1)}$ and $I_{m}^{(2)}$ are real functions and, with factors
$(s\,i)^{|q|}$ and $(s\,i)^{{|q|}+1}$ respectively, they determine real and
imaginary parts of $I_{m}$ separately. The above representation of $I_{m}$ by
two separate parts $I_{m}^{(1)}$ and $I_{m}^{(2)}$ is to signify the following
very useful fact: at least, one of $I_{m}^{(1)}$ and $I_{m}^{(2)}$ vanishes
for any $(p,q,{\bm{k}})$ independently of $m$, which implies that

$E^{(p,q)}_{\bm{k}}$ is either a real or a pure imaginary.

Moreover, depending on the parameter $(p,q,{\bm{k}})$, many of $I_{m}$ vanish,
which results in the nice sparsity of the multipole expansion matrix. These
properties are the immediate consequence of the following properties of
orthogonal polynomials.

#### (1) Oddity

Any orthogonal polynomial $\phi^{k}$ with symmetric domain and weight is even
(odd) if the degree $k$ is even (odd). Hence,

${\widehat{I}}_{k}^{l}=0\quad\text{if $(l+k)$ is odd.}$

Since $m$ always appears in the equation with the factor of 2, any consequence
of the oddity condition is $m$-independent; the resulting sparsity of
$E^{(p,q)}_{\bm{k}}$ is pre-determined by $(p,q,{\bm{k}})$ only (independently
of the level $n$ and $\lambda$). We can observe that

  1. (a)

$I_{m}^{(2)}=0$ if $q=0$.

  2. (b)

$I_{m}^{(1)}=0$ if $k_{x}$ is odd or $({|q|}+k_{y})$ is odd or
$(p+{|q|}+k_{z})$ is odd.

  3. (c)

$I_{m}^{(2)}=0$ if $k_{x}$ is even or $({|q|}+k_{y})$ is even or
$(p+{|q|}+k_{z})$ is odd.

Therefore,

$E^{(p,q)}_{\bm{k}}=0\quad\text{if}\quad\begin{cases}\text{$(k_{z}+p+{|q|})$
is odd}\\\ \text{$(k_{x}+k_{y}+{|q|})$ is odd}\\\ \text{$q=0$ and at least one
of $k_{x}$ and $k_{y}$ is odd}\end{cases}$ (46)

Suppose $E^{(p,q)}_{\bm{k}}\neq 0$ from the above test. Then, the oddity of
$k_{x}$ must be the same as the oddity of $({|q|}+k_{y})$, which results in

$I_{m}=c\cdot\begin{cases}I_{m}^{(2)}&\text{if $k_{x}$ is odd}\\\
I_{m}^{(1)}&\text{if $k_{x}$ is even}\end{cases}\quad
c=\begin{cases}(-1)^{\lfloor\frac{{|q|}}{2}\rfloor}\,{\operatorname{sign}}(q)\,i&\text{if
$k_{y}$ is odd}\\\ (-1)^{\lceil\frac{{|q|}}{2}\rceil}&\text{if $k_{y}$ is
even}\end{cases}$ (47)

Notice, $E^{(p,q)}_{\bm{k}}$ is real (imaginary) if $k_{y}$ is even (odd).

The following table illustrates the sparsity of the multipole expansion matrix
for parameters: $0\leq p\leq 10$, $0\leq q\leq p$, and $0\leq k_{x,y,z}\leq
10$. We can observe that about a quarter of elements are non-zeroes. (See
Table 1.)

total elements | real non-zeroes | imaginary non-zeroes
---|---|---
87846 | 12186 (13.9%) | 8450 (9.6%)
Table 1: $\lambda$-independent sparsity estimated by the oddity condition.

#### (2) Moment condition

Recall the moment conditions satisfied by orthogonal polynomials.

${\widehat{I}}_{k}^{l}=0\quad\text{if $l<k$.}$

Consider a term with a fixed set of indices
$(p,q,{\bm{k}},\mu,\nu,\alpha,\beta)$ in (42). The term vanishes if

$k_{z}>p-{|q|}+2m-2\alpha\quad\text{or}\quad
k_{y}>{|q|}+2\beta-\mu\quad\text{or}\quad k_{x}>2\alpha-2\beta+\mu$

which is true if

$k_{x}+k_{y}+k_{z}>p+2m.$

Thus,

$I_{m}(p,q,{\bm{k}})=0\quad\text{if}\quad 2m<k_{x}+k_{y}+k_{z}-p$ (48)

This condition is $m$-dependent, hence, cannot be used to pre-determine the
sparsity pattern of $E^{(p,q)}_{\bm{k}}$. However, it still can affect the
sparsity for a given $\lambda$; suppose that the convergence criterion (34) is
satisfied at $M$ for $2M<k_{x}+k_{y}+k_{z}-p$. Then, the corresponding
$E^{(p,q)}_{\bm{k}}(n,\lambda)$ is effectively zero. Since $M\sim\lambda$ and
$E^{(p,q)}_{\bm{k}}(n,\lambda)=constant\cdot
E^{(p,q)}_{\bm{k}}(0,\lambda/2^{n})$, the multipole expansion matrix becomes
more sparse as $\lambda$ decreases and as $n$ increases. Table 2 shows the
number of vanishing elements (for $n=0$) among those predicted to be non-
zeroes by the oddity condition. With parameters, $0\leq p\leq 10$, $0\leq
q\leq p$, and $0\leq k_{x,y,z}\leq 10$, the number of elements is 87846 and
the numbers of non-zero real and imaginary elements (predicted by the oddity
condition) are 12186 and 8450 respectively (same as the above example).
Tolerances are $\epsilon_{a}=\epsilon_{r}=10^{-16}$.

$\lambda$ | additional real zeroes | additional imaginary zeroes
---|---|---
1 | 9567 | 6679
2 | 8813 | 6154
4 | 7478 | 5235
6 | 6340 | 4439
8 | 5439 | 3775
10 | 4630 | 3203
50 | 1309 | 851
100 | 1301 | 848
200 | 1273 | 835
300 | 1251 | 824
Table 2: $\lambda$-dependent sparsity estimated from the moment condition.

The additional sparsity decreases as $\lambda$, hence $M$, increases. There
are two factors which controls $M$ and, hence, the the additional sparsity –
the absolute tolerance $\epsilon_{a}$ and the relative tolerance
$\epsilon_{r}$. Among them, the contribution of $\epsilon_{r}$ decreases
rapidly and becomes quite negligible when $\lambda\gg\max\,k_{i}$. However,
the contribution of $\epsilon_{a}$ is persistent. From the table, we can
observe that the additional sparsities by $\epsilon_{a}$ are $\sim 1200$ for
the real matrix and $\sim 800$ for the imaginary matrix.

Also, the moment condition enhances the computational efficiency slightly. We
can simply skip the evaluation of $I_{m}$ if
$m<\lceil(k_{x}+k_{y}+k_{z}-p)/2\rceil$. Like the sparsity by $\epsilon_{r}$,
the effect decreases quite rapidly as $\lambda$ increases. However, in
practical applications of fast multipole and multiwavelet representation, the
levels of terminal boxes where we need to perform the expansion is likely to
be high. Hence, the additional sparsity by $\epsilon_{r}$ should not be
considered insignificant.

###  4.2 The Laplacian Kernel ($\bm{\lambda=0}$)

In this case, $Q_{p}^{q}$ becomes simply the regular solid harmonics. The
corresponding $E^{(p,q)}_{\bm{k}}(n,0)$ is just the first term ($m=0$) of the
series form (30) with an appropriate adjustment of the constant factor. In
this case, the moment condition becomes

$E^{(p,q)}_{\bm{k}}=0\quad\text{if}\quad p<k_{x}+k_{y}+k_{z}$

which results in a more sparse multipole expansion matrices. With the same
condition as the previous examples, $\max p=\max k_{i}=10$, the number of non-
zero elements are given in Table 3.

total elements | real non-zeroes | imaginary non-zeroes
---|---|---
87846 | 1512 (1.72%) | 1001 (1.14%)
Table 3: Sparsity of the case with $\lambda=0$.

We can observe that the resulting matrices are very sparse – only less than 3%
of total elements are non-zeroes. This example illustrates the efficiency of
the multipole expansion on multiwavelet representations based on _orthogonal_
(almost synonymously in this paper, Legendre) polynomials.

###  4.3 Recurrence Relations for ${\widehat{I}}_{k}^{l}$

Finally, we present the algorithm to build the table of
${\widehat{I}}_{k}^{l}$ required for the evaluation of $I_{m}$. Let $p\leq
p_{\max}$, $k_{i}\leq k_{\max}$, and $M\leq M_{\max}$ (for a given $\lambda$).
Then, the required size of table is $(2M_{\max}+p_{\max})\times k_{\max}$, and
the half of the elements are zero by the oddity condition.

Each element ${\widehat{I}}_{k}^{l}$ can be calculated by the identical
recurrence relations to those of the orthogonal polynomials $\phi^{k}$. Recall
any sequence orthogonal polynomials satisfy a three term recurrence relation
of the form,

$\phi^{k+1}=(\alpha_{k}\,\zeta+\beta_{k})\,\phi^{k}-\gamma_{k}\,\phi^{k-1}.$
(49)

It immediately follows that

${\widehat{I}}_{k+1}^{l}=\alpha_{k}\,{\widehat{I}}_{k}^{l+1}+\beta_{k}\,{\widehat{I}}_{k}^{l}-\gamma_{k}\,{\widehat{I}}_{k-1}^{l}.$
(50)

From the oddity condition, ${\widehat{I}}_{k+1}^{l}\neq 0$ if and only if
${\widehat{I}}_{k}^{l}=0$, and ${\widehat{I}}^{l}_{k}=0$ for $l<k$. Hence, for
$k<l$,

${\widehat{I}}_{k}^{l+1}=\begin{cases}0&\text{if $(l+k)$ is even}\\\
\alpha_{k}^{-1}\,{\widehat{I}}_{k+1}^{l}+\alpha_{k}^{-1}\gamma_{k}\,{\widehat{I}}_{k-1}^{l}&\text{if
$(l+k)$ is odd}\end{cases}$ (51)

and

${\widehat{I}}_{k}^{k}=\alpha_{k}^{-1}\,\gamma_{k}\,{\widehat{I}}_{k-1}^{k-1}\quad(\because{\widehat{I}}_{k+1}^{k-1}=0).$
(52)

The recurrence relation can be evaluated from the initial data,

${\widehat{I}}_{0}^{l}=a_{0}\,\frac{1+(-1)^{l}}{l+1}\quad\text{and}\quad{\widehat{I}}_{1}^{l}=a_{1}\,\frac{1-(-1)^{l}}{l+2}$
(53)

where $\phi^{0}=a_{0}$ and $\phi^{1}=a_{1}\zeta$.

For _normalized_ Legendre polynomials, the coefficients are given by

$\alpha_{k}^{-1}=\frac{k+1}{2k+1}\,\sqrt{\frac{2k+1}{2k+3}}\quad\text{and}\quad\alpha_{k}^{-1}\gamma_{k}=\frac{k}{2k+1}\,\sqrt{\frac{2k+1}{2k-1}}.$
(54)

##  5 Results and Conclusions

Most of the implementation is done very faithfully with the formulae presented
in this paper. The only special treatment is that, in order to suppress the
accumulation of round-off errors affecting the result, we used higher
precision floating point arithmetics for internal calculations including the
table for ${\widehat{I}}^{l}_{k}$; for example, to generate matrices with
64bit double precision, we employed 80bit long(extended)-double arithmetics.
The computational cost is governed by the number of terms to be added, $m$,
and is not significantly affected by the augmented internal precision. By
comparing with values obtained by applying adaptive numerical integrator to
(15), we could validate the presented formula. When $\lambda$ or ${\bm{k}}$ is
only moderately large, an adaptive integrator typically fails to converge
since the integrand of (15) becomes near-singular or highly oscillating. Thus,
the presented formula can be viewed as a reliable way to evaluate (15) (or a
similar form of integral) when a typical numerical quadrature is not
applicable due to the near-singularity and/or the oscillation of the
integrand. It is also observed that the computing time of building
${\widehat{I}}_{k}^{l}$ table is negligible compared to the computing time of
$E^{(p,q)}_{\bm{k}}$. We summarize the contributions of this paper as follows.

  1. 1.

We presented a method to build the multipole expansion matrices for functions
represented by multiwavelets.

  2. 2.

The presented method does not involve any numerical quadrature and based
entirely on a series representation like a special function of $\lambda$.

  3. 3.

The proposed scheme generates highly accurate multipole conversion matrices
stably and reliably for a wide range of parameters $(p,q,{\bm{k}})$ and
$\lambda$.

## References

  * (1) B. Alpert, _Sparse Representation of Smooth Linear Operators_ , Ph.D. Thesis, Yale University (1990).
  * (2) B. Alpert, G. Beylkin, D. Gines, and L. Vozovoi, _Adaptive Solution of Partial Differential Equations in Multiwavelet Bases_ , J. Comput. Phys., 182(1), 149-190 (2002).
  * (3) G. Beylkin and M. Mohlenkamp, _Algorithms for Numerical Analysis in High Diemensions_ , SIAM J. Sci. Comput., 26 (6), 2133 2159 (2005).
  * (4) R. Harrison, G. Fann, T. Yanai, Z. Gan, and G. Beylkin, _Multiresolution quantum chemistry: Basic theory and initial applications_ , J. Chem. Phys. 121 (23), 11587 11598 (2004).
  * (5) T. Yanai, G. Fann, Z. Gan, R. Harrison, and G. Beylkin, _Multiresolution quantum chemistry: Hartree Fock exchange_ , J. Chem. Phys. 121 (14), 6680 6688 (2004).
  * (6) T. Yanai, G. Fann, Z. Gan, R. Harrison, and G. Beylkin, _Multiresolution quantum chemistry: Analytic derivatives for Hartree Fock and density functional theory_ , J. Chem. Phys. 121 (7), 2866 2876 (2004).
  * (7) L. Greengard, and J. Huang, _A New Version of the Fast Adaptive Multipole Method for Screened Coulomb Interactions in Three Dimensions_ , Journal of Computational Physics, 180, 642-658 (2002).


# Stable equivalence of handlebody decompositions whose partitions are
multibranched surfaces

Masaki Ogawa

###### Abstract.

In this paper, we consider decompositions of closed orientable 3-manifolds
with more than 3 handlebodies, where the union of intersections of
handlebodies is a multibranched surface. We define stabilization operations
for such decompositions and show the stable equivalence.

##  1\. Introduction

Recently, we introduced a handlebody decomposition of a closed orientable
3-manifold [10, 8]. If a 3-manifold is decomposed into several handlebodies,
then we call this decomposition a handlebody decomposition. In such
decomposition, we call a union of intersection of handlebodies a partition. In
particular, if the partition of handlebody decomposition is simple polyhedron,
we say handlebody decomposition is simple. This is a generalization of a
Heegaard splitting and a trisection of a 3-manifold. It is well known that
Heegaard splittings of the same 3-manifold are stable equivalent [1, 2].
Recently, Koenig showed a stable equivalence of a trisection of a 3-manifold
in [5]. Also, in [8], we showed the stable equivalence of simple handlebody
decompositions. In [8], we consider the case where handlebody decomposition is
simple. To show the stable equivalence of such handlebody decomposition, we
use not only one but some types of stabilizations and moves on a simple
polyhedron. Stabilizations used in [8] are called type 0 and type 1
stabilizations. A type 0 stabilization is similar to a stabilization of a
Heegaard splitting.

A multibranched surface is a 2-dimensional complex such that a point in it
have a regular neighborhood homeomorphic to a disk or branched point where a
branched point is a point whose neighborhood as in Figure 1.

Figure 1. A regular neighborhood of a branched point in a multibranched
surface.

We consider the multibranched surface embedded in a 3-manifold which separates
it into some handlebodies. For a multibranched surface in a 3-manifold,
Ishihara, Koda, Ozawa and Shimokawa introduced IX and XI moves which do not
change the regular neighborhood [9]. See Section 2 for the detail.

If a 3-manifold is decomposed into some handlebodies so that the union of
intersections of handlebodies is a multibranched surface, we call this a
multibranched handlebody decomposition. If a multibranched handlebody
decomposition consists of three handlebodies, this corresponds to a handlebody
decomposition with no vertex in the partition. On the other hand, if the
number of handlebodies is greater than 4, there exists a multibranched
handlebody decomposition which does not correspond to simple handlebody
decomposition. We say two multibranched handlebody decompositions are isotopic
if the union of the intersections of handlebodies is isotopic to each other.
For such decomposition, we show the following theorem.

######  Theorem 1.1.

Two multibranched handlebody decompositions with four handlebodies of the same
3-manifold are isotopic to each other after applying XI and IX moves and type
0, 1 stabilizations finitely many times.

Also, we characterize 3-manifolds which have a certain multibranched
handlebody decomposition. We say that such multibranched handlebody
decomposition has a type-$(g_{1},...,g_{n})$ decomposition if a handlebody
$H_{i}$ of the decomposition has genus $g_{i}$ for $i=1,...,n$. We consider
3-manifolds which have a handlebody decomposition with exactly four
handlebodies with small genera. In this paper, lens space is a 3-manifold with
genus one Heegaard splitting which is not homeomorphic to both the 3-sphere
and $S^{2}\times S^{1}$. Let $\mathbb{B}$ be a connected sum of a finite
number of $S^{2}\times S^{1}$’s, let $\mathbb{L}$ and $\mathbb{L}_{i}$ be lens
spaces, and let $\mathbb{S}(n)$ be a Seifert manifold with at most $n$
exceptional fibers. Then we obtain the following theorem.

######  Theorem 1.2.

Let $M$ be a closed orientable 3-manifold. Then the following holds.

  1. (1)

$M$ has a type-$(0,0,0,0)$ decomposition if and only if $M$ is homeomorphic to
$\mathbb{B}$.

  2. (2)

$M$ has a type-$(0,0,0,1)$ decomposition if and only if $M$ is homeomorphic to
$\mathbb{B}$ or $\mathbb{B}\\#\mathbb{L}$.

  3. (3)

$M$ has a type-$(0,0,1,1)$ decomposition if and only if $M$ is homeomorphic to
$\mathbb{B}$ or $\mathbb{B}\\#\mathbb{L}$ or
$\mathbb{B}\\#\mathbb{L}_{1}\\#\mathbb{L}_{2}$.

  4. (4)

$M$ has a type-$(0,1,1,1)$ decomposition if and only if $M$ is homeomorphic to
$\mathbb{B}$ or $\mathbb{B}\\#\mathbb{L}$ or
$\mathbb{B}\\#\mathbb{L}_{1}\\#\mathbb{L}_{2}$ or
$\mathbb{B}\\#\mathbb{L}_{1}\\#\mathbb{L}_{2}\\#\mathbb{L}_{3}$ or
$\mathbb{B}\\#\mathbb{S}(3)$.

Also we characterize 3-manifolds with type-$(1,1,1,1)$ decomposition.

######  Theorem 1.3.

Let $M$ be a closed orientable 3-manifold. Then $M$ has a type-$(1,1,1,1)$
decomposition if and only if $M$ is homeomorphic to $\mathbb{B}$ or
$\mathbb{B}\\#\mathbb{L}$ or $\mathbb{B}\\#\mathbb{L}_{1}\\#\mathbb{L}_{2}$ or
$\mathbb{B}\\#\mathbb{L}_{1}\\#\mathbb{L}_{2}\\#\mathbb{L}_{3}$ or
$\mathbb{B}\\#\mathbb{L}_{1}\\#\mathbb{L}_{2}\\#\mathbb{L}_{3}\\#\mathbb{L}_{4}$
or $\mathbb{B}\\#\mathbb{S}(4)$.

We call the union of intersections of handlebodies of handlebody decomposition
a partition. If a partition is a simple polyhedron, any closed orientable
3-manifolds has type-$(0,0,0,0)$ decomposition. Hence Theorem 1.2 shows a
difference between multibranched handlebody decomposition and a handlebody
decomposition with simple polyhedron.

This paper is organized as follows. In Section 2, we introduce a multibranched
surface and its moves. In Section 3, we describe the notion of multibranched
handlebody decomposition and its stabilizations. After that, we show
stableequivalence theorem in Section 4. After that, we characterize a
3-manifolds by multibranched handlebody decomposition with four handlebodies
in Section 5.

##  2\. multi-branched surface

Let $\mathbb{R}^{2}_{+}$ be the closed upper half-plane
$\\{(x_{1},x_{2})\in\mathbb{R}^{2}\mid x_{2}\geq 0\\}$. The multibranched
Euclidean plane, denoted by $\mathbb{R}^{2}_{i}$ $(i\geq 1)$, is the quotient
space obtained from $i$ copies of $\mathbb{R}^{2}_{+}$ by identifying with
their boundaries
$\partial\mathbb{R}^{2}_{+}=\\{(x_{1},x_{2})\in\mathbb{R}^{2}\mid x_{2}=0\\}$
via the identity map.

######  Definition 2.1.

A second countable Hausdorff space $X$ is called a multibranched surface if
$X$ contains a disjoint union of simple closed curves $l_{1},\ldots,l_{n}$
satisfying the following:

  1. (1)

For each point $x\in l_{1}\cup\cdots\cup l_{n}$, there exists an open
neighborhood $U$ of $x$ and a positive integer $i$ such that $U$ is
homeomorphic to $\mathbb{R}^{2}_{i}$.

  2. (2)

For each point $x\in X-(l_{1}\cup\cdots\cup l_{n})$, there exists an open
neighborhood $U$ of $x$ such that $U$ is homeomorphic to $\mathbb{R}^{2}$.

We call $l_{i}$ a branched locus. The surfaces divided by branched loci are
called regions.

Sometimes multibranched surface is studied as a 2-stratifolds [4]. A
multibranched surface has been studied recently [6, 7, 4]. Ishihara, Koda,
Ozawa and Shimokawa introduced the moves of multi-branched surface which does
not change its regular neighborhood [9]. We shall review the definition of XI
and IX moves.

Let $X$ be a multibranched surface with brach loci $B=B_{1}\cup\cdots\cup
B_{m}$ and regions $S=S_{1}\cup\cdots\cup S_{n}$, where $S$ is a (possibly
disconnected or/and non-orientable) compact surface without disk components
such that each component $S_{j}$ ($j=1,\ldots,n$) has a non-empty boundary.
Each point $x$ in $\partial S$ is identified with a point $f(x)$ in $B$ by a
covering map $f:\partial S\to B$, where $f|_{f^{-1}(B_{i})}:f^{-1}(B_{i})\to
B_{i}$ is a $d_{i}$-fold covering ($d_{i}>2$). We call $d_{i}$ the degree of
$B_{i}$. We say that $B_{i}$ is tribranched or a tribranch locus if $d_{i}=3$.
If all the branched loci in the multibranched surface are tribranched, we call
it tribranched surface. For each component $C$ of $\partial S$, the wrapping
number of $C$ is $w_{C}$ if $f|_{C}$ is a $w_{C}$-fold covering for the branch
locus $f(C)$. Suppose $X$ is embedded in an orientable $3$-manifold $M$. By
[6], then for each branch locus $B_{i}$ of $X$, the wrapping number of all
components of $f^{-1}(B_{i})$ is a divisor of $d_{i}$. We call the divisor
$w_{i}$ the wrapping number of $B_{i}$. We say a branch locus $B_{i}$ is
normal (resp. pure) if $w_{i}=1$ (resp. $d_{i}=w_{i}$). In this paper, we
assume that all the branched loci in a multibranched surface are normal.

######  Definition 2.2.

Let $A$ be an annulus region of a multibranched surface $X$. Suppose that each
component of $\partial A$ is a tribranched locus. Then we can obtain another
multibranched surface from $X$ by performing deformation retraction of $A$ to
the core circle of $A$ which sends $\partial A$ to a degree 4 branched locus.
We call this operation an IX move along $A$.

Let $l$ be a branched locus of $X$ with degree 4, $S$ a region whose boundary
contains $l$ and $A^{\prime}$ a regular neighborhood of $l$ in $S$. Then, we
can consider the reverse operation of an IX move called XI move along
$A^{\prime}$. See Figure 2.

Figure 2. IX and XI move on a multibranched surface.

######  Theorem 2.1 (Theorem 1 in [9]).

Let $X,X^{\prime}$ be multibranched surfaces in an orientable 3-manifold $M$,
and let $N,N^{\prime}$ be their regular neighborhoods respectively. If $N$ is
isotopic to $N^{\prime}$, then $X$ is transformed into $X^{\prime}$ by a
finite sequence of IX moves and XI moves and isotopies.

##  3\. Handlebody decomposition whose partition is multi-branched surface

Ishihara, Mishina, Koda, Ozawa, Sakata, Shimokawa and author introduced a
handlebody decomposition of a 3-manifold whose partition is a simple
polyhedron and showed the stable equivalent theorem for such decompositions
[8]. To show the stable equivalent theorem of handlebody decompositions, we
use two stabilizations and two moves of a simple polyhedron. In this section,
we introduce the new decomposition of 3-manifolds called a multibranched
handlebody decomposition.

######  Definition 3.1 (Multibranched handlebody decomposition).

Let $M$ be a closed orientable 3-manifold and $H_{i}$ a genus $g_{i}$
handlebody embedded in $M$ for $i=1,...,n$. $M=H_{1}\cup\cdots\cup H_{n}$ is a
type-$(g_{1},g_{2},...,g_{n})$ multibranched handlebody decomposition if the
followings hold;

  1. (1)

$H_{i}\cap H_{j}=\partial H_{i}\cap\partial H_{j}$ is a union of possibly
disconnected compact surfaces and simple closed curves. We denote
$F_{ij}=H_{i}\cap H_{j}$.

  2. (2)

$H_{i1}\cap\cdots\cap H_{ik}$ is a union of simple closed curves in $M$ or
emptyset for $k\geq 3$ and $\\{i_{1},...,i_{k}\\}\subset\\{1,...,n\\}$. We
call this simple closed curve branched locus.

We call the union of $F_{ij}$ for all $i\neq j$ the partition of a
multibranched handlebody decomposition. We say that two multibranched
handlebody decompositions of the same 3-manifold are isotopic to each other if
each partition is isotopic to each other.

######  Remark 3.1.

It is clear that partition of a multibranched handlebody decomposition is a
multibranched surface in $M$. Also, all the branched loci in a partition are
normal since $H_{i}$ does not have self-intersection.

We can obtain a type $(0,0,g,g)$ multibranched handlebody decomposition from a
genus $g$ Heegaard splitting. Hence any closed orientable 3-manifold admits
multibranched handlebody decomposition.

Let $M=H_{1}\cup\cdots\cup H_{n}$ be a multibranched handlebody decomposition
and $P$ a partition of the multibranched handlebody decomposition. Let $m$ be
the maximal of degrees of branched loci. Then we say $M=H_{1}\cup\cdots\cup
H_{n}$ is a degree $m$ multibranched handlebody decomposition. If $n=3$, the
degree is also 3. In this paper, we consider the case where $n=4$.

In [8], we introduced type 0, 1 stabilizations for handlebody decomposition.
We shall review the definition of stabilizations.

######  Definition 3.2 (stabilization).

  1. (1)

The following operation is called a type 0 stabilization (Figure 3). We take
two points on the interior of $F_{ij}$ and connect them by a properly embedded
boundary parallel arc $\alpha$ in $H_{i}$. Let $N(\alpha)$ be the regular
neighborhood of $\alpha$ in $H_{i}$. we define a new handlebody decomposition
$M=H_{1}^{\prime}\cup\cdots\cup H^{\prime}_{i}\cup\cdots\cup
H^{\prime}_{j}\cup\cdots\cup H^{\prime}_{n}$ by
$H^{\prime}_{i}:=H_{i}\setminus int(N(\alpha))$, $H^{\prime}_{j}:=H_{j}\cup
N(\alpha)$ and $H^{\prime}_{k}:=H_{k}$ for $k\neq i,j$. Then the n-tuple
$(g_{1},...,g_{i},...,g_{j},...,g_{n})$ is changed into
$(g_{1},...,g_{i}+1,...,g_{j}+1,...,g_{n})$ and the number of components of
branched loci is not changed by this operation.

  2. (2)

The following operation is called a type 1 stabilization (Figure 4). We take
two points on the branched loci and connect them by an arc $\alpha$ on
$F_{jk}$. Let $N(\alpha)$ be the regular neighborhood of $\alpha$ in $M$. we
define a new handlebody decomposition $M=H_{1}^{\prime}\cup\cdots\cup
H^{\prime}_{i}\cup\cdots\cup H^{\prime}_{j}\cup\cdots\cup H^{\prime}_{n}$
where $H^{\prime}_{i}:=H_{i}\cup N(\alpha)$, $H^{\prime}_{j}:=H_{j}\setminus
int(N(\alpha))$ and $H^{\prime}_{k}:=H_{k}\setminus int(N(\alpha))$
$H_{l}^{\prime}=H_{l}$ for $l\neq i,j,k$. Then the n-tuple
$(g_{1},...,g_{i},...,g_{n})$ is changed into $(g_{1},...,g_{i}+1,...,g_{n})$
and the number of components of branched loci is changed by $1$. Conversely,
if there exists a non-separating disk $D_{i}\subset H_{i}$ whose boundary
intersects the set of branched loci exactly two points transversely, then
$D_{i}$ can be canceled by an inverse operation of a type 1 stabilization. We
call this operation a type 1 destabilization.

Figure 3. A type 0 stabilization along the arc $\alpha$. A n-tuple
$(g_{1},...,g_{i},...,g_{j},...,g_{n})$ is changed into
$(g_{1},...,g_{i}+1,...,g_{j}+1,...,g_{n})$ Figure 4. A type 1 stabilization
along the arc $\alpha$. A n-tuple $(g_{1},...,g_{i},...,g_{n})$ is changed
into $(g_{1},...,g_{i}+1,...,g_{n})$.

##  4\. stable equivalent theorem

In this section, we will prove Theorem 1.1 by using stabilizations described
above and XI, IX moves. First, we consider the following lemma.

######  Lemma 4.1.

Let $X$ be a partition of a multibranched handlebody decomposition and $A$ an
annulus component of $F_{ij}$. Suppose that one of the components of $\partial
A$ is a component of $H_{i}\cap H_{j}\cap H_{l}$ and the other is a component
of $H_{i}\cap H_{j}\cap H_{k}$ for $l\neq k$. Also, suppose that $X$ is a
tribranched surface. Then we can eliminate $A$ from $F_{ij}$ by XI and IX
moves so that the obtained partition $X^{\prime}$ is also a tribranched
surface.

######  Remark 4.1.

After eliminating $A$ in Lemma 4.1, $F_{kl}$ shall have a new annulus
component.

###### Proof of Lemma 4.1.

After performing IX move along $A$, we can eliminate $A$ from $F_{ij}$ and
obtain the branched locus $l$ with degree 4. By the assumption that X is a
tribranched surface, $l=H_{i}\cap H_{j}\cap H_{k}\cap H_{l}$. Then there is a
component of $F_{jl}$ whose boundary contains $l$. Then we can take a regular
neighborhood $A^{\prime}$ of $l$ in the components of $F_{jl}$. An XI moves
along $A^{\prime}$ gives a tribranched surface X’ as in conclusion. See Figure
5.

Figure 5. XI and IX moves which deform $A$ into empty set.

∎

To prove the stable equivalence theorem, we shall define a local 1-handle
attached to a handlebody.

######  Definition 4.1.

Let $M$ be a closed orientable 3-manifold and $H$ a handlebody embedded in
$M$. We say a 1-handle $h$ attached to $\partial H$ is local for $H$ if there
exists a disk in the exterior of $H\cup h$ whose boundary intersects the
boundary of a cocore of $h$ at one point. We call $D$ a dual disk of the pair
$(H,h)$.

Figure 6. A 1-handle $h$ which is local for $H$

We note that two local 1-handles attached to the same handlebody is isotopic
to each other after performing the handleslide on the handlebody.

The proof of Theorem 1.1 is divided into the following steps. Let $M=H_{1}\cup
H_{2}\cup H_{3}\cup H_{4}$ and $M=H_{1}^{\prime}\cup H_{2}^{\prime}\cup
H_{3}^{\prime}\cup H_{4}^{\prime}$ be two multibranched handlebody
decompositions.

  1. Step 1:

We deform each of $F_{12}$, $F_{13}$, $F_{23}$, $F_{12}^{\prime}$,
$F_{13}^{\prime}$ and $F_{23}^{\prime}$ to a disk by performing type 1
stabilizations and XI, IX moves. Then $(H_{1}\cup H_{2}\cup H_{3})\cup H_{4}$
and $(H_{1}^{\prime}\cup H_{2}^{\prime}\cup H_{3}^{\prime})\cup
H_{4}^{\prime}$ become Heegaard splittings. Perform type 0 stabilizations
until two Heegaard splittings $(H_{1}\cup H_{2}\cup H_{3})\cup H_{4}$ and
$(H_{1}^{\prime}\cup H_{2}^{\prime}\cup H_{3}^{\prime})\cup H_{4}^{\prime}$
are isotopic. Then we obtain $H_{4}=H_{4}^{\prime}$.

  2. Step 2:

Perform type 1 stabilizations and IX, XI moves until each of $F_{24}$,
$F_{34}$, $F_{24}^{\prime}$ and $F_{34}^{\prime}$ is a disk. Then each of
$H_{i}$ and $H_{i}^{\prime}$ is a handlebody attached to
$H_{4}=H_{4}^{\prime}$ at a disk for $i=2,3$.

  3. Step 3:

We show that each of 1-handles $h_{i}$ (resp. ${h_{i}}^{\prime}$) of $H_{i}$
(resp. $H_{i}^{\prime}$) is a local 1-handle attached to
$H_{4}\cup(H_{i}-h_{i})$ (resp.
$H_{4}^{\prime}\cup(H_{i}^{\prime}-h_{i}^{\prime})$) for $i=2,3$ so that dual
disks of 1-handles are disjoint. Also we show that a 1-handle $h$ (resp.
$h^{\prime}$) whose cocore is $F_{23}$ (resp. $F_{23}^{\prime}$) is a local
1-handle attached to $\partial(H_{2}\cup H_{3}\cup H_{4})$ (resp.
$\partial(H_{2}\cup H_{3}\cup H_{4}^{\prime})$) so that a dual disk of $h$
(resp. $h^{\prime}$) is a disjoint from dual disks of 1-handles of $H_{i}$
(resp. $H_{i}^{\prime}$) for $i=2,3$. This implies that $H_{i}=H_{i}^{\prime}$
after performing handleslides for $i=2,3$.

  4. Step 4:

In oder to perform handleslides $H_{2}$ on $H_{4}$, perform type 1
stabilization and XI, IX moves until $F_{14}$ is an annulus. After that, we
perform type 0 stabilization until the genus of $H_{2}$ equals to that of
$H_{2}^{\prime}$. Then $H_{2}=H_{2}^{\prime}$ after performing handleslides.

  5. Step 5:

In oder to perform handleslides $H_{3}$ on $H_{2}$, perform type 1
stabilizations and XI, IX moves until $F_{12}$ is a disk and $F_{14}$ is an
empty set. After that, we perform type 0 stabilization until the genus of
$H_{3}$ equals to that of $H_{3}^{\prime}$.Then $H_{3}=H_{3}^{\prime}$ after
performing handleslides.

###### Proof of Theorem 1.1.

Let $H_{1}\cup H_{2}\cup H_{3}\cup H_{4}$ and $H_{1}^{\prime}\cup
H_{2}^{\prime}\cup H_{3}^{\prime}\cup H_{4}^{\prime}$ be multibranched
handlebody decompositions of the same 3-manifold $M$. Let $F_{ij}=H_{i}\cap
H_{j}$ and $F_{ij}^{\prime}=H_{i}^{\prime}\cap H_{j}^{\prime}$. After
performing XI moves to each degree 4 branches, we can assume that all branched
loci are tribranched. For each $\partial H_{i}$, we suppose $\partial
H_{i}=F_{ij}\cup F_{ik}$ for $k\neq j$. Then we can assume that
$H_{1}=F_{12}\cup F_{13}$. Since all the branched loci are tribranched,
$\partial H_{2}=F_{12}\cup F_{23}$ and $\partial H_{3}=F_{13}\cup F_{23}$.
This is a contradiction. Hence we can assume that $F_{1i}\neq\emptyset$ for
$i=2,3,4$ without loss of generality as necessary after renaming indices.

Step1: We show the following claim to achieve step 1.

######  Claim 4.1.

We can assume $H_{1}\cup H_{2}\cup H_{3}$ is a handlebody after applying some
XI and IX moves and type 1 stabilizations i.e. $(H_{1}\cup H_{2}\cup
H_{3})\cup H_{4}$ is a Heegaard splitting.

###### Proof.

We shall consider about $F_{12}$. Each component of $\partial F_{12}$ is a
component of $\partial F_{13}$ or $\partial F_{14}$ also. Let $S_{12}$ be a
component of $F_{12}$. Suppose that $\partial S_{12}\cap\partial
F_{13}\neq\emptyset$ and $\partial S_{12}\cap\partial F_{14}\neq\emptyset$.
Let $C$ be a component of $\partial S_{12}\cap\partial F_{13}$. Then we can
take arcs properly embedded in $S_{12}$ which cuts open $S_{12}$ into a planar
surface and their endpoints are in $C$. After performing type 1 stabilizations
along such arcs, we can assume $S_{12}$ is a planar surface. Then we can take
arcs properly embedded in $S_{12}$ which connects the components of $\partial
S_{12}\cap\partial F_{13}$ (resp. $\partial S_{12}\cap\partial F_{14}$) and
cut open $S_{12}$ into an annulus. After performing type 1 stabilizations
along such arcs, we can assume $S_{12}$ is an annulus. Now one of the
components of $\partial S_{12}$ is a component of $\partial F_{13}$ and the
other is a component of $\partial F_{14}$. Then we can assume
$S_{12}=\emptyset$ after performing XI move and IX moves along $S_{1}2$ by
Lemma 4.1.If $S_{12}$ satisfies that $\partial S_{12}\cap\partial
F_{13}=\emptyset$ or $\partial S_{12}\cap\partial F_{14}=\emptyset$, $S_{12}$
is a disk after performing type 1 stabilizations. After performing the above
procedure for all components of $F_{12}$, $F_{12}$ is an empty set or a union
of disks.

Suppose that $F_{12}$ is an empty set. We shall consider about $F_{13}$. We
can take arcs properly embedded in $F_{13}$ which cut open each component of
$F_{13}$ into a disk. Since $\partial H_{1}=F_{13}\cup F_{14}$, the endpoints
of such arcs are contained in $\partial F_{14}$. Hence we can perform type 1
stabilization along such arcs. After performing type 1 stabilization along
such arcs, we can assume that $F_{13}$ is a union of disks. Then we shall
consider about $F_{23}$. Since $\partial H_{2}=F_{23}\cup F_{24}$, we can take
arcs properly embedded in $F_{23}$ so that such arcs cut open $F_{23}$ into a
disks. Hence $F_{23}$ can be deformed into an empty set or a union of disks
without changing $F_{12}$ and $F_{13}$ in the same way as before. Since
$F_{12}=\emptyset$, $F_{13}$ is a union of disks, $F_{23}$ is an empty set or
a union of disks, $H_{1}\cup H_{2}\cup H_{3}$ is a handlebody.

Next, we suppose that $F_{12}$ consists of disks. Let $S_{13}$ be a component
of $F_{13}$. Suppose $\partial S_{13}\cap\partial F_{14}=\emptyset$. Then we
can assume that each of the components of $\partial S_{13}$ is also a
component of $\partial F_{12}$. Since $F_{12}$ is a union of disks, $\partial
H_{1}=S_{13}\cup F_{12}$. This contradicts that $F_{14}\neq\emptyset$. Hence
we can assume that $\partial S_{13}\cap\partial F_{14}\neq\emptyset$. Suppose
that $\partial S_{13}\cap\partial F_{12}\neq\emptyset$ and $\partial
S_{13}\cap\partial F_{14}\neq\emptyset$. Let $C^{\prime}$ be a component of
$\partial S_{13}\cap\partial F_{14}$. Then we can take arcs properly embedded
in $S_{13}$ which cuts open $S_{13}$ into a planar surface and satisfies their
endpoints are in $C^{\prime}$. After performing type 1 stabilizations along
such arcs, we can assume $S_{13}$ is a planar surface without changing
$F_{12}$. Then we can take arcs properly embedded in $S_{13}$ which connects
the components of $\partial S_{13}\cap\partial F_{12}$ (resp. $\partial
S_{13}\cap\partial F_{14}$) each other and cut open $S_{13}$ into an annulus
with keeping $F_{12}$ as a union of disks. After perfroming type 1
stabilizations along such arcs, we can assume $S_{13}$ is an annulus. Then we
can deform $S_{13}$ into an empty set by performing XI move and IX moves along
$S_{13}$ without changing $F_{12}$ by Lemma 4.1. Suppose that $\partial
S_{13}\cap\partial F_{12}=\emptyset$ and $\partial S_{13}\cap\partial
F_{14}\neq\emptyset$. Then we can take arcs properly embedded in $S_{13}$
which cuts open $S_{13}$ into a disk so that endpoints of such arcs are
contained in $\partial F_{14}$. After performing type 1 stabilizations along
such arcs, $S_{13}$ becomes a disk. Hence $F_{13}$ is an empty set or a union
of disks. Then we shall consider $F_{23}$. We note that $F_{24}$ or $F_{34}$
is not an empty set. Hence we can assume that $F_{24}\neq\emptyset$. Let
$S_{23}$ be a component of $F_{23}$. If $S_{23}\cap F_{24}=\emptyset$,
$\partial H_{2}=S_{23}\cup F_{12}$ since $F_{12}$ is a union of disks. In
particular, $F_{24}=\emptyset$. This is a contradiction. Hence $S_{23}\cap
F_{24}\neq\emptyset$. Then we can take arcs properly embedded in $S_{23}$
which cuts open $S_{23}$ into an annulus or disk so that endpoints of such
arcs are contained in $\partial F_{24}$. We can deform $F_{23}$ into an empty
set or a union of disks by performing type 1 stabilizations along such arcs
and XI move and IX moves. Now, $F_{ij}$ is an empty set or a union of disks
for $\\{i,j\\}\subset\\{1,2,3\\}$. After performing type 1 stabilization, we
can assume $F_{ij}$ is an empty set or exactly one disk for
$\\{i,j\\}\subset\\{1,2,3\\}$. Hence we can assume that $H_{1}\cup H_{2}\cup
H_{3}$ is a handlebody. ∎

Figure 7. $H_{1}\cup H_{2}\cup H_{3}$ is a handlebody.

Similarly, we can assume $H_{1}^{\prime}\cup H_{2}^{\prime}\cup
H_{3}^{\prime}$ is a handlebody. By Claim 4.1 and a stable equivalence of
Heegaard splittings, we can assume $H_{4}=H_{4}^{\prime}$ after performing
type 0 stabilizations finitely many times. From now, we assume that each of
$F_{12}$, $F_{13}$ and $F_{23}$ is a disk.

Step 2: We show the following claim to achieve step 2.

######  Claim 4.2.

We can deform $F_{24}$ and $F_{34}$ into disks by type 1 stabilizations and XI
and IX moves.

###### Proof.

Now, each of $F_{12}$, $F_{13}$ and $F_{23}$ is a disk. Then we can take arcs
properly embedded in $F_{24}$ which cut open $F_{24}$ into a disk and annulus
and satisfies their endpoints are contained in $\partial F_{12}$. After
applying type 1 stabilizations along such arcs, we can assume $F_{24}$ is a
union of a disk and an annulus. One of the boundaries of the annulus component
of $F_{24}$ is the component of $F_{12}$ and the other is the component of
$F_{34}$. By Lemma 4.1, after applying XI and IX moves along the annulus, we
can assume $F_{24}$ is a disk and $F_{13}$ has the new annulus component.

Now, $F_{13}$ is the union of a disk and an annulus. We note that each of the
components of $\partial F_{34}$ is a component of $\partial F_{13}$. Then we
can take arcs properly embedded in $F_{34}$ which cut open $F_{34}$ into a
disk. After applying type 1 stabilizations along such arcs, we can assume that
$F_{34}$ is a disk. (See Figure 8)

Figure 8. The situation of handlebody decomposition after Claim 4.2. The red
curves in this figure are branched loci.

∎

Step 3: We show the following two claims to achieve step 3.

######  Claim 4.3.

Let $D_{i1},...,D_{ig_{i}}$ be a complete meridian disks system of $H_{i}$ so
that $\partial D_{ij}\subset F_{1i}$ for $i\in\\{2,3\\}$ and
$j\in\\{1,...,g_{i}\\}$ and $D$ the union $\cup_{i,j}D_{ij}$ for all $D_{ij}$.
Then there exist disjoint meridian disks $E_{ij}$
$(i\in\\{2,3\\},j\in\\{1,...,g_{i}\\})$ of $H_{1}$ such that $\partial
E_{ij}\subset F_{14}\cup F_{1i}$ and $E_{ij}\cap D=E_{ij}\cap D_{ij}$ is one
point.

###### Proof.

There exist mutually disjoint disks $E_{2}$ and $E_{3}$ in $H_{1}$ such that
$E_{2}\cup E_{3}$ cuts off a handlebody $W$ from $H_{1}$ so that
$(W,F_{12}\cup F_{13})$ is homeomorphic to $((F_{12}\cup
F_{13})\times[0,1],(F_{12}\cup F_{13})\times\\{0\\})$ (See Figure 8). Then we
can take mutually disjoint non-separating arcs
$\alpha_{i1},...,\alpha_{ig_{i}}$ properly embedded in $F_{1i}$ so that
$\alpha_{ij}\cap D=\alpha_{ij}\cap D_{ij}$ is exactly one point and
$\partial\alpha_{j}\subset F_{i4}$ for $i=2,3$. Let $E_{ij}$ be a disk
corresponding to $\alpha_{ij}\times[0,1]$ so that $E_{ij}\cap E_{i}=\emptyset$
for each $i\in\\{2,3\\}$. Then the statement holds since $\partial
W-(E_{1}\cup E_{2})\subset F_{12}\cup F_{13}\cup F_{14}$. We note that
$E_{ij}$ is a meridian disk of $H_{i}$ since each of $\alpha_{ij}$ is a non-
separating arc. ∎

######  Claim 4.4.

Let $D_{i1},...,D_{ig_{i}}$ be a complete meridian disks system of $H_{i}$ so
that $\partial D_{ij}\subset F_{1i}$ for $i\in\\{2,3\\}$ and
$j\in\\{1,...,g_{i}\\}$ and $D$ the union $\cup_{i,j}D_{ij}$ for all $D_{ij}$.
Then there is a meridian disk $D^{\prime}$ of $H_{1}$ which satisfies the
following.

  1. (1)

$D^{\prime}\cap D=\emptyset$.

  2. (2)

$\partial D\subset F_{12}\cup F_{13}\cup F_{14}$.

  3. (3)

$D\cap F_{34}$ is exactly one point.

  4. (4)

$D^{\prime}$ does not intersects $E_{ij}$ constructed in Claim 4.3

###### Proof.

Let $W$ be the handlebody in a proof of Claim 4.3 and each of $E_{ij}$ is a
disk obtained by Claim 4.3. Since $E_{ij}\cap H_{2}$ and $E_{ij}\cap H_{3}$
does not intersects $F_{23}$, there is a non-separating arc properly embedded
in $F_{12}\cup F_{13}$ which does not intersects all $E_{ij}$ in Claim 4.3.
Hence we can take a non-separating arc $\beta$ properly embedded in
$F_{12}\cup F_{13}$ so that $\beta\cap D=\emptyset$, $\beta\cap F_{23}$ is one
point and one of the endpoints of $\partial\beta$ is in $F_{24}$ and the other
is in $F_{34}$. Let $D^{\prime}$ be a disk corresponding to $\beta\times[0,1]$
so that $D^{\prime}\cap E_{i}$ for each $i=2,3$. Then the statement holds. ∎

We call a regular neighborhood of each of $D_{ij}$ in $H_{i}$ a 1-handle of
$H_{i}$ for $i=2,3$. We call a regular neighborhood of $F_{23}$ in $H_{2}\cup
H_{3}$ a 1-handle connecting $H_{2}$ and $H_{3}$. Claim 4.3, 4.4 implies that
any 1-handle of $H_{2}$ and $H_{3}$ is a local 1-handle for $H_{4}$. The disks
$E_{ij}$’s and $D^{\prime}$ in Claim 4.3, 4.4 are dual disks for 1-handles of
$H_{i}$ for $i=2,3$. Similarly, we can also take such dual disks for the
1-handles of $H_{2}^{\prime}$ and $H_{3}^{\prime}$ and a 1-handle connecting
$H_{2}^{\prime}$ and $H_{3}^{\prime}$. Let $S_{1}$ be the surface $F_{14}$ at
this stage.

Step 4: We shall show $H_{2}=H_{2}^{\prime}$ in this step. Since $F_{24}$,
$F_{34}$, $F_{24}^{\prime}$ and $F_{34}^{\prime}$ are disks, we can assume
that $F_{24}=F_{24}^{\prime}$ and $F_{34}=F_{34}^{\prime}$. We can take arcs
properly embedded in $S_{1}$ so that the arcs cut open $S_{1}$ into an annulus
and their endpoints lie in $\partial F_{24}=\partial F_{24}^{\prime}$. We
perform type 1 stabilizations for $H_{2}$ and $H_{2}^{\prime}$ along such
arcs. Then $F_{14}=S_{1}-F_{12}(=S_{1}-F_{12}^{\prime})$ becomes an annulus
$A$ such that one of the boundaries of $A$ is a component of $\partial F_{13}$
(resp. $F_{13}$’) and the other is a component of $\partial F_{23}$ (resp.
$F_{14}$’). See Figure 9.

According to the stabilizations of $H_{2}$ (resp. $H_{2}^{\prime}$), there
exists a separating disk $D_{2}$ and $D_{2}^{\prime}$ in $H_{2}$ and
$H_{2}^{\prime}$ respectively which cut off handlebodies $V_{2}$ and
$V_{2}^{\prime}$ from $H_{2}$ and $H_{2}^{\prime}$ respectively so that
$(V_{2},S_{1}-A)$ and $(V_{2}^{\prime},S_{1}-A)$ are homeomorphic to
$((S_{1}-A)\times[0,1],(S_{1}-A)\times\\{0\\})$. Since $H_{4}=H_{4}^{\prime}$,
$V_{2}=V_{2}^{\prime}$. See Figure 9.

We note that dual disks of 1-handles of $H_{2}-V_{2}$ and
$H_{2}^{\prime}-V_{2}^{\prime}$ induce dual disks of $H_{2}-V_{2}$ and
$H_{2}^{\prime}-V_{2}^{\prime}$ in $H_{1}$ for $V_{2}=V_{2}^{\prime}$
respectively. Hence, 1-handles of $H_{2}-V_{2}$ and
$H_{2}^{\prime}-V_{2}^{\prime}$ are local for $V_{2}=V_{2}^{\prime}$. If
necessary, we perform type 0 stabilizations of $H_{2}$ or $H_{2}^{\prime}$
until genus of $H_{2}$ and $H_{2}^{\prime}$ are the same. The 1-handles of
$H_{2}$ and $H_{2}^{\prime}$ which are obtained by type 0 stabilizations are
local for $V_{2}$ and $V_{2}^{\prime}$ respectively by a definition of a type
0 stabilization. After that we perform handle sliding 1-handles of
$H_{2}-V_{2}$ on $V_{2}=V_{2}^{\prime}$ until
$H_{2}-V_{2}=H_{2}^{\prime}-V_{2}^{\prime}$. Since $V_{2}=V_{2}^{\prime}$,
$H_{2}=H_{2}^{\prime}$.

Figure 9. We perform type 1 stabilizations along green arcs in this left
figure. After that $H_{2}$ is divided two handlebodies by $D_{2}$ in the right
figure.

Let $S_{2}$ be the surface $F_{12}$ at this stage.

Step 5: We shall show $H_{3}=H_{3}^{\prime}$ in this step. After performing XI
and IX move along $A$, we can eliminate $A$ from $F_{14}$ by Lemma 4.1. After
that, $F_{14}$ becomes an emptyset. Then we can take arcs properly embedded in
$F_{12}$ (resp. $F_{12}^{\prime}$) which cut open $F_{12}$ (resp.
$F_{12}^{\prime}$) into a disk $D^{2}$ and their endpoints lie in $\partial
H_{3}$ (resp. $\partial H_{3}^{\prime}$). We can perform type 1 stabilizations
along such arcs.

According to the stabilizations of $H_{3}$ and $H_{3}^{\prime}$, there exists
a separating disk $D_{3}$ and $D_{3}^{\prime}$ in $H_{3}$ and $H_{3}^{\prime}$
respectively which cut off handlebodies $V_{3}$ and $V_{3}^{\prime}$ from
$H_{3}$ and $H_{3}^{\prime}$ respectively so that $(V_{3},S_{2}-D^{2})$ and
$(V_{3}^{\prime},S_{2}-D^{2})$ are homeomorphic to
$((S_{2}-D^{2})\times[0,1],(S_{2}-D^{2})\times\\{0\\})$. Since
$H_{2}=H_{2}^{\prime}$ and $H_{4}=H_{4}^{\prime}$, $V_{3}=V_{3}^{\prime}$.

By Claim 4.3, 1-handles of $H_{3}-V_{3}$ and $H_{3}^{\prime}-V_{3}^{\prime}$
are local for $V_{3}=V_{3}^{\prime}$. Also, by Claim 4.4, 1-handles connecting
$H_{3}$ and $H_{2}$ (resp. $H_{2}^{\prime}$ and $H_{3}^{\prime}$) is local for
$V_{3}$ (resp. $V_{3}^{\prime}$). If necessary, we perform type 0
stabilization of $H_{3}$ or $H_{3}^{\prime}$ until genus of $H_{3}$ and
$H_{3}^{\prime}$ are the same. After that, we perform handle sliding 1-handles
of $H_{3}-V_{3}$ on $V_{3}=V_{3}^{\prime}$ until
$H_{3}-V_{3}=H_{3}^{\prime}-V_{3}^{\prime}$. Since $V_{3}=V_{3}^{\prime}$,
$H_{3}=H_{3}^{\prime}$.

Finally we have $H_{1}=H_{1}^{\prime}$ automatically from
$H_{1}=H_{1}^{\prime}$, $H_{2}=H_{2}^{\prime}$ and $H_{4}=H_{4}^{\prime}$.
This implies that partitions of two multibranched handlebody decompositions
are isotopic to each other. ∎

##  5\. characterization of 3-manifolds with multibranched handlebody
decompositions with four handlebodies

In this section, we characterize 3-manifolds with multibranched handlebody
decompositions with four handlebodies. We consider the case where the genera
of handlebodies are at most one. First, we consider the decompositions such
that one of the handlebodies is a 3-ball.

######  Proposition 5.1.

Let $M$ be a closed, connected, orientable 3-manifold. If $M$ has a
type-$(0,g_{2},g_{3},g_{4})$ multibranched handlebody decomposition, then $M$
has a type-$(g_{2},g_{3},g_{4})$ decomposition.

###### Proof.

After performing XI moves, we can assume that all branched loci are
tribranched. $H_{1}$ is a 3-ball. Suppose that $F_{14}=\emptyset$. Then
$\partial H_{4}=F_{24}\cup F_{34}$. If one of $F_{24}$ and $F_{34}$ is an
emptyset, $M$ is not connected. This is a contradiction. Then each of $F_{24}$
and $F_{34}$ is not an emptyset. If any components of $F_{23}$ do not
intersect component of $F_{24}$, $\partial F_{24}$ is contained $\partial
F_{12}$. This contradicts that $F_{14}=\emptyset$. Hence any components of $F$
of $F_{23}$ have a boundary component which is also a boundary component of
$F_{24}$. Then we can take an arc properly embedded in the component of
$F_{23}$ which connects $H_{1}$ and $H_{4}$. Let $N$ be a regular neighborhood
of such arc. Then, let $H_{2}^{\prime}=H_{2}-N$, $H_{3}^{\prime}=H_{3}-N$ and
$H_{4}^{\prime}=H_{4}\cup N\cup H_{1}$. Since $H_{4}\cap N$ and $N\cap H_{1}$
is a disk and $H_{4}\cap H_{1}=\emptyset$, $H_{i}^{\prime}\cong H_{i}$ for
$i=2,3,4$. Hence $M$ has a type-$(g_{2},g_{3},g_{4})$ decomposition.

Then, we can suppose that $F_{1i}\neq\emptyset$ for $i=2,3,4$. We take a
regular neighborhood $N(F_{12})$ of $F_{12}$ in $\partial H_{1}$ so that
branched loci contained in $N(F_{12})$ is only $\partial F_{12}$. Hence
$N(F_{12})-F_{12}$ is a union of annuli which are the regular neighborhood of
$\partial F_{12}$ in $F_{13}$ or $F_{14}$. Let $A_{1},...,A_{k}$ be such
annuli. There are mutually disjoint disks properly embedded in $H_{1}$ whose
boundaries are components of $\partial N(F_{12})$. Such disks cut open $H_{1}$
into some 3-balls. We call such 3-balls $C_{1},...,C_{n}$ if their boundary
contain the component of $F_{12}$. Otherwise, we call
$C_{1}^{\prime},...,C_{m}^{\prime}$.

There exist properly embedded essential arcs in each components of
$N(F_{12})-F_{12}=A_{1}\cup\cdots\cup A_{k}$. We take a subset of such arcs
$\\{\alpha_{1},...,\alpha_{m}\\}$ so that one of the endpoints of $\alpha_{i}$
are contained in $C_{i}^{\prime}$. Let $N$ be a regular neighborhood of
$\alpha_{1}\cup\cdots\cup\alpha_{m}$. Let $H_{2}^{\prime}=H_{2}\cup N\cup
C_{1}^{\prime}\cup\cdots\cup C_{m}^{\prime}$, $H_{3}^{\prime}=H_{3}-N$,
$H_{4}^{\prime}=H_{4}-N$. Since $H_{2}\cap N$ are disks and $N\cap
C_{i}^{\prime}$ is a disk, $H_{i}^{\prime}\cong H_{i}$ for $i=2,3,4$.

Next, we shall consider the 3-balls $C_{1},...,C_{n}$. Suppose that at least
one of the 3-ball $C_{i}$ does not contain the subsurface of $F_{13}$. Let
$C_{1}$ be a such 3-ball. If there is a component of $F_{14}$ which has an
intersection with $C_{1}$ intersects $F_{13}$, we can take an arc properly
embedded in $F_{14}-(F_{14}\cap C_{1})$ which connects $C_{1}$ and $H_{3}$.
Let $N^{\prime}$ be a regular neighborhood of a such arc. Then we can replace
$H_{3}^{\prime}=H_{3}\cap N\cap C_{1}$. Next, Suppose that any components of
$F_{14}$ which has an intersection with $C_{1}$ do not intersect $F_{13}$.
Then the components of $F_{14}$ in $\partial C_{1}$ adjacent to a component of
$F_{12}$. Let $F^{\prime}$ be the component of $F_{14}$ in $\partial C_{1}$.
Let $C_{2}$ be a 3-ball which contains a component of $F_{12}$ adjacent to
$F^{\prime}$. Suppose $\partial C_{2}$ contains a subsurface of $F_{13}$. We
can take a regular neighborhood $N(F^{\prime})$ of $F^{\prime}$ in $\partial
C_{2}$. Then there is a disk which cuts open $C_{2}$ into two 3-balls. Let
$C_{2}^{1}$ be one of the 3-ball which contains subsurface of $F^{\prime}$ and
$C_{2}^{2}$ the other. We can take an arc which connect $H_{3}$ and
$C_{2}^{1}$, and an arc properly embedded in $F^{\prime}-(F^{\prime}\cap
C_{2})$ which connects $C_{2}^{1}$ and $C_{1}$. Let $N^{\prime}$ be a regular
neighborhood of such arcs. Then we can replace $H_{3}^{\prime}=H_{3}\cap
N^{\prime}\cap(C_{1}\cap C_{2}^{1})$. Even if $C_{2}$ does not contains a
subsurface of $F_{13}$, we can proceed the steps above. Hence we can assume
any $C_{i}$ contains $F_{13}$ and $F_{14}$ for $i=1,...,n$.

The intersection $C_{i}\cap H_{2}^{\prime}$ equals to $(C_{i}\cap
N)\cup(C_{i}\cap(C_{1}^{\prime}\cup\cdots\cup C_{m}^{\prime}))\cup S_{i}$
where $S_{i}$ is a component of $F_{12}$ in $C_{i}$. Then $C_{i}\cap(H_{3}\cup
H_{4})$ equals to $C_{i}\cap((A_{1}\cup\cdots\cup A_{k})-N)$. If $\alpha_{i}$
is contained in $A_{k}$, $N(\alpha_{i})$ cuts open $A_{k}$ into a disk. This
implies that some of the intersections $C_{i}\cap(H_{3}\cup H_{4})$ are disks
and the others are annuli. Let $F^{i}_{j}$ be intersections $C_{i}$ and
$H_{j}^{\prime}$ for $j=2,3,4$. Then $\partial C_{i}$ can be seen as in Figure
10.

Figure 10. $\partial C_{i}$ intersects $H_{3}^{\prime}$ and $H_{4}^{\prime}$
in annuli and disks.

We take a regular neighborhood $N(F^{i}_{4})$ of $F^{i}_{4}$ so that branched
loci in $N(F^{i}_{4})$ is only $\partial F^{i}_{4}$ for $i=1,...,n$. We can
take mutually disjoint disks properly embedded in $C_{i}$ whose boundary
equals to the components of $\partial N(F^{i}_{4})$ which is contained in
$F_{12}$ for $i=1,...,n$. Such disks cuts open $(C_{i}-N)$ into 3-balls for
$i=1,...,n$.

Let $B_{1},...,B_{l}$ be such 3-balls. Some of $B_{1},...,B_{l}$ contains
$S_{i}$ for $i=1,...,n$. Suppose that $\partial B_{i}$ contains $S_{i}$ for
$i=1,...,n$. There are mutually disjoint arcs
$\\{\alpha_{1},...,\alpha_{l}\\}$ properly embedded in $F_{12}-N(F^{i}_{4})$
so that $\alpha_{i}$ connect $F$ and $B_{i}^{\prime}$ for $i=n+1,...,l$ where
$F$ is a one of the component of $F^{i}_{3}$ (See Figure 11).

Figure 11. We take arcs connects $F^{i}_{3}$ and $F^{i}_{4}$. Such arcs
connect $H_{3}^{\prime}$ and $B_{i}$ for $i\neq 1,...,n$.

Let $N^{\prime}$ be a regular neighborhood of such arcs. Also there is an
essential arc properly embedded in $N(F^{i}_{4})-F^{i}_{4}$ for $i=1,...,n$.
Let $N^{\prime\prime}$ be a regular neighborhood of such arcs.
$H_{3}^{\prime\prime}=H_{3}^{\prime}\cup
N^{\prime}\cup((B_{1}-N^{\prime\prime})\cup\cdots\cup(B_{l}-N^{\prime\prime}))$,
$H_{2}^{\prime\prime}=H_{2}^{\prime}$ and $H_{4}^{\prime\prime}=H_{4}\cup
N^{\prime\prime}\cup((C_{1}-N-N^{\prime})\cup\cdots\cup(C_{n}-N-N^{\prime}))$
Since each of $H_{3}^{\prime}\cap N^{\prime}$ and $B_{i}\cap N^{\prime}$ is a
disk for $i=1,...,l$, $H_{3}^{\prime\prime}\cong H_{3}$. Also since each of
$H_{4}^{\prime}\cap N^{\prime\prime}$ and $(C_{i}-N-N^{\prime})\cap
N^{\prime\prime}$ is a disk for $i=1,...,n$, $H_{4}^{\prime\prime}\cong
H_{4}$. Since $H_{i}^{\prime\prime}$ has no self intersection for $i=2,3,4$,
$H_{2}^{\prime\prime}\cup H_{3}^{\prime\prime}\cup H_{4}^{\prime\prime}$ is a
type-$(g_{2},g_{3},g_{4})$ decomposition. ∎

By Proposition 5.1, we obtain the following Proposition.

######  Proposition 5.2.

Let $M$ be a closed, connected, orientable 3-manifold. Then the following is
satisfied.

  1. (1)

If $M$ has a type-$(0,0,0,0)$ decomposition, then $M$ has a type-$(0,0,0)$
decomposition

  2. (2)

If $M$ has a type-$(0,0,0,1)$ decomposition, then $M$ has a type-$(0,0,1)$
decomposition.

  3. (3)

If $M$ has a type-$(0,0,1,1)$ decomposition, then $M$ has a type-$(0,1,1)$
decomposition.

  4. (4)

If $M$ has a type-$(0,1,1,1)$ decomposition, then $M$ has a type-$(1,1,1)$
decomposition.

Gomez-Larrañaga studied handlebody decompositions in [3]. He characterized
3-manifolds which admit decompositions with handlebodies of genera at most
one. Let $\mathbb{B}$ be a connected sum of a finite number of $S^{2}\times
S^{1}$’s, let $\mathbb{L}$ and $\mathbb{L}_{i}$ be lens spaces, and let
$\mathbb{S}(3)$ be a Seifert manifold with at most three exceptional fibers.
He showed the following proposition in [3].

######  Proposition 5.3 ([3]).

Let $M$ be a closed, connected, orientable 3-manifold.

  1. (1)

$M$ has a type-$(0,0,0)$ decomposition if and only if $M$ is homeomorphic to
$\mathbb{B}$.

  2. (2)

$M$ has a type-$(0,0,1)$ decomposition if and only if $M$ is homeomorphic to
$\mathbb{B}$ or $\mathbb{B}\\#\mathbb{L}$.

  3. (3)

$M$ has a type-$(0,1,1)$ decomposition if and only if $M$ is homeomorphic to
$\mathbb{B}$ or $\mathbb{B}\\#\mathbb{L}$ or
$\mathbb{B}\\#\mathbb{L}_{1}\\#\mathbb{L}_{2}$.

  4. (4)

$M$ has a type-$(1,1,1)$ decomposition if and only if $M$ is homeomorphic to
$\mathbb{B}$ or $\mathbb{B}\\#\mathbb{L}$ or
$\mathbb{B}\\#\mathbb{L}_{1}\\#\mathbb{L}_{2}$ or
$\mathbb{B}\\#\mathbb{L}_{1}\\#\mathbb{L}_{2}\\#\mathbb{L}_{3}$ or
$\mathbb{B}\\#\mathbb{S}(3)$.

By Proposition 5.3 and Proposition 5.2, we can obtain the following theorem.

######  Theorem 1.2.

Let $M$ be a closed, connected, orientable 3-manifold. Then the following is
satisfied.

  1. (1)

$M$ has a type-$(0,0,0,0)$ decomposition if and only if $M$ is homeomorphic to
$\mathbb{B}$.

  2. (2)

$M$ has a type-$(0,0,0,1)$ decomposition if and only if $M$ is homeomorphic to
$\mathbb{B}$ or $\mathbb{B}\\#\mathbb{L}$.

  3. (3)

$M$ has a type-$(0,0,1,1)$ decomposition if and only if $M$ is homeomorphic to
$\mathbb{B}$ or $\mathbb{B}\\#\mathbb{L}$ or
$\mathbb{B}\\#\mathbb{L}_{1}\\#\mathbb{L}_{2}$.

  4. (4)

$M$ has a type-$(0,1,1,1)$ decomposition if and only if $M$ is homeomorphic to
$\mathbb{B}$ or $\mathbb{B}\\#\mathbb{L}$ or
$\mathbb{B}\\#\mathbb{L}_{1}\\#\mathbb{L}_{2}$ or
$\mathbb{B}\\#\mathbb{L}_{1}\\#\mathbb{L}_{2}\\#\mathbb{L}_{3}$ or
$\mathbb{B}\\#\mathbb{S}(3)$.

Next we characterize 3-manifolds with type-$(1,1,1,1)$ decomposition.

######  Theorem 1.3.

Let $M$ be a closed, connected, orientable 3-manifold. Then $M$ has a
type-$(1,1,1,1)$ decomposition if and only if $M$ is homeomorphic to
$\mathbb{B}$ or $\mathbb{B}\\#\mathbb{L}$ or
$\mathbb{B}\\#\mathbb{L}_{1}\\#\mathbb{L}_{2}$ or
$\mathbb{B}\\#\mathbb{L}_{1}\\#\mathbb{L}_{2}\\#\mathbb{L}_{3}$ or
$\mathbb{B}\\#\mathbb{L}_{1}\\#\mathbb{L}_{2}\\#\mathbb{L}_{3}\\#\mathbb{L}_{4}$
or $\mathbb{B}\\#\mathbb{S}(4)$.

###### Proof.

Let $H_{1}\cup H_{2}\cup H_{3}\cup H_{4}$ be a type-$(1,1,1,1)$ decomposition.
If the number of branched loci of a type-$(1,1,1,1)$ decomposition is at most
one, one of the handlebodies has self intersection. Hence the number of
branched loci of a type-$(1,1,1,1)$ decomposition is at least two. We perform
XI moves to deform degree four branched loci of this decomposition to
tribranched loci. First, we consider the case where one of $F_{ij}$’s contains
a disk component.

######  Claim 5.1.

Let $D$ be a disk component of $F_{ij}$. If $\partial D$ is inessential in
$\partial H_{k}$ or $\partial H_{l}$ for $k\neq l$, then $M\cong
M^{\prime}\\#S^{2}\times S^{1}$ or $M\cong M^{\prime}\\#\mathbb{L}$ where
$M^{\prime}$ has either a type-$(1,1,1,1)$ or a type-$(0,0,1,1)$ decomposition
respectively whose partition is tribranched surface.

###### Proof of Claim.

Let $D$ be a disk component of $F_{12}$ and $\partial D$ be inessential in
$\partial H_{3}$. Suppose that exactly one of $F_{2i}$ is an emptyset for
$i=3,4$ and $F_{12}$ is only a disk. Assume that $F_{24}$ is an emptyset.
Since $\partial H_{2}=F_{12}\cup F_{23}$ and $F_{12}$ is a disk, $F_{23}$ is a
punctured torus. Then we can take a meridian disk of $H_{2}$ whose boundary is
contained in $F_{23}$ and its regular neighborhood $h$ in $H_{2}$. After
attaching $h$ to $H_{3}$ as a 2-handle, we can obtain a punctured lens space
$h\cup H_{3}$. Then $M=M^{\prime}\\#\mathbb{L}$ where $\mathbb{L}$ is a lens
space which is obtained from $h\cup H_{3}$ by capping off.
$M^{\prime}=H_{1}\cup(H_{2}-h)\cup H_{4}\cup B$ is a type-$(0,0,1,1)$
decomposition where $B$ is a 3-ball since $H_{2}-h$ is a 3-ball. If exactly
one of the $F_{1i}$ is an emptyset for $i=3,4$ and $F_{12}$ is a disk, we can
show samely as above. We only remains two cases. One is a case where each of
$F_{1i}$ and $F_{2i}$ is not emptyset for $i=3,4$ and the other is a case
where $F_{12}$ has at least two components.

Next, we suppose that each of $F_{1i}$ and $F_{2i}$ are not emptyset for
$i=3,4$ or $F_{12}$ has at least two components. Let $D^{\prime}$ be a disk in
$\partial H_{3}$ such that $\partial D=\partial D^{\prime}$ and $S=D\cup
D^{\prime}$. If each of $F_{1i}$ and $F_{2i}$ are not emptyset for $i=3,4$, we
can take an arc properly embedded in $H_{1}\cup H_{2}$ so that one of the
endpoints of the arc is contained in a component of $F_{14}$ and the other is
contained in a component $F_{24}$ and it intersects $D$ exactly once. Also we
can take an arc properly embedded in $H_{4}$ so that the end points of the
each arcs are the same. If $F_{12}$ has at least two components, we can take
an arc properly embedded in $H_{1}$ so that one of the endpoints if the arc is
contained in $D$ and the other is contained in a component of $F_{12}$. Also
we can take an arc properly embedded in $H_{2}$ so that the end points of the
each arcs are the same. Hence $S=D\cup D^{\prime}$ is a non-separating sphere
in $M$. Hence $M\cong M^{\prime}\\#S^{2}\times S^{1}$. To show a claim, we
will show $M^{\prime}$ has a type-$(1,1,1,1)$ decomposition.

Let $N(D)$ be a regular neighborhood of $D$ in $H_{1}\cup H_{2}$ and $N(D)\cap
H_{1}=D_{1}$ and $N(D)\cap H_{2}=D_{2}$. Then $D_{1}$ and $D_{2}$ are disks.

We can take a properly embedded disk $D_{1}^{\prime}$ in $H_{3}$ such that
$\partial D_{1}^{\prime}=\partial D_{1}$ and disk $D_{2}^{\prime}$ in
$\partial H_{3}$ such that $\partial D_{2}=\partial D_{2}^{\prime}$. Hence
$D_{2}^{\prime}$ may contain components each of $F_{3i}$ for $i=1,2,4$.

We can take a regular neighborhood $N(S)$ of $S$ so that $S_{1}=D_{1}\cup
D_{1}^{\prime}$ and $S_{2}=D_{2}\cup D_{2}^{\prime}$ where $\partial
N(S)=S_{1}\cup S_{2}$. See Figure 12.

Figure 12. We take a regular neighborhood of $S$ so that $\partial
N(S)=S_{1}\cup S_{2}$ satisfies that $S_{1}=D_{1}\cup D_{1}^{\prime}$ and
$S_{2}=D_{2}\cup D_{2}^{\prime}$.

Then $\partial(M-N(S))=S_{1}\cup S_{2}$. We cap off $M-N(S)$ by 3-balls
$C_{1}$, $C_{2}$ with $\partial C_{i}=S_{i}$ for $i=1,2$. Then
$M^{\prime}=M-N(S)\cup C_{1}\cup C_{2}$. Let $H_{1}^{\prime}=(H_{1}-N(S))\cup
C_{1}$, $H_{2}^{\prime}=H_{2}-N(S)$, $H_{4}^{\prime}=H_{4}$ and
$H_{3}^{\prime}=H_{3}-N(S)$. By definition, $M^{\prime}=H_{1}^{\prime}\cup
H_{2}^{\prime}\cup H_{3}^{\prime}\cup H_{4}^{\prime}\cup C_{2}$. We note that
$C_{2}$ may have intersections with each of $H_{i}^{\prime}$ for $i=1,2,4$.

Let $F_{i}=C_{2}\cap H_{i}^{\prime}$ for $i=1,2,4$. Recall that $F_{2}$
contains a disk $D_{2}$. Suppose that one of the $F_{i}=\emptyset$ for
$i=1,4$. We can assume that $F_{4}=\emptyset$. Let $F$ be a component of
$F_{1}$. Then there is a components of $F_{12}$ whose boundary contains one of
the components of $\partial F$. We note that such components $F^{\prime}$ of
$F_{12}$ is adjacent to $F_{i4}$ or $F_{i3}$ for $i=1,2$. Suppose that
$F^{\prime}$ is adjacent to $F_{14}$. Then we can take an arc $\alpha$
properly embedded the component of $F_{12}$ which connects $C_{2}$ and
$H_{4}$. Then we define $H_{4}^{\prime\prime}=H_{4}\cup N(\alpha)\cup C_{2}$
and $H_{i}^{\prime\prime}=H_{i}^{\prime}$ for $i=1,2,3$. Since $\partial
C_{2}$ does not have an intersection with $H_{4}^{\prime}$, each of
$H_{i}^{\prime\prime}$ does not have self intersection. Then
$H_{1}^{\prime\prime}\cup H_{2}^{\prime\prime}\cup H_{3}^{\prime\prime}\cup
H_{4}^{\prime\prime}$ is a type-$(1,1,1,1)$ decomposition.

Hence we can assume that $F_{i}\neq\emptyset$ for $i=1,2,4$. We can take a
regular neighborhood $N(F_{4})$ of $F_{4}$ which contains no branched loci
other than $\partial F_{4}$ and properly embedded disks in $C_{2}$ whose
boundaries are components of $\partial N(F_{4})$. Such disks cut open $C_{2}$
into some 3-balls. Let $B_{1},...,B_{n}$ be such 3-balls whose boundaries
contain components of $F_{4}$. On the other hands, let
$B_{1}^{\prime},...,B_{m}^{\prime}$ be such 3-balls whose boundaries does not
contain components of $F_{4}$.

There exists a properly embedded essential arcs in each components of
$N(F_{4})-F_{4}$. Let $\alpha_{1},...,\alpha_{m}$ be a subset of such arcs
such that $\alpha_{i}$ connects $H_{4}^{\prime}$ and $B_{i}^{\prime}$. Let $N$
be a regular neighborhood of arcs $\alpha_{1},...,\alpha_{m}$ and
$H_{4}^{\prime\prime}=H_{4}\cup N\cup B_{1}^{\prime}\cup\cdots\cup
B_{m}^{\prime}$, $H_{i}^{\prime\prime}=H_{i}^{\prime}-N$ for $i=1,2,3$. It is
clear that $H_{i}^{\prime\prime}\cong H_{i}$ for $i=1,2,3$. Since each of
components of $N\cap H_{4}$ is a disk and $N\cap B_{i}$ is a disk for
$i=1,...,m$, $H_{4}^{\prime\prime}\cong H_{4}$. Since each of
$\alpha_{1},...,\alpha_{m}$ does not intersects branched loci, the
intersection of handlebodies is a tribranched surface.

Suppose that one of $\partial B_{i}$’s does not contain $F_{1}$. Let $\partial
B_{1}$ does not contain a component of $F_{1}$. Then $\partial B_{1}$ consists
of $F_{1}$ and $F_{4}$. There is a components of $F_{14}$ which is adjacent to
a component of $F_{1}$. Let $F^{\prime\prime}$ be a such component of
$F_{14}$. $F^{\prime\prime}$ adjacent to a components of either $F_{12}$ or
$F_{13}$. Suppose that $F^{\prime\prime}$ adjacent to $F_{13}$. Then we can
take an arc $\beta$ properly embedded $F^{\prime\prime}$ which connects
$B_{1}$ and $H_{3}$. We replace $H_{3}^{\prime}$ by $H_{3}^{\prime}\cup
N(\beta)\cup B_{1}$ where $N(\beta)$ is a regular neighborhood of $\beta$.
Since each of $H_{3}^{\prime}\cap N(\beta)$ and $N(\beta)\cap B_{1}$ is a
disk, a homeomorphism type of $H_{3}^{\prime}$ does not change by this
operation. This operation sends a tribranched surface to a tribranched surface
(See Figure 13).

Figure 13. An operation which sends a tribranched surface to a tribranched
surface

Hence we can assume that each of $\partial B_{i}$’s satisfies that $F_{j}$ in
$\partial B_{i}$ are not emptyset for $i=1,...,n$, $j=1,2,4$.

Let $N(F_{1})$ be a regular neighborhood of $F_{1}$ in $\partial B_{i}$’s
which contains no branched loci other than $\partial F_{1}$ for $i=1,...,n$.
The components of $\partial N(F_{1})$ in $F_{4}$ bounds disks properly
embedded in $B_{i}$ for $i=1,...,n$. Such disks cuts open $B_{i}$ into some
3-balls for $i=1,...,n$. Let $B_{1}^{\prime\prime},...,B_{l}^{\prime\prime}$
be such 3-balls whose boundary contain a component of $F_{1}$. We can take
essential arcs properly embedded in $F_{4}-N(F_{1})$ so that one of the
endpoints is contained in $B_{i}^{\prime\prime}$ for $i=1,...,l$ the other is
contained in $H_{2}$ since $F_{j}$ in $\partial B_{i}$ are not emptyset for
$i=1,...,n$, $j=1,2,4$. Let $\beta_{1},...,\beta_{l}$ be such arcs such that
$\beta_{i}$ connects $H_{2}$ and $B_{i}^{\prime\prime}$ for $i=1,...,l$ and
$N^{\prime}$ a regular neighborhood of union of such arcs.

Also, we can take essential arcs properly embedded in annuli $N(F_{1})\cap
F_{4}$. Let $\gamma_{1},...,\gamma_{n}$ be a such arcs such that $\gamma_{i}$
connects $H_{1}$ and $B_{i}$ for $i=1,...,n$ and $N^{\prime\prime}$ be a
regular neighborhood of union of such arcs.

Let $H_{1}^{\prime\prime\prime}=H_{1}^{\prime\prime}\cap N^{\prime\prime}\cup
B_{1}\cup\cdots B_{n}$, $H_{2}^{\prime\prime\prime}=H_{2}^{\prime\prime}\cup
N^{\prime}\cup B_{1}^{\prime\prime}\cup\cdots\cup B_{l}^{\prime\prime}$,
$H_{3}^{\prime\prime\prime}=H_{3}^{\prime\prime}$ and
$H_{4}^{\prime\prime\prime}=H_{4}^{\prime\prime}$. Then
$M^{\prime}=H_{1}^{\prime\prime\prime}\cup H_{2}^{\prime\prime\prime}\cup
H_{3}^{\prime\prime\prime}\cup H_{4}^{\prime\prime\prime}$. Since
$N^{\prime\prime}\cap H_{1}^{\prime\prime}$ is a union of disks and
$N^{\prime\prime}\cap B_{i}$ is a disk for $i=1,...,n$,
$H_{1}^{\prime\prime\prime}\cong H_{1}$. Also, Since $N^{\prime}\cap
H_{2}^{\prime\prime}$ is union of disks and $N^{\prime}\cap
B_{i}^{\prime\prime}$ is a disk for $i=1,...,l$,
$H_{2}^{\prime\prime\prime}\cong H_{2}$. Since each of
$\beta_{1},...,\beta_{l}$ and $\gamma_{1},...,\gamma_{n}$ does not intersect
the branched loci, the intersection of handlebodies is a tri-branched surface.
Hence Then $M^{\prime}=H_{1}^{\prime\prime\prime}\cup
H_{2}^{\prime\prime\prime}\cup H_{3}^{\prime\prime\prime}\cup
H_{4}^{\prime\prime\prime}$ is a type-$(1,1,1,1)$ handlebody decomposition
with tri-branched surface. ∎

By Claim 5.1, we can assume that disk components of $F_{ij}$ is essential in
$\partial H_{k}$ for $k\neq i,j$. If $F_{12}$ has a disk component $D$, we can
take a regular neighborhood $N(D)$ of $D$ in $H_{1}\cup H_{2}$. If $\partial
D$ is in $\partial H_{4}$, $H_{4}\cup N(D)$ is a punctured lens space $L$
since $\partial D$ is essential in $\partial H_{3}$. Then $M\cong
Cap(L)\\#M^{\prime}$ where $M^{\prime}$ is a capping off of $(H_{1}\cup
H_{2}\cup H_{3})-N(D)$. Hence $M^{\prime}=H_{1}\cup H_{2}\cup H_{3}\cup
H_{4}^{\prime}$ is a type-$(0,1,1,1)$ decomposition where $H_{4}^{\prime}$ is
a 3-ball. This implies that $M\cong\mathbb{L}\\#M^{\prime}$ where $M^{\prime}$
has a type-$(0,1,1,1)$ decomposition.

If $F_{ij}$ has no disk component, $F_{ij}$ is annuli for
$\\{i,j\\}\subset\\{1,2,3,4\\}$. This implies that $M$ is a Seifert manifold
with at most four singular fibers. ∎

We can see the difference between a multibranched handlebody decomposition and
a handlebody decomposition by Theorem 1.2. We can show that any orientable,
closed 3-manifold admits a type-$(0,0,0,0)$ handlebody decomposition. On the
other hand, there are a lot of orientable, closed 3-manifold which does not
admits type-$(0,0,0,0)$ multibranched handlebody decomposition.

##  6\. Acknowledgement

The author thanks to his supervisor Koya Shimokawa for very meaningful
discussion and insight. The author was partially supported by Grant-in-Aid for
JSPS Research Fellow from JSPS KAKENHI Grant Number JP20J20545.

## References

  * [1] K. Reidemeister, Zur dreidimensionalen Topologie, Abh. Math. Sem. Univ. Hamburg 9 (1933), 189-194.
  * [2] J. Singer, Three-dimensional manifolds and their Heegaard diagrams, Trans. Amer. Math. Soc. 35, (1933), 88-111.
  * [3] J. C. Gómez-Larrañaga, 3-manifolds which are unions of three solid tori. Manuscripta Math. 59 (1987), 325-330.
  * [4] J. C. Gómez-Larrañaga, F. González-Acuña and W. Heil, 2-stratifold splines of closed 3-manifolds. Osaka J. Math. 57 (2020), 267-277.
  * [5] D. R. Koenig, Trisections in Three and Four Dimensions, Doctor Thesis, University of California, (2017).
  * [6] S. Matsuzaki and M. Ozawa, Genera and minors of multibranched surfaces, Topology Appl. 230 (2017), 621-638.
  * [7] M. Ozawa, A partial order on multi-branched surfaces in 3-manifolds, Topology Appl. 272 (2020).
  * [8] K. Ishihara, Y. Koda, R. Mishina, M. Ogawa, M. Ozawa, N. Sakata, K. Shimokawa Handlebody decomposition of 3-manifolds and polycontinuous patterns, Proc. R. Soc. A 478 (2021)
  * [9] K. Ishihara, Y. Koda, M.Ozawa and K. Shimokawa. Neighborhood equivalence for multibranched surfaces in 3-manifolds. Topology Appl. 257 (2019), 11-21.
  * [10] Y. Ito and M.Ogawa. Decompositions of the 3-sphere and lens spaces with three handlebodies J. Knot Theory. Ramif 30, No. 9 (2021)