# NutCracker at WNUT-2020 Task 2: Robustly Identifying Informative COVID-19
Tweets using Ensembling and Adversarial Training

Priyanshu Kumar and Aadarsh Singh

Indian Institute of Technology (Indian School of Mines) Dhanbad, India
{kpriyanshu256, aadarshsingh191198<EMAIL_ADDRESS>

###### Abstract

We experiment with COVID-Twitter-BERT and RoBERTa models to identify
informative COVID-19 tweets. We further experiment with adversarial training
to make our models robust. The ensemble of COVID-Twitter-BERT and RoBERTa
obtains a F1-score of 0.9096 (on the positive class) on the test data of
WNUT-2020 Task 2 and ranks 1 on the leaderboard. The ensemble of the models
trained using adversarial training also produces similar result.

##  1 Introduction

Since 2006, Twitter has been a popular social network where people express
their thoughts and opinions on various topics. The enforcement of lockdown in
various parts of the world, due to COVID-19, led to an increased usage of
social media. Thus, the world has witnessed a plethora of tweets since the
beginning of COVID-19. People have tweeted about many issues regarding the
pandemic, mostly about the increasing infection rate, carelessness and
incapability of governance and authorities to handle the increasing rate of
cases. In addition, various preventive measures have also been conveyed
through tweets.

Although there have been more than 600 million English tweets on COVID-19
(Lamsal, 2020) , only a few of them are informative enough to be used by
various monitoring systems to update their databases. Manual identification of
these informative tweets can be tedious and erroneous. Hence, there is a dire
need to develop systems in the form of machine learning models that can help
us in filtering informative tweets.

In this paper, we present our approaches for the shared task “Identification
of informative COVID-19 English Tweets” organized under the Workshop on Noisy
User-generated Text (W-NUT). Our method makes use of ensembles consisting of
Bidirectional Encoder Representations from Transformers (BERT) (Devlin et al.,
2018) pretrained on COVID-19 tweets (Müller et al., 2020) and Robustly
Optimized BERT Pretraining Approach (RoBERTa) (Liu et al., 2019). We also
experiment with adversarial training so as to create models that generalise
well and are robust.

The rest of the paper is organized as follows: Related work has been discussed
in Section 2, followed by a brief description of the data used in Section 3.
The proposed methods and experimental settings 111Source code available at
https://github.com/kpriyanshu256/WNUT-2020-Task-2 have been elaborated in
Section 4, 5 and 6. Section 7 and 8 contains the results and error analysis
respectively. Section 9 concludes the paper and also includes possible future
work.

##  2 Related Work

There has been much research to identify informative tweets during times of
emergency and disaster. Neppalli et al. (2018) explored the performance of
traditional machine learning algorithms and deep learning approaches for
identifying informative tweets during disaster. They created manual features
using the content of tweets for machine learning approaches and also tried out
features obtained from Convolutional and Recurrent networks for deep learning
approaches. A multi-modal approach for classifying informative tweets during
disaster was proposed by Madichetty and Sridevi (2020). They combined the
features obtained from text by a Convolutional Neural Network and the VGG-16
features obtained from the image accompanying the tweet, using late fusion for
better performance than models using only text or only image.

Roy et al. (2020) proposed a classification and summarisation approach to
identify informative tweets during the Fani cyclone (which occurred in 2019,
affecting large parts of South-East Asia). They trained a Support Vector
Machine (SVM) on linguistic features and Parts of Speech (POS) tags from
tweets to identify informative tweets. To summarise the informative tweets,
they experimented with Latent Semantic Analysis (LSA) and Luhn summarisation
techniques. Zahera et al. (2019) experimented with the transformer based
architecture BERT to classify disaster related tweets into multi-label
information types. They preprocessed the tweets of TREC-IS dataset before
feeding them into BERT to produce significantly better results than the median
score. In addition, they also experimented with Focal loss instead of binary
cross-entropy loss.

A new dataset for identifying informative tweet was released by Aggarwal
(2019). The results of various machine learning algorithms using GloVe
(Pennington et al., 2014) word embeddings, syntactic information in the form
of tf-idf vectors and BERT embeddings were also presented in the work.

Due to the abundance of tweets related to COVID-19, many works have been done
to analyze the content, intent and effect of such tweets. Singh et al. (2020)
presented an analysis of COVID-19 tweets on the grounds of location, content
and misinformation spread. A comprehensive study about the content of
misinformative COVID-19 tweets and other aspects associated with them have
been done by Shahi et al. (2020).

##  3 Dataset

The dataset (Nguyen et al., 2020) provided to the participants of the shared
task contains 10,000 English COVID-19 tweets, out of which 4719 are labeled as
INFORMATIVE and 5281 are labeled as UNINFORMATIVE. The tweets were annotated
by 3 independent annotators and an inter-annotator agreement score of Fleiss’
Kappa at 0.818 was obtained. The dataset contains the tweet ID, the tweet and
the corresponding label.

##  4 Data Preprocessing

Twitter data contains a lot of noise. Therefore, preprocessing on Twitter data
will help the pretrained models in better performance. We perform the
following data preprocessing steps, most of which have been inspired from
Müller et al. (2020) :

  1. 1.

Unescape HTML tags

  2. 2.

Remove unnecessary spaces, tabs and newlines

  3. 3.

Replacing the the mentioned hyperlinks in the tweets (depicted as HTTPURL),
with URL. A simple explanation for this could be that “URL” is a more commonly
used expression of hyperlinks than HTTPURL.

  4. 4.

Using the Python emoji 222https://pypi.org/project/emoji/ library to demojise
the emojis i.e. replace them with a short textual description.

The user handles were already replaced by @USER in the tweets, hence no
processing was required.

##  5 Models

We experiment with the following models and techniques:

  1. 1.

COVID-Twitter-BERT: BERT is based on the Transformer architecture Vaswani et
al. (2017). It consists of multi-attention heads which apply a sequence-to-
sequence transformation on the input text sequence. For its training, BERT
makes use of the following objectives: (a) learn to predict a masked token
using the left and right context of the text sequence (Masked Language Model)
(b) learn to predict whether two sentences occur in continuation or not (Next
Sentence Prediction)

Müller et al. (2020) pretrain the large version of BERT (BERT-Large) on
COVID-19 related tweets posted by users between January 12 and April 16, 2020.
This version of BERT has a better understanding of the given data as compared
to BERT-large, which is pretrained on texts from Wikipedia. Hence, COVID-
Twitter-BERT will be even more beneficial for the task when fine tuned.

  2. 2.

RoBERTa Large: RoBERTa has the same architecture as BERT, but is different
from BERT on the grounds of pretraining, which helps in better optimisation
and performance. RoBERTa is pretrained on a larger dataset as compared to
BERT, uses a larger batch size and replaces the Next Sentence Prediction
objective. It also uses dynamic masking pattern as a better alternative to the
static masking pattern used in BERT, i.e. RoBERTa duplicates the data and
masks those differently each time, whereas BERT will mask the data only once.

  3. 3.

Adversarial Training: With time, adversarial training is gaining popularity in
Natural Language Processing (NLP) as well. In the field of Computer Vision,
adversarial training is done by perturbing the input images slightly and
minimising the adversarial loss. In NLP, the nature of input being discrete,
small perturbations are done on the word embeddings. Adversarial training not
only increases the robustness of models but also helps in better
generalisation. Both properties are beneficial and desirable for
identification of informative tweets.

Although many approaches for adversarial training in NLP have been developed,
we experiment with the approach proposed by Miyato et al. (2016) with a slight
modification. In their approach, first the word embeddings are normalized. The
gradients are then computed using the data and the required perturbations are
created using the obtained gradients.

Let the sequence of (normalized) word embedding vectors of a text be $t$. The
model parameters are represented by $\theta$. The probability of the text
belonging to class $y$ is given by $p(y|\bm{t;\theta})$. The adversarial
perturbations $\bm{z}_{adv}$ are computed as follows:

$\bm{g}=\nabla_{t}\>log\>p(y|\bm{t;\theta})$

$\bm{z}_{adv}=-\epsilon\bm{g}/\\!\parallel\bm{g}\\!\parallel_{2}$

where $\epsilon$ is a hyper-parameter controlling the size of the
perturbations. The adversarial loss is defined as :

$\bm{L}_{adv}(\bm{\theta})=-\frac{1}{N}\sum_{n=1}^{N}log\>p(y_{n}|\bm{t}_{n}+\bm{z}_{adv,n};\bm{\theta})$

By using the gradients calculated from the above loss, the weights of the
model are updated (the non-perturbed word embeddings of the model are
updated). The slight modification in our experiments is that we do not
normalize our pretrained word embedding of the model, since it might change
the semantic meaning of the pretrained word embeddings. We perform adversarial
training on both COVID-Twitter-BERT and RoBERTa Large models using
$\epsilon=1$ .

  4. 4.

Ensembling: The ensembling of the predictions for our submissions is done at
two levels-

    1. (a)

Fold level i.e. the predictions obtained by the models trained using the
different folds (during cross validation) are averaged.

    2. (b)

Model level i.e. the fold level averaged predictions of the two different
models are ensembled using averaging.

##  6 Experimental Settings

We concatenate the training and the validation data and perform a 5-fold
stratified cross validation to train our models. Each fold is trained for 5
epochs using early stopping with patience of 3 and tolerance of 1e-3. The
models are optimised using AdamW (Loshchilov and Hutter, 2017) with a learning
rate of 2e-5 and a batch size of 16. The models have been implemented using
Pytorch (Paszke et al., 2019) and Huggingface’s Transformers (Wolf et al.,
2019) library.

##  7 Results

We evaluate the performance of the models and their ensemble using cross-
validation (CV). We also tabulate the models’ performance on the test set as
evaluated by the F1 score on the positive class.

The ensembling done at two levels increases the robustness of the results. The
out-of-folds predictions were used to find the optimal threshold of the
submissions, 0.498 for the ensemble without adversarial training and 0.487 for
the ensemble with adversarial training. We also compare our results with the
fastText-baseline (Joulin et al., 2016) by the organizers. Table 1 shows the
results of our experiments.

Tweet | Label
---|---
Election Judge Hospitalized After Primary Dies Of Coronavirus #RIP #SemperFi fought for his life while @USER got her hair done #LetThatSinkIn “face of Chicago” thinks she’s more important than Chicagoans welfare #LightfootLiedPeopleDied HTTPURL | UNINFORMATIVE
Austin area nursing home residents who test positive for COVID-19 but do not need to be in the hospital will soon be moving to one of two new “isolation facilities,” one in Travis County, one in Williamson County: HTTPURL @USER | INFORMATIVE
LOCAL NEWS SHOUTOUT: Have a family member or close friend with a Michigan connection who has died from COVID-19 and would like to share their story with @USER Please contact Georgea Kovanis at gkovanis@USER | INFORMATIVE
BREAKING: Southern AB #coronavirus case rumored to be Steve Busey, the younger brother of movie star @USER According to our sources, Steve works in the oil & gas industry and is a huge @USER fan. #COVIDー19  HTTPURL | UNINFORMATIVE
Table 2:  Some common highly misclassified samples. Model | CV | Test
---|---|---
Baseline - fastText | - | 0.7503
COVID-Twitter-BERT | 0.9622 | -
RoBERTa Large | 0.9560 | -
COVID-Twitter-BERT Adv. | 0.9632 | -
RoBERTa Large Adv. | 0.9578 | -
COVID-Twitter-BERT + RoBERTa Large | 0.9636 | 0.9096
COVID-Twitter-BERT Adv. + RoBERTa Large Adv. | 0.9655 | 0.9082
Table 1:  Comparison of results.

The ensemble of COVID-Twitter-BERT and RoBERTa Large performs the best on the
test data and also obtains the 1 rank on the leaderboard. Owing to its
pretraining, COVID-Twitter-BERT performs better than RoBERTa Large. The
adversarial training of the models is also found to boost the scores. The
ensemble of adversarial models produces results similar to the ensemble of
models trained without adversarial training.

##  8 Analysis

We perform our analysis on the out-of-folds predictions from our two ensembles
- without adversarial training and with adversarial training.

We calculate the binary cross entropy loss for all samples and then examine
some of the top common mis-classifications by both the ensembles ( Table 2).

We observe that there are instances where our models are mistaken. A possible
reason might be the variance in gold-labels of samples from annotator-to-
annotator. This acts as noise in the labels of the data which is used to train
the normal ensemble models. On the other hand, adversarial training adds some
noise to the samples. Hence, the models in the adversarial ensemble have been
trained on data which has a combination of existing noise and externally added
noise. We believe that because of this difference in noise, the models in the
two ensembles must be behaving in different ways. To inspect this, we examine
the number of samples which have been inferred incorrectly by one ensemble and
correctly by the other.

We observe that the normal ensemble misclassified a total of 277 samples
whereas, only 260 samples were misclassified by the adversarial ensemble.
Moreover, out of the 277 examples that were misclassified by the normal
ensemble, 102 were correctly predicted by the adversarial ensemble. On the
other hand, only 85 out of the 260 samples misclassified by the adversarial
ensemble, were correctly predicted by the normal ensemble. Thus, it is evident
that the models in both the ensembles have learnt different patterns from the
data.

##  9 Conclusion

We explored the performance of COVID-Twitter-BERT and RoBERTa-Large at
identifying COVID-19 English tweets that are informative in nature. Their
ensemble achieves the state-of-the-art performance. Adversarial training is
found to improve our model further. For future work, we can pretrain other
Transformer-based models on COVID-19 tweets. Data augmentation techniques can
help us generate more data for training models. We can also experiment with
combining models trained with and without adversarial training.

## Acknowledgments

We thank Google Colab for providing free GPU services for experimentation
purposes.

## References

  * Aggarwal (2019) Piush Aggarwal. 2019.  Classification approaches to identify informative tweets.  In _Proceedings of the Student Research Workshop Associated with RANLP 2019_ , pages 7–15.
  * Devlin et al. (2018) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2018.  Bert: Pre-training of deep bidirectional transformers for language understanding.  _arXiv preprint arXiv:1810.04805_.
  * Joulin et al. (2016) Armand Joulin, Edouard Grave, Piotr Bojanowski, and Tomas Mikolov. 2016.  Bag of tricks for efficient text classification.  _arXiv preprint arXiv:1607.01759_.
  * Lamsal (2020) R Lamsal. 2020.  Corona virus (covid-19) tweets dataset.  _IEEE Dataport_.
  * Liu et al. (2019) Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. 2019.  Roberta: A robustly optimized bert pretraining approach.  _arXiv preprint arXiv:1907.11692_.
  * Loshchilov and Hutter (2017) Ilya Loshchilov and Frank Hutter. 2017.  Fixing weight decay regularization in adam.  _CoRR_ , abs/1711.05101.
  * Madichetty and Sridevi (2020) Sreenivasulu Madichetty and M Sridevi. 2020.  Classifying informative and non-informative tweets from the twitter by adapting image features during disaster.  _Multimedia Tools and Applications_ , pages 1–23.
  * Miyato et al. (2016) Takeru Miyato, Andrew M Dai, and Ian Goodfellow. 2016.  Adversarial training methods for semi-supervised text classification.  _arXiv preprint arXiv:1605.07725_.
  * Müller et al. (2020) Martin Müller, Marcel Salathé, and Per E Kummervold. 2020.  Covid-twitter-bert: A natural language processing model to analyse covid-19 content on twitter.  _arXiv preprint arXiv:2005.07503_.
  * Neppalli et al. (2018) Venkata Kishore Neppalli, Cornelia Caragea, and Doina Caragea. 2018.  Deep neural networks versus naive bayes classifiers for identifying informative tweets during disasters.  In _ISCRAM_.
  * Nguyen et al. (2020) Dat Quoc Nguyen, Thanh Vu, Afshin Rahimi, Mai Hoang Dao, Linh The Nguyen, and Long Doan. 2020.  WNUT-2020 Task 2: Identification of Informative COVID-19 English Tweets.  In _Proceedings of the 6th Workshop on Noisy User-generated Text_.
  * Paszke et al. (2019) Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. 2019\.  Pytorch: An imperative style, high-performance deep learning library.  In _Advances in neural information processing systems_ , pages 8026–8037.
  * Pennington et al. (2014) Jeffrey Pennington, Richard Socher, and Christopher D Manning. 2014.  Glove: Global vectors for word representation.  In _Proceedings of the 2014 conference on empirical methods in natural language processing (EMNLP)_ , pages 1532–1543.
  * Roy et al. (2020) Sujoy Roy, Sumit Mishra, and Rakesh Matam. 2020.  Classification and summarization for informative tweets.  In _2020 IEEE International Students’ Conference on Electrical, Electronics and Computer Science (SCEECS)_ , pages 1–4. IEEE.
  * Shahi et al. (2020) Gautam Kishore Shahi, Anne Dirkson, and Tim A Majchrzak. 2020.  An exploratory study of covid-19 misinformation on twitter.  _arXiv preprint arXiv:2005.05710_.
  * Singh et al. (2020) Lisa Singh, Shweta Bansal, Leticia Bode, Ceren Budak, Guangqing Chi, Kornraphop Kawintiranon, Colton Padden, Rebecca Vanarsdall, Emily Vraga, and Yanchen Wang. 2020.  A first look at covid-19 information and misinformation sharing on twitter.  _arXiv preprint arXiv:2003.13907_.
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. 2017.  Attention is all you need.  In _Advances in neural information processing systems_ , pages 5998–6008.
  * Wolf et al. (2019) Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Rémi Louf, Morgan Funtowicz, et al. 2019.  Transformers: State-of-the-art natural language processing.  _arXiv preprint arXiv:1910.03771_.
  * Zahera et al. (2019) Hamada M Zahera, Ibrahim A Elgendy, Rricha Jalota, and Mohamed Ahmed Sherif. 2019\.  Fine-tuned bert model for multi-label tweets classification.  In _TREC_.


# A Structure Theorem for Bad 3-Orbifolds

R. Lehman  and  Yo’av Rieck  Dept. of Mathematics
University of Arkansas
Fayetteville, AR 72701<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract.

We explicitly construct a collection of bad 3-orbifolds, $\mathcal{X}$,
satisfying the following properties:

  1. (1)

The underlying topological space of any $X\in\mathcal{X}$ is homeomorphic to
$S^{2}\times I$ or $(S^{2}\times S^{1})\backslash B^{3}$.

  2. (2)

The boundary of any $X\in\mathcal{X}$ consists of one or two spherical
2-orbifolds.

  3. (3)

Any bad 3-orbifold is obtained from a good 3-orbifold by repeating, finitely
many times, the following operation: remove one or two orbifold-balls, and
glue in some $X\in\mathcal{X}$.

Conversely, any bad 3-orbifold $\mathcal{O}$ contains some $X\in\mathcal{X}$
as a sub-orbifold; we call removing $X$ and capping the resulting boundary
cut-and-cap. Then by cutting-and-capping finitely many times we obtain a good
orbifold.

C’est tellement mystérieux, le pays des larmes.

— Antoine De Saint-Exupery

##  1\. Introduction

Sometime around 1980 WP Thurston stated and sketched the proof of his
celebrated Orbifold Theorem, showing that if a 3-dimensional orbifold
$\mathcal{O}$ with non-empty singular set is good — covered by a manifold —
then $\mathcal{O}$ admits a decomposition into geometric pieces (for
definitions see Section 2, and for a discussion and proof see, for example,
[17], [1], [2], [6], [3]). The case of an empty singular set — manifolds — is
Thurston’s Geometrization Conjecture, proved by Perelman [12] [13] [14] (a
proof of the Orbifold Theorem along these lines can be found in [10]). These
theorems have been immensely influential and allowed the study of various
aspects of 3-dimensional topology by considering well-understood geometric
pieces and combining them. Discussion about 3-orbifolds can also be found in
[5] and [11]. In [4] the reader can find the classification of Seifert fibered
3-orbifolds.

By its very definition a bad orbifold cannot be constructed from geometric
pieces, and so the assumption that the orbifold is good cannot be removed. Our
goal in this paper is to present an explicit structure theorem for bad
orbifolds that allows their study by means of induction.

We now provide some more details about our strategy and results. Let
$\mathcal{O}$ be a closed, orientable (possibly bad) 3-orbifold. Thurston’s
Orbifold Theorem and Perelman’s Geometrization Theorem state that after
performing prime decomposition (decomposing $\mathcal{O}$ along spherical
2-orbifolds — 2-orbifolds covered by $S^{2}$) and then JSJ decomposition
(decomposing along certain toroidal 2-orbifolds — 2-orbifolds covered by the
2-torus) each of the pieces obtained, say $\mathcal{O}^{\prime}$, satisfies
exactly one of the following:

  1. (1)

$\mathcal{O}^{\prime}$ is geometric (the geometric quotient of one of
Thurston’s eight geometries), or

  2. (2)

$\mathcal{O}^{\prime}$ contains an embedded bad 2-orbifold.

Consequently $\mathcal{O}$ itself is bad if and only if it contains an
embedded bad 2-orbifold, which we can take to be either a teardrop or a bad-
football (see Proposition 2.2). Using this we show that if $\mathcal{O}$ is
bad, then it contains a compact 3-suborbifold, $X$, satisfying the following
properties:

  1. (1)

$X$ is a member of one of twelve explicitly constructed families,

  2. (2)

$X$ contains an embedded teardrop or bad-football,

  3. (3)

$\partial X$ consists of one or two spherical 2-orbifolds, and

  4. (4)

$X$ has underlying topological space $S^{2}\times I$ or $(S^{2}\times
S^{1})\backslash B^{3}$.

Let the process of removing $X$ from $\mathcal{O}$ and capping the resulting
boundary components by attaching a cone be called cutting and capping $X$.

The main result of this paper is:

######  Theorem 1.1.

Let $\mathcal{O}$ be a closed, orientable 3-orbifold. Then there exists
orbifolds $\mathcal{O}_{0},\mathcal{O}_{1},\dots,\mathcal{O}_{n+m}$ (for some
$n,m\geq 0$) so that $\mathcal{O}_{i}$ is obtained from $\mathcal{O}_{i-1}$ by
cutting and capping $X_{i}$, where:

  1. (1)

$\mathcal{O}=\mathcal{O}_{0}$,

  2. (2)

$(1\leq i\leq n)$ $X_{i}$ is listed in Theorem 16,

  3. (3)

$(n+1\leq i\leq n+m)$ $X_{i}$ is listed in Theorem 5.1,

  4. (4)

$\mathcal{O}_{n+m}$ is good.

In particular, the boundary of each $X_{i}$ consists of 1 or 2 spherical
2-orbifolds, and its underlying topological space is $S^{2}\times I$ or
$(S^{2}\times S^{1})\backslash B^{3}$.

Reversing the process of Theorem 1.1 gives us the following corollary.

######  Corollary 1.2.

Any closed, orientable 3-orbifold is obtained from some good 3-orbifold by a
repeating the following process finitely many times:

  1. (1)

Removing 1 or 2 orbifold 3-balls, and —

  2. (2)

Attaching a bad 3-orbifold listed in Theorem 5.1 or 16.

######  Remark 1.3.

A few comments are in order:

  1. (1)

The constructions in Theorems 5.1 and 16 are explicit and therefore Corollary
1.2 lends itself to the constructions of a variety of examples. We invite the
reader to do so.

  2. (2)

The reader is also invited to simplify our constructions. While doing so, keep
in mind that the constructions are designed so that the boundary of $X$ is
spherical. This is essential: it allows capping the boundary. This is, of
course, similar to prime decomposition of $3$-manifolds.

  3. (3)

Since $X$ may have 2 boundary components, it is possible that
$\mathcal{O}_{n+m}$ is disconnected even if $\mathcal{O}$ is connected.

Outline. The content of each section is summarized here:

Section 2:

Review of standard definitions, mostly to fix ideas.

Section 3:

A bound on the number of disjoint, pairwise non-parallel teardrops in
$\mathcal{O}$ (the analogous statement for bad-footballs is false, see Example
4.2).

Section 4:

A bound on the number of disjoint, pairwise non-parallel, bad-footballs in
$\mathcal{O}$ in the absence of teardrops.

Sections 5 and 6:

Classification of compact 3-suborbifolds needed for Theorem 1.1.

Section 7:

Proof of Theorem 1.1.

Acknowledgment. This project grew out of discussions with Michael McQuillan
and the authors are grateful for his insight and suggestions. The authors also
thank Daryl Cooper, Chaim Goodman–Strauss, and Neil Hoffman for helpful
correspondence and conversations. We are grateful to the referees for helpful
suggestions. Yo’av Rieck was partially supported by the Simons Foundation
through grant #637880.

##  2\. Preliminaries

We assume familiarity with the basic notions of 3-manifold topology (see, for
example, [8], [9] and [15]), including the basic definitions related to
orbifolds (see, for example, [6] or [1]). To fix ideas we summarize the main
definitions here. Most of the notation we use is standard, with $N$, $E$, and
$\partial$ denoting closed normal neighborhood, exterior, and boundary. We use
$|\mathcal{O}|$ to denote the underlying topological space of an orbifold
$\mathcal{O}$, and we use $\Sigma$ to denote its singular set. An $n$-orbifold
is called orientable if its underlying topological space is orientable and
locally it is given as the quotient of a finite group whose action on
$\mathbb{R}^{n}$ is orientation preserving. An orbifold is smooth if its
singular set is empty; $B^{3}$ is a smooth open $3$-ball.

$2$-orbifolds. Any 2-orbifold that we consider is assumed to be closed and
orientable (except in the proof of Proposition 2.2 where we are forced to
consider non-orientable 2-orbifolds). Any point $p$ in such a 2-orbifold has a
standard neighborhood that is either a smooth disk or a disk with a single
singular point, corresponding to $p$, of weight $a>1$ (by which we mean that
it is the quotient of a disk in $\mathbb{R}^{2}$ under the group generated by
a rotation by angle $2\pi/a$, where $a\geq 2$ is an integer). A teardrop,
$S^{2}(a)$, is a 2-orbifold with $|S^{2}(a)|\cong S^{2}$ (the smooth 2-sphere)
and exactly one singular point of weight $a>1$. A bad-football, $S^{2}(a,b)$,
is a $2$-orbifold with $|S^{2}(a,b)|\cong S^{2}$ and exactly two singular
points of unequal weights $a$ and $b$, where we assume $b>a>1$. It is well-
known that teardrops and bad-footballs are closed, orientable, bad
2-orbifolds.

A spherical 2-orbifold is a 2-orbifold that is covered by $S^{2}$ (not to be
confused with a 2-orbifold whose underlying topological space is $S^{2}$). A
closed spherical orbifold of the from $S^{2}(a_{1},a_{2},a_{3})$ must satisfy:

$\frac{1}{a_{1}}+\frac{1}{a_{2}}+\frac{1}{a_{3}}>1$

This inequality allows us to list all the spherical $2$-orbifolds:

  * •

$S^{2}$

  * •

$S^{2}(a,a)$ for any $a\geq 2$

  * •

$S^{2}(2,2,a)$ for any $a\geq 2$

  * •

$S^{2}(2,3,3)$, $S^{2}(2,3,4)$, and $S^{2}(2,3,5)$

A toroidal 2-orbifold is a 2-orbifold that is covered by the 2-torus (for
example, $S^{2}(3,3,3)$ is toroidal and is not spherical).

$3$-orbifolds. By an orbifold we mean a compact, orientable $3$-orbifold. Any
point $p$ in the interior of an orbifold has a standard neighborhood which is
a cone on a closed spherical 2-orbifold; hence its underlying topological
space is a closed 3-ball and (by the classification of finite group actions on
$S^{2}$) its singular set is one of the following:

  * •

Empty.

  * •

A single unknotted arc, containing $p$, of weight $a>1$.

  * •

Exactly three arcs, each connecting the boundary to $p$, so that the union of
any two of these arcs is an unknotted arc. The weights of the arcs (say
$a_{1}$, $a_{2}$, and $a_{3}>1$) satisfy

$\frac{1}{a_{1}}+\frac{1}{a_{2}}+\frac{1}{a_{3}}>1$

We observe that each component of the singular set of a closed orbifold has
one of the following forms:

  * •

A smooth simple closed curve (here “smooth” means “contains no vertex”).

  * •

A trivalent graph, and in particular, the graph has no leaves (valence one
vertices).

To clarify our usage of the term edge we define it here:

######  Definition 2.1 (edge).

By an edge of $\Sigma$ we mean either a smooth simple closed curve, or an edge
ending in two vertices, which may or may not be distinct.

The following proposition is an application of Thurston’s Orbifold Theorem
that allows us to avoid disks with corner lines and corner reflectors:111We
refer the reader to [16, page 408] for the definition of corner lines and
corner reflectors; in light of Proposition 2.2, they will not be considered in
this paper beyond the proof of the proposition.

######  Proposition 2.2.

A closed, orientable, bad 3-orbifold admits an embedded teardrop or bad-
football.

###### Proof.

Let $\mathcal{O}$ be a closed orientable bad 3-orbifold. Thurston’s Orbifold
Theorem implies that $\mathcal{O}$ admits an embedded, closed, connected, bad
2-suborbifold, say $S$.

It follows from [16, Theorem 2.3, page 425] that $S$ is one of the
following:222The notation used in [16] is $D^{2}(a)$ and $D^{2}(a,b)$, but we
will use the notation $\widehat{D}^{2}(a)$ and $\widehat{D}^{2}(a,b)$ instead
to avoid conflicts with the notation used below.

  1. (1)

$S=S^{2}(a)$ with $a>1$,

  2. (2)

$S=S^{2}(a,b)$ with $b>a>1$,

  3. (3)

$S=\widehat{D}^{2}(a)$, where the weight of the corner reflector is $a>1$, or

  4. (4)

$S=\widehat{D}^{2}(a,b)$, where the weights of the corner reflectors are
$b>a>1$.

If $S=S^{2}(a)$ or $S^{2}(a,b)$ we are done. Suppose that
$S=\widehat{D}^{2}(a)$ or $\widehat{D}^{2}(a,b)$, see Figure 1 where $S$ is
shaded. $S$ admits a neighborhood $U$ with $|U|\cong B^{3}$, and since the
corner reflector points of $S$ have valence three, $\Sigma\cap\partial U$ is
either in one point of weight $a>1$ (corresponding to case 3) or two points of
weights $b>a>1$ (corresponding to case 4). Thus $\partial U$ is either a
teardrop or a bad-football.

Figure 1. Figure for Proposition 2.2

∎

In the next three lemmas we study the local picture near $\Sigma$, the
singular set of a closed orbifold. Note that every component $V$ of
$|N(\Sigma)|$ is a handlebody with the $|\Sigma|\cap V$ its core. In
particular, $V$ is irreducible.

######  Lemma 2.3.

If $B\subset N(\Sigma)$, where $|B|$ is a closed 3-ball, then every component
of $\Sigma\cap B$ is a tree and all its leaves are on the boundary.

###### Proof.

First assume, for a contradiction, that $\Sigma\cap B$ contains a cycle, say
$c$. Then $\pi_{1}(|c|)\not\hookrightarrow\pi_{1}(|B|)$ as $|B|$ is simply
connected, which is a contradiction as $|c|$ represents a nontrivial element
of $\pi_{1}(|\Sigma|)$ and $\pi_{1}(|\Sigma|)$ injects into
$\pi_{1}(|N(\Sigma)|)$. This shows that every component of $\Sigma\cap B$ is a
tree.

No leaf of $\Sigma\cap B$ can be in the interior of $B$ since $\Sigma$ has no
vertex of valence one. ∎

Consequently:

######  Lemma 2.4.

$N(\Sigma)$ admits no bad orbifolds.

###### Proof.

Let $S\subset N(\Sigma)$ be an embedded 2-orbifold with $|S|$ a 2-sphere and
$S\cap\Sigma$ one or two points. Any bad 2-orbifold in $N(\Sigma)$ certainly
satisfies these conditions. Irreducibility of $|N(\Sigma)|$ implies that $|S|$
bounds a closed ball $|B|\subset|N(\Sigma)|$. By Lemma 2.3, $\Sigma\cap B$
consists of trees with their leaves on the boundary. Since every tree has at
least two leaves, we have that $S\cap\Sigma$ consists of exactly two points.
The only tree with exactly two leaves is a single arc, implying that the two
singular points on $S$ have the same weight, so $S$ is a good football. ∎

And for footballs in $V$ we have:

######  Lemma 2.5.

Any football $F\subset N(\Sigma)$ bounds an orbifold isomorphic to
$D^{2}(a)\times I$ (where $D^{2}$ is a 2-disk and $a>1$).

###### Proof.

$F$ is a good football by Lemma 2.4; in the proof of that lemma we observed
that $F$ bounds $B$, where $|B|$ is a closed ball and $\Sigma\cap B$ is a
single arc. Since the core of a handlebody is locally unknotted, we have that
this arc is unknotted which gives the desired product structure. ∎

We conclude this section with the following simple lemma:

######  Lemma 2.6.

Let $a_{1}^{*},a_{2},$ and $a_{3}$ be the weights of three edges of $\Sigma$
that meet at a vertex of $\Sigma$. If $a_{1}^{*}\geq a_{1}$ then
$S^{2}(a_{1},a_{2},a_{3})$ is a spherical 2-orbifold.

###### Proof.

The weights of edges meeting at a vertex satisfy
$\frac{1}{a_{1}^{*}}+\frac{1}{a_{2}}+\frac{1}{a_{3}}>1$. By assumption
$a_{1}^{*}\geq a_{1}$, and thus
$\frac{1}{a_{1}}+\frac{1}{a_{2}}+\frac{1}{a_{3}}\geq\frac{1}{a_{1}^{*}}+\frac{1}{a_{2}}+\frac{1}{a_{3}}>1$.
Hence $S^{2}(a_{1},a_{2},a_{3})$ is a spherical 2-orbifold. ∎

##  3\. A Bound on the Number of Teardrops

By Proposition 2.2 we have that an orbifold $\mathcal{O}$ is bad if and only
if it contains an embedded teardrop or bad-football. As our goal is to remove
all bad components from $\mathcal{O}$ we must first know that there exists a
bound on their number, starting with teardrops:

######  Theorem 3.1 (finiteness of teardrops).

Given a closed, orientable 3-orbifold, there exists a bound on the number of
disjointly embedded, pairwise non-parallel teardrops.

For a teardrop $T$, we consider $T\cap N(\Sigma)$ and $T\cap E(\Sigma)$
(recall that $E(\Sigma)$ is the exterior of the singular set). We first
prepare two lemmas:

######  Lemma 3.2.

Let $T\subset\mathcal{O}$ be a teardrop. Then $T\cap E(\Sigma)$ is an
essential disk in $E(\Sigma)$.

###### Proof.

Obviously, $T\cap N(\Sigma)$ is a disk that intersects $\Sigma$ in a single
point. Since $|N(\Sigma)|$ consists of handlebodies for which $|\Sigma|$ are
cores, we have that $T\cap\partial E(\Sigma)$ is essential in $\partial
E(\Sigma)$; the lemma follows. ∎

######  Lemma 3.3.

Let $T_{1}$ and $T_{2}$ be teardrops disjointly embedded in $\mathcal{O}$. If
$T_{1}\cap E(\Sigma)$ and $T_{2}\cap E(\Sigma)$ are parallel in $E(\Sigma)$,
then $T_{1}$ and $T_{2}$ are parallel in $\mathcal{O}$.

###### Proof.

Suppose that $T_{1}\cap E(\Sigma)$ and $T_{2}\cap E(\Sigma)$ are parallel in
$E(\Sigma)$. Then, in particular, $\partial(T_{1}\cap E(\Sigma))$ and
$\partial(T_{2}\cap E(\Sigma))$ co-bound an annulus $A\subset\partial
N(\Sigma)$. Then $\left(T_{1}\cap N(\Sigma)\right)\cup A\cup\left(T_{2}\cap
N(\Sigma)\right)$ is a football in $N(\Sigma)$ and bounds a product region by
Lemma 2.5 which, together with the product region between $T_{1}\cap
E(\Sigma)$ and $T_{2}\cap E(\Sigma)$ in $E(\Sigma)$, shows that $T_{1}$ and
$T_{2}$ are parallel. ∎

###### Proof of Theorem 3.1.

By Lemmas 3.2 and 3.3 the intersection of a family of disjoint, pairwise non-
parallel teardrops with $E(\Sigma)$ forms a family of disjoint, pairwise non-
parallel, essential disks in $E(\Sigma)$, whose number is bounded by
Kneser–Haken finiteness. ∎

##  4\. A Bound on the Number of Bad-Footballs

Having bounded the number of teardrops we now turn our attention to bad-
footballs; to that end we place a restriction on teardrops:

######  Theorem 4.1 (Finiteness of bad-footballs).

Let $\mathcal{O}$ be a closed orientable orbifold, and suppose that no
component of $\mathcal{O}$ admits disjointly embedded teardrops of distinct
weights. Then there is a bound on the number of disjointly embedded, pairwise
non-isotopic, bad-footballs.

######  Example 4.2.

Let $\mathcal{O}$ be a connected 3-orbifold that admits two disjointly
embedded teardrops, $S^{2}(a)$ and $S^{2}(b)$, with $a\neq b$. Tubing the two
together in $E(\Sigma)$ we obtain a bad-football that compresses down to
$S^{2}(a)$ and $S^{2}(b)$ (see Figure 2, where $D$ is a compressing disk for
the tube). We can tube $S^{2}(a)$ and $S^{2}(b)$ again, using a knotted tube
nested inside the first tube. Repeating this process (see Figure 3) we obtain
arbitrarily many disjointly embedded, pairwise non-isotopic bad-footballs.
Thus the assumptions of Theorem 4.1 cannot be removed.

Figure 2. The bad-football containing a compression disc.

Figure 3. We may obtain an unbounded sequence of non-parallel, compressible
bad-footballs.

In contrast to the case of teardrops (Lemma 3.2), a bad-football may not give
rise to an essential annulus in $E(\Sigma)$ (as it may boundary compress). We
prepare three lemmas for the proof of Theorem 4.1. In these lemmas, $F,F_{1}$
and $F_{2}$ are disjointly embedded bad-footballs, and we set $A=F\cap
E(\Sigma)$, $A_{1}=F_{1}\cap E(\Sigma)$ and $A_{2}=F_{2}\cap E(\Sigma)$.

######  Lemma 4.3.

The annulus $A$ is not boundary parallel in $E(\Sigma)$, and $\partial A$ is
essential in $\partial N(\Sigma)$.

###### Proof.

Lemma 2.4 implies that $A$ is not boundary parallel, and since each of its
boundary components bounds a disk of $F\cap N(\Sigma)$ that intersects
$\Sigma$ once, both are essential in $\partial N(\Sigma)$. ∎

######  Lemma 4.4.

If $A_{1}$ and $A_{2}$ are parallel in $E(\Sigma)$, then $F_{1}$ and $F_{2}$
are parallel in $\mathcal{O}$.

###### Proof.

Suppose $A_{1}$ and $A_{2}$ co-bound the region $A_{1}\times[0,1]$ in
$E(\Sigma)$, and let $\mathcal{O}^{\prime}$ be the component of $\mathcal{O}$
cut open along $F_{1}\cup F_{2}$ containing $A_{1}\times[0,1]$. Then
$\partial(\mathcal{O}^{\prime}\cap N(\Sigma))$ consists of two bad footballs,
and each bounds a product region by Lemma 2.5. These product regions, together
with $A_{1}\times[0,1]$, show that $\mathcal{O}^{\prime}$ is a product region
between $F_{1}$ and $F_{2}$. ∎

The annuli discussed above are not necessarily essential, but we do have:

######  Lemma 4.5.

Suppose that no component of $\mathcal{O}$ admits disjointly embedded
teardrops of distinct weights. Then $F\cap E(\Sigma)$ is incompressible.

###### Proof.

This is clear, since compressing $F\cap E(\Sigma)$ would yield disjointly
embedded teardrops of weights $a$ and $b$, which are distinct as $F$ is bad. ∎

###### Proof of Theorem 4.1.

By Lemmas 4.3, 4.4, and 4.5 (whose conditions are satisfied by assumption) the
intersection of a family of disjoint, pairwise non-parallel bad-footballs with
$E(\Sigma)$ forms a family of disjoint, pairwise non-parallel, non-boundary
parallel, incompressible annuli whose number is bounded by [7]. ∎

##  5\. Local Pictures about a Bad-Football

Although Theorem 1.1 requires us to deal with teardrops first, we start with
bad-footballs as the discussion is simpler. In Theorem 5.1 we will discover
three families of compact 3-orbifolds that satisfy the requirements of Theorem
1.1. The very detailed treatment is meant to serve as a warm-up for the more
complicated Theorem 6.2.

######  Theorem 5.1 (Local Pictures about a Bad-Football).

Let $\mathcal{O}$ be a closed, orientable 3-orbifold and $F\subset\mathcal{O}$
an embedded bad-football. Then there exists a compact 3-suborbifold $X$ with
$F\subset X\subset\mathcal{O}$ satisfying the following properties (here,
$B^{3}$ is the interior of an embedded smooth closed ball):

  1. (1)

the underlying topological space of $X$ is either:

    1. (a)

$|X|\cong S^{2}\times I$ (corresponding to Form $1$), or

    2. (b)

$|X|\cong(S^{2}\times S^{1})\backslash B^{3}$ (corresponding to Form $2$ or
Smooth Form below),

  2. (2)

$\partial X$ consists of one or two spherical 2-orbifolds,

  3. (3)

the orbifold structure is one of the forms listed in Figures 4–6 below.

Figure 4. Smooth Form

Figure 5. Form 1

Figure 6. Form 2

###### Proof.

A flow chart for the proof of this theorem can be found in Figure 7.

Figure 7. The flowchart diagraming the proof of Theorem 5.1

Suppose that $F\cong S^{2}(a,b)$ with $b>a$. Let $e$ and $f$ be the edges of
the singular set $\Sigma$ that intersect $F$ whose weights are $b$ and $a$
respectively (so $e$ is heavier than $f$).

######  Case 1.

$\boldsymbol{e}$ or $\boldsymbol{f}$ is smooth: See Figure 4. We set $X$ to be
$N\left(S^{2}(a,b)\cup e\right)$ if $e$ is smooth and $N\left(S^{2}(a,b)\cup
f\right)$ if $f$ is smooth and $e$ is not; choosing $e$ when both are smooth
is not necessary but does make our construction of $X$ canonical. Clearly,
$|X|\cong\left(S^{2}\times S^{1}\right)\backslash B^{3}$ and $\partial
X=S^{2}(a,a)$ if $e$ is smooth and $S^{2}(b,b)$ otherwise. Thus $\partial X$
is a single good-football (which is spherical). This is the Smooth Form.

We assume from now on that neither $e$ nor $f$ is smooth. To organize the
remaining cases we construct the tree $\chi$ and the map
$\omega:\chi\to\Sigma$; this is more than we need for dealing with bad-
footballs but serves to prepare the reader for Theorem 6.2. (It may be helpful
to note that $\chi$ is a subspace of the universal cover of a component of
$\Sigma$ and $\omega$ is the restriction of the covering projection.)

Construction of $\boldsymbol{\chi}$ and $\boldsymbol{\omega}$. Let $\chi$ be
the tree that consists of the six vertices and the five edges as shown in
Figure 8. Next we construct a map $\omega:\chi\to\Sigma$; $\omega$ is required
to map the interior of every edge of $\chi$ homeomorphically onto the interior
of an edge of $\Sigma$. We first map $e^{\prime}$ to $e$ (with either
orientation); this can be done since $e$ is not smooth. We then extend the map
to $e_{+}^{\prime}$ and $\overline{e}_{+}^{\prime}$, mapping them to edges
adjacent to $\omega(v_{+}^{\prime})$ in such a way that $\omega$ is locally
injective; this can be done because the valence of the vertices of $\Sigma$ is
three. We similarly extend $\omega$ to $e_{-}^{\prime}$ and
$\overline{e}_{-}^{\prime}$, obtaining $\omega:\chi\to\Sigma$ that is locally
injective although it may well fail to be injective. We denote images under
$\omega$ by dropping the primes, for example, $\omega(v_{+}^{\prime})=v_{+}$
(thus, for example, when $e$ forms a simple closed curve we have that
$v_{+}=v_{-}$ although $v_{+}^{\prime}\not=v_{-}^{\prime}$).

Figure 8. The tree $\chi$

######  Remark 5.2.

Since $\omega$ is locally injective, whenever the restriction of $\omega$ to a
sub-tree $K\subset\chi$ is injective, we have that
$\omega|_{N(K)}:N(K)\to\Sigma$ is injective as well, where here $N(K)$ is a
sufficiently small normal neighborhood of $K$. This requires only local
injectivity of $\chi$ and compactness of $K$ and will also hold for $\chi$ and
$\omega$ constructed in the proof of Theorem 6.2.

Having constructed $\chi$ and $\omega$ we now return to the proof of Theorem
5.1 (under the assumption that $e$ and $f$ are not smooth).

######  Case 2.

$\boldsymbol{v_{+}\neq v_{-}}$. See Figure 5, where $e$ is the bottom edge. We
set $X\subset\mathcal{O}$ to be $N\left(F\cup e\right)$. The assumption that
$v_{+}\neq v_{-}$ implies that $\omega$ embeds $N(e^{\prime})$ into $\Sigma$
(recall Remark 5.2), and hence $|X|\cong S^{2}\times I$. Next we show that the
boundary component near $v_{-}$ is spherical. Let $b$, $a_{2}$ and $a_{3}$ be
the weights of the edges adjacent to $v_{-}$ (recall that $b$ is the weight of
$e$). Then the component of $\partial X$ near $v_{-}$ is isomorphic to
$S^{2}(a,a_{2},a_{3})$. Since $b$, $a_{2}$ and $a_{3}$ are the weights at a
vertex and $b>a$, by Lemma 2.6 we have that $S^{2}(a,a_{2},a_{3})$ is
spherical. Similarly, the component of $\partial X$ near $v_{+}$ (denoted
$S^{2}(a,a_{2}^{\prime},a_{3}^{\prime})$ in the Figure 5) is spherical as
well. This is Form 1.

We have reduced the proof to the case where neither $e$ nor $f$ is smooth and
—

######  Case 3.

$\boldsymbol{v_{+}=v_{-}}$. See Figure 6, where $e$ is the bottom edge. The
assumption $v_{+}=v_{-}$ implies that $e$ forms a simple closed curve that
contains exactly one vertex $v=v_{+}=v_{-}$. We set $X$ to be $N\left(F\cup
e\right)$. Similar to the Smooth Form, we clearly see that
$|X|\cong\left(S^{2}\times S^{1}\right)\backslash B^{3}$.

It remains to show that $\partial X$ is spherical. Let $a^{*}$ denote the
weight of the edge connected to $e$ at $v$. Clearly, $\partial X\cong
S^{2}(a,a,a^{*})$. The weights at vertex $v$ are $b,b,a^{*}$ and satisfy

$\frac{1}{b}+\frac{1}{b}+\frac{1}{a^{*}}>1$ (1)

This forces $b<4$; moreover, as $b>a>1$, we have that $b=3$ and $a=2$.
Equation (1) (together with $b=3$) forces $a^{*}=2$, and we conclude that

$\partial X\cong S^{2}(a,a,a^{*})\cong S^{2}(2,2,2)$

which is indeed spherical as required. This is Form 2.

This completes the proof of Theorem 5.1. ∎

######  Remark 5.3.

We could have set things up differently. For example, the assumption in Case 1
could have been $e$ is smooth, since smoothness of $f$ was not used in cases
(2) and (3). We chose the specific structure (as reflected in the flowchart in
Figure 7) to get a canonical construction and a streamlined proof, but other
(equally canonical) choices are available.

##  6\. Local Pictures about a Teardrop

In Theorem 16 we will show that every embedded teardrop in a closed,
orientable 3-orbifold is contained in a compact 3-suborbifold satisfying the
requirement of Theorem 1.1. Before we delve into the intricacies of this
theorem and its proof let us see the construction in an explicit example:

Figure 9. $X=N\left(\text{left}\right)\cup N\left(S^{2}(3)\right)\cup
N\left(\text{right}\right)$

######  Example 6.1.

For this example see Figure 9. Let $T\subset\mathcal{O}$ be a teardrop in a
closed orientable orbifold, $T\cong S^{2}(3)$, and let $e$ be the edge of
$\Sigma$ that intersects $S^{2}(3)$ (thus the weight of $e$ is 3). In our
example the endpoints of $e$ are distinct, say $v_{+}\neq v_{-}$. We begin the
construction of $X$ with $N\left(S^{2}(3)\right)\cong S^{2}(3)\times I$. Next
we travel to the right of $N\left(S^{2}(3)\right)$ along $e$ until we reach
$v_{+}$, where $\Sigma$ branches out into two edges weights $2$ and $4$. We
continue to travel along the heavier edge, of weight $4$, until we meet
another vertex (denoted $v_{++}$ in the construction below) which branches out
into two edges of weights $2$ and $3$. Then we consider a normal neighborhood
of the path traveled which we denote by $N(\text{right})$ (green in Figure 9).
Next, we travel to the left of $N\left(S^{2}(3)\right)$ along $e$ until we
reach $v_{-}$, where $\Sigma$ branches out into two edges of the same weight,
$2$. Again we consider a normal neighborhood of the path traveled which we
denote by $N(\text{left})$. We set $X$ to be $N(\text{left})\cup
N\left(S^{2}(3)\right)\cup N(\text{right})$ ($X$ is an explicit example of
Form 2 from Theorem 16). Note that $|X|\cong S^{2}\times I$ and $\partial X$
consisits of two components, isomorphic to $S^{2}(2,2)$ and $S^{2}(2,2,3)$,
which are both spherical 2-orbifolds.

The reader may question our choices, in particular when traveling right:

  * •

If we stopped at $v_{+}$ we would get $S^{2}(2,4)$ as a boundary component.

  * •

If we continued past $v_{+}$ along the lighter edge (of weight $2$) past a
vertex with weights, say, $2,a,b$, we would get a boundary component
$S^{2}(4,a,b)$.

This is a problem: $S^{2}(2,4)$ is not spherical, and it is distinctly
possible (depending on $a,b$) that $S^{2}(4,a,b)$ is not spherical. As
discussed in the introduction, having spherical boundary components is an
essential feature of Theorem 1.1 without which we cannot possibly hope to cut
and cap (cf. the choice of the heavier edge in Case (3) of the proof of
theorem 5.1).

######  Theorem 6.2 (Local Pictures about a Teardrop).

Let $\mathcal{O}$ be a closed, orientable 3-orbifold and $T\subset\mathcal{O}$
an embedded teardrop. Then there exists a compact 3-orbifold $X$, $T\subset
X\subset\mathcal{O}$, satisfying the following properties (here, $B^{3}$ is
the interior of an embedded smooth closed ball):

  1. (1)

for the underlying topological space $|X|$ we have either:

    1. (a)

$|X|\cong S^{2}\times I$ (corresponding to Form $1,2$, or $3$ below), or

    2. (b)

$|X|\cong(S^{2}\times S^{1})\backslash B^{3}$ (corresponding to Form $4,5,6$
or Smooth Form below),

  2. (2)

$\partial X$ consists of one or two spherical 2-orbifolds, and

  3. (3)

the orbifold structure is one of the forms listed in Figures 10–16.

Figure 10. Smooth Form

Figure 11. Form 1 ($a_{+}=\overline{a}_{+}$ and $a_{-}=\overline{a}_{-}$)

Figure 12. Form 2 ($a_{+}=\overline{a}_{+}$)

Figure 13. Form 3

Figure 14. Forms 4.a (left) and 4.b (right)

Figure 15. Forms 5.a (left) and 5.b (right)

Figure 16. Form 6

###### Proof.

A flow chart for the proof of this theorem can be found in Figure 17.

Figure 17. The flowchart diagraming the proof of Theorem 16

We note that the labels in Figures 10–16 correspond to weights. Let us
consider the teardrop $T$ and the edge333For the way we use the term edge
recall Definition 2.1. $e$ of $\Sigma$ that intersects it.

######  Case 1.

$\boldsymbol{e}$ is smooth. See Figure 10. When $e$ is a smooth simple closed
curve we set $X$ to be $N\left(S^{2}(a)\cup e\right)$. Clearly
$X\cong\left(S^{2}(a)\times S^{1}\right)\setminus B^{3}$, where $a>1$.
Therefore, $|X|\cong\left(S^{2}\times S^{1}\right)\setminus B^{3}$ and
$\partial X=S^{2}$. This is the Smooth Form.

For the remainder of the proof we assume that $e$ is not smooth. Before
proceeding we construct $\chi$ and $\omega$ (cf. the construction of $\chi$
and $\omega$ on Page 5). Again we note that $\chi$ is a subspace of the
universal cover of a component of $\Sigma$ and $\omega$ is the restriction of
the covering projection to $\chi$.

Construction of $\boldsymbol{\chi}$ and $\boldsymbol{\omega}$. Let $\chi$ be
the tree shown in Figure 18. We construct a map $\omega:\chi\to\Sigma$;
$\omega$ is required to map the interior of every edge of $\chi$
homeomorphically onto the interior of an edge of $\Sigma$. We first map
$e^{\prime}$ to $e$ (with either orientation); this can be done since $e$ is
not smooth. We then extend the map to $e_{+}^{\prime}$ and
$\overline{e}_{+}^{\prime}$, mapping them to edges adjacent to
$\omega(v_{+}^{\prime})$ so that $\omega$ is locally injective; this can be
done because $\Sigma$ is tri-valent. We similarly extend $\omega$ to the rest
of $\chi$, obtaining $\omega:\chi\to\Sigma$ that is locally injective although
it may well fail to be injective. We denote images under $\omega$ by dropping
the primes, for example, $\omega(e^{\prime})=e$. Since the edges of $\Sigma$
are weighted, $\omega$ induces weights on the edges
$e^{\prime},e_{+}^{\prime},\overline{e}_{+}^{\prime},e_{-}^{\prime}$ and
$\overline{e}_{-}^{\prime}$ which we denote $a,a_{+},\overline{a}_{+},a_{-}$
and $\overline{a}_{-}$.

Figure 18. $\chi$

With the construction of $\chi$ and $\omega$ behind us we are now ready to
proceed with the proof of Theorem 16. Recall that we already dispensed with
Case 1, and we continue the work under the assumption that $e$ is not smooth.

######  Case 2.

$\boldsymbol{v_{+}=v_{-}}$. See Figure 14. We use $v$ to denote $v_{+}=v_{-}$.
Since the valence of $v$ is three we have that
$e_{+}=\overline{e}_{+}=e_{-}=\overline{e}_{-}$ and we use $e_{+}$ to denote
this edge and $a_{+}$ to denote its weight. Let $a_{++}$ and
$\overline{a}_{++}$ be the weights of the edges attached to $e_{+}$ at
$v_{++}$. We assume as we may that $a_{++}\geq\overline{a}_{++}$ and
distinguish two subcases:

Subcase 2.a: $\boldsymbol{a_{++}=\overline{a}_{++}}$. We take $X$ to be
$N\left(T\cup e\cup e_{+}\right)$ (see the left part of Figure 14). Since $e$
is a simple closed curve and $e_{+}\cap e$ is exactly one endpoint of $e_{+}$
(since the valence of $v_{++}$ is three) we have that $|X|\cong S^{2}\times
S^{1}\setminus B^{3}$ and $\partial X\cong S^{2}(a_{++},a_{++})$. This is Form
4.a.

Subcase 2.b: $\boldsymbol{a_{++}>\overline{a}_{++}}$. Let $e_{++}$ be the edge
of weight $a_{++}$ that is connected to $a_{+}$, and take $X$ to be
$N\left(T\cup e\cup e_{+}\cup e_{++}\right)$ (see the right part of Figure
14). As above $e$ is a simple closed curve and $e_{+}$ intersects it in a
single point. Moreover, $e_{++}$ intersects $e\cup e_{+}$ in a single point
since the other endpoint of $e_{++}$ cannot be $v$ (since its valence is
three) nor can it be $v_{+}$, since the third edge connected to $v_{+}$ is of
weight $\overline{a}_{++}\neq a_{++}$. Therefore we have that $|X|\cong
S^{2}\times S^{1}\setminus B^{3}$ and $\partial X\cong
S^{2}(\overline{a}_{+},a_{1},a_{2})$, where here $a_{1}$ and $a_{2}$ are the
weights of the edges attached to $e_{++}$. Since $a_{++}>\overline{a}_{++}$
and $a_{++},a_{1},a_{2}$ are the weights at a vertex, by Lemma 2.6 we have
that $S^{2}(\overline{a}_{++},a_{1},a_{2})$ is spherical. This is Form 4.b.

We assume from now on that $e$ is not smooth and $v_{+}\neq v_{-}$. By
parallel edges we mean edges that connect the same vertices; they are not
assumed to co-bound a disk in the orbifold.

######  Case 3.

Some edge of $\boldsymbol{\Sigma}$ is parallel to $\boldsymbol{e}$. See Figure
15. Let $e^{*}$ be an edge parallel to $e$; if there are two such edges we
choose the heavier of the two if their weights are distinct, and we choose one
of the two arbitrarily otherwise. This is not essential but does make the
construction of $X$ canonical. Let $a_{1}\leq a_{1}^{*}$ be the weights of the
edges connected to $e$ and $e^{*}$ at $v_{+}$ and $v_{-}$. We distinguish two
subcases:

Subcase 3.a: $\boldsymbol{a_{1}=a_{1}^{*}}$. See the left part of Figure 15.
We take $X$ to be $N\left(T\cup e\cup e_{*}\right)$. Since $e\cup e^{*}$ is a
simple closed curve we have that $|X|\cong S^{2}\times S^{1}\setminus B^{3}$.
By construction $\partial X\cong S^{2}(a_{1},a_{1})$. This is Form 5.a.

Subcase 3.b: $\boldsymbol{a_{1}<a_{1}^{*}}$. Let $e_{1}^{*}$ be the edge of
weight $a_{1}^{*}$ (see the right part of Figure 15). We set $X$ to be $T\cup
e\cup e^{*}\cup e_{1}^{*}$. Since $a_{1}\neq a_{1}^{*}$ we have that
$e_{1}^{*}\cap\left(e\cup e^{*}\right)$ is a single vertex. It follows that
$|X|\cong S^{2}\times S^{1}\setminus B^{3}$. Moreover, $\partial X\cong
S^{2}(a_{1},a_{2},a_{3})$, where here $a_{2}$ and $a_{3}$ are the weights of
the edges connected to $e_{1}^{*}$. Since $a_{1}^{*}>a_{1}$ and
$a_{1}^{*},a_{2},a_{3}$ are the weights at a vertex, by Lemma 2.6 we have that
$S^{2}(a_{1},a_{2},a_{3})$ is spherical. This is Form 5.b.

We assume from now on that $e$ is not smooth, $v_{+}\neq v_{-}$, and no edge
of $\Sigma$ is parallel to $e$. We then have the following (recall the labels
as in Figure 18):

  1. (1)

$v_{--}\neq v_{+}$ and $v_{++}\neq v_{-}$ (otherwise we would be in Case 3).
Similar statements hold $\overline{v}_{++}$, and $\overline{v}_{--}$ but we
will not need them. (However we cannot rule out $v_{++}=v_{+}$,
$\overline{v}_{++}=v_{+}$, $v_{--}=v_{-}$, and $\overline{v}_{--}=v_{-}$.)

  2. (2)

By reversing the embedding $e^{\prime}\to e$ and relabeling,
$e_{+}\leftrightarrow\overline{e}_{+}$ and
$e_{-}\leftrightarrow\overline{e}_{-}$, if necessary, we may assume further
that one of the following holds:

    1. (a)

$a_{+}=\overline{a}_{+}$ and $a_{-}=\overline{a}_{-}$.

    2. (b)

$a_{+}=\overline{a}_{+}$ and $a_{-}>\overline{a}_{-}$.

    3. (c)

$a_{+}>\overline{a}_{+}$ and $a_{-}>\overline{a}_{-}$.

This leaves us with the three cases below:

######  Case 4.

${\boldsymbol{a_{+}=\overline{a}_{+}$and$a_{-}=\overline{a}_{-}}$.}SeeFigure~{}\ref{figure:form1}.Weset$X$tobe$N(T\cup
e)$.Clearly$|X|\cong S^{2}\times[0,1]$and$\partial
X$consistsofthetwogoodfootballs$S^{2}(a_{+},\overline{a}_{+})$and$S^{2}(a_{-},\overline{a}_{-})$.Thisis\em
Form~{}1.\em$

######  Case 5.

${\boldsymbol{a_{+}=\overline{a}_{+}$and$a_{-}>\overline{a}_{-}}$.}SeeFigure~{}\ref{figure:form2}.Since$a_{-}>\overline{a}_{-}$wehavethat$e_{-}$and$\overline{e}_{-}$aredistinctedges,thatis,$v_{--}\neq
v_{-}$.Furthermore,weknowthat$v_{--}\neq
v_{+}$(assumption~{}(1)above).Therefore$e\cup
e_{-}$ishomeomorphictoaclosedinterval.Weset$X$tobe$N(T\cup e\cup
e_{+})$.Clearly$|X|\cong S^{2}\times[0,1]$and$\partial
X$consistsoftwocomponents,oneofwhichisthegoodfootball$S^{2}(a_{+},\overline{a}_{+})$andtheother$S^{2}(\overline{a}_{-},a_{2},a_{3})$,wherehere$a_{2}$and$a_{3}$aretheweightsoftheedgesattachedto$e_{-}$at$v_{--}$.Since$a_{-},a_{2},a_{3}$aretheweightsatavertexand$\overline{a}_{-}<a_{-}$,byLemma~{}\ref{firstcut}wehavethat$S^{2}(\overline{a}_{-},a_{2},a_{3})$isspherical.Thisis\em
Form~{}2.\em$

######  Case 6.

$\boldsymbol{a_{+}>\overline{a}_{+}}$ and
$\boldsymbol{a_{-}>\overline{a}_{-}}$. We distinguish two subcases:

Subcase 6.a: $\boldsymbol{v_{--}\neq v_{++}}$. See Figure 13. The assumption
that $v_{--}\neq v_{++}$ together with the assumptions above imply that
$e_{-}\cup e\cup e_{+}$ homeomorphic to a closed interval. We set $X$ to be
$N(T\cup e\cup e_{+}\cup e_{-})$. Clearly $|X|\cong S^{2}\times[0,1]$.
Morevoer, $\partial X$ consists of two components,
$S^{2}(\overline{a}_{+},a_{2},a_{3})$ and
$S^{2}(\overline{a}_{-},a^{\prime}_{2},a^{\prime}_{3}$), where here $a_{2}$
and $a_{3}$ (respectively, $a_{2}^{\prime}$ and $a_{3}^{\prime}$) are the
weights of the edges attached to $e_{+}$ at $v_{++}$ (respectively, to $e_{-}$
at $v_{--}$). Similar to Case 5, by Lemma 2.6 both components of $\partial X$
are spherical. This is Form 3.

Subcase 6.b: $\boldsymbol{v_{--}=v_{++}}$. See Figure 16. We again take $X$ to
be $N(T\cup e\cup e_{+}\cup e_{-})$. This time, however, the assumption that
$v_{--}=v_{++}$ implies that $e\cup e_{+}\cup e_{-}$ forms a simple closed
curve. We therefore see that $|X|\cong(S^{2}\times S^{1})\setminus B^{3}$ and
$\partial X\cong S^{2}(\overline{a}_{+},\overline{a}_{-},a^{*})$, where
$a^{*}$ is the weight of the edge attached to $e_{+}$ and $e_{-}$ at
$v_{++}=v_{--}$.

It remains to show that $\partial X$ is spherical. Since all the weights are
integers no less than $2$, the assumptions of Case 6 imply that $a_{+}\geq 3$
and $a_{-}\geq 3$. The weights at $v_{++}$ are $a_{+},a_{-},$ and $a^{*}$, and
satisfy (as the weights about any vertex do)

$\frac{1}{a_{+}}+\frac{1}{a_{-}}+\frac{1}{a^{*}}\geq 1$

This forces (recall the list of spherical 2-orbifolds on Page 2) at least one
of the weights to be $2$, showing that $a^{*}=2$. Furthermore, at least one of
$a_{+}\leq 3$ or $a_{-}\leq 3$ holds, and we may assume that $a_{-}=3$. Since
$3=a_{-}>\overline{a}_{-}\geq 2$, we have that $\overline{a}_{-}=2$. Thus

$\partial X\cong S^{2}(\overline{a}_{+},\overline{a}_{-},a^{*})\cong
S^{2}(\overline{a}_{+},2,2)$

Thus $\partial X$ is spherical (regardless of $\overline{a}_{+}$). (The keen
reader will have observed that the labels in Figure 16 provide more
information; we will leave it as an exercise to justify this, as it is not
used in the proof.) This is Form 6.

∎

##  7\. Proof of Main Theorem

Before proving Theorem 1.1 we state and prove a few preliminary lemmas.

######  Lemma 7.1.

Let $Y$ be a 3-orbifold with spherical boundary and let $\hat{Y}$ be the
3-orbifold obtained from $Y$ by capping its boundary. Then any collection of
disjointly embedded 2-orbifolds in $\hat{Y}$ can be isotoped into $Y$.

###### Proof.

Each cap is the cone on a boundary component. Since embedded 2-orbifolds
cannot intersect the vertices of $\Sigma$, any such collection can be isotoped
out of the caps and into $Y$. ∎

This is the setup for Lemma 7.2: let $\mathcal{O}_{i-1}$ be a closed,
orientable orbifold admitting an embedded teardrop (the index is chosen to
coincide with indices below). Let $T\subset\mathcal{O}_{i-1}$ be a member of a
maximal444Here by maximal we mean a family with the largest possible number of
teardrops (similarly below, footballs). family of disjointly embedded, non-
parallel teardrops (a maximal family exists by Theorem 3.1). Let
$X_{i}\subset\mathcal{O}_{i-1}$ be the sub-orbifold containing $T$ guaranteed
to exist by Theorem 16. Finally, let $\mathcal{O}_{i}$ be the orbifold
obtained from $\mathcal{O}_{i-1}$ by cutting-and-capping $X_{i}$.

######  Lemma 7.2.

The maximal number of disjointly embedded, non-parallel teardrops in
$\mathcal{O}_{i}$ is strictly less than the maximal number of disjointly
embedded, non-parallel teardrops in $\mathcal{O}_{i-1}$.

###### Proof.

Let $t_{\text{max}}$ be the maximal number of disjointly embedded, non-
parallel teardrops in $\mathcal{O}_{i-1}$. Suppose towards contradiction that
$\mathcal{T}_{i}\subset\mathcal{O}_{i}$ is a collection of $t_{\text{max}}$
disjointly embedded, non-parallel teardrops. Since $X_{i}$ is obtained by
capping $\mathcal{O}_{i-1}\setminus X_{i}$, by Lemma 7.1 we may isotope
$\mathcal{T}_{i}$ out of the caps and consider
$\mathcal{T}_{i}\subset\mathcal{O}_{i-1}\backslash X_{i}$. As $T\subset
X_{i}$, we have that

$\mathcal{T}_{i}\cap T=\emptyset.$

Therefore, $\mathcal{T}_{i}\cup T$ form $t_{\text{max}}+1$ disjointly embedded
teardrops in $\mathcal{O}_{i-1}$ and by definition of $t_{\text{max}}$ one of
the following holds:

  1. (1)

There exists $T^{\prime},T^{\prime\prime}\in\mathcal{T}_{i}$ that are parallel
in $\mathcal{O}_{i-1}$: let $P\subset\mathcal{O}_{i-1}$ be a product region
that $T^{\prime}$ and $T^{\prime\prime}$ co-bound. Since $T^{\prime}\cap
X_{i},T^{\prime\prime}\cap X_{i}=\emptyset$, one of the following two cases
holds:

    1. (a)

$X_{i}\subset P$: By considering all of the forms of $X_{i}$ from Theorem 16,
we see that $\Sigma\cap X_{i}$ contains either a smooth simple closed curve
(Smooth Form) or a vertex (all other forms). Therefore $X_{i}\not\subset P$,
as a product region contains no simple closed curve or vertex of the singular
set.

    2. (b)

$X_{i}\cap P=\emptyset$: Then $P\subset\mathcal{O}_{i}$ showing that
$T^{\prime}$ and $T^{\prime\prime}$ are parallel in $\mathcal{O}_{i}$,
contrary to our assumption.

Therefore, case (1) cannot happen.

  2. (2)

$T$ is parallel to $T^{\prime}$, for some $T^{\prime}\in\mathcal{T}_{i}$: Let
$e$ be the edge of $\Sigma$ that meets $T$.555 Keep in mind that an edge may
be a simple closed curve, as explained in Definition 2.1. By considering all
the forms of $X_{i}$ in Theorem 16 we know that $e\subset X_{i}$. As
$T^{\prime}$ is parallel to $T$, the orbifold point of $T^{\prime}$ must also
lie on $e$. Therefore $T^{\prime}$ cannot be isotoped out of $X_{i}$,
contradicting our construction. Therefore, case (2) cannot happen.

This establishes Lemma 7.2. ∎

This is the set-up for Lemma 7.3: let $\mathcal{O}_{n+i-1}$ be a closed,
orientable orbifold admitting an embedded bad-football but no embedded
teardrop (the index is chosen to coincide with indices below). Let
$F\subset\mathcal{O}_{n+i-1}$ be a member of a maximal family of disjointly
embedded, non-parallel bad-footballs (a maximal family exists by Theorem 4.1).
Let $X_{n+i}\subset\mathcal{O}_{n+i-1}$ be the sub-orbifold containing $F$
guaranteed to exist by Theorem 5.1. Finally, let $\mathcal{O}_{n+i}$ be the
orbifold obtained from $\mathcal{O}_{n+i-1}$ by cutting-and-capping $X_{n+i}$.

######  Lemma 7.3.

The maximal number of disjointly embedded, non-parallel bad-footballs in
$\mathcal{O}_{n+i}$ is strictly less than the maximal number of disjointly
embedded, non-parallel bad-footballs in $\mathcal{O}_{n+i-1}$. Furthermore,
there does not exist a teardrop in $\mathcal{O}_{n+i}$.

###### Proof.

Let $f_{\text{max}}$ be the maximal number of disjointly embedded, non-
parallel footballs in $\mathcal{O}_{n+i-1}$. Suppose towards contradiction
that $\mathcal{F}_{n+i}\subset\mathcal{O}_{n+i}$ is a collection of
$f_{\text{max}}$ disjointly embedded, non-parallel footballs. By Lemma 7.1 we
may assume that $\mathcal{F}_{n+i}\subset\mathcal{O}_{n+i-1}\backslash X_{i}$.
As $F\subset X_{n+i}$ we have that

$\mathcal{F}_{n+i}\cap F=\emptyset.$

Therefore, $\mathcal{T}_{n+i}\cup F$ form $f_{\text{max}}+1$ disjointly
embedded bad-footballs in $\mathcal{O}_{n+i-1}$ and by definition of
$f_{\text{max}}$ one of the following holds:

  1. (1)

There exists $F^{{}^{\prime}},F^{{}^{\prime\prime}}\in\mathcal{F}_{n+i}$ that
are parallel in $\mathcal{O}_{n+i-1}$: let $P\subset\mathcal{O}_{i-1}$ be a
product region that $F^{{}^{\prime}}$ and $F^{{}^{\prime\prime}}$ co-bound.
Since $F^{{}^{\prime}}\cap X_{n+i},F^{{}^{\prime\prime}}\cap
X_{n+i}=\emptyset$, one of the following two cases holds:

    1. (a)

$X_{n+i}\subset P$: By considering all of the forms of $X_{n+i}$ from Theorem
5.1, we see that $\Sigma\cap X_{n+i}$ contains either a smooth simple closed
curve (Smooth Form) or a vertex (all other forms). Therefore
$X_{n+i}\not\subset P$, as these do not exist in a product region.

    2. (b)

$X_{n+i}\cap P=\emptyset$: Then $P\subset\mathcal{O}_{n+i}$ showing that
$F^{{}^{\prime}}$ and $F^{{}^{\prime\prime}}$ are parallel in
$\mathcal{O}_{n+i}$, contrary to our assumption.

Therefore, case (1) cannot happen.

  2. (2)

$F$ is parallel to $F^{\prime}$, for some $F^{\prime}\in\mathcal{T}_{n+i}$:
Let $e$ and $f$ be the edges of $\Sigma$ that meet $F$. By considering all the
forms of $X_{n+i}$ in Theorem 5.1 we see that $e\subset X_{n+i}$ or $f\subset
X_{n+i}$. As $F^{\prime}$ is parallel to $F$, at least one orbifold point of
$F^{\prime}$ must lie on $e$ or $f$. Therefore $F^{\prime}$ cannot be isotoped
out of $X_{i}$, contradicting our construction. Therefore, case (2) cannot
happen.

If $\mathcal{O}_{n+i}$ admitted a teardrop $T$ then, by Lemma 7.1 we could
isotope $T$ into $\mathcal{O}_{n+i-1}$, contradicting our assumptions.

This establishes Lemma 7.3. ∎

###### Proof Theorem 1.1.

We construct $n$ and $\mathcal{O}_{i}$ $(i=0,\dots,n)$ as follows: set
$\mathcal{O}_{0}=\mathcal{O}$ and assume we have constructed
$\mathcal{O}_{i-1}$.

  1. (1)

If $\mathcal{O}_{i-1}$ does not contain a teardrop, set $n=i-1$.

  2. (2)

If $\mathcal{O}_{i-1}$ does contain a teardrop, let $T$ be a member of a
maximal family of disjointly embedded, non-parallel teardrops, and let $X_{i}$
be a suborbifold containing $T$ guaranteed to exist by Theorem 16. Construct
$\mathcal{O}_{i}$ by cutting-and-capping $X_{i}\subset\mathcal{O}_{i-1}$.

By Theorem 3.1 the number of disjointly embedded, pairwise non-parallel
teardrops in $\mathcal{O}_{i}$ is finite, and by Lemma 7.2 this number is
smaller than the corresponding number in $\mathcal{O}_{i-1}$. Therefore the
process terminates, yielding $n$ with $\mathcal{O}_{n}$ not containing a
teardrop.

We next construct $m$ and $\mathcal{O}_{n+i}$ $(i=1,\dots,m)$ as follows:
starting with $\mathcal{O}_{n}$ above, assume we have constructed
$\mathcal{O}_{n+i-1}$ not containing a teardrop.

  1. (1)

If $\mathcal{O}_{n+i-1}$ does not contain a bad-football, set $m=i-1$.

  2. (2)

If $\mathcal{O}_{n+i-1}$ does contain a teardrop, let $F$ be a member of a
maximal family of disjointly embedded, mutually non-parallel bad-footballs,
and let $X_{n+i}$ be a suborbifold containing $F$ guaranteed to exist by
Theorem 5.1. Construct $\mathcal{O}_{n+i}$ by cutting-and-capping
$X_{n+i}\subset\mathcal{O}_{n+i-1}$.

By Theorem 4.1 the number of disjointly embedded, pairwise non-parallel
footballs in $\mathcal{O}_{n+i}$ is finite, and by Lemma 7.3 this number is
smaller than the corresponding number in $\mathcal{O}_{n+i-1}$. Lemma 7.3 also
tells us that $\mathcal{O}_{n+i}$ does not admit a teardrop, and hence we may
continue this process, eventually yielding $m$ with $\mathcal{O}_{n+m}$ not
containing a bad-football or a teardrop. ∎

## References

  * [1] M. Boileau, B. Leeb, and J. Porti.  Geometrization of 3-dimensional orbifolds.  Ann. of Math. (2), 162(1):195–290, 2005.
  * [2] Michel Boileau, Sylvain Maillot, and Joan Porti.  Three-dimensional orbifolds and their geometric structures.  15:viii+167, 2003.
  * [3] Michel Boileau and Joan Porti.  Geometrization of 3-orbifolds of cyclic type.  Astérisque, (272):208, 2001.  Appendix A by Michael Heusener and Porti.
  * [4] F. Bonahon and L. Siebenmann.  The classification of Seifert fibred $3$-orbifolds.  In Low-dimensional topology (Chelwood Gate, 1982), volume 95 of London Math. Soc. Lecture Note Ser., pages 19–85. Cambridge Univ. Press, Cambridge, 1985.
  * [5] John H. Conway, Heidi Burgiel, and Chaim Goodman-Strauss.  The symmetries of things.  A K Peters, Ltd., Wellesley, MA, 2008.
  * [6] Daryl Cooper, Craig D. Hodgson, and Steven P. Kerckhoff.  Three-dimensional orbifolds and cone-manifolds, volume 5 of MSJ Memoirs.  Mathematical Society of Japan, Tokyo, 2000.  With a postface by Sadayoshi Kojima.
  * [7] Benedict Freedman and Michael H. Freedman.  Kneser-Haken finiteness for bounded $3$-manifolds locally free groups, and cyclic covers.  Topology, 37(1):133–147, 1998.
  * [8] John Hempel.  $3$-Manifolds.  Princeton University Press, Princeton, N. J.; University of Tokyo Press, Tokyo, 1976.  Ann. of Math. Studies, No. 86.
  * [9] William Jaco.  Lectures on three-manifold topology, volume 43 of CBMS Regional Conference Series in Mathematics.  American Mathematical Society, Providence, R.I., 1980.
  * [10] Bruce Kleiner and John Lott.  Geometrization of three-dimensional orbifolds via Ricci flow.  Astérisque, (365):101–177, 2014.
  * [11] José María Montesinos.  Classical tessellations and three-manifolds.  Universitext. Springer-Verlag, Berlin, 1987.
  * [12] Grisha Perelman.  Finite extinction time for the solutions to the ricci flow on certain three–manifolds.  arxiv.org/abs/math/0307245.
  * [13] Grisha Perelman.  Ricci flow with surgery on three–manifolds.  https://arxiv.org/abs/math/0303109.
  * [14] Grisha Perelman.  Finite extinction time for the solutions to the ricci flow on certain three-manifolds.  arxiv.org/abs/math/0307245, 2003.
  * [15] Jennifer Schultens.  Introduction to 3-manifolds, volume 151 of Graduate Studies in Mathematics.  American Mathematical Society, Providence, RI, 2014.
  * [16] Peter Scott.  The geometries of $3$-manifolds.  Bull. London Math. Soc., 15(5):401–487, 1983.
  * [17] William P. Thurston.  The geometry and topology of 3-manifolds.  Princeton Math. Dept., 1979.


Log-based Anomaly Detection Without Log Parsing

Van-Hoang Le and
Hongyu Zhang22Hongyu Zhang is the corresponding author.
The University of Newcastle, NSW, Australia
<EMAIL_ADDRESS><EMAIL_ADDRESS>
Software systems often record important runtime information in system logs for troubleshooting purposes.
There have been many studies that use log data to construct machine learning models for detecting system anomalies. Through our empirical study, we find that existing log-based anomaly detection approaches are significantly affected by log parsing errors that are introduced by 1) OOV (out-of-vocabulary) words, and 2) semantic misunderstandings. The log parsing errors could cause the loss of important information for anomaly detection. To address the limitations of existing methods, we propose NeuralLog, a novel log-based anomaly detection approach that does not require log parsing. NeuralLog extracts the semantic meaning of raw log messages and represents them as semantic vectors. These representation vectors are then used to detect anomalies through a Transformer-based classification model, which can capture the contextual information from log sequences. Our experimental results show that the proposed approach can effectively understand the semantic meaning of log messages and achieve accurate anomaly detection results. Overall, NeuralLog achieves F1-scores greater than 0.95 on four public datasets, outperforming the existing approaches.

Anomaly Detection, Log Analysis, Log Parsing, Deep Learning

§ INTRODUCTION

§ BACKGROUND

§ AN EMPIRICAL STUDY OF LOG PARSING ERRORS

§ NEURALLOG: LOG-BASED ANOMALY DETECTION WITHOUT LOG PARSING

§ EVALUATION

§ DISCUSSION

§ RELATED WORK

§ CONCLUSION

[1]
E. Bauer and R. Adams, Reliability and availability of cloud
computing.1em plus 0.5em minus 0.4emJohn Wiley & Sons, 2012.

[2]
R. S. Kazemzadeh and H.-A. Jacobsen, “Reliable and highly available
distributed publish/subscribe service,” in 2009 28th IEEE
International Symposium on Reliable Distributed Systems.1em plus
0.5em minus 0.4emIEEE, 2009, pp. 41–50.

[3]
J. Breier and J. Branišová, “Anomaly detection from log files using
data mining techniques,” in Information Science and
Applications.1em plus 0.5em minus 0.4emSpringer, 2015, pp.

[4]
B. Zhang, H. Zhang, P. Moscato, and A. Zhang, “Anomaly detection via mining
numerical workflow relations from logs,” in 2020 International
Symposium on Reliable Distributed Systems (SRDS).1em plus 0.5em minus
0.4emIEEE, 2020, pp. 195–204.

[5]
M. Du, F. Li, G. Zheng, and V. Srikumar, “Deeplog: Anomaly detection and
diagnosis from system logs through deep learning,” in Proceedings of
the 2017 ACM SIGSAC Conference on Computer and Communications Security,
2017, pp. 1285–1298.

[6]
M. Chen, A. X. Zheng, J. Lloyd, M. I. Jordan, and E. Brewer, “Failure
diagnosis using decision trees,” in International Conference on
Autonomic Computing, 2004. Proceedings.1em plus 0.5em minus
0.4emIEEE, 2004, pp. 36–43.

[7]
W. Xu, L. Huang, A. Fox, D. Patterson, and M. I. Jordan, “Detecting
large-scale system problems by mining console logs,” in Proceedings of
the ACM SIGOPS 22nd symposium on Operating systems principles, 2009, pp.

[8]
X. Zhang, Y. Xu, Q. Lin, B. Qiao, H. Zhang, Y. Dang, C. Xie, X. Yang, Q. Cheng,
Z. Li et al., “Robust log-based anomaly detection on unstable log
data,” in Proceedings of the 2019 27th ACM Joint Meeting on European
Software Engineering Conference and Symposium on the Foundations of Software
Engineering, 2019, pp. 807–817.

[9]
H. Guo, S. Yuan, and X. Wu, “Logbert: Log anomaly detection via bert,”
arXiv preprint arXiv:2103.04475, 2021.

[10]
P. Bodik, M. Goldszmidt, A. Fox, D. B. Woodard, and H. Andersen,
“Fingerprinting the datacenter: automated classification of performance
crises,” in Proceedings of the 5th European conference on Computer
systems, 2010, pp. 111–124.

[11]
J.-G. Lou, Q. Fu, S. Yang, Y. Xu, and J. Li, “Mining invariants from console
logs for system problem detection.” in USENIX Annual Technical
Conference, 2010, pp. 1–14.

[12]
W. Meng, Y. Liu, Y. Zhu, S. Zhang, D. Pei, Y. Liu, Y. Chen, R. Zhang, S. Tao,
P. Sun et al., “Loganomaly: Unsupervised detection of sequential and
quantitative anomalies in unstructured logs.” in IJCAI, vol. 7, 2019,
pp. 4739–4745.

[13]
T. Mikolov, K. Chen, G. Corrado, and J. Dean, “Efficient estimation of word
representations in vector space,” arXiv preprint arXiv:1301.3781,

[14]
A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez,
L. Kaiser, and I. Polosukhin, “Attention is all you need,” arXiv
preprint arXiv:1706.03762, 2017.

[15]
J. Zhu, S. He, J. Liu, P. He, Q. Xie, Z. Zheng, and M. R. Lyu, “Tools and
benchmarks for automated log parsing,” in 2019 IEEE/ACM 41st
International Conference on Software Engineering: Software Engineering in
Practice (ICSE-SEIP).1em plus 0.5em minus 0.4emIEEE, 2019, pp.

[16]
P. He, J. Zhu, S. He, J. Li, and M. R. Lyu, “An evaluation study on log
parsing and its use in log mining,” in 2016 46th annual IEEE/IFIP
international conference on dependable systems and networks (DSN).1em
plus 0.5em minus 0.4emIEEE, 2016, pp. 654–661.

[17]
M. Nagappan and M. A. Vouk, “Abstracting log lines to log event types for
mining software system logs,” in 2010 7th IEEE Working Conference on
Mining Software Repositories (MSR 2010).1em plus 0.5em minus
0.4emIEEE, 2010, pp. 114–117.

[18]
R. Vaarandi and M. Pihelgas, “Logcluster-a data clustering and pattern mining
algorithm for event logs,” in 2015 11th International conference on
network and service management (CNSM).1em plus 0.5em minus
0.4emIEEE, 2015, pp. 1–7.

[19]
H. Dai, H. Li, C. S. Chen, W. Shang, and T.-H. Chen, “Logram: Efficient log
parsing using n-gram dictionaries,” IEEE Transactions on Software
Engineering, 2020.

[20]
L. Tang, T. Li, and C.-S. Perng, “Logsig: Generating system events from raw
textual logs,” in Proceedings of the 20th ACM international conference
on Information and knowledge management, 2011, pp. 785–794.

[21]
H. Hamooni, B. Debnath, J. Xu, H. Zhang, G. Jiang, and A. Mueen, “Logmine:
Fast pattern recognition for log analytics,” in Proceedings of the
25th ACM International on Conference on Information and Knowledge
Management, 2016, pp. 1573–1582.

[22]
K. Shima, “Length matters: Clustering system log messages using length of
words,” arXiv preprint arXiv:1611.03213, 2016.

[23]
S. Thaler, V. Menkonvski, and M. Petkovic, “Towards a neural language model
for signature extraction from forensic logs,” in 2017 5th
International Symposium on Digital Forensic and Security (ISDFS).1em
plus 0.5em minus 0.4emIEEE, 2017, pp. 1–6.

[24]
P. He, J. Zhu, Z. Zheng, and M. R. Lyu, “Drain: An online log parsing approach
with fixed depth tree,” in 2017 IEEE International Conference on Web
Services (ICWS).1em plus 0.5em minus 0.4emIEEE, 2017, pp.

[25]
Z. M. Jiang, A. E. Hassan, P. Flora, and G. Hamann, “Abstracting execution
logs to execution events for enterprise applications (short paper),” in
2008 The Eighth International Conference on Quality Software.1em plus 0.5em minus 0.4emIEEE, 2008, pp. 181–186.

[26]
A. A. Makanju, A. N. Zincir-Heywood, and E. E. Milios, “Clustering event logs
using iterative partitioning,” in Proceedings of the 15th ACM SIGKDD
international conference on Knowledge discovery and data mining, 2009, pp.

[27]
M. Du and F. Li, “Spell: Streaming parsing of system event logs,” in
2016 IEEE 16th International Conference on Data Mining (ICDM).1em plus 0.5em minus 0.4emIEEE, 2016, pp. 859–864.

[28]
S. He, J. Zhu, P. He, and M. R. Lyu, “Experience report: System log analysis
for anomaly detection,” in 2016 IEEE 27th International Symposium on
Software Reliability Engineering (ISSRE).1em plus 0.5em minus
0.4emIEEE, 2016, pp. 207–218.

[29]
D. El-Masri, F. Petrillo, Y.-G. Guéhéneuc, A. Hamou-Lhadj, and
A. Bouziane, “A systematic literature review on automated log abstraction
techniques,” Information and Software Technology, vol. 122, p.
106276, 2020.

[30]
Y. Liang, Y. Zhang, H. Xiong, and R. Sahoo, “Failure prediction in ibm
bluegene/l event logs,” in Seventh IEEE International Conference on
Data Mining (ICDM 2007).1em plus 0.5em minus 0.4emIEEE, 2007,
pp. 583–588.

[31]
A. Joulin, E. Grave, P. Bojanowski, M. Douze, H. Jégou, and T. Mikolov,
“Fasttext. zip: Compressing text classification models,” arXiv
preprint arXiv:1612.03651, 2016.

[32]
G. Salton and C. Buckley, “Term-weighting approaches in automatic text
retrieval,” Information processing & management, vol. 24, no. 5, pp.
513–523, 1988.

[33]
A. Oliner and J. Stearley, “What supercomputers say: A study of five system
logs,” in 37th Annual IEEE/IFIP International Conference on Dependable
Systems and Networks (DSN'07).1em plus 0.5em minus 0.4emIEEE,
2007, pp. 575–584.

[34]
S. He, J. Zhu, P. He, and M. R. Lyu, “Loghub: a large collection of system log
datasets towards automated log analytics,” arXiv preprint
arXiv:2008.06448, 2020.

[35]
(2021) Logpai. [Online]. Available: <https://github.com/logpai/logparser>

[36]
M. Schuster and K. Nakajima, “Japanese and korean voice search,” in
2012 IEEE International Conference on Acoustics, Speech and Signal
Processing (ICASSP).1em plus 0.5em minus 0.4emIEEE, 2012, pp.

[37]
Y. Wu, M. Schuster, Z. Chen, Q. V. Le, M. Norouzi, W. Macherey, M. Krikun,
Y. Cao, Q. Gao, K. Macherey et al., “Google's neural machine
translation system: Bridging the gap between human and machine translation,”
arXiv preprint arXiv:1609.08144, 2016.

[38]
J. Devlin, M.-W. Chang, K. Lee, and K. Toutanova, “Bert: Pre-training of deep
bidirectional transformers for language understanding,” arXiv preprint
arXiv:1810.04805, 2018.

[39]
V. Sanh, L. Debut, J. Chaumond, and T. Wolf, “Distilbert, a distilled version
of bert: smaller, faster, cheaper and lighter,” arXiv preprint
arXiv:1910.01108, 2019.

[40]
K. Clark, M.-T. Luong, Q. V. Le, and C. D. Manning, “Electra: Pre-training
text encoders as discriminators rather than generators,” arXiv
preprint arXiv:2003.10555, 2020.

[41]
R.-M. Karampatsis, H. Babii, R. Robbes, C. Sutton, and A. Janes, “Big code!=
big vocabulary: Open-vocabulary models for source code,” in 2020
IEEE/ACM 42nd International Conference on Software Engineering (ICSE).1em plus 0.5em minus 0.4emIEEE, 2020, pp. 1073–1085.

[42]
Q. Le and T. Mikolov, “Distributed representations of sentences and
documents,” in International conference on machine learning.1em plus 0.5em minus 0.4emPMLR, 2014, pp. 1188–1196.

[43]
(2021) Bert pretrained models. [Online]. Available:

[44]
(2021) Loghub. [Online]. Available: <https://github.com/logpai/loghub>

[45]
K. Yao, H. Li, W. Shang, and A. E. Hassan, “A study of the performance of
general compressors on log files,” Empirical Software Engineering,
vol. 25, no. 5, pp. 3043–3085, 2020.

[46]
I. Loshchilov and F. Hutter, “Decoupled weight decay regularization,”
arXiv preprint arXiv:1711.05101, 2017.

[47]
X. Li, P. Chen, L. Jing, Z. He, and G. Yu, “Swisslog: Robust and unified deep
learning based log anomaly detection for diverse faults,” in 2020 IEEE
31st International Symposium on Software Reliability Engineering
(ISSRE).1em plus 0.5em minus 0.4emIEEE, 2020, pp. 92–103.

[48]
W. Meng, Y. Liu, Y. Huang, S. Zhang, F. Zaiter, B. Chen, and D. Pei, “A
semantic-aware representation framework for online log analysis,” in
2020 29th International Conference on Computer Communications and
Networks (ICCCN).1em plus 0.5em minus 0.4emIEEE, 2020, pp.

[49]
Y. Pinter, R. Guthrie, and J. Eisenstein, “Mimicking word embeddings using
subword rnns,” arXiv preprint arXiv:1707.06961, 2017.

[50]
S. Sasaki, J. Suzuki, and K. Inui, “Subword-based compact reconstruction of
word embeddings,” in Proceedings of the 2019 Conference of the North
American Chapter of the Association for Computational Linguistics: Human
Language Technologies, Volume 1 (Long and Short Papers), 2019, pp.

[51]
J. Zhao, S. Mudgal, and Y. Liang, “Generalizing word embeddings using bag of
subwords,” arXiv preprint arXiv:1809.04259, 2018.

[52]
Z. Hu, T. Chen, K.-W. Chang, and Y. Sun, “Few-shot representation learning for
out-of-vocabulary words,” arXiv preprint arXiv:1907.00505, 2019.

[53]
A. Radford, J. Wu, R. Child, D. Luan, D. Amodei, and I. Sutskever, “Language
models are unsupervised multitask learners,” OpenAI blog, vol. 1,
no. 8, p. 9, 2019.

[54]
A. Conneau, K. Khandelwal, N. Goyal, V. Chaudhary, G. Wenzek, F. Guzmán,
E. Grave, M. Ott, L. Zettlemoyer, and V. Stoyanov, “Unsupervised
cross-lingual representation learning at scale,” arXiv preprint
arXiv:1911.02116, 2019.

[55]
(2021) Loglizer. [Online]. Available: <https://github.com/logpai/loglizer>

[56]
S. Nedelkoski, J. Bogatinovski, A. Acker, J. Cardoso, and O. Kao,
“Self-attentive classification-based anomaly detection in unstructured
logs,” arXiv preprint arXiv:2008.09340, 2020.

[57]
R. Vaarandi, “A data clustering algorithm for mining patterns from event
logs,” in Proceedings of the 3rd IEEE Workshop on IP Operations &
Management (IPOM 2003)(IEEE Cat. No. 03EX764).1em plus 0.5em minus
0.4emIeee, 2003, pp. 119–126.

[58]
Q. Fu, J.-G. Lou, Y. Wang, and J. Li, “Execution anomaly detection in
distributed systems through unstructured log analysis,” in 2009 ninth
IEEE international conference on data mining.1em plus 0.5em minus
0.4emIEEE, 2009, pp. 149–158.

[59]
S. Zhang, W. Meng, J. Bu, S. Yang, Y. Liu, D. Pei, J. Xu, Y. Chen, H. Dong,
X. Qu et al., “Syslog processing for switch failure diagnosis and
prediction in datacenter networks,” in 2017 IEEE/ACM 25th
International Symposium on Quality of Service (IWQoS).1em plus 0.5em
minus 0.4emIEEE, 2017, pp. 1–10.