# Teorema de Nielsen–Schreier

O Teorema de Nielsen-Schreier é um importante resultado da Teoria dos Grupos que demonstra que todo subgrupo de um grupo livre é livre sobre algum conjunto.

## Conjuntos fechados por prefixos

Seja $F=F(X)$ um grupo livre sobre o conjunto $X$. Um subconjunto $A$ de $F(X)$ será dito fechado por prefixos quando para toda palavra $w=a_{1}a_{2}\ldots a_{r}\in A$, $a_{i}\in X\cup X^{-1}$, reduzida como escrita, temos $a_{1}\ldots a_{r-1}\in A$. Note que um subconjunto fechado por prefixos necessariamente contém a palavra vazia $1$. (É verdade que o grupo livre é construído como o conjunto de classes de equivalência de palavras, mas é natural identificar uma classe com o único elemento em forma reduzida que contém.)

## Transversais de Schreier

Se $H$ é um subgrupo do grupo livre $F(X)$, uma transversal à direita de $H$ em $F(X)$ será dita transversal de Schreier quando for um subconjunto fechado por prefixos. É um fato que, dado um subgrupo de um grupo livre, existe uma transversal de Schreier correspondente.

## O enunciado

Teorema. (Nielsen-Schreier)
Seja $F=F(X)$ um grupo livre sobre o conjunto $X$ e seja $H\leq F$. Fixe uma transversal à direita ${\mathcal {T}}$ para $H$ em $F$ e, dado um elemento $w\in F$, seja ${\overline {w}}$ o único elemento de ${\mathcal {T}}$ tal que ${\overline {w}}w^{-1}\in H$. Assuma-se que ${\overline {1}}=1$. Então
* O subgrupo $H$ é gerado pelo conjunto ${\big \(tx)({\overline {tx}})^{-1}\mid t\in {\mathcal {T}},x\in X{\big \}}$.
A cada elemento não-idêntico do conjunto dos $(tx)({\overline {tx}})^{-1}$, $t\in {\mathcal {T}},x\in X$, associe um símbolo $y_{t,x}$ e forme o conjunto $Y=\{y_{t,x}\}$.
* Se a transversal ${\mathcal {T}}$ for uma transversal de Schreier, o epimorfismo $\alpha :F(Y)\twoheadrightarrow H$ que estende $y_{t,x}\mapsto (tx)({\overline {tx}})^{-1}$ é um isomorfismo. Em outras palavras, o (sub)grupo $H$ é livre, livremente gerado por $Y^{\alpha }$. Vale também que $H$ tem posto $\operatorname {rank} F(Y)=\operatorname {card} Y=(\operatorname {card} X)[F:H]-[F:H]+1$.
A substância do Teorema está no segundo item. Com efeito, o que se afirma no primeiro item independe da liberdade do grupo em questão. Temos então a seguinte
Afirmação. Seja $G$ um grupo gerado pelo subconjunto $S$. Se $H\leq G$ e ${\mathcal {R}}$ é uma transversal à direita para $H$ em $G$ com ${\overline {1}}=1$, então $H=\langle {\overline {rs}}\left(rs\right)^{-1}\mid r\in {\mathcal {R}},s\in S\rangle$.
Para ver por que a afirmação segue, note-se primeiro que ${\overline {rs^{-1}}}{\bigrs^{-1}{\big )}^{-1}=r^{\prime }sr^{-1}=(r^{\prime }s){\overline {r^{\prime }s}}^{-1}{\overline {r^{\prime }s}}r^{-1}=(r^{\prime }s){\overline {r^{\prime }s}}^{-1}$, pois ${\overline {r^{\prime }s}}=r$ se $r^{\prime }={\overline {rs^{-1}}}$. Portanto se $s_{1}^{\epsilon _{1}}s_{2}^{\epsilon _{2}}\ldots s_{r}^{\epsilon _{r}}\in H$, podemos realizar o seguinte malabarismo simbólico: $s_{1}^{\epsilon _{1}}s_{2}^{\epsilon _{2}}s_{3}^{\epsilon _{3}}\ldots ={\bigs_{1}^{\epsilon _{1}}{\overline {s_{1}^{\epsilon _{1}}}}^{-1}{\big )}{\big{\overline {s_{1}^{\epsilon _{1}}}}s_{2}^{\epsilon _{2}}{\overline {{\overline {s_{1}^{\epsilon _{1}}}}s_{2}^{\epsilon _{2}}}}^{-1}{\big )}{\Big{\overline {{\overline {s_{1}^{\epsilon _{1}}}}s_{2}^{\epsilon _{2}}}}s_{3}^{\epsilon _{3}}{\overline {{\overline {{\overline {s_{1}^{\epsilon _{1}}}}s_{2}^{\epsilon _{2}}}}s_{3}^{\epsilon _{3}}}}^{-1}{\Big )}{\overline {{\overline {{\overline {s_{1}^{\epsilon _{1}}}}s_{2}^{\epsilon _{2}}}}s_{3}^{\epsilon _{3}}}}\ldots$
Continuando, obtemos $s_{1}^{\epsilon _{1}}s_{2}^{\epsilon _{2}}\ldots s_{r}^{\epsilon _{r}}=av$, onde $a$ está no subgrupo gerado proposto e $v\in {\mathcal {R}}$. Como o subgrupo gerado claramente é subgrupo de $H$, temos $v\in H$, donde $v=1$, finalizando o argumento. Como corolário, obtemos que são finitamente gerados subgrupos de índice finito de grupos finitamente gerados; além disso, o número mínimo de geradores de tal subgrupo é majorado pelo produto de seu índice pelo número mínimo de geradores do grupo que o contém.
Note que, em geral, para uma transversal $T$ com ${\overline {1}}=h\in H$, temos a transversal $h^{-1}T$ na qual ${\overline {\overline {1}}}=1$; claramente ${\overline {\overline {g}}}=h^{-1}{\overline {g}}$ (barras duplas evidentemente se referem à nova transversal). Logo o conjunto gerador obtido nas considerações anteriores torna-se ${\big \h^{-1}(tx)({\overline {tx}})^{^{\scriptstyle -1}}\!h\mid t\in T,x\in X{\big \}}$.

## O Teorema de Schreier-Reidemeister

O Teorema de Nielsen-Schreier permite exibir uma apresentação de um subgrupo a partir de uma para o grupo que o contém. Para isso, temos o seguinte
Teorema. (Schreier-Reidemeister)
Seja $G$ o grupo apresentado $\langle X\mid R\rangle$, isto é, $G=F(X)/\langle R\rangle ^{F(X)}$, o subgrupo pelo qual estamos fatorando sendo o fecho normal do subgrupo gerado pelo conjunto $R\subset F(X)$ de relatores. Seja $H$ um subgrupo de $G$ e seja $K$ a pré-imagem de $H$ em $F(X)$. Se $\theta :K\to F(W)$ é um isomorfismo de $K$ com o grupo livre sobre o conjunto $W$ e se $T$ é uma transversal qualquer de $K$ em $F(X)$, então temos a apresentação $H\cong \langle W\mid S\rangle$, onde o conjunto $S$ de relatores é $S={\big \(trt^{-1})^{\theta }\mid t\in T,r\in R{\big \}}$.
A demonstração é imediata pois temos a igualdade entre fechos normais $\langle R\rangle ^{F}=\langle tRt^{-1}\mid t\in T\rangle ^{K}$.
É também imediato o seguinte
Corolário. São finitamente apresentáveis subgrupos de grupos finitamente apresentáveis que possuem índice finito.
Haja vista que o índice da pré-imagem será finito, implicando que o será também o posto da pré-imagem como grupo livre; além disso, $\operatorname {card} S\leq [G:H](\operatorname {card} R)$.

## Um critério para infinitude

O objetivo nesta seção é provar o seguinte
Teorema. Seja $G\cong \langle x_{1},x_{2},\ldots ,x_{r}\mid w_{1}^{m_{1}},w_{2}^{m_{2}},\ldots ,w_{s}^{m_{s}}\rangle$. Suponha que $\mathop {\textstyle {\sum }} _{i=1}^{s}\textstyle {\frac {1}{m_{i}}}\leq r-1$. Se houver um grupo $P$ e um epimorfismo $\theta :G\twoheadrightarrow P$ tal que a ordem do elemento $w_{i}^{\theta }\in P$ é precisamente $m_{i}$, então o grupo $G$ é infinito.
Começaremos com um
Lema. Se $G$ tem apresentação $G\cong \langle X\mid R\rangle$, com $X,R$ conjuntos finitos e $\operatorname {card} X>\operatorname {card} R$, então a abelianização $G_{\textrm {ab}}=G/[G,G]$ possui infinitos elementos. Em particular, $G$ é um grupo infinito.
Prova. Seja $X=\{x_{1},\ldots ,x_{n}\}$, $\operatorname {card} X=n$. Passando para a abelianização e adotando a notação aditiva, podemos ver os relatores em $R$ como polinômios homogêneos de grau $1$ em $\mathbb {Q} [x_{1},\ldots ,x_{n}]$ — de fato, em $\mathbb {Z} [x_{1},\ldots ,x_{n}]$. Por exemplo, o relator $x_{1}^{3}x_{2}^{-1}x_{3}^{7}x_{1}^{-2}x_{4}$ deve corresponder ao polinômio $3x_{1}-x_{2}+7x_{3}-2x_{1}+x_{4}=x_{1}-x_{2}+7x_{3}+x_{4}$. É fato elementar da Álgebra Linear que existe um elemento em $(\mathbb {Q} \times \mathbb {Q} \times \dots \times \mathbb {Q} )\smallsetminus \{0\}$ que anula todo elemento de $R$ (heurística: há mais incógnitas do que equações); existe, pois, um elemento em $\mathbb {Z} ^{n}\smallsetminus \{0\}$ que anula todo elemento de $R$ (multiplique a solução anterior por um inteiro adequado). Escolha uma solução $w=(w_{1},\ldots ,w_{n})\in \mathbb {Z} ^{n}\smallsetminus \{0\}$, digamos, com $w_{1}\neq 0$. O Teorema de von Dyck garante então que a associação $x_{i}\mapsto w_{i}$ estende-se a um homomorfismo $\psi :G_{\textrm {ab}}\to \mathbb {Z}$. Possuindo $G_{\textrm {ab}}$ uma imagem homomorfa infinita, uma vez que $\mathbb {Z} \cong \langle w_{1}\rangle \leq \operatorname {Im} \psi$, segue o Lema.
Prova do Teorema. Se $P$ for infinito, não há nada a fazer. Suponha então $P$ finito de ordem $n$, de forma que $H=\operatorname {Ker} \theta$ tem índice finito $n$ em $G$. Seja $K\vartriangleleft F(X)$ a pré-imagem de $H$ no grupo livre sobre $X$, $F/K\cong G/H\cong P$. Por Nielsen-Schreier, podemos escolher um isomorfismo $\beta :K\to F(Y)$, $\operatorname {card} Y=n(r-1)+1$. Por Schreier-Reidemeister, temos $H\cong {\big \langle }Y\,{\big \vert }\,\left(aw_{i}^{m_{i}}a^{-1}\right)^{\beta },i=1,2,\ldots ,s,a\in A{\big \rangle }$, o conjunto $A$ sendo uma transversal à direita fixa para $K$ em $F(X)$. Para cada $i=1,2,\ldots ,s$ temos $n$ relatores. A ideia principal da demonstração é encontrar relatores redundantes, de modo que o Lema venha à mão. Fá-lo-emos do seguinte modo: escolha um elemento da transversal, digamos $a_{0}\in A$. Note que as classes $Ka_{0},Ka_{0}w_{1},Ka_{0}w_{1}^{2},\ldots ,Ka_{0}w_{1}^{m_{1}-1}$ são duas a duas distintas: caso não fossem, teríamos $Ka_{0}w_{1}^{\ell }=Ka_{0}$ para algum $0<\ell <m_{1}$. Por normalidade de $K$, ter-se-ia $w_{1}^{\ell }\in K$, donde, em $G$, $w_{1}^{\ell }\in H$, isto é, ${\bigw_{1}^{\theta }{\big )}^{\ell }=1$ — absurdo pois a ordem de $w_{1}^{\theta }$ é $m_{1}$. Temos então $m_{1}$ elementos de $A$, $a_{0},{\overline {a_{0}w_{1}}},{\overline {a_{0}w_{1}^{2}}},\ldots ,{\overline {a_{0}w_{1}^{m_{1}-1}}}$. Agora ${\overline {a_{0}w_{1}^{\nu }}}w_{1}^{m_{1}}{\overline {a_{0}w_{1}^{\nu }}}^{-1}={\overline {a_{0}w_{1}^{\nu }}}{\biga_{0}w_{1}^{\nu }{\big )}^{-1}{\biga_{0}w_{1}^{\nu }{\big )}w_{1}^{m_{1}}{\biga_{0}w_{1}^{\nu }{\big )}^{-1}{\biga_{0}w_{1}^{\nu }{\big )}{\overline {a_{0}w_{1}^{\nu }}}^{-1}=u_{\nu }(a_{0}w_{1}^{m_{1}}a_{0}^{-1})u_{\nu }^{-1}$ para algum $u\in K$. Daí, os $m_{1}$ relatores oriundos de tais elementos da transversal são mutuamente conjugados, logo, destes, precisamos de apenas um. Escolhendo um elemento da transversal diferente daqueles já obtidos, podemos repetir o argumento até a exaustão dos $n$ relatores. Vê-se facilmente agora que são necessários apenas $n/m_{1}$ dos relatores iniciais. Isso claramente se repete para $i=2,\ldots ,s$. Portanto, $H$ tem uma apresentação com $n(r-1)+1$ geradores e $(n/m_{1})+(n/m_{2})+\ldots +(n/m_{s})=n\mathop {\textstyle {\sum }} _{i=1}^{s}\textstyle {\frac {1}{m_{i}}}$ relatores. Por hipótese, o número de geradores excede o número de relatores; apelando ao Lema, temos $H$ infinito, finalizando a demonstração.
Exemplo. O grupo $\langle x,y\mid x^{4},y^{8},(xy)^{6}\rangle$ é infinito. Temos ${\tfrac {1}{4}}+{\tfrac {1}{8}}+{\tfrac {1}{6}}\leq 1$. Considere as permutações $\pi _{1}=(1,2,3,4),\pi _{2}=(1,2,3,4,5,6,7,8),\pi _{1}\pi _{2}=(1,3,5,6,7,8)(2,4)$ e escolha $P=\langle \pi _{1},\pi _{2}\rangle$. Em geral, o grupo $D(l,m,n)=\langle x,y\mid x^{l},y^{m},(xy)^{n}\rangle$, intimamente relacionado com certas tesselações triangulares de planos (no sentido amplo de geometrias Euclidianas ou não), é infinito se, e somente se, ${\tfrac {1}{l}}+{\tfrac {1}{m}}+{\tfrac {1}{n}}\leq 1$. É possível mostrar que, dada uma tripla $(l,m,n)$ de inteiros maiores que $1$, existem elementos $\gamma ,\delta$ do grupo $\operatorname {PSL} (2,\mathbb {C} )$ das transformações fracionais lineares do plano complexo estendido ${\tilde {\mathbb {C} }}=\mathbb {C} \sqcup \{\infty \}$, tais que $\operatorname {ord} (\gamma )=l$, $\operatorname {ord} (\delta )=m$, $\operatorname {ord} (\gamma \delta )=n$. Por outro lado, as únicas triplas daquela forma satisfazendo ${\tfrac {1}{l}}+{\tfrac {1}{m}}+{\tfrac {1}{n}}>1$ são $(2,2,n)$, $(2,3,3)$, $(2,3,4)$, $(2,3,5)$. No primeiro caso, vê-se facilmente que se trata de um grupo diedral $D_{2n}$. Nos casos restantes, temos, respectivamente, $\operatorname {Alt} (4)$, $\operatorname {Sym} (4)$, $\operatorname {Alt} (5)$. Considere as permutações $\sigma =(1,2,3)$, $\tau =(2,4)(3,5)$, $\sigma \tau =(1,4,2,5,3)$. Note que $\sigma ^{\tau \sigma \tau }=(4,2,3)$, $\alpha :=\tau \sigma ^{\tau \sigma \tau }=(3,5,4)$ e $\langle \tau ,\alpha \rangle \leq {\big\!\operatorname {Alt} (5){\big )}_{1}=\operatorname {Stab} (1)\cong \operatorname {Alt} (4)$. Em $\langle \tau ,\alpha \rangle$, temos $\langle \tau ,\tau ^{\alpha }\rangle =\langle (2,4)(3,5),(2,3)(5,4)\rangle \cong C_{2}\times C_{2}$; além disso as classes $\langle \tau ,\tau ^{\alpha }\rangle ,\langle \tau ,\tau ^{\alpha }\rangle \alpha ,\langle \tau ,\tau ^{\alpha }\rangle \alpha ^{2}$ são duas a duas distintas e esgotam o espaço de classes $\operatorname {mod} \,\,\langle \tau ,\tau ^{\alpha }\rangle$, logo $\vert \langle \tau ,\alpha \rangle \vert =12$. Como $5$ e $12$ dividem a ordem de $\langle \sigma ,\tau \rangle \leq \operatorname {Alt} (5)$, temos a igualdade. Usando ideias similares, mas em $D(2,3,3)$, prova-se que $D(2,3,3)$ é finito de ordem no máximo $12$; portanto, $x\to \tau ,y\to \alpha$ é um isomorfismo $D(2,3,3)\cong \operatorname {Alt} (4)$. Em $D(2,3,5)$ há um subgrupo que é uma imagem homomorfa de $D(2,3,3)$, portanto é finito de ordem no máximo $12$. Usando as potências de $xy$ como representantes de classes módulo tal subgrupo, mostra-se que $D(2,3,5)$ é finito de ordem no máximo $12\cdot 5=60$, permitindo-nos concluir que $x\to \tau ,y\to \sigma$ é um isomorfismo $D(2,3,5)\cong \operatorname {Alt} (5)$. Ideias inteiramente análogas mostram que $x\to (1,4)$, $y\to (1,2,3)$ é um isomorfismo $D(2,3,4)\cong \operatorname {Sym} (4)$.

## Um último exemplo

Seja $G=\langle x,y\mid x^{3},y^{3},(xy)^{3}\rangle$ e $H=\langle x^{-1}y,yx^{-1}\rangle \leq G$. Afirmo que $H$ é um grupo Abeliano livre de posto $2$, isto é, $H\cong \mathbb {Z} \oplus \mathbb {Z}$. Primeiro, temos $[G:H]=3$. De fato, $H\!\vartriangleleft G$, já que $xyx=(yx^{-1})^{-1}(x^{-1}y)^{-1}\in H$ e $yxy=(yx^{-1})(x^{-1}y)\in H$; logo, o quociente $G/H$ tem apresentação $\langle x,y\mid x^{3},y^{3},(xy)^{3},x^{-1}y,yx^{-1}\rangle \cong \langle x\mid x^{3}\rangle \cong \mathbb {Z} /3\mathbb {Z}$.
Seja $K$ a imagem inversa de $H$ em $F=F_{\{x,y\}}$ (usar-se-á o mesmo símbolo para denotar um elemento de $F$ e sua imagem em $G$; esperadamente, não haverá confusão). Temos a transversal de Schreier ${\mathcal {S}}=\{1,x,x^{2}\}\subset F$ para $K$. Pelo Teorema de Nielsen-Schreier, $K\cong F_{\{a,b,c,d\}}$ é livre de posto $4=2\cdot 3-3+1$, com a associação $a\mapsto x^{3},b\mapsto yx^{-1},c\mapsto xyx^{-2},d\mapsto x^{2}y$ (estendendo-se a) um isomorfismo cuja inversa será denotada por $\delta :K\to F_{\{a,b,c,d\}}$. Calculando, temos $(x^{3})^{\delta }=a$, $(y^{3})^{\delta }={\big(yx^{-1})(xyx^{-2})(x^{2}y){\big )}^{\delta }=bcd$,${\big(xy)^{3}{\big )}^{\delta }={\big(xyx^{-2})(x^{3})(yx^{-1})(x^{2}y){\big )}^{\delta }=cabd$,$(xy^{3}x^{-1})^{\delta }={\big(yx^{-1})^{x^{-1}}(xyx^{-2})^{x^{-1}}(x^{2}y)^{x^{-1}}{\big )}^{\delta }=(c)(da^{-1})(ab)=cdb$, ${\bigx(xy)^{3}x^{-1}{\big )}^{\delta }={\big(x^{2}y)(xyx^{-2})(x^{3})(yx^{-1}){\big )}^{\delta }=dcab$, ${\bigx^{2}y^{3}x^{-2}{\big )}^{\delta }={\big(x^{2}y)(yx^{-1})(xyx^{-2}){\big )}^{\delta }=dbc$, ${\bigx^{2}(xy)^{3}x^{-2}{\big )}^{\delta }={\bigx^{3}(yx^{-1})(x^{2}y)(xyx^{-2}){\big )}^{\delta }=abdc$. Note que os elementos de $F_{\{a,b,c,d\}}$ obtidos de comprimento $4$ são permutações cíclicas uns dos outros, portanto são conjugados, logo constituem um conjunto de relatores redundantes, dos quais precisamos de apenas um; o mesmo vale para aqueles de comprimento $3$. O gerador $a$ some. Temos daí que $H\cong \langle b,c,d\mid bcd,bdc\rangle$. Finalmente, $b\in \langle c,d\rangle$ e $[c,d]=1$; agora é fácil estabelecer, por exemplo, via Teorema de Von Dyck, um isomorfismo $H\cong \langle c,d\mid \![c,d]\rangle \cong \mathbb {Z} \oplus \mathbb {Z}$. Isso prova a afirmação inicial. Note que como subproduto desses argumentos, obtemos $G$ como um produto semidireto $(\mathbb {Z} ^{2})\rtimes (\mathbb {Z} /3\mathbb {Z} )$.