\documentclass[a4paper,parskip,BCOR=12mm,DIV=10]{scrbook}

%\usepackage{german}
\usepackage[utf8]{inputenc}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{mathtools}
\usepackage{faktor}
\usepackage{nicefrac}
\usepackage{listings}
\usepackage{enumerate}
\usepackage{dsfont}
\usepackage{remreset}
\usepackage{booktabs}
\usepackage{lettrine}
%\usepackage{txfonts}
\usepackage{varioref}
\usepackage{multirow}
\usepackage{rotating}
\usepackage{cancel}
\usepackage[pdfauthor={Joachim Breitner}]{hyperref}
\usepackage[amsmath,thmmarks]{ntheorem}
\usepackage[capitalise]{cleveref}
\usepackage{tikz}
%\usepackage[tracking=true,kerning=true,spacing=true]{microtype}
\usepackage{microtype}
\usetikzlibrary{automata}
\usetikzlibrary{decorations}
\usetikzlibrary{snakes}
\usepackage[ruled,vlined]{algorithm2e}

\usepackage[numbers,square]{natbib}
\bibliographystyle{amsalpha}

% theorem-settings
\theoremnumbering{arabic}
\theoremstyle{plain}
\theorembodyfont{\itshape}
\theoremheaderfont{\normalfont\bfseries}
\theoremseparator{}
\newtheorem{theorem}{Theorem}
\newtheorem{proposition}{Proposition}
\newtheorem{lemma}{Lemma}
\newtheorem{corollary}{Corollary}

\theorembodyfont{\upshape}
\newtheorem{example}{Example}
\newtheorem{remark}{Remark}
\newtheorem{definition}{Definition}

\theoremstyle{nonumberplain}
\theoremheaderfont{\scshape}
\theorembodyfont{\normalfont}
\theoremsymbol{\ensuremath{_\blacksquare}}
\newtheorem{proof}{Proof}

% for \autoref
\newcommand{\examplename}{Example}
\newcommand{\lemmaname}{Lemma}
\newcommand{\remarkname}{Remark}
\newcommand{\corollaryname}{Corollary}
\newcommand{\definitionname}{Definition}
\newcommand{\algocflinename}{Algorithm}
\newcommand{\AlgoLineautorefname}{line}
\renewcommand{\chapterautorefname}{Chapter}
\renewcommand{\sectionautorefname}{Section}
\renewcommand{\subsectionautorefname}{Section}

% for \cref
\crefname{algocf}{Algorithm}{Algorithms}
\crefname{figure}{Figure}{Figure}

% vref settings
\vrefwarning
\def\reftextfaceafter {\unskip}%
\def\reftextfacebefore{\unskip}%
\def\reftextafter     {on the \reftextvario{following}{next} page}%
\def\reftextbefore    {on the \reftextvario{preceding}{previous} page}%
\def\reftextcurrent   {\unskip}%

% titlesec
\usepackage{titlesec}
\titleformat{\chapter}[display]
	{\sectfont\Large\filcenter}
	{\titlerule%[1pt]%
	 \vspace{1pt}%
	 \titlerule%
	 %\vspace{.4pc}%
	 \LARGE\MakeUppercase{\chaptertitlename} \thechapter}
	{1pc}
	{\titlerule
	 \vspace{1pc}%
	 \Huge}
% \titleformat{\chapter}[display]
% 	{\sectfont\Large}
% 	{%\titlerule%[1pt]%
% 	 %\vspace{1pt}%
% 	 %\titlerule%
% 	 %\vspace{.4pc}%
% 	 \LARGE{\chaptertitlename} \thechapter}
% 	{1pc}
% 	{%\titlerule
% 	 %\vspace{1pc}%
% 	 \sectfont%
% 	 \Huge}

%\pagestyle{headings}

% get rid of fourier fontenc warnings
% from http://newsgroups.derkeiler.com/Archive/Comp/comp.text.tex/2006-01/msg00679.html
\makeatletter
\let\my@@font@warning\@font@warning
\let\@font@warning\@font@info
\makeatother
%
\usepackage{mathpazo}
%\usepackage{fourier}
%\usepackage[math]{iwona}
%\usepackage{ccfonts}
%\usepackage{arev}
%\usepackage[garamond]{mathdesign}
%\usepackage{pxfonts}
%
\makeatletter
\let\@font@warning\my@@font@warning
\makeatother 

% Palatino: 5% mehr Zeilendurchschuss (laut KOMA-skript)
\linespread{1.05}

% Satzspiegel neu berechen
\recalctypearea

% Figures unabhängig vom Kapitel zählen
\makeatletter
\@removefromreset{figure}{chapter}
\renewcommand{\thefigure}{\arabic{figure}}
\@removefromreset{table}{chapter}
\renewcommand{\thetable}{\arabic{table}}
\makeatother

% Disable single lines at the start of a paragraph (Schusterjungen)
\clubpenalty = 10000
%
% Disable single lines at the end of a paragraph (Hurenkinder)
\widowpenalty = 10000 \displaywidowpenalty = 10000

% Durchgestrichene Tabellenzeilen
% wie machen?
\makeatletter
\def\stline{%
  \noalign{\vskip-.7em\vskip-\arrayrulewidth\hrule \@height \arrayrulewidth\vskip.7em}}
\makeatother

\DeclareMathOperator{\Aut}{Aut}
\DeclareMathOperator{\Out}{Out}
\DeclareMathOperator{\GL}{GL}
\DeclareMathOperator{\SL}{SL}
\DeclareMathOperator{\PSL}{PSL}
\DeclareMathOperator{\Stab}{Stab}
\newcommand{\Id}{\mathrm{Id}}
\DeclareMathOperator{\Kern}{Kern}
\DeclareMathOperator{\NT}{NT}
\DeclareMathOperator{\Diag}{Diag}
\DeclareMathOperator{\Sym}{Sym}
\newcommand{\da}{\coloneqq}
\newcommand{\ad}{\eqqcolon}
\newcommand{\Z}{\mathds Z}
\newcommand{\N}{\mathds N}
\newcommand{\ev}{\mathds 1}
\newcommand{\ep}{\varepsilon}

\newcommand{\llangle}{\langle\!\langle}
\newcommand{\rrangle}{\rangle\!\rangle}

\SetKwFunction{Len}{len}
\SetKwFunction{Coincidence}{Coincidence}
\SetKwFunction{NewCoset}{NewCoset}
\SetKwFunction{AccA}{AccA}
\SetKwFunction{pop}{pop}
\SetKwFunction{push}{push}

\hyphenation{Karls-ruhe}

\author{Joachim Breitner}
\title{Loop subgroups of $F_r$ and the images of their stabilizer subgroups in $\GL_r(\Z)$}

\begin{document}
%\KOMAoptions{twoside=false}
\begin{titlepage}
\centering
\makeatletter
\textsc{\Large{Karlsruher Institut für Technologie}}\\
\vspace{.5em}
\textsc{\Large{Fakultät für Mathematik}} \\
\vspace{4em}
{\Large \@author} \\
\vspace{2em}
{\large Diploma Thesis}\\
\vspace{2.5em}
{\sectfont\huge \@title }\\
\vfill
\begin{tikzpicture}[auto]
\draw (0,0) node[state,accepting,draw,circle] (1) {$U$};
\begin{scope}[xshift=2cm]
\path (1) --
      (canvas polar cs:radius=2cm, angle=60) node[state,draw,circle] (2) {$y^1U$} --
      (canvas polar cs:radius=2cm, angle=-60) node[state,draw,circle] (3) {$y^2U$};
\draw[->] (canvas polar cs:radius=2cm, angle=160) arc(160:120:2cm) node[above] {$y$} arc(120:80:2cm);
\draw[->] (canvas polar cs:radius=2cm, angle=40) arc(40:0:2cm) node[right] {$y$} arc(0:-40:2cm);
\draw[->] (canvas polar cs:radius=2cm, angle=-80) arc(-80:-120:2cm) node[below] {$y$} arc(-120:-160:2cm);
\draw[->] (2) edge [in=45,out=75,loop] node {$z,x$} (2);
\draw[->] (3) edge [in=-75,out=-45,loop] node {$z,x$} (3);
\end{scope}
\begin{scope}[xshift=-2cm]
\path (1) --
      (canvas polar cs:radius=2cm, angle=120) node[draw,circle] (2) {$x^1U$} --
      (canvas polar cs:radius=2cm, angle=-120) node[draw,circle] (3) {$x^2U$};
\draw[->] (canvas polar cs:radius=2cm, angle=20) arc(20:60:2cm) node[above] {$x$} arc(60:100:2cm);
\draw[->] (canvas polar cs:radius=2cm, angle=140) arc(140:180:2cm) node[left] {$x$} arc(180:220:2cm);
\draw[->] (canvas polar cs:radius=2cm, angle=-100) arc(-100:-60:2cm) node[below] {$x$} arc(-60:-20:2cm);
\draw[->] (2) edge [in=105,out=135,loop] node {$z,y$} (2);
\draw[->] (3) edge [in=225,out=255,loop] node {$z,y$} (3);
\end{scope}
\draw[->] (1) edge [loop left] node {$z$} (1);
\end{tikzpicture} \\
\vfill
Supervisors: \\
Prof. Dr. Frank Herrlich \\
Dr. Gabriela Schmithüsen \\
\vspace{2em}
{\large \@date }
\makeatother
\end{titlepage}
%\KOMAoptions{twoside=true}

\chapter*{Preface}

\lettrine[nindent=0ex]T{he} abelianization of the free group over $r$ generators is a group homomorphism $F_r \to \Z^r$. Its kernel is a characteristic subgroup of $F_r$ and thus, this map gives rise to a map between the respective automorphism groups
\[
B\colon \Aut(F_r) \to \GL_r(\Z).
\]
This homomorphism can also be given explicitly. It maps each automorphism $\gamma\in \Aut(F_r)$ to an integral matrix by counting the number of occurrences of each generator in the image of each generator: If $g_1,\ldots,g_r$ are the generators of the free group, this means
\[
\gamma \mapsto \big(\#_{g_i}\,\gamma(g_j)\big)_{i,j=1\ldots r}\,.
\]

In the study of imprimitive translation surfaces, especially origamis \cite{Sch05}, this map is used to obtain Veech groups. Each origami can be associated with a subgroup $U\le F_2$ of finite index. The image of the stabilizer group of $U$ in $\Aut(F_2)$ under $B$, intersected with $\SL_2(\Z)$, gives the Veech group of the origami.
In the case of origamis, an interesting question is which subgroups of $\SL_2(\Z)$ occur as Veech groups. There is a positive answer for many congruence subgroups (see \cite{Sch05}), and for all subgroups of the principal congruence group of level 2 (see \citep[Theorem 1.2]{ellenberg-2009}).

The construction of a Veech group can be generalized to subgroups of $F_r$ for a general $r\in\N$ instead of origamis. For rank of 3 or higher,  there is a reason to hope that these groups will be easier to understand, as every normal subgroup of $\SL_r(\Z)$ besides $\{I\}$ and $\{I,-I\}$ is a congruence group and thus can be thought of as a subgroup of $\SL_r(\Z/l\Z)$, where $l$ is the congruence level of the subgroup \citep[Theorem 4-4.2]{Sury}.

To investigate this situation, we implemented an algorithm called \emph{CosetProject} that projects a subgroup of $\Aut(F_r)$ to $\GL_r(\Z)$ and detects its congruence level. Together with the algorithm implemented in \cite{Frei08}, which calculates the stabilizer group of a subgroup of $F_r$ in $\Aut(F_r)$, it can be used to detect the congruence level of a Veech group. The algorithm is described in detail in \cref{cosetproject}.

Following these investigations, a certain class of subgroups of $F_r$ arose my interest. I dubbed them \emph{loop subgroups}, due to the appearance of their coset graphs. These are generalizations of the L-origamis, but their analogs to the Veech groups show very different behavior. They are studied in \cref{loopsubgroups}, where the image of their stabilizer group under the map $B$ is calculated. Because of the similar results, the index two subgroups are treated in the same manner in \cref{index2}.

\vfill
\lettrine[nindent=1ex]I{} owe sincere thanks to Dr.\ Gabriela Schmithüsen, under whose guidance this thesis was created. She was always generous with time, advice, regular proof-reading, ideas and inspiration.

Moreover, I wish to thank Mareike Schmidtobreick and Pascal Maillard for proof-reading the final work.



\tableofcontents
{
\let\cleardoublepage\relax  % book
\let\clearpage\relax        % report
\let\chapter\section
\parskip1pt
\listofalgorithms
}
\chapter{Fundamentals}

\lettrine[nindent=0pt]T{he} document at hand does not require very deep mathematical knowledge. Readers familiar with concepts taught in foundations courses – groups, homomorphisms, matrices – should be able to read this thesis with little effort. Some definitions that slightly extend beyond this basic knowledge, such as the group of automorphisms, finitely presented groups and the coset graph, are explained briefly in this chapter. Also, the pseudocode notation used for the algorithms is explained.

\section{The automorphism group}

One of the main objects of interest is $\Aut(F_r)$, the automorphism group of the free group of rank $r$. 

\begin{definition}[Automorphism group]
Let $G$ be a group. Denote with $\Aut(G)$ the set of automorphisms of $G$, i.e.\ the bijective homomorphisms from $G$ to $G$. This set becomes a group, called the \emph{automorphism group of $G$}, when equipped with the function concatenation $\circ$ as the group operator.
\end{definition}

\begin{remark}
Because abelian groups are $\Z$-modules, one can identify the automorphisms of the group $\Z^r$ with the group of integral, invertible matrices of rank~$r$:
\[
\Aut(\Z^r) = \GL(\Z^r) = \GL_r(\Z)
\]
\end{remark}

\begin{definition}[Stabilizer group]
For a subgroup $U\le G$, the \emph{stabilizer subgroup} is defined as the set of automorphisms that map $U$ to $U$:
\[
\Stab_{\Aut(G)}(U) \da \{\gamma \in \Aut(G) : \gamma(U) = U\}.
\]
\end{definition}

\begin{definition}
A subgroup $U\le G$ is called \emph{characteristic} if it is left invariant under all automorphisms of $U$, i.e.\ $\forall \gamma\in\Aut(G): \gamma(U) = U$. In other words, $U\le G$ is called characteristic if $\Stab_{\Aut(G)}(U) = \Aut(G)$.
\end{definition}

\begin{remark}
Let $\varphi \colon G \to G'$ be a surjective group homomorphism such that $\Kern\varphi$ is a characteristic subgroup of $G$. This homomorphism naturally gives rise to a homomorphism $\hat\varphi\colon \Aut(G) \to \Aut(G')$, defined by
\[
\hat\varphi(\gamma)(g') = \varphi(\gamma(g)) \text{ with } g\in \varphi^{-1}(g')
\]
for $\gamma\in \Aut(G)$, $g'\in G'$.

This definition is sound: If $g_1,g_2 \in \varphi^{-1}(g')$, then $g_1g_2^{-1}\in \Kern\varphi$. Therefore,
\[
\varphi(\gamma(g_1))\cdot \varphi(\gamma(g_2^{-1})) = \varphi(\gamma(g_1g_2^{-1})) \in \varphi(\gamma(\Kern\varphi)) = \varphi(\Kern\varphi) = \{\Id\}
\]
and hence $\varphi(\gamma(g_1)) = \varphi(\gamma(g_2))$.
\end{remark}

The kernel of the map $F_r\to \Z^r$ mentioned in the preface is, by definition of abelianization, the commutator subgroup $[F_r,F_r]$ of the free group. Every commutator subgroup is characteristic. This justifies the introduction of the map $B\colon \Aut(F_r) \to \GL_r(\Z)$.

\section{The free group}

\begin{definition}[Free group]
The \emph{free group} $F_r$ of rank $r$ with generators $g_1,\ldots,g_r$ is the set of words over the alphabet $\{g_1^{},\ldots,g_r^{},g_1^{-1},\ldots,g_r^{-1}\}$, considering two words equal if they can be reduced to the same word by means of canceling $g_ig_i^{-1}$ and $g_i^{-1}g_i$. The group operation is the concatenation of words.
\end{definition}

The empty word is the identity of the group $F_r$, and in the following denoted by $\Id$.

\begin{example}
In $F_3$ with generators $g_1,g_2,g_3$, the following identities hold:
\begin{gather*}
(g_1 g_2^{-1} g_3^{-1})^{-1} = g_3 g_2 g_1^{-1}\\
g_1 = g_1 g_2^{-1} g_2 = (g_2^{-1} g_1)^{-1} g_2\\
(g_1 g_2 g_3^{-1}) \cdot (g_3 g_2^{-1} g_1^{-1}) = \Id.
\end{gather*}
\end{example}

An equivalent definition of the free group $F_r$ with generators $g_1,\ldots,g_r$ is the universal property of the free group:

\begin{remark}[Universal property of the free group]
\strut\\
\label{prop:uae}For any group $G$ and map \mbox{$f\colon \{g_1,\ldots,g_r\} \to G$}, there is exactly one group homomorphism $\varphi\colon F_r \to G$ such that $\varphi(g_i) = f(g_i)$ for $i=1,\ldots,r$.
\end{remark}

A useful consequence of this property is that group homomorphisms $F_r \to G$ can be sufficiently specified by stating the images of the generators of $F_r$. Naturally, this includes automorphisms of the free group.

\begin{example}
For $i\in\{1,\ldots,r\}$, the map
\[
\#_{g_i}\colon F_r \to \Z
\]
is defined by its images of the generators of $F_r$:
\[
\#_{g_i}(g_k) \da 
\begin{cases}
1, & k = i \\
0, & k \ne i.
\end{cases}
\]
It is the generator-counting map which calculates the number of occurrences of the generator $g_i$ in a word $w\in F_r$, counting negative powers of $g_i$ negatively.
\end{example}

\begin{remark}
Every finitely generated group $G=\langle h_1,\ldots,h_r\rangle$ is isomorphic to a quotient group of the free group of rank $r$.
\end{remark}

\begin{proof}
By the universal property of the free group, the mapping $g_i \mapsto h_i$ defines a group homomorphism $\varphi\colon F_r \to G$. This homomorphism is surjective, so by the fundamental homomorphism theorem, we have 
\[
\faktor{F_r}{\ker \varphi} \cong G.
\]
\end{proof}

\begin{definition}[Finitely presented group]
Let $F_r$ be the free group of rank $r$ and generators $g_1,\ldots,g_r$, and $R = \{r_1,\ldots,r_s\} \subset F_r$ be a finite subset of $F_r$, called the relations. Then $\langle g_1,\ldots,g_r\mid r_1,\ldots,r_s\rangle$ is called a \emph{finite presentation} of the group
\[
\faktor{F_r}{\llangle R \rrangle},
\]
where
\[
\llangle R \rrangle \da \bigcap_{\substack{N\vartriangleleft F_r\\ R\subset N}} N
\]
is the normal closure of the set $R$.

Any group that has a finite presentation is called a \emph{finitely presented group}.
\end{definition}

Usually, the symbols used as generators in the presentation are interchangeably used for the group element they represent.

The free groups of finite rank are trivially finitely presented. Many other important groups – $\Aut(F_r)$, the matrix groups $\GL_r(\Z)$ and $\SL_r(\Z)$ – are also finitely presented. This is fortunate, as these groups can then be investigated computationally.

\begin{example}
The modular group is a finitely presented group:
\[
\PSL_2(\Z) = \faktor{\SL_2(\Z)}{\{I,-I\}} = \langle S, T\mid S^2, (ST)^3 \rangle.
\]
The symbols $S$ and $T$ represent the matrices
$
\big(
\begin{smallmatrix}
\phantom-0 & 1 \\
-1 & 0 
\end{smallmatrix}
\big)
$ respectively $
\big(
\begin{smallmatrix}
1 & 1 \\
0 & 1 
\end{smallmatrix}
\big)
$.
\end{example}

\begin{example}
\label{slrzpres}\label{elementarymatrices}\citep[Theorem 4-3.2]{Sury} The integral special linear group $\SL_r(\Z)$, $r\ge3$, is generated by the \mbox{$r\cdot(r-1)$} symbols $X_{ij}$, $i,j\in\{1,\ldots,r\}$, $i\ne j$, subject to the relations
\begin{gather*}
[X_{ij},X_{jk}] = X_{ik}  \text{ for } i\ne k\\
[X_{ij},X_{kl}] = \Id  \text{ for } j\ne k,\, i\ne l\\
(X_{12}X_{21}^{-1}X_{12})^4 = \Id,
\end{gather*}
where $[\alpha,\beta] \da \alpha\beta\alpha^{-1}\beta^{-1}$ denotes the commutator bracket. The symbol $X_{ij}$ represents the elementary matrix $X_{ij}$, i.e.\ the $r\times r$-matrix with ones on the diagonal, one additional one in the $i$-th row and $j$-th column and zeroes everywhere else.
\end{example}

Any element of a finitely generated group $G$ with $r$ generators can be represented by a word in the generators and their inverses, which the computer can treat as a list of numbers from the set $\{-r,\ldots,-1, 1,\ldots,r\}$, where the positive numbers correspond to the generators of the group and the negative numbers to their inverses.
%
In the following, I will at times use a word in the generators of $G$ as an element of $G$, an element of $F_r$ and as a list of generators.

\section{The coset graph}

The most natural way to specify a subgroup $U$ of a group $G$, i.e.\ a subset that is itself again a group, is by a defining property. For example, a point-stabilizer subgroup of the symmetric group can be written as
\[
\Stab_{S_n}(1) = \{ \pi \in S_n \mid \pi(1)=1\}.
\]

Another way of specifying subgroups is by a set of subgroup generators: If $H\subset G$ is a subset of the group, then
\[
\langle H \rangle \da \bigcap_{\substack{U \le G\\ H \subset U}} U
\]
is the smallest subgroup containing $H$ and is called the subgroup generated by $H$.

% Analogously, one defines the normal closure 
% \[
% \llangle H \rrangle  \da \bigcap_{\substack{N \vartriangleleft G\\ H \subset N}} N
% \]
% as the smallest normal subgroup containing $H$.

While these methods are often convenient to define subgroups, they are not necessarily useful when working with subgroups, especially when applying computational methods to them. Therefore, where possible, it can be useful to describe a subgroup by its coset graph. In this document, we will work with left cosets and will not always mention this fact. Of course, it is possible to work with right cosets in an analogous manner.

\begin{definition}[Coset graph]
The \emph{coset graph} of a subgroup $U$ of a finitely generated group $G$ with generators $g_1,\ldots,g_r$ is the directed multigraph with the left cosets \mbox{$\{ w U \mid w \in G\}$} of $U$ as nodes and, for each coset $w U$ and generator $g_i$, one edge from $w U$ to $g_iw U$, labeled $g_i$. 
\end{definition}

When convenient, one can also add edges labeled by the inverses of the generators. 

\begin{figure}
\centering
\begin{tikzpicture}[auto]
\node[state,draw,circle,accepting] (1) at (canvas polar cs:radius=3cm, angle=90) {$U_0$};
\node[state,draw,circle] (2) at (canvas polar cs:radius=3cm, angle=0) {$U_1$};
\node[state,draw,circle] (3) at (canvas polar cs:radius=3cm, angle=-90) {$U_2$};
\node[state,draw,circle] (4) at (canvas polar cs:radius=3cm, angle=-180) {$U_3$};
\draw[->] (canvas polar cs:radius=3cm, angle=75) arc(75:45:3cm) node[right] {$(1\,2\,3\,4)$} arc(45:15:3cm);
\draw[->] (canvas polar cs:radius=3cm, angle=-15) arc(-15:-45:3cm) node[right] {$(1\,2\,3\,4)$} arc(-45:-75:3cm);
\draw[->] (canvas polar cs:radius=3cm, angle=-105) arc(-105:-135:3cm) node[left] {$(1\,2\,3\,4)$} arc(-135:-165:3cm);
\draw[->] (canvas polar cs:radius=3cm, angle=165) arc(165:135:3cm) node[left] {$(1\,2\,3\,4)$} arc(135:105:3cm);
\draw[->] (1) edge [loop below] node {$(1\,2)$} (1);
\draw[->] (2) edge[out=-160,in=70,shorten >=2.6mm,shorten <=2.6mm] node[left] {$(1\,2)$} (3);
\draw[->] (3) edge[out=20,in=-110,shorten >=2.6mm,shorten <=2.6mm] node[left] {$(1\,2)$} (2);
\draw[->] (4) edge [loop right] node {$(1\,2)$} (1);
\end{tikzpicture}
\caption{The coset graph of $S_3\le S_4$}
\label{fig:S3S4}
\end{figure}

\begin{example}
\label{ex:S3S4}
The coset graph of $S_3$ as a subgroup of $S_4$ with respect to the generators $(1\,2)$ and $(1\,2\,3\,4)$ is depicted in \vref{fig:S3S4}. The nodes are numbered for readability. The corresponding cosets are:
\begin{align*}
U_0 &\da S_3 \\
U_1 &\da (1\,2\,3\,4) \cdot S_3 \\
U_2 &\da (1\,3)(2\,4) \cdot S_3 \\
U_3 &\da (1\,4\,3\,2) \cdot S_3 
\end{align*}
\end{example}

\begin{remark}
\label{rem:cosetgraphs}Let $U\le G$.
\begin{enumerate}
\item The coset graph of $U$ is a connected, regular graph of degree $2\cdot r$, as every node has $r$ outgoing and $r$ ingoing edges.

\item The number of nodes in the coset graph of $U$ is $[G:U]$. Therefore, the graph is finite if and only if $U$ has finite index.

We can see in \vref{fig:S3S4} that $[S_4:S_3]=4$
\item The node labels are not essential and can be omitted as long as one remembers which node, called the \emph{origin}, represents the subgroup itself. Using another node to represent the subgroup gives the coset graph of a conjugate of the subgroup. The coset graph of every subgroup conjugate can be obtained this way.

We can see in \vref{fig:S3S4} that $S_3$ is not normal in $S_4$: The coset graph of $S_3$ looks different when using $U_1$ as the origin, therefore $S_3 \ne (1\,2\,3\,4) S_3 (1\,2\,3\,4)^{-1}$.

\item The Cayley graph of $G$ is the coset graph of the trivial subgroup $\{\Id\}\le G$. % If $G$ is finite, the multiplication table is the Cayley graph of $G$ with regard to the whole group as a generating set.
\end{enumerate}
\end{remark}

In the computational part of this thesis, we will often trace elements of the group, i.e.\ a word in the generators, in the graph. This is best explained by example. Tracing the permutation $(1\,2)^{-1}(1\,2\,3\,4)(1\,2)$ in \vref{fig:S3S4}, starting at the node $U_0$, ends up at the node $U_2$: Looking at the generators in the word from the right, we first have $(1\,2)$. The edge with that label from $U_0$ is reflexive, so we stay in node $U_0$. The next generator is $(1\,2\,3\,4)$, so we follow the edge to $U_1$. The final generator is an inverse, so we have to traverse the edge from $U_2$ to $U_1$ labeled $(1\,2)$ in the opposite direction.

This way, once we have a coset graph for a subgroup $U\le G$, we can for a word $w\in G$ and a coset $vU$ determine the coset $wvU$. This gives us a procedure to determine the subgroup membership problem $w\in U$ for a word $w\in G$: We have $w\in G$ if and only if tracing that word from the coset $U$ ends up in the coset $U$.

In the following chapter, the coset graph is represented by a coset table, which has the adjacency lists of the nodes as rows. It has one row for each coset $vU$, one column for each generator $g_i$ and entries referring to the number of the row of $g_ivU$. As an optimization measure, columns for the inverses of generators are also added.

\section{Pseudocode notation}

The next chapter contains a series of algorithms, written in pseudocode. The syntax is mostly self-explanatory.

The main body of each algorithm extends from the declaration of input and output to the \KwSty{return} statement, possible functions are declared afterward. The statement \KwSty{forall} $x\in S$ executes the body of the statement once for each element of $S$, with the variable $x$ bound to that value.

Variables are assigned using the $\leftarrow$ operator, which corresponds to $\da$ in Pascal-like programming languages. The statement $a \leftarrow b \leftarrow c$ is short for $b \leftarrow c;\ a\leftarrow b$. The equals-to symbol $=$ is exclusively used for comparisons.

Array access is zero-based, i.e. $A[0]$ is the first entry of the array and $A[\Len(A)-1]$ is the last entry. Tables are written as arrays of arrays, so $C[0][0]$ is the entry in the first row and first column, while $C[3][2]$ is the entry in the forth row and third column. Therefore, $\Len(C)$ denotes the number of rows in the table. For convenience, at times we say that a table has columns “labeled by the elements of the set $X$”. In that case, $X$ is finite and there is an implicit numbering of these elements. The expression $C[0][x]$ stands for $C[0][i]$ where $i$ is the implicit number of $x$.

\chapter{The CosetProject algorithm}
\label{cosetproject}

\lettrine As outlined in the preface, we are interested in applying the map $B$, as defined in the preface, to the stabilizer subgroup of a finite index subgroup $U\le F_r$.

For the first step, we can use Algorithm 6 in \cite{Frei08}. Its input is a finite index subgroup $U\le F_r$, given by a list of Nielsen-reduced generators. The algorithm calculates the stabilizer group $\Stab_{\Aut(F_r)}(U)$ of the subgroup and returns
{\parskip0pt
\begin{itemize}
\item a list of generators of the stabilizer group,
\item a list of representatives of the cosets of the stabilizer group or
\item the coset graph of the automorphism group.
\end{itemize}
}
\cite{Frei08} also contains variants of this algorithm optimized for efficiency.

This algorithm needs a set of generators of $\Aut(F_r)$. Freidinger suggests that the generating set $\tau_1,\,\sigma_{1\,2},\,\sigma_{2\,3},\ldots,\sigma_{r-1\,r},\,\eta$ (cf.\ \citep{AFV}) is beneficial for the run time efficiency of her algorithms. See \vref{tab:autfrgens} for the definitions of these generators. Note that each of these are self-inverse. An automorphism as returned by her algorithm is represented by their image of the generators of $F_r$ as well as a decomposition in these generators of $\Aut(F_r)$.

\begin{table}[hbtp]
\begin{align*}
\tau_i(g_k) =
\begin{cases}
g_i^{-1}, & k= i \\
g_k,      & k\ne i
\end{cases} &&
\sigma_{i\,j}(g_k) =
\begin{cases}
g_j, & k=i \\
g_i, & k=j \\
g_k, & k\ne i,j
\end{cases} &&
\eta(g_k) = 
\begin{cases}
g_2^{-1}g_1, & k=1 \\
g_2^{-1}, & k=2 \\
g_k, & k>2
\end{cases}
\end{align*}
\caption{A system of generators of $\Aut(F_r)$}
\label{tab:autfrgens}
\end{table}

\section{First approach: Todd-Coxeter}

Given $\Stab_{\Aut(F_r)}(U)$, the task is to calculate $\Gamma \da B(\Stab_{\Aut(F_r)}(U))\le \GL_r(\Z)$ and $\Gamma' \da \Gamma \cap \SL_r(\Z) \le \SL_r(\Z)$. For the latter group, generators and relations are given in \citep[Theorem 4-3.2]{Sury} (see \vref{slrzpres}). This allows the use of the very general Todd-Coxeter algorithm, which calculates a coset graph of a subgroup of finite index in any finitely generated group. \cite{ToddCoxeter}.

The variant of the algorithms described here is very close to the original algorithm from 1936, which was obviously designed to be carried out by hand. A serious implementation as a computer program would involve a number of optimizations, such as constructing the relation tables on demand or special-casing involutory constructors. \cite{Leech}

\subsection{Description of the algorithm}

\begin{algorithm}
\caption{Todd-Coxeter algorithm}
\label{algo:toddcoxeter}
\dontprintsemicolon
\KwIn{Group $G$ given by generators $(g_i)_{i=1,\ldots,r}$ and relations $R$}
\KwIn{Subgroup $U\le G$ given by the set of generators $H$}
\KwOut{A coset table of $U\le G$}
\BlankLine
Let $X$ be the set of generators and their inverses.\;
$C \leftarrow$ empty table with $2r$ columns labeled by the elements of $X$ and one row\; 
\ForAll{$w \in R$}{
	$R_w \leftarrow$ empty table with \Len{$w$}+1 columns and one row\;
	$R_w[0][0] \leftarrow R_w[0][\Len(w)] \leftarrow 0$\;
}
\ForAll{$h \in H$}{
	$U_h \leftarrow$ empty table with \Len{$h$}+1 columns and one row\;
	$U_h[0][0] \leftarrow U_h[0][\Len(h)] \leftarrow 0$\;
}
\BlankLine

\While{there is a table $T_w\in\{U_h, h\in H\} \cup \{R_w, w\in R\}$ with an empty spot}{
	Let $i$ be a row that is not complete and $j$ the column of the first empty spot.\;
	$k \leftarrow T_w[i][j-1]$\;
	$g \leftarrow w[\Len(w)-(j+1)]$\;
	\If{$C[k][g]$ is not set}{
		$l\leftarrow $\Len{$C$}\;	
		Extend each of the tables $C$ and $R_w$, $w\in R$ by one row, the $l$-th.\;
		$C[k][g] \leftarrow l$\;
		$C[l][g^{-1}] \leftarrow k$\;
		\lForAll{$w \in R$}{
			$R_w[l][0] \leftarrow R_w[l][\Len(w)] \leftarrow l$\;
		}
	}
	$T[i][j] \leftarrow l \leftarrow C[k][g]$\;
	{
		\If{$T[i][j+1]$ is set}{
			$m\leftarrow T[i][j+1]$\;
			$\bar g \leftarrow w[\Len(w)-j]$\;
			\lIf{$C[l][\bar g]$ is not set}{
				$C[l][\bar g] \leftarrow m$\;
			}\;
			\lIf{$C[m][\bar g^{-1}]$ is not set}{
				$C[m][\bar g^{-1}] \leftarrow l$\;
			}\;
			\lIf{$C[l][\bar g] \ne m$}{
				$\Coincidence(C[l][\bar g],m)$
			}\;
			\lIf{$C[m][\bar g^{-1}] \ne l$}{
				$\Coincidence(C[m][\bar g^{-1}],l)$
			}\;
		}
	}
}
\Return{C}
\BlankLine
\KwSty{function} $\Coincidence(i,j)$
\Begin{
	\lIf{$j<i$}{
		$\Coincidence(j,i)$
	}\;
	\Else{
		\ForAll{table entries $T[k][l]$}{
			\lIf{$T[k][l] = j$}{$T[k][l] \leftarrow i$}
		}
		\ForAll{$g\in X$}{
			\If{$C[j][g]$ is set}{
				\lIf{$C[i][g]$ is not set}{$C[i][g] \leftarrow C[j][g]$}\;
				\lIf{$C[i][g] \ne C[j][g]$}{$\Coincidence(C[i][g],C[j][g])$\; }

			}
		}
	}
}
\end{algorithm}

The pseudocode listing \vref{algo:toddcoxeter} outlines the Todd-Coxeter algorithm. The input to the algorithm is provided as a list of relations $R$ of the group $G$, written as words in the generators of the group, and a list of generators $H$ of the subgroup $U$, also written as words in the generators of the whole group.

It works with three types of tables:
\begin{enumerate}
\item A left coset table $C$, with the columns labeled by the generators and their inverses and the rows labeled by the coset numbers.
\item For each relation $w$ in the presentation of the group $G$, a relation table $R_w$ with columns labeled by the letters of the word $w$ and rows labeled by the coset numbers.
\item For each generator $h$ of the subgroup, a generator table $U_h$ with columns labeled by letters of the word $h$ and exactly one row, labeled by $0$.
\end{enumerate}
The entries of these tables are cosets of the subgroup $U$, represented by natural numbers. The coset $\Id\cdot U$ has the number 0, other numbers are added as required. Let $U_i$ denote the coset represented by $i$. For convenience, an unlabeled zeroth column is added to the latter two tables, whose entries contain the coset number of the respective row.

The semantics of the coset table is as follows: If the entry $C[i][g]$ in the $i$-th row and the column labeled by the generator or inverse of a generator $g$ is set, then multiplying the generator $g$ with the coset represented by $i$ gives the coset with number $C[i][g]$: 
\[
U_{C[i][g]} = g\cdot U_i.
\] Storing this information about both generators and inverses of generators is redundant, but convenient.

For the other tables the semantics is as follows: Let $T_w$ be the table corresponding to the relation or generator $w$. If both $T[i][j]$ and $T[i][j+1]$ are set, then multiplying the generator $w[\Len(w)-(j+1)]$, which is the $j$-th last letter in the word $w$, with the coset represented by $T[i][j]$ gives the coset with number $T[i][j+1]$:
\[
U_{T[i][j+1]} = w[\Len(w)-(j+1)] \cdot U_{T[i][j]}
\]
We have to reverse the words because we are working with left cosets. When working with right cosets, this is not necessary.

Missing entries in these tables will now be filled sequentially, adding new coset numbers as required and merging coset numbers when known to represent the same coset, until the table $C$ is filled completely and fully determines  the subgroup $U$. The other tables can then be discarded and $C$ is returned.

Upon initialization, the tables are generated and an initial row 0, representing the coset $\Id\cdot U$, is added. For the relation and generator tables, the zeroth column of the row is set to 0. Also, the last column is set to zero, as $w\cdot U = U$ for $w\in R$ and $h\cdot U = U$ for $h\in H$.

As long as there is an empty entry in the relation or generator tables, it is filled. If the necessary information is already contained in the coset table, it is used. Otherwise, a new coset number is created. For this, the coset table and the relation tables are extended by an additional row. Both the first and last entry in the new row in the relation tables is set to the number of the new coset, as $w\cdot U_i = U_i$ for a relation $w\in R$ and a coset $U_i$. The coset table is amended with this information. Note that we do not extend the generator tables, as in general $h \cdot U_i \ne U_i$ for a generator $h\in H$ of the subgroup. If we did this, we would treat them just like group relations and effectively calculating the coset graph of  $\llangle H\rrangle$, the normal closure of $U$, instead of $\langle H \rangle$.

If we complete a row of a relation or generator table this way, since the last column of the row is already known, we find a new bit of information: Let $w$ be the relation or generator of the table, $\bar g$ the first letter of the word $w$ and $i$ the number of the row. If we have just put $k$ in the penultimate entry in the row, then we know that $\bar g$ multiplied with the coset represented by $k$ gives the coset represented by $i$:
\[
U_i = \bar g \cdot U_k
\]
This is called a \emph{deduction}. If the corresponding entry $C[k][\bar g]$ (resp.\ the entry for the inverse edge in the graph) in the coset table is still empty, we set it to $i$. If the entry is already set to $l$ and differs from $i$, we know that the numbers $i$ and $l$ represent the same coset. This is called a \emph{coincidence} and is handled by the function \Coincidence.

This function replaces every occurrence of the larger coset number in the tables with the lower coset numbers. The information in the respective rows in the coset table is compared. If it disagrees, a new coincidence was found, and the function is called recursively. The row of the larger coset number is deleted from the tables (without changing the indexes of the following rows).

Eventually, all entries in the tables (ignoring deleted rows) have been filled. Therefore, $C$ contains the full coset table of $U$ and is returned. In practice, one might want to compress the table by moving the rows “up” to fill the empty spots left over by deleted lines before returning it.


\subsection{An example application of the Todd-Coxeter algorithm}

We want to derive the coset graph of $S_3 \le S_4$, as seen in \vref{fig:S3S4}. The representation
\[
\langle B,C \mid B^2,\, C^4,\, (B C)^3,\, (BC^{-1}BC)^3\rangle
\]
is given in \citep{SymPres}, along with presentations for other symmetric groups and alternating groups. The symbols $B$ and $C$ represent the permutations $(1\,2)$ and $(1\,2\,3\,4)$ respectively. In our case of $S_4$, this can be reduced further to
\[
\langle B,C \mid B^2,\, C^4,\, (B C)^3\rangle
\]
as $(BC^{-1}BC)^3 \in \llangle B^2,\, C^4,\, (B C)^3\rrangle$ (this can be verified by some lengthy manual calculations\footnote{
\raggedright
$(BC^{-1}BC)^3 =
B^2 (B^2 (((B^2 ((B^2   (C^4)^B   (((BC)^3)^{-1})^B)^{C B^{-1}} B^2 C^4)^{C^{-1} B} (((BC)^3)^{-1})^B)^{C B^{-1}} B^2 C^4)^{C^{-1}})^B\allowbreak(((BC)^3)^{-1})^B)^{C B} \allowbreak 
(B^2 (B^2 (B^2 ( ((BC)^3)^{-1})^B)^{C B})^{C B})^{C^{-1}}
$ where $\beta^\alpha \da \alpha^{-1}\beta\alpha$.
} or by using a computer algebra system like \citep{GAP}). The subgroup generators $(1\,2)$ and $(1\,2\,3)$ of $S_3$ are represented by the words $B$ and $C^{-1}BC^{2}$.

For the Todd-Coxeter algorithm, we create six tables: The coset table $C$, the three relations tables $R_{B^2}$, $R_{C^4}$ and $R_{(BC)^3}$ and the subgroup generator tables $U_B$ and $U_{C^{-1}BC^2}$, initialized as shown in \vref{tab:tcex1}.


\begin{table}
\tabcolsep=1.1pt
\begin{center}
\begin{tabular}[t]{l|llll}
$C$ & $B$ & $B^{-1}$ & $C$ & $C^{-1}$ \\
\hline
$0$ &     &          &     & 
\end{tabular}
\hfill
\begin{tabular}[t]{l|ll}
$R_{B^2}$ & $B$ & $B$  \\
\hline
$0$      &     & $0$   
\end{tabular}
\hfill
\begin{tabular}[t]{l|llll}
$R_{C^4}$ & $C$ & $C$ & $C$ & $C$  \\
\hline
$0$      &      &     &     & $0$
\end{tabular}
\hfill
\begin{tabular}[t]{l|llllll}
$R_{(BC)^3}$ & $C$ & $B$ & $C$ & $B$ & $C$ & $B$  \\
\hline
$0$      &      &     &     &    &   & $0$
\end{tabular}
\hfill
\begin{tabular}[t]{l|l}
$U_{B} $ & $B$ \\
\hline
0 & 0
\end{tabular}
\hfill
\begin{tabular}[t]{l|llll}
$U_{C^{-1}BC^2} $ & $C$ & $C$ & $B$ & $C^{-1}$ \\
\hline
0 &   &   &   & 0 
\end{tabular}
\end{center}
\caption{Todd-Coxeter tables for $S_3\le S_4$ after initialization}
\label{tab:tcex1}
\end{table}
We have a subgroup generator of length one, so the deduction $B\cdot S_3 = S_3 $ follows immediately. This special-casing of length-one relations and subgroup generators was omitted in the pseudocode listing in \cref{algo:toddcoxeter}. This deduction fills the entry $C[0][B]=0$ and its inverse direction, $C[0][B^{-1}]= 0$. We then proceed by filling the table $U_{C^{-1}BC^2}$. Because we have no information about $C[0][C]$, we introduce a new coset number $1$, and likewise coset $2$ and $3$. We now are in the situation of \vref{tab:tcex2}.

\begin{table}[p]
\tabcolsep=1.1pt
\begin{center}
\begin{tabular}[t]{l|llll}
$C$ & $B$ & $B^{-1}$ & $C$ & $C^{-1}$ \\
\hline
0 & 0 & 0 & 1 &   \\
1 &   &   & 2 & 0 \\
2 & 3 &   &   & 1 \\
3 &   & 2 &   &   \\
\end{tabular}
\hfill
\begin{tabular}[t]{l|ll}
$R_{B^2}$ & $B$ & $B$  \\
\hline
0 &  & 0 \\
1 &  & 1 \\
2 &  & 2 \\
3 &  & 3 \\
\end{tabular}
\hfill
\begin{tabular}[t]{l|llll}
$R_{C^4}$ & $C$ & $C$ & $C$ & $C$  \\
\hline
0 &   &   &   & 0 \\
1 &   &   &   & 1 \\
2 &   &   &   & 2 \\
3 &   &   &   & 3 \\
\end{tabular}
\hfill
\begin{tabular}[t]{l|llllll}
$R_{(BC)^3}$ & $C$ & $B$ & $C$ & $B$ & $C$ & $B$  \\
\hline
0 &   &   &   &   &   & 0 \\
1 &   &   &   &   &   & 1 \\
2 &   &   &   &   &   & 2 \\
3 &   &   &   &   &   & 3 \\
\end{tabular}
\hfill
\begin{tabular}[t]{l|l}
$U_{B} $ & $B$ \\
\hline
0 & 0
\end{tabular}
\hfill
\begin{tabular}[t]{l|llll}
$U_{C^{-1}BC^2} $ & $C$ & $C$ & $B$ & $C^{-1}$ \\
\hline
0 & 1 & 2 & 3 & 0 
\end{tabular}
\end{center}
\caption{Todd-Coxeter tables for $S_3\le S_4$ before the first coincidence}
\label{tab:tcex2}
\end{table}

The deduction from table $U_{C^{-1}BC^2}$ tells us that we have to set $C[3][C^{-1}] = 0$, which is no problem, and $C[0][C]=3$. But this table entry is already set to 1, so these coset numbers actually represent the same coset. A call to $\Coincidence(1,3)$ copies the value of $C[3][B^{-1}]$, which is 2, to $C[1][B^{-1}]$, replaces 3 by 1 everywhere and marks coset 3 as deleted. We are now in the situation of \vref{tab:tcex3}.

\begin{table}[p]
\tabcolsep=1.1pt
\begin{center}
\begin{tabular}[t]{l|llll}
$C$ & $B$ & $B^{-1}$ & $C$ & $C^{-1}$ \\
\hline
0 & 0 & 0 & 1 &   \\
1 &   & 2 & 2 & 0 \\
2 & 1 &   &   & 1 \\
3 &   & 2 &   & 0 \\
\stline
\end{tabular}
\hfill
\begin{tabular}[t]{l|ll}
$R_{B^2}$ & $B$ & $B$  \\
\hline
0 &  & 0 \\
1 &  & 1 \\
2 &  & 2 \\
3 &  & 3 \\
\stline
\end{tabular}
\hfill
\begin{tabular}[t]{l|llll}
$R_{C^4}$ & $C$ & $C$ & $C$ & $C$  \\
\hline
0 &   &   &   & 0 \\
1 &   &   &   & 1 \\
2 &   &   &   & 2 \\
3 &   &   &   & 3 \\
\stline
\end{tabular}
\hfill
\begin{tabular}[t]{l|llllll}
$R_{(BC)^3}$ & $C$ & $B$ & $C$ & $B$ & $C$ & $B$  \\
\hline
0 &   &   &   &   &   & 0 \\
1 &   &   &   &   &   & 1 \\
2 &   &   &   &   &   & 2 \\
3 &   &   &   &   &   & 3 \\
\stline
\end{tabular}
\hfill
\begin{tabular}[t]{l|l}
$U_{B} $ & $B$ \\
\hline
0 & 0
\end{tabular}
\hfill
\begin{tabular}[t]{l|llll}
$U_{C^{-1}BC^2} $ & $C$ & $C$ & $B$ & $C^{-1}$ \\
\hline
0 & 1 & 2 & 1 & 0 
\end{tabular}
\end{center}
\caption{Todd-Coxeter tables for $S_3\le S_4$ after the first coincidence}
\label{tab:tcex3}
\end{table}

We now continue to fill the relation tables. The value $R_{B^2}[0][0]$ is already known from $C[0][B]=0$. For $R_{B^2}[1][0]$ we introduce a new coset number $4$, which is already merged with coset number $2$ when we fill the next row in the table $R_{B^2}$. We continue filling $R_{C^4}$, which leads to the introduction of coset number $5$. To fill $R_{B^2}[5][0]$, we introduce coset number 6, which allows us to fill $R_{C^4}$ completely with known information. Turning to the remaining table, $T_{(CB)^3}$, we fill the first row. For the last entry, we require a new coset 7. Now, the coset tables look as in \vref{tab:tcex4}.

\begin{table}[p]
\tabcolsep=1.1pt
\begin{center}
\begin{tabular}[t]{l|llll}
$C$ & $B$ & $B^{-1}$ & $C$ & $C^{-1}$ \\
\hline
0 & 0 & 0 & 1 & 5 \\
1 & 2 & 2 & 2 & 0 \\
2 & 1 & 1 & 5 & 1 \\
3 &   & 2 &   & 0 \\
\stline
4 & 1 & 1 &   &   \\
\stline
5 & 6 & 6 & 0 & 2 \\
6 & 5 & 5 & 7 &   \\
7 &   &   &   & 6 \\
\end{tabular}
\hfill
\begin{tabular}[t]{l|ll}
$R_{B^2}$ & $B$ & $B$  \\
\hline
0 & 0 & 0 \\
1 & 2 & 1 \\
2 & 1 & 2 \\
3 &  & 3 \\
\stline
4 &  & 4 \\
\stline
5 & 6 & 5 \\
6 & 5 & 6 \\
7 &   & 7 \\
\end{tabular}
\hfill
\begin{tabular}[t]{l|llll}
$R_{C^4}$ & $C$ & $C$ & $C$ & $C$  \\
\hline
0 & 1 & 2 & 5 & 0 \\
1 & 2 & 5 & 0 & 1 \\
2 & 5 & 0 & 1 & 2 \\
3 &   &   &   & 3 \\
\stline
4 &   &   &   & 4 \\
\stline
5 &   &   &   & 5 \\
6 &   &   &   & 6 \\
7 &   &   &   & 7 \\
\end{tabular}
\hfill
\begin{tabular}[t]{l|llllll}
$R_{(BC)^3}$ & $C$ & $B$ & $C$ & $B$ & $C$ & $B$  \\
\hline
0 & 1 & 2 & 5 & 6 & 7 & 0 \\
1 &   &   &   &   &   & 1 \\
2 &   &   &   &   &   & 2 \\
3 &   &   &   &   &   & 3 \\
\stline
4 &   &   &   &   &   & 4 \\
\stline
5 &   &   &   &   &   & 5 \\
6 &   &   &   &   &   & 6 \\
7 &   &   &   &   &   & 7 \\
\end{tabular}
\hfill
\begin{tabular}[t]{l|l}
$U_{B} $ & $B$ \\
\hline
0 & 0
\end{tabular}
\hfill
\begin{tabular}[t]{l|llll}
$U_{C^{-1}BC^2} $ & $C$ & $C$ & $B$ & $C^{-1}$ \\
\hline
0 & 1 & 2 & 1 & 0 
\end{tabular}
\end{center}
\caption{Todd-Coxeter tables for $S_3\le S_4$ before the final deduction}
\label{tab:tcex4}
\end{table}

The deduction would yield $C[7][B]=0$ and thus $C[0][B^{-1}]=7$, which is in conflict with the existing data. Therefore, $\Coincidence(0,7)$ is called and rows 0 and 7 are merged. As they disagree in the last column, $\Coincidence(5,6)$ is called, leaving only coset numbers 0, 1, 2 and 5 in place. Now, the coset table is complete. Filling the other tables with this information, as shown in \vref{tab:tcex5}, does not lead to any new deductions, so the algorithm terminates. It is easily verified that the coset table describes the coset graph as depicted in \vref{fig:S3S4}.

\begin{table}[p]
\tabcolsep=1.1pt
\begin{center}
\begin{tabular}[t]{l|llll}
$C$ & $B$ & $B^{-1}$ & $C$ & $C^{-1}$ \\
\hline
0 & 0 & 0 & 1 & 5 \\
1 & 2 & 2 & 2 & 0 \\
2 & 1 & 1 & 5 & 1 \\
{3} &   & 2 &   & 0 \\
\stline
{4} & 1 & 1 &   &   \\
\stline
5 & 5 & 5 & 0 & 2 \\
6 & 5 & 5 & 0 &   \\
\stline
7 & 0 &   &   & 6 \\
\stline
\end{tabular}
\hfill
\begin{tabular}[t]{l|ll}
$R_{B^2}$ & $B$ & $B$  \\
\hline
0 & 0 & 0 \\
1 & 2 & 1 \\
2 & 1 & 2 \\
3 &  & 3 \\
\stline
4 &  & 4 \\
\stline
5 & 5 & 5 \\
6 & 5 & 6 \\
\stline
7 &   & 7 \\
\stline
\end{tabular}
\hfill
\begin{tabular}[t]{l|llll}
$R_{C^4}$ & $C$ & $C$ & $C$ & $C$  \\
\hline
0 & 1 & 2 & 5 & 0 \\
1 & 2 & 5 & 0 & 1 \\
2 & 5 & 0 & 1 & 2 \\
3 &   &   &   & 3 \\
\stline
4 &   &   &   & 4 \\
\stline
5 & 0 & 1 & 2 & 5 \\
6 &   &   &   & 6 \\
\stline
7 &   &   &   & 7 \\
\stline
\end{tabular}
\hfill
\begin{tabular}[t]{l|llllll}
$R_{(BC)^3}$ & $C$ & $B$ & $C$ & $B$ & $C$ & $B$  \\
\hline
0 & 1 & 2 & 5 & 5 & 0 & 0 \\
1 & 2 & 1 & 2 & 1 & 2 & 1 \\
2 & 5 & 5 & 0 & 0 & 1 & 2 \\
3 &   &   &   &   &   & 3 \\
\stline
4 &   &   &   &   &   & 4 \\
\stline
5 & 0 & 0 & 1 & 2 & 5 & 5 \\
6 &   &   &   &   &   & 6 \\
\stline
7 &   &   &   &   &   & 7 \\
\stline
\end{tabular}
\hfill
\begin{tabular}[t]{l|l}
$U_{B} $ & $B$ \\
\hline
0 & 0
\end{tabular}
\hfill
\begin{tabular}[t]{l|llll}
$U_{C^{-1}BC^2} $ & $C$ & $C$ & $B$ & $C^{-1}$ \\
\hline
0 & 1 & 2 & 1 & 0 
\end{tabular}
\end{center}
\caption{Todd-Coxeter tables for $S_3\le S_4$ at the end of the algorithm}
\label{tab:tcex5}
\end{table}

\subsection{Analysis of the algorithm}

Todd and Coxeter did not explicitly specify the order in which the tables have to be filled. If the algorithm ensures that for any coset added, its row in the coset table is eventually filled, and if the index of $U$ in $G$ is finite then the algorithm is guaranteed to terminate \citep{Seress}.

A formal proof can be found in \citep{Mendelsohn}. Mendelsohn adds additional, redundant  relations to $R$, such that they form what Mendelsohn calls an “algorithmic set”: A set of relations where each generator is both the first letter of a relation and the last letter of a relation. This way, the coset table rows are guaranteed to fill eventually.

Unfortunately, a run time complexity analysis as usual of this algorithm will fail: Assume that the run time were bounded by a computable function of the size of the input. Note that the algorithm does not terminate when applied to a subgroup of infinite index. Given an arbitrary subgroup, we could use the algorithm to determine whether its index is infinite: If the algorithm runs longer than the given bound, this is the case. But this is a problem known to be unsolvable \citep[Theorem 7]{Baumslag}, therefore no such upper bound can exist \citep{Sims}.

% The unsolvability property of the finite-index-problem is a corollary to a very general and thus very interesting theorem due to Baumslag et al.\ \citep[Theorem 2]{Baumslag}. Therefore, I’d like to cite it here:
% 
% \begin{theorem} 
% Let $P$ be an algebraic property of groups (i.e.\ one that is shared by all isomorphic copies of any group that has it), and assume that there is a finitely presented group that has $P$ and that there is an integer $n$ such that no free group $F_r$ of rank $r\ge n$ has $P$; then there is a finitely presented group $G_P$ such that no effective procedure exists to determine whether the elements represented by a finite set of words in given generators of $G_P$ generate a subgroup with $P$.
% \end{theorem}

\section{Second approach: CosetProject}

Our implementation of the Todd-Coxeter algorithm, which was relatively naïve, turned out to be too slow for our purposes. Using it here is like using a sledgehammer to crack a nut: We already have the coset graph of $\Stab_{\Aut(F_r)}(U)$ available, but did not use this information. This observation led to a faster algorithm for the calculation of a coset graph of $B(\Stab_{\Aut(F_r)}(U))$.

\begin{algorithm}
\caption{CosetProject algorithm}
\label{algo:cosetproject}
\dontprintsemicolon
\KwIn{Generators $(g_i)_{i=1,\ldots,r}$ of a group $G$}
\KwIn{The coset table $C$ of a subgroup $U\le G$}
\KwIn{Relations $R$ describing the quotient group $G' \da G/\llangle R\rrangle$}
\KwOut{The coset table of the image $U'$ of $U$ in $G'$}
\BlankLine
Let $X$ be the set of generators and their inverses.\;
\ForAll{cosets numbers $i\in\{0,\ldots,\Len(C)-1\}$}{
	\If{row $i$ in $C$ is not marked as merged}{
		\ForAll{relations $w\in R$}{
			Trace $w$ in $C$ starting with coset $i$, let $j$ be the resulting coset.\;
			\lIf{$i\ne j$}{$\Coincidence(i,j)$}
		}
	}
}
Return $C$.
\BlankLine
\KwSty{function} $\Coincidence(i,j)$
\Begin{
	\lIf{$j<i$}{
		$\Coincidence(j,i)$
	}\;
	\Else{
		\ForAll{table entries $C[k][g]$}{
			\lIf{$C[k][g] = j$}{$C[k][g] \leftarrow i$}
		}
		\ForAll{$g\in X$}{
			\lIf{$C[i][g] \ne C[j][g]$}{$\Coincidence(C[i][g],C[j][g])$\; }
		}
		Mark row $j$ in $C$ as merged.
	}
}
\end{algorithm}

This algorithm, which is given in pseudocode in \vref{algo:cosetproject}, works in the general setting of projecting a subgroup $U\le G$ with a given coset table $C$ onto a quotient group $G'$ given by additional relations $R$ such that $G' = G / \llangle R  \rrangle$. Let $\pi: G \to G'$ denote the projection map. Note that $\pi$ maps cosets of $U$ to cosets of $U'\da \pi(U)$.

During the process of the algorithm, the coset table of $U$ is modified to become the coset table of $U'$. Speaking in terms of the coset graph, edges are bent to point to another coset of of $U$ that maps to the same coset of $U'$ as the previous target of the edge.

To do so, the algorithm iterates through all cosets $U_i$ of $U\le G$ and relations $w$ in the presentation of $G'$ and traces the word $w$ in the coset graph of $U$. Because $\pi(w)=\Id$ in $G'$ we have $\pi(w)\cdot \bar v\cdot \pi(U) = \bar v \cdot \pi(U)$. So if we end up at a different coset number, these numbers represent the same coset of $U'$. We replace the higher number everywhere in the tables with the lower number and mark the row of the higher number as merged, so that we can skip it in the main loop. The entries of the two rows are compared, and if they disagree, we have found the next pair of cosets of $U$ that map to the same coset of~$U'$.

\subsection{Proof of termination}
The main loop iterates through the cosets and relations, both of which are finite lists. Also the loops in the function \Coincidence loop over finite lists. For each coset $i$ the function \Coincidence is called at most once with $i$ as the second argument, as after the first loop in the body of the function, the table does not contain an $i$ anywhere. Therefore, only finitely many calls to \texttt{Coincidence} occur, and the algorithm is guaranteed to terminate.

\subsection{Proof of correctness}
Define the relation $i\sim j$ on the set of cosets of $U$ to indicate that $\Coincidence(i,j)$ has been called during the execution of the algorithm. Define the relation $\approx$ as the equivalence relation generated by $\sim$, i.e.\ its transitive, reflexive, symmetrical hull. Let cosets of $U$ that are projected to the same coset of $U'$ in $G'$ be related by $\equiv$, i.e.\ $i\equiv j \iff \pi(U_i) = \pi(U_j)$.

Note that at the beginning of the algorithm, $C$ is the coset table for $U$ in $G$, so $j = C[i][g] \iff U_j = g\cdot U_i$. As the entries of $C$ are changed, this property can be violated. Instead, we will show that at any point in the algorithm, the following invariant holds:
\[
j = C[i][g] \implies \pi(U_j) = \pi(U_{C[i][g]}) =\pi(g\cdot U_i).
\]
The invariant obviously holds at the beginning of the algorithm. 

A change to the table $C$ only happens after a call to $\Coincidence(i,j)$ with $i<j$, which replaces the value $j$ by $i$. To preserve the invariant, we want $\pi(U_i) = \pi(U_j)$ to hold, i.e.\ $i \equiv j$. The function is called on two occasions:

\begin{enumerate}[\quad{Case} 1:]
\item The main loop calls $\Coincidence(i,j)$ if there is a relation $w\in R$ such that tracing the word $w$ in the graph from node $i$ ends up in node $j$. This implies, as the invariant holds, $\pi(U_j) = \pi(w\cdot U_i)$. Since $\pi(w)=\Id$, we have $\pi(U_i) = \pi(U_j)$ and hence $i\equiv j$.

\item $i = C[i'][g]$, $j = C[j'][g]$ and $\Coincidence(i,j)$ is called from the body of a call to $\Coincidence(i',j')$. By induction on the nesting level of the calls to \Coincidence, with the base case being Case 1 from above, we know $i'\equiv j'$. $i=C[i'][g]$ indicates $\pi(g\cdot U_{i'}) = (U_i)$, and $j=C[j'][g]$ indicates $\pi(g \cdot U_{j'}) = (U_j)$. Hence we have $\pi(U_i) = \pi(g \cdot U_{i'}) = \pi(g)\cdot \pi(U_{i'}) = \pi(g) \cdot \pi(U_{j'}) = \pi(g\cdot U_{j'}) = \pi(U_j)$ and therefore $i\equiv j$.
\end{enumerate}

This proves that the invariant is never violated and also shows that the implication “$i \sim j \implies i\equiv j$” holds. Because $\approx$ is contained in every equivalence relation that contains $\sim$, “$i\approx j\implies i\equiv j$” follows.

On the other hand, “$i\equiv j \implies i\approx j$” holds as well: We have $\pi(U_i) = \pi(U_j)$ if and only if there is a word $w\in \llangle R \rrangle$ with $U_j=w\cdot U_i$. This means that $w$ is a product of conjugates of elements of $R$. Because $\approx$ is transitive, it is sufficient to assume that $w=vrv^{-1}$ is a conjugate of $r\in R$. Let $k$ be the coset reached by tracing $v^{-1}$ from $i$ in the coset graph, i.e.\ $U_k = v^{-1}\cdot U_i$, and likewise let $l$ denote the coset with $U_l = r\cdot U_k = r\cdot v^{-1}\cdot U_i$. At some point in the main loop of the algorithm, the relation $r$ is traced from the coset $k$, $\Coincidence(l,k)$ is called and $k\approx l$ holds. We prove $k\approx l$ by induction over the length of $v$. If $v$ is actually the empty word, $k=i$ and $l=j$ and we are done.

\begin{figure}[htbp]
\centering
\begin{tikzpicture}[auto]
\draw (-6,-.5) node[state,draw,circle] (i) {$U_i$};
\draw (-4.3,.5) node[state,draw,circle] (bk) {$U_{\bar k}$};
\draw (-2,1) node[state,draw,circle] (k) {$U_{k}$};
\draw (1,1) node[state,draw,circle] (l) {$U_{l}$};
\draw (3.3,.5) node[state,draw,circle] (bl) {$U_{\bar l}$};
\draw (5,-.5) node[state,draw,circle] (j) {$U_{j}$};
\draw[->] (i) edge[] node {$g^{\mathrlap{-1}}$} (bk);
\draw[->] (bk) edge[,decorate,decoration={coil,aspect=1,post length=2mm,pre length=2mm,amplitude=.8mm,segment length=1.5mm}] node {$\bar v^{\mathrlap{-1}}$} (k);
\draw[->] (k) edge[,decorate,decoration={coil,aspect=1,post length=2mm,pre length=2mm,amplitude=.8mm,segment length=1.5mm}] node {$r$} (l);
\draw[->] (l) edge[,decorate,decoration={coil,aspect=1,post length=2mm,pre length=2mm,amplitude=.8mm,segment length=1.5mm}] node {$\bar v$} (bl);
\draw[->] (bl) edge[] node {$g$} (j);
\end{tikzpicture}
\caption{Denotations of cosets in the proof for $i\equiv j \implies i\approx j$}
\label{fig:cosetprojproofimg}
\end{figure}

Otherwise, let $g\in X$ be the first letter in the word $v$, i.e.\ $v = g \cdot \bar v$, let $U_{\bar k} = g^{-1}\cdot U_i$ and $U_{\bar l} = \bar v \cdot r \cdot v^{-1} \cdot U_i$. The situation is illustrated in \vref{fig:cosetprojproofimg}. By the induction hypothesis, we have $\bar k \approx \bar l$. In the second loop of the function $\Coincidence(\bar k, \bar l)$ the entries of the coset table for the cosets $\bar k$ and $\bar l$ are compared. The original entries of $C[\bar k][g]$ resp.\ $C[\bar l][g]$ as they were before the algorithm runs are $i$ resp.\ $j$, as $g\cdot U_{\bar k} = g\cdot g^{-1}\cdot U_i = U_i$ and $g \cdot U_{\bar l} = g\cdot \bar v \cdot r \cdot v^{-1} \cdot U_i = w \cdot U_i = U_j$. Table entries are only altered if they were arguments to \Coincidence once, hence $C[\bar k][g] \approx i$ and $C[\bar l][g] \approx j$. Either we already have $C[\bar k][g] = C[\bar l][g]$ and $i \approx C[\bar k][g] = C[\bar l][g]\approx j$ gives $i\approx j$. Or $C[\bar k][g] \ne C[\bar l][g]$, in which case the algorithm calls $\Coincidence(C[\bar k][g],C[\bar l][g])$, and hence $i \approx C[\bar k][g]\sim  C[\bar l][g]\approx j$ gives $i\approx j$.

Every call to \Coincidence removes the larger of the arguments completely from the table entries. Therefore, when the algorithm ends, there is only one representative, the smallest one, left for each equivalence class of $\equiv$. The rows corresponding to the other cosets are marked as merged. Especially, row 0 is not marked as merged. Let $U'_i \da \pi(U_i)$ for an $i$ whose row is not marked as merged. The invariant $\pi(U_{C[i][g]}) = \pi(g \cdot U_i)$ implies $U'_{C[i][g]} = \pi(g)\cdot U'$, so $C$ actually is the coset graph of $U'=\pi(U)$, as required.

\section{Run time analysis}

In the following analysis I assume that the index of $U$ in $G$ is smaller than the largest integer representable by a machine word and that the table entries are one such machine word. Therefore, operations involving these numbers run in $O(1)$ and the table entries occupy $O(1)$ pieces of storage.

The space complexity of the algorithm is very good, as it mostly just changes the table it obtains as the input. This table has one row per coset of $U\le G$ and two columns per generator of $G$, thus a total number of $[G:U]\cdot 2\cdot r$ entries. The marking of the rows can be done by writing invalid entries to the table rows, otherwise an additional $[G:U]$ bits of storage is required. The stack for the recursive function \Coincidence requires constant storage for the arguments and is at most $[G:U]-2$ levels deep.

As to the time complexity of the algorithm: The outer main loop is executed at most  $[G:U]$ times, and less if some rows are marked as merged. Inside the loop, each relation $w\in R$ is traced in the table, which takes $|w|$ steps of constant time. Each call to \Coincidence iterates through the whole table, requiring $[G:U]\cdot 2\cdot r$ steps of constant time each. Additionally, it compares the $2\cdot2\cdot r$ entries of the two rows, possibly calling \Coincidence. The total number of calls to \Coincidence, no matter from where the function is called, is $[G:U]-[G':U']$, as each call to \Coincidence marks exactly one row as merged.  Therefore, the total run time complexity is
\[
O\bigg([G:U]\cdot \sum_{w\in R}|w| + ([G:U]-[G':U'])\cdot([G:U]\cdot 2\cdot r +  2\cdot2\cdot r)\bigg)
\]
which can be simplified in the $O$-calculus to 
\[
O\bigg([G:U]\cdot\sum_{w\in R}|w| + [G:U]^2\cdot r\bigg).
\]

\subsection{Improved data structures}

\begin{algorithm}
\caption{CosetProject algorithm (variant 1)}
\label{algo:cosetprojectvar1}
\dontprintsemicolon
\KwIn{Generators $(g_i)_{i=1,\ldots,r}$ of a group $G$}
\KwIn{The coset table $C$ of a subgroup $U\le G$}
\KwIn{Relations $R$ describing the quotient group $G' \da G/\llangle R\rrangle$}
\KwOut{The coset table of the image $U'$ of $U$ in $G'$}
\BlankLine
Let $X$ be the set of generators of $G$ and their inverses.\;
Let $A$ be an array of $\Len(C)$ elements.\;
\lForAll{$i\in\{0,\ldots,\Len(A)-1\}$}{$A[i] \leftarrow i$}\;
\BlankLine
\ForAll{cosets numbers $i\in\{0,\ldots,\Len(C)-1\}$}{
	\If{row $i$ in $C$ is not marked as merged}{
		\ForAll{relations $w\in R$}{
			Trace $w$ in $C$ starting with coset $i$, let $j$ be the resulting coset.\;
			\lIf{$\AccA(i)\ne \AccA(j)$}{$\Coincidence(A[i],A[j])$}
		}
	}
}
\Return $\FuncSty{map}(\AccA,C)$.
\BlankLine
\KwSty{function} \Coincidence($i$,$j$)
\Begin{
	\lIf{$j<i$}{
		\Coincidence($j$,$i$)
	}\;
	\Else{
		$A[j] \leftarrow i$\;
		\ForAll{$g\in X$}{
			\If{$\AccA(C[i][g]) \ne \AccA(C[j][g])$}{
				$\Coincidence(A[C[i][g]],A[C[j][g]])$
			}
		}
		Mark row $j$ in $C$ as merged.
	}
}
\BlankLine
\KwSty{function} $\AccA(i)$
\Begin{
	\If{$i \ne A[i] \wedge A[i] \ne  \AccA( A[i] )$}{
		$A[i] \leftarrow A[A[i]]$
	}
	Return $A[i]$.
}
\end{algorithm}

As a possible optimization, one can skip updating the whole table inside the function \Coincidence if one maintains an array $A$ of $[G:U]$ entries, initially mapping each coset number to itself. This variant is provided in pseudocode in \vref{algo:cosetprojectvar1}. The array $A$ or, more precisely, the function \AccA used to access values from $A$ maps each coset to the equivalent coset with the lowest coset number found so far. At the end of the algorithm, it will map each coset to the lowest representative of its equivalence class with respect to $\equiv$.

Therefore, the main loop needs to call \Coincidence only if two related cosets are not already found to be related, i.e.\ they do not map to the same coset via $A$.

Each call to $\Coincidence(i,j)$ with $i<j$ sets the array entry $A[j]$ to $i$. The arguments to \Coincidence are always lowest representatives, i.e.\ from the image of $\AccA$. Instead of directly comparing the values $C[i][g]$ with $C[j][g]$ the algorithm compares their images under the function $\AccA$. This does not change the semantics of the algorithm, but the run time cost for each call to \Coincidence is reduced to $O(r)$.  

Immediately after a call to $\AccA(i)$, $A[i]$ is set to the result of $\AccA[i]$, so direct array access is allowed then. When accessing the array $A$ at position $j$, the function $\AccA$ first checks if either $A[j] = j$ or $\AccA(A[j]) = A[j]$. If that is not the case, it sets $A[j]$ to the result of the recursive lookup $A[A[j]]$. Note that the condition of the if-clause calls $\AccA(A[i])$ recursively and thus, $A[A[i]]$ can be accessed directly in the body of the if-clause. This way, $\AccA(j)$ always returns the number that the unoptimized algorithm would have put in place of $j$ in the table, and each entry is kept up-to-date to avoid unnecessary recursive lookups.

We want to count the calls to $\AccA$ from other parts of the program as constant-time operations. This is correct unless $\AccA$ calls itself recursively. Therefore, we have to report the time spent inside recursive calls to $\AccA$ separately. Each of the $[G:U]$ entries of $A$ is changed at most $[G:U]/[G':U']$ times, as that many cosets of $U$ are mapped to the same coset of $U'$. Hence, up to $[G:U]\cdot [G:U]/[G':U']$ recursive calls to $\AccA$ may occur.
%Excluding this cost from accessing the array and reporting it separately allows us to count calls to \AccA as constant-time operations.

This gives a total run time of
\[
O\bigg([G:U]\cdot\sum_{w\in R}|w| + [G:U]\cdot r + [G:U]\cdot \frac{[G:U]}{[G':U']}\bigg).
\]

\section{Preimage calculation}

The CosetProject algorithm in the present form calculates a coset table of the image subgroup $U'\le G'$. This also gives the index $[G':U']$ and can be used to efficiently decide for an element of $w\in G'$, given as a word in the generators, whether it is in $U'$. In some applications, this is not enough and we would also want to know a preimage of $w$ under $\pi$ that lies in $U$. In general, using the same word is not sufficient: In the coset graph of $U\le G$, this might trace to a coset other than $U$, which also happens to be mapped to $U'$ by $\pi$.

\begin{algorithm}
\caption{CosetProject algorithm (variant 2, preimage calculation)}
\label{algo:cosetprojectvar2}
\dontprintsemicolon
\KwIn{Generators $(g_i)_{i=1,\ldots,r}$ of a group $G$}
\KwIn{The coset table $C$ of a subgroup $U\le G$}
\KwIn{Relations $R$ describing the quotient group $G' \da G/\llangle R\rrangle$}
\KwOut{The coset table of the image $U'$ of $U$ in $G'$}
\KwOut{An array $A$ of $\Len(C)$ indexes such that $\pi(U_i) = \pi(U_{A[i]})$}
\KwOut{An array $W$ of $\Len(C)$ words such that $U_{A[i]} = W[i]\cdot U_i$}
\BlankLine
Let $X$ be the set of generators and their inverses.\;
Let $A$ be an array of $\Len(C)$ elements.\;
\lForAll{$i\in\{0,\ldots,\Len(A)-1\}$}{$A[i] \leftarrow i$}\;
Let $W$ be an array of $\Len(C)$ elements, each initialized to the empty word.\;
\BlankLine
\ForAll{cosets numbers $i\in\{0,\ldots,\Len(C)-1\}$}{
	\If{row $i$ in $C$ is not marked as merged}{
		\ForAll{relations $w\in R$}{
			Trace $w$ in $C$ starting with coset $i$, let $j$ be the resulting coset.\;
			\If{$\AccA(i)\ne \AccA(j)$}{
				$\Coincidence(A[i],A[j],W[i]\cdot w^{-1}\cdot W[j]^{-1})$
				}
		}
	}
}
Return $\FuncSty{map}(\AccA,C)$, $A$ and $W$.
\BlankLine
\KwSty{function} $\Coincidence(i,j,w)$
\Begin{
	\lIf{$j<i$}{
		$\Coincidence(j,i,w^{-1})$
	}\;
	\Else{
		$A[j] \leftarrow i$\;
		$W[j] \leftarrow w$\;
		\ForAll{$g\in X$}{
			\If{$\AccA(C[i][g]) \ne \AccA(C[j][g])$}{
				$w' \leftarrow W[C[i][g]]\cdot g\cdot w\cdot g^{-1}\cdot W[C[j][g]]^{-1}$\;
				$\Coincidence(A[C[i][g]],A[C[j][g]], w')$\;
			}
		}
		Mark row $j$ in $C$ as merged.
	}
}
\BlankLine
\KwSty{function} $\AccA(i)$
\Begin{
	\If{$i \ne A[i] \wedge A[i] \ne  \AccA( A[i] )$}{
		$W[i] \leftarrow W[A[i]] \cdot W[i]$\;
		$A[i] \leftarrow A[A[i]]$
	}
	Return $A[i]$.
}
\end{algorithm}

The algorithm can be extended in a straight forward manner to remember, for each coset $U_i$ of $U$, a word $w_i\in G$ such that $U_{A[i]} = w_i\cdot U_i$. Then, given a word $w\in U'$ that traces from $U$ to $U_i$ in the coset graph of $U$, $w_i\cdot w$ is a preimage of $w$ that lies in $U$.

The modified algorithm, based on the optimized variant \cref{algo:cosetprojectvar1}, is outlined in \vref{algo:cosetprojectvar2}. Besides the array $W$, a new parameter to the function \Coincidence is introduced.

The correctness of the extended algorithm follows from the following invariant involving the array $W$:
\[
U_{A[i]} = W[i]\cdot U_i
\]

The invariant holds after the initialization of the arrays. $A$ and $W$ are always changed together: Either in \Coincidence, or in \AccA. In the body of the if-clause in \AccA, let $A'$ and $W'$ denote the arrays after the modification. We have, by using the invariant twice,
\[
U_{A'[i]} = U_{A[A[i]]} = W[A[i]]\cdot U_{A[i]} = W[A[i]] \cdot W[i] \cdot U_i = W'[i]\cdot U_i
\]
and thus the invariant is preserved.

When the function \Coincidence is called from the main loop, $j$ was chosen by \mbox{$U_j = w\cdot U_i$}, hence $U_i = w^{-1} \cdot U_j$. Let $i'=A[i]$, $j'=A[j]$ and $w'= W[i] \cdot w^{-1} \cdot W[j]^{-1}$ be the arguments passed to \Coincidence. By invoking the invariant, we find that they fulfill the condition $U_{i'} = w'\cdot U_{j'}$:
\begin{align*}
w'\cdot U_{j'} &=
(W[i] \cdot w^{-1} \cdot W[j]^{-1}) \cdot U_{A[j]} \\
&= W[i] \cdot w^{-1} \cdot W[j]^{-1} \cdot W[j] \cdot U_j \\
&= W[i] \cdot w^{-1} \cdot U_j \\
&= W[i] \cdot U_i \\
&= U_{A[i]} \\
&= U_{i'}
\end{align*}

In a call to $\Coincidence(i,j,w)$, assume $U_i = w\cdot U_j$. This means that the invariant is preserved after updating the array $A$ and $W$. When \Coincidence is now called recursively, a similar calculation shows that the arguments again fulfill the assumed condition:
\begin{align*}
w' \cdot U_{A[C[j][g]]}
&= W[C[i][g]] \cdot g \cdot w \cdot g^{-1} \cdot W[C[j][g]]^{-1} \cdot U_{A[C[j][g]} \\
&= W[C[i][g]] \cdot g \cdot w \cdot g^{-1} \cdot W[C[j][g]]^{-1} \cdot W[C[j][g]] \cdot U_{C[j][g]} \\
&= W[C[i][g]] \cdot g \cdot w \cdot g^{-1} \cdot U_{C[j][g]} \\
&= W[C[i][g]] \cdot g \cdot w \cdot g^{-1} \cdot g\cdot U_j \\
&= W[C[i][g]] \cdot g \cdot w \cdot U_j \\
&= W[C[i][g]] \cdot g \cdot U_i \\
&= W[C[i][g]] \cdot U_{C[i][g]} \\
&= U_{A[C[i][g]]}
\end{align*}

By induction, this shows that the condition $U_i = w\cdot U_j$ holds for all calls to the function $\Coincidence(i,j,w)$. Hence, the invariant is preserved inside calls to \Coincidence as well and the array contains the desired information.

\section{Application to the automorphism group}

 In the preceding sections, we assumed that the preimage group $G$ and the image group $G'$ were given with the same generators and $G'$ could be considered a quotient group of $G$ by the normal closure of the additional relations. In the application described at the beginning of this chapter, this is unfortunately not the case: Subgroups of $\Aut(F_r)$ are given by their coset graph with respect to the generators $\tau_1,\,\sigma_{1\,2},\,\ldots,\sigma_{r-1\,r},\,\eta$ (see \vref{tab:autfrgens}), while we would like to use the generators $X_{ij}$, $i\ne j$, when referring to subgroups of $\SL_r(\Z)$.
 
Additionally we want, for a subgroup $U\le \Aut(F_r)$, to calculate $B(U)\cap \SL_r(\Z)$, so we have to implement the intersection of a subgroup, given by its coset graph, with an index two subgroup.

Depending on whether we utilize the Todd-Coxeter algorithm or the CosetProject algorithm, different steps have to be taken. These are outlined here and explained below.

When using the Todd-Coxeter algorithm, the steps are:
{\parskip=0pt
\begin{enumerate}
\item Calculate generators of $U\cap \Aut^+(F_r)$ via \cref{index2intersection}.
\item Map generators of the subset $U\cap\Aut^+(F_r)$ through $B$.
\item Calculate the coset graph using the Todd-Coxeter algorithm.
\end{enumerate}}

When using the CosetProject algorithms, the steps are
{\parskip=0pt
\begin{enumerate}
\item Using \cref{algo:cosetgraphintersect}, create a coset graph of $U\cap \Aut^+(F_r)\le \Aut^+(F_r)$.
\item Apply the CosetProject algorithm to the coset graph of $U\cap \Aut^+(F_r)$ to obtain the coset graph of $B(U)\cap \SL_r(\Z)\le\SL_r(\Z)$.
\item Rewrite the coset graph in terms of the desired generators using \cref{algo:cosetgraphintersect}.
\end{enumerate}
} 


\subsection{Index two subgroup intersection}

\begin{lemma}
\label{index2intersection}
Let $S\le G$ be a subgroup with index 2. Let $U\le G$ be a subgroup generated by $h_1,\ldots,h_n\in G$ with $U\not\le S$. Without loss of generality, assume that there is an $m\in\{1,\ldots,n\}$ such that $h_1,\ldots,h_m \in G\setminus S$ and $h_{m+1},\ldots,h_n\in S$.

The subgroup $U\cap S\le G$ is generated by the set
\[
\{ h_i^2,\, h_i\cdot h_1^{-1} \mid i=1,\ldots,m \} \cup \{ h_i,\, h_1\cdot h_i\cdot h_1^{-1} \mid i=m+1,\ldots, n\}.
\]

\end{lemma}

\begin{proof}
Let $w$ be a word in the generators $h_1,\ldots,h_n$ such that $w\in U\cap S$ and without loss of generality assume that $w\ne \Id$ and that any proper prefix of $w$ is in $U \setminus S$ (otherwise split $w$ after the prefix and apply the proof to both parts).

If $w$ has length 1, it is already one of the generators $h_{m+1},\ldots,h_{n}$ or their inverses.
 
If $w$ has length 2, it is a product $h_i^{\ep_i} \cdot  h_j^{\ep_j}$ with $\ep_i,\ep_j\in\{-1,1\}$ and $i,j\in\{1,\ldots,m\}$. If $\ep_i=\ep_j=1$, $w$ is generated by the given generators by 
\[
w = h_i\cdot h_j = h_i\cdot h_1^{-1} \cdot (h_j \cdot h_1^{-1})^{-1} \cdot h_j^2.
\]
The other cases are obtained by multiplying with $(h_i^{2})^{-1}$ from the left respectively with $(h_j^{2})^{-1}$ from the right.

If the length of $w$ exceeds 2, assume that the proposition holds for shorter words. The first letter of $w$ is one of $h_1,\ldots,h_m$ or their inverses, and the second letter is one of $h_{m+1},\ldots,h_n$ or their inverses, because no proper prefix of $w$ is in $U\setminus S$. So $w=h_i^{\ep_i}\cdot h_k^{\ep_k} \cdot w'$ for some $\ep_i,\ep_j\in\{-1,1\}$ and $w'\in G$. By writing
\[
h_i \cdot h_k^{\ep_k} \cdot w' = (h_i \cdot h_1^{-1}) \cdot (h_1\cdot h_k \cdot h_1^{-1})^{\ep_k} \cdot h_1\cdot w'
\]
and prepending $(h_i^2)^{-1}$ if $\ep_i=-1$ the problem is reduced to the shorter word $h_1\cdot w'$ and due to the induction hypothesis, $w$ can be written as a product of the alleged generators.
\end{proof}

If one works with the Todd-Coxeter algorithm, subgroups are initially represented by a generating set. So the generators $h_1,\ldots,h_n$ of $U \le \Aut(F_r)$ can be mapped through $B$ to obtain a generating set $B(h_1),\ldots,B(h_n)$ of $B(U)\le \GL_r(\Z)$. Using \cref{index2intersection}, we obtain a generating set of $B(U)\cap \SL_r(\Z)$, which can be fed to the Todd-Coxeter algorithm to obtain the coset graph of $B(U)\cap \SL_r(\Z) \le \SL_r(\Z)$.

For the CosetProject algorithm it is convenient to first intersect $U$ with $\Aut^+(F_r)$, which is the preimage of $\SL_r(\Z)$ under $B$, and then rewrite the coset graph of $U\cap \Aut^+(F_r)$ using preimages of the generators $X_{ij}, i\ne j$ (see \vref{elementarymatrices}).

A set of generators of $\Aut^+(F_r)$ is, by \cref{index2intersection}, 
\[
\{ \tau_1^2,\, \tau_1\cdot \tau_1^{-1} \} \cup \{ \sigma_{i\,(i+1)}^2,\, \sigma_{i\,(i+1)}\cdot \tau_1^{-1} \mid i \in \{1,\ldots,r-1\}\} \cup \{ \eta^2,\, \eta\cdot\tau_1^{-1} \},
\]
which can be simplified to the $r$ generators
\[
\{ \sigma_{i\, (i+1)}\cdot \tau_1 \mid i\in\{1,\ldots,r-1\} \}\cup\{ \eta\cdot\tau_1 \},
\]
as each generator is involutory.

\subsection{The map \texorpdfstring{$B$}{B} in terms of generators}

For the second step when using Todd-Coxeter, we apply the map $B$ to automorphisms given as words in $(\sigma_{1\,2}\cdot\tau_1),\dots,(\sigma_{r-1\,r}\cdot\tau_1),(\eta\cdot\tau_1)$ and expect results in the generators $X_{ij}$, $i\ne j$. The map-defining generator images can be found by experimenting with the Sury generators, and are given in \vref{tab:mapBgens}. The matrices are those in the case of $r=3$ and serve exemplification purposes.

\begin{table}
\begin{align*}
B(\sigma_{1\,2}\cdot \tau_1) &= 
\begin{pmatrix}
0 & 1 &  \\
-1 & 0 & \\
  &   & 1 
\end{pmatrix} \\
&=
X_{21}^{-1} \cdot X_{12} \cdot X_{21}^{-1}\\[2em]
B(\sigma_{i\,i+1}\cdot \tau_1) &=
\begin{pmatrix}
-1 \\
& 0 & 1\\
& 1 & 0 \\
\end{pmatrix}
=
\begin{pmatrix}
-1 \\
& 1& \\
&  & -1\\ 
\end{pmatrix}
\cdot
\begin{pmatrix}
1 \\
& 0 & 1\\
& -1 & 0 \\ 
\end{pmatrix} \tag{for $1<i<r$}
\\
&= (X_{i+1\,1}^{-1} \cdot X_{1\,i+1} \cdot X_{i+1\,1}^{-2} \cdot X_{1\,i+1} \cdot X_{i+1\,1}^{-1}) \cdot (X_{i+1\,i}^{-1}\cdot X_{i\,i+1} \cdot X_{i+1\,i}^{-1}) \\[2em]
B(\eta\cdot \tau_1) &= 
\begin{pmatrix}
-1 & 0 \\
1 & -1 \\
& & 1
\end{pmatrix} \\
&= X_{21}^{-2}\cdot X_{12} \cdot X_{21}^{-2} \cdot X_{12} \cdot X_{21}^{-1}
\end{align*}
\caption{The map $B$ in terms of generators}
\label{tab:mapBgens}
\end{table}

No such explicit mapping is required when going the CosetProject path, as the mapping step does not change the used generators. The transformation happens in the invocation of \cref{algo:cosetgraphintersect}, using the equations from \cref{sec:genrewrite}.


\subsection{Subgroup intersection and coset graphs}

To intersect the subgroup $U\le \Aut(F_r)$, represented by its coset graph with regard to the generators $\tau_1,\sigma_{1\,2},\ldots,\sigma_{(r-1)\,r},\eta$, with $\Aut^+(F_r)$, one can use \vref{algo:cosetgraphintersect}. Given the coset graph of $U$ and the generators of $\Aut^+(F_r)$, it does a breadth-first search to re-assemble the coset graph of $U\cap \Aut^+(F_r)\le \Aut^+(F_r)$ with respect to the correct generators. The resulting coset table might be sparse and could be compressed by moving the rows “up” to fill the empty spots left over by unused lines before returning it.

\begin{algorithm}
\caption{Subgroup intersection algorithm}
\label{algo:cosetgraphintersect}
\dontprintsemicolon
\KwIn{Generators $(g_i)_{i=1,\ldots,r}$ of a group $G$}
\KwIn{The coset table $C$ of a subgroup $U\le G$}
\KwIn{Generators $(h_i)_{i=1,\ldots,s}$ of a subgroup $S\le G$, as words in the $g_i$}
\KwOut{The coset table of the intersection $U\cap S \le S$}
\BlankLine
Let $Y$ be the set of generators of $S$ and their inverses.\;
Let $C'$ be an empty coset table with $|C|$ rows and columns labeled by the elements of $Y$.\;
Let $q$ be a first-in-first-out queue, initialized with $(0)$.\;
Let $d$ be a set, initialized with $\{0\}$.\;
\While{$q$ is not empty}{
	$i \leftarrow \pop(q)$\;
	\ForAll{$h \in Y$}{
		Trace $h$ in $C$ starting with coset $i$, let $j$ be the resulting coset.\;
		$C'[i][h] \leftarrow j$\;
		\If{$j \notin d$}{
			$\push(q,j)$\;
			$d \leftarrow d \cup \{j\}$\;
			
		}
	}
}
\Return{$C'$}.
\end{algorithm}

\subsection{Generator rewriting}
\label{sec:genrewrite}

We have a presentation of $\SL_r(\Z)$ in terms of the generators $X_{ij}$, $i\ne j$, and relations between these generators \citep[Theorem 4-3.2]{Sury}. To turn this into a presentation with regard to the generators
\[
\{ B(\sigma_{i\, (i+1)}\cdot \tau_1) \mid i\in\{1,\ldots,r-1\} \}\cup\{ B(\eta\cdot\tau_1)\},
\]
we have to rewrite the given relations as products of these generators. To do so, it is sufficient to replace each $X_{ij}$ by a product of these generators.

To find these products, we first write them as products of images of $\tau_1,\allowbreak\, \sigma_{12},\allowbreak\ldots,\allowbreak\sigma_{r-1\,r},\allowbreak\eta$ under $B$ as follows: As the base case, we have
\[
X_{21} = B(\tau_2 \cdot \eta) = B(\sigma_{12} \cdot \tau_1 \cdot \sigma_{12} \cdot \eta)
\]
and 
\[
X_{12} = B(\sigma_{12}) \cdot X_{21} \cdot B(\sigma_{12}).
\]
An elementary matrix $X_{ij}$ with $i>j$, can then be written as
\[
X_{ij} = B\big( \sigma_{j-1\, j} \cdots  \sigma_{12} \cdot \sigma_{i-1\, i} \cdots\sigma_{23} \big) \cdot X_{21} \cdot B\big( \sigma_{23} \cdots \sigma_{i-1\, i}  \cdot  \sigma_{12} \cdots \sigma_{j-1\, j} \big) 
\]
and an elementary $X_{ij}$ with $i<j$ can be written as
\[
X_{ij} = B\big(\sigma_{i-1\, i} \cdots  \sigma_{12} \cdot \sigma_{j-1\, j} \cdots\sigma_{23}\big) \cdot X_{12}  \cdot B\big(\sigma_{23} \cdots \sigma_{j-1\, j} \cdot \sigma_{12} \cdots \sigma_{i-1\, i}\big)\mathrlap{.}
\]

To turn these products of images of $\tau_1,\, \sigma_{12},\ldots,\sigma_{r-1\,r},\eta$ under $B$ into products of images of $(\sigma_{12}\cdot \tau_1),\ldots,(\sigma_{r-1\,r}\cdot \tau_1), (\eta\cdot \tau_1)$ under $B$ as required, one can proceed as in the proof of \cref{index2intersection}. Since these generators of $\Aut(F_r)$ are involutory, this boils down to replace pairs of generators according to the following identities, where $g_1$ and $g_2$ stand for one of $\sigma_{12},\ldots,\sigma_{r-1\,r},\eta$:
\begin{align*}
\tau_1\cdot\tau_1 &= \Id \\
g_1 \cdot \tau_1 &= (g_1\cdot \tau_1) \\
\tau_1 \cdot g_1 &= (g_1\cdot \tau_1)^{-1} \\
g_1 \cdot g_2 &= (g_1\cdot \tau_1)\cdot (g_2\cdot \tau_1)^{-1}.
\end{align*}

Applying the CosetProject algorithm to the coset graph of $U \cap \Aut^+(F_r) \le \Aut^+(F_r)$ with the relations rewritten in terms of these generators gives a coset graph of $B(U) \cap \SL_r(\Z) \le \SL_r(\Z)$. As a last step, \cref{algo:cosetgraphintersect} can be used to transform this coset graph into a coset graph with regard to the generators $X_{ij}$. In this invocation of the algorithm, the group $G$ is $\SL_r(\Z)$ with generators $B(\sigma_{12}\cdot \tau_1),\ldots,B(\sigma_{r-1\,r}\cdot \tau_1), B(\eta\cdot \tau_1)$, the subgroup $S$ is the full group $\SL_r(\Z)$ and the subgroup generators $(h_i)_{i=1,\ldots,s}$ are the elementary matrices $X_{ij}$, $i\ne j$, written in terms of the group generators as explained above.

\section{Congruence level}

To detect the congruence level of a subgroup $U\le \SL_r(\Z)$, given its coset graph, we use the fact that the principal congruence subgroup of level $l$ is the normal subgroup generated by $X_{12}^l$: \citep[Proof of Theorem 4-4.2]{Sury}
\[
\Gamma_l = \llangle X_{12}^l \rrangle.
\]

Therefore, to check $\Gamma_l \le U$, it is sufficient to check whether $X_{12}^l \in wUw^{-1}$ for all $w\in U$. As the coset graphs of conjugates of $U$ are obtained from the coset graph of $U$ by taking another node as the origin (\cref{rem:cosetgraphs}), we trace the word $X_{12}^l$ from each coset $U_i$ of $U$ and check if we end up at $U_i$. Trying this procedure for $l=1,2,\ldots$ until we succeed, we calculate the congruence level of $U$. This procedure is given in pseudocode in \vref{algo:congruencelevel}.

\begin{algorithm}
\caption{Congruence level detection}
\label{algo:congruencelevel}
\dontprintsemicolon
\KwIn{The coset table $C$ of a subgroup $U\le \SL_r(\Z)$}
\KwOut{The congruence level $l$ of $U$}
\BlankLine
$l \leftarrow 1$\;
\While{true}{
	$ok \leftarrow 1$\;
	\ForAll{$i \in \{0,\ldots,\Len(C)\}$}{
		Trace $X_{12}^l$ in $C$ starting with coset $i$, let $j$ be the resulting coset.\;
		\lIf{$j \ne i$}{
			$ok \leftarrow 0$\;
		}\;
	}
	\eIf{$ok = 1$}{
		\Return{$l$}
	}{
		$l \leftarrow l + 1$\;
	}\;
}
\end{algorithm}

\section{Results}

The algorithm from the previous section was used in combination with the algorithm found in \citep{Frei08} to calculate the congruence levels of $B(\Stab_{\Aut(F_r)}(U))\cap\SL_r(\Z)$ for all subgroups $U\le F_r$ with a given index $i$, for approachable values of $r$ and $i$. The results are printed in \vref{congtable}. Unfortunately, both the number of subgroups and the index of $\Stab_{\Aut(F_r)}(U)$ grow very fast, so not many samples were obtained. In the case of the index 4 subgroups of $F_3$ and the index 3 subgroups of $F_5$, the program was stopped before handling all subgroups.

Although only low congruence levels are found in this sample, any congruence level is reached (see \cref{excludedcasesec}).


Eventually, working on this problem and inspecting the results gave the ideas and hints that led to the definition of loop subgroups and the results presented in the next chapter.

\begin{table}[b!]
\centering
\begin{tabular}{rrrrr}
\rule{0pt}{26ex}% Manueller Platzhalter
\turnbox{50}{$r$} &
\hspace{4ex}\turnbox{50}{$[F_r:U]$} &
\hspace{4ex}\turnbox{50}{$[\Aut(F_r):\Stab_{\Aut(F_r)}(U)]$} &
\hspace{4ex}\turnbox{50}{$[\SL_r(\Z):B(\Stab_{\Aut(F_r)}(U))]$} &
\hspace{4ex}\turnbox{50}{congruence level of $B(\Stab_{\Aut(F_r))}(U)$} \\
\midrule
3 & 1 & 1 & 1 & 1 \\
\cmidrule{2-5}
  & 2 & 7 & 7 & 2 \\
\cmidrule{2-5}
  & 3 & 84 & 7 & 2 \\
  &   & 13 & 13 & 3 \\
\cmidrule{2-5}
  & 4 & 7 & 7 & 2 \\
  &   & 28 & 28 & 4 \\
  &   & 260 & 13 & 3 \\
  &   & 168 & 42 & 2 \\
  &   & 1680 & 7 & 2 \\
\cmidrule{1-5}
4 & 1 & 1 & 1 & 1 \\
\cmidrule{2-5}
  & 2 & 15 & 15 & 2 \\
\cmidrule{2-5}
  & 3 & 585 & 15 & 2 \\
  &   & 40 & 40 & 3 \\
\cmidrule{1-5}
5 & 1 & 1 & 1 & 1 \\
\cmidrule{2-5}
  & 2 & 31 & 31 & 2 \\
\cmidrule{2-5}
  & 3 & 3720 & 31 & 2 \\
  &   & 121 & 121 & 3 \\
\end{tabular}
\caption{Some occurring congruence levels}
\label{congtable}
\end{table}

\chapter{The loop subgroups}
\label{loopsubgroups}

\lettrine In this chapter, we will study \emph{loop subgroups} of the free group $F_r$ for $r\ge 3$. This class of subgroups stands out because the image of its stabilizer group in $\GL_r(\Z)$ is fully calculable. Loop subgroups are quite particular among the general subgroups, but there are legitimate reasons to assume that the results for loop subgroups can be generalized, as discussed in the last section.

\section{Definition of loop subgroups}

Let $F_r$ be the free group with generators $g_1=x, g_2=y, g_3=z, g_4,\ldots,g_r$. The $s_1/\ldots/s_r$ loop subgroup $U$, $s_i\in\N$, is the subgroup with the distinct left cosets
\[
N \da \{U,\ g_1^1U,\ldots,g_1^{s_1-1}U,\ g_2^1U,\ldots,g_2^{s_2-1}U,\ \ldots,\ g_r^1U,\ldots,g_r^{s_r-1}U\}
\]
and the following edges in its left coset graph
\begin{align*}
U &\xrightarrow{g_i} g_i^1U && \forall i=1,\ldots,r, \\
g_i^kU &\xrightarrow{g_i} g_i^{k+1}U && \forall i=1,\ldots,r,\, k = 1,\ldots,s_i-2, \\
g_i^{s_i-1}U &\xrightarrow{g_i} U && \forall i=1,\ldots,r, \\
g_j^kU &\xrightarrow{g_i} g_j^kU && \forall i,j=1,\ldots,r,\, j \ne i,\, k = 1,\ldots,s_j-1.
\end{align*}

The sequence of nodes $U,g_i^1U,\ldots, g_i^{s_i-1}U, U$ is called a \emph{loop}. $s_i$ is the \emph{length} of the loop. A loop is called \emph{odd} (resp.\ \emph{even}) if its length is odd (resp.\ even). A loop of length 1 is called a \emph{looplet}\footnote{The German language allows to build diminutive forms of almost all nouns by appending the suffix \emph{-chen}. I take the liberty to do the same in English, as it makes the text easier and more pleasant to read than if I had named them \emph{small loops}.}.

The reason for this nomenclature becomes evident if we draw the coset graph of a loop subgroup:

%\pagebreak[4]
\begin{example}
\label{loopex}The coset graph of the $3/3/1$ loop subgroup of $F_3$, a subgroup with only odd loops and one looplet, is shown in \vref{loopexfigure}.
\end{example}
\begin{figure}[h]
\centering
\begin{tikzpicture}[auto]
\draw (0,0) node[state,accepting,draw,circle] (1) {$U$};
\begin{scope}[xshift=2cm]
\path (1) --
      (canvas polar cs:radius=2cm, angle=60) node[state,draw,circle] (2) {$y^1U$} --
      (canvas polar cs:radius=2cm, angle=-60) node[state,draw,circle] (3) {$y^2U$};
\draw[->] (canvas polar cs:radius=2cm, angle=160) arc(160:120:2cm) node[above] {$y$} arc(120:80:2cm);
\draw[->] (canvas polar cs:radius=2cm, angle=40) arc(40:0:2cm) node[right] {$y$} arc(0:-40:2cm);
\draw[->] (canvas polar cs:radius=2cm, angle=-80) arc(-80:-120:2cm) node[below] {$y$} arc(-120:-160:2cm);
\draw[->] (2) edge [in=45,out=75,loop] node {$z,x$} (2);
\draw[->] (3) edge [in=-75,out=-45,loop] node {$z,x$} (3);
\end{scope}
\begin{scope}[xshift=-2cm]
\path (1) --
      (canvas polar cs:radius=2cm, angle=120) node[draw,circle] (2) {$x^1U$} --
      (canvas polar cs:radius=2cm, angle=-120) node[draw,circle] (3) {$x^2U$};
\draw[->] (canvas polar cs:radius=2cm, angle=20) arc(20:60:2cm) node[above] {$x$} arc(60:100:2cm);
\draw[->] (canvas polar cs:radius=2cm, angle=140) arc(140:180:2cm) node[left] {$x$} arc(180:220:2cm);
\draw[->] (canvas polar cs:radius=2cm, angle=-100) arc(-100:-60:2cm) node[below] {$x$} arc(-60:-20:2cm);
\draw[->] (2) edge [in=105,out=135,loop] node {$z,y$} (2);
\draw[->] (3) edge [in=225,out=255,loop] node {$z,y$} (3);
\end{scope}
\draw[->] (1) edge [loop left] node {$z$} (1);
\end{tikzpicture}
\caption{The left coset graph of the 3/3/1 loop subgroup of $F_3$.}
\label{loopexfigure}
\end{figure}

The $s_1/\ldots/s_r$ loop subgroup of $F_r$ is generated by the the following set of words in $F_r$:
\begin{align*}
\{ g_i^{s_i}, \ i=1,\ldots,r \} \cup\ \{ g_i^{-k}g_j^{} g_i^k, \ i,j=1,\ldots,r,\, i\ne j,\, k=1,\ldots, s_i-1.\}. 
\end{align*}
This set actually is a basis of $U$ as a free group, as the number of generators is
\begin{align*}
r + \sum_{i=1}^r (r-1) \cdot (s_i-1) & = r-1+1 + (r-1)\sum_{i=1}^r (s_i-1) \\
&= (r-1)(1+\sum_{i=1}^r (s_i-1)) + 1\\
&= (r-1)[F_r:U]+1,
\end{align*}
which is the number of basis elements of a subgroup of $F_r$ with this index.

%\pagebreak[4]
\section{Preparations}

Before we now start investigating loop subgroups, some preparational definitions and calculations are due. 

\subsection{Permutations of cosets}
\label{someperm}

In what follows it will often be handy to consider how elements of $F_r$ act on the coset graph of a subgroup $U$. To make this explicit, let $\Sym(N)$ be the symmetric group on the set $N$ of left cosets of $U$, and define the group homomorphism
\[
\pi\colon F_r \to \Sym(N),
\]
which assigns to the word $w\in F_r$ the permutation $\pi(w)$ which maps $v U$ to $w v U$:
\[
\pi(w)(vU) \da wvU.
\]

We can find out a few things about a word $w\in F_r$ by looking at its permutation in $\Sym(N)$. We have
\[
\pi(w)(U) = U \iff w\in U.
\]
Furthermore, we have
\[
\pi(w) = \Id \iff w \in \NT(U) \da \bigcap_{v\in F_r} v^{-1}U v.
\]

To bring automorphisms into this picture, we first note that any $\gamma\in\Stab_{\Aut(F_r)}(U)$ maps left cosets of $U$ to left cosets of $U$:
\[
\gamma(w)U=\gamma(v)U \iff \gamma(v^{-1}w)\in U \iff v^{-1}w\in U \iff wU=vU
\]

Therefore, we can also assign the whole automorphism $\gamma$ a permutation in $\Sym(N)$ which we denote, by abuse of notation, with $\pi(\gamma)$:
\[
\pi(\gamma)(vU) \da \gamma(v)U.
\]
Note that $\pi(\gamma)^{-1}(vU) = \gamma^{-1}(v)U$. This allows us to formulate the next statement:

\begin{lemma}
\label{autconj}
For $U\le F_r$, $\gamma\in\Stab_{\Aut(F_r)}(U)$ and $w\in F_r$,
$\pi(\gamma(w))$ is conjugate to $\pi(w)$.
\end{lemma}
\begin{proof} Using the notation introduced above, for any $v\in F_r$ we have
\begin{align*}
\pi(\gamma(w))(vU) &= \gamma(w) v U \\
&= \gamma(w \cdot \gamma^{-1}(v)) U \\
&= \pi(\gamma)\big(w \cdot \gamma^{-1}(v)U\big) \\
&= \pi(\gamma)\big(w \cdot \pi(\gamma)^{-1}(vU)\big)\\
&= \pi(\gamma)\Big(\pi(w)\big(\pi(\gamma)^{-1}(vU)\big)\Big) \\
&= \big(\pi(\gamma) \circ \pi(w) \circ \pi(\gamma)^{-1}\big)(vU)
\end{align*}
thus $\pi(\gamma(w)) = \pi(\gamma) \circ \pi(w) \circ \pi(\gamma)^{-1}$.
\end{proof}

\begin{remark}
\label{autconstr}A map $\gamma\colon F_r \to F_r$ defined by
\[
\gamma(g_j) = 
\begin{cases}
w g_i, &\text{if } j = i \\
\phantom w g_j, &\text{if } j \ne i
\end{cases}
\]
is an automorphism if the generator $g_i$ does not occur as a letter in the word $w$, i.e.\ $w\in \langle g_1,\ldots,g_{i-1},g_{i+1},\ldots,g_r\rangle$. It stabilizes the subgroup $U$ if $w\in\NT(U)$, as then $\pi(w)=\Id$ holds, implying $\pi(\gamma(v)) = \pi(v)$ and thus $\gamma(v)\in U \iff v\in U$.
\end{remark}

\begin{lemma}
\label{unboundstabgroup}
The index $[\Aut(F_r) : \Stab_{\Aut(F_r)}(U)]$ of the stabilizer subgroup of $U$ goes to infinity as the index $[F_r:U]$ of the loop subgroup goes to infinity.
\end{lemma}

\begin{proof}
For $i,j\in\{1,\ldots,r\}$, $i\ne j$ and $s_i>1$ consider the automorphism $\gamma\in \Aut(F_r)$ defined by
\[
\gamma(g_k) \da 
\begin{cases}
g_jg_i, &\text{if } k=j \\
g_k, &\text{if } k\ne j.
\end{cases}
\]
Let $n\in\{1,\ldots,s_i-1\}$. The $n$-th power of $\gamma$ is given by
\[
\gamma^n(g_k) = 
\begin{cases}
g_jg_i^n, &\text{if } k=j \\
g_k, &\text{if } k\ne j.
\end{cases}
\]
The permutation $\pi(g_i)$ is a cycle of length $s_i$, hence $\pi(g_i)^n$ is also a cycle of length $s_i$ and one can be obtained from the other by renaming the entries of the cycle. Written formally, there exists a permutation $\sigma\in \Sym(N)$ with $\pi(s_i)^n = \sigma \pi(s_i) \sigma^{-1}$ and $\sigma(U)=U$ \citep[Abschnitt 5.3, Aufgabe 6]{Bosch}. Note that $\sigma$ and $\pi(s_j)$ permute.

We have $g_j^{s_j}\in U$.  To check whether $\gamma^n(g_j^{s_j})$ is in $U$, we calculate
\begin{align*}
\pi(\gamma^n(g_j^{s_j})) 
&= \pi(g_j g_i^n)^{s_j}
= (\pi(g_j) \pi(g_i)^n)^{s_j}
= (\pi(g_j) \sigma \pi(s_i) \sigma^{-1})^{s_j} \\
&= (\sigma \pi(g_j) \pi(s_i) \sigma^{-1})^{s_j}
= \sigma(\pi(g_jg_i))^{s_j}\sigma^{-1}
\end{align*}
thus
\begin{align*}
\gamma(g_j^{s_j}) \in U 
&\iff \pi(\gamma(g_j^{s_j}))(U) = U \iff \sigma(\pi(g_jg_i))^{s_j}\sigma^{-1}(U) = U \\
& \iff \pi( (g_jg_i)^{s_j})(U) = U 
\iff (g_jg_i)^{s_j}\in U
\end{align*}
By consulting the coset graph of $U$, we know $(g_jg_i)^{s_j-1}g_j\in U$ and  $g_i\notin U$, as $s_i>1$, so $\gamma^n(g_j^{s_j})\notin U$ and $\gamma^n\notin\Stab_{\Aut(F_r)}(U)$.

Since $\gamma^n\notin\Stab_{\Aut(F_r)}(U)$ for $1\le n <s_i$, the index of the stabilizer subgroup must be larger than $s_i-1$. Hence,
\[
[\Aut(F_r) : \Stab_{\Aut(F_r)}(U)] \ge \max_{i\in\{1,\ldots,r\}} s_i \to \infty
\]
as $[F_r:U]\to\infty$.
\end{proof}

The following fact about permutations will be very useful for our later calculations:
\begin{lemma}
\label{altperm}
Let $\sigma, \omega \in S_n$ be permutations of the form
\[
\sigma = (1,2,\ldots,m)
\quad\text{and}\quad
\omega=(1,m+1,\ldots,n)
\]
with $1<m<n$. Then all even permutations are in the commutator subgroup of the group generated by $\sigma$ and $\omega$, i.e.\ they can be written as a product of commutations of $\sigma$ and $\omega$: 
\[
A_n \le [\langle \sigma, \omega \rangle, \langle \sigma, \omega \rangle]
\]
where $A_n$ is the alternating group of degree $n$ and $[G,G]$ denotes the commutator subgroup of $G$.
\end{lemma}

\begin{proof}
The alternating group $A_n$, $n\ge 3$, is generated by all three-cycles in $S_n$ \cite[section 5.3, Satz 3]{Bosch}. We first generate all three-cycles which do not fix the 1. These are cycles of the form $(1,i,j)$. There are four cases:
\begin{itemize}
\item $1<j\le m$ and $m < i \le n$. In this case, we take the inverse and enter the next case.
\item $1<i\le m$ and $m < j \le n$. We write the cycle using commutators of $\omega$ and $\sigma$:
\[
(1,i,j) = \sigma^{i-1} \circ \omega^{j-m} \circ \sigma^{-(i-1)} \circ \omega^{-(j-m)}
\]
\item $1<i\le m$ and $1< j \le m$. We can reduce this case to the previous by writing:
\[
(1,i,j) = (1,j,m+1)^{-1}\circ (1,i,m+1)
\]
\item $m<i\le n$ and $m< j \le n$. This case works analogously to the previous case:
\[
(1,i,j) = (1,2,j)\circ (1,2,i)^{-1}
\]
\end{itemize}

Observe that $\omega \circ \sigma = (1,2,\ldots,n)$.
If we now have a general three-cycle $(k,i,j)$, it is conjugate to a three-cycle that moves the 1:
\[
(k,i,j) = (\omega\circ\sigma)^{k-1} \circ (1,i-(k-1),j-(k-1)) \circ (\omega\circ\sigma)^{-(k-1)}
\]
So we can write any even permutation in $S_n$ as a product of $\omega$’s and $\sigma$’s, such that for either of the two generators, the sum of its occurrences, counting negative powers negatively, is zero.
\end{proof}

\subsection{The linear group and the principal congruence subgroup}
\label{lingrpsec}

The elementary matrix $X_{ij} \in \GL_r(\Z)$, $i\ne j$, is the matrix with ones on the diagonal, one additional one in the $i$-th row and $j$-th column and zeroes everywhere else. The elementary matrices generate $\SL_r(\Z)$ \citep[Theorem 4-3.2]{Sury}. Another generating set is 
\[
\{X_{ik}, k\ne i\} \cup \{ X_{ji}, j\ne i\}
\]
for a fixed $i$. This follows from the relations $[X_{ji},X_{ik}] = X_{jk}$ for $j\ne k$ \citep[Theorem 4-3.2]{Sury}.

The matrix $T_i \da \Diag(1,\ldots,1,-1,1,\ldots,1)$ is defined as the identity matrix with the exception of one $-1$ on the diagonal in the $i$-th row.
The index of $\SL_r(\Z)$ in $\GL_r(\Z)$ is 2, thus together with $T_1$ either of the generating sets above generate the whole group $\GL_r(\Z)$.

A similar result for the principal congruence subgroup requires some calculations and therefore, it is formulated as a lemma:
\begin{lemma}
\label{gamma2gens}The principal congruence subgroup of level 2 in $\GL_r(\Z)$
\[
\Gamma_2 = \{A \in \GL_r(\Z) \mid A\equiv \Id \pmod 2\},
\]
is generated by the set
\[
\{X_{ij}^2,\, i\ne j\}  \cup \{T_i, i=1,\ldots,r\}
\]
of squares of elementary matrices and diagonal matrices which are the identity matrix with the exception of one $-1$ on the diagonal.
\end{lemma}

\begin{proof}
To show this, we transform a matrix $M = (M_{ij}) \in \Gamma_2$ to the identity matrix, by multiplying it with the given generators. The idea of the proof is to apply the idea behind the Euclidean algorithm. In this proof, $M_{ij}$ will always refer to the current state of the matrix, including any transformation applied so far.

Multiplying the matrix $X_{ij}^2$ from the left has the effect of adding the $j$-th row twice on the $i$-th row. Multiplying it from the right has the effect of adding the $i$-th column twice on the $j$-th column. Multiplication from the left with the matrix $T_i$ inverts the signs of the entries in the $i$-th row.

Starting with the first column, we repeat the following step until the column is that of the identity matrix:

Let $i$ be a row with a smallest non-zero absolute value in the first column, and let $j$ be another row with a larger absolute value in the first column. Add the $i$-th row on the $j$-th row $2k$ times, by multiplication of $X_{ji}^{2k}$, with a $k\in\Z\setminus\{0\}$ such that $|M_{j1} + 2kM_{i1}|$ becomes as small as possible.
%, preferring positive values over negative values of the same absolute value.

Note that if all entries in the first column but one are zero, this one value must be $\pm 1$, as it divides the determinant of the matrix. If there are more than one non-zero entries, they can not be all of equal absolute value, as $M_{11}$ is odd and the other entries are even. Hence, we will always find such rows $i$ and $j$.

%A consequence of this fact is that before each step, if the termination condition is not yet fulfilled, we can find such a row $j$, because otherwise all non-zero entries would have the same absolute value, in contrast to the fact that $M_{11}$ is odd and the other entries are even.

Also, each step reduces the sum of the absolute values in the column $\sum_{i=1}^r|M_{i1}|$, because $|M_{j1}+2kM_{i1}| < |M_{j1}|$. As $\sum_{i=1}^r|M_{i1}|$ is always positive, this algorithm terminates when $\sum_{i=1}^r|M_{i1}|=1$, which means, due to the invariant parity of the entries, that the first column is $(1,0,\ldots,0)^\top$ or $(-1,0,\ldots,0)^\top$.

If the upper right entry of the matrix is now $-1$, we multiply the matrix by $T_1$. $M_{11}$ is now 1. As all entries $M_{1i}$, $i>1$ in the first row of the matrix, besides the first one, are even, we can now easily cancel them by multiplication from the right with
\[
(X_{12}^2)^{-\frac{M_{12}}2} \cdots (X_{1r}^2)^{-\frac{M_{1r}}2}.
\]
to achieve that the first row and column are those of the identity matrix. Repeating this procedure for the other columns as well, we obtain the identity matrix as a product of the matrix $M$ and the given generators.
\end{proof}

\begin{corollary}
\label{gamma2gensalt}
The set
\[
\{X_{ik}, k\ne i\} \cup \{ X_{ji}^2, j\ne i\} \cup \{T_j, j=1,\ldots,r\}
\]
for some fixed $i\in\{1,\ldots,r\}$ generates a superset of $\Gamma_2$.
\end{corollary}
\begin{proof}
This can be shown using the following calculation, which uses the commutator relations given in \citep{Sury}, Theorem 4-3.2:
\begin{align*}
X_{jk}^2  &= [X_{ji},X_{ik}] \cdot X_{jk} \\
&= X_{ji} X_{ik} X_{ji}^{-1} X_{ik}^{-1} \cdot X_{jk} \\
&= X_{ji} \cdot X_{jk} \cdot X_{ik} X_{ji}^{-1} X_{ik}^{-1} \\
&= X_{ji} \cdot [X_{ji},X_{ik}]\cdot X_{ik} X_{ji}^{-1} X_{ik}^{-1} \\
&= X_{ji} X_{ji} X_{ik} X_{ji}^{-1} X_{ik}^{-1}  X_{ik} X_{ji}^{-1} X_{ik}^{-1} \\
&= X_{ji}^2  X_{ik} X_{ij}^{-2} X_{ik}^{-1} \\
&= [X_{ji}^2,X_{ik}]
\end{align*}
\end{proof}

%\pagebreak
\section{The odd case}

Before handling the most general case, we will first look at loop subgroups with only odd loops, followed by those with only even loops. The case of loop subgroups with mixed parity will then be easily accessible.

\begin{theorem}
\label{oddcase}For a loop subgroup $U\le F_r$, $r\ge 3$, with all loops odd and at most $r-2$ looplets, we have
\[
B(\Stab_{\Aut(F_r)}(U)) = \GL_r(\Z),
\]
where $B\colon \Aut(F_r) \to \GL_r(\Z)$ is the map defined in the preface.
\end{theorem}

I extract the part of the proof that will be re-used in the general case in a statement of its own:

\begin{lemma}
\label{oddcasepreimage}
Let $U\le F_r$, $r\ge 3$, be an $s_1/\ldots/s_r$-loop subgroup, $i,j\in\{1,\ldots,r\}$ with $i\ne j$ and $s_i$ odd. If $s_i =1$ or there exists $k\in\{1,\ldots,r\}$ with $s_k>1$, then 
\[
X_{ij} \in B(\Stab_{\Aut(F_r)}(U)).
\]
\end{lemma}

\begin{proof}[of \cref{oddcasepreimage}]
We construct a preimage of the elementary matrix $X_{ij}$ as a map of the form
\[
\gamma_{ij}(g_k) =
\begin{cases}
w\cdot g_i \cdot g_j, & k=j \\
\phantom{w\cdot g_i \cdot {}} g_k, & k\ne j
\end{cases}
\]
with a suitable $w\in F_r$. By \cref{autconstr}, this is an automorphism that stabilizes $U$ if the gene\-rator $g_j$ does not occur in $w$ and $\pi(w\cdot g_i) = \Id$.

To have $B(\gamma_{ij}) = X_{ij}$, the number of occurrences of all generators in $w$ must be zero each, that is $w\in [F_r,F_r]$. If the $i$-th loop actually is a looplet, we can choose $w=\Id$, as $\pi(g_i)=\Id$.

If $s_i>1$, this is where our preliminary calculations about permutations kick in. $g_k$ is another generator whose loop is not a looplet, i.e.\ $s_k>1$. If we only consider the set of cosets of $U$ that are on the loops $i$ or $k$
\[
N_{ik} \da \{ U, g_i^1 U, \ldots, g_i^{s_i-1}U, \, g_k^1 U,\ldots, g_k^{s_k-1}U\}
\]
we can interpret the permutations $\pi(g_i)$ and $\pi(g_k)$ as elements of $\Sym(N_{ik})$. We are now in the situation of \cref{altperm} with $\sigma = \pi(g_i)$ and $\omega = \pi(g_k)$, hence $A_{N_{ik}} \le \pi([\langle g_i,g_k\rangle ,\langle g_i,g_k\rangle])$. Since $\pi(g_i)$ is a cycle of odd length $s_i$, it is itself an even permutation, thus $\pi(g_i)\in A_{N_{ik}}$. This proves the existence of a word $w\in [\langle g_i,g_k\rangle ,\langle g_i,g_k\rangle]$ with $\pi(w) = \pi(g_i)^{-1}$, that is $\pi(w\cdot g_i) = \Id$. With this word, the automorphism $\gamma_{ij}$ is indeed in $\Stab_{\Aut(F_z)}(U)$ and a preimage of $X_{ij}$.
\end{proof}

\begin{proof}[of \cref{oddcase}]
In order to show that the image of the stabilizer subgroup of $U$ is the full linear group, we will find preimages of a generating set of $\GL_r(\Z)$. The automorphism $\tau_i\in\Aut(F_r)$ that sends $g_i\mapsto g_i^{-1}$ and $g_j \mapsto g_j$ for $j\ne i$ stabilizes any loop subgroup, in particular $U$. Thus we have $\tau_1$ as a suitable preimage of $T_1$ under $B$.

If there are at most $r-3$ looplets in the loop subgroup, we can choose suitable $k\in\{1,\ldots,r\}$ with $s_k>1$ for all $i,j\in\{1,\ldots,r\}$, $i\ne j$. Thus we find preimages in $\Stab_{\Aut(F_z)}(U)$ for all elementary matrices, by \cref{oddcasepreimage}, and the proof is complete.

If there are $r-2$ looplets, since $r\ge 3$, there is at least one looplet, for example the $i$-th. Now we can find preimages for the elements of the generating set 
\[
\{X_{ik}, k\ne i\} \cup \{ X_{ji}, j\ne i\}
\]
of $\SL_n(\Z)$, concluding the proof: For the first set of matrices, \cref{oddcasepreimage} can be applied since $s_i=1$. For the second set either $s_j=1$ or there is a suitable $k$, as there are two proper loops and the $i$-th is none of them, hence \cref{oddcasepreimage} can be applied.
\end{proof}

\begin{example}
For the 3/3/1 loop subgroup seen in \vref{loopex}, the following automorphisms are constructed:
\begin{align*}
\gamma_{31}(x,y,z) &= (z\cdot x,y,z) \\
\gamma_{32}(x,y,z) &= (x,z\cdot y,z) \\
\gamma_{13}(x,y,z) &= (x,y, yxy^{-1}xyx^{-2}y^{-1} \cdot x \cdot z) \\
\gamma_{23}(x,y,z) &= (x,y, \underbrace{xyx^{-1}yxy^{-2}x^{-1}}_{\in [\langle x,y\rangle,\langle x,y\rangle]} \cdot y \cdot z).
\end{align*}
\end{example}

\section{The level}

To get closer to the general case, we will now find a useful lower bound to  the subgroup $B(\Stab_{\Aut(F_z)}(U))$. Once we know that the principal congruence subgroup of level 2
\[
\Gamma_2 = \{M \in \GL_r(\Z) \mid M\equiv \Id \pmod 2\}
\]
is contained in $B(\Stab_{\Aut(F_z)}(U))$, we can consider the projection
\[
\overline{B(\Stab_{\Aut(F_z)}(U))} \le \GL_r(\Z/2\Z),
\]
which still contains all information about the group.

The following set generates $\Gamma_2$ according to \cref{gamma2gens}:
\[
\{X_{ij}^2,\, i\ne j\}  \cup \{T_j, j=1,\ldots,r\}.
\]
The set
\[
\{X_{ik}, k\ne i\} \cup \{ X_{ji}^2, j\ne i\} \cup \{T_j, j=1,\ldots,r\}
\]
for some fixed $i$ generates a superset of $\Gamma_2$ (\cref{gamma2gensalt})

\begin{lemma}
\label{level}For a loop subgroup $U\le F_r$, $r\ge 3$, with at most $r-2$ looplets, we have
\[
\Gamma_2 \le B(\Stab_{\Aut(F_r)}(U)).
\]
\end{lemma}

\begin{proof}
As in the proof for the odd case, \cref{oddcase}, we will find preimages in the stabilizer subgroup $\Stab_{\Aut(F_z)}(U)$ to the elements of a generating set of $\Gamma_2$. As preimages for the matrices $\{T_j, j=1,\ldots,r\}$ we choose the same automorphisms $\tau_j$, which invert the $j$-th generator $g_j$ and do not modify the other generators.

We will find preimages of squares of elementary matrices $X_{ij}^2$ as maps $\gamma_{ij}^{(2)}$ of the form 
\[
\gamma_{ij}^{(2)}(g_k) =
\begin{cases}
w\cdot g_i^2 \cdot g_j, & k=j \\
\phantom{w\cdot g_i^2 \cdot {}}g_k & k\ne j.
\end{cases}
\]
The important fact to consider here is that while $\pi(g_i)$ may not be an even permutation, $\pi(g_i^2) = \pi(g_i)^2 \in A_N$ certainly is. Therefore \cref{altperm} provides us with a suitable $w\in F_r$ so that $\gamma_{ij}^{(2)}\in \Stab_{\Aut(F_r)}$ by \cref{autconstr}.

If we have at most $r-3$ looplets, we find preimages to all squares of elementary matrices this way. In the case of $r-2$ looplets, we find, as above, preimages for each of 
\[
\{X_{ik}, k\ne i\} \cup \{ X_{ji}^2, j\ne i\}
\]
for a fixed $i$ with $s_i=1$.
\end{proof}

\section{Stabilizer subgroups in \texorpdfstring{$\GL_r(\Z/2\Z)$}{GL\_r(Z/2Z)}}

When we inspect the loop subgroup with even loops, we will come across the group of integral matrices with odd column sums. It contains the principal congruence subgroup of level 2, hence it is completely determined by its image in $\GL_r(\Z/2\Z)$:
\[
S(\ev) \da \{ M\in \GL_r(\Z/2\Z) \mid \ev \cdot M = \ev \}
\]
where $\ev = (1,\ldots,1) \in (\Z/2\Z)^r$ is the row vector, all of whose entries are one. More general, we will be interested in the stabilizer subgroup of a row vector $v=(v_1,\ldots,v_r)\in (\Z/2\Z)^r$ under the action of right multiplication:
\[
S(v) \da \{ M\in \GL_r(\Z/2\Z) \mid v \cdot M = v \}
\]

These are indeed groups, as $\Id \in S(v)$ and for $M_1,M_2\in S(v)$ we have $v \cdot (M_1 M_2) = (v \cdot M_1) \cdot M_2 = v \cdot M_2 = v$ and $v = v \cdot M_1 M_1^{-1} = v \cdot M_1^{-1}$. Of course we have $S(0) = \GL_r(\Z/2\Z)$.

%\pagebreak[3]
\subsection{Generators}

\begin{lemma}
\label{stabgens}The group $S(\ev)$ is generated by “double elementary matrices” of the form $X_{ik} X_{jk}$, $i,j,k\in\{1,\ldots,r\}$ pairwise distinct, having ones on the diagonal and in two additional positions in the same column, and zeros everywhere else.

More general, $S(v)$ is generated by the elementary matrices $X_{ij}$ for $i\ne j$ and $v_i=0$ and the double elementary matrices $X_{ik}X_{jk}$ for $i,j,k\in\{1,\ldots,r\}$ pairwise distinct and $v_i=v_j=1$
\end{lemma}

Note that the case $v=0$ is covered by the lemma, as $S(0) = \GL_r(\Z/2\Z)$ is generated by all the elementary matrices $X_{ij}$, $i\ne j$. If the vector $v$ is a unit vector, i.e.\ precisely one entry is $1$, the generating set does indeed not contain any double elementary matrices.

\begin{proof}
What does the defining equation $v\cdot M = v$ tell us? On the one hand, any row $i$ of the matrix where the corresponding entry $v_i$ in the row vector is zero does not affect the equation at all and its entries are irrelevant. On the other hand, the sum of all relevant entries in a column $j$ is odd if and only if $v_j=1$. Therefore, the alleged generators are indeed contained in $S(v)$.

We first summarize the effect that multiplying one of these generators to an matrix in $S(v)$ has:  The multiplication from the left of an elementary matrix $X_{ij}$ has the effect of adding the $j$-th row on the $i$-th row. The multiplication from the left of a double elementary matrix $X_{ik}X_{jk}$ has the effect of adding the $k$-th row simultaneously on the $i$-th and the $j$-th row. 

We will now transform a matrix in $S(v)$ into the identity matrix by multiplying the alleged generators from the left. To do so, we suppose that the first $i-1$ columns are already that of the elementary matrix and treat each column $i=1,\ldots,r$ consecutively as follows:

\begin{enumerate}
\item Ensure that there is a 1 on the diagonal. If there is none, there still must be at least one 1 in the column, otherwise the matrix would not be regular. There even must be a 1 in a row $j$ with $j > i$, as otherwise the current column would be a linear combination of the columns to the left of it, which are, due to our transformation, the unit vectors $e_1,\ldots,e_{i-1}$.

Now add this row $j$ on the $i$-th row (multiplication with $X_{ij}$).  If $v_i=1$, then, to be allowed to do that, also add the $j$-th row on any other row $k$ with $v_k=1$ (multiplication with $X_{ij}X_{kj}$). This step does not alter the previous columns, as the row $j$ has zeros there.

If there is no such other row $k$, that is, if there are exactly two ones in the vector $v$, namely $v_i=v_j=1$, and if the current column has only one 1 in the $j$-th row, some additional shuffling is necessary. Let $k\ne i,j$ be any other row. This implies $v_k=0$. The matrix
\[
(X_{ik}X_{jk}\cdot X_{ki}\cdot X_{kj})^2
\]
is actually the permutation matrix that swaps the $i$-th and $j$-th row, and is here written in terms of the given generators. Multiplying this matrix from the left, we move the 1 to the right spot, while again not altering the previous columns.

\item Eliminate all ones that are not on the diagonal. Ones that are in rows $j$ with $v_j=0$ can be eliminated directly with $X_{ji}$. Ones in rows $j$ and $k$ with $v_j=v_k=1$ can only be eliminated pairwise with $X_{ji}X_{ki}$. But in any case there is an even number of them: Either $v_i=0$. Then we know that there is an even number of ones on relevant rows to be eliminated. Or $v_i=1$, then there is an odd number of relevant ones in this column. But the $i$-th row itself is relevant, and we do not want to eliminate the one on the diagonal. This leaves an even number of relevant ones to be eliminated.
\end{enumerate}
So any matrix in $S(v)$ can be transformed into the identity matrix using the given generators, thus they indeed generate all of $S(v)$.
\end{proof}

\subsection{Maximality}

Although not strictly required for what follows, for a better understanding of the subgroups $S(v)$ we will now see that they are maximal if $v\ne0$. 

\begin{lemma}
\label{stabconj}Any subgroup $S(v)\le\GL_r(\Z/2\Z)$ with $v\in (\Z/2\Z)^r\setminus\{0\}$ is conjugated to $S(\ev)$.
\end{lemma}

\begin{proof}
Let $N\in \GL_r(\Z/2\Z)$ be a matrix with $\ev\cdot N = v$. Then
\begin{align*}
S(v) 
&= \{ M\in \GL_r(\Z/2\Z) \mid v \cdot M = v \} \\
&= \{ M\in \GL_r(\Z/2\Z) \mid \ev \cdot N \cdot M =\ev \cdot N \}  \\
&= \{ M\in \GL_r(\Z/2\Z) \mid \ev \cdot N \cdot M \cdot N^{-1}=\ev  \}  \\
&= \{ N^{-1} \cdot M'\cdot N \in \GL_r(\Z/2\Z) \mid \ev \cdot M' \cdot =\ev  \} \\
&= N^{-1} S(\ev) N.
\end{align*}
\end{proof}

\begin{lemma}
\label{max}Any subgroup $S(v)\le\GL_r(\Z/2\Z)$, $r\ge 3$, with $v\in (\Z/2\Z)^r\setminus\{0\}$ is maximal, that is, there is no proper subgroup of $\GL_r(\Z/2\Z)$ that is a proper supergroup of $S(v)$.
\end{lemma}

\begin{proof}
Due to \cref{stabconj} it is sufficient to show that $S(\ev)$ is maximal. To show this we take a matrix $M\notin S(\ev)$ and transform it into an elementary matrix by multiplying it with matrices in $S(\ev)$. Since $S(\ev)$ also contains the permutation matrices, we then get all elementary matrices and thus the full group $\GL_r(\Z/2\Z)$.

As established in the previous section, multiplication from the left with a double elementary matrix $X_{ik}X_{jk}$ has the effect of adding the $k$-th row on the $i$-th and on the $j$-th row. Multiplication from the left with a permutation matrix swaps rows. Multiplication from the right with $X_{ik}X_{jk}$ has the effect of replacing the $k$-th column with the sum of the $k$-th, $i$-th and $j$-th columns. The permutation matrices swap the columns when multiplied from the right.

The matrix $M$ has at least one column with an even column sum, otherwise we had $M\in S(\ev)$. It also has at least one column with an odd column sum. Otherwise $M$ would map the standard basis vectors to vectors with even sums. But these would not span all of $(\Z/2\Z)^r$, as the sum of two such vectors has again even sum. By swapping the columns we can ensure that the first column has an odd column sum and the last column has an even column sum. Then we make all column sums in between odd: If column $j$, $1<j<r$ has an even column sum we multiply from the right with $X_{1j}X_{rj}$. This replaces this column by the sum of the first, $j$-th and last column, which then has, as required, odd column sum.

Now we proceed by running the Gaussian Elimination Algorithm for the first $r-1$ columns, as done in the previous section. Since all these columns have an odd column sum, this is possible using transformations which are represented by matrices in $S(\ev)$. Hence, we obtain a matrix of the form
\[
\begin{pmatrix}
1 & 0 & \cdots & 0 & * \\
0 & \ddots &  \ddots & \vdots & \vdots \\
\vdots & \ddots & \ddots & 0 & \vdots \\
\vdots & &\ddots & 1 & * \\
0 & \cdots &\cdots  & 0 & 1 
\end{pmatrix}.
\]

The transformations did not alter the parity of the column sums, thus the last column still has an even sum of $2k+2$ for some $k\in\N$. By adding the last row to $2k$ of the other rows having a one in the last column, which is possible with matrices from $S(\ev)$, we eliminate all but two ones in the last column. This is then an elementary matrix, finishing this proof.

\end{proof}

\section{The even case}

With the knowledge about $S(\ev)$ from the previous section we can find out more about the image of stabilizer subgroups of loop subgroups with all loops even.

\begin{theorem}
\label{evencase}For a loop subgroup $U\le F_r$, $r\ge 3$, with all loops even, we have
\[
S(\ev) \le \overline{B(\Stab_{\Aut(F_r)}(U))}
\]
\end{theorem}

\begin{proof}
The set of double elementary matrices $X_{ik}X_{jk}$ generate $S(\ev)$. By the following lemma, these are in $\overline{B(\Stab_{\Aut(F_r)}(U))}$.
\end{proof}


\begin{lemma}
\label{evencasepreimage}
Let $U\le F_r$, $r\ge 3$ be an $s_1/\ldots/s_r$-loop subgroup and $i,j,k\in\{1,\ldots,r\}$ distinct with $s_i$ and $s_j$ even. Then 
\[
X_{ik}X_{jk} \in B(\Stab_{\Aut(F_r)}(U)).
\]
\end{lemma}

\begin{proof}
We again vary the construction that led us to preimages of generators of $\GL_r(\Z)$ in the odd case (\cref{oddcasepreimage}) and of $\Gamma_2$ when calculating the level (\cref{level}). This means that we find automorphisms $\gamma_{ijk}$ of the form 
\[
\gamma_{ijk}(g_l) =
\begin{cases}
w\cdot g_i g_j \cdot g_k, & l=k \\
\phantom{w\cdot g_i g_j \cdot {}}g_l, & l\ne k.
\end{cases}
\]
such that $\gamma_{ijk}$ is a preimage of $X_{ik}X_{jk}$. The conditions under which these are actually automorphisms, and under which they stabilize $U$ are given by \cref{autconstr}. We know that the cycles $\pi(g_i)$ and $\pi(g_j)$ are both of even length, thus odd permutations. Therefore, their pro\-duct $\pi(g_ig_j)\in A_N$ and with \cref{altperm} we can find a suitable $w\in [\langle g_i,g_j\rangle, \langle g_i,g_j\rangle]$.
\end{proof}

\section{The mixed case}

If we combine the proofs for the odd and the even case, we can find an analogous result for general loop subgroups.


\begin{theorem}
\label{mixedcase}For a loop subgroup $U\le F_r$, $r\ge 3$, with at most $r-2$ looplets, we have
\[
S(v) \le \overline{B(\Stab_{\Aut(F_r)}(U))}
\]
where
\[
v_i = 
\begin{cases}
0, & \text{if } s_i \text{ odd} \\
1, & \text{if } s_i \text{ even}.
\end{cases}
\]
\end{theorem}

\begin{proof}
By \cref{stabgens}, $S(v)$ is generated by the elementary matrices $X_{ij}$ for $i\ne j$ and $v_i=0$ and the double elementary matrices $X_{ik}X_{jk}$ for $v_i=v_j=1$.

The double elementary matrices $X_{ik}X_{jk}$ are in $\overline{B(\Stab_{\Aut(F_r)}(U))}$ for $v_i=v_j=1$, as shown in \vref{evencasepreimage}.

Let $i,j\in\{1,\ldots,r\}$, $i\ne j$ and $v_i=0$. We need to show $X_{ij}\in \overline{B(\Stab_{\Aut(F_r)}(U))}$. If $s_i=1$ or there is $k\in\{1,\ldots,r\}$ with $k\ne i,j$ and $s_k>1$, this follows from \cref{oddcasepreimage}. If that is not the case, we are in the situation of $r-2$ looplets with $s_i>1$, $s_j>1$ and $s_k=1$ for $k\ne i,j$. Invoking \cref{oddcasepreimage} for $X_{ik}$ and for $X_{kj}$, and using $[X_{ik},X_{kj}]=X_{ij}$, we show $X_{ij}\in \overline{B(\Stab_{\Aut(F_r)}(U))}$.
\end{proof}

\section{Sharper bounds}

To fully understand the situation, we yet have to find out whether the lower bound $S(v)$ from \cref{mixedcase} is already the full group $\overline{B(\Stab_{\Aut_(F_r)}(U))}$. It turns out that this is indeed the case.

Information on the upper bound of the image of the stabilizer subgroup can be obtained in the more general setting of congruence subgroups of level 2:
\begin{theorem}
\label{generalupperbound}
Let $U\le F_r$, $r\ge 3$, be a subgroup with $\Gamma_2 \le B(\Stab_{\Aut(F_r)}(U))$, and let
\[
v_i = 
\begin{cases}
0, & \text{if $\pi(g_i)$ is an even permutation} \\
1, & \text{if $\pi(g_i)$ is an odd permutation.} 
\end{cases}
\]
Then,
\[
\overline{B(\Stab_{\Aut(F_r)}(U))} \le S(v).
\]
\end{theorem}

\begin{proof}
Let $\gamma\in\Stab_{\Aut(F_r)}(U)$. For a generator $g_i$, $i\in\{1,\ldots,r\}$, the permutation $\pi(\gamma(g_i))$ has the same parity as $\pi(g_i)$, by \cref{autconj}. Therefore, the number of odd permutations in the word $\gamma(g_i)$ equals $v_i$ modulo 2:
\[
\sum_{j=1}^r \#_{g_j}\gamma(g_i) \cdot v_j \equiv v_i \pmod 2
\]
This condition can be written as $v\cdot \overline{B(\gamma)} = v$, hence $\overline{B(\gamma)} \in S(v)$. 
\end{proof}

This is an interesting result, as the subgroups $S(v)$ are maximal, but far from the only maximal groups.

\begin{corollary}
\label{sharpbound}For a loop subgroup $U\le F_r$, $r\ge 3$, with at most $r-2$ looplets, we have
\[
S(v) = \overline{B(\Stab_{\Aut(F_r)}(U))}
\]
where
\[
v_i = 
\begin{cases}
0, & \text{if } s_i \text{ odd} \\
1, & \text{if } s_i \text{ even}.
\end{cases}
\]
\end{corollary}

\begin{proof}
\cref{generalupperbound} applies because $\Gamma_2\le\overline{B(\Stab_{\Aut(F_r)}(U))}$ by \cref{level} and the permutation $\pi(g_i)$ is odd if and only if $s_i$ is even. \cref{mixedcase} provides the inclusion in the other direction.
\end{proof}

\section{The excluded case}
\label{excludedcasesec}

In the previous sections, we have always excluded loop subgroups with exactly $r-1$ looplets. These subgroups have some special properties that make them break rank and therefore, they are handled separately here.

Let $U$ be a loop subgroup with exactly $r-1$ looplets and assume without loss of generality that $s_1\ne 1$. The subgroup can now be written as 
\[
U = \{ w\in F_r \mid \#_x w \equiv 0 \pmod {s_1}\}.
\]
This fact is easily seen by tracing a word in the coset graph of $U$: Only occurrences of $x$ advance on the graph, and $x$ must occur a multiple of $s_i$ times to end up at the node $U$.

Let $A\colon F_r \to \Z^r$ be the surjective abelianization map defined by $w \mapsto (\#_{g_i} w)_{i=1,\ldots,r}$. Then $U = A^{-1}(U')$ with $U' \da \{ v\in\Z^r \mid v_1 \equiv 0 \mod s_1\}\le \Z^r$. This allows us to calculate $B(\Stab_{\Aut(F_r)}(U))$ using the following, more general observation:

\begin{lemma}
\label{stabofpreimage}
Let $\varphi\colon G \to G'$ be a surjective group homomorphism with its kernel characteristic in $G$. Let $H\le G$ and $H'\le G'$ be subgroups such that $H = \varphi^{-1}(H')$. Let $\psi\colon \Aut(G)\to \Aut(G')$ be the map induced by $\varphi$. Then
\[
\psi(\Stab_{\Aut(G)}(H)) = \Stab_{\Aut(G')}(H') \cap \psi(\Aut(G)).
\]
\end{lemma}

\begin{proof}
For $\gamma\in\Aut(G)$, $y\in G'$ the map $\psi\colon \Aut(G) \to \Aut(G')$ is defined by $\psi(\gamma)(y) \da \varphi(\gamma(x))$ for an $x\in\varphi^{-1}(y)$. This is well-defined because the kernel of $\varphi$ is characteristic. Thus
\begin{align*}
\psi(\Stab_{\Aut(G)}(H)) 
&= \psi(\{\gamma \in \Aut(G) \mid \gamma(H) = H\}) \\
&= \{\psi(\gamma) \mid \gamma \in \Aut(G),\ \forall x\in H: \gamma(x) \in H\} \\
&= \{\psi(\gamma) \mid \gamma \in \Aut(G),\ \forall x\in H: \varphi(\gamma(x)) \in \varphi(H)\} \\
&= \{\psi(\gamma) \mid \gamma \in \Aut(G),\ \forall y\in H': \varphi(\gamma(\varphi^{-1}(y))) \in \varphi(H)\} \\
&= \{\psi(\gamma) \mid \gamma \in \Aut(G),\ \forall y\in H': \psi(\gamma)(y) \in H'\} \\
&= \{\gamma' \in \Aut(G') \mid \forall y\in H': \gamma'(y) \in H'\} \cap \psi(\Aut(G))\\
&= \Stab_{\Aut(G')}(H') \cap \psi(\Aut(G))
\end{align*}
\end{proof}

\begin{proposition}
For the $s_1/1/\ldots/1$ loop subgroup $U$, $s_i\in \N$, of $F_r$ we have
\[
\Gamma_{s_1} \le B(\Stab_{\Aut(F_r)}(U)) = \Stab_{\GL_r(\Z)}(U') \le \GL_r(\Z)
\]
where
\[
U' \da \{v \in \Z^r \mid v_1 \equiv 0\mod s_1\}.
\]
\end{proposition}

\begin{proof}
As noted before, $U = A^{-1}(U')$. $B$ is surjective, because preimages of a generating set of $\GL_r(\Z)$ are given by $\tau_1$ and the automorphisms in the proof of \cref{oddcasepreimage}. Therefore, \cref{stabofpreimage} gives us
\[
B(\Stab_{\Aut(F_r)}(U)) = \Stab_{\GL_r(\Z)}(U'). 
\]

Since every matrix in $\Gamma_{s_1}$ stabilizes $U'$, $B(\Stab_{\Aut(F_r)}(U))$ contains $\Gamma_{s_1}$.
\end{proof}

As a matter of fact, $s_1$ is the level of the congruence subgroup $B(\Stab_{\Aut(F_r)}(U))$. The difference to the other loop subgroups is evident: While here we easily reach any congruence subgroup level, in the other cases we do not exceed level 2.

\section{Index two subgroups of \texorpdfstring{$F_r$}{F\_r}}
\label{index2}

The property of subgroups of $F_r$ that the image of their stabilizer subgroups under $\bar B$ is one of the groups
\[
S(v) = \{ M\in \GL_r(\Z/2\Z) \mid v \cdot M = v \}
\]
for $v\in (\Z/2\Z)^r$ is not limited to loop subgroups. In this section, we will see that it holds for subgroups of $F_r$ of index $2$ as well. These are in general not loop subgroups.

\begin{theorem}
Let $U < F_r$ be a subgroup of index two. We have
\[
\overline{B(\Stab_{\Aut(F_r)}(U))} = S(v)
\]
where
\[
v_i =
\begin{cases}
1, & \text{ if } g_i \notin U \\
0, & \text{ if } g_i \in U.
\end{cases}
\]
\end{theorem}

\begin{proof}
As shown e.g.\ in \citep{Frei08}, Lemma 3.7, a subgroup $U<F_r$ of index 2 is fully determined by the generators of the free group that are contained in $U$, since $g_i^2\in U$ for all generators $g_i$. The coset graph of $U$ is:

\begin{center}
\begin{tikzpicture}[auto]
\draw (0,0) node[state,accepting,draw,circle,minimum size = 1.3cm] (1) {$U$};
\draw (3,0) node[state,draw,circle,minimum size = 1.3cm] (2) {$F_r\setminus U$};
\draw[->] (1) to[out=45,in=135] node [above] {$g_i\notin U$} (2);
\draw[->] (2) to[out=-135,in=-45] node [below] {$g_i\notin U$} (1);
\draw[->] (1) edge [loop left] node {$g_i\in U$} (1);
\draw[->] (2) edge [loop right] node {$g_i\in U$} (2);
\end{tikzpicture}
\end{center}

As can be seen from the graph, we actually have $g_i^2\in \NT(U)$. By the argument of \cref{someperm}, preimages of the generators $X_{ij}^2$, $i\ne j$, and $T_i$ of $\Gamma_2$ in the stabilizer subgroup of $U$ can be given explicitly by the automorphisms $\gamma_{ij}: g_j \mapsto g_i^2g_j$, $g_k \mapsto g_k$, $k\ne j$, and $\tau_i$. This proves $\Gamma_2 \le B(\Stab_{\Aut(F_r)}(U))$ and we can actually project this group into $\GL_r(\Z/2\Z)$ without losing information.


% To prove $\overline{B(\Stab_{\Aut(F_r)}(U)} \ge S^\top(v)$, we assume we have a $\gamma\in \Stab_{\Aut(F_r)}(U)$ with $\overline{B(\gamma)}\notin S^\top(v)$. This implies that at least one of the two sum equations $(*)$ or $(**)$ are violated.
% If the first one is violated, we have a $g_i\notin U$ with $\sum_{j=1}^r \#g_j \gamma(g_i) \cdot v_j \equiv 0 \pmod 2$, which is equivalent to $\gamma(g_i)\in U$, in contradiction to the fact that gamma stabilizes $U$. Similarly, if the second is violated, we find that $\gamma(g_i)\notin U$ for a generator with $g_i\in U$, which is again a contradcition.

For a word $w\in F_r$, only the number of generators with $g_i\notin U$ in the word decide whether it is in $U$, as only those have an effect when tracing the word in the coset graph. Due to our definition of $v$, this leads to the equation
\[
w \in U \iff \sum_{j=1}^r \#_{g_j} w \cdot v_j \equiv 0 \pmod 2
\]
and thus for all $i\in\{1,\ldots,r\}$
\[
\sum_{j=1}^r \#_{g_j}  \gamma(g_i) \cdot v_j \equiv v_i \pmod 2.
\]

We first prove $\overline{B(\Stab_{\Aut(F_r)}(U))} \ge S(v)$. For a matrix $M\in S(v)$, take any preimage $\gamma\in \bar B^{-1}(M)$. For a word $w\in U$ we have, using the two previous equations,
\begin{align*}
\sum_{j=1}^r \#_{g_j} \gamma(w) \cdot v_j
&= \sum_{j=1}^r \left( \sum_{i=1}^r \#_{g_j} \gamma(g_i) \cdot \#_{g_i} w\right) \cdot v_j \\
&= \sum_{i=1}^r \#_{g_i} w \cdot \left( \sum_{j=1}^r \#_{g_j} \gamma(g_i) \cdot v_j \right)  \\
&\equiv \sum_{i=1}^r \#_{g_i} w \cdot v_i  \pmod 2\\
&\equiv 0  \pmod 2,
\end{align*}
showing $\gamma(w)\in U$ and thus $\gamma\in \Stab_{\Aut(F_r)}(U)$.

The other inclusion, $\overline{B(\Stab_{\Aut(F_r)}(U))} \le S(v)$, follows from \cref{generalupperbound} and the fact that $\pi(g_i)$ is even if and only if $g_i\in U$.
\end{proof}

\section{Discussion and further directions}

The study of images of stabilizer subgroups under the map $B$ was motivated by the analogy to origamis, which are restricted to the rank $r=2$. Comparing these settings, we see that higher ranks cause the objects to become simpler. In \citep{HubLe}, Theorem B and Conjecture 1, the size of the orbit of an $L(a,b)$-origami with $n$ squares under the action of $\Out^+(F_2)\cong\SL_r(\Z)$ is calculated for even $n$ and conjectured for odd $n$. This number, which is also the index of the Veech group of the origami, grows without bound as $n$ increases. The $F_2$ subgroups induced by $L$-origamis are loop subgroups in our sense, but here we find that, no matter what the index of the loop subgroup (with not $r-2$ looplets) is, the index of the image of its stabilizer subgroup in $\GL_r(\Z)$ with $r>2$, is bounded by $[\GL_r(\Z/2\Z):S(v)] = 2^r-1$.

This bound is caused by applying the map $B$, as the index of the stabilizer subgroups in $\Aut(F_r)$ is still unbounded, as shown in \cref{unboundstabgroup}. Thus a lot of information about these subgroups is lost in the process, making this approach less useful if one is primarily interested in the situation in $\Aut(F_r)$.

While our main result has been reached now, we want to give some thoughts about possible further directions.

So far, the loops of the loop subgroups were pairwise disjoint, with exception of the node $U$ itself. This was a crucial part of the argument, as it allowed us, for a pair of generators $g_i$ and $g_j$, to find another generator $g_k$, $k\ne i,j$, such that the permutations $\pi(g_j)$ and $\pi(g_k)$ were in the shape required by \cref{altperm}. But to find such a generator $g_k$, it is not really necessary that \emph{all} other loops are disjoint, it is sufficient to have \emph{one} such loop. Therefore, one can expect a possible generalization of \cref{sharpbound} to require just this. Unfortunately, for non-loop-subgroups, it is not easy to see that we have pre-images of a matrix $T_i$ or any other matrix with determinant $-1$.


\begin{example}
One such group can be obtained by taking the $3/3/1/3$ subgroup, and merging the nodes $g_4^1U$ and $g_4^2U$ with $x^1U$ resp.\ $x^2U$. The resulting coset graph is shown in \vref{mergedcosetfigure1}.
\begin{figure}
\centering
\begin{tikzpicture}[auto]
\draw (0,0) node[state,accepting,draw,circle] (1) {$U$};
\begin{scope}[xshift=2cm]
\path (1) --
      (canvas polar cs:radius=2cm, angle=60) node[state,draw,circle] (2) {$y^1U$} --
      (canvas polar cs:radius=2cm, angle=-60) node[state,draw,circle] (3) {$y^2U$};
\draw[->] (canvas polar cs:radius=2cm, angle=160) arc(160:120:2cm) node[above] {$y$} arc(120:80:2cm);
\draw[->] (canvas polar cs:radius=2cm, angle=40) arc(40:0:2cm) node[right] {$y$} arc(0:-40:2cm);
\draw[->] (canvas polar cs:radius=2cm, angle=-80) arc(-80:-120:2cm) node[below] {$y$} arc(-120:-160:2cm);
\draw[->] (2) edge [in=45,out=75,loop] node {$z,x,g_4$} (2);
\draw[->] (3) edge [in=-75,out=-45,loop] node {$z,x,g_4$} (3);
\end{scope}
\begin{scope}[xshift=-2cm]
\path (1) --
      (canvas polar cs:radius=2cm, angle=120) node[draw,circle] (2) {$x^1U$} --
      (canvas polar cs:radius=2cm, angle=-120) node[draw,circle] (3) {$x^2U$};
\draw[->] (canvas polar cs:radius=2cm, angle=20) arc(20:60:2cm) node[above] {$x,g_4$} arc(60:100:2cm);
\draw[->] (canvas polar cs:radius=2cm, angle=140) arc(140:180:2cm) node[left] {$x,g_4$} arc(180:220:2cm);
\draw[->] (canvas polar cs:radius=2cm, angle=-100) arc(-100:-60:2cm) node[below] {$x,g_4$} arc(-60:-20:2cm);
\draw[->] (2) edge [in=105,out=135,loop] node {$z,y$} (2);
\draw[->] (3) edge [in=225,out=255,loop] node {$z,y$} (3);
\end{scope}
\draw[->] (1) edge [loop left] node {$z$} (1);
\end{tikzpicture}
\caption{A subgroup obtained from a 3/3/1/3 loop subgroup by merging nodes.}
\label{mergedcosetfigure1}
\end{figure}
The similarity to \cref{loopex} is obvious. Preimages to the elementary matrices are found the same way. We also see that $T_2$ has the preimage $\tau_2$, thus the image of the stabilizer subgroup is again the whole linear group.
\end{example}

\begin{example}
But also the more convoluted case of the subgroup with the coset graph from \vref{mergedcosetfigure2},
\begin{figure}
\centering
\begin{tikzpicture}[auto]
\node[state,accepting,draw,circle] (1) at (0,0) {$U$};
\node[state,draw,circle] (2) at (canvas polar cs:radius=3cm, angle=378) {$g_1^1U$};
\node[state,draw,circle] (3) at (canvas polar cs:radius=3cm, angle=306) {$g_2^1U$};
\node[state,draw,circle] (4) at (canvas polar cs:radius=3cm, angle=234) {$g_3^1U$};
\node[state,draw,circle] (5) at (canvas polar cs:radius=3cm, angle=162) {$g_4^1U$};
\node[state,draw,circle] (6) at (canvas polar cs:radius=3cm, angle=90) {$g_5^1U$};
\draw (2) edge[->,in=363,out=393,loop] node {$y,z,g_4$} (2);
\draw (3) edge[->,in=291,out=321,loop] node {$z,g_4,g_5$} (3);
\draw (4) edge[->,in=219,out=249,loop] node {$x,g_4,g_5$} (4);
\draw (5) edge[->,in=147,out=177,loop] node {$x,y,g_5$} (5);
\draw (6) edge[->,in=75,out=105,loop] node {$x,y,z$} (6);
\foreach \gen/\n in {g_5/0, g_4/1, z/2, y/3, x/4} {
\begin{scope}[rotate=90-72/2+\n*72,xshift=1.577cm]
\draw[->,rotate=0] (canvas polar cs:radius=1.577cm, angle=45) arc(45:-45:1.577cm);
\node at (canvas polar cs:radius=1.577cm + 2mm, angle=0) {$\gen$};
\draw[->,rotate=0] (canvas polar cs:radius=1.577cm, angle=-85) arc(-85:-160:1.577cm);
\node at (canvas polar cs:radius=1.577cm + 2mm, angle=-105) {$\gen$};
\draw[->,rotate=0] (canvas polar cs:radius=1.577cm, angle=160) arc(160:85:1.577cm);
\node at (canvas polar cs:radius=1.577cm + 2mm, angle=105) {$\gen$};
\end{scope}
}
\end{tikzpicture}
\caption{A supergroup of the 3/3/3/3/3 loop subgroup.}
\label{mergedcosetfigure2}
\end{figure}
which is obtained by merging the cosets of the $3/3/3/3/3$ loop subgroup of $F_5$, has the property that for generators $i,j$, there is a third generator $k$ that the permutations $\pi(g_j)$ and $\pi(g_k)$ are in the shape required for \cref{altperm}. Therefore, preimages to the elementary matrices exist. The automorphism $\tau_1$ is not a stabilizer, so a preimage to $T_1$ is not easily given. Our results so far tell us that the image of the stabilizer subgroup contains the full special linear group, but to decide whether it is the full group, additional arguments are required. Unfortunately, the code described in \cref{cosetproject} was not able to calculate the stabilizer subgroup in reasonable time.
\end{example}

\Vref{subgrouptable} gives, for a given rank of the the free group and a given maximum index the number of conjugacy classes of subgroups, the number of loop subgroups where \cref{sharpbound} is applicable and the number of subgroups where for each pair of generators there is a third generator with permutations as required for \cref{altperm}. It is calculated using \cite{GAP} using the script printed on page \pageref{countingsubgroupsscript}.

Our proofs are based on the fact that we have the whole alternating group $A_N$ as commutators of $\langle \pi(g_j),\pi(g_k)\rangle$, and that the permutations $\pi(g_j)$ in the odd case, $\pi(g_j^2)$ in the level calculation resp.\ $\pi(g_jg_l)$ in the even case are all even permutations. But the essence of the argument is that these permutations lie in $[\langle \pi(g_j),\pi(g_k)\rangle,\langle \pi(g_j),\pi(g_k)\rangle]$, even if that is might not be the whole group $A_N$. Using this argument might lead to an even larger class of subgroups where the argument above runs through. Furthermore, we are not limited to two generators to build the commutators from, we just must not use $g_i$ in it, possibly allowing for further generalization.

If a subgroup $U\le F_r$ is not in a shape accessible by these methods, one can try to obtain a suitable shape by using another basis of $F_r$. This is equivalent to turning to another subgroup $\gamma(U)$ in the orbit of $U$ under the action of $\Aut(F_r)$. All subgroups in the same orbit have the same stabilizer subgroup (up to conjugation).

It might therefore be fruitful to study to which larger class of subgroups of $F_r$ we can generalize our argument.
%under which conditions a subgroup obtained by enlarging a loop subgroup still allows for the same arguments as the loop subgroup it was derived from. 

\begin{table}[b!p]
\centering
\begin{tabular}{rrrrr}
\rule{0pt}{16ex}% Manueller Platzhalter
\turnbox{50}{rank} &
\hspace{6ex}\turnbox{50}{max. index} &
\hspace{6ex}\turnbox{50}{conjugacy classes} &
\hspace{6ex}\turnbox{50}{conjugacy classes with loop subgroups} &
\hspace{6ex}\turnbox{50}{conjugacy classes suitable for \cref*{altperm}} \\
\midrule
3 & 1 & 1 & 1 & 1 \\
  & 2 & 8 & 1 & 1 \\
  & 3 & 49 & 4 & 2 \\
  & 4 & 653 & 11 & 9 \\
  & 5 & 14406 & 23 & 33 \\
  & 6 & 518659 & 41 & 95 \\
\midrule
4 & 1 & 1 & 1 & 1 \\
  & 2 & 16 & 1 & 1 \\
  & 3 & 251 & 7 & 14 \\
  & 4 & 14371 & 23 & 197 \\
  & 5 & 1727216 & 54 & 1866 \\
\midrule
5 & 1 & 1 & 1 & 1 \\
  & 2 & 32 & 1 & 1 \\
  & 3 & 1393 & 11 & 91 \\
  & 4 & 335969 & 41 & 3651 \\
\midrule
6 & 1 & 1 & 1 & 1 \\
  & 2 & 64 & 1 & 1 \\
  & 3 & 8051 & 16 & 481 \\
\end{tabular}
\caption{Conjugacy classes containing loop subgroups}
\label{subgrouptable}
\end{table}


\appendix

\chapter*{Counting loop subgroups}

The following GAP script is used to calculate \vref{subgrouptable}:
\vspace{1pc}
\label{countingsubgroupsscript}

\lstdefinelanguage{GAP}{
	morekeywords={and,do,elif,else,end,fi,for,function,if,in,local,mod,not,od,or,repeat,return,then,until,while,quit,QUIT,break,rec,continue},
	sensitive=false,
	morecomment=[l]{\#},
	morestring=[b]"
	}


\lstinputlisting[
	language=GAP,
	basicstyle=\small,
	commentstyle=\rmfamily\textit,
	keywordstyle=\bfseries,
	showstringspaces=false,
	columns=fullflexible,
	frame=tb,
]{CountSubgroups-nodebug.gap}

\bibliography{bib}

\chapter*{Erklärung}

\lettrine H{iermit} erkläre ich, Joachim Breitner, dass ich die vorliegende Diplomarbeit selb\-ständig
und ausschließlich unter Verwendung der angegebenen Quellen und Hilfsmittel verfasst
habe.
\vspace{20mm}
\begin{tabbing}
\rule{4cm}{.4pt}\hspace{1cm} \= \rule{7cm}{.4pt} \\
Ort, Datum \> Unterschrift
\end{tabbing}

\end{document}
