\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) 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{$jj$, 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] (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 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$, $11$, 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] (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}