Satz von Nielsen-Schreier

Graph mit Spannbaum (schwarz) und verbleibenden Kanten (rot). Letztere erzeugen frei die Fundamentalgruppe des Graphen. Als Beispiel gelb eingezeichnet ist der zur Kante ${\displaystyle s_{1}}$ gehörige Erzeuger.

Sei ${\displaystyle \Gamma }$ ein zusammenhängender Graph. Diesen realisieren wir als topologischen Raum, wobei jede Kante einem Weg zwischen den angrenzenden Ecken entspricht. Die entscheidende Feststellung ist nun, dass die Fundamentalgruppe ${\displaystyle \pi _{1}(\Gamma ,*)}$ eine freie Gruppe ist.

Um dieses Ergebnis explizit zu machen und damit auch zu beweisen, wählt man einen maximalen Baum ${\displaystyle T\subset \Gamma }$, also einen Baum, der alle Ecken von ${\displaystyle \Gamma }$ enthält. Die verbleibenden Kanten ${\displaystyle S=\Gamma \setminus T}$ liefern eine Basis von ${\displaystyle \pi _{1}(\Gamma ,*)}$, indem man für jede Kante ${\displaystyle s\in S}$ einen Weg ${\displaystyle w_{s}}$ wählt, der vom Fußpunkt ${\displaystyle *}$ im Baum ${\displaystyle T}$ bis zur Kante ${\displaystyle s}$ läuft, diese überquert und anschließend in ${\displaystyle T}$ wieder zum Fußpunkt zurückkehrt. (Man wählt als Fußpunkt zweckmäßigerweise eine Ecke von ${\displaystyle \Gamma }$; diese liegt dann automatisch in jedem maximalen Baum ${\displaystyle T}$.) Die Tatsache, dass die Homotopieklassen ${\displaystyle [w_{s}]}$ mit ${\displaystyle s\in S}$ eine Basis von ${\displaystyle \pi _{1}(\Gamma ,*)}$ bilden, kann man mittels kombinatorischer Homotopie beweisen, oder durch explizite Konstruktion der universellen Überlagerung des Graphen ${\displaystyle \Gamma }$.

Dieses Ergebnis können wir quantitativ fassen, wenn ${\displaystyle \Gamma }$ ein endlicher Graph mit ${\displaystyle e}$ Ecken und ${\displaystyle k}$ Kanten ist. Er hat dann die Euler-Charakteristik ${\displaystyle \chi (\Gamma )=e-k}$. Jeder maximale Baum ${\displaystyle T\subset \Gamma }$ enthält dann genau ${\displaystyle e}$ Ecken und ${\displaystyle e-1}$ Kanten, und hat insbesondere die Euler-Charakteristik ${\displaystyle \chi (T)=1}$. Es verbleiben die Kanten ${\displaystyle \Gamma \setminus T=\{x_{1},\dots ,x_{r}\}}$ und deren Anzahl ist ${\displaystyle r=k-e+1=1-\chi (\Gamma )}$. Die Fundamentalgruppe ${\displaystyle \pi _{1}(\Gamma ,*)}$ ist demnach eine freie Gruppe vom Rang ${\displaystyle r=1-\chi (\Gamma )}$.

Qualitative Fassung: Jede freie Gruppe ${\displaystyle F}$ lässt sich darstellen als Fundamentalgruppe ${\displaystyle \pi _{1}(\Gamma ,*)}$ eines Graphen ${\displaystyle \Gamma }$. Zu jeder Untergruppe ${\displaystyle U\subset F}$ gehört eine Überlagerung ${\displaystyle {\tilde {\Gamma }}\to \Gamma }$. Der Überlagerungsraum ${\displaystyle {\tilde {\Gamma }}}$ ist dann wieder ein Graph, also ist die Gruppe ${\displaystyle U=\pi _{1}({\tilde {\Gamma }},*)}$ frei.

Quantitative Fassung: Jede freie Gruppe ${\displaystyle F}$ von endlichem Rang ${\displaystyle r}$ lässt sich darstellen als Fundamentalgruppe ${\displaystyle \pi _{1}(\Gamma ,*)}$ eines endlichen Graphen ${\displaystyle \Gamma }$ mit Euler-Charakteristik ${\displaystyle \chi (\Gamma )=1-r}$. Zu jeder Untergruppe ${\displaystyle U\subset F}$ von Index ${\displaystyle n}$ gehört dann eine ${\displaystyle n}$-blättrige Überlagerung ${\displaystyle {\tilde {\Gamma }}\to \Gamma }$. Der überlagernde Graph ${\displaystyle {\tilde {\Gamma }}}$ hat also die Euler-Charakteristik ${\displaystyle \chi ({\tilde {\Gamma }})=n\chi (\Gamma )=n(1-r)}$, und die Gruppe ${\displaystyle U=\pi _{1}({\tilde {\Gamma }},*)}$ ist demnach frei vom Rang ${\displaystyle 1-\chi ({\tilde {\Gamma }})=1-n(1-r)=1+n(r-1)}$.

Eine Gruppenoperation auf einem ungerichteten Graphen, also ein Homomorphismus in die Automorphismengruppe eines Graphen, heißt frei, wenn jedes vom neutralen Element verschiedene Gruppenelement frei operiert. Letzteres bedeutet, dass kein Knoten und keine Kante bei der Operation erhalten bleiben. Im geometrischen Beweis zeigt man, dass eine Gruppe genau dann frei ist, wenn sie eine freie Gruppenoperation auf einem Baum besitzt. Der Satz von Nielsen-Schreier ist nun ein einfaches Korollar, denn diese Charakterisierung freier Gruppen überträgt sich offenbar auf Untergruppen.[2]

Für den Rang ${\displaystyle r=0}$ ist ${\displaystyle F}$ die triviale Gruppe, die nur aus dem neutralen Element besteht, und die Aussage des Satzes ist leer.

Die erste interessante Aussage finden wir im Rang ${\displaystyle r=1}$. Hier ist ${\displaystyle F\cong \mathbb {Z} }$ die freie abelsche Gruppe, und wir finden die Klassifikation der Untergruppen von ${\displaystyle \mathbb {Z} }$ wieder: Die triviale Untergruppe ${\displaystyle \{0\}}$ ist frei vom Rang ${\displaystyle 0}$, jede andere Untergruppe ${\displaystyle I\subset \mathbb {Z} }$ ist von der Form ${\displaystyle I=\langle n\rangle }$ vom Index ${\displaystyle n}$ und selbst wieder frei abelsch vom Rang ${\displaystyle 1}$. Diese einfache Aussage kann auch ohne den Satz von Nielsen-Schreier bewiesen werden, zeigt aber, was im Spezialfall ${\displaystyle F\cong \mathbb {Z} }$ in ihm steckt.

Für eine freie Gruppe ${\displaystyle F}$ vom Rang ${\displaystyle r\geq 2}$ folgt aus dem (quantitativen) Satz von Nielsen-Schreier, dass ${\displaystyle F}$ freie Untergruppen von beliebigem endlichen Rang enthält. Es genügt, dies für die von 2 Elementen erzeugte Gruppe ${\displaystyle F_{2}}$ zu zeigen, da diese in allen von ${\displaystyle r\geq 2}$ Elementen erzeugten freien Gruppen enthalten ist. Bildet man die beiden Erzeuger von ${\displaystyle F_{2}}$ auf den Erzeuger der zyklischen Gruppe ${\displaystyle Z_{n}}$ ab, so erhält man aus der definierenden Eigenschaft der freien Gruppe einen surjektiven Gruppenhomomorphismus ${\displaystyle \varphi :F_{2}\rightarrow \mathbb {Z} _{n}}$. Nach dem Homomorphiesatz ist ${\displaystyle F_{2}/\mathrm {ker} (\varphi )\cong \mathbb {Z} _{n}}$, das heißt die Untergruppe ${\displaystyle \mathrm {ker} (\varphi )\subset F_{2}}$ hat den Index ${\displaystyle n}$. Sie ist nach der quantitativen Aussage des Satzes von Nielsen-Schreier daher isomorph zur von ${\displaystyle 1+n}$ Elementen erzeugten freien Gruppe.

Man kann in ${\displaystyle F_{2}}$ sogar eine Untergruppe von abzählbar unendlichem Rang konstruieren.

Diese erstaunliche Eigenschaft steht im Gegensatz zu freien abelschen Gruppen (wo der Rang einer Untergruppe stets kleiner oder gleich dem Rang der gesamten Gruppe ist) oder Vektorräumen über einem Körper (wo die Dimension eines Unterraums stets kleiner oder gleich der Dimension des gesamten Raums ist).

Der Satz von Nielsen-Schreier handelt zwar zunächst nur von freien Gruppen, seine quantitative Fassung hat aber auch interessante Konsequenzen für beliebige, endliche erzeugte Gruppen. Ist eine Gruppe ${\displaystyle G}$ endlich erzeugt, von einer Familie mit ${\displaystyle r}$ Elementen aus ${\displaystyle G}$, und ist ${\displaystyle H\subset G}$ eine Untergruppe von endlichem Index ${\displaystyle n}$, dann hat auch ${\displaystyle H}$ ein endliches Erzeugendensystem mit höchstens ${\displaystyle 1+n(r-1)}$ Elementen.

Wie schon im Fall freier Gruppen muss man im Allgemeinen also damit rechnen, dass eine Untergruppe ${\displaystyle H\subset G}$ mehr Erzeuger benötigt als die gesamte Gruppe ${\displaystyle G}$.