TEORIA GEOM´ETRICA DE GRUPOS Pedro V. Silva

Transcrição

TEORIA GEOMÉTRICA DE GRUPOS
Curso de pré-doutorado, Universidade Federal da Bahia 2014
Pedro V. Silva
Neste curso, faremos uma digressão por alguns dos grandes desenvolvimentos
que a teoria de grupos sofreu nos últimos 30 anos, dos autômatos de Stallings
aos grupos hiperbólicos de Gromov e aos grupos automáticos de Epstein,
Thurston et al.... Veremos uma nova e inesperada álgebra que se relaciona
de forma surpreendente com muitas outras áreas: combinatória, geometria,
sistemas dinâmicos, teoria de autômatos e linguagens, topologia.
Índice
1 Grupos
1.1 Grupos de permutações . . .
1.2 Noção abstrata de grupo . . .
1.3 Homomorfismos e quocientes
1.4 Outros conceitos . . . . . . .
1.5 Exercı́cios . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
4
4
4
5
7
8
2 Grafos e autômatos
2.1 Palavras e linguagens .
2.2 Grafos . . . . . . . . .
2.3 Autômatos . . . . . .
2.4 Sistemas de reescrita .
2.5 Exercı́cios . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
10
10
11
12
16
17
. . . . . .
. . . . . .
racionais
. . . . . .
. . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
19
19
22
24
27
29
.
.
.
.
.
.
.
.
.
.
3 Grupos livres
3.1 Construção . . . . . . . .
3.2 Propriedades básicas . . .
3.3 Autômatos e subconjuntos
3.4 Grafos de Cayley . . . . .
3.5 Exercı́cios . . . . . . . . .
.
.
.
.
.
4 Representação de subgrupos
4.1 Construção de Stallings . .
4.2 Aplicações . . . . . . . . . .
4.3 A métrica profinita . . . . .
4.4 Exercı́cios . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
5 Bordo de um grupo livre
5.1 Palavras infinitas . . . . . . . . .
5.2 A métrica dos prefixos e o espaço
5.3 Construção do bordo . . . . . . .
5.4 Exercı́cios . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
31
31
34
39
42
. . . . . .
de Cantor
. . . . . .
. . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
43
43
44
46
47
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
6 Pontos fixos de endomorfismos
49
6.1 O subgrupo dos pontos fixos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
6.2 Pontos fixos no bordo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
6.3 Exercı́cios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
7 Apresentações de grupos
56
7.1 Geradores e relatores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
7.2 Grupos finitamente apresentáveis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
2
7.3
7.4
7.5
7.6
Decidibilidade . . . . . . . .
Diagramas de van Kampen
Funções isoperimétricas . .
Exercı́cios . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
58
59
63
65
8 Produto livre e generalizações
8.1 Produto livre . . . . . . . . .
8.2 Generalizações . . . . . . . .
8.3 Grupos de grafo . . . . . . . .
8.4 Exercı́cios . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
67
67
69
70
72
9 Grupos hiperbólicos
9.1 Grafos hiperbólicos . . . . . .
9.2 Grafos de Cayley hiperbólicos
9.3 Propriedades . . . . . . . . .
9.4 Exercı́cios . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
74
74
76
79
82
10 Grupos automáticos
10.1 Estruturas automáticas .
10.2 Caraterização geométrica
10.3 Propriedades . . . . . . .
10.4 Exercı́cios . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
85
85
88
91
95
.
.
.
.
.
.
.
.
Bibliografia
96
Índice de conceitos
97
3
1
Grupos
Começamos este curso lembrando fatos básicos sobre grupos que já foram estudados na graduação.
1.1
Grupos de permutações
Uma grande parte da Matemática é dedicada ao estudo de funções. E dentro do estudo das funções,
merece destaque o estudo das permutações. Uma permutação de um conjunto X é simplesmente
uma função bijetiva σ : X → X.
À primeira vista, o conceito parece um pouco restritivo... a maior parte das funções não são
bijetivas... mas muitas funções importantes, na Matemática e fora dela, são bijetivas:
• Álgebra linear: isomorfismos de um espaço vetorial.
• Topologia: homeomorfismos de espaços métricos/topológicos.
• Sistemas dinâmicos: em geral, as transformações consideradas são homeomorfismos.
• Fı́sica quântica: as transformações na mecânica quântica assumem-se reversı́veis (e bijetivas).
Uma das coisas mais importantes e úteis que se podem fazer com funções é compô-las. É claro
que a composição de duas permutações de um conjunto X é ainda uma permutação de X. E a
função inversa de uma permutação de X é ainda uma permutação de X. Estas duas operações
(composição e inversão) são fundamentais na construção do conceito de grupo de permutações:
Seja SX o conjunto de todas as permutações do conjunto X e seja 1X a permutação identidade.
Dizemos que G ⊆ SX é um grupo de permutações se:
• G é fechado para composição;
• 1X ∈ G;
• a permutação inversa de uma permutação em G está também em G.
Eis alguns exemplos de grupos de permutações:
• SX (diz-se o grupo simétrico sobre X);
• o conjunto dos automorfismos de um espaço vetorial;
• o conjunto dos auto-homeomorfismos de um espaço métrico/topológico;
1.2
Noção abstrata de grupo
Historicamente, o estudo dos grupos começou por ser o estudo dos grupos de permutações, e em
muitos casos grupos bem concretos que interessavam à Fı́sica e a várias áreas da Matemática. Na
segunda metade do século XIX, apareceu uma outra perspetiva do conceito de grupo, bem mais
abstrata, que dispensava permutações e composição. Na versão abstrata, um grupo é um conjunto
não vazio G, no qual está definida uma operação binária · : G × G → G satisfazendo as seguintes
propriedades:
4
(G1) Associatividade: a · (b · c) = (a · b) · c para todos a, b, c ∈ G.
(G2) Existência de elemento neutro: existe um elemento 1G ∈ G tal que 1G · a = a · 1G = a para
todo a ∈ G.
(G3) Existência de inversos: para todo a ∈ G, existe um elemento b ∈ G tal que a · b = b · a = 1G .
É fácil mostrar que o elemento neutro é único e que cada elemento tem um único inverso. Em
geral, designamos o neutro por 1 e o inverso de a por a−1 . Se só exigirmos (G1) e (G2), a estrutura
é chamada de monóide.
Exemplo 1.1 Seja n ∈ N e seja GLn (R) o conjunto de todas as matrizes n × n invertı́veis com
entradas reais. Então GLn (R), com o produto de matrizes, constitui um grupo.
É claro que todo grupo de permutações satisfaz os axiomas (G1) – (G3), pois a composição de
funções é associativa, a identidade funciona como elemento neutro e cada permutação inversa é um
inverso no sentido de (G3). Veremos mais adiante que os dois conceitos de grupo (o abstrato e o de
grupo de permutações) são essencialmente equivalentes. Mas primeiro necessitamos de relembrar
alguns conceitos básicos.
Seja G um grupo (quando falamos de um grupo abstrato genérico, dispensamo-nos de referir a
operação binária · e escrevemos ab em vez de a · b).
Dizemos que H ⊆ G é um subgrupo de G e escrevemos H ≤ G se:
• 1G ∈ H;
• se a, b ∈ H, então ab ∈ H;
• se a ∈ H, então a−1 ∈ H.
Isto equivale a dizer que H é ele próprio um grupo quando consideramos a restrição a H × H
da operação binária em G.
Exemplo 1.2 Seja n ∈ N e seja SLn (R) o conjunto de todas as matrizes n × n com entradas reais
e determinante 1. Então SLn (R) constitui um subgrupo do grupo GLn (R) do Exemplo 1.1.
1.3
Homomorfismos e quocientes
Outro conceito fundamental é o conceito de homomorfismo. Sejam G, H grupos. Uma função
ϕ : G → H é um homomorfismo (de grupos) se (ab)ϕ = (aϕ)(bϕ) para todos a, b ∈ G.
Se ϕ : G → H é um homomorfismo, então é fácil verificar as seguintes propriedades:
• 1G ϕ = 1H ;
• a−1 ϕ = (aϕ)−1 para todo a ∈ G.
5
Um isomorfismo bijetivo é um isomorfismo. Dois grupos G e H dizem-se isomorfos (e escrevemos
G∼
= H) se existir um isomorfismo ϕ : G → H. Note-se que nesse caso a função inversa ϕ−1 : H → G
é também um isomorfismo. Um isomorfismo de um grupo nele próprio é um automorfismo.
Analogamente se define homomorfismo de monóides, mas exige-se também a igualdade 1ϕ = 1,
pois no caso dos monóides esta não resulta automaticamente da igualdade (ab)ϕ = (aϕ)(bϕ).
Podemos agora estabelecer a mencionada equivalência entre os conceitos de grupo (abstrato) e
grupo de permutações (Teorema de Cayley):
Teorema 1.3 (Cayley 1854, Jordan 1870) Todo grupo é isomorfo a algum grupo de permutações.
Prova. Seja G um grupo e seja SG o grupo simétrico sobre o conjunto G. Dado g ∈ G, seja
σg ∈ SG a permutação definida por aσg = ag. Seja H = {σg | g ∈ G}. Temos
• σ1 = 1G ,
• σgh = σg σh ,
• σg−1 = σg−1
para todos g, h ∈ G, logo H é um subgrupo de SG . Finalmente, σ : G → H é um isomorfismo (a
injetividade resulta de g 6= h ⇒ 1σg 6= 1σh ). Vamos agora introduzir o conceito de grupo quociente. A ideia é fazer uma partição dos elementos de um grupo G em classes de equivalência [g] (g ∈ G) de forma a que o conjunto das classes
possa constituir um grupo sob a operação induzida
(g, h ∈ G).
[g][h] = [gh]
Para que esta operação esteja bem definida e dê efetivamente origem a um grupo, é preciso que a
classe N = [1] seja um subgrupo do seguinte tipo:
Se G é um grupo e N ≤ G, dizemos que N é um subgrupo normal e escrevemos N E G se
aN a−1 = N para cada a ∈ G.
Além do mais, verifica-se que para cumprir o nosso programa precisamos que a partição seja
constituı́da por classes da forma [a] = aN = N a. Isto conduz-nos ao conceito de grupo quociente:
Seja G um grupo e N EG. Seja G/N = {N a | a ∈ G} com a operação binária (N a)(N b) = N ab.
Então G/N constitui um grupo, que se diz o grupo quociente de G por N .
Exemplo 1.4 SLn (R) E GLn (R) para todo n ∈ N.
De fato, se P ∈ GLn (R), então det(P −1 ) = (det(P ))−1 , logo det(M ) = 1 implica det(P M P −1 ) =
(det(P ))(det(M ))(det(P −1 )) = 1, e o subgrupo é normal. O grupo quociente consiste então em todas os conjuntos de matrizes do tipo (SLn (R))M (M ∈ GLn (R)). Podemos encontrar uma descrição
mais simples?
A resposta é dada com a ajuda dos teoremas do homomorfismo, que relacionam homomorfismos
e quocientes. É claro que se N E G, então a projeção canónica
πN : G → G/N
a 7→ N a
6
é um homomorfismo. Por outro lado, dado um homomorfismo de grupos ϕ : G → H, o núcleo de
ϕ é definido por Ker(ϕ) = 1ϕ−1 .
Teorema 1.5 Seja ϕ : G → H um homomorfismo de grupos. Então:
(i) Ker(ϕ) E G;
(ii) se N E G e N ⊆ Ker(ϕ), então existe um e um só homomorfismo de grupos Φ : G/N → H
tal que πN Φ = ϕ,
G
πN
ϕ
/H
<
Φ
G/N
dado por (N a)Φ = aϕ;
(iii) se ϕ for sobrejetivo e N = Ker(ϕ), então Φ é um isomorfismo.
A prova é simples, e já foi estudada em cursos de álgebra na graduação.
Agora podemos revisitar o grupo quociente do Exemplo 1.4. Seja R∗ o grupo constituı́do por
R \ {0}, com a operação produto.
Exemplo 1.6 GLn (R) / SLn (R) ∼
= R∗ .
Consideremos ϕ : GLn (R) → R∗ definida por M ϕ = det(M ). Como
det(M M 0 ) = (det(M ))(det(M 0 ))
para todas matrizes M, M 0 ∈ GLn (R), ϕ é um homomorfismo, além do mais sobrejetivo. Finalmente, Kerϕ = SLn (R), logo obtemos
GLn (R) / SLn (R) = GLn (R) / Ker(ϕ) ∼
= R∗
pelo Teorema 1.5(iii).
1.4
Outros conceitos
Dado um grupo G, dizemos que H ≤ G tem ı́ndice finito se G = Hg1 ∪ . . . ∪ Hgn para algum
número finito de elementos g1 , . . . , gn ∈ G. Nesse caso, o menor n possı́vel diz-se o ı́ndice de H em
G e designa-se por [G : H].
Dado X ⊆ G, é fácil de ver que o conjunto dos elementos da forma
xε11 . . . xεnn ,
onde n ≥ 0, xi ∈ X e εi ∈ {1, −1} para i = 1, . . . , n, constitui o menor subgrupo de G contendo X.
Diz-se o subgrupo de G gerado por X e representa-se por hXi. Um (sub)grupo diz-se finitamente
7
gerado se puder ser gerado por um subconjunto finito. Usaremos a notação H ≤f.g. G para exprimir
que H é um subgrupo finitamente gerado de G.
Nem todo grupo é finitamente gerado: para quem dominar argumento de cardinalidade, é fácil
ver que todo o grupo finitamente gerado é enumerável, e existem grupos não enumeráveis (por
exemplo, o grupo aditivo dos reais).
Um grupo gerado por um único elemento diz-se um grupo cı́clico. A menos de isomorfismo,
(Z, +) é o único grupo cı́clico infinito. Dado n ≥ 1, existe também um único grupo cı́clico com n
elementos a menos de isomorfismo, e é designado por Cn . Se Cn = hai, então
Cn = {a, a2 , . . . , an−1 , an = 1}.
Dado um elemento a de um grupo G, a ordem de a é a cardinalidade do subgrupo hai. Um
elemento pode ter ordem finita ou infinita.
Dados grupos G e H, podemos definir uma operação em G × H através de
(g, h)(g 0 , h0 ) = (gg 0 , hh0 ).
Com esta operação, G × H é um grupo que se diz o produto direto dos grupos G e H.
1.5
Exercı́cios
(1.1) Seja
G=
R∗ R
0 R∗
com a operação produto de matrizes. Mostre que:
(a) G é um grupo;
(b)
H=
1 Z
0 1
é um subgrupo cı́clico de G.
(1.2) Sejam G e H grupos.
(a) Mostre que H pode ser visto como um subgrupo de G × H.
∼ G.
(b) Mostre que nesse caso (G × H)/H =
(1.3) Seja G = R × R∗ com a operação
(x, y)(x0 , y 0 ) = (x + yx0 , yy 0 ).
Mostre que:
(a) G é um grupo;
8
(b) H = R × {1} é um subgrupo normal de G;
(b) G/H ∼
= R∗ .
(1.4) Mostre que C35 ∼
= C5 × C7 .
(1.5) Seja G um grupo e sejam a, b ∈ G tais que H, aHb ≤ G. Mostre que aHb = aHa−1 = b−1 Hb.
(1.6) Seja H um subgrupo de ı́ndice finito de um grupo G. Mostre que:
(a) xHx−1 é um subgrupo de ı́ndice finito de G para todo x ∈ G;
(b) só existe um número finito de subgrupos da forma xHx−1 (x ∈ G).
9
2
Grafos e autômatos
O conceito de autômato é fundamental na teoria da computação, e tem-se revelado da maior utilidade para a moderna teoria de grupos. Vamos apresentar em seguida alguns conceitos e resultados
básicos.
2.1
Palavras e linguagens
Neste contexto, usamos o termo alfabeto para designar um conjunto e os seus elementos são chamados de letras. Muito apropriadamente, uma sequência finita de letras é chamada de palavra. Isto
inclui a palavra vazia, que convencionamos representar pelo sı́mbolo 1. As palavras não vazias (no
alfabeto A) são geralmente representadas na forma a1 a2 . . . an com a1 , . . . , an ∈ A. O comprimento
da palavra a1 . . . an é n, e o comprimento da palavra vazia é 0. Designamos o comprimento da
palavra u por |u|.
Ao longo deste curso, A designará sempre um alfabeto finito, pelo que não faremos mais referências a esse fato. O conjunto de todas as palavras em A é designado por A∗ , e A é identificado
com o conjunto das palavras de comprimento 1. Escrevemos também A+ = A∗ \ {1}.
Podemos definir um produto em A∗ , dito de concatenação. Para palavras não vazias, é definido
por
(a1 . . . an )(b1 . . . bm ) = a1 . . . an b1 . . . bm ,
e a palavra vazia funciona como elemento neutro. Com esta operação, A∗ é um monóide. Mas não
é um monóide qualquer, pois satisfaz a seguinte propriedade (dita universal):
Proposição 2.1 Seja ϕ : A → M uma função de A num monóide M qualquer. Então existe um
único homomorfismo de monóides Φ : A∗ → M que estende a função ϕ:
A _
ϕ
/M
>
Φ
A∗
Prova. É fácil ver que Φ tem que ser definido por (a1 . . . an )Φ = (a1 ϕ) . . . (an ϕ) e 1Φ = 1, e que é
realmente um homomorfismo de monóides. O significado desta propriedade é que A tem em relação a A∗ o mesmo comportamento que
a base de um espaço vetorial V tem em relação a V , quando substituı́mos homomorfismos por
aplicações lineares. Logo podemos pensar em A como uma base de A∗ . As diferenças são as
seguintes:
• Nem todo monóide tem uma base: a menos de isomorfismo, só os monóides da forma A∗ têm
uma base.
• A é a única base de A∗ .
10
Como A∗ satisfaz a propriedade universal relativamente a A, diz-se o monóide livre sobre A.
Certas relações entre palavras são muito importantes. Dadas u, v ∈ A∗ , dizemos que:
• u é um prefixo de v se v = uy para alguma y ∈ A∗ ;
• u é um sufixo de v se v = xu para alguma x ∈ A∗ ;
• u é um fator de v se v = xuy para algumas x, y ∈ A∗ .
Um subconjunto de palavras em A é chamado de A-linguagem, ou simplesmente linguagem
quando o alfabeto está implı́cito ou é irrelevante. A teoria de linguagens é um ramo importante da
teoria da computação que pretende classificar as linguagens e explorar o potencial algorı́tmico das
diversas subclasses. O trabalho pioneiro de Noam Chomsky nos anos 50 está na sua origem, pelo
que a teoria de linguagens se desenvolveu inicialmente no seio da Linguı́stica e não da Informática
ou da Matemática. A teoria deve importantes contribuições ao informático brasileiro Imre Simon.
Se L é uma A-linguagem, é habitual designar por L∗ o conjunto de todas as palavras do tipo
u1 u2 . . . un com n ≥ 0 e ui ∈ L para todo i. Claro que se n = 0 temos a palavra vazia. Isto faz
de L∗ é o submonóide de A∗ gerado por L. É desagradável que se tenha instucionalizado o uso da
notação ∗ com dois significados diferentes (monóide livre e submonóide gerado por), mas felizmente
não há confusão quando escrevemos A∗ .
2.2
Grafos
Os grafos são estruturas combinatórias que desempenham um papel muito importante em várias
áreas da Matemática, pura ou aplicada, e da Computação.
Neste curso, designaremos por grafo uma estrutura do tipo Γ = (V, E), onde V é um conjunto
não vazio (o conjunto dos vértices) e E um conjunto de pares (não ordenados) de elementos de
V (arestas). É habitual descrever um grafo geometricamente utlizando pontos para representar
os vértices e linhas para representar as arestas. Eis um exemplo de um grafo com 7 vértices e 5
arestas:
•
•
•
•
•
•
•
Note-se que nenhuma aresta pode ligar um vértice a si próprio!
Um grafo com um número finito de vértices diz-se finito. Dois vértices dizem-se adjacentes se
estiverem ligados por uma aresta. O grafo diz-se conexo se quaisquer dois vértices estiverem ligados
por uma sequência de arestas (isto é, se pertencerem a uma sequência de vértices adjacentes).
Um isomorfismo de grafos estabelece uma bijeção entre os vértices que preserva a adjacência
(isto é, a estrutura é a mesma a menos da designação dos vértices). Dois grafos são isomorfos se
houver um isomorfismo entre eles. Um isomorfismo de um grafo nele próprio é um automorfismo.
Uma variante deste conceito é a noção de grafo orientado, em que cada aresta está dotada de uma
orientação especı́fica. Formalmente, um grafo orientado é uma estrutura do tipo Γ = (V, E), onde
V é um conjunto não vazio e E ⊆ V ×V . É habitual descrever um grafo orientado geometricamente
11
utlizando pontos para representar os vértices e setas para representar as arestas. Eis um exemplo
de um grafo orientado com 4 vértices e 4 arestas:
*•o
•j
2.3
•
•e
Autômatos
Um autômato pode ser descrito informalmente como um grafo orientado em que as arestas têm
rótulos que não são mais do que letras de um certo alfabeto finito. Além disto, alguns vértices
são chamados de iniciais e outros (que podem ser ou não os mesmos!) de terminais. Também é
habitual utilizar uma representação geométrica, em que os vértices iniciais (respetivamente finais)
são identificados por uma seta que entra (respetivamente sai), sem rótulo:
Exemplo 2.2 Autômato no alfabeto A = {a, b}:
b
o
/•j
a
*•p
b
a
Formalmente, se A é um alfabeto finito, um A-autômato é uma estrutura do tipo A = (Q, I, T, E),
onde
• Q é um conjunto;
• E ⊆ Q × A × Q;
• I, T ⊆ Q.
O conjunto Q é o conjunto dos vértices, I é o conjunto dos vértices iniciais, T é o conjunto dos
vértices terminais e E é o conjunto das arestas. Se não designarmos vértices iniciais nem terminais,
temos a estrutura simplificada (Q, E), que se diz um A-grafo.
O autômato A = (Q, I, T, E) diz-se finito se Q for finito. Dois autômatos A = (Q, I, T, E) e
A0 = (Q0 , I 0 , T 0 , E 0 ) dizem-se isomorfos se existir uma bijeção ϕ : Q → Q0 tal que Iϕ = I 0 , T ϕ = T 0
e
(p, a, q) ∈ E ⇔ (pϕ, a, qϕ) ∈ E 0
para todos p, q ∈ Q e a ∈ A (isto é, têm a mesma estrutura a menos da designação dos vértices).
A grande utilidade de um A-autômato é que ele permite definir uma A-linguagem do seguinte
modo:
Um caminho não trivial em A = (Q, I, T, E) é uma sequência
a
a
a
1
2
n
q0 −→q
1 −→ . . . −→qn
tal que (qi−1 , a, qi ) ∈ E para i = 1, . . . , n. O seu rótulo é a palavra a1 . . . an ∈ A∗ . Diz-se um
1
caminho bem-sucedido se q0 ∈ I e qn ∈ T . Consideramos também o caminho trivial q −→q para
12
cada q ∈ Q (o rótulo é a palavra vazia 1), que é bem-sucedido se q ∈ I ∩ T . Representamos por
u
p−→q qualquer caminho de rótulo u ligando p a q. Um caminho que começa e termina no mesmo
vértice diz-se um loop.
A linguagem L(A) reconhecida por A é o conjunto dos rótulos dos caminhos bem-sucedidos em
A. Uma A-linguagem L diz-se racional se L = L(A) para algum A-autômato finito A.
Exemplo 2.3 A linguagem do autômato do Exemplo 2.2 é o conjunto de todas as palavras no
alfabeto A = {a, b} onde a letra a ocorre um número par de vezes.
Um A-autômato A = (Q, I, T, E) diz-se determinı́stico se tiver um único estado inicial e
(p, a, q), (p, a, r) ∈ E ⇒ q = r
para todos p, q, r ∈ Q e a ∈ A. A vantagem de um autômato ser determinı́stico é que, para testar
se uma palavra u é reconhecida pelo autômato, basta considerar no máximo um caminho de rótulo
u a partir do estado inicial.
Por outro lado, podemos alargar o conceito de autômato admitindo também arestas com rótulo
1: são os autômatos com transições-1. O teorema seguinte mostra que estas 3 versões de autômato
são equivalentes no que respeita a linguagens:
Proposição 2.4 Seja L uma A-linguagem. As condições seguintes são equivalentes:
(i) L é racional;
(ii) L = L(A) para algum A-autômato finito determinı́stico A;
(iii) L = L(A) para algum A-autômato finito com transições-1 A;
(iv) existe um homomorfismo de monóides ϕ : A∗ → M com M finito tal que L = Lϕϕ−1 .
Prova. (ii) ⇒ (i) ⇒ (iii). Imediato.
(iii) ⇒ (iv). Seja A = (Q, I, T, E) um A-autômato finito com transições-1 tal que L = L(A).
Seja M 0 = 2Q×Q o conjunto de todas as relações binárias no conjunto Q. Dadas R, S ∈ M 0 , a sua
composição é definida por
R ◦ S = {(p, q) ∈ Q × Q | (p, r) ∈ R, (r, q) ∈ S para algum r ∈ Q}.
Esta operação é associativa e a relação identidade 1Q funciona como elemento neutro, logo M 0 é de
fato um monóide (finito).
Definimos uma função ϕ : A∗ → M 0 do seguinte modo. Para toda palavra u ∈ A∗ , fazemos
u
uϕ = {(p, q) ∈ Q × Q | existe um caminho p−→q em A}.
Temos (uv)ϕ = (uϕ) ◦ (vϕ) para todas u, v ∈ A∗ . Em particular,
(uϕ) ◦ (1ϕ) = (u · 1)ϕ = uϕ = (1 · u)ϕ = (1ϕ) ◦ (uϕ)
13
para todo u ∈ A∗ , logo M = im(ϕ) munido da operac cão de composição é um monóide finito com
elemento neutro 1ϕ, e ϕ : A∗ → M é um homomorfismo sobrejetivo de monóides.
Claro que L ⊆ Lϕϕ−1 . Reciprocamente, suponhamos que uϕ = vϕ com v ∈ L. Então existe
v
u
um caminho I 3 i−→t ∈ T em A. Mas então existe também um caminho i−→t, logo u ∈ L. Assim
se conclui que L = Lϕϕ−1 como pretendido.
(iv) ⇒ (ii). Seja A = (M, 1M , Lϕ, E) com
E = {(x, a, y) ∈ M × A × M | y = x(aϕ)}.
u
É claro que A é um A-autômato finito determinı́stico. Além disso, p−→q é um caminho se e só se
q = p(uϕ). Logo
L(A) = {u ∈ A∗ | 1M (uϕ) ∈ Lϕ} = Lϕϕ−1 = L
e a prova está completa. Para além do determinismo, há outras propriedades importantes de autômatos. Dizemos que
um autômato A = (Q, I, T, E) é:
• aparado se todo vértice ocorre nalgum caminho bem-sucedido;
• completo se, para todos p ∈ Q e a ∈ A, existe alguma aresta da forma (p, a, q).
A seguir mostramos que o conjunto das A-linguagens racionais é fechado para os operadores
booleanos:
Proposição 2.5 Sejam K, L A-linguagens racionais. Então as linguagens K ∪ L, K ∩ L e A∗ \ L
são racionais.
Prova. Como K∩L = A∗ \((A∗ \K)∪(A∗ \L)), basta mostrar o resultado para união e complemento.
Para a união, tomamos a união disjunta de dois autômatos reconhecendo K e L.
Para o complemento, recordamos que na prova de (iv) ⇒ (ii) da Proposição 2.4 construimos um
autômato finito que além de determinı́stico é completo. Se trocarmos os vértices terminais pelos
não-terminais num tal autômato, passaremos a reconhecer o complemento da linguagem. No entanto, há um método mais construtivo de lidar com a interseção: dados A-autômatos
A = (Q, I, T, E) e A0 = (Q0 , I 0 , T 0 , E 0 ), definimos o produto direto A×A0 = (Q×Q0 , I ×I 0 , T ×T 0 , E 00 )
com
E 00 = {((p, p0 ), a, (q, q 0 )) | (p, a, q) ∈ E, (p0 , a0 , q 0 ) ∈ E 0 }.
Proposição 2.6 Dados A-autômatos A e A0 , L(A × A0 ) = L(A) ∩ L(A0 ).
Prova. Basta observar que os caminhos bem sucedidos em A × A0 são da forma
a
a
a
1
2
n
0
0
→ (q0 , q00 )−→(q
1 , q1 )−→ . . . −→(qn , qn ) →,
com a1 , . . . , an ∈ A, onde
a
a
a
1
2
n
→ q0 −→q
1 −→ . . . −→qn →
14
é um caminho bem sucedido em A e
a
a
a
1
n
0 2
0
→ q00 −→q
1 −→ . . . −→qn →
é um caminho bem sucedido em A0 . A classe das linguagens racionais também é fechada para os operadores produto e estrela:
Proposição 2.7 Sejam K, L A-linguagens racionais. Então as linguagens KL e K ∗ são racionais.
Prova. Suponhamos que A = (Q, I, T, E) e A0 = (Q0 , I 0 , T 0 , E 0 ) são A-autômatos finitos reconhecendo K e L, respetivamente. POdemos assumir que Q ∩ Q0 = ∅. Definimos um A-autômato
finito com transições-1
B = (Q ∪ Q0 , I, T 0 , E ∪ E 0 ∪ (T × {1} × I 0 )).
/ij
*t
A
1
i0 k
A0
+ t0
/
Os caminhos bem-sucedidos em B são da forma
u
1
v
I 3 i−→t−→i0 −→t0 ∈ T 0
com t ∈ T , i0 ∈ I 0 , u ∈ K e v ∈ L, logo
L(B) = {uv | u ∈ K, v ∈ L} = KL.
Por outro lado, seja z ∈
/ Q. Definimos um A-autômato finito com transições-1
B 0 = (Q ∪ {z}, z, z, E ∪ ({z} × {1} × I) ∪ (T × {1} × {z})).
i j_
o
*t
A
1
/z
1
É fácil ver que L(B 0 ) = K ∗ .
Pela Proposição 2.4, as linguagens KL e K ∗ são racionais. Como as linguagens finitas são obviamente racionais, resulta das Proposições 2.5 e 2.7 que
qualquer linguagem obtida a partir de linguagens finitas utilizando um número finito de vezes os
operadores união, produto e estrela é necessariamente racional. O recı́proco é também verdadeiro:
Teorema 2.8 (Kleene 1956) Seja L ⊆ A∗ . Então as condições seguintes são equivalentes:
15
(i) L é racional;
(ii) L pode ser obtida a partir de A-linguagens finitas utilizando um número finito de vezes os
operadores união, produto e estrela.
A demonstração de (i) ⇒ (ii) é proposta no Exercı́cio 2.8.
Podemos também mostrar que as linguagens racionais se comportam muito bem relativamente
a homomorfismos:
Proposição 2.9 Sejam A, B alfabetos finitos e ϕ : A∗ → B ∗ um homomorfismo de monóides.
(i) Se K ⊆ A∗ é racional, então Kϕ é racional.
(ii) Se L ⊆ B ∗ é racional, então Lϕ−1 é racional.
Prova. (i) Seja A um A-autômato finito reconhecendo K. Substituindo cada rótulo a em A por
uma aresta ou sucessão de arestas de rótulo aϕ, obtemos um B-autômato finito (com transições-1
se 1 ∈ Aϕ) que reconhece Kϕ. Pela Proposição 2.4, Kϕ é racional.
(ii) Seja L0 = L ∩ (A∗ ϕ). Pelas alı́nea (i) e pela Proposição 2.5, L0 é racional. Pela Proposição
2.4, existe um homomorfismo de monóides θ : B ∗ → M com M finito tal que L0 = L0 θθ−1 . Seja
ψ : A∗ → M o homomorfismo definido por ψ = ϕθ. Então
(L0 ϕ−1 )ψψ −1 = L0 ϕ−1 ϕθθ−1 ϕ−1 = L0 θθ−1 ϕ−1 = L0 ϕ−1 ,
logo L0 ϕ−1 é racional. Como Lϕ−1 = L0 ϕ−1 , resulta que Lϕ−1 é racional. 2.4
Sistemas de reescrita
Os sistemas de reescrita são uma ferramenta importante na álgebra e na teoria da computação.
Vamos apresentar algumas noções básicas que serão úteis para o estudo do grupo livre.
Seja A um alfabeto finito. Um sistema de reescrita em A é um subconjunto R of A∗ × A∗
(isto é, uma relação binária em A!). Recebem aqui um nome diferente porque vamos usá-los numa
perspetiva diferente: vão-nos permitir substituir fatores dentro de palavras:
Dadas u, v ∈ A∗ , escrevemos u −→R v (redução elementar) se existirem (r, s) ∈ R e x, y ∈ A∗
tais que u = xry e v = xsy. Escrevemos u −→∗R v (redução) se u = v ou se existir alguma cadeia
x = z0 −→R z1 −→R . . . −→R zm = y.
Sempre que não haja confusão possı́vel, omitimos o ı́ndice
Dizemos que R é:
R.
• redutor se |r| > |s| para todo (r, s) ∈R;
• noetheriano se não existir nenhuma cadeia infinita de reduções elementares
w0 −→R w1 −→R w2 −→R . . .
16
• confluente se, sempre que u−→∗ v e u−→∗ w, existir alguma z ∈ A∗ tal que v−→∗ z e w−→∗ z:
u
∗
∗
w
∗
/v
/ z
∗
É claro que todo sistema de reescrita redutor é necessariamente noetheriano. Uma palavra u ∈ A∗
é irredutı́vel se não existir v ∈ A∗ tal que u−→v. Seja Irr(R) o conjunto de todas as palavras
irredutı́veis de A∗ com respeito a R.
Proposição 2.10 Seja R ⊆ A∗ × A∗ um sistema de reescrita noetheriano e confluente. Para toda
palavra u ∈ A∗ , existe uma e uma só v ∈ Irr(R) tal que u−→∗ v.
Prova. O ser noetheriano garante a existência, a confluência garante a unicidade. 2.5
Exercı́cios
(2.1) Seja M um monóide finito não trivial. Mostre que a propriedade universal não é válida para
nenhum subconjunto de M , e que portanto M não possui uma base.
(2.2) Quantos grafos de 4 vértices existem, a menos de isomorfismo?
(2.3) Quantos grafos orientados de 2 vértices existem, a menos de isomorfismo?
(2.4) Seja A = {a, b}. Construa um A-autômato finito reconhecendo cada uma das seguintes Alinguagens:
(a) {palavras acabando em aba};
(b) {palavras de comprimento par}.
(2.5) Seja A = {0, 1}. Construa um A-autômato finito reconhecendo todos os números naturais
divisı́veis por 3, escritos em binário.
(2.6) Considere os seguintes autômatos:
o
b
/•
a
/•
a
`
b
•
~
o
a
/•
`
b
b
B•
A
B
17
/•
b
a

b
(a) Determine L(A) e L(B).
(b) Construa um autômato finito reconhecendo L(A) ∩ L(B).
(2.7) Seja A = {a, b} e seja A o A-autômato com transições-1 descrito por
a
/1j
a
b
*2
/
1
Usando os algoritmos implı́citos na prova da Proposição 2.4, construa um autômato finito
determinı́stico completo que reconheça A∗ \ L(A).
(2.8) Seja A um alfabeto finito e seja A = (Q, 0, T, E) um A-autômato com Q = {0, . . . , m}. Dados
(k)
p, q ∈ Q e k ∈ {0, . . . , m + 1}, seja Lp,q o conjunto dos rótulos dos caminhos p−→q em que
todos os vértices intermédios são < k.
(a) Mostre que
(k)
(k)
(k)
∗
L(k+1)
= L(k)
p,q
p,q ∪ Lp,k (Lk,k ) Lk,q
para todos p, q, k ∈ Q.
(b) Usando recursivamente a alı́nea (a), demonstre a implicação (i) ⇒ (ii) do Teorema 2.8.
(2.9) Seja A = {a, b} e considere o sistema de reescrita em A definido por R= {(ab, 1)}.
(a) Mostre que R é redutor e confluente.
(b) Calcule Irr(R).
18
3
Grupos livres
Nesta secção definimos os grupos livres e estudamos algumas das suas propriedades básicas.
3.1
Construção
Seja A um alfabeto. Queremos que o grupo livre sobre A seja um grupo que satisfaça a propriedade
universal na classe dos grupos (analogamente à Proposição 2.1).
Começamos por introduzir um conjunto A−1 de inversos formais of A (i.e. a 7→ a−1 define uma
e = A ∪ A−1 , estendemos
bijeção de A com um conjunto A−1 disjunto de A). Usando a notação A
−1
−1
∗
∗
e →A
e através de
indutivamente a função a 7→ a a uma transformação
:A
• 1−1 = 1,
• (a−1 )−1 = a
(a ∈ A),
• (ua)−1 = a−1 u−1
e+ , a ∈ A).
e
(u ∈ A
e∗ , pelo que é chamada de
Note-se que esta transformação satisfaz (u−1 )−1 = u para todo u ∈ A
involução. Esta involução será importante para os chamados homomorfismos involutivos. Se G é
e∗ → G se diz involutivo se u−1 ϕ = (uϕ)−1 para
um grupo, um homomorfismo (de monóides) ϕ : A
∗
e
todo u ∈ A .
e por
Definimos agora um sistema de reescrita em A
e
RA = {(aa−1 , 1) | a ∈ A}.
É fácil provar que:
Lema 3.1 O sistema de reescrita RA é redutor e confluente.
Prova. É claro que o sistema é redutor. Para a confluência, supomos que
x00 −→x01 −→ . . . −→x0n ,
x00 −→x10 −→ . . . −→xm0 ,
são duas sequências de transições em RA . Basta mostrar a confluência localmente, construindo a
19
grelha
x00
/ x01
/
...
/ x0n
x10
/ x11
/
...
/ x1n
..
.
..
.
..
.
/ xm1
xm0
/
...
/ xmn
/ pode representar uma redução elementar ou igualdade
passo a passo (onde cada seta
mesmo). Para completar cada quadrado, basta mostrar a confluência para qualquer caso da forma
/ x 1 y1
u
x 2 y2
−1
−1
−1
e∗
e
onde u = x1 a1 a−1
1 y1 = x2 a2 a2 y2 com xi , yi ∈ A e ai ∈ A. Se as ocorrências de a1 a1 e a2 a2
forem disjuntas, podemos reproduzir a redução de tipo alternativo em cada uma das palavras x1 y1
e x2 y2 . Caso as ocorrências se sobreponham, resulta imediatamente x1 y1 = x2 y2 . Logo é válida a
confluência local, que implica a confluência no sentido geral do termo. e
Seja RA = Irr(RA ). As palavras de RA dizem-se reduzidas. São precisamente as palavras em A
e Pela Proposição 2.10 e pelo Lema 3.1, obtemos:
sem fatores do tipo aa−1 (a ∈ A).
e∗ , existe uma única palavra reduzida u ∈ RA tal que
Lema 3.2 Seja A um alfabeto. Dada u ∈ A
∗
u −→RA u.
e∗ por
Definimos uma relação de equivalência ρA em A
u ρA v
se u = v
e∗ , definimos
Designando por uρA a classe de equivalência de u ∈ A
e∗ /ρA = {uρA | u ∈ A
e∗ }.
FA = A
Mostramos em seguida que FA é um grupo que satisfaz a propriedade universal:
20
Teorema 3.3 Seja A um alfabeto. Então:
(i) FA é um grupo para a operação binária (uρA )(vρA ) = (uv)ρA .
(ii) A função
ι : A → FA
a 7→ aρA
é injetiva.
(iii) Seja ϕ : A → G uma função de A num grupo G qualquer. Então existe um único homomorfismo de grupos Φ : FA → G tal que ιΦ = ϕ:
ϕ
A _
ι
/G
>
Φ
FA
Prova. (i) Primeiro há que mostrar que a operação está bem definida. Suponhamos que u ρA u0 e
v ρA v 0 . Será que (uv)ρA (u0 v 0 )? Efetivamente, de u = u0 e v = v 0 resulta (pela unicidade no Lema
3.2) que
uv = u v = u0 v 0 = u0 v 0 ,
logo (uv)ρA (u0 v 0 ) e a operação está bem definida.
e∗ se
É imediato que a operação é associativa e tem elemento neutro 1ρA . Como para todo u ∈ A
−1
−1
−1
tem uu−1 = 1, resulta que (uρA )(u ρA ) = (uu )ρA = 1ρA . Analogamente, (u ρA )(uρA ) = 1ρA ,
logo FA é um grupo.
(ii) Como todas as letras são palavras reduzidas, a injetividade resulta do Lema 3.2.
e → G fazendo a−1 ϕ0 =
(iii) Começamos por estender a função ϕ : A → G a uma função ϕ0 : A
−1
(aϕ) (a ∈ A). Pela propriedade universal (Proposição 2.1), existe um único homomorfismo de
e∗ → G que estende ϕ0 . Note-se que este homomorfismo é involutivo.
monóides Φ0 : A
e∗ , é fácil ver que uΦ0 = uΦ0 , logo u ρA v implica uΦ0 = vΦ0 . Podemos então definir
Dado u ∈ A
uma função Φ : FA → G através de
(uρA )Φ = uΦ0
e∗ ).
(u ∈ A
e∗ → FA a
É fácil verificar que Φ é na realidade um homomorfismo de grupos. Designando por θ : A
projeção canónica, obtemos um diagrama
ϕ
A _
ϕ0
e
A
/G
? O `
Φ
Φ0
e∗
/A
θ
/ FA
que é composto de três diagramas comutativos. Logo ιΦ = ϕ. Finalmente, a unicidade de Φ resulta
do fato de Aθ gerar o grupo FA , pelo que Φ vem determinado por ϕ. 21
Face ao Teorema 3.3, podemos dizer que FA é o grupo livre sobre A. É simples verificar que RA
com a operação binária (u, v) 7→ uv constitui um grupo e que
FA → RA
uρA 7→ u
é um isomorfismo de grupos. Por isso é muito comum identificar o grupo livre com o conjunto
das palavras reduzidas. Nós também faremos isso quando for conveniente. Usaremos também a
e∗ .
notação uρA = u para todo u ∈ A
Além do mais, estendemos a FA vários dos conceitos introduzidos na Subsecção 2.1. Por exemplo, dados g, h ∈ FA , temos |g| = |g| e g é prefixo de h se e só se g é prefixo de h.
3.2
Propriedades básicas
A primeira consequência da existência dos grupos livres é a seguinte:
Teorema 3.4 Todo o grupo é isomorfo a algum quociente de um grupo livre.
Prova. Seja G um grupo e seja A ⊆ G um subconjunto gerador de G (poderı́amos até tomar o
próprio G!). Pela propridade universal, a inclusão A ,→ G induz um homomorfismo de grupos
Φ : FA → G, que é sobrejetivo dado que G = hAi. Logo G ∼
= FA /Ker(Φ) pelo Teorema 1.5(iii). Em seguida vamos determinar quando dois grupos livres são isomorfos.
Teorema 3.5 Sejam A e B conjuntos. Então as condições seguintes são equivalentes:
(i) FA ∼
= FB ;
(ii) |A| = |B|.
|A|
Prova. (i) ⇒ (ii). Seja ϕ : FA → FB um isomorfismo. Seja C2 o produto direto de |A| cópias
do grupo cı́clico C2 . Suponhamos que A = {a1 , . . . , am }. Para i = 1, . . . , m, designamos por |u|ai
e∗ . Note-se que |u|a = |u|a ,
a soma dos expoentes das ocorrências de a/a−1 na palavra u ∈ A
i
i
|A|
logo isto permite definir |g|ai para todo g ∈ FA . Seja πA : FA → C2 a função definida por
gπA = (|g|a1 , . . . , |g|am ). É rotina verificar que πA é um homomorfismo sobrejetivo de grupos.
|B|
Definindo de forma análoga πB : FB → C2 , temos também um homomorfismo sobrejetivo.
Suponhamos que g ∈ Ker(πA ). Então |g|ai é par para i = 1, . . . , m. Daqui resulta que |gϕ|b é
par para todo b ∈ B, logo gϕ ∈ Ker(πB ) e portanto Ker(πA ) ⊆ Ker(ϕπB ). Pelo Teorema 1.5(ii),
|B|
existe um homomorfismo Φ : FA /Ker(πA ) → C2 tal que o diagrama
FA
ϕ
/ FB
πB
FA /Ker(πA )
Φ
22
/ C |B|
2
|A|
comuta. Note-se que Φ é sobrejetivo porque ϕπB é sobrejetivo. Como FA /Ker(πA ) ∼
= C2 pelo
|A|
|B|
|A|
Teorema 1.5(iii), resulta a existência de um homomorfismo sobrejetivo C2 → C2 . Como |C2 | =
|B|
2|A| e |C2 | = 2|B| , segue que |A| ≥ |B|. Aplicando o mesmo argumento ao isomorfismo ϕ−1 : FB →
FA , concluimos qu |A| = |B|.
(ii) ⇒ (i). É imediato que qualquer bijeção A → B induz um isomorfismo FA → FB . Um subconjunto B de um grupo G dix-se uma base de G se B gera G e não existe nenhuma
palavra reduzida não vazia bε11 . . . bεnn no alfabeto B que seja igual a 1 em G. Isto equivale a dizer
que a inclusão B ,→ G induz um isomorfismo FB → G. Em particular, G tem que ser um grupo
livre. É claro que A é uma base de FA , mas existem muitas mais (como veremos na Secção 4), ao
contrário do caso dos monóides livres. Podemos então concluir do Teorema 3.5 que todas as bases
de um mesmo grupo livre possuem o mesmo número de elementos. Este número diz-se a dimensão
do grupo livre (logo dim(FA ) = |A|). É comum designar por Fn o grupo livre de dimensão n (que é
único a menos de isomorfismo). O grupo livre F2 estará presente em muitos exemplos e exercı́cios.
Assumiremos genericamente A = {a, b} como base para F2 .
e∗ /ρA ), é imporQuando um grupo é definido como quociente (é o caso do grupo livre FA = A
tante saber resolver o problema da palavra, isto é, saber em que condições (algoritmicamente, isto
é, queremos ser capazes de dizer SIM ou NÃO!) duas palavras representam o mesmo elemento.
Dizemos então que o problema da palavra é decidı́vel. No caso dos grupos livres, é muito fácil:
e∗ representam o mesmo elemento se e só se u = v.
u, v ∈ A
O problema da conjugação constitui um desafio menos óbvio. Aqui o objetivo é determinar
algoritmicamente se dois elementos g, h ∈ G são ou não conjugados, isto é, se existe algum x ∈ G
tal que g = xhx−1 . É fácil ver que a relação de conjugação é uma relação de equivalência.
Uma palavra reduzida u ∈ RA diz-se ciclicamente reduzida se não for da forma u = ava−1 com
e
a ∈ A.
Lema 3.6 Seja u ∈ RA . Então existem x, v ∈ RA tais que u = xvx−1 e v é ciclicamente reduzida.
Além disso, x e v são únicas.
Prova. A existência é fácil. Suponhamos agora que u = xvx−1 = ywy −1 com v, w ciclicamente
reduzidas. Se |x| < |y|, então y = xz para alguma z ∈ RA não vazia, logo v = zwz −1 , contradizendo
v ciclicamente reduzida. Por simetria, |x| > |y| também está excluı́da, logo |x| = |y| e obtemos
sucessivamente x = y e v = w. Dizemos que a palavra v no enunciado anterior é o núcleo cı́clico de u.
Um grupo diz-se:
• de torsão se todos seus elementos tiverem ordem finita;
• livre de torsão se o elemento neutro for o único elemento de ordem finita.
Corolário 3.7 FA é livre de torsão.
Prova. Seja g ∈ FA \{1}. Pelo Lema 3.6, podemos escrever g = xvx−1 com x ∈ RA e v ciclicamente
reduzida. Dado n ≥ 1, temos g n = (xvx−1 )n ρA = (xv n x−1 )ρA . Como g 6= 1, também v 6= 1 e logo
xv n x−1 é reduzida. Logo g n = xv n x−1 6= 1 e portanto g n tem ordem infinita. 23
Se u = vw for uma palavra ciclicamente reduzida, então a palavra wv é também ciclicamente
reduzida. Diz-se um conjugado cı́clico de u. Note-se que u = w−1 (wv)w, logo os conjugados cı́clicos
são de fato conjugados no grupo livre.
É claro que só existe um número finito de conjugados cı́clicos para uma dada palavra. É fácil
ver que a relação “ser conjugado cı́clico de” é uma relação de equivalência.
Teorema 3.8 Seja A um alfabeto e g, h ∈ FA . Então as condições seguintes são equivalentes:
(i) g e h são conjugados em FA ;
(ii) os núcleos cı́clicos de g e h são conjugados cı́clicos.
Prova. (i) ⇒ (ii). Como o único conjugado de 1 é ele próprio, podemos assumir que g 6= 1. Seja
e Como ser conjugado cı́clico é uma relação de
g = xux−1 com u ciclicamente reduzido. Seja a ∈ A.
equivalência, basta mostrar que o núcleo cı́clico v de aga−1 é um conjugado cı́clico de u.
Se x 6= 1, então v = u, logo podemos assumir que x = 1. Se aua−1 for reduzida, então mais
uma vez u = v. Como u 6= 1 (pois g 6= 1), podemos assumir que au não é reduzida (o outro caso é
análogo). Então podemos escrever u = a−1 w, logo
aga−1 = aua−1 = aa−1 wa−1 = wa−1 .
Como u é ciclicamente reduzida, não pode terminar em a. Logo wa−1 ∈ RA e aga−1 = wa−1 .
Como w não começa por a (senão u = a−1 w não seria reduzida), resulta que wa−1 = v. Portanto
v é um conjugado cı́clico de u.
(ii) ⇒ (i). No grupo livre, toda a palavra é conjugada do seu núcleo cı́clico, e os conjugados cı́clicos são conjugados. Agora basta recordar que a relação de conjugação é uma relação de
equivalência. Daqui resulta a solução do problema da conjugação de FA , pois os núcleos cı́clicos são efetivamente computáveis, assim como os seus conjugados cı́clicos.
Exemplo 3.9 a−1 (ba)2 é conjugado de b−1 ab3 em F2 , mas não de ba3 b−1 a−1 b−1 .
Com efeito, os núcleos cı́clicos destas três palavras são respetivamente bab, ab2 e a2 b−1 , donde
resulta a afirmação.
3.3
Autômatos e subconjuntos racionais
Veremos em seguida alguns resultados clássicos dos anos 60 e 70 que estabeleceram as primeiras
relações entre a teoria de grupos e a teoria de autômatos.
Lema 3.10 RA é uma linguagem racional.
24
e ∪ {1} e
Prova. Seja Q = A
e p ∈ Q \ {a−1 }}.
E = {(p, a, a) | a ∈ A,
e
Definimos o A-autômato
finito A = (Q, 1, Q, E). Os caminhos bem-sucedidos neste autômato são
da forma
a1
a2
a3
an
1−→a
1 −→a2 −→ . . . −→an
e e ai 6= a−1 . Daqui resulta que L(A) = RA , pelo que RA é racional. com n ≥ 0, ai ∈ A
i−1
Exemplo 3.11 Se A = {a, b}, o autômato construı́do na prova do Lema 3.10 é
a
b
= bL
b
o
aL m`
a
/
b
a
1o
b−1
a
/
a−1
b
a−1
b−1
o
~
b−1
N m
a−1
b−1
b−1
! - a−1
P
/
a−1
e∗ , escrevemos L = {u | u ∈ L}. O resultado seguinte (Teorema
Dada uma linguagem L ⊆ A
de Benois) foi pioneiro nas relações entre grupos livres e autômatos, e mostrou que a redução de
palavras não constituı́a um problema:
e
e
Teorema 3.12 (Benois 1969) Seja L uma A-linguagem
racional. Então L é também uma Alinguagem racional que pode ser calculada algoritmicamente a partir de L.
e
Prova. Seja A = (Q, I, T, E) um A-autômato
finito reconhecendo L. Definimos uma sucessão
(An )n de autômatos finitos com transições-1 do seguinte modo. Seja A0 = A. Assumindo que
An = (Q, I, T, En ) já está definido, consideramos todas as instâncias de pares ordenados (p, q) ∈
Q × Q tais que:
−1
aa
1
e mas nenhum caminho p−→q.
existe um caminho p−−→q em An para algum a ∈ A,
(1)
É claro que só existe um número finito de instâncias de (1) em An . Seja En+1 a união de En
com novas arestas da forma (p, 1, q), onde (p, q) ∈ Q × Q é uma instância de (1) em An , e seja
25
An+1 = (Q, I, T, En+1 ). Note que An = An+k para todo k ≥ 1 caso não exista nenhuma instância
de (1) em An .
Como Q é finito, a sucessão (An )n tem que se tornar constante, digamos a partir de Am . Vamos
mostrar que
L = L(Am ) ∩ RA .
(2)
Seja u ∈ L. Então existe uma sucessão de reduções elementares
u = u0 −→RA u1 −→RA . . . −→RA un = u.
Uma indução simples mostra que ui ∈ L(Ai ) para i = 0, . . . , n. Logo u ∈ L(Ak )∩RA ⊆ L(Am )∩RA .
Resulta que L ⊆ L(Am ) ∩ RA .
u
Para a inclusão oposta, começamos por notar que todo caminho p−→q em Ai+1 dá origem a
v
um caminho p−→q em Ai , tal que v pode ser obtido a partir de u inserindo um número finito de
fatores da forma aa−1 . Logo
L(Am ) = L(Am−1 ) = · · · = L(A0 ) = L
(3)
e portanto L(Am ) ∩ RA ⊆ L(Am ) = L. Isto completa a prova de (2).
Pelos Lema 3.10 e Proposição 2.5, a linguagem L é racional. A natureza construtiva destes dois
resultados permite a construção efetiva de um autômato reconhecendo L a partir do autômato A.
A noção de linguagem racional pode ser estendida a subconjuntos de outros monóides/grupos.
Seja M um monóide. Podemos definir um M -autômato ou autômato sobre M como sendo um
autômato em que os rótulos das arestas são elementos de M . Então L(A), o conjunto dos rótulos
dos caminhos bem-sucedidos, é naturalmente um subconjunto de M . Um subconjunto X ⊆ M
dis-se racional se X = L(A) para algum M -autômato finito A. O resultado seguinte generaliza a
Proposição 2.9(i):
Proposição 3.13 Seja ϕ : M → N um homomorfismo de monóides e seja X ⊆ M racional.
Então Xϕ é um subconjunto racional de N .
Prova. Seja A um M -autômato tal que L(A) = X. Se substituirmos cada rótulo m ∈ M de uma
aresta de A por mϕ, obtemos um N -autômato A0 tal que L(A0 ) = Xϕ. Logo Xϕ é racional. No contexto dos grupos, a noção de subconjunto racional é uma útil generalização do conceito
de subgrupo finitamente gerado. O resultado seguinte comprova a legitimidade deste perspetiva,
mesmo para grupos arbitrários:
Teorema 3.14 (Anisimov e Seifert 1975) Seja H um subgrupo de um grupo G. Então as condições
seguintes são equivalentes:
(i) H é um subconjunto racional de G;
(ii) H é finitamente gerado.
26
Prova. (i) ⇒ (ii). Seja A = (Q, I, T, E) um G-autômato tal que H = L(A). Podemos assumir que
A é aparado (caso contrário suprimimos os vértices supérfluos). Seja A ⊆ G o conjunto (finito) dos
rótulos das arestas de A. Escrevendo m = |Q|, definimos
−1 k
X = H ∩ (∪2m−1
k=0 (A ∪ A ) ).
Como A é finito, X é um subconjunto finito de H. Vamos provar que H = hXi.
Dado h ∈ H, podemos escrever h = a1 a2 . . . an para algum caminho
a
a
a
1
2
n
I 3 q0 −→q
1 −→ . . . −→qn ∈ T
em A (logo a1 , . . . , an ∈ A). Vamos mostrar que h ∈ hXi por indução sobre n.
Se n < 2m, então h ∈ X por definição de X. Logo podemos assumir que n ≥ 2m e que a
hipótese é válida para menos que n fatores. Seja u = a1 . . . an−m e v = an−m+1 . . . an . Eliminando
w
ciclos desnecessários, podemos tomar um caminho qn−m −→qn de comprimento < m (isto é, com
menos de m arestas). Logo uw ∈ L(A) = H e pela hipótese de indução uw ∈ hXi. Por outro lado,
−1 k
w−1 v ∈ ∪2m−1
k=0 (A ∪ A )
e w−1 v = (w−1 u−1 )(uv) ∈ H, logo w−1 v ∈ X. Daqui resulta que h = (uw)(w−1 v) ∈ hXi, logo
H = hXi é finitamente gerado.
(ii) ⇒ (i). Seja H = hh1 , . . . , hm i. Definimos um G-autômato com um só vértice A =
({q}, q, q, E), onde
−1
E = {q} × {h1 , . . . , hm , h−1
1 , . . . , hm } × {q}.
É imediato que H = L(A), logo H é racional. 3.4
Grafos de Cayley
A existência de inversos nos grupos conduz naturalmente ao conceito de autômato inverso. Dado
e
um A-autômato
A = (Q, I, T, E), dizemos que A é:
• involutivo se satisfaz
(p, a, q) ∈ E ⇔ (q, a−1 , p) ∈ E
para todo a ∈ A;
• inverso se é determinı́stico, aparado e involutivo.
Uma boa ilustração destes conceitos é dada pelos grafos de Cayley de grupos. Seja G um grupo
e
gerado por A. O grafo de Cayley ΓA (G) é um A-grafo
que tem os elementos de G como vértices e
arestas da forma
a
e
g −→ga (g ∈ G, a ∈ A).
Fixando a identidade 1 como o único vértice inicial e terminal (num autômato, chamamos um tal
vértice de ponto base), obtemos um autômato inverso. Qual é a sua linguagem? Precisamente o
27
e∗ tais que u = 1 em G. Isto é, se π : A
e∗ → G designar o homomorfismo
conjunto das palavras u ∈ A
involutivo que estende a inclusão A ,→ G (e que é sobrejetivo porque G = hAi), então a linguagem
reconhecida pelo autômato é 1π −1 , linguagem de suma importância para a compreensão da estrutura de G! Esta linguagem está intimamente ligada ao problema da palavra de G, discutido na
Subsecção 7.3.
Na representação de autômatos inversos (e grafos de Cayley) é habitual omitir a representação
das arestas com rótulo em A−1 .
Exemplo 3.15 O grupo simétrico S3 (permutações do conjunto {1, 2, 3} é gerado pelas permutações
a = (123) e b = (12). O respetivo grafo de Cayley é
a
•V k
b
+•o
b
>•
b
a
F•
a
~
b
a
a
a
•T
b
b
•
Note-se que podemos omitir a designação dos vértices devido à natureza simétrica dos grafos de
Cayley. Como G actua à esquerda no grafo por translações (isto é, cada elemento x ∈ G transforma
a
a
o vértice g ∈ G em xg e a aresta g −→ga em xg −→xga), sempre tem um automorfismo deste grafo
levando qualquer vértice p em qualquer vértice q. Dizemos que um tal grafo é transitivo nos vértices.
O grafo de Cayley de FA (relativamente à base canónica A) é fácil de descrever. Como 1θ−1 =
e∗ → FA , ΓA (FA ) não pode conter ciclos cujo rótulo seja
RA para o homomorfismo canónico θ : A
uma palavra reduzida. Sendo assim, se omitirmos a representação das arestas com rótulo em A−1 ,
obtemos uma árvore infinita.
28
Exemplo 3.16 Se A = {a, b}, podemos descrever uma porção de ΓA (FA ) por
· ·O ·
b
···
/•
O
a
· ·O ·
a
/ ···
· ·O ·
b
b
···
a
/•
O
b
/•
O
a
/•
O
a
b
a
/ ···
b
···
···
b
/•
O
a
···
a
/ ···
b
···
3.5
Exercı́cios
(3.1) Seja A um alfabeto finito. Mostre que o produto direto Z|A| é o grupo abeliano livre sobre A.
(3.2) Mostre que {abn , b} é uma base de F2 para todo n ∈ Z.
(3.3) Seja H = han ba−n | n ∈ Ni ≤ F2 . Mostre que H não é finitamente gerado.
(3.4) Determine se os seguintes pares de palavras representam elementos conjugados de F2 :
(a) b−1 abb−1 ab−1 a−1 ba−1 baa−1 e bab−1 aa−1 aba−2 bb−2 ;
(b) bababb−2 a−1 baa−2 b−1 e b−3 a−1 a3 b−1 a−2 ab2 a−2 b3 .
e∗
(3.5) Seja A um alfabeto finito. Mostre que a linguagem das palavras ciclicamente reduzidas de A
é racional.
(3.6) Seja A o autômato descrito por
b
/•
_
/•p
a
b−1
•

b
a−1
/
Construa a sucessão de autômatos com transições-1 definida na prova do Teorema 3.12.
29
(3.7) Seja A um alfabeto finito. Mostre que:
e
(a) para todo X ⊆ FA , X é um subconjunto racional de FA se e só se X é uma A-linguagem
racional;
(b) o conjunto dos subconjuntos racionais de FA é fechado para os operadores booleanos.
(3.8) Construa ΓA (G) para:
(a) G = C2 × C4 e A = {(1, 0), (0, 1)}.
(b) G = Z × Z e A = {(1, 0), (0, 1), (1, 1)}.
30
4
Representação de subgrupos
Os autômatos finitos constituem hoje a forma mais eficiente de representar um subgrupo finitamente
gerado H de um grupo livre FA . O algoritmo conhecido como construção de Stallings constrói um
autômato inverso S(H) que tem imensas aplicações (embora no artigo original de Stallings ele usasse
imersões de grafos, o que é mais complicado). Várias das ideias presentes eram já conhecidas de
matemáticos como Reidemeister, Schreier, e sobretudo Serre.
4.1
Construção de Stallings
Uma das maiores contribuições de Stallings é mesmo o algoritmo para construir S(H):
(1) Tomando um conjunto finito de geradores h1 , . . . , hm de H em forma reduzida, começamos por
construir o chamado autômato flor F(H), em que pétalas rotuladas pelas palavras reduzidas
hi (e as arestas inversas, para que seja um autômato involutivo) são coladas a um ponto base
q0 :
h2
0•
P
h1
hm
a
a
(2) Numa segunda fase, identificamos successivamente pares de arestas da forma q ←−p−→r até
obtermos um autômato determinı́stico (inverso, de fato!), designado por S(H).
Note-se que, como o número de arestas diminui a cada dobragem, acabamos sempre por obter
um autômato inverso, dito autômato de Stallings de H.
Exemplo 4.1 Construção do autômato de Stallings de H = ha2 , ab−1 c, ci:
F(H):
•J
a
•O o
b
a
? qO0 d
a
c
•
31
c
1a dobragem:
•J
a
•o
a,b
a
q o
D 0
/
3 q0 o
Q
/
c
2a
dobragem e S(H):
•t
a,b
a
c
Há duas questões naturais no que respeita a esta construção:
• O resultado final depende da ordem em que as dobragens de arestas são feitas?
• O resultado final depende do conjunto finito de geradores de H escolhido?
Veremos que a resposta é NÃO a ambas as questões. Para mostrar isso, precisamos de introduzir
e
um novo conceito. Dizemos que um A-autômato
finito A é SFG se:
• A é inverso;
• A tem um ponto base (o vértice inicial é também o único vértice terminal);
• todo vértice ocorre nalgum caminho bem-sucedido de rótulo reduzido.
Veremos mais adiante que estes autômatos são precisamente os autômatos de Stallings de subgrupos
finitamente gerados de FA (o que explica a designação SFG).
e
Lema 4.2 Sejam A e A0 A-autômatos
SFG. Então as condições seguintes são equivalentes:
(i) A ∼
= A0 ;
(ii) L(A) ∩ RA = L(A0 ) ∩ RA .
Prova. (i) ⇒ (ii). Autômatos isomorfos têm a mesma linguagem.
(ii) ⇒ (i). Sejam A = (Q, q0 , q0 , E) e A0 = (Q0 , q00 , q00 , E 0 ). Definimos uma função ϕ : Q → Q0
u
v
do seguinte modo. Seja q ∈ Q. Como A é SFG, possui um caminho q0 −→q −→q0 com uv ∈ RA .
u
v
Logo uv ∈ L(A0 ) ∩ RA e A0 possui um caminho q00 −→q 0 −→q00 . Definimos qϕ = q 0 .
w
z
Será que ϕ está bem definida? Suponhamos que q0 −→q −→q0 é um caminho alternativo com
w
z
wz ∈ RA , e q00 −→p0 −→q00 é um caminho em A0 . Pelo menos uma das palavras uz, uw−1 é reduzida,
logo uz ∈ L(A0 ) ou uw−1 ∈ L(A0 ). Como A0 é determinı́stico, resulta facilmente que ϕ está bem
definida. Note-se que q0 ϕ = q00 (considerando u = v = 1).
32
u
v
w
z
Sejam p, q ∈ Q. Tomemos caminhos q0 −→q −→q0 e q0 −→p−→q0 em A com uv, wz ∈ RA . Se
u
v
w
z
pϕ = qϕ = q 0 , então existem caminhos q00 −→q 0 −→q00 e q00 −→q 0 −→q00 em A0 . Usando um argumento
análogo ao do parágrafo anterior, obtemos uw−1 ∈ L(A) ou uz ∈ L(A). Como A é determinı́stico,
resulta que p = q, logo ϕ é injetiva.
u
v
Suponhamos agora que (p0 , a, q 0 ) ∈ E 0 . Como A0 é SFG, possui caminhos q00 −→p0 −→q00 e
w
z
q00 −→q 0 −→q00 com uv, wz ∈ RA . Logo uma das palavras uaw−1 , uaz, v −1 aw−1 , v −1 az −1
é reduzida,
u
a
w
−1
e pertencerá a L(A). Assumindo que é uaw , obtemos um caminho q0 −→p−→q −→q0 em A,
donde resulta que pϕ = p0 e qϕ = q 0 . Em particular, ϕ é sobrejetiva! Além disso, mostrámos que
(pϕ, a, qϕ) ∈ E 0 implica (p, a, q) ∈ E. A implicação recı́proca é análoga, logo ϕ é um isomorfismo
de autômatos. Teorema 4.3 (Stallings 1983) Seja H ≤f.g. FA . Então:
(i) S(H) é um autômato SFG;
(ii) L(S(H)) ∩ RA = H.
Prova. (i) É claro que S(H) é inverso e tem um ponto base. Por outro lado, já é verdade que todo
o vértice de F(H) ocorre nalgum caminho bem-sucedido de rótulo reduzido. Esta propriedade se
mantém ao longo do processo de dobragens, pois L(F(H)) ⊆ L(S(H)).
(ii) É fácil ver que L(F(H)) ⊆ H. Por outro lado, se A0 resulta do autômato involutivo A por
uma dobragem de arestas, o argumento usado para provar (3) implica que L(A0 ) = L(A). Daqui
se conclui que L(S(H)) = L(F(H)) ⊆ H e logo L(S(H)) ∩ RA ⊆ L(S(H)) ⊆ H.
Reciprocamente, seja u ∈ H. Suponhamos que h1 , . . . , hm foram os geradores de H usados na
construção. Então u = hεi11 . . . hεinn para alguns n ≥ 0, i1 , . . . , in ∈ {1, . . . , m} e ε1 , . . . , εn ∈ {1, −1}.
É claro que hεi11 . . . hεinn ∈ L(F(H)) ⊆ L(S(H)). Como uma palavra da forma aa−1 só pode ser rótulo
de ciclos num autômato inverso, resulta que u = hεi11 . . . hεinn ∈ L(S(H)) e logo H ⊆ L(S(H)) ∩ RA .
Podemos finalmente provar o seguinte:
Corolário 4.4 (Stallings 1983) Dado H ≤f.g. FA , o autômato de Stallings S(H) não depende nem
da ordem em que as dobragens de arestas são feitas, nem do conjunto finito de geradores de H
escolhido.
Prova. Pelo Teorema 4.3(ii), L(S(H)) ∩ RA é independente destes dois fatores. Como S(H) é SFG
pelo Teorema 4.3(i), segue do Lema 4.2 que L(S(H))∩RA determina S(H) a menos de isomorfismo.
Observação 4.5 Por vezes, a construção de Stallings aparece definida de forma um pouco mais
geral, admitindo o uso de formas não reduzidas dos geradores na construção do autômato flor
F(H). Nesse caso, haveria que acrescentar uma terceira etapa à etapa das dobragens, eliminando
sucessivamente todos os vértices diferentes do ponto base que apresentem grau 1 (o grau de um
vértice de um autômato é o número de arestas que nele têm origem).
33
Exemplo 4.6 Construção do auômato de Stallings de H = haa−1 b2 , bacaa−1 c−1 bi partindo de
formas não reduzidas dos geradores:
O autômato flor é
/•
a
•
>•
`
a
b
•
/•
c
/•
b
a
/ q0 o
O
b
b
a
•
c
/•
a
/•
Depois de proceder a todas as dobragens, obtemos
•o
a
•O
•O
c
a
a
b
t
<•
3 q0 o
/
b
Eliminando sucessivamente todos os vértices diferentes de q0 que apresentem grau 1, obtemos
finalmente o autômato de Stallings
a
4.2
<•
t
b
3 q0 o
/
b
Aplicações
A primeira aplicação da construção de Stallings é a solução simples e elegante do chamado problema
da palavra generalizado. Para um grupo G, este problema consiste em encontrar um algoritmo que
decida, dados g ∈ G e H ≤f.g. G, se g ∈ H ou não. No caso particular H = {1}, permite decidir se
g = 1 e logo se g = g 0 para g, g 0 ∈ G (equivalente a g −1 g 0 = 1). Isto explica a terminologia.
Teorema 4.7 O problema da palavra generalizado é decidı́vel para FA .
Prova. Sejam g ∈ FA e H ≤f.g. FA . Temos L(S(H)) ∩ RA = H pelo Teorema 4.3(ii). Logo, para
determinar se g ∈ H, basta construir S(H) e testar se a palavra g é aceite pelo autômato. Exemplo 4.8 Podemos usar o autômato de Stallings construı́do no Exemplo 4.1 para verificar que
ba ∈ H = ha2 , ab−1 c, ci mas ab ∈
/ H.
Os autômatos de Stallings também permitem a construção de bases para subgrupos finitamente
gerados, como veremos em seguida.
Seja H ≤f.g. FA , e seja m o número de vértices de S(H). Uma árvore geradora T de S(H)
consiste em m−1 arestas e suas inversas que, juntas, conectam todos os vértices de S(H). Dado um
34
wp
vértice p de S(H), designamos por wp a T -geodésica conectando o ponto base q0 a p, isto é, q0 −→p
é o caminho mais curto contido em T ligando q0 a p. Note-se que esta T -geodésica é única, pois
caso contrário poderı́amos dispensar uma das m − 1 arestas e continuar ligando todos os vértices, o
que é manifestamente impossı́vel com m−2 arestas: se formos colocando as arestas sucessivamente,
cada uma ligando a alguma das anteriores, estamos introduzindo dois novos vértices da primeira
vez e depois um novo vértice de cada vez!
Teorema 4.9 Seja H ≤f.g. FA e seja T uma árvore geradora de S(H) = (Q, q0 , q0 , E). Seja
E+ = E ∩ (Q × A × Q). Então
Y = {wp awq−1 | (p, a, q) ∈ E+ \ T }
é uma base de H.
Prova. Note-se que como (p, a, q) ∈
/ T , temos Y ⊆ RA . Como Y ⊆ L(S(H)), resulta do Teorema
4.3(ii) que Y ⊆ H. Logo Y ⊆ H no grupo livre.
e Pelo Teorema 4.3(ii), existe um
Seja agora h = a1 · · · ak ∈ H em forma reduzida (ai ∈ A).
caminho bem-sucedido
ak
a1
a2
q0 −→q
1 −→ · · · −→qk = q0
em S(H). Para cada i = 1, . . . , k, ou wqi−1 ai wq−1
∈ Y ∪ Y −1 ou wqi−1 ai wq−1
= 1, esta última
i
i
possibilidade ocorrendo se (qi−1 , ai , qi ) ∈ T . Em qualquer caso, obtemos
−1
−1
h = a1 · · · ak = (wq0 a1 wq−1
1 )(wq1 a2 wq2 ) · · · (wqk−1 ak wq0 ) ∈ hY i
e logo H = hY i.
−1
Para mostrar que Y é uma base, sejam y1 , . . . , yk ∈ Y ∪ Y −1 com yi =
6 yi−1
para i = 2, . . . , k.
−1
e
Seja yi = wpi ai wri , onde ai ∈ A é o rótulo da aresta que não pertence a T . Resulta facilmente de
−1
yi 6= yi−1
e da definição de árvore geradora que
−1
y1 · · · yk = wp1 a1 wr−1
1 wp2 a2 · · · ak−1 wrk−1 wpk ak wrk ,
uma palavra reduzida não vazia se k ≥ 1. Logo Y é uma base de H. Como consequência imediata, obtemos:
Corolário 4.10 (Nielsen 1921) Todo subgrupo finitamente gerado de FA é livre.
Na realidade, todo subgrupo de um grupo livre é livre (Schreier 1926). A versão geral é conhecida
como o Teorema de Nielsen-Schreier.
Note-se que o Teorema 4.9 mostra também que todo autômato SFG é autômato de Stallings
de algum subgrupo finitamente gerado, pois a construção da base Y é válida para todo autômato
SFG. Observamos também que diferentes árvores geradoras produzem em geral bases distintas.
Exemplo 4.11 Usando o autômato de Stallings do Exemplo 4.1, podemos tomar como árvore geradora a aresta de rótulo b e sua inversa. Logo {ab−1 , ba, c} constitui uma base de H = ha2 , ab−1 c, ci.
35
Uma outra aplicação da construção de Stallings é a identificação de subgrupos de ı́ndice finito:
Teorema 4.12 Seja H ≤f.g. FA . Então as condições seguintes ão equivalentes:
(i) [FA : H] < ∞;
(ii) S(H) é um autômato completo.
Prova. (i) ⇒ (ii). Suponhamos que S(H) = (Q, q0 , q0 , E) não é completo. Então existem q ∈ Q e
u
e tais que (q, a, p) ∈
a∈A
/ E para todo p ∈ Q. Seja q0 −→q um caminho em S(H). Como S(H) é
inverso, podemos assumir que u ∈ RA . Vamos mostrar que
Huam 6= Huan
se
m − n > |u|.
(4)
De fato, Huam = Huan implica uam−n u−1 ∈ H e logo uam−n u−1 ∈ L(S(H)) pelo Teorema 4.3(ii).
Ora como S(H) é inverso temos ua ∈ RA . Como m − n > |u|, resulta que uaam−n−1 u−1 =
uam−n u−1 ∈ L(S(H)), pois u−1 não tem comprimento suficiente para apagar todos os a’s. Mas
então, como S(H) é determinı́stico, tem que existir uma aresta (q, a, p), contradição. Logo (4) é
válida e logo [FA : H] = ∞.
wq
(ii) ⇒ (i). Para cada q ∈ Q, fixamos uma geodésica q0 −→q (isto é, caminho de comprimento
g
mı́nimo). Seja g ∈ FA em forma reduzida. Como S(H) é completo, existe um caminho q0 −→q
para algum q ∈ Q. Logo gwq−1 ∈ H e portanto g = gwq−1 wq ∈ Hwq . Logo FA = ∪q∈Q (Hwq ) e
[FA : H] < ∞. Corolário 4.13 Seja H ≤f.g. FA com ı́ndice finito. Então [FA : H] é o número de vértices de
S(H).
Prova. Vimos na prova do Teorema 4.12 que FA = ∪q∈Q (Hwq ), logo basta mostrar que as classes
Hwq são todas distintas. Suponhamos que Hwp = Hwq para p, q ∈ Q. Então wp wq−1 ∈ H e logo
pelo Teorema 4.3(ii) existe um caminho
wp wq−1
q0 −−−→q0
em S(H), e logo um caminho
wp wq−1 wq
q0 −−−−−→q.
Como S(H) é inverso e wp wq−1 wq = wp (os rótulos das geodésicas são palavras reduzidas), obtemos
wp
um caminho q0 −→q. Logo p = q como pretendı́amos. Exemplo 4.14 Como o seu autômato de Stallings não é completo, o subgrupo H = ha−1 ba, ba2 i
não tem ı́ndice finito em F2 .
Corolário 4.15 Se H ≤f.g. FA tem ı́ndice n, então dim(H) = 1 + n(|A| − 1).
Prova. Pelo Teorema 4.12, o autômato S(H) tem n vértices e n|A| arestas positivas. Uma árvore
geradora tem n − 1 arestas positivas, logo dim(H) = n|A| − (n − 1) = 1 + n(|A| − 1) pelo Teorema
4.9. 36
Consideramos em seguida a relação de conjugação a nı́vel de subgrupos. Dois subgrupos H, K ≤
G dizem-se conjugados se H = gKg −1 para algum g ∈ G.
Seja H ≤f.g. FA e S(H) = (Q, q0 , q0 , E). Como S(H) é um autômato SFG, o ponto base q0 é o
único vértice que pode ter grau 1. Seja S0 (H) = (Q, E). Trata-se de um grafo orientado em que
e Se q0 tiver grau 6= 1, seja S1 (H) = S0 (H). Se q0 tiver grau 1, S1 (H)
as arestas têm rótulos em A.
é obtido a partir de S0 (H) eliminando sucessivamente todos os vértices de grau 1.
Teorema 4.16 Sejam H, K ≤f.g. FA . As condições seguintes são equivalentes:
(i) H e K são conjugados;
(ii) S1 (H) ∼
= S1 (K).
Prova. Vamos esboçar apenas a prova, apelando à intuição. É fácil compreender que S(H) tem
uma das duas formas seguintes:
• é S1 (H) com um ponto base designado;
u
• é obtido a partir de S1 (H) “colando” uma cauda q0 −→q (sendo a colagem feita identificando
q com um vértice de S1 (H)) e sendo q0 o ponto base.
Esta segunda opção só é possı́vel se S1 (H) tiver mais que um vértice.
Consideremos a igualdade K = g −1 Hg. Seja X um subconjunto gerador de H em forma
reduzida. Usando a versão mais geral da construção de Stallings referida na Observação 4.5,
poderı́amos construir S(K) usando o subconjunto gerador g −1 Xg. Aplicando as dobragens na
ordem conveniente, o processo de dobragens seria equivalente a colar a cauda
g −1
p0 −−→p
em S(H) (sendo a colagem feita identificando p com o ponto-base de S(H)), passando p0 a ser o
novo ponto base, e dobrando a cauda se for necessário. Haveria que aplicar em seguida a terceira
fase do algoritmo referida na Observação 4.5, o que pode conduzir a várias possibilidades, que
criam/alteram/suprimem a cauda e/ou alteram o ponto base (ilustradas no Exemplo 4.17), mas
que mantêm S1 (H) inalterado (a menos de isomorfismo).
Reciprocamente, S1 (H) ∼
= S1 (K) implica que S(H) e S(K) diferem apenas pela eventual
“cauda” e/ou ponto base, e podemos conjugar por um elemento adequado (ver Exemplo 4.17).
Exemplo 4.17 Seja H = hab2 ab−1 a−1 i ≤ F2 . Então:
O
O
q0
a
/•
b
/•h
b
(
•
q0
a
37
b
/•h
b
a
(
•
S(a−1 Ha)
S(H)
O
q0 o
O
a
•o
•o
a
b
a
•h
(
a
S(a−3 b−1 a−1 Haba3 )
b
b
•h
q0
a
S(b
a
•
a
O
) −2 −1
(
S(b−1 a−1 Hab)
O
•h
b
q0 i
•
a
(
•
/ q0
b
S(b−3 a−1 Hab3 )
2
Hab )
Podemos caraterizar facilmente os autômatos de Stallings dos subgrupos normais finitamente
gerados:
Corolário 4.18 Seja H ≤f.g. FA . Então H E FA se e só se verifica uma das condições seguintes:
(i) H = {1};
(ii) [FA : H] < ∞ e S1 (H) é transitivo nos vértices.
Prova. Podemos assumir que H 6= {1}. Ora H é normal se e só se S(gHg −1 ) ∼
= S(H) para
todo g ∈ FA . Isto não pode acontecer se existir a possibilidade de S(gHg −1 ) ter uma cauda.
Logo S(H) é completo e [FA : H] < ∞ pelo Teorema 4.12. Mas então, pelo Teorema 4.16, os
autômatos S(gHg −1 ) correspondem a todas as versões de S(H) com o ponto base alterado. Como
S(gHg −1 ) ∼
= S(H) se só se S1 (H) admite um automorfismo levando o ponto base q0 em q (onde
g −1
q0 −−→q
é um caminho em S(H)), isto é equivalente a dizer que S1 (H) é transitivo nos vértices. Vamos agora usar os autômatos de Stallings para dar uma prova simples do Teorema de Howson:
Teorema 4.19 (Howson 1954) Sejam H, K ≤f.g. FA . Então H ∩ K ≤f.g. FA .
Prova. O produto direto S(H)×S(K) reconhece L(S(H))∩L(S(H)) pela Proposição 2.6. Seja A a
componente conexa de S(H)×S(K) contendo o novo ponto base (isto é, removemos todos os vértices
e arestas que não estão ligados ao ponto base). Então temos também L(A) = L(S(H)) ∩ L(S(K)).
Se removermos de A eventuais vértices de grau 1 que não sejam o ponto base (ver Observação 4.5),
obtemos um autômato inverso SFG A0 . Vejamos que A0 ∼
= S(H ∩ K).
Pelo Lema 4.2 e pelo Teorema 4.3, basta mostrar que L(A0 )∩RA = H ∩ K. Como L(A0 )∩RA =
L(A) ∩ RA e H ∩ K = H ∩ K, isto equivale a mostrar que
L(S(H)) ∩ L(S(K)) ∩ RA = H ∩ K,
uma consequência imediata do Teorema 4.3(ii).
Logo S(H ∩ K) ∼
= A0 , sendo em particular finito. Daqui resulta que H ∩ K é finitamente gerado.
38
O Teorema de Howson está estreitamente ligado ao que foi durante muitos anos um dos mais
famosos problemas em aberto da teoria de grupos: a Conjetura de Hanna Neumann. Em 1957,
Hanna Neumann provou que
dim(H ∩ K) − 1 ≤ 2(dim(H) − 1)(dim(K) − 1)
para todos H, K ≤f.g. FA e conjeturou que o fator 2 podia ser removido da desigualdade. A
conjetura foi finalmente provada em 2011 por Friedman e Mineyev (de forma independente).
4.3
A métrica profinita
Há várias métricas de grande interesse que podem ser definidas em FA . Apresentaremos em seguida
a primeira delas, mas primeiro precisamos de provar que FA é residualmente finito. Um grupo G
diz-se residualmente finito se
∩{H ≤ G | [G : H] < ∞} = {1}.
Proposição 4.20 FA é residualmente finito.
e Consideremos o autômato inverso
Prova. Seja g ∈ FA \ {1}. Seja g = a1 . . . am com ai ∈ A.
o
/ q0
a1
/ q1
a2
/ . . . am / qm
É fácil verificar que podemos acrescentar arestas a este autômato para obter um autômato inverso
completo (e SFG), que será o autômato de Stallings de algum H ≤f.g. FA . Pelo Teorema 4.12, H
tem ı́ndice finito, e pelo Teorema 4.3(ii), g ∈
/ H. Logo g ∈
/ H e portanto FA é residualmente finito.
Vamos necessitar também do seguinte lema:
Lema 4.21 Sejam H, K ≤ G de ı́ndice finito. Então H ∩ K tem ı́ndice finito.
Prova. Suponhamos que G = Ha1 ∩ . . . Ham = Kb1 . . . Kbn . Então
G=
m [
n
[
(Hai ∩ Kbj ).
i=1 j=1
Basta-nos mostrar que
c ∈ Hai ∩ Kbj ⇒ Hai ∩ Kbj ⊆ (H ∩ K)c.
(5)
Com efeito,
(Hai ∩ Kbj )c−1 ⊆ Hai c−1 ⊆ Hai a−1
i H = H,
e analogamente (Hai ∩ Kbj )c−1 ⊆ K. Logo (Hai ∩ Kbj )c−1 ⊆ H ∩ K e (5) é válido como pretendı́amos. 39
Uma métrica (ou distância) num conjunto X é uma função d : X × X → R satisfazendo os
axiomas seguintes para todos x, y, z ∈ X:
(M1) d(x, y) ≥ 0;
(M2) d(x, y) = 0 ⇔ x = y;
(M3) d(x, y) = d(y, x);
(M4) d(x, z) ≤ d(x, y) + d(x, z).
A estrutura (X, d) diz-se então um espaço métrico. Se substituirmos o axioma (M4) pelo axioma
mais forte
(M4’) d(x, z) ≤ max {d(x, y), d(x, z)},
temos o que se chama de ultramétrica.
Definimos uma função d : FA × FA → R do seguinte modo. Sejam g, h ∈ FA . Se g = h, seja
d(g, h) = 0. Se g 6= h, seja d(g, h) = 2−k , onde k é o menor número de elementos de um grupo
finito F tal que gϕ 6= hϕ para algum homomorfismo ϕ : FA → F .
Lema 4.22 A função d é uma ultramétrica em FA .
Prova. Primeiro há que mostrar que d está bem definida. Suponhamos que g 6= h. Então gh−1 6= 1
e pela Proposição 4.20 existe H ≤ FA de ı́ndice finito tal que gh−1 ∈
/ H. Seja
\
K=
xHx−1 .
x∈G
Como xHx−1 = (xH)(Hx−1 ) = (Hx−1 )−1 (Hx−1 ) e [FA : H] < ∞, K é na realidade interseção de
um número finito de subgrupos da forma xHx−1 . Cada um deles tem naturalmente ı́ndice finito,
logo [FA : H] < ∞ pelo Lema 4.21.
É fácil confirmar que K é um subgrupo normal, logo FA /K é um grupo finito. Como gh−1 ∈
/H
−1
implica gh ∈
/ K, a projeção canónica FA → FA /K envia g e h em elementos distintos de FA /K.
Logo d está bem definida.
Os axiomas (M1) – (M3) são obviamente satisfeitos. Falta verificar (M4’). Sejam x, y, z ∈ FA .
Sem perda de generalidade, podemos assumir que os três elementos são distintos e que
max {d(x, y), d(y, z)} = 2−m .
Seja ϕ : FA → F um homomorfismo de grupos com |F | < m. Como |F | < d(x, y), temos xϕ = yϕ.
Analogamente, yϕ = zϕ. Logo xϕ = zϕ e d(x, z) ≤ 2−m . Logo (M4’) é válido e d é uma
ultramétrica. 40
A função d diz-se a métrica profinita.
Podemos provar agora o famoso Teorema de Marshall Hall:
Teorema 4.23 (Marshall Hall 1950) Seja H ≤f.g. FA . Então H é fechado para a métrica profinita.
Prova. Seja g ∈ FA \ H. Pelo Teorema 4.3(ii), g ∈
/ L(S(H)). Caso exista um caminho da forma
g
q0 −→ . . . em S(H), seja A = S(H). Caso contrário, A é o autômato inverso obtido acrescentando
g
vértices e arestas a S(H) de forma a que passe a existir um caminho q0 −→r (sendo r um novo
vértice). Agora, tal como na prova da Proposição 4.20, acrescentamos arestas a A até obter um
autômato inverso completo (e SFG), que será o autômato de Stallings de algum K ≤f.g. FA . Pelo
Teorema 4.12, K tem ı́ndice finito, e pelo Teorema 4.3(ii), g ∈
/ K. Logo g ∈
/ K. Seja
\
J=
xKx−1 .
x∈G
Tal como na prova do Lema 4.22, temos J E FA e [FA : J] < ∞. Seja π : FA → FA /J a projeção
canónica.
Suponhamos que gπ = hπ para algum h ∈ H. Então gh−1 ∈ J ⊆ K. Como H ⊆ K, resulta
que g ∈ Kh = K, contradição. Logo gπ 6= hπ e portanto d(g, h) ≥ 2−[FA :J] para todo h ∈ H.
Designando por Bε (g) a bola aberta de centro g e raio ε no espaço métrico (FA , d), resulta que
B2−[FA :J] (g) ⊆ FA \ H
e portanto FA \ H é um subconjunto aberto, donde H é um subconjunto fechado de FA . Exemplo 4.24 Consideramos a construção da prova do Teorema 4.23 para H = ha2 i ≤ F2 e
g = ab. Obtemos
o
S(H) :
o
)
q1
a
a
/ q0 i
A:
S(K) :
a
/ q0 i
)
q1
b
/r
b
(
a
a
)
/ q0 i
q1 i
M
a
b
o
a
rp
b
Logo K tem três conjugados, correspondendo a cada uma das três escolhas possı́veis para ponto
base. Utilizando a construção descrita na prova do Teorema 4.19, baseada no produto direto (ver
também a Proposição 2.6), acabamos obtendo
S(J) :
o
/ q0 o b
O
/•o a /•
O
a
•o
41
b
/•o
/•
a
b
4.4
Exercı́cios
(4.1) Para cada um dos seguintes subgrupos de F2 ,
H1 = ha2 b−1 a−2 , a2 b−2 a−2 i,
H2 = ha2 , a−1 baba2 i,
H3 = ha3 , ba2 , b−2 , babai,
H4 = ha3 , b3 , aba−1 , a(ba)2 , bab−1 , b−1 abi:
(a) Construa S(Hi ).
(b) Determine quais das palavras a2 b−1 a, a7 bab, a2 b99 a−2 , (ab)100 representam elementos de
Hi .
(c) Determine uma base de Hi .
(d) Calcule [FA : Hi ].
(4.2) Sejam H ≤f.g. FA e g ∈ FA . Mostre que é decidı́vel se xgx−1 ∈ H para algum x ∈ G.
(4.3) Sejam H = ha2 , aba, b2 , babi e K = ha2 , b, abai subgrupos de F2 .
(a) Construa os autômatos de Stallings de todos os subgrupos conjugados de H e K.
(b) Determine se H ou K é subgrupo normal de F2 .
(c) Construa S(H ∩ K).
(4.4) Seja H um subgrupo de ı́ndice finito de FA . Mostre que existe apenas um número finito de
K ≤ FA contendo H.
(4.5) Mostre que F2 possui apenas 3 subgrupos de ı́ndice 2.
(4.6) Mostre que o produto direto Zn = Z × . . . Z é residualmente finito.
(4.7) Seja H = haba−1 i ≤ F2 . Seguindo o algoritmo da prova do Teorema 4.24, construa J E F2 de
ı́ndice finito tal que H ≤ J e a2 ∈
/ J.
(4.8) Sejam g, g 0 , x ∈ FA e H ≤f.g. FA . Mostre que:
(a) d(xg, xg 0 ) = d(gx, g 0 x) = d(g, g 0 );
(b) Hg e gH são fechados em (FA , d).
42
5
Bordo de um grupo livre
Nesta seção estudamos uma segunda métrica do grupo livre que nos conduz a uma compactificação
famosa: o bordo, que pode ser descrito usando palavras infinitas.
5.1
Palavras infinitas
Uma palavra infinita no alfabeto A é uma sequência infinita de letras de A do tipo a1 a2 a3 . . ..
Designamos por Aω o conjunto de todas as palavras infinitas no alfabeto A e usamos também a
notação A∞ = A∗ ∪ Aω .
Podemos associar também palavras infinitas a um A-autômato A = (Q, I, T, E). Se (pi−1 , ai , pi ) ∈
E para todo i ≥ 1, temos definido um caminho infinito
a
a
a
1
2
3
p0 −→p
1 −→p2 −→ . . .
O seu rótulo é a palavra infinita a1 a2 a3 . . . ∈ Aω . Designamos por Lω (A) o conjunto dos rótulos
α
de todos os caminhos infinitos da forma I 3 q0 −→ . . . em A. Note-se que os estados terminais não
desempenham qualquer papel no cálculo de Lω (A)! Há outras formas de associar uma linguagem de
palavras infinitas a A (por exemplo, exigindo uma infinidade de passagens por um estado terminal
(Büchi)), mas não nos interessam no presente contexto.
Dada L ⊆ A+ , designamos por Lω o conjunto de todas as palavras infinitas da forma u1 u2 u3 . . .
(ui ∈ L). Em particular, se a ∈ A, aω designa a palavra infinita aaa . . .
Exemplo 5.1 Seja A o autômato
a
o
Então L(A) =
a∗
e Lω (A) =
aω
∪
c
/•
b
/•
a∗ bcω .
Não podemos concatenar duas palavras infinitas, mas podemos concatenar u = a1 . . . an e
α = b1 b2 b3 . . . (ai , bj ∈ A) por
uα = a1 . . . an b1 b2 b3 . . .
Dadas u ∈ A∗ e α ∈ Aω , dizemos que:
• u é um prefixo de α se α = uβ para alguma β ∈ Aω ;
• u é um fator de α se α = vuβ para algumas v ∈ A∗ e β ∈ Aω .
Se α = uβ, dizemos também que β é um sufixo de α.
Escreveremos u ≤ x para exprimir que u é prefixo de x ∈ A∞ . Designamos por x[n] o prefixo
de comprimento n de x (ou a própria x caso |x| < n).
43
5.2
A métrica dos prefixos e o espaço de Cantor
A métrica dos prefixos é definida em A∗ do seguinte modo. Dadas u, v ∈ A∗ , seja u ∧ v o mais longo
prefixo comum de u e v. Definimos
−|u∧v|
2
se u 6= v
0
d (u, v) =
0
se u = v
Exemplo 5.2 Sejam u = a3 b, v = a3 b3 e v = b2 . Então d0 (u, v) = 2−4 e d0 (u, w) = d0 (v, w) = 1.
Lema 5.3 A função d0 é uma ultramétrica em A∗ .
Prova. Os axiomas (M1) – (M3) são obviamente satisfeitos. Falta verificar (M4’) para u, v, w ∈ A∗ .
Sem perda de generalidade, podemos assumir que as três palavras são distintas, pelo que nos basta
mostrar que
|u ∧ w| ≥ min {|u ∧ v|, |v ∧ w|}.
Esta desigualdade é válida por transitividade, pois se u e v têm um prefixo comum de comprimento
m, e o mesmo se passa com v e w, então u e w vão ter também um prefixo comum de comprimento
m. É fácil ver que o espaço métrico (A∗ , d0 ) é discreto, isto é, todo ponto é aberto. Com efeito,
dada u ∈ A∗ , temos
B2−|u| (u) = {u} :
se v ∈ B2−|u| (u) \ {u}, então |u ∧ v| > |u|, absurdo. Isto quer dizer que (A∗ , d0 ) não é muito
interessante enquanto espaço métrico. Mas o seu completado vai ser!
Uma sucessão (xn )n num espaço métrico (X, d) dix-se de Cauchy se
∀ε > 0 ∃p ∈ N ∀m, n ≥ p d(xm , xn ) < ε.
A sucessão diz-se convergente para x ∈ X se
∀ε > 0 ∃p ∈ N ∀n ≥ p d(xn , x) < ε.
Dizemos então que x é o limite da sucessão (xn )n . Resultados bem conhecidos da topologia afirmam
que o limite de uma sucessão convergente é único e que toda sucessão convergente é de Cauchy. No
entanto, o recı́proco não é necessáriamente verdade: por exemplo, a sucessão ( n1 )n é de Cauchy em
]0, +∞[ (para a métrica usual) mas não é convergente. Um espaço métrico em que toda a sucessão
de Cauchy é convergente diz-se completo.
Suponhamos agora que (X, d) é um espaço métrico mas não é completo. Um outro resultado
de topologia afirma que podemos mergulhar (X, d) num espaço métrico completo (Y, d0 ) (com
d0 |X×X = d). Se escolhermos Y menor possı́vel (isto é, se todo elemento de Y for limite de alguma
sucessão em (X, d)), dizemos que (Y, d0 ) é o completado de (X, d). E um outro resultado de topologia
b
afirma que o completado é único a menos de homeomorfismo. É designado por X.
Por exemplo, para a métrica usual, R é o completado de Q.
A construção do completado é em geral técnicamente complicada, mas isso não acontece com
o completado de (A∗ , d0 ). Começamos por estender d0 a A∞ com a mesma definição (e a mesma
designação d0 !). É fácil ver que d0 é uma ultramétrica em A∞ . Mas há mais:
44
Teorema 5.4 (A∞ , d0 ) é o completado de (A∗ , d0 ).
Prova. Seja (αn )n uma sucessão de Cauchy em (A∞ , d0 ). Então
∀k ∈ N ∃pk ∈ N ∀m, n ≥ pk d0 (αm , αn ) < 2−k .
Logo
[k]
∀k ∈ N ∃pk ∈ N ∀m, n ≥ pk αm
= αn[k] .
(6)
Podemos assumir que a sucessão (pk )k é não decrescente. Daqui resulta facilmente que
αp[1]1 ≤ αp[2]2 ≤ αp[3]3 ≤ . . .
[k]
É claro que existe uma única palavra α ∈ A∞ tal que α[k] = αpk para todo k ∈ N: é finita se a
[k]
sucessão (αpk )k for estacionária e infinita caso contrário. Vejamos que α = limn→+∞ αn :
[k]
[k]
Seja ε > 0 e seja k ∈ N tal que 2−k < ε. Tomemos n ≥ pk . Por (6), temos αn = αpk . Por
[k]
[k]
outro lado, α[k] = αpk , logo αn = α[k] e portanto d0 (αn , α) ≤ 2−k < ε. Logo α = limn→+∞ αn e
portanto (A∞ , d0 ) é completo.
Como α = limn→+∞ α[n] para toda α ∈ Aω , (A∞ , d0 ) é o completado de (A∗ , d0 ). Um espaço métrico (X, d) é compacto se toda a sucessão em X admite uma subsucessão convergente. Há muitas outras definições equivalentes. Argumentos ditos de compacidade são usados
com grande eficácia em topologia e lógica, e por virtude destas duas disciplinas, na álgebra.
Teorema 5.5 (A∞ , d0 ) é compacto.
Prova. Seja (αn )n uma sucessão em (A∞ , d0 ). Se existir algum p ∈ N tal que {αn : |αn | ≤ p} seja
infinito, então há alguma palavra de comprimento ≤ p a repetir-se infinitamente na sucessão, o que
resolve imediatamente a questão. Por isso podemos assumir que {αn : |αn | ≤ p} é finito para todo
p ∈ N.
[1]
Como A é finito, existe algum a1 ∈ A tal que αn = a1 para uma infinidade de n. Mas então
[2]
existe algum a2 ∈ A tal que αn = a1 a2 para uma infinidade de n, existe algum a3 ∈ A tal que
[2]
αn = a1 a2 a3 para uma infinidade de n, e assim sucessivamente. Construimos assim uma palavra
infinita a1 a2 a3 . . . Consideremos agora a subsucessão (αin )n definida do seguinte modo: seja i1 o
[1]
[2]
primeiro ı́ndice n tal que αn = a1 , seja i2 o primeiro ı́ndice n > i1 tal que αn = a1 a2 , seja i3
[3]
o primeiro ı́ndice n > i3 tal que αn = a1 a2 a3 , e assim sucessivamente. É fácil verificar que a
subsucessão está bem definida e converge para a1 a2 a3 . . . ∈ Aω . Os espaços métricos (A∞ , d0 ) dizem-se espaços de Cantor. Quem já ouviu falar de conjunto de
Cantor pode ficar algo confuso... então o conjunto de Cantor C não é esse conjunto estranho que
se obtém removendo o terço interior ] 13 , 23 [ do intervalo [0, 1] e seguindo removendo o terço interior
de cada um dos pequenos intervalos que vão aparecendo, até ao infinito? Qual é a relação com
(A∞ , d0 )?
45
Há de fato uma relação, pois o conjunto de Cantor descrito acima, com a métrica usual herdada
de R, é homeomorfo a (A∞ , d0 ) se |A| = 2. Consideremos os números reais de [0, 1] escritos na
base 3. Cada número é uma dı́zima, finita ou infinita, composta pelos algarismos 0, 1, 2. Tal
como na base 10, há um pequeno problema de dupla representação. Por exemplo, as dı́zimas 0, 1
e 0, 0222 . . . representam o mesmo número real. Se for possı́vel, optaremos pela dı́zima que não
contenha 1. Se não for possı́vel, tanto faz... Tudo isto porque o conjunto de Cantor corresponde
precisamente a todas as dı́zimas que não contêm o algarismo 1: eliminar o terço interior de cada
intervalo corresponde sempre a eliminar as dı́zimas contendo 1! Logo existe uma bijeção entre C e
{0, 2}∞ . E pode verificar-se que é um homeomorfismo (ver o Exercı́cio 5.2).
5.3
Construção do bordo
Introduzimos agora uma segunda ultramétrica em FA : a métrica dos prefixos de FA é definida a
e∗ por
partir da métrica dos prefixos de A
d0 (g, h) = d0 (g, h)
(g, h ∈ FA ).
Resulta imediatamente do Lema 5.3 que
Lema 5.6 A função d0 é uma ultramétrica em FA .
Analogamente, o espaço métrico (FA , d0 ) é discreto, ao contrário do que acontece com a métrica
profinita d. Efetivamente, é fácil confirmar que
d(an! , 1) < 2−n
para todo n ∈ N: se ϕ : FA → F é um homomorfismo de grupos e |F | ≤ n, então (aϕ)|F | = 1
implica an! ϕ = (aϕ)n! = 1, logo precisamos no mı́nimo de |F | = n + 1 para separar 1 de an! . Logo
{1} não é aberto e (FA , d) não é discreto.
Qual é o completado de (FA , d0 )?
eω sem fatores do tipo aa−1 (a ∈ A)
e diz-se uma palavra infinita reduzida.
Uma palavra α ∈ A
Designamos por ∂FA o conjunto de todas as palavras infinitas reduzidas. Estendemos a ultramétrica
cA = FA ∪ ∂FA da forma óbvia, adaptando o que fizemos para A∞ . Os mesmos
d0 : FA × FA → R a F
argumentos permitem mostrar que:
cA , d0 ) é o completado de (FA , d0 ).
Teorema 5.7 (F
cA , d0 ) é compacto.
Teorema 5.8 (F
O espaço ∂FA diz-se o bordo de FA . Muitas vezes, o bordo é pensado geometricamente como
o conjunto dos raios do grafo de Cayley ΓA (FA ) com origem num determinado vértice. Um raio é
uma geodésica infinita, isto é, um caminho infinito em que cada secção finita é uma geodésica.
Dado um subconjunto Y de um espaço métrico X, designamos por Fec(Y ) o fecho de Y , que
pode ser definido como o menor fechado contendo Y , ou o conjunto dos pontos de X que são limite
de sucessões em Y .
O resultado seguinte mostra que os autômatos de Stallings podem desempenhar também um
papel em relação ao bordo.
46
cA . Então
Proposição 5.9 Seja H ≤f.g. FA e seja Fec(H) o fecho de H em F
Fec(H) = H ∪ (Lω (S(H)) ∩ ∂FA ).
Prova. Como (FA , d0 ) é discreto, temos Fec(H) ∩ FA = H. Seja α ∈ ∂FA . Temos que provar que
α ∈ Fec(H) ⇔ α ∈ Lω (S(H)).
(7)
Suponhamos que α ∈ Fec(H). Então α = limn→+∞ hn para alguma sucessão (hn )n em H.
e tais
Suponhamos que α ∈
/ Lω (S(H)). Então podemos fatorizar α = uaβ com u ∈ A∗ e a ∈ A
u
a
que q0 −→q é um caminho em S(H) mas não existe nenhuma aresta da forma q −→ . . .. Como
α = limn→+∞ hn , existe p ∈ N tal que d0 (hn , α) < 2−|u| para todo n ≥ p. Mas então |α ∧ hp | > |u|,
a
logo ua ≤ hp . Pelo Teorema 4.3(ii), isto implica a existência de uma aresta q −→ . . . em S(H),
contradição. Logo α ∈ Lω (S(H)).
e Seja m o número de vértices de
Reciprocamente, seja α = a1 a2 a3 · · · ∈ Lω (S(H)), com ai ∈ A.
S(H). Para cada n ≥ 1, existe alguma palavra wn ∈ RA de comprimento < m tal que a1 · · · an wn ∈
L(S(H)). Logo a1 · · · an wn ∈ L(S(H)) ∩ RA = H pelo Teorema 4.3(ii), e portanto a1 · · · an wn ∈ H.
Como |wn | < m, temos |a1 · · · an wn ∧ α| ≥ n − m para todo n ∈ N, logo resulta facilmente que
α = limn→+∞ a1 · · · an wn e α ∈ Fec(H). Logo (7) é válido como pretendı́amos. 5.4
Exercı́cios
(5.1) Seja A o autômato descrito por
b
a
/•j
* •
/
c
Calcule L(A) e Lω (A).
(5.2) Seja A = {0, 2} e seja ϕ : A∞ → C a bijeção definida no final da Subsecção 5.2. Mostre que:
(a) 3−|α∧β|−1 ≤ |αϕ − βϕ| ≤ 3−|α∧β| para todas α, β ∈ A∞ distintas;
(b) ϕ é um homeomeorfismo (para a métrica d0 em A∞ e a métrica usual em C).
cA , d0 ),
(5.3) No espaço métrico (F
(a) calcule d0 (abaω , aba−1 b−1 );
(b) determine B 1 (abaω ).
4
cA , d0 ):
(5.4) Calcule os seguintes limites em (F
(a) limn→+∞ an b2n ;
(b) limn→+∞ (ab2 a−1 )n .
47
(5.5) Calcule Fec(H) para cada um dos seguintes subgrupos de F2 :
(a) H = ha, bab−1 i;
(b) H = ha, b2 , bab−1 i.
(5.6) Seja H ≤f.g. FA e g ∈ G. Mostre que, para a métrica d0 ,
Fec(Hg) = Hg ∪ (Lω (S(H)) ∩ ∂FA ).
48
6
Pontos fixos de endomorfismos
Nesta secção usamos os autômatos para estudar os pontos fixos de um endomorfismo de FA .
6.1
O subgrupo dos pontos fixos
Um endomorfismo de um grupo G é um homomorfismo ϕ : G → G. Dizemos que g ∈ G é um ponto
fixo de ϕ se gϕ = g. É imediato que o conjunto dos pontos fixos de ϕ constitui um subgrupo de G,
que designaremos por Fix(ϕ).
Quando definimos um subgrupo através de uma propriedade, a primeira questão que se põe
é saber se ele é finitamente gerado ou não, pois nesse caso podemos ambicionar a construção do
respetivo autômato de Stallings, com todas as vantagens que lhe estão inerentes. Vamos ver que
esse é o caso dos endomorfismos de um grupo livre:
Teorema 6.1 (Goldstein e Turner 1986) Seja ϕ um endomorfismo de FA . Então Fix(ϕ) é finitamente gerado.
Prova. Para todo g ∈ FA , seja pg = g −1 (gϕ) ∈ FA . Note-se que 1 = p1 e g ∈ Fix(ϕ) se e só se
e
pg = 1. Definimos um A-autômato
A = (P, 1, 1, E) por
P = {pg | g ∈ FA };
e
E = {(pg , a, pga ) | g ∈ FA , a ∈ A}.
Provamos em seguida uma série de lemas intermédios que nos ajudarão a demonstrar o teorema:
Lema 6.2 A é um autômato inverso e L(A) = (Fix(ϕ))θ−1 .
e Como pgaa−1 = pg , resulta que
Prova. É imediato que A é determinı́stico. Sejam g ∈ FA e a ∈ A.
−1
(pga , a , pg ) é também uma aresta de A, logo A é involutivo.
u
e∗ , com ai ∈ A,
e existe um caminho (único) do tipo 1−→
Dado u = a1 . . . an ∈ A
. . ., a saber:
a
a
a
a
1
2
3
n
1 = p1 −→p
a1 θ −→p(a1 a2 )θ −→ . . . −→puθ .
g
g −1
Logo, para todo g ∈ FA , existe um caminho bem-sucedido 1−→pg −−→1 e A é aparado.
Finalmente,
u ∈ L(A) ⇔ puθ = 1 ⇔ uθ ∈ Fix(ϕ) ⇔ u ∈ (Fix(ϕ))θ−1 .
No entanto, o autômato A é infinito caso ϕ 6= 1FA : se aϕ 6= a para algum a ∈ A, então é fácil
ver que ak ϕ 6= ak para todo k ∈ N (usando o Lema 3.6), donde resulta que os vértices pak são todos
distintos. Como proceder? A estratégia é apontada pelo seguinte lema:
Lema 6.3 Se A possuir um subautômato finito A0 tal que Fix(ϕ) ⊆ L(A0 ), então Fix(ϕ) é finitamente gerado.
49
Prova. Se Fix(ϕ) ⊆ L(A0 ), então Fix(ϕ) ⊆ L(A0 ) ⊆ L(A). Pelo Lema 6.2, temos
L(A) = (Fix(ϕ))θ−1 = Fix(ϕ),
logo Fix(ϕ) ⊆ L(A0 ) ⊆ Fix(ϕ) e portanto L(A0 ) = Fix(ϕ). Daqui resulta que Fix(ϕ) = (L(A0 ))θ.
e
Como A0 é finito, L(A0 ) é uma A-linguagem
racional, e logo Fix(ϕ) é um subconjunto racional
de FA pela Proposição 3.13. Logo Fix(ϕ) é finitamente gerado pelo Teorema 3.14. Seja
hϕ = max {|aϕ| : a ∈ A}
e fixemos
P 0 = {pg ∈ P : |pg | ≤ 2hϕ + 1}.
Como A é finito, P 0 também o é. No entanto, pode haver uma infinidade de elementos g ∈ FA a
dar origem ao mesmo vértice pg .
Dado g ∈ FA , seja gι = g [1] . Por outras palavras, gι é a primeira letra de g caso g 6= 1, e é igual
a 1 caso contrário. Dizemos que uma aresta (q, a, q 0 ) ∈ E é:
• central se q, q 0 ∈ P 0 ;
• compatı́vel se não for central e qι = a.
O próximo lema recolhe algumas propriedades elementares envolvendo estes conceitos:
Lema 6.4
(i) Só existe um número finito de arestas centrais em A.
(ii) Se (q, a, q 0 ) ∈ E é não central, então (q, a, q 0 ) ou (q 0 , a−1 , q) é compatı́vel.
(iii) Para cada q ∈ P , existe no máximo uma aresta compatı́vel com origem em q.
Prova. (i) Porque A e P 0 são ambos finitos.
(ii) Suponhamos que (q, a, q 0 ) não é nem central nem compatı́vel. Então podemos escrever
e \ {a}. Suponhamos que |q| ≤ hϕ . Então |q 0 | = |a−1 q(aϕ)| ≤ 2hϕ + 1 e (q, a, q 0 ) seria
qι = b ∈ A
central, absurdo. Logo |q| > hϕ .
Escrevendo q = bg, obtemos q 0 = a−1 q(aϕ) = a−1 bg(aϕ). Como b 6= a e |g| ≥ hϕ , obtemos
q 0 = a−1 bg(aϕ). Logo q 0 ι = a−1 e (q 0 , a−1 , q) é compatı́vel.
(iii) Porque uma aresta compatı́vel com origem em q tem necessariamente rótulo qι, e A é
determinı́stico. a
a
1
2
Um caminho (possivelmente infinito) q0 −→q
1 −→ . . . em A diz-se:
• central se todos os seus vértices estiverem em P 0 ;
• compatı́vel se todas as suas arestas forem compatı́veis e nenhum vértice intermédio pertencer
a P 0.
50
Lema 6.5 Seja u ∈ Fix(ϕ). Então existe em A um caminho
u
w−1
v
u
v
v
w−1
u
1
n
0
n
0 1 00 2
00 1
0 n 00
1 = q00 −→q
0 −→q1 −→q1 −→q1 −→ . . . −→qn −→qn −→qn = 1
(8)
tal que:
(i) u = u0 v1 w1−1 u1 . . . vn wn−1 un ;
uj
(ii) os caminhos qj0 −→qj00 são centrais;
vj
wj
00 −→q e q 0 −→q são compatı́veis;
(iii) os caminhos qj−1
j
j
j
(iv) qj ∈
/ P 0 se vj e wj forem ambas 6= 1.
Prova. Como 1 ∈ P 0 e u ∈ L(A) pelo Lema 6.2, existe um caminho
u
x
u
x
x
u
0
n
00 1 0 1 00 2
0 n 00
1 = q00 −→q
0 −→q1 −→q1 −→ . . . −→qn −→qn = 1
uj
em A tal que u = u0 x1 u1 . . . xn un e os caminhos qj0 −→qj00 (que podem ser triviais!) recolhem todas
as ocorrências de vértices em P 0 (sendo consequentemente caminhos centrais).
xj 0
00 −→q
Pelo Lema 6.4(ii), se uma aresta (r, a, s) ocorre num caminho qj−1
j , então (r, a, s) ou
xj 0
−1
00 −→q
(s, a , r) é compatı́vel. Por outro lado, como xj é reduzida, resulta do Lema 6.4(iii) que qj−1
j
se pode fatorizar como
−1
w
vj
j
00
qj−1
−→qj −→qj0
vj
wj
00 −→q e q 0 −→q compatı́veis. Note-se que a condiç ao (iv) é válida porque nenhum vértice
com qj−1
j
j
j x
j
00 −→q
0
0
intermédio de qj−1
j pode pertencer a P . a
a
1
2
Dizemos que um caminho compatı́vel q0 −→q
1 −→ . . . é maximal se for infinito ou não puder ser
prolongado (à direita) continuando compatı́vel.
Lema 6.6 Para cada q ∈ P 0 , existe em A um único caminho compatı́vel maximal Mq com origem
em q.
Prova. É claro que qualquer caminho compatı́vel pode ser estendido a um caminho compatı́vel
maximal. A unicidade resulta do Lemma 6.4(iii). Definimos agora
P10 = {q ∈ P 0 | Mq só tem um número finito de arestas distintas}
e P20 = P 0 \ P10 . Logo Mq não contém ciclos se q ∈ P20 . Pelo Lema 6.6, se os caminhos Mq e Mq0 se
intersetarem num vértice rqq0 , então eles vão coincidir a partir de rqq0 . Em particular, se Mq e Mp0
se intersetarem, então q ∈ P10 se e só se q 0 ∈ P10 . Seja
Y = {(q, q 0 ) ∈ P20 × P20 | Mq interseta Mq0 }.
Para cada (q, q 0 ) ∈ Y , seja Mq \ Mq0 o subcaminho (finito) q−→rqq0 de Mq . Note-se que se q 0 = q,
então Mq \ Mq0 é o caminho trivial no vértice q.
Seja A0 o subautômato de A contendo:
51
• todos os vértices em P 0 e todas as arestas centrais;
• todos os vértices e arestas nos caminhos Mq (q ∈ P10 ) e as respetivas arestas inversas;
• todos os vértices e arestas nos caminhos Mq \Mq0 ((q, q 0 ) ∈ Y ) e as respetivas arestas inversas.
Segue facilmente do Lema 6.4(i) e das definições de P10 e Mq \ Mq0 que A0 é um subautômato finito
de A. Pelo Lema 6.3, basta mostrar que Fix(ϕ) ⊆ L(A0 ).
Seja u ∈ Fix(ϕ). Consideremos o caminho fatorizado (8) fornecido pelo Lema 6.5. Como A0
contém todas as arestas centrais de A, basta mostrar que todos os subcaminhos
vj
wj−1
00
qj−1
−→qj −→qj0
aparecendo em (8) são caminhos em A0 .
00
Se perda de generalidade, podemos assumir que vj 6= 1. Se wj = 1, então qj−1
∈ P10 e temos o
00
, logo podemos assumir que wj 6= 1 também. Se um
pretendido pois A0 contém o caminho Mqj−1
00 , q 0 estiver em P 0 , o outro também está e de novo obtemos o pretendido. Logo
dos vértices qj−1
1
j
00 , q 0 ∈ P 0 .
podemos assumir que qj−1
2
j
−1
00 ,q 0 : como vj w
00
Daqui resulta que qj = rqj−1
∈ RA , é fácil ver que os caminhos Mqj−1
e Mqj0
j
j
wj
vj
0
00
0
00
não se podem encontrar antes de pj . Logo qj−1 −→qj é precisamente Mqj−1 \ Mqj e qj −→qj é
00
precisamente Mqj0 \ Mqj−1
. Portanto são ambos caminhos em A0 como necessitávamos. Em geral, o problema de construir efetivamente S(Fix(ϕ)) (equivalente a calcular uma base para
Fix(ϕ)) é muito difı́cil, mesmo para automorfismos de FA . Maslakova publicou uma prova para
automorfismos em 2003, que se descobriu mais tarde conter erros. Recentemente, foram anunciados
resultados que cobrem o caso de todos os endomorfismos de FA , mas estão ainda sendo verificados.
O exemplo seguinte mostra um caso em que é fácil calcular todos os pontos fixos:
Exemplo 6.7 Seja ϕ o automorfismo de F2 definido por aϕ = aba−1 e bϕ = a. Então Fix(ϕ) =
habi.
Antes de proceder ao cálculo, confirmamos que ϕ é um automorfismo tomando o endomorfismo
ψ de F2 definido por aψ = b e bψ = b−1 ab. Como ϕψ = ψϕ = 1, então ϕ e ψ são automorfismos.
É imediato que (ab)ϕ = aba−1 a = ab, logo ab ∈ Fix(ϕ) e habi ⊆ Fix(ϕ). Reciprocamente, seja
u ∈ Fix(ϕ), digamos
u = an0 bm1 an1 bm2 an2 . . . bmk−1 ank−1 bmk ank
com k ≥ 0, m1 , . . . , mk , n1 , . . . , nk−1 6= 0. Se k = 0, então u = 1, logo podemos assumir que k > 0
e escrever
uϕ = (abn0 a−1 )am1 (abn1 a−1 )am2 (abn2 a−1 ) . . . amk−1 (abnk−1 a−1 )amk (abnk a−1 )
= (abn0 a−1 )am1 +1 bn1 am2 bn2 . . . amk−1 bnk−1 amk −1 (abnk a−1 ).
Comparando as séries de b’s em u = uϕ, concluimos que n0 6= 0 = nk ou n0 = 0 6= nk .
52
Suponhamos que n0 6= 0 = nk . Então u = uϕ traduz-se por
an0 bm1 an1 bm2 an2 . . . bmk−1 ank−1 bmk = abn0 am1 bn1 am2 bn2 . . . amk−1 bnk−1 amk −1 ,
logo obtemos sucessivamente
1 = n0 = m1 = n1 = . . . = mk−1 = nk−1 = mk
e u = (ab)k ∈ habi.
Caso n0 = 0 6= nk , podemos substituir u por u−1 e usar o caso anterior. Logo Fix(ϕ) = habi.
6.2
Pontos fixos no bordo
Vamos agora apresentar alguns resultados sobre pontos fixos no bordo, sem demonstração.
Como (FA , d0 ) é um espaço métrico discreto, toda função de domı́nio FA é contı́nua. Mas há
uma versão mais forte da continuidade que é ainda mais útil, em que as constantes na condição de
continuidade não dependem do ponto considerado. Mais precisamente, uma função ϕ : (X, d) →
(X 0 , d0 ) entre espaços métricos diz-se uniformemente contı́nua se:
∀ε > 0 ∃δ > 0 ∀x, y ∈ X (d(x, y) < δ ⇒ d(xϕ, yϕ) < ε).
A grande vantagem é que se ϕ for uniformente contı́nua, existe uma (única) extensão contı́nua
b → Yb de ϕ aos completados de X e Y . A extensão é definida por
Φ:X
αΦ = lim (xn ϕ),
n→+∞
onde (xn )n é uma sucessão de X que converge para α.
Nem todos os endomorfismos de FA são uniformente contı́nuos, mas os endomorfismos injetivos
têm essa propriedade. Logo todo o endomorfismo injetivo ϕ de FA admite uma única extensão
cA → F
cA (e por restrição, ao bordo ∂FA ). Os pontos fixos α ∈ Fix(Φ) ∩ ∂FA dizem-se
contı́nua Φ : F
os pontos fixos infinitos de φ.
Exemplo 6.8 Seja ϕ o endomorfismo de F2 definido por aϕ = aba−1 e bϕ = a2 . Então Fix(ϕ) =
n
n
{1} mas α = aba2 b2 a4 b4 . . . a2 b2 . . . ∈ Fix(Φ).
Procedendo analogamente ao Exemplo 6.7, mostramos que Fix(ϕ) = {1}.
i
i
Para todo n ∈ N, seja un = Πni=0 a2 b2 . É claro que α = limn→+∞ un , logo uΦ = limn→+∞ (un ϕ).
Temos
i
i
i
i
i
i+1
i
i+1
(a2 b2 )ϕ = (aba−1 )2 (a2 )2 = (ab2 a−1 )a2 = ab2 a2 −1 ,
logo
un ϕ =
n
Y
i=0
Como un
n+1
a2 −1
i
ab2 a2
i+1 −1
n
n
Y
Y
i
i+1
i
n+1
n+1
= a( b2 a2 )a−1 = ( a2i b2 )a2 −1 = un a2 −1 .
i=0
i=0
∈ RA , resulta facilmente que
n+1 −1
αΦ = lim (un ϕ) = lim un a2
n→+∞
n→+∞
53
= α,
logo α é um ponto fixo infinito de ϕ.
Que se pode dizer sobre os pontos fixos infinitos de ϕ? É fácil ver que Fec(Fix(ϕ)) ⊆ Fix(Φ):
se α = limn→+∞ (xn ϕ) para alguma sucessão em Fix(ϕ), então
αΦ = lim (xn ϕ) = lim xn = α.
n→+∞
n→+∞
Tais pontos fixos infinitos dizem-se singulares. Os restantes dizem-se regulares. Seja Fixr (ϕ) o
conjunto dos pontos fixos infinitos regulares de ϕ. O resultado seguinte mostra que Fixr (ϕ) é num
certo sentido finitamente gerado:
Teorema 6.9 (Silva 2010) Seja ϕ um endomorfismo injetivo de FA . Então existem α1 , . . . , αm ∈
Fixr (ϕ) tais que
Fixr (ϕ) = Fix(ϕ)α1 ∪ . . . ∪ Fix(ϕ)αm .
Este resultado foi provado para automorfismos por Cooper em 1987.
cA ), é também possı́vel proceder à
Se ϕ for um automorfismo de FA (com extensão contı́nua Φ a F
classificação dos pontos fixos infinitos regulares do ponto de vista da teoria dos sistemas dinâmicos.
Dizemos que α ∈ Fixr (ϕ) é um:
• atrator se
cA (d0 (α, β) < ε ⇒ lim (βΦn ) = α);
∃ε > 0 ∀β ∈ F
n→+∞
• repulsor se for um atrator para ϕ−1 .
Noutros sistemas dinâmicos, podem existir outros tipos (hiperbólico, degenerado), mas não no
nosso caso:
Teorema 6.10 (Gaboriau, Jaeger, Levitt e Lustig 1998) Seja ϕ um automorfismo de FA . Então
todo α ∈ Fixr (ϕ) é atrator ou repulsor.
6.3
Exercı́cios
(6.1) Seja ϕ o endomorfismo de F2 definido por aϕ = aba−1 e bϕ = a−1 . Determine os pontos fixos
de ϕ de comprimento < 3.
(6.2) Seja ϕ o endomorfismo de F2 definido por aϕ = ab2 e bϕ = b−1 .
(a) Mostre que {ab, b} é uma base alternativa de FA .
(b) Usando a base alternativa, calcule Fix(ϕ).
(6.3) Seja ϕ um endomorfismo injetivo de FA com Fix(ϕ) = {1}. Mostre que Fix(Φ) é finito.
(6.4) Seja ϕ o endomorfismo de F2 definido por aϕ = a2 e bϕ = b2 .
(a) Mostre que ϕ é injetivo.
54
(b) Calcule Fix(Φ).
(c) Mostre que os pontos fixos infinitos de ϕ são todos atratores.
(6.5) Seja ϕ o endomorfismo de F2 definido por aϕ = ab e bϕ = ba (endomorfismo de Thue-Morse).
Mostre que:
(a) ϕ é injetivo;
(b) Fix(ϕ) = {1};
(c) limn→∞ aϕn ∈ Fixr (ϕ).
(6.6) Dado um endomorfismo ϕ de FA , dizemos que h ∈ FA é um ponto periódico se hϕn = h para
algum n ≥ 1. Seja A = {a, b, c, d} e seja ϕ o endomorfismo de FA definido por
aϕ = b,
bϕ = a,
cϕ = c2 ,
Calcule o conjunto dos pontos periódicos de ϕ.
55
dϕ = d2 .
7
Apresentações de grupos
Nesta secção deixamos para trás o grupo livre e procuramos ferramentas para lidar com grupos
mais gerais.
7.1
Geradores e relatores
Dado um grupo G, sabemos pelo Teorema 3.4 que G é isomorfo a algum quociente de um grupo
livre FA . Isto equivale a dizer que existe um homomorfismo sobrejetivo ϕ : FA → G. Pelo Teorema
1.5, temos Ker(ϕ) E FA e G ∼
= FA /Ker(ϕ), logo G é determinado por A e Ker(ϕ), a menos de
isomorfismo.
Como Aϕ gera G, dizemos por extensão que A é um conjunto de geradores de G. Quanto a
Ker(ϕ), qual a forma mais simples de descrevê-lo?
Na Subsecção 1.4, definimos subgrupo gerado por um subconjunto. De forma análoga, dado um
subconjunto X de um grupo G, definimos o subgrupo normal gerado por X como sendo o conjunto
dos elementos da forma
εn −1
(a1 xε11 a−1
1 ) . . . (an xn an ),
onde n ≥ 0, ai ∈ G, xi ∈ X e εi ∈ {1, −1} para i = 1, . . . , n. É fácil verificar que este é efetivamente
o menor subgrupo normal de G contendo X, sendo representado por hhXii.
Voltando à representação de G ∼
= FA /Ker(ϕ), podemos então descrever Ker(ϕ) através de um
subconjunto R tal que Ker(ϕ) = hhRii. A vantagem é que R pode ser muito mais pequeno e fácil
de descrever que Ker(ϕ)! Dizemos que um tal R é um conjunto de relatores de G, e a expressão
formal hA | Ri diz-se uma apresentação de G.
Inversamente, podemos começar com um conjunto A e um subconjunto R ⊆ FA quaisquer.
Então hA | Ri constitui uma apresentação de FA /hhRii, bem como de qualquer grupo que lhe seja
isomorfo.
7.2
Grupos finitamente apresentáveis
Uma apresentação hA | Ri diz-se finita se A e R forem ambos finitos. Um grupo diz-se finitamente
apresentável se admitir uma apresentação finita.
As apresentações mais simples são as da forma hA | ∅i, que definem os grupos livres FA . O
exemplo seguinte envolve uma apresentação com um único relator. Introduzimos a notação [g, h] =
ghg −1 h−1 para quaisquer elementos g, h ∈ G. Um elemento desta forma diz-se um comutador de
G.
Exemplo 7.1 ha, b | [a, b]i é uma apresentação de Z × Z.
Para mostrar isto, definimos um homomorfismo ϕ : F2 → Z × Z por aϕ = (1, 0) e bϕ = (0, 1). É
claro que ϕ é sobrejetivo e [a, b] ∈ Ker(ϕ). Seja N = hh[a, b]ii. Então N ⊆ Ker(ϕ) e pelo Teorema
1.5 ϕ induz um homomorfismo (sobrejetivo) Φ : F2 /N → Z × Z definido por (aN )Φ = (1, 0) e
(bN )Φ = (0, 1).
56
Por outro lado, definimos Ψ : Z × Z → F2 /N por (m, n)Ψ = am bn N . Como abN = baN ,
resulta facilmente que am bn N = bn am N para todos m, n ∈ Z, e daqui se conclui que Ψ é um
homomorfismo. Como (xN )ΦΨ = xN para x ∈ {a, b} e F2 /N é gerado por aN, bN , resulta que
ΦΨ = 1F2 /N e logo Φ é injetivo. Logo Φ é um isomorfismo e ha, b | [a, b]i é uma apresentação de
Z × Z.
Vejamos em seguida que todos os grupos finitos são finitamente apresentáveis:
Proposição 7.2 Todo grupo finito é finitamente apresentável.
Prova. Seja G um grupo finito. Seja A = {ag | g ∈ G} um alfabeto em bijeção com G e seja
R = {ag ah a−1
gh | g, h ∈ G}.
Vamos mostrar que hA | Ri é uma apresentação de G.
Seja ϕ : FA → G o homomorfismo sobrejetivo definido por ag ϕ = g e seja N = hhRii. Como
R ⊆ Ker(ϕ), resulta do Teorema 1.5 que ϕ induz um homomorfismo (sobrejetivo) Φ : FA /N → G
definido por (ag N )Φ = g.
−1
2
Como a1 a1 a−1
1 ∈ R, obtemos a1 N = a1 N e logo a1 N = N . Por outro lado, como ag ag −1 a1 ∈ R,
−1
obtemos a−1
g N = (ag −1 N )(a1 N ) = ag −1 N . Junto com as relações ag ah N = agh N e a1 N = N ,
isto implica que todo elemento de FA /N se pode escrever na forma ag N para algum g ∈ G. Logo
|FA /N | ≤ |A| = |G|. Como Φ é sobrejetivo, resulta que |FA /N | = |G| e logo Φ é um isomorfismo.
Mostramos em seguida que a existência de uma apresentação finita é independente do conjunto
(finito) de geradores considerado:
Proposição 7.3 Seja G um grupo finitamente apresentável e seja ψ : FB → G um homomorfismo
sobrejetivo de grupos com B finito. Então G admite uma apresentação finita da forma hB | Si.
Prova. Seja hA | Ri uma apresentação finita de G, e seja ϕ : FA → G o correspondente homomorfismo sobrejetivo. Podemos definir um homomorfismo α : FA → FB tal que o diagrama
FA
α
ϕ
/G
>
ψ
FB
comuta: basta escolher aα ∈ aϕψ −1 para todo a ∈ A e usar a propriedade universal. Analogamente,
57
existe um homomorfismo β : FB → FA tal que o diagrama
FOA
ϕ
β
/G
>
ψ
FB
comuta.
Seja
S = Rα ∪ {b−1 (bβα) | b ∈ B}
e N = hhSii. Como bN = (bβα)N para todo b ∈ B, resulta facilmente que
uN = (uβα)N para todo u ∈ FB .
(9)
É fácil verificar que S ⊆ Ker(ψ), logo N ⊆ Ker(ψ). Reciprocamente, seja u ∈ Ker(ψ). Como
uβϕ = uψ = 1 e Kerϕ = hhRii, obtemos
uβα ∈ hhRiiα ⊆ hhRαii ⊆ N.
Aplicando (9), resulta que u ∈ N e logo Ker(ψ) ⊆ N . Logo Ker(ψ) = N = hhSii e hB | Si é uma
apresentação finita de G. 7.3
Decidibilidade
O problema da palavra ganha generalidade no contexto as apresentações: dizemos que a apresentação hA | Ri tem problema da palavra decidı́vel se existir um algoritmo que determine se um
elemento arbitrário de FA pertence a N = hhRii. Como uN = vN se e só se u−1 v ∈ N , isto equivale
a poder determinar quando dois elementos de FA representam o mesmo elemento de FA /N .
Tal como na Proposição 7.3, a decidibilidade do problema da palavra não depende da apresentação considerada para o grupo:
Proposição 7.4 Sejam hA | Ri e hB | Si apresentações finitas de um grupo G. Então hA | Ri tem
problema da palavra decidı́vel se e só se hB | Si tem problema da palavra decidı́vel.
Prova. Suponhamos que hA | Ri tem problema da palavra decidı́vel. Tal como na prova da
Proposição 7.3, consideramos o diagrama comutativo
FOA
β
ϕ
/G
>
ψ
FB
58
onde ϕ e ψ são sobrejetivos, Ker(ϕ) = hhRii e Ker(ψ) = hhSii. Dado u ∈ FB , temos
u ∈ hhSii ⇔ uψ = 1 ⇔ uβϕ = 1 ⇔ uβ ∈ hhRii.
Como podemos decidir se uβ ∈ hhRii, então hB | Si tem problema da palavra decidı́vel. Por
simetria, obtemos o resultado. Graças à Proposição 7.4, podemos dizer que um grupo finitamente apresentável tem problema
da palavra decidı́vel ou indecidı́vel sem especificarmos a apresentação (finita).
O resultado seguinte foi demonstrado de forma independente por Novikov e Boone durante
a Guerra Fria, numa época em que a matemática produzida em cada um dos blocos era pouco
divulgada no outro:
Teorema 7.5 (Novikov 1955, Boone 1957) Existem grupos finitamente apresentáveis com problema
da palavra indecidı́vel.
A prova deste teorema é complexa e pode ser obtida codificando uma das estruturas mais
gerais da teoria da computação (a máquina de Turing) através de uma apresentação finita de um
grupo! A indecidibilidade do chamado problema da paragem da máquina de Turing implica então
a indecidibilidade do problema da palavra do grupo.
Como consequência do Teorema 7.5, todos os problemas algébricos não triviais se revelam
indecidı́veis para apresentações finitas arbitrárias de grupos. Por exemplo:
Teorema 7.6 (Adjan 1955, Rabin 1958) É indecidı́vel se um grupo finitamente apresentável arbitrário é trivial, finito, infinito, livre.
7.4
Diagramas de van Kampen
Os diagramas de van Kampen constituem uma das ferramentas geométricas clássicas para estudar
apresentações de grupos.
Um grafo Γ = (V, E) diz-se planar se puder ser realizado geometricamente num plano, isto é, se
pudermos representar V e E como conjuntos de pontos e linhas no plano de forma a que as linhas
não se intersetem fora dos vértices. Por exemplo, o grafo completo com 4 vértices (K4 ) é planar
pois admite a representação
•
•
•
•
59
enquanto K5 constitui o mais pequeno exemplo (em termos de vértices) de grafo não planar
•
•
•
•
•
e o grafo bipartido K3,3
•
•
•
•
•
•
é o grafo não planar com menor número de arestas.
O conceito de planaridade estende-se da maneira óbvia a grafos orientados e a A-grafos. Um
A-grafo diz-se conexo se for conexo enquanto grafo não orientado.
Note-se que um grafo (grafo orientado, A-grafo) planar finito divide o plano num número finito
de regiões (incluindo a região exterior). A fronteira de uma região é o conjunto dos vértices e das
arestas que lhe são adjacentes. No caso de um A-grafo conexo, o bordo de uma região é uma palavra
e∗ obtida lendo sucessivamente o rótulo das arestas da sua fronteira, começando num vértice
w∈A
qualquer e seguindo o sentido horário ou anti-horário. Para este efeito, lemos o rótulo das arestas
como se o autômato fosse involutivo. Note-se que o bordo de uma região pode ser representado
por várias palavras, mas cada uma delas será sempre um conjugado cı́clico ou o inverso de um
conjugado cı́clico da outra.
Exemplo 7.7 Seja A = {a, b} e seja Γ o A-grafo descrito por
a
•o
?•
/•o
•_
b
a
?•
a
a
b
a
b
•

/•
a
b
As 4 regiões interiores de Γ têm bordo a3 (duas vezes), aba−1 b−1 e b3 , enquanto a região exterior
tem bordo ba−2 b2 a2 .
Seja P = hA | Ri uma apresentação de grupos. É claro que podemos sempre assumir que os
relatores de R estão na forma reduzida. Como u = 1 se e só se xux−1 = 1 em qualquer grupo,
podemos até assumir que os relatores são palavras ciclicamente reduzidas. Sob esta suposição,
definimos diagrama de van Kampen de P como sendo um A-grafo conexo finito em que:
• cada região interior admite como bordo um relator de R;
60
• o bordo da região exterior é ciclicamente reduzido.
Note-se que, para ler o relator de R, temos o direito de escolher o vértice inicial e o sentido no
cálculo do bordo da região interior. O bordo da região exterior diz-se o bordo do diagrama. Mais
uma vez, um diagrama pode admitir como bordo várias palavras, mas cada uma delas será sempre
um conjugado cı́clico ou o inverso de um conjugado cı́clico da outra. A dimensão do diagrama é o
número de regiões interiores.
É imediato que o A-grafo do Exemplo 7.7 é um diagrama de van Kampen da apresentação
ha, b | a3 , b3 , [a, b]i com bordo ba−2 b2 a2 .
O resultado seguinte explica a importância dos diagramas de van Kampen no estudo do problema
da palavra. Note-se que para resolver o problema da palavra, basta considerar palavras ciclicamente
reduzidas!
Teorema 7.8 (van Kampen 1933) Seja P = hA | Ri uma apresentação de grupos com relatores
ciclicamente reduzidos e seja w ∈ FA ciclicamente reduzida. Então as condições seguintes são
equivalentes:
−1
−1 e x ∈ F ;
(i) w = (x1 r1 x−1
i
A
1 ) . . . (xk rk xk ) para alguns k ≥ 0, ri ∈ R ∪ R
(ii) existe um diagrama de van Kampen de P de dimensão k e bordo w.
Além disso, se R for finito e M = max {|r| : r ∈ R}, podemos assumir que
1
|xi | ≤ (k|w| + k 2 M ) para i = 1, . . . , k.
2
(10)
e
Prova. (i) ⇒ (ii). Consideramos o A-grafo
involutivo descrito por
rk
%
•o
xk
•
x3
...
E•
x1
x2
/•e
r1
•Q
r2
r3
ao qual removemos em seguida todas as arestas com rótulo em A−1 . Obtemos assim um A-grafo
planar conexo com k regiões interiores. O último passo consiste em executar a dobragem sucessiva
de arestas da forma
•
8•
a
•
a
a
/•
ou
•
a
/&
quando não exista nenhuma aresta no meio! Esta versão da dobragem de arestas preserva a planaridade do grafo, a conexidade e o número de regiões interiores, bem como os seus bordos (que
permanecem relatores de R). Quando o processo terminar, poderemos ler no bordo a palavra
61
−1
(x1 r1 x−1
1 ) . . . (xk rk xk ), isto é, w. Logo construı́mos um diagrama de van Kampen de P de dimensão k e bordo w.
(ii) ⇒ (i). Procedemos por indução sobre a dimensão do diagrama de van Kampen. O único
diagrama de dimensão 0 é o diagrama trivial que contém apenas um único vértice e tem como
bordo a palavra vazia. Logo a implicação é válida para k = 0. Além disso, se R for finito então
(10) é trivialmente verificada.
Suponhamos agora que D é um diagrama de dimensão k > 0 e bordo w, e que a implicação (ii)
⇒ (i) é válida para diagramas de dimensão k − 1. Supomos ainda que (10) é verificada para k − 1
quando R é finito.
e
Para efeitos de representação de rótulos de regiões e caminhos, encaramos D como um A-grafo
involutivo. Nesse caso, temos um loop em D
pd
w
que dá origem ao bordo. Entre os vértices deste loop adjacentes a uma região interior, seja q o
mais próximo de p. Trocando w por w−1 se necessário, podemos assumir que o loop de rótulo w se
fatoriza como
pj
u
*q
v
com uv = w e |u| ≤
acordo com a figura
|w|
2 .
Podemos assumir que a região interior I adjacente a q tem bordo v 0 z de
p
u
/qk
v0
I
+ q0
v 00
/p
z
v0
onde v 0 v 00 = v e q −→q 0 é a parte da fronteira de I contı́gua à região exterior.
Seja D0 o A-grafo
v0 0
obtido removendo de D as arestas e os vértices intermédios do caminho q −→q . É fácil verificar
que D0 é um diagrama de van Kampen de P com bordo uz −1 v 00 se z 6= 1 pois nesse caso uz −1 v 00 é
ciclicamente reduzida. E se z = 1? Então pode acontecer que uv 00 não seja reduzida – por exemplo,
se D for da forma
p
q
•
Nesse caso, se y é o núcleo cı́clico de uv 00 = hyh−1 , eliminamos as arestas de D0 correspondentes
ao rótulo h (e que estão totalmente imersas na face exterior do A-grafo). Logo podemos sempre
afirmar em qualquer caso que existe um diagrama de van Kampen D00 de P de dimensão k − 1 que
tem como bordo o núcleo cı́clico y de uz −1 v 00 = hyh−1 . Note-se que |h| ≤ |w|
2 e |y| ≤ |w| + M .
−1
Pela hipótese de indução, podemos escrever y = (x1 r1 x1 ) . . . (xk−1 rk−1 x−1
k−1 ) para alguns ri ∈
R ∪ R−1 e xi ∈ FA . Além disso, se R for finito, temos |xi | ≤ 21 ((k − 1)|y| + (k − 1)2 M ) para
i = 1, . . . , k − 1. Logo
w = uv = uv 0 v 00 = (u(v 0 z)u−1 )(uz −1 v 00 ) = (u(v 0 z)u−1 )(hyh−1 )
= (u(v 0 z)u−1 )((hx1 )r1 (hx1 )−1 ) . . . ((hxk−1 )rk−1 (hxk−1 )−1 ).
Como v 0 z é um conjugado cı́clico de algum r ∈ R ∪ R−1 , (i) é válido.
62
Suponhamos agora que R é finito. Podemos escrever u(v 0 z)u−1 = (ut)r(ut)−1 para algum
t ∈ FA tal que |t| ≤ M
2 . Logo
|ut| ≤ |u| + |t| ≤
|w| M
1
+
≤ (k|w| + k 2 M ).
2
2
2
Por outro lado, para i = 1, . . . , k − 1, temos
1
2
|hxi | ≤ |h| + |xi | ≤ |w|
2 + 2 ((k − 1)|y| + (k − 1) M )
1
1
2
2
≤ |w|
2 + 2 ((k − 1)|w| + (k − 1)M + (k − 1) M ) ≤ 2 (k|w| + k M ).
Logo (10) é válido e a prova está completa. 7.5
Funções isoperimétricas
Seja P = hA | Ri uma apresentação finita de um grupo G e seja ϕ : FA → G o correspondente
homomorfismo sobrejetivo. Dado w ∈ 1ϕ−1 , definimos a área de w como sendo o menor k ≥ 0 tal
que
−1
w = (x1 r1 x−1
1 ) . . . (xk rk xk )
para alguns ri ∈ R ∪ R−1 e xi ∈ FA . Designamo-la por Area(w).
Uma função Iso : N → [0, +∞[ diz-se uma função isoperimétrica para P se
Area(w) ≤ Iso(|w|)
para todo w ∈ 1ϕ−1 .
Certos tipos de funções são particularmente importantes. Dizemos que uma função Iso : N →
[0, +∞[ é:
• linear se existir K > 0 tal que Iso(n) = Kn para todo n ∈ N;
• quadrática se existir K > 0 tal que Iso(n) = Kn2 para todo n ∈ N;
• polinomial se existirem K > 0 e m ∈ N tais que Iso(n) = Knm para todo n ∈ N;
• exponencial se existir K > 0 tal que Iso(n) = K n para todo n ∈ N;
• recursiva se existir um algoritmo que calcula efetivamente Iso(n) para todo n ∈ N.
Exemplo 7.9 A apresentação P = ha, b | [a, b]i de Z × Z admite uma função isoperimétrica
quadrática.
Consideremos o homomorfismo ϕ : F2 → Z × Z definido por aϕ = (1, 0) e bϕ = (0, 1). Sejam
2
Iso(n) = n4 e w ∈ 1ϕ−1 . Vamos mostrar que Area(w) ≤ Iso(w) por indução sobre |w|.
Temos Area(w) = 0 quando |w| < 4 pois a única palavra reduzida de comprimento < 4 em 1ϕ−1
é a palavra vazia. Suponhamos agora que |w| = n ≥ 4 e que a desigualdade Area(w0 ) ≤ Iso(w0 ) é
válida para elementos w0 ∈ 1ϕ−1 de comprimento < n.
63
Podemos fatorizar w = uaε bm a−ε v (em forma reduzida) para alguns ε ∈ {1, −1} e m 6= 0.
Então w = (uaε bm a−ε b−m u−1 )(ubm v). Como ambos os fatores desta fatorização pertencem a
1ϕ−1 , podemos escrever
Area(w) ≤ Area(uaε bm a−ε b−m u−1 ) + Area(ubm v).
(11)
Ora Area(xyx−1 ) = Area(y) para todos x ∈ FA e y ∈ 1ϕ−1 , logo
Area(uaε bm a−ε b−m u−1 ) = Area(aε bm a−ε b−m ).
Como existe um diagrama de van Kampen
•O
b
a
/•
O
b
b
b
/
...
b
a
a
•
/•
O
/•
b
/•
/•
O
a
b
/
...
b
/•
de bordo aε bm a−ε b−m e dimensão m, resulta do Teorema 7.8 que Area(aε bm a−ε b−m ) ≤ m <
Por outro lado, Area(ubm v) ≤
Area(w) <
(n−2)2
4
n
2.
por hipótese de indução, logo resulta de (11) que
n (n − 2)2
2n + n2 − 4n + 4
n2 − 2n + 4
n2
+
=
=
<
2
4
4
4
4
e portanto Iso é uma função isoperimétrica para P.
O seguinte resultado é uma das consequências importantes do Teorema 7.8:
Corolário 7.10 Seja P = hA | Ri uma apresentação finita. Então as condições seguintes são
equivalentes:
(i) P tem problema da palavra decidı́vel;
(ii) P admite uma função isoperimétrica recursiva.
Prova. (i) ⇒ (ii). Seja
Dehn(n) = max ({Area(w) | w ∈ hhRii, |w| = n} ∪ {0}).
É claro que a função Dehn constitui uma função isoperimétrica para P, dita função de Dehn de P.
Note-se que Dehn(n) ≤ Iso(n) para toda outra função isoperimétrica Iso.
Para mostrar que a função Dehn é recursiva, tomamos w ∈ FA com |w| = n. Podemos utilizar
(i) para decidir se w pertence ou não a hhRii. Suponhamos que pertence. Agora basta mostrar que
Area(w) é computável, para o que utilizamos o seguinte algoritmo:
Para k = 0, 1, 2, . . ., vamos testar se Area(w) = k verificando se a igualdade
−1
w = (x1 r1 x−1
1 ) . . . (xk rk xk )
64
(12)
é válida em FA para alguma escolha de xi ∈ FA e ri ∈ R ∪ R−1 . Pelo Teorema 7.8, só temos que
testar um número finito de xi , e o mesmo acontece com os ri visto que R é finito. Como w ∈ hhRii,
acabaremos inevitavelmente por encontrar um valor de k para o qual (12), se verifique. Esse valor
é Area(w). Logo a função Dehn é uma função isoperimétrica recursiva para P.
(ii) ⇒ (i). Seja Iso uma função isoperimétrica recursiva para P. Seja w ∈ FA . Queremos
mostrar que é decidı́vel se w ∈ hhRii. Como Area(w) ≤ Iso(|w|), isto equivale a ter a igualdade
(12) para alguns k ≤ Iso(|w|), xi ∈ FA e ri ∈ R ∪ R−1 . Mais uma vez, resulta do Teorema 7.8 que
só temos que testar um número finito de xi , e o mesmo acontece com os ri . Logo só temos de testar
um número finito de igualdades do tipo (12) em FA , donde resulta a decidibilidade do problema
da palavra. Dado um grupo finitamente apresentável, a existência de uma função isoperimétrica de um
determinado tipo não depende da apresentação finita escolhida, sendo pois um invariante do grupo:
Proposição 7.11 Sejam P = hA | Ri e P 0 = hA0 | R0 i apresentações finitas de um grupo G.
Se P admite uma função isoperimétrica recursiva (respetivamente linear, quadrática, polinomial,
exponencial), o mesmo acontece com P 0 .
Prova. O caso recursivo segue da Proposição 7.4 e do Corolário 7.10. Os restantes casos podem
ser demonstrados usando argumentos análogos aos desenvolvidos na prova da Proposição 7.3. 7.6
Exercı́cios
(7.1) (a) Mostre que S3 é gerado pelo subconjunto de permutações A = {(123), (12)}.
(b) Construa uma apresentação finita de S3 com dois geradores.
(7.2) Dados m, n ∈ N, construa uma apresentação finita de Cm × Cn com 3 relatores.
(7.3) Dado n ∈ N, construa uma apresentação finita de Z × Cn .
(7.4) Mostre que os grafos seguintes são planares:
(a)
•
•
•
•
•
(b)
•
•
•
•
•
•
65
(7.5) Para cada uma das apresentações dos grupos S3 , C3 × C3 e Z × C2 construı́das nos Exercı́cios
7.1 – 7.3, construa um diagrama de van Kampen com 5 regiões interiores e calcule o respetivo
bordo.
(7.6) Seja G o grupo definido pela apresentação P = ha, b, c | a2 c−1 , a2 b−2 i.
(a) Mostre que
a
•
c
/•
b
/•
a
a
•
c
•
/•
c
a
•
c
a
b
/•
b
a
•
b
/•
/•
a
é um diagrama de van Kampen de P.
(b) Determine se bca−1 cab−2 c−1 ac−2 ab = 1 em G.
(7.7) Determine se existe algum diagrama de van Kampen da apresentação ha, b | [a, b]i com bordo
aba−1 b−2 .
(7.8) Mostre que o grupo cı́clico Cn admite uma função isoperimétrica linear para todo n ≥ 1.
66
8
Produto livre e generalizações
As apresentações revelam-se particularmente úteis no estudo de certos operadores, como é o caso
do produto livre e suas generalizações, que incluem casos tão importantes como os produtos livres
com amalgamação ou os produtos de grafo.
8.1
Produto livre
Dizemos que o grupo H é o produto livre dos grupos G1 e G2 se existirem homomorfismos ιi : Gi →
H (i = 1, 2) tais que: para todo grupo K e homomorfismos ϕi : Gi → K (i = 1, 2), existe um único
homomorfismo Φ : H → K tal que o diagrama
G1
ι1
/ H o ι2
Φ
ϕ1
~
G2
ϕ2
K
comuta.
Lema 8.1 Sejam G1 e G2 grupos. O produto livre de G1 e G2 , a existir, é único a menos de
isomorfismo.
Prova. Suponhamos que H é o produto livre de G1 e G2 para os homomorfismos ιi : Gi → H
(i = 1, 2), e H 0 é o produto livre de G1 e G2 para os homomorfismos ι0i : Gi → H 0 (i = 1, 2). Então
existem homomorfismos Φ : H → H 0 e Ψ : H 0 → H tais que ιi Φ = ι0i e ι0i Ψ = ιi (i = 1, 2). Mas
então
ι1
ι2
/Ho
G1
G2
ι1
1H
ΦΨ
ι2
~
H
é um diagrama comutativo. Pela unicidade do homomorfismo na definição de produto direto,
obtemos ΦΨ = 1H . Analogamente, ΨΦ = 1H 0 , logo Φ e Ψ são isomorfismos e H ∼
= H 0. Para demonstrar a existência do produto livre, vamos proceder à seguinte construção. Dado
um grupo G, seja G̊ = G \ {1}. Fixemos agora grupos G1 e G2 . Construimos um alfabeto
AG1 ,G2 = {ag | g ∈ G1 } ∪ {bh | h ∈ G2 }
e consideramos o sistema de reescrita
RG1 ,G2
= {(ag ag0 , agg0 ) | g, g 0 ∈ G1 } ∪ {(bh bh0 , bhh0 ) | h, h0 ∈ G2 }
∪ {(a1 , 1), (b1 , 1)}.
67
Lema 8.2 Sejam G1 e G2 grupos. Então RG1 ,G2 é um sistema de reescrita redutor e confluente.
Prova. É evidente que RG1 ,G2 é redutor, e a confluência prova-se analogamente à demonstração
do Lema 3.1: só temos que testar a confluência local para situações do tipo
xag ag0 ag00 y
/ xagg0 ag00 y
xag a1 y
/ xag y
xa1 ag y
xag ag0 g00 y
/ xag y
xag1 y
xa1g y
e as versões análogas para G2 , o que se confirma facilmente. Seja G1 ∗ G2 = Irr(RG1 ,G2 ). Então G1 ∗ G2 consiste na palavra vazia e em todas as palavras
que alternam letras da forma ag (g ∈ G̊1 ) com letras da forma bh (h ∈ G̊2 ).
Definimos uma operação binária ◦ em G1 ∗ G2 do seguinte modo: Dados u, v ∈ G1 ∗ G2 , u ◦ v é
a forma reduzida da palavra uv em RG1 ,G2 . A confluência garante que esta operação é associativa,
e a palavra vazia é o elemento neutro. É fácil verificar a existência de inversos: por exemplo,
(ag1 bh1 . . . agn bhn ) ◦ (bh−1
agn−1 . . . bh−1 ag−1 ) = 1
n
1
1
e todos os outros casos são análogos. Logo (G1 ∗ G2 , ◦) é um grupo. Note-se que existe um
homomorfismo injetivo ι1 : G1 → G1 ∗ G2 definido por
ag se g 6= 1
gι1 =
1
se g = 1
Analogamente definimos ι2 : G2 → G1 ∗ G2 .
Teorema 8.3 Sejam G1 e G2 grupos. Então G1 ∗ G2 é o produto livre de G1 e G2 relativamente
aos homomorfismos ιi : Gi → G1 ∗ G2 (i = 1, 2).
Prova. Seja A = AG1 ,G2 e R = RG1 ,G2 . Seja K um grupo e seja ϕi : Gi → K um homomorfismo
para i = 1, 2. Definimos um homomorfismo ϕ : A∗ → K por ag ϕ = gϕ1 (g ∈ G1 ) e bh ϕ = hϕ2
(h ∈ G2 ). Seja Φ = ϕ |Irr(R) . Para todo g ∈ G̊1 , temos gι1 Φ = ag Φ = gϕ1 . Como 1G1 ι1 Φ = 1Φ =
1 = 1G1 ϕ1 , obtemos ι1 Φ = ϕ1 . Analogamente, ι2 Φ = ϕ2 .
Para mostrar que Φ : G1 ∗ G2 → K é um homomorfismo de grupos, temos que provar que
(u◦v)Φ = (uΦ)(vΦ) para todos u, v ∈ G1 ∗G2 . Como (uΦ)(vΦ) = (uϕ)(vϕ) = (uv)ϕ, basta verificar
que rϕ = sϕ para todo (r, s) ∈ R, o que é obviamente verdade. Logo Φ é um homomorfismo.
Finalmente, a unicidade de Φ resulta do fato de X = G1 ι1 ∪ G2 ι2 gerar G1 ∗ G2 , e Φ|X estar
univocamente determinado. Habitualmente, simplificamos a representação dos elementos de G1 ∗G2 escrevendo g1 h1 . . . gn hn
em vez de ag1 bh1 . . . agn bhn e assim sucessivamente. É a representação do produto livre em forma
normal.
Podemos afirmar que o produto livre G1 ∗G2 é o maior grupo, gerado por G1 ∪G2 , pois qualquer
outro grupo K nestas condiçõs será necessariamente imagem homomorfa de G1 ∗ G2 .
Vamos ver em seguida como o produto livre se traduz em termos de apresentações:
68
Teorema 8.4 Seja hAi | Ri i uma apresentação do grupo Gi para i = 1, 2, com A1 ∩ A2 = ∅. Então
hA1 ∪ A2 | R1 ∪ R2 i é uma apresentação de G1 ∗ G2 .
Prova. Sem perda de generalidade, podemos assumir que Gi = FAi /hhRi ii. Sejam A = A1 ∪ A2
e R = R1 ∪ R2 . Seja H = FA /hhRii. Pelo Teorema 1.5, podemos definir um homomorfismo
ιi : Gi → H para i = 1, 2 por (ghhRi ii)ιi = ghhRii.
Dado um grupo K e homomorfismos ϕi : Gi → K (i = 1, 2), consideremos os homomorfismos
canónicos πi : FAi → Gi . É fácil construir um homomorfismo ϕ : FA → K tal que ϕ|FAi = πi ϕi
para i = 1, 2. Ora Ri ⊆ Ker(πi ) ⊆ Ker(ϕ) para i = 1, 2 implica R ⊆ Ker(ϕ), logo pelo Teorema 1.5
existe um homomorfismo Φ : H → K tal que (ghhRii)Φ = gϕ.
Para todo g ∈ FAi , temos
(ghhRi ii)ιi Φ = (ghhRii)Φ = gϕ = gπi ϕi = (ghhRi ii)ϕi ,
logo ιi Φ = ϕi para i = 1, 2. A unicidade de Φ resulta do fato de im(ι1 ) ∪ im(ι2 ) gerar H. Logo H
é o produto livre de G1 e G2 e portanto hA1 ∪ A2 | R1 ∪ R2 i é uma apresentação de G1 ∗ G2 . 8.2
Generalizações
Os produtos livres com amalgamação constituem uma das generalizações mais importantes do
produto livre pelo seu significado geométrico. Suponhamos que G1 e G2 são grupos com subgrupos
H1 , H2 (respetivamente), e existe um isomorfismo ϕ : H1 → H2 . Seja
N = hh(hϕ)h−1 : h ∈ H1 ii E G1 ∗ G2 .
O grupo quociente (G1 ∗ G2 )/N diz-se o produto livre com amalgamação de G1 e G2 (relativamente
ao isomorfismo ϕ). O produto livre corresponde ao caso particular H1 = H2 = {1}.
O produto livre com amalgamação aparece por exemplo no famoso Teorema de van Kampen. Em topologia algébrica, o chamado grupo fundamental é o mais importante dos invariantes
topológicos associados a um espaço topológico (isto é, espaços topológicos homeomorfos têm grupos
fundamentais isomorfos). Ora no estudo das variedades, as técnicas ditas de cirurgia são muito
importantes pois elas permitem decompor/construir variedades mais complexas a partir de variedades mais simples. O Teorema de van Kampen (1933) explica que, nas condições apropriadas, o
grupo fundamental da união de duas variedades é um produto livre com amalgamação dos grupos
fundamentais das dua variedades mais simples.
Esta é mais um resultado brilhante do belga Egbert van Kampen. Infelizmente ele morreu com
apenas 33 anos!
Outra generalização é o chamado produto de grafo. Suponhamos que G1 , . . . , Gn são grupos e
que Γ = (V, E) é um grafo com V = {1, . . . , n}. O Γ-produto de G1 , . . . , Gn pretende ser o maior
grupo, gerado por G1 ∪ . . . ∪ Gn , no qual os elementos de Gi comutam com os elementos de Gj
quando existe uma aresta i −− j em Γ.
Note-se que o produto livre é na realidade uma operação associativa (ver o Exercı́cio 8.2), o
que permite falar do produto livre G1 ∗ G2 ∗ . . . ∗ Gn . Formalmente, o Γ-produto de G1 , . . . , Gn é o
grupo quociente
Γ(G1 , . . . , Gn ) = (G1 ∗ G2 ∗ . . . ∗ Gn )/N,
69
onde
N = hh[gi , gj ] : gi ∈ Gi , gj ∈ Gj , (i −− j) ∈ Eii E G1 ∗ . . . ∗ Gn .
Se E = ∅, então Γ(G1 , . . . , Gn ) é o produto livre G1 ∗ . . . ∗ Gn . Se Γ for um grafo completo,
Γ(G1 , . . . , Gn ) é o produto direto G1 × . . . × Gn . Se Γ for o quadrado
1
2
3
4
é fácil ver que
Γ(G1 , G2 , G3 , G4 ) ∼
= (G1 ∗ G4 ) × (G2 ∗ G3 ).
Os produtos de grafos permitem assim introduzir elementos de comutatividade parcial num
operador tão ferozmente anti-comutativo como o produto livre. Estas ideias de comutatividade
parcial são muito importantes também na teoria da computação, onde são usadas na construção
de modelos para a computação em paralelo.
8.3
Grupos de grafo
Os grupos de grafo são produtos de grafo de grupos cı́clicos infinitos, ou seja, da forma Γ(Z, . . . , Z).
Se Γ = (V, E) e V = {1, . . . , n}, resulta que Γ(Z, . . . , Z) admite a apresentação
ha1 , . . . , an | [ai , aj ] ((i −− j) ∈ E)i.
(13)
Se E = ∅, obtemos o grupo livre Fn . Se Γ for um grafo completo, obtemos o grupo abeliano livre
Zn (ver o Exercı́cio 3.1).
Os grupos de grafo, também chamados de grupos de Artin ortogonais, partilham com os grupos
livres muitas das suas boas propriedades. Por exemplo:
Teorema 8.5 Todo grupo de grafo tem problema da palavra decidı́vel.
Prova. Vamos traçar as linhas gerais da demonstração, omitindo alguns detalhes técnicos.
Seja Γ = (V, E) um grafo com V = {1, . . . , n} e seja G o grupo definido pela apresentação (13).
e∗ → G a projeção canónica.
Seja A = {a1 , . . . , an } e seja ϕ : A
e tais que:
Designamos por X o conjunto de todos os subconjuntos X de A
• X ∩ X −1 = ∅;
• se aδi e aεj são elementos distintos de X, então (i −− j) ∈ E.
Para simplificar a notação, escreveremos
X + a = X ∪ {a},
e
para todos X ∈ X e a ∈ A.
70
X − a = X \ {a}
Construimos um alfabeto finito
B = {bX | X ∈ X }
e um sistema de reescrita em B definido por
R = {(bX bY , bX−a bY −a−1 ) | X, Y ∈ X ; a ∈ X ∩ Y −1 }
∪ {(bX bY , bX+a bY −a ) | X + a, Y ∈ X ; a ∈ Y \ X}
∪ {(b∅ , 1)}.
É fácil ver que R é noetheriano, logo a confluência resultará da confluência local tal como no Lemma
3.1. Limitar-nos-emos a analisar um único caso como exemplo:
e são tais que a ∈ X ∩ Y −1 , c ∈ Z \ Y e
Suponhamos que w, z ∈ B ∗ , X, Y, Z ∈ X e a, c ∈ A
±1
Y + c ∈ X . É fácil verificar que c 6= a e que podemos completar o diagrama seguinte da forma
indicada,
/ wbX−a b
wbX bY bZ z
Y −a−1 bZ z
/ wbX−a b
Y −a−1 +c bZ−c z
wbX bY +c bZ−c z
o que comprova a confluência local para sobreposições deste tipo.
Admitida a confluência, resulta da Proposição 2.10 que para cada w ∈ B ∗ existe uma única
palavra wη ∈ Irr(R) tal que w−→∗ wη.
e∗ → B ∗ o homomorfismo de monóides definido por aα = ba (a ∈ A).
e Definimos
Seja α : A
Q
∗
∗
e
também um homomorfismo de monóides β : B → A por Xβ = a∈X a (X ∈ X ), sendo a ordem
e resulta que
no produto das letras fixada arbitrariamente. Como aαβ = a para toda a ∈ A,
uαβ = u
(14)
e∗ .
para toda u ∈ A
Por outro lado, se (r, s) ∈ R, é fácil verificar que rβϕ = sβϕ, logo
w−→z implica wβϕ = zβϕ
e consequentemente
w−→∗ z implica wβϕ = zβϕ
(15)
para todas w, z ∈ B ∗ .
Para provar que o problema da palavra de G é decidı́vel, basta agora mostrar que
uϕ = 1 se e só se uαη = 1
e∗ , uma vez que uαη é efetivamente computável.
para toda u ∈ A
Suponhamos então que uϕ = 1. Então podemos escrever uθ = vθ para alguma palavra
εk −1
v = (x1 [ai1 , aj1 ]ε1 x−1
1 ) . . . (xk [aik , ajk ] xk ),
71
(16)
e∗ , (it −− jt ) ∈ E, εt = ±1 para t = 1, . . . , k. É fácil verificar que [ait , ajt ]αη = 1
com k ≥ 0 e xt ∈ A
f∗ e a ∈ A,
e logo
para todo t, logo vαη = 1. Por outro lado, (paa−1 q)αη = (pq)αη para todas p, q ∈ A
uθ = vθ implica uαη = vαη = 1.
Reciprocamente, suponhamos que uαη = 1. Então uα−→∗ 1, logo uαβϕ = 1 por (15). Logo
uϕ = 1 por (14) e portanto (16) é válido com pretendı́amos. Mas seria prematuro pensar que todas as boas propriedades dos grupos livres são herdadas
pelos grupos de grafo. Por exemplo, mesmo no caso particular do quadrado
1
2
3
4
que define o grupo F2 × F2 , as dificuldades aparecem:
Teorema 8.6 (Mihailova 1966) O problema da palavra generalizado é indecidı́vel para F2 × F2 .
Pior ainda, Mihailova constrói um certo H ≤f.g. F2 × F2 tal que é indecidı́vel , para g ∈ F2 × F2
arbitrário, se g ∈ H ou não.
8.4
Exercı́cios
(8.1) Sejam G e H grupos não triviais. Mostre que:
(a) os elementos de ordem finita de G ∗ H são os conjugados dos elementos de ordem finita
de G e H;
(b) G ∗ H tem elementos de ordem infinita.
(8.2) Mostre que o produto livre de grupos é associativo.
(8.3) Sejam G e H grupos não triviais e seja K o conjunto dos elementos de G ∗ H da forma
g1 h1 . . . gn hn
(gi ∈ G \ {1}, hi ∈ H \ {1}).
Mostre que:
(a) todo elemento de G ∗ H é conjugado de algum elemento de G ou H ou K;
(b) os conjugados em K de g1 h1 . . . gn hn ∈ K são da forma gi hi . . . gn hn g1 h1 . . . gi−1 hi−1 ;
(c) se G e H têm problema da conjugação decidı́vel, o mesmo acontece com G ∗ H.
(8.4) Sejam G1 e G2 grupos. Mostre que o produto direto G1 × G2 é, a menos de isomorfismo, o
único grupo H com a seguinte propriedade: existem homomorfismos πi : H → Gi (i = 1, 2)
72
tais que: para todo grupo K e homomorfismos ϕ1 : K → Gi (i = 1, 2), existe um único
homomorfismo Φ : K → H tal que o diagrama
G1 ` o
π1
ϕ1
HO
Φ
π2
/ G2
>
ϕ2
K
comuta.
(8.5) Exprima (Z × Z) ∗ (Z × Z) como um grupo de grafo.
(8.6) Mostre que todo grupo de grafo é livre de torsão.
[Sugestão: dentro de cada classe de conjugação, trabalhe com o elemento da forma mais
conveniente.]
73
9
Grupos hiperbólicos
Os grupos hiperbólicos constituem certamente um dos temas mais belos da moderna teoria de
grupos, e devem-se a uma ideia revolucionária de Gromov nos anos 80: usar a geometria local do
grafo de Cayley para resolver problemas algorı́tmicos.
9.1
Grafos hiperbólicos
Seja Γ = (V, E) um grafo conexo. Podemos definir uma métrica d em V do seguinte modo: dados
p, q ∈ V , d(p, q) é o comprimento mı́nimo de um caminho ligando p a q em Γ. Um tal caminho
diz-se uma geodésica de Γ.
Note-se que d está bem definida porque o grafo é conexo, e satisfaz efetivamente os axiomas
(M1) – (M4). Diz-se a métrica geodésica de Γ.
Dado p ∈ V e W ⊆ V não vazio, escrevemos
d(p, W ) = min {d(p, q) | q ∈ W }.
Se X ⊆ V ∪ E, escrevemos d(p, X) = d(p, X ∩ V ).
Um triângulo geodésico em Γ é um conjunto de 3 geodésicas
X : p −− q,
Y : q −− r,
Z : r −− p
formando um triângulo
p
q
r
Designamos um tal triângulo geodésico por ∆[XY Z]. Note-se que o triângulo pode ser degenerado,
uma vez que um caminho trivial é também uma geodésica.
Dada uma constante δ ≥ 0, dizemos que Γ é δ-hiperbólico se, para todo o triângulo geodésico
∆[XY Z] em Γ e todo vértice x em X, se tem
d(x, Y ∪ Z) ≤ δ.
Dizemos que Γ é hiperbólico se for δ-hiperbólico para algum δ ≥ 0. A designação é inspirada pela
natureza dos triângulos no espaço hiperbólico, que têm curvatura negativa:
Discutimos em seguida a condição em alguns casos simples. Dado um grafo conexo Γ = (V, E),
o seu diâmetro é definido por
diam(Γ) = sup{d(p, q) | p, q ∈ V }.
74
Lema 9.1
(i) Se Γ é um grafo conexo finito, então Γ é δ-hiperbólico para δ = diam(Γ).
(ii) Se Γ é uma árvore, então Γ é 0-hiperbólico.
(iii) Se Γ é o grafo descrito por
..
.
..
.
..
.
...
•
•
•
...
...
•
•
•
...
...
•
•
•
...
..
.
..
.
..
.
então Γ não é hiperbólico.
Prova. (i) Imediato.
(ii) Se ∆[XY Z] é um triângulo geodésico numa árvore Γ, então os vértices de X ocorrem todos
em Y ∪ Z.
(iii) Vamos identificar os vértices de Gamma com Z × Z da forma óbvia. Para cada n ≥ 1,
definimos as geodésicas
Xn : (0, 0) −− (0, n),
Yn : (0, n) −− (n, n) −− (n, 0),
Zn : (n, 0) −− (0, 0)
e consideramos o triângulo geodésico ∆[Yn Zn Xn ]. Temos que (n, n) ocorre em Yn e d((n, n), Zn ∪
Xn ) = n. Como n pode ser arbitrariamente grande, concluimos que Γ não é hiperbólico. Vamos agora introduzir o importante conceito de quasi-isometria. Dois espaços métricos (X, d)
e (X 0 , d0 ) dizem-se isométricos se existir uma bijeção ϕ : X → X 0 tal que
d0 (xϕ, yϕ) = d(x, y) para todos x, y ∈ X.
Se aplicarmos este conceito ao espaço dos vértices de um grafo conexo, com a distância geodésica,
verificamos facilmente que a isometria corresponde precisamente ao isomorfismo de grafos: se ϕ :
V → V 0 é uma bijeção que preserva a distância geodésica, então preserva a relação de adjacência e
logo os grafos são isomorfos, e vice-versa.
Por isso é muito mais interessante enfraquecer um pouco as exigências. Dois espaços métricos
(X, d) e (X 0 , d0 ) dizem-se quase-isométricos se existirem funções ϕ : X → X 0 e ψ : X 0 → X
e constantes λ, C ≥ 0 tais que, para todos x, y ∈ X e x0 , y 0 ∈ X 0 . as condições seguintes são
verificadas:
75
(Q1) d0 (xϕ, yϕ) ≤ λd(x, y) + C;
(Q2) d(x0 ψ, y 0 ψ) ≤ λd0 (x0 , y 0 ) + C;
(Q3) d(xϕψ, x) ≤ C;
(Q4) d0 (x0 ψϕ, x0 ) ≤ C.
Dizemos que dois grafos são quase-isométricos se os respetivos conjuntos de vértices, munidos
da distância geodésica, constituem espaços métricos isométricos.
Podemos provar o seguinte resultado:
Lema 9.2
(i) Todos os grafos conexos de diâmetro finito são quase-isométricos.
(ii) Nenhum grafo conexo de diâmetro finito é quase-isométrico a um grafo conexo de diâmetro
infinito.
Prova. (i) Tomamos C igual ao máximo dos diâmetros dos dois grafos, e λ, ϕ, ψ arbitrários.
(ii) Sejam Γ = (V, E), Γ0 = (V 0 , E 0 ) e ϕ : V → V 0 , ψ : V 0 → V funções satisfazendo os axiomas
(Q1) – (Q4) para as métricas geodésicas. Suponhamos que Γ tem diâmetro finito M . Para todos
x0 , y 0 ∈ V 0 , temos
d0 (x0 , y 0 ) ≤ d0 (x0 , x0 ψϕ) + d0 (x0 ψϕ, y 0 ψϕ) + d0 (y 0 ψϕ, y 0 ) ≤ C + λd(x0 ψ, y 0 ψ) + C + C
≤ 3C + λM,
logo Γ0 tem diâmetro finito ≤ 3C + λM . O teorema seguinte mostra a robustez do conceito de grafo hiperbólico:
Teorema 9.3 Sejam Γ e Γ0 grafos conexos quase-isométricos. Então Γ é hiperbólico se e só se Γ0
é hiperbólico.
A demonstração usa argumentos geométricos complexos envolvendo o conceito de quase-geodésica,
que não vamos introduzir neste curso. Atenção que as constantes de hiperbolicidade de Γ e Γ0 podem
ser muito diferentes!
9.2
Grafos de Cayley hiperbólicos
Suponhamos agora que G é um grupo gerado por um subconjunto finito A. O grafo de Cayley
e
ΓA (G) não é um grafo no sentido formal da palavra, é na realidade um A-grafo
(conexo), mas
as ideias e os resultados apresentados na subsecção anterior podem ser aplicadas também neste
contexto.
Como G é o conjunto dos vértices de ΓA (G), podemos em particular definir uma métrica dA
e∗ tal que h = gu em G.
em G, tal que dA (g, h) é o comprimento da mais curta palavra u ∈ A
Dizemosque dA é a métrica geodésica de G (relativamente ao conjunto A de geradores).
76
É fácil verificar que
dA (xg, xh) = dA (g, h) para todos g, h, x ∈ G.
(17)
a
Note-se também que, sendo ΓA (G) involutivo (a cada aresta g −→ga corresponde uma aresta
ga−→g), a orientação das arestas é irrelevante no cálculo da distância, o que elimina qualquer
dúvida sobre a sua simetria... Temos igualmente o conceito de triângulo geodésico e a definição de
hiperbolicidade é a mesma. Mas a hiperbolicidade do grafo de Cayley poderá depender do conjunto
finito de geradores escolhido? O resultado seguinte mostra que não:
a−1
Teorema 9.4 Sejam A e B conjuntos finitos de geradores de um mesmo grupo G. Então os grafos
de Cayley ΓA (G) e ΓB (G) são quase-isométricos.
Prova. Ambos os grafos têm G como conjunto dos vértices, logo podemos considerar ϕ = ψ = 1G .
Fixamos C = 0 e
λ = max ({dA (b, 1) | b ∈ B} ∪ {dB (a, 1) | a ∈ A}).
É claro que (Q3) e (Q4) são satisfeitos. Sejam g, h ∈ G. Se dA (g, h) = n, então existem a1 , . . . , an ∈
e tais que ga1 . . . an = h. Em virtude de (17), temos dB (ai , 1) = dB (a−1 , 1) e também
A
i
dB (ga1 . . . ai−1 , ga1 . . . ai ) = dB (1, ai ) ≤ λ,
logo
dB (g, h) ≤
n
X
dB (ga1 . . . ai−1 , ga1 . . . ai ) ≤ λn = λdA (g, h)
i=1
e (Q1) é válido. Por simetria, obtemos também (Q2), logo os dois grafos de Cayley são isométricos.
Em consequência, podemos dizer que um grupo finitamente gerado é hiperbólico se ΓA (G) for
hiperbólico para algum (qualquer) subconjunto finito A de geradores de G.
Teorema 9.5 Seja G um grupo finitamente gerado e seja H um subgrupo de ı́ndice finito de G.
Então G é hiperbólico se e só se H é hiperbólico.
Prova. Suponhamos que [G : H] = m + 1. Podemos escrever G como uma união disjunta
G = Hb0 ∪ Hb1 ∪ . . . ∪ Hbm
para alguns b0 , . . . , bm ∈ G. Podemos assumir também que b0 = 1.
Seja A = {a1 , . . . , an } um conjunto gerador finito de G. Podemos assumir que A = A ∪ A−1 .
Para cada i ∈ {0, . . . , m} e j ∈ {1, . . . , n}, existem wij ∈ H e (i, j)α ∈ {0, . . . , m} únicos tais que
bi aj = wij b(i,j)α . Seja
W = {wij | i = 0, . . . , m; j = 1, . . . , n}.
77
Seja h ∈ H. Como h ∈ G = hAi, existem i1 , . . . , ik ∈ {1, . . . , n} tais que h = ai1 . . . aik . Seja
r0 = 0.Para j = 1, . . . , k, seja rj = (rj−1 , ij )α. Daqui resulta que
h = b0 h = br0 ai1 . . . aik = wr0 i1 br1 ai2 . . . aik
= wr0 i1 wr1 i2 br2 ai3 . . . aik = . . .
= wr0 i1 . . . wrk−1 ik brk .
Como h ∈ H, obtemos rk = 0, logo h ∈ hW i e portanto W é um conjunto finito de geradores de
H. Além disso,
dW (h, 1) ≤ dA (h, 1).
(18)
Seja B = W ∪ {b1 , . . . , bm }. Então B é também um conjunto finito de geradores de G, e resulta
da demonstração do Teorema 9.4 que
dA (h, h0 ) ≤ λdB (h, h0 ) para todos h, h0 ∈ H,
(19)
onde
λ = max ({dA (b, 1) | b ∈ B} ∪ {dB (a, 1) | a ∈ A}).
Podemos assumir que G é não trivial, logo λ ≥ 1. Seja ϕ : H → G a inclusão e seja ψ : G → H
definida por (hbi )ψ = h. Vamos mostrar que ΓA (G) e ΓW (H) são quase-isométricos verificando
que os axiomas (Q1) – (Q4) são satisfeitos para C = 2λ.
Sejam h, h0 ∈ H e i, j ∈ {0, . . . , m}. Então (19) e W ⊆ B implicam
dA (hϕ, h0 ϕ) = dA (h, h0 ) ≤ λdB (h, h0 ) ≤ λdW (h, h0 ) ≤ λdW (h, h0 ) + C.
Por outro lado, dW (hϕψ, h) = dW (h, h) = 0 ≤ C, logo (Q1) e (Q3) são válidos.
Temos também, graças a (18) e (17),
dW ((hbi )ψ, (h0 bj )ψ) = dW (h, h0 ) ≤ dA (h, h0 ) ≤ dA (h, hbi ) + dA (hbi , h0 bj ) + dA (h0 bj , h0 )
= dA (1, bi ) + dA (hbi , h0 bj ) + dA (bj , 1) ≤ λdA (hbi , h0 bj ) + C,
e
dA ((hbi )ψϕ, hbi ) = dA (h, hbi ) = dA (1, bi ) ≤ λ < C,
logo (Q2) e (Q4) são válidos.
Concluimos assim que ΓA (G) e ΓW (H) são quase-isométricos e aplicamos o Teorema 9.3. Podemos clarificar agora a questão da hiperbolicidade para várias classes de grupos. Um grupo
diz-se virtualmente livre se tiver um subgrupo livre de ı́ndice finito. Por exemplo, Fn × G é virtualmente livre para todo n ≥ 1 e todo grupo finito G.
Teorema 9.6
(i) Os grupos finitos são hiperbólicos.
(ii) Os grupos livres de dimensão finita são hiperbólicos.
(iii) Os grupos virtualmente livres finitamente gerados são hiperbólicos.
78
(iv) O grupo abeliano livre Z × Z não é hiperbólico.
Prova. (i) Pelo Lema 9.1(i).
(ii) Pelo Lema 9.1(ii).
(iii) Pela alı́nea (ii) e pelo Teorema 9.5.
(iv) Pelo Lema 9.1(iii). Uma outra classe importante de grupos hiperbólicos é a dos grupos fundamentais de variedades
riemannianas compactas com curvatura negativa. Foi esta classe de grupos que motivou Gromov a
criar o conceito de grupo hiperbólico.
9.3
Propriedades
Num dos resultados mais extraordinários da teoria dos grupos hiperbólicos, geometria e complexidade se encontram de forma inesperada:
Teorema 9.7 (Gromov 1987) Seja G um grupo finitamente apresentável. Então as condições
seguintes são equivalentes:
(i) G é hiperbólico;
(ii) G admite uma função isoperimétrica linear;
(iii) G admite uma função isoperimétrica subquadrática.
Aqui subquadrática significa “melhor que quadrática”! Pelo Corolário 7.10, concluimos que todo
grupo hiperbólico finitamente apresentável tem problema da palavra decidı́vel. Veremos na Secção
10 que todo grupo hiperbólico é automático e logo finitamente apresentável, bem como uma solução
mais construtiva do problema da palavra.
Seja G um grupo hiperbólico gerado pelo conjunto finito A. Isto equivale a considerar um
e∗ → G. Designamos por GeoA (G) o conjunto dos
homomorfismo involutivo sobrejetivo ϕ : A
rótulos de geodésicas em ΓA (G). Note-se que, como ΓA (G) é transitivo nos vértices, todas estas
palavras são rótulo de geodésicas iniciando em qualquer vértice. É habitual chamar também de
geodésicas as palavras de GeoA (G).
e∗ e ε > 0, dizemos que L é ε-lipschitziana (relativamente a ΓA (G)) se, para todas
Dados L ⊆ A
u, v ∈ L,
dA (uϕ, vϕ) ≤ 1 implica dA (u[n] ϕ, v [n] ϕ) ≤ ε para todo n ∈ N.
Esta propriedade é também conhecida como a propriedade dos dois viajantes: imaginemos dois
viajantes que, partindo do mesmo sı́tio, vão percorrer dois caminhos em ΓA (G) com rótulos u e v,
respetivamente. O ritmo é uma aresta por dia! Se eles terminarem seus caminhos a distância ≤ 1,
então em cada dia da viagem eles nunca estarão a distância > ε.
Dizemos que L é lipschitziana se for ε-lipschitziana para algum ε > 0.
79
e∗ → G um homomorfismo involutivo
Teorema 9.8 Seja G um grupo hiperbólico e seja ϕ : A
sobrejetivo com A finito. Suponhamos que ΓA (G) é δ-hiperbólico. Então GeoA (G) é (2δ + 2)lipschitziana.
Prova. Consideremos um triângulo geodésico
5p
u
q0
w
/ q
v
com |w| ≤ 1 em ΓA (G). Temos que mostrar que dA (u[n] ϕ, v [n] ϕ) ≤ 2δ + 2 para todo n ∈ N.
Consideremos as geodésicas no diagrama fatorizadas na forma
u[n]
v [n]
u
n
q0 −−→pn −→p,
v
n
q0 −−→qn −→q.
v
w−1
Suponhamos que vn = 1. Como |u| ≤ |v| + 1 (caso contrário q0 −→q −→p seria uma alternativa
u
mais curta a q0 −→p, absurdo), resulta que dA (u[n] ϕ, uπ) ≤ 1 e logo
dA (u[n] ϕ, v [n] ϕ) = dA (u[n] ϕ, vϕ) ≤ dA (u[n] ϕ, uϕ) + dA (uϕ, vϕ) ≤ 2 ≤ 2δ + 2.
O caso un = 1 é análogo, logo podemos assumir que un , vn 6= 1. Como ΓA (G) é δ-hiperbólico,
z
existe algum m ≤ |u| tal que dA (v [n] π, u[m] ) ≤ δ + 1. Logo existe um caminho qn −→pm com
|z| ≤ δ + 1.
Suponhamos que m > n + δ + 1. Então
v [n]
z
q0 −−→qn −→pm
u[m]
é uma alternativa mais curta à geodésica q0 −−→pm pois
|v [n] | + |z| ≤ n + δ + 1 < m = |u[m] |.
Por outro lado, se m < n − δ − 1, então
z −1
u[m]
q0 −−→pm −−→qn
v [n]
é uma alternativa mais curta à geodésica q0 −−→qn .
Logo |m − n| ≤ δ + 1, pelo que
dA (u[n] ϕ, v [n] ϕ) ≤ dA (u[n] ϕ, u[m] ϕ) + dA (u[m] ϕ, v [n] ϕ) ≤ 2δ + 2
e GeoA (G) é (2δ + 2)-lipschitziana. 80
O resultado seguinte mostra que o conjunto das geodésicas dum grupo hiperbólico tem uma
estrutura simples:
e∗ → G um homomorfismo involutivo
Teorema 9.9 Seja G um grupo hiperbólico e seja ϕ : A
sobrejetivo com A finito. Então GeoA (G) é uma linguagem racional.
Prova. Suponhamos que ΓA (G) é δ-hiperbólico e seja ε = 2δ + 2. Consideremos a bola aberta
B = Bε (1) no espaço métrico (G, dA ). Como A é finito, B é finita. Além disso, 1 ∈ B. Definimos
e
um A-autômato
finito A = (Q, {1}, Q, E) por:
Q = {X ⊆ B | 1 ∈ X};
e ∪ {1})) ∩ B) | X ∈ Q, a ∈ A
e \ (Xϕ−1 )}.
E = {(X, a, ((a−1 ϕ)X(Aϕ
e ∪ {1}), logo E ⊆ Q × A
e × Q e A está bem definido.
Note-se que 1 ∈ X implica 1 ∈ (a−1 ϕ)X(Aϕ
Além disso, A é determinı́stico. Vamos mostrar que L(A) = GeoA (G).
Começamos por mostrar que
u
e ∪ {1})|u| .
se {1}−→X é um caminho em A, então X ⊆ (u−1 ϕ)(Aϕ
(20)
Usamos indução sobre |u|. O caso u = 1 é trivial. Suponhamos que (20) é válido para u e que
u
a
e Então
{1}−→X −→X 0 é um caminho em A com a ∈ A.
e ∪ {1}) ⊆ (a−1 ϕ)(u−1 ϕ)(Aϕ
e ∪ {1})|u| (Aϕ
e ∪ {1}) = (ua)−1 ϕ(Aϕ
e ∪ {1})|ua|
X 0 ⊆ (a−1 ϕ)X(Aϕ
e por indução (20) é válido para todo u.
Seja u ∈ GeoA (G). Vamos mostrar que u ∈ L(A) por indução sobre |u|. O caso |u| = 0 é trivial,
logo assumimos que |u| > 0 e que a implicação é válida para palavras mais curtas. Seja u = va com
v
e Como v ∈ GeoA (G), existe um caminho {1}−→X
a ∈ A.
em A pela hipótese de indução. Temos
a
que mostrar que existe uma aresta da forma X −→X 0 em A, e para isso basta que aϕ ∈
/ X.
Suponhamos que aϕ ∈ X. Por (20), temos
e ∪ {1})|v| ,
X ⊆ (v −1 ϕ)(Aϕ
logo aϕ = (v −1 ϕ)(wϕ) para alguma palavra w tal que |w| ≤ |v|. Logo uϕ = (va)ϕ = wϕ com
|w| < |u|, contradizendo u ∈ GeoA (G). Logo aϕ ∈
/ X e portanto u ∈ L(A). Logo GeoA (G) ⊆ L(A).
Suponhamos que GeoA (G) ⊂ L(A). Seja u ∈ L(A) \ GeoA (G) de comprimento mı́nimo. Como
e Logo v ∈ GeoA (G) por minimalidade
1 ∈ GeoA (G), podemos escrever u = va para alguma a ∈ A.
w
de u. Como u ∈
/ GeoA (G), existe algum caminho 1−→uϕ em ΓA (G) com |w| < |u|. Logo
5 vϕ
v
1
w
a
/ uϕ
é um triângulo geodésico em ΓA (G). Note-se que |w| = |v| ou |w| = |v| − 1 pois qualquer outra
hipótese contradiz |w| < |u| ou v ∈ GeoA (G).
81
v [i]
Como v ∈ GeoA (G) ⊆ L(A), existe em A um caminho {1}−−→Xi para i = 0, . . . , |v|. Vamos
usar indução sobre i para mostrar que
((v [i] )−1 w[i] )ϕ ∈ Xi
(21)
para i = 0, . . . , |v|. O caso i = 0 é trivial, logo assumimos que 0 < i ≤ |v| e que (21) é válido para
e ∪ {1})) ∩ B, logo
i − 1. Seja v [i] = v [i−1] c. Como (Xi−1 , c, Xi ) ∈ E, temos Xi = ((c−1 ϕ)Xi−1 (Aϕ
[i−1]
−1
[i−1]
((v
) w
)ϕ ∈ Xi−1 implica
e ∪ {1}) ⊆ (c−1 ϕ)Xi−1 (Aϕ
e ∪ {1}).
((v [i] )−1 w[i] )ϕ ∈ (c−1 (v [i−1] )−1 w[i−1] )ϕ(Aϕ
Por outro lado,
dA (((v [i] )−1 w[i] )ϕ, 1) = dA (w[i] ϕ, v [i] ϕ) ≤ ε
pois GeoA (G) é ε-lipschitziana pelo Teorema 9.8. Logo ((v [i] )−1 w[i] )ϕ ∈ B e portanto
e ∪ {1})) ∩ B = Xi ,
((v [i] )−1 w[i] )ϕ ∈ ((b−1 ϕ)Xi−1 (Aϕ
provando (21).
Em particular, para i = |v|, obtemos (v −1 w)ϕ ∈ X|v| . Como u = va e uϕ = wϕ, obtemos aϕ =
a
v
(v −1 w)ϕ ∈ X|v| , pelo que não existe nenhuma aresta da forma X|v| −→ . . . em A. Como {1}−→X|v|
é um caminho em A e A é determinı́stico, isto contradiz u ∈ L(A). Logo L(A) = GeoA (G) e
portanto GeoA (G) é uma linguagem racional. Note-se que, mesmo em casos muito simples, GeoA (G) de modo algum determina G. Por
exemplo, se considerarmos o gerador canónico a para os grupos cı́clicos C2 e C3 , com grafos de
Cayley
?•
a
•j
a
*•
a
•o
a
a
•
obtemos
Geoa (C2 ) = {1, a, a−1 } = Geoa (C3 ).
9.4
Exercı́cios
(9.1) Mostre que o grafo
...
•
•
•
•
...
...
•
•
•
•
...
...
•
•
•
•
...
é 2-hiperbólico.
82
(9.2) Considere o grafo do exercı́cio (9.1) e os grafos
•
•
•
•
..
.
..
.
..
.
..
.
...
•
•
•
•
...
...
•
•
•
•
...
...
•
•
•
•
...
..
.
..
.
..
.
..
.
...
...
e
Quais destes grafos são quase-isométricos?
(9.3) Sejam H um grupo hiperbólico e F um grupo finito. Mostre que H × F é hiperbólico.
(9.4) Sejam A = {a, b} e D4 o grupo diedral infinito definido pela apresentação hA | a4 , b2 , bab−1 ai.
(a) Construa o grafo de Cayley ΓA (D4 ).
(b) Calcule GeoA (D4 ).
(9.5) Sejam A = {a, b} e G o grupo fundamental da garrafa de Klein, definido pela apresentação
hA | bab−1 ai.
(a) Construa o grafo de Cayley ΓA (G).
(b) Mostre que G não é hiperbólico.
(9.6) Mostre que o grupo C2 ∗ C2 é virtualmente livre.
[Sugestão: Considere o subgrupo cı́clico gerado pelo produto ab, onde a (respetivamente b)
gera o primeiro (respetivamente segundo) C2 .]
(9.7) Mostre que Iso(n) =
C2 ∗ C2 .
n
2
define uma função isoperimétrica para a apresentação ha, b | a2 , b2 i de
(9.8) Seja A = {a, b} o conjunto canónico de geradores de G = Z × Z e considere a linguagem
racional
[
L=
(aδ bε )∗ ((aδ )∗ ∪ (bε )∗ ).
δ,ε=±1
Mostre que:
83
(a) L ⊆ GeoA (G);
u
(b) dado g ∈ G, existe um e um só caminho em ΓA (G) da forma 1−→g (u ∈ L);
(c) L é 2-lipschitziana (relativamente a ΓA (G)).
84
10
Grupos automáticos
Os grupos automáticos foram oficialmente introduzidos por Cannon, Epstein, Holt, Levy, Paterson
e Thurston num livro publicado em 1992! Esta teoria procura descrever a estrutura de um grupo
utilizando autômatos finitos, e admite também uma abordagem geométrica que generaliza num
certo sentido a teoria dos grupos hiperbólicos.
10.1
Estruturas automáticas
Seja A um alfabeto finito e seja ϕ : A∗ → G um homomorfismo sobrejetivo. Isto equivale a dizer
que A pode ser visto como um conjunto que gera G enquanto monóide. Uma linguagem L ⊆ A∗
diz-se uma secção de ϕ se Lϕ = G. Se ϕ|L : L → G é bijetiva, L diz-se uma transversal de ϕ.
Naturalmente, uma secção não determina a estrutura do grupo. Mas podemos complementar
essa informação do modo que passamos a descrever.
Dada w ∈ A∗ , estamos interessados em exprimir a relação
{(u, v) ∈ L × L | vϕ = (uw)ϕ}
sob a forma de uma linguagem. Como proceder? Uma forma simples de o conseguir é usando a
convolução.
Seja $ um sı́mbolo que assumimos não pertencer a A. Definimos o alfabeto
A$ = (A × A) ∪ (A × {$}) ∪ ({$} × A).
Dadas u, v ∈ A∗ , a convolução u v é a (única) palavra de A∗$ cuja projeção na primeira (respetivamente segunda) componente pertence a u$∗ (respetivamente v$∗ ). Por exemplo,
ab bc = (a, b)(b, c),
ab b = (a, b)(b, $),
1 bc = ($, b)($, c).
Por outras palavras, as palavras u e v são alinhadas à esquerda para produzir uma palavra de A∗$
e o sı́mbolo $ é usado para compensar a possı́vel diferença de comprimento entre u e v.
Para todo w ∈ A∗ , definimos então
Lw = {u v | u, v ∈ L, vϕ = (uw)ϕ} ⊆ A∗$ .
Dizemos que L ⊆ A∗ é uma estrutura automática para ϕ : A∗ → G se:
(E1) L é uma secção racional de ϕ;
(E2) La é racional para todo a ∈ A ∪ {1}.
Se substituirmos (E1) pela condição mais forte
(E1’) L é uma transversal racional de ϕ,
85
dizemos que L é uma estrutura automática com unicidade para ϕ.
Logo uma estrutura automática envolve uma coleção (finita) de |A| + 2 autômatos finitos. Se
a estrutura tiver unicidade, podemos prescindir do autômato reconhecendo L1 , pois este autômato
pode ser facilmente obtido a partir do autômato reconhecendo L substituindo cada rótulo a ∈ A
por (a, a).
Vamos ver em seguida que a existência de uma estrutura automática implica a existência de
uma estrutura automática com unicidade. Mas antes precisamos de introduzir a chamada ordem
lexicográfica:
Seja A um alfabeto finito que supomos totalmente ordenado por <. Definimos uma relação <l
em A∗ do seguinte modo: dados u, v ∈ A∗ ,

|u| < |v|





ou
u <l v se





|u| = |v| e u = wau0 , v = wbv 0 com a, b ∈ A e a < b
É fácil verificar que esta relação é transitiva e tricotômica (isto é, dados u, v ∈ A∗ , ocorre precisamente um dos casos u = v, u <l v ou v <l u). Logo <l é uma ordem total. Como qualquer
subconjunto não vazio tem necessariamente um mı́nimo, <l é uma boa ordem.
Lema 10.1 Seja A um alfabeto finito totalmente ordenado e seja
Ol = {u v | u, v ∈ A∗ , u <l v}.
Então Ol é uma linguagem racional.
Prova. Seja ∆ = {(a, a) | a ∈ A} e P = {(a, b) ∈ A × A | a <l b}. Verifica-se facilmente que
Ol = (A × A)∗ ({$} × A)+ ∪ ∆∗ P (A × A)∗ ,
logo Ol é racional pelo Teorema 2.8. Necessitamos também provar o seguinte lema:
Lema 10.2 Sejam K, L A-linguagens racionais. Então
K L = {u v | u ∈ K, v ∈ L}
é uma A$ -linguagem racional.
Prova. Seja π1 : A∗$ → A∗ o homomorfismo definido por
(a, b)π1 =
a
1
86
se a ∈ A
se a = $
Analogamente definimos o homomorfismo π2 : A∗$ → A∗ considerando a segunda componente.
Temos
A∗ A∗ = (A × A)∗ ((A × {$})∗ ∪ ({$} × A)∗ ),
logo A∗ A∗ é racional. Como
K L = Kπ1−1 ∩ Lπ2−1 ∩ (A∗ A∗ ),
resulta das Proposições 2.5 e 2.9(ii) que K L é racional. Podemos agora provar o resultado anunciado:
Proposição 10.3 Sejam A um alfabeto finito, G um grupo e ϕ : A∗ → G um homomorfismo
sobrejetivo. Se existir uma estrutura automática para ϕ, então existe uma estrutura automática
com unicidade para ϕ.
Prova. Seja L uma estrutura automática para ϕ. Para cada g ∈ G, seja wg o mı́nimo de L ∩ gϕ−1
para a ordem lexicográfica. Definimos
W = {wg | g ∈ G}.
Vamos mostrar que W é uma estrutura automática com unicidade para ϕ.
Seja π2 : A∗$ → A∗ o homomorfismo definido na prova do Lema 10.2. Então (L1 ∩ Ol )π2 é o
conjunto de todas as palavras v ∈ L que admitem uma representação alternativa u <l v, logo
W = L \ (L1 ∩ Ol )π2 .
Como L é uma estrutura automática para ϕ, resulta das Proposições 2.5 e 2.9(i) e do Lema 10.1
que (L1 ∩ Ol )π2 é uma A-linguagem racional. Mas então
W = L ∩ (A∗ \ (L1 ∩ Ol )π2 ),
e resulta da Proposição 2.5 que W é racional.
Resulta da construção de W que W é uma transversal de ϕ. Seja a ∈ A. Temos
Wa = {u v | u, v ∈ W, vϕ = (ua)ϕ} = La ∩ (W W ).
Pelo Lema 10.2, Wa é racional e logo W é uma estrutura automática com unicidade para ϕ. Tal como em casos anteriores, é possı́vel mostrar que a existência de uma estrutura automática
não depende do conjunto de geradores:
Teorema 10.4 Seja G um grupo admitindo uma estrutura automática para o homomorfismo sobrejetivo ϕ : A∗ → G, onde A é um alfabeto finito. Seja ψ : B ∗ → G um outro homomorfismo
sobrejetivo, onde B é um alfabeto finito. Então G admite uma estrutura automática para ψ.
A prova é bastante técnica e não será apresentada aqui.
87
10.2
Caraterização geométrica
A parte mais técnica da manipulação dos grupos automáticos envolve naturalmente as linguagens
La ⊆ A∗$ . Isso pode ser evitado recorrendo ao grafo de Cayley ΓA (G), através da métrica dA e do
conceito de linguagem lipschitziana definida na Subsecção 9.3:
Teorema 10.5 Sejam A um alfabeto finito, G um grupo e ϕ : A∗ → G um homomorfismo sobrejetivo. Seja L ⊆ A∗ uma secção racional de ϕ. Então as condições seguintes são equivalentes:
(i) L é uma estrutura automática para ϕ;
(ii) L é lipschitziana.
Prova. (i) ⇒ (ii). Para cada a ∈ A ∪ {1}, seja Aa um A$ -autômato finito reconhecendo La .
Seja K o maior número de vértices existente nalgum destes autômatos. Vamos mostrar que L é
(2K − 1)-lipschitziana.
e
Sejam u, v ∈ L tais que dA (uϕ, vϕ) ≤ 1. No grafo de Cayley as arestas têm rótulos em A,
mas podemos afirmar que existe a ∈ A tal que vϕ = (ua)ϕ ou uϕ = (va)ϕ. Trocando u com v se
necessário, podemos assumir que vϕ = (ua)ϕ, logo u v ∈ La . Logo existe em Aa um caminho
bem-sucedido da forma
uv
→ q0 −−−→t →
(22)
Seja n ∈ N e seja w = u[n] v [n] . Podemos fatorizar (22) como
w0
w
→ q0 −→q −→t →
z
Seja q −→t uma geodésica de Aa . Então |z| ≤ K − 1. Como z é sufixo de uma palavra em
L(Aa ) = La , podemos escrever z = z1 z2 para alguns z1 , z2 ∈ A∗ . Considerando o caminho
bem-sucedido
w
z
→ q0 −→q −→t →
em Aa , resulta facilmente que wz é necessariamente da forma (u[n] z1 ) (v [n] z2 ), logo (u[n] z1 a)ϕ =
(v [n] z2 )ϕ e portanto
dA (u[n] ϕ, v [n] ϕ) ≤ |z1 az2−1 | ≤ 2K − 1.
Logo L é (2K − 1)-lipschitziana.
(ii) ⇒ (i). Podemos assumir que L é ε-lipschitziana com ε ≥ 1. Definimos
• Q = {g ∈ G | dA (g, 1) ≤ ε},
• E = {(p, x, q) ∈ Q × A$ × Q | q = (xπ1 ϕ)−1 p(xπ2 ϕ)}.
Seja a ∈ A e consideremos o A$ -autômato finito (determinı́stico) Aa = (Q, 1, aϕ, E). Vamos
mostrar que
La = L(Aa ) ∩ (L L).
(23)
88
Seja w ∈ La . Então w = u v para alguns u, v ∈ L tais que vϕ = (ua)ϕ, logo w ∈ L L. Para
0 ≤ n ≤ max {|u|, |v|}, seja un a n-ésima letra de u (se n ≤ |u|) ou 1 (se n > |u|). Analogamente,
definimos vn . Sejam qn = (u[n] ϕ)−1 (v [n] ϕ) e xn = un vn . Vamos mostrar que
x
x
x
1
2
n
q0 −→q
1 −→ . . . −→qn
(24)
é um caminho em Aa .
Como L é ε-lipschitziana, temos qk ∈ Q para todo k. Além disso, se 1 ≤ k ≤ n, então
qk = (u[k] ϕ)−1 (v [k] ϕ) = (uk ϕ)−1 (u[k−1] ϕ)−1 (v [k−1] ϕ)(vk ϕ) = (xk π1 ϕ)−1 qk−1 (xk π2 ϕ),
logo (qk−1 , xk , qk ) ∈ E e portanto (24) é um caminho em Aa . Como q0 = 1 e qn = (uϕ)−1 (vϕ) = aϕ,
resulta que (24) é bem-sucedido e logo x1 x2 . . . xn ∈ L(Aa ), isto é
w = u v = x1 x2 . . . xn ∈ L(Aa ).
Logo
La ⊆ L(Aa ) ∩ (L L).
Reciprocamente, seja x ∈ L(Aa ) ∩ (L L). Então temos x = u v para alguns u, v ∈ L e x é
o rótulo de um caminho bem-sucedido em Aa da forma (24). Como qk = (xk π1 ϕ)−1 qk−1 (xk π2 ϕ)
para k = 1, . . . , n, obtemos
aϕ = qn = (xn π1 ϕ)−1 . . . (x1 π1 ϕ)−1 q0 (x1 π2 ϕ) . . . (xn π2 ϕ)
= (xπ1 ϕ)−1 (xπ2 ϕ) = (uϕ)−1 (vϕ)
e logo (ua)ϕ = vϕ. Resulta que x = u v ∈ La e logo (23) é válido.
Pela Proposição 2.5 e pelo Lema 10.2, La é racional e logo L é uma estrutura automática para
ϕ. Corolário 10.6 Todo grupo hiperbólico é automático.
Prova. Seja G um grupo hiperbólico. Como G é finitamente gerado, podemos tomar um homomorfismo sobrejetivo de monóides ϕ : A∗ → G para algum alfabeto finito A. Podemos estender ϕ
e∗ → G, que designamos também por ϕ.
a um homomorfismo involutivo (sobrejetivo) A
Pelo Teorema 9.9, GeoA (G) é racional, e é obviamente uma secção de ϕ. Por outro lado,
o Teorema 9.8 implica que GeoA (G) é lipschitziana. Logo, pelo Teorema 10.5, GeoA (G) é uma
estrutura automática para ϕ e portanto G é automático. Usaremos o Teorema 10.5 para provar a existência de grupos automáticos não hiperbólicos.
Começamos pelo seguinte lema:
Lema 10.7 Sejam A um alfabeto finito, G um grupo e ϕ : A∗ → G um homomorfismo sobrejetivo.
Seja L uma estrutura automática com unicidade para ϕ. Então existe K > 0 tal que
|u| − |v| ≤ KdA (uϕ, vϕ)
para todos u, v ∈ L.
89
Prova. Para cada a ∈ A, seja Aa um A$ -autômato finito reconhecendo La . Seja K o maior número
de vértices existente nalgum destes autômatos.
Sejam u, v ∈ L. O caso dA (uϕ, vϕ) = 0 é trivial pois a estrutura tem unicidade. Suponhamos
que dA (uϕ, vϕ) = 1. Trocando u e v se necessário, podemos assumir que vϕ = (ua)ϕ para algum
a ∈ A. Logo u v ∈ L(Aa ). Suponhamos que |v| > |u| + K. Seja v = v 0 v 00 com |v 0 | = |u|. Então
temos em Aa um caminho bem-sucedido da forma
uv 0
1v 00
→ i−−−→q −−−→t →
1v 00
Como |v 00 | > K, existe algum vértice repetido no caminho q −−−→t. Logo podemos eliminar um
loop e obter u w ∈ L(Aa ) = La para algum w ∈ L \ {v}. Mas então wϕ = (ua)ϕ = vϕ,
contradizendo a unicidade da estrutura.
Analogamente se exclui o caso |u| > |v| + K, logo |u| − |v| ≤ K e o resultado é válido quando
dA (uϕ, vϕ) = 1.
Finalmente, suponhamos que dA (uϕ, vϕ) = n > 1. Então existe uma sucessão w0 , w1 , . . . , wn ∈
L
tal
que w0 = u, wn = v e dA (wi−1 ϕ, wi ϕ) = 1 para i = 1, . . . , n. Pelo caso anterior, temos
|wi−1 | − |wi | ≤ K para i = 1, . . . , n. Pela desigualdade triangular, obtemos
n
n
X
X
|wi−1 | − |wi | ≤ Kn = KdA (uϕ, vϕ)
|u| − |v| = |wi−1 | − |wi | ≤
i=1
i=1
como pretendı́amos. Vamos agora discutir o produto direto:
Proposição 10.8 O produto direto de grupos automáticos é um grupo automático.
Prova. Para i = 1, 2, seja Li uma estrutura automática com unicidade para o homomorfismo
sobrejetivo ϕi : A∗i → Gi , onde Ai é um alfabeto finito e Gi um grupo. Podemos assumir que
A1 ∩ A2 = ∅. Seja A = A1 ∪ A2 e ϕ : A∗ → G1 × G2 o homomorfismo (sobrejetivo) definido por
ϕ|A∗i = ϕi (i = 1, 2). Vamos mostrar que L1 L2 é uma estrutura automática para ϕ.
Pela Proposição 2.7, L1 L2 é racional, e é claro que L1 L2 é uma transversal de ϕ. Logo, pelo
Teorema 10.5, basta mostrar que L1 L2 é lipschitziana.
Suponhamos que Li é εi -lipschitziana (i = 1, 2) e que K é a constante dada pelo Lema 10.7
para ϕ1 e L1 . Seja
ε = max {ε1 + K + 1, ε2 }.
Vamos mostrar que L1 L2 é ε-lipschitziana.
Sejam ui , vi ∈ Li (i = 1, 2) com dA ((u1 u2 )ϕ, (v1 v2 )ϕ) ≤ 1. Se (u1 u2 )ϕ = (v1 v2 )ϕ, então u1 = v1
e u2 = v2 pois Li é uma estrutura automática com unicidade para i = 1, 2, logo podemos assumir
sem perda de generalidade que (v1 v2 )ϕ = (u1 u2 a)ϕ para algum a ∈ A.
Suponhamos primeiro que a ∈ A2 . Então (v1 v2 )ϕ = (u1 u2 a)ϕ implica v1 ϕ1 = u1 ϕ1 e v2 ϕ2 =
(u2 a)ϕ2 , logo v1 = u1 e u2 v2 ∈ (L2 )a . Logo
(
0
se n ≤ |u1 |
[n]
[n]
dA (((u1 u2 ) )ϕ, ((v1 v2 ) )ϕ) =
[n−|u1 |]
[n−|u1 |]
dA (u2
ϕ, v2
ϕ) ≤ ε2 ≤ ε
se n > |u1 |
90
Suponhamos agora que a ∈ A1 . Então (v1 v2 )ϕ = (u1 u2 a)ϕ implica v1 ϕ1 = (u1 a)ϕ1 e v2 ϕ2 =
u2 ϕ2 , logo u1 v1 ∈ (L1 )a e v2 = u2 . Temos pois a seguinte situação no grafo de Cayley ΓA (G1 ×G2 ):
u2
5•
/•
u1
•
a
v1
···
a
) •
a
/•
v2 =u2
a
Se n ≤ |u1 |, |v1 |, então
[n]
[n]
dA (((u1 u2 )[n] )ϕ, ((v1 v2 )[n] )ϕ) = dA (u1 ϕ, v1 ϕ) ≤ ε1 ≤ ε.
Por outro lado, se n ≥ |u1 |, |v1 |, então
[n−|u |]
[n−|v1 |]
1
dA (((u1 u2 )[n] )ϕ, ((v1 v2 )[n] )ϕ) = dA ((u1 u2
)ϕ, (v1 v2
pois |u1 | − |v1 | ≤ K por definição de K e pela figura anterior.
Suponhamos agora que |v1 | < n < |u1 |. Então
dA (((u1 u2 )[n] )ϕ, ((v1 v2 )[n] )ϕ) =
≤
≤
<
<
[n]
)ϕ) ≤ K + 1
[n−|v |]
1
dA (u1 ϕ, (v1 v2
)ϕ)
[n]
[n−|v1 |]
dA (u1 ϕ, v1 ϕ) + dA (v1 ϕ, (v1 v2
)ϕ)
[n]
[n]
dA (u1 ϕ, v1 ϕ) + n − |v1 |
ε1 + |u1 | − |v1 |
ε1 + K < ε.
O caso |u1 | < n < |v1 |, é análogo, logo L1 L2 é ε-lipschitziana e G1 × G2 é automático. Corolário 10.9 Todo grupo abeliano livre finitamente gerado Z × . . . × Z é automático.
Prova. O grupo livre Z é automático pelo Teorema 9.6 e pelo Corolário 10.6. Aplicando sucessivamente a Proposição 10.8, obtemos o pretendido. Pelo Teorema 9.6(iv), comprovamos que a classe dos grupos automáticos contém estritamente
a dos grupos hiperbólicos.
10.3
Propriedades
Terminamos estudando algumas propriedades dos grupos automáticos. Começamos pelo problema
da palavra:
Teorema 10.10 Todo grupo automático tem problema da palavra decidı́vel.
91
Prova. Seja G um grupo e seja L uma estrutura automática para o homomorfismo sobrejetivo
e∗ → G,
ϕ : A∗ → G, onde A é finito. Estendemos ϕ a um homomorfismo involutivo (sobrejetivo) A
∗
e
que designamos ainda por ϕ. Queremos mostrar que é decidı́vel, dado u ∈ A , se uϕ = 1.
Suponhamos primeiro que u ∈ A∗ , digamos u = a1 . . . an (ai ∈ A). Tomamos v0 ∈ L qualquer.
Para i = 1, . . . , n, determinamos vi ∈ L ∩ (ua1 . . . ai )ϕϕ−1 do seguinte modo:
Suponhamos que vi−1 está definido. Usando os homomorfismos πi : A∗$ → A∗ definidos na prova
do Lema 10.2, basta tomar vi ∈ (Lai ∩ vi−1 π1−1 )π2 . Pelas Proposições 2.5 e 2.9, (Lai ∩ vi−1 π1−1 )π2
é uma linguagem racional e nós podemos calcular efetivamente um dos seus elementos.
Em particular, calculámos vn ∈ L∩(v0 u)ϕ−1 . Agora, para determinar se uϕ = 1, basta verificar
se v0 vn ∈ L1 ou não.
Para provar o caso geral, temos que saber lidar com letras da forma a−1 (a ∈ A). Para começar,
podemos utilizar o caso anterior para determinar w1 ∈ L ∩ 1ϕ−1 : se for necessário, testamos todas
as palavras u ∈ L (que é bem ordenado pela ordem lexicográfica) até encontrar a desejada. Agora
e∗
é fácil encontrar wa−1 ∈ L ∩ a−1 ϕϕ−1 : basta tomar wa−1 ∈ (Lai ∩ w1 π2−1 )π1 . Assim, dada u ∈ A
−1
qualquer, começamos por substituir cada letra a (a ∈ A) em u por wa−1 , obtendo assim uma
palavra u0 ∈ A∗ . Como uϕ = u0 ϕ, basta usar o caso anterior para determinar se u0 ϕ = 1. Vamos agora usar a caraterização geométrica para provar o seguinte resultado. A prova é longa
e por vezes técnica, mas interessante:
Teorema 10.11 Todo grupo automático:
(i) é finitamente apresentável;
(ii) admite uma função isoperimétrica quadrática.
Prova. (i) Seja G um grupo e seja L uma estrutura automática com unicidade para o homomorfismo sobrejetivo ϕ : A∗ → G, onde A é finito. Estendemos ϕ a um homomorfismo involutivo
e∗ → G, que designamos ainda por ϕ. Então existe um homomorfismo sobrejetivo
(sobrejetivo) A
Φ : FA → G tal que o diagrama
e∗ ϕ / G
A
>
θ
Φ
FA
e∗ → FA designa a projeção canónica. Para cada g ∈ G, seja wg o único elemento
comuta, onde θ : A
de L ∩ gϕ−1 .
Pelo Teorema 10.5, L é ε-lipschitziana para algum ε > 0. Seja
R = {u ∈ 1ϕ−1 |u| ≤ 2ε + 2} ∪ {w1 }
e N = hhRθii. É claro que Rθ é um subconjunto finito de Ker(Φ), logo N ⊆ Ker(Φ). Para mostrar
que P = hA | Ri é uma apresentação finita de G, basta mostrar que KerΦ ⊆ N .
92
Começamos por fazer um esboço da prova de que
u v ∈ La ⇒ (uav −1 )θ ∈ N
(25)
para todos u, v ∈ L e a ∈ A.
zn [n]
Seja m = max {|u|, |v|}. Para cada n ∈ {1, . . . , m}, seja u[n] ϕ−→v
ϕ uma geodésica em ΓA (G).
u
v
É claro que |zn | ≤ ε para todo n. Usando estas geodésicas e os caminhos 1−→uϕ e 1−→vϕ, podemos
construir um diagrama de van Kampen (generalizado) de P de bordo uav −1 . Este diagrama diz-se
generalizado porque os relatores de Rθ não são necessariamente palavras ciclicamente reduzidas, e
o mesmo acontece com o bordo. Mas a sua existência garante igualmente que a imagem do bordo
por θ está em N . Exemplificamos a construção do diagrama para u = a1 a2 a3 e v = b1 b2 b3 b4 :
a2
@•
a1
1
b1
z1
/•
a3
/•
z2
b2
/•
/ uϕ
z3
b3
/•
z4
b4
!
/ vϕ
Em geral, cada um dos diagramas interiores tem como bordo uma palavra que é rótulo de um loop
em ΓA (G) e tem comprimento ≤ 2ε + 2, logo pertence a R. Logo (25) é válido.
Em seguida mostramos que
−1
(uwuϕ
)θ ∈ N
(26)
e∗ . Usamos indução sobre |u|.
para todo u ∈ A
O caso |u| = 0 resulta de w1 ∈ R. Suponhamos então que |u| = n > 0 e que (26) é válido para
e Logo
palavras mais curtas. Podemos escrever u = vb para algum b ∈ A.
−1
−1
−1
−1
)θ = (vwvϕ
)θ(wvϕ bwuϕ
)θ.
(uwuϕ
)θ = (vbw(vb)ϕ
(27)
−1 )θ ∈ N por hipótese de indução, basta mostrar que
Como (vwvϕ
−1
(wvϕ bwuϕ
)θ ∈ N.
(28)
Se b ∈ A, usamos diretamente (25), logo podemos assumir que b = a−1 para algum a ∈ A, isto
−1 )θ ∈ N por (25) e logo
é, u = va−1 . Mas então (wuϕ awvϕ
−1
−1
(wvϕ bwuϕ
)θ = ((wuϕ awvϕ
)θ)−1 ∈ N.
Concluimos assim que (28) é válido e portanto (26) também.
Finalmente, seja g ∈ Ker(Φ). Então (26) e w1 ∈ R implicam
−1
−1
g = gθ = (gwgΦ
)θ(wgΦ θ) = (gwgϕ
)θ(w1 θ) ∈ N,
logo Ker(Φ) ⊆ N e P é uma apresentação finita de G.
(ii) Mantendo toda a notação de (i), tomamos a constante K > 0 dada pelo Lema 10.7. Começamos por mostrar que
−1
Area((uwuϕ
)θ) ≤ (K + |w1 | + 1)|u|2
(29)
93
e+ . Usamos indução sobre |u|.
para todo u ∈ A
Suponhamos que |u| ≥ 1 e (29) é válida para palavras mais curtas. Escrevemos u = vb com
e Por (27), temos
b ∈ A.
−1
−1
−1
(uwuϕ
)θ = (vwvϕ
)θ(wvϕ bwuϕ
)θ.
Se v = 1, temos
−1
Area((vwvϕ
)θ) = Area(w1−1 θ) = 1.
Se v 6= 1, obtemos
−1
Area((vwvϕ
)θ) ≤ (K + |w1 | + 1)|v|2
pela hipótese de indução, logo em qualquer caso
−1
−1
Area((uwuϕ
)θ) ≤ (K + |w1 | + 1)|v|2 + 1 + Area((wvϕ bwuϕ
)θ).
(30)
−1 por w b−1 w −1 se necessário) que
Resulta da prova de (25) (substituindo wvϕ bwuϕ
uϕ
vϕ
−1
Area((wvϕ bwuϕ
)θ) ≤ max {|wvϕ |, |wuϕ |}.
Como |w1 | − |wuϕ | ≤ KdA (1, uϕ) ≤ K|u| pelo Lema 10.7, obtemos |wuϕ | ≤ K|u| + |w1 |. Analogamente, |wvϕ | ≤ K|v| + |w1 |, logo
−1
Area((wvϕ bwuϕ
)θ) ≤ K|u| + |w1 |
e logo por (30) é fácil verificar que
−1 )θ) ≤ (K + |w | + 1)|v|2 + 1 + K|u| + |w |
Area((uwuϕ
1
1
≤ (K + |w1 | + 1)(|u| − 1)2 + (K + |w1 | + 1)|u|
≤ (K + |w1 | + 1)|u|2 .
e+ .
Logo (29) é válido para todo u ∈ A
Seja agora g ∈ Ker(Φ). Se g 6= 1, resulta de (29) que
−1
−1
Area(g) = Area((gwgΦ
wgΦ )θ) ≤ Area((gwgϕ
)θ) + Area(w1 θ) ≤ (K + |w1 | + 1)|g|2 + 1
2
≤ (K + |w1 | + 2)|g| .
Como esta desigualdade é trivialmente válida quando g = 1, então G admite uma função isoperimétrica
quadrática. Notamos que, contrariamente ao que acontece com os grupos hiperbólicos, o recı́proco de (ii) não
é válido, pois existem grupos não automáticos admitindo uma função isoperimétrica quadrática.
De fato, nem tudo são sucessos na teoria dos grupos automáticos... por exemplo, ainda hoje
se desconhece se todo grupo automático tem problema da conjugação decidı́vel! Para contornar
esse problema, os criadores do conceito de grupo automático inventaram também os grupos biautomáticos. Na versão autômatos, exige-se que as linguagens a L (onde a convolução é feita à
direita em vez de ser à esquerda) sejam também racionais. Na versão geométrica, considera-se uma
94
versão da propriedade dos dois viajantes em que os caminhos a percorrer no grafo de Cayley devem
começar a distância ≤ 1 e terminar a distância ≤ 1.
O problema da conjugação é decidı́vel para todo grupo biautomático... mas ignora-se se os dois
conceitos são ou não equivalentes, pois todos os exemplos conhecidos de grupos automáticos são
também biautomáticos!
Um outro frustrante problema em aberto é o da existência de um recı́proco para a Proposição
10.8: será que G × H automático implica G e H automáticos?
10.4
Exercı́cios
(10.1) Construa uma estrutura automática L para Z, produzindo explicitamente autômatos finitos
reconhecendo L e as linguagens La .
(10.2) Um grupo diz-se de Burnside se for infinito, finitamente gerado e de torsão. Mostre que um
grupo de Burnside não pode ser automático.
[Sugestão: Considere um loop não trivial num autômato reconhecendo uma estrutura automática de um grupo infinito.]
(10.3) Seja L ⊆ A∗ . Dadas X, Y ⊆ L L, seja
X ◦ Y = {u v | u w ∈ X, w v para algum w ∈ L}.
Mostre que se X e Y são racionais, então X ◦ Y é racional.
[Sugestão: Use projeções πij : (A ∪ {$})3 → (A ∪ {$})2 para i, j ∈ {1, 2, 3} distintos.]
(10.4) Seja L uma estrutura automática para ϕ : A∗ → G. Mostre que Lw é racional para todo
w ∈ A∗ .
[Sugestão: Use o Exercı́cio (10.3).]
(10.5) Indique uma estrutura automática para Z × Z × C3 .
(10.6) Mostre que o produto livre de grupos automáticos é automático.
95
Bibliografia
1. L. Bartholdi e P. V. Silva, Rational subsets of groups, Chapter 23 of the handbook AutoMathA
(aguarda publicação), arXiv:1012.1532, 2010.
2. L. Bartholdi e P. V. Silva, Groups defined by automata, Chapter 24 of the handbook AutoMathA (aguarda publicação), arXiv:1012.1531, 2010.
3. G. B. Baumslag, S. M. Gersten, M. Shapiro e H. Short, Automatic groups and amalgams, J.
Pure Appl. Algebra 76 (1991), 229–316.
4. J. Berstel, Transductions and Context-free Languages, Teubner, Stuttgart, 1979.
5. R. V. Book e F. Otto, String-Rewriting Systems, Springer-Verlag, New York, 1993.
6. D. B. A. Epstein, J. W. Cannon, D. F. Holt, S. V. F. Levy, M. S. Paterson e W. P. Thurston,
Word processing in groups, Jones and Bartlett Publishers, Boston, MA, 1992.
7. E. Ghys e P. de la Harpe (eds), Sur les Groupes Hyperboliques d’après Mikhael Gromov,
Birkhauser, Boston, 1990.
8. I. Kapovich e A. Miasnikov, Stallings foldings and subgroups of free groups, J. Algebra 248
(2002), 608–668.
9. R. C. Lyndon e P. E. Schupp, Combinatorial Group Theory, Springer-Verlag, 1977.
10. J. Sakarovitch, Eléments de Théorie des Automates, Vuibert, Paris, 2003.
11. P. V. Silva, Groups and automata: a perfect match, in M. Kutrib, N. Moreira and R. Reis
(eds.): Proceedings 14th International Workshop on Descriptional Complexity of Formal Systems (DCFS 2012), volume 7386 of LNCS (2012) 50–63.
96
Índice de conceitos
alfabeto, 10
apresentação, 56
finita, 56
área, 63
aresta
central, 50
compatı́vel, 50
de um autômato, 12
de um grafo, 11
árvore geradora, 34
atrator, 54
autômato, 12
aparado, 14
com transições-1, 13
completo, 14
de Stallings, 31
determinı́stico, 13
finito, 12
flor, 31
inverso, 27
involutivo, 27
SFG, 32
sobre um monóide M , 26
automorfismo
de grafos, 11
de grupos, 6
infinito, 43
não trivial, 12
trivial, 12
completado, 44
composição de relações, 13
comprimento
em A∗ , 10
em FA , 22
comutador, 56
concatenação, 10, 43
Conjetura de Hanna Neumann, 39
conjugado, 23
cı́clico, 24
construção de Stallings, 31
convolução, 85
diâmetro, 74
diagrama de van Kampen, 60
bordo de um, 61
diagrama de van Kampen
dimensão de um, 61
dimensão
de um diagrama de van Kampen, 61
de um grupo livre, 23
base
em FA , 23
em A∗ , 10
bordo
de um diagrama de van Kampen, 61
de uma região, 60
do grupo livre, 46
endomorfismo, 49
espaço de Cantor, 45
espaço métrico, 40
compacto, 45
completado de um, 44
completo, 44
discreto, 44
estrutura automática, 85
com unicidade, 86
caminho
bem-sucedido, 12
central, 50
compatı́vel, 50
maximal, 51
fator
em A∗ , 11
em Aω , 43
fecho, 46
função
97
de Dehn, 64
isoperimétrica, 63
exponencial, 63
linear, 63
polinomial, 63
quadrática, 63
recursiva, 63
subquadrática, 79
uniformemente contı́nua, 53
geodésica
num autômato, 36
num grafo, 74, 79
numa árvore geradora, 35
grafo, 11
A-, 12
conexo, 60
δ-hiperbólico, 74
bipartido, 60
completo, 59
conexo, 11
de Cayley, 27
diâmetro de um, 74
finito, 11
hiperbólico, 74
orientado, 11
planar, 59
transitivo nos vértices, 28
grupo, 4
cı́clico, 8
de Artin ortogonal, 70
de Burnside, 95
de grafo, 70
de permutações, 4
de torsão, 23
finitamente apresentável, 56
finitamente gerado, 8
fundamental, 69
hiperbólico, 77
livre, 22
livre de torsão, 23
quociente, 6
residualmente finito, 39
simétrico, 4
virtualmente livre, 78
homomorfismo
de grupos, 5
de monóides, 6
involutivo, 19
núcleo de um, 7
inverso formal, 19
involução, 19
isometria, 75
isomorfismo
de autômatos, 12
de grafos, 11
de grupos, 6
letra, 10
linguagem, 11
ε-lipschitziana, 79
lipschitziana, 79
racional, 13
loop, 13
máquina de Turing, 59
métrica, 40
dos prefixos
em A∗ , 44
em FA , 46
geodésica
num grafo, 74
num grupo, 76
profinita, 41
monóide, 5
livre, 11
núcleo cı́clico, 23
operadores booleanos, 14
ordem, 8
boa, 86
lexicográfica, 86
total, 86
98
palavra, 10
ciclicamente reduzida, 23
infinita, 43
reduzida, 46
irredutı́vel, 17
reduzida, 20
permutação, 4
ponto base, 27
ponto fixo, 49
infinito, 53
regular, 54
singular, 54
prefixo
em A∗ , 11
em Aω , 43
em FA , 22
problema da conjugação, 23
problema da palavra, 23
decidı́vel, 23, 58
generalizado, 34
produto
Γ-, 69
de grafo, 69
direto
de autômatos, 14
de grupos, 8
livre, 67
com amalgamação, 69
forma normal do, 68
propriedade dos dois viajantes, 79
propriedade universal
em A∗ , 10
em FA , 20
quase-isometria
de espaços métricos, 75
de grafos, 76
raio, 46
redução, 16
elementar, 16
região, 60
bordo de uma, 60
exterior, 60
fronteira de uma, 60
relator, 56
repulsor, 54
rótulo
de um caminho, 12
infinito, 43
de uma aresta, 12
secção, 85
sistema de reescrita, 16
confluente, 17
noetheriano, 16
redutor, 16
subconjunto racional, 26
subgrupo, 5
conjugado, 37
de ı́ndice finito, 7
gerado por um subconjunto, 7
ı́ndice de um, 7
normal, 6
gerado por um subconjunto, 56
sucessão
convergente, 44
de Cauchy, 44
limite de uma, 44
sufixo
em A∗ , 11
em Aω , 43
Teorema
de Benois, 25
de Cayley, 6
de Howson, 38
de Marshall Hall, 41
de Nielsen-Schreier, 35
de van Kampen, 69
transversal, 85
triângulo geodésico, 74
ultramétrica, 40
vértice
adjacente, 11
99
de um grafo, 11
inicial, 12
terminal, 12
100