Embed Size (px)
Citation preview
TEORIA GEOMETRICA DE GRUPOS
Curso de pre-doutorado, Universidade Federal da Bahia 2014
Pedro V. Silva
Neste curso, faremos uma digressao por alguns dos grandes desenvolvimentosque a teoria de grupos sofreu nos ultimos 30 anos, dos automatos de Stallingsaos grupos hiperbolicos de Gromov e aos grupos automaticos de Epstein,Thurston et al.... Veremos uma nova e inesperada algebra que se relacionade forma surpreendente com muitas outras areas: combinatoria, geometria,sistemas dinamicos, teoria de automatos e linguagens, topologia.
Indice
1 Grupos 41.1 Grupos de permutacoes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41.2 Nocao abstrata de grupo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41.3 Homomorfismos e quocientes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51.4 Outros conceitos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71.5 Exercıcios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2 Grafos e automatos 92.1 Palavras e linguagens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92.2 Grafos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102.3 Automatos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102.4 Sistemas de reescrita . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152.5 Exercıcios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3 Grupos livres 173.1 Construcao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173.2 Propriedades basicas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193.3 Automatos e subconjuntos racionais . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223.4 Grafos de Cayley . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243.5 Exercıcios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
4 Representacao de subgrupos 284.1 Construcao de Stallings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 284.2 Aplicacoes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314.3 A metrica profinita . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 354.4 Exercıcios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
5 Bordo de um grupo livre 395.1 Palavras infinitas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 395.2 A metrica dos prefixos e o espaco de Cantor . . . . . . . . . . . . . . . . . . . . . . . . 395.3 Construcao do bordo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 415.4 Exercıcios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
6 Pontos fixos de endomorfismos 446.1 O subgrupo dos pontos fixos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 446.2 Pontos fixos no bordo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 476.3 Exercıcios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
7 Apresentacoes de grupos 507.1 Geradores e relatores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 507.2 Grupos finitamente apresentaveis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 507.3 Decidibilidade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 527.4 Diagramas de van Kampen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 537.5 Funcoes isoperimetricas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
2
7.6 Exercıcios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
8 Produto livre e generalizacoes 608.1 Produto livre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 608.2 Generalizacoes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 628.3 Grupos de grafo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 638.4 Exercıcios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
9 Grupos hiperbolicos 679.1 Grafos hiperbolicos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 679.2 Grafos de Cayley hiperbolicos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 699.3 Propriedades . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 719.4 Exercıcios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
10 Grupos automaticos 7710.1 Estruturas automaticas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7710.2 Caraterizacao geometrica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7910.3 Propriedades . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8310.4 Exercıcios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
Bibliografia 87
Indice de conceitos 88
3
1 Grupos
Comecamos este curso lembrando fatos basicos sobre grupos que ja foram estudados na graduacao.
1.1 Grupos de permutacoes
Uma grande parte da Matematica e dedicada ao estudo de funcoes. E dentro do estudo das funcoes,merece destaque o estudo das permutacoes. Uma permutacao de um conjunto X e simplesmenteuma funcao bijetiva σ : X → X.
A primeira vista, o conceito parece um pouco restritivo... a maior parte das funcoes nao saobijetivas... mas muitas funcoes importantes, na Matematica e fora dela, sao bijetivas:
• Algebra linear: isomorfismos de um espaco vetorial.
• Topologia: homeomorfismos de espacos metricos/topologicos.
• Sistemas dinamicos: em geral, as transformacoes consideradas sao homeomorfismos.
• Fısica quantica: as transformacoes na mecanica quantica assumem-se reversıveis (e bijetivas).
Uma das coisas mais importantes e uteis que se podem fazer com funcoes e compo-las. E claroque a composicao de duas permutacoes de um conjunto X e ainda uma permutacao de X. E a funcaoinversa de uma permutacao de X e ainda uma permutacao de X. Estas duas operacoes (composicaoe inversao) sao fundamentais na construcao do conceito de grupo de permutacoes:
Seja SX o conjunto de todas as permutacoes do conjunto X e seja 1X a permutacao identidade.Dizemos que G ⊆ SX e um grupo de permutacoes se:
• G e fechado para composicao;
• 1X ∈ G;
• a permutacao inversa de uma permutacao em G esta tambem em G.
Eis alguns exemplos de grupos de permutacoes:
• SX (diz-se o grupo simetrico sobre X);
• o conjunto dos automorfismos de um espaco vetorial;
• o conjunto dos auto-homeomorfismos de um espaco metrico/topologico;
1.2 Nocao abstrata de grupo
Historicamente, o estudo dos grupos comecou por ser o estudo dos grupos de permutacoes, e emmuitos casos grupos bem concretos que interessavam a Fısica e a varias areas da Matematica. Nasegunda metade do seculo XIX, apareceu uma outra perspetiva do conceito de grupo, bem maisabstrata, que dispensava permutacoes e composicao. Na versao abstrata, um grupo e um conjuntonao vazio G, no qual esta definida uma operacao binaria · : G × G → G satisfazendo as seguintespropriedades:
4
(G1) Associatividade: a · (b · c) = (a · b) · c para todos a, b, c ∈ G.
(G2) Existencia de elemento neutro: existe um elemento 1G ∈ G tal que 1G · a = a · 1G = a paratodo a ∈ G.
(G3) Existencia de inversos: para todo a ∈ G, existe um elemento b ∈ G tal que a · b = b · a = 1G.
E facil mostrar que o elemento neutro e unico e que cada elemento tem um unico inverso. Emgeral, designamos o neutro por 1 e o inverso de a por a−1. Se so exigirmos (G1) e (G2), a estruturae chamada de monoide.Exemplo 1.1 Seja n ∈ N e seja GLn(R) o conjunto de todas as matrizes n × n invertıveis comentradas reais. Entao GLn(R), com o produto de matrizes, constitui um grupo.
E claro que todo grupo de permutacoes satisfaz os axiomas (G1) – (G3), pois a composicao defuncoes e asociativa, a identidade funciona como elemento neutro e cada permutacao inversa e uminverso no sentido de (G3). Veremos mais adiante que os dois conceitos de grupo (o abstrato e ode grupo de permutacoes) sao essencialmente equivalentes. Mas primeiro necessitamos de relembraralguns conceitos basicos.
Seja G um grupo (quando falamos de um grupo abstrato generico, dispensamo-nos de referir aoperacao binaria · 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, entao ab ∈ H;
• se a ∈ H, entao a−1 ∈ H.
Isto equivale a dizer que H e ele proprio um grupo quando consideramos a restricao a H ×H daoperacao binaria em G.Exemplo 1.2 Seja n ∈ N e seja SLn(R) o conjunto de todas as matrizes n× n com entradas reaise determinante 1. Entao 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 funcaoϕ : G→ H e um homomorfismo (de grupos) se (ab)ϕ = (aϕ)(bϕ) para todos a, b ∈ G.
Se ϕ : G→ H e um homomorfismo, entao e facil verificar as seguintes propriedades:
• 1Gϕ = 1H ;
• a−1ϕ = (aϕ)−1 para todo a ∈ G.
Um isomorfismo bijetivo e um isomorfismo. Dois grupos G e H dizem-se isomorfos (e escrevemosG ∼= H) se existir um isomorfismo ϕ : G→ H. Note-se que nesse caso a funcao inversa ϕ−1 : H → Ge tambem um isomorfismo. Um isomorfismo de um grupo nele proprio e um automorfismo.
Analogamente se define homomorfismo de monoides, mas exige-se tambem a igualdade 1ϕ = 1,pois no caso dos monoides esta nao resulta automaticamente da igualdade (ab)ϕ = (aϕ)(bϕ).
Podemos agora estabelecer a mencionada equivalencia entre os conceitos de grupo (abstrato) egrupo de permutacoes (Teorema de Cayley):
5
Teorema 1.3 (Cayley 1854, Jordan 1870) Todo grupo e isomorfo a algum grupo de permutacoes.
Prova. Seja G um grupo e seja SG o grupo simetrico sobre o conjunto G. Dado g ∈ G, seja σg ∈ SGa permutacao definida por aσg = ag. Seja H = {σg | g ∈ G}. Temos
• σ1 = 1G,
• σgh = σgσh,
• σ−1g = σg−1
para todos g, h ∈ G, logo H e um subgrupo de SG. Finalmente, σ : G → H e um isomorfismo (ainjetividade resulta de g 6= h⇒ 1σg 6= 1σh). �
Vamos agora introduzir o conceito de grupo quociente. A ideia e fazer uma particao dos elementosde um grupo G em classes de equivalencia [g] (g ∈ G) de forma a que o conjunto das classes possaconstituir um grupo sob a operacao induzida
[g][h] = [gh] (g, h ∈ G).
Para que esta operacao esteja bem definida e de efetivamente origem a um grupo, e preciso que aclasse 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 seaNa−1 = N para cada a ∈ G.
Alem do mais, verifica-se que para cumprir o nosso programa precisamos que a particao sejaconstituıda por classes da forma [a] = aN = Na. Isto conduz-nos ao conceito de grupo quociente:
Seja G um grupo e N EG. Seja G/N = {Na | a ∈ G} com a operacao binaria (Na)(Nb) = Nab.Entao G/N constitui um grupo, que se diz o grupo quociente de G por N .Exemplo 1.4 SLn(R)EGLn(R) para todo n ∈ N.
De fato, se P ∈ GLn(R), entao det(P−1) = (det(P ))−1, logo det(M) = 1 implica det(PMP−1) =(det(P ))(det(M))(det(P−1)) = 1, e o subgrupo e normal. O grupo quociente consiste entao em todasos conjuntos de matrizes do tipo (SLn(R))M (M ∈ GLn(R)). Podemos encontrar uma descricao maissimples?
A resposta e dada com a ajuda dos teoremas do homomorfismo, que relacionam homomorfismose quocientes. E claro que se N EG, entao a projecao canonica
πN : G→G/Na 7→Na
e um homomorfismo. Por outro lado, dado um homomorfismo de grupos ϕ : G→ H, o nucleo de ϕe definido por Ker(ϕ) = 1ϕ−1.Teorema 1.5 Seja ϕ : G→ H um homomorfismo de grupos. Entao:
(i) Ker(ϕ)EG;
(ii) se N EG e N ⊆ Ker(ϕ), entao existe um e um so homomorfismo de grupos Φ : G/N → H talque πNΦ = ϕ,
Gϕ //
πN
��
H
G/N
Φ
<<zz
zz
6
dado por (Na)Φ = aϕ;
(iii) se ϕ for sobrejetivo e N = Ker(ϕ), entao Φ e um isomorfismo.
A prova e simples, e ja foi estudada em cursos de algebra na graduacao.Agora podemos revisitar o grupo quociente do Exemplo 1.4. Seja R∗ o grupo constituıdo por
R \ {0}, com a operacao produto.Exemplo 1.6 GLn(R) /SLn(R) ∼= R∗.
Consideremos ϕ : GLn(R)→ R∗ definida por Mϕ = det(M). Como
det(MM ′) = (det(M))(det(M ′))
para todas matrizes M,M ′ ∈ GLn(R), ϕ e um homomorfismo, alem 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 numerofinito de elementos g1, . . . , gn ∈ G. Nesse caso, o menor n possıvel diz-se o ındice de H em G edesigna-se por [G : H].
Dado X ⊆ G, e facil 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 〈X〉. Um (sub)grupo diz-se finitamentegerado se puder ser gerado por um subconjunto finito. Usaremos a notacao H ≤f.g. G para exprimirque H e um subgrupo finitamente gerado de G.
Nem todo grupo e finitamente gerado: para quem dominar argumento de cardinalidade, e facil verque todo o grupo finitamente gerado e enumeravel, e existem grupos nao enumeraveis (por exemplo,o grupo aditivo dos reais).
Um grupo gerado por um unico elemento diz-se um grupo cıclico. A menos de isomorfismo,(Z,+) e o unico grupo cıclico infinito. Dado n ≥ 1, existe tambem um unico grupo cıclico com nelementos a menos de isomorfismo, e e designado por Cn. Se Cn = 〈a〉, entao
Cn = {a, a2, . . . , an−1, an = 1}.
Dado um elemento a de um grupo G, a ordem de a e a cardinalidade do subgrupo 〈a〉. Umelemento pode ter ordem finita ou infinita.
Dados grupos G e H, podemos definir uma operacao em G×H atraves de
(g, h)(g′, h′) = (gg′, hh′).
Com esta operacao, G×H e um grupo que se diz o produto direto dos grupos G e H.
7
1.5 Exercıcios
(1.1) Seja
G =(
R∗ R0 R∗
)com a operacao produto de matrizes. Mostre que:
(a) G e um grupo;
(b)
H =(
1 Z0 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.
(b) Mostre que nesse caso (G×H)/H ∼= G.
(1.3) Seja G = R× R∗ com a operacao
(x, y)(x′, y′) = (x+ yx′, yy′).
Mostre que:
(a) G e um grupo;
(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−1Hb.
(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 numero finito de subgrupos da forma xHx−1 (x ∈ G).
8
2 Grafos e automatos
O conceito de automato e fundamental na teoria da computacao, e tem-se revelado da maior utilidadepara a moderna teoria de grupos. Vamos apresentar em seguida alguns conceitos e resultados basicos.
2.1 Palavras e linguagens
Neste contexto, usamos o termo alfabeto para designar um conjunto e os seus elementos sao chamadosde letras. Muito apropriadamente, uma sequencia finita de letras e chamada de palavra. Isto inclui apalavra vazia, que convencionamos representar pelo sımbolo 1. As palavras nao vazias (no alfabetoA) sao geralmente representadas na forma a1a2 . . . an com a1, . . . , an ∈ A. O comprimento da palavraa1 . . . 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 nao faremos mais referenciasa esse fato. O conjunto de todas as palavras em A e designado por A∗, e A e identificado com oconjunto das palavras de comprimento 1. Escrevemos tambem A+ = A∗ \ {1}.
Podemos definir um produto em A∗, dito de concatenacao. Para palavras nao vazias, e definidopor
(a1 . . . an)(b1 . . . bm) = a1 . . . anb1 . . . bm,
e a palavra vazia funciona como elemento neutro. Com esta operacao, A∗ e um monoide. Mas naoe um monoide qualquer, pois satisfaz a seguinte propriedade (dita universal):Proposicao 2.1 Seja ϕ : A → M uma funcao de A num monoide M qualquer. Entao existe umunico homomorfismo de monoides Φ : A∗ →M que estende a funcao ϕ:
Aϕ //
� _
��
M
A∗Φ
>>||
||
Prova. E facil ver que Φ tem que ser definido por (a1 . . . an)Φ = (a1ϕ) . . . (anϕ) e 1Φ = 1, e que erealmente um homomorfismo de monoides. �
O significado desta propriedade e que A tem em relacao a A∗ o mesmo comportamento que a basede um espaco vetorial V tem em relacao a V , quando substituımos homomorfismos por aplicacoeslineares. Logo podemos pensar em A como uma base de A∗. As diferencas sao as seguintes:
• Nem todo monoide tem uma base: a menos de isomorfismo, so os monoides da forma A∗ temuma base.
• A e a unica base de A∗.
Como A∗ satisfaz a propriedade universal relativamente a A, diz-se o monoide livre sobre A.Certas relacoes entre palavras sao 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∗;
9
• u e um fator de v se v = xuy para algumas x, y ∈ A∗.
Um subconjunto de palavras emA e chamado deA-linguagem, ou simplesmente linguagem quandoo alfabeto esta implıcito ou e irrelevante. A teoria de linguagens e um ramo importante da teoriada computacao que pretende classificar as linguagens e explorar o potencial algorıtmico das diversassubclasses. O trabalho pioneiro de Noam Chomsky nos anos 50 esta na sua origem, pelo que ateoria de linguagens se desenvolveu inicialmente no seio da Linguıstica e nao da Informatica ou daMatematica. A teoria deve importantes contribuicoes ao informatico brasileiro Imre Simon.
Se L e uma A-linguagem, e habitual designar por L∗ o conjunto de todas as palavras do tipou1u2 . . . 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 submonoide de A∗ gerado por L. E desagradavel que se tenha instucionalizado o uso da notacao∗ com dois significados diferentes (monoide livre e submonoide gerado por), mas felizmente nao haconfusao quando escrevemos A∗.
2.2 Grafos
Os grafos sao estruturas combinatorias que desempenham um papel muito importante em variasareas da Matematica, pura ou aplicada, e da Computacao.
Neste curso, designaremos por grafo uma estrutura do tipo Γ = (V,E), onde V e um conjuntonao vazio (o conjunto dos vertices) e E um conjunto de pares (nao ordenados) de elementos deV (arestas). E habitual descrever um grafo geometricamente utlizando pontos para representar osvertices e linhas para representar as arestas. Eis um exemplo de um grafo com 7 vertices e 5 arestas:
•
@@@@@@@
•
~~~~~~~• • • • •
Note-se que nenhuma aresta pode ligar um vertice a si proprio!Um grafo com um numero finito de vertices diz-se finito. Dois vertices dizem-se adjacentes se
estiverem ligados por uma aresta. O grafo diz-se conexo se quaisquer dois vertices estiverem ligadospor uma sequencia de arestas (isto e, se pertencerem a uma sequencia de vertices adjacentes).
Um isomorfismo de grafos estabelece uma bijecao entre os vertices que preserva a adjacencia (istoe, a estrutura e a mesma a menos da designacao dos vertices). Dois grafos sao isomorfos se houverum isomorfismo entre eles. Um isomorfismo de um grafo nele proprio e um automorfismo.
Uma variante deste conceito e a nocao de grafo orientado, em que cada aresta esta dotada de umaorientacao especıfica. Formalmente, um grafo orientado e uma estrutura do tipo Γ = (V,E), onde Ve um conjunto nao vazio e E ⊆ V × V . E habitual descrever um grafo orientado geometricamenteutlizando pontos para representar os vertices e setas para representar as arestas. Eis um exemplo deum grafo orientado com 4 vertices e 4 arestas:
• ** •jj •oo • ee
2.3 Automatos
Um automato pode ser descrito informalmente como um grafo orientado em que as arestas temrotulos que nao sao mais do que letras de um certo alfabeto finito. Alem disto, alguns verticessao chamados de iniciais e outros (que podem ser ou nao os mesmos!) de terminais. Tambem e
10
habitual utilizar uma representacao geometrica, em que os vertices iniciais (respetivamente finais)sao identificados por uma seta que entra (respetivamente sai), sem rotulo:Exemplo 2.2 Automato no alfabeto A = {a, b}:
•
b
�� a**//oo •
a
jjb
pp
Formalmente, se A e um alfabeto finito, um A-automato e uma estrutura do tipo A = (Q, I, T,E),onde
• Q e um conjunto finito;
• E ⊆ Q×A×Q;
• I, T ⊆ Q.
O conjunto Q e o conjunto dos vertices, I e o conjunto dos vertices iniciais, T e o conjunto dosvertices terminais e E e o conjunto das arestas. Se nao designarmos vertices iniciais nem terminais,temos a estrutura simplificada (Q,E), que se diz um A-grafo.
O automato A = (Q, I, T,E) diz-se finito se Q for finito. Dois automatos A = (Q, I, T,E) eA′ = (Q′, I ′, T ′, E′) dizem-se isomorfos se existir uma bijecao ϕ : Q→ Q′ tal que Iϕ = I ′, Tϕ = T ′ e
(p, a, q) ∈ E ⇔ (pϕ, a, qϕ) ∈ E′
para todos p, q ∈ Q e a ∈ A (isto e, tem a mesma estrutura a menos da designacao dos vertices).A grande utilidade de um A-automato e que ele permite definir uma A-linguagem do seguinte
modo:Um caminho nao trivial em A = (Q, I, T,E) e uma sequencia
q0a1−→q1
a2−→ . . .an−→qn
tal que (qi−1, a, qi) ∈ E para i = 1, . . . , n. O seu rotulo e a palavra a1 . . . an ∈ A∗. Diz-se um caminhobem-sucedido se q0 ∈ I e qn ∈ T . Consideramos tambem o caminho trivial q 1−→q para cada q ∈ Q(o rotulo e a palavra vazia 1), que e bem-sucedido se q ∈ I ∩ T . Representamos por p u−→q qualquercaminho de rotulo u ligando p a q. Um caminho que comeca e termina no mesmo vertice diz-se umloop.
A linguagem L(A) reconhecida por A e o conjunto dos rotulos dos caminhos bem-sucedidos emA. Uma A-linguagem L diz-se racional se L = L(A) para algum A-automato finito A.Exemplo 2.3 A linguagem do automato do Exemplo 2.2 e o conjunto de todas as palavras no alfabetoA = {a, b} onde a letra a ocorre um numero par de vezes.
Um A-automato A = (Q, I, T,E) diz-se determinıstico se tiver um unico 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 automato ser determinıstico e que, para testar seuma palavra u e reconhecida pelo automato, basta considerar no maximo um caminho de rotulo u apartir do estado inicial.
11
Por outro lado, podemos alargar o conceito de automato admitindo tambem arestas com rotulo1: sao os automatos com transicoes-1. O teorema seguinte mostra que estas 3 versoes de automatosao equivalentes no que respeita a linguagens:Proposicao 2.4 Seja L uma A-linguagem. As condicoes seguintes sao equivalentes:
(i) L e racional;
(ii) L = L(A) para algum A-automato finito determinıstico A;
(iii) L = L(A) para algum A-automato finito com transicoes-1 A;
(iv) existe um homomorfismo de monoides ϕ : 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-automato finito com transicoes-1 tal que L = L(A).
Seja M = 2Q×Q o conjunto de todas as relacoes binarias no conjunto Q. Dadas R,S ∈ M , a suacomposicao e definida por
R ◦ S = {(p, q) ∈ Q×Q | (p, r) ∈ R, (r, s) ∈ S para algum r ∈ Q}.
Esta operacao e associativa e a relacao identidade 1Q funciona como elemento neutro, logo M e defato um monoide (finito).
Definimos uma funcao ϕ : A∗ →M do seguinte modo. Seja 1ϕ = 1Q. Para toda palavra u ∈ A+,fazemos
uϕ = {(p, q) ∈ Q×Q | existe um caminho p u−→q em A}.
Como (uv)ϕ = (uϕ) ◦ (vϕ) para todas u, v ∈ A∗, entao ϕ e um homomorfismo de monoides.Claro que L ⊆ Lϕϕ−1. Reciprocamente, suponhamos que uϕ = vϕ com v ∈ L. Entao existe um
caminho I 3 i v−→t ∈ T em A. Se u, v 6= 1, e imediato que existe tambem um caminho i u−→t, logou ∈ L.
Suponhamos agora que v = 1 e u 6= 1. Como uϕ = vϕ, existe um ciclo i u−→i e logo um caminhoiu−→i 1−→t, donde resulta que u ∈ L.
Finalmente, se u = 1, podemos assumir que v 6= 1. Como uϕ = vϕ, resulta que t = i e logou ∈ 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ϕ)}.
E claro que A e um A-automato finito determinıstico. Alem disso, p u−→q e um caminho se e so seq = p(uϕ). Logo
L(A) = {u ∈ A∗ | 1M (uϕ) ∈ Lϕ} = Lϕϕ−1 = L
e a prova esta completa. �
Para alem do determinismo, ha outras propriedades importantes de automatos. Dizemos que umautomato A = (Q, I, T,E) e:
• aparado se todo vertice ocorre nalgum caminho bem-sucedido;
• completo se, para todos p ∈ Q e a ∈ A, existe alguma aresta da forma (p, a, q).
12
A seguir mostramos que o conjunto das A-linguagens racionais e fechado para os operadoresbooleanos:Proposicao 2.5 Sejam K,L A-linguagens racionais. Entao as linguagens K ∪ L, K ∩ L e A∗ \ Lsao racionais.
Prova. Como K∩L = A∗\((A∗\K)∪(A∗\L)), basta mostrar o resultado para uniao e complemento.Para a uniao, tomamos a uniao disjunta de dois automatos reconhecendo K e L.Para o complemento, recordamos que na prova de (iv) ⇒ (ii) da Proposicao 2.4 construimos um
automato finito que alem de determinıstico e completo. Se trocarmos os vertices terminais pelosnao-terminais num tal automato, passaremos a reconhecer o complemento da linguagem. �
No entanto, ha um metodo mais construtivo de lidar com a intersecao: dados A-automatosA = (Q, I, T,E) e A′ = (Q′, I ′, T ′, E′), definimos o produto direto A×A′ = (Q×Q′, I×I ′, T×T ′, E′′)com
E′′ = {((p, p′), a, (q, q′)) | (p, a, q) ∈ E, (p′, a′, q′) ∈ E′}.
Proposicao 2.6 Dados A-automatos A e A′, L(A×A′) = L(A) ∩ L(A′).
Prova. Basta observar que os caminhos bem sucedidos em A×A′ sao da forma
→ (q0, q′0) a1−→(q1, q
′1) a2−→ . . .
an−→(qn, q′n)→,
com a1, . . . , an ∈ A, onde→ q0
a1−→q1a2−→ . . .
an−→qn →
e um caminho bem sucedidos em A e
→ q′0a1−→q′1
a2−→ . . .an−→q′n →
e um caminho bem sucedidos em A′. �
A classe das linguagens racionais tambem e fechada para os operadores produto e estrela:Proposicao 2.7 Sejam K,L A-linguagens racionais. Entao as linguagens KL e K∗ sao racionais.
Prova. Suponhamos que A = (Q, I, T,E) e A′ = (Q′, I ′, T ′, E′) sao A-automatos finitos recon-hecendo K e L, respetivamente. POdemos assumir que Q∩Q′ = ∅. Definimos um A-automato finitocom transicoes-1
B = (Q ∪Q′, I, T ′, E ∪ E′ ∪ (T × {1} × I ′)).
// i **A tjj
1
��========
i′++A′ t′kk //
Os caminhos bem-sucedidos em B sao da forma
I 3 i u−→t 1−→i′ v−→t′ ∈ T ′
com t ∈ T , i′ ∈ I ′, u ∈ K e v ∈ L, logo
L(B) = {uv | u ∈ K, v ∈ L} = KL.
13
Por outro lado, seja z /∈ Q. Definimos um A-automato finito com transicoes-1
B′ = (Q ∪ {z}, z, z, E ∪ ({z} × {1} × I) ∪ (T × {1} × {z})).
i **A tjj
1����������
oo // z1
__????????
E facil ver que L(B′) = K∗.Pela Proposicao 2.4, as linguagens KL e K∗ sao racionais. �
Como as linguagens finitas sao obviamente racionais, resulta das Proposicoes 2.5 e 2.7 que qual-quer linguagem obtida a partir de linguagens finitas utilizando um numero finito de vezes os oper-adores uniao, produto e estrela e necessariamente racional. O recıproco e tambem verdadeiro:Teorema 2.8 (Kleene 1956) Seja L ⊆ A∗. Entao as condicoes seguintes sao equivalentes:
(i) L e racional;
(ii) L pode ser obtida a partir de A-linguagens finitas utilizando um numero finito de vezes osoperadores uniao, produto e estrela.
A demonstracao de (i) ⇒ (ii) e proposta no Exercıcio 2.8.Podemos tambem mostrar que as linguagens racionais se comportam muito bem relativamente a
homomorfismos:Proposicao 2.9 Sejam A,B alfabetos finitos e ϕ : A∗ → B∗ um homomorfismo de monoides.
(i) Se K ⊆ A∗ e racional, entao Kϕ e racional.
(ii) Se L ⊆ B∗ e racional, entao Lϕ−1 e racional.
Prova. (i) Seja A um A-automato finito reconhecendo K. Substituindo cada rotulo a em A poruma aresta ou sucessao de arestas de rotulo aϕ, obtemos um B-automato finito (com transicoes-1 se1 ∈ Aϕ) que reconhece Kϕ. Pela Proposicao 2.4, Kϕ e racional.
(ii) Seja L′ = L ∩ (A∗ϕ). Pelas alınea (i) e pela Proposicao 2.5, L′ e racional. Pela Proposicao2.4, existe um homomorfismo de monoides θ : B∗ → M com M finito tal que L′ = L′θθ−1. Sejaψ : A∗ →M o homomorfismo definido por ψ = ϕθ. Entao
(L′ϕ−1)ψψ−1 = L′ϕ−1ϕθθ−1ϕ−1 = L′θθ−1ϕ−1 = L′ϕ−1,
logo L′ϕ−1 e racional. Como Lϕ−1 = L′ϕ−1, resulta que Lϕ−1 e racional. �
14
2.4 Sistemas de reescrita
Os sistemas de reescrita sao uma ferramenta importante na algebra e na teoria da computacao.Vamos apresentar algumas nocoes basicas que serao uteis 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 relacao binaria em A!). Recebem aqui um nome diferente porque vamos usa-los numa perspetivadiferente: vao-nos permitir substituir fatores dentro de palavras:
Dadas u, v ∈ A∗, escrevemos u−→R v (reducao elementar) se existirem (r, s) ∈ R e x, y ∈ A∗ taisque u = xry e v = xsy. Escrevemos u−→∗R v (reducao) se u = v ou se existir alguma cadeia
x = z0−→R z1−→R . . . −→R zm = y.
Sempre que nao haja confusao possıvel, omitimos o ındice R.Dizemos que R e:
• redutor se |r| > |s| para todo (r, s) ∈R;
• noetheriano se nao existir nenhuma cadeia infinita de reducoes elementares
w0−→Rw1−→Rw2−→R . . .
• confluente se, sempre que u−→∗v e u−→∗w, existir alguma z ∈ A∗ tal que v−→∗z e w−→∗z:
u ∗ //
∗��
v
∗�����
w ∗//___ z
E claro que todo sistema de reescrita redutor e necessariamente noetheriano. Uma palavra u ∈ A∗e irredutıvel se nao existir v ∈ A∗ tal que u−→v. Seja Irr(R) o conjunto de todas as palavrasirredutıveis de A∗ com respeito a R.Proposicao 2.10 Seja R ⊆ A∗ × A∗ um sistema de reescrita noetheriano e confluente. Para todapalavra u ∈ A∗, existe uma e uma so v ∈ Irr(R) tal que u−→∗v.
Prova. O ser noetheriano garante a existencia, a confluencia garante a unicidade. �
2.5 Exercıcios
(2.1) Seja M um monoide finito nao trivial. Mostre que a propriedade universal nao e valida paranenhum subconjunto de M , e que portanto M nao possui uma base.
(2.2) Quantos grafos de 4 vertices existem, a menos de isomorfismo?
(2.3) Quantos grafos orientados de 2 vertices existem, a menos de isomorfismo?
(2.4) Seja A = {a, b}. Construa um A-automato finito reconhecendo cada uma das seguintes A-linguagens:
(a) {palavras acabando em aba};
15
(b) {palavras de comprimento par}.
(2.5) Seja A = {0, 1}. Construa um A-automato finito reconhecendo todos os numeros naturaisdivisıveis por 3, escritos em binario.
(2.6) Considere os seguintes automatos:
oo // • a //
b
��•
b~~}}}}}}}}oo // • b //
a
��•
b��~~~~~~~
a
��
•b
``AAAAAAAA•
b
``@@@@@@@
a
BB
A B
(a) Determine L(A) e L(B).
(b) Construa um automato finito reconhecendo L(A) ∩ L(B).
(2.7) Seja A = {a, b} e seja A o A-automato com transicoes-1 descrito por
// 1b
**
a
��2
1
jj
a
��//
Usando os algoritmos implıcitos na prova da Proposicao 2.4, construa um automato finitodeterminıstico completo que reconheca A∗ \ L(A).
(2.8) Seja A um alfabeto finito e seja A = (Q, 0, T, E) um A-automato com Q = {0, . . . ,m}. Dadosp, q ∈ Q e k ∈ {0, . . . ,m + 1}, seja L
(k)p,q o conjunto dos rotulos dos caminhos p−→q em que
todos os vertices intermedios sao < k.
(a) Mostre queL(k+1)p,q = L(k)
p,q ∪ L(k)p,k(L
(k)k,k)∗L
(k)k,q
para todos p, q, k ∈ Q.
(b) Usando recursivamente a alınea (a), demonstre a implicao (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).
16
3 Grupos livres
Nesta seccao definimos os grupos livres e estudamos algumas das suas propriedades basicas.
3.1 Construcao
Seja A um alfabeto. Queremos que o grupo livre sobre A seja um grupo que satisfaca a propriedadeuniversal na classe dos grupos (analogamente a Proposicao 2.1).
Comecamos por introduzir um conjunto A−1 de inversos formais of A (i.e. a 7→ a−1 define umabijecao de A com um conjunto A−1 disjunto de A). Usando a notacao A = A ∪ A−1, estendemosindutivamente a funcao a 7→ a−1 a uma transformacao −1 : A∗ → A∗ atraves de
• 1−1 = 1,
• (a−1)−1 = a (a ∈ A),
• (ua)−1 = a−1u−1 (u ∈ A+, a ∈ A).
Note-se que esta transformacao satisfaz (u−1)−1 = u para todo u ∈ A∗, pelo que e chamada deinvolucao. Esta involucao sera importante para os chamados homomorfismos involutivos. Se G e umgrupo, um homomorfismo (de monoides) ϕ : A∗ → G se diz involutivo se u−1ϕ = (uϕ)−1 para todou ∈ A∗.
Definimos agora um sistema de reescrita em A por
RA= {(aa−1, 1) | a ∈ A}.
E facil provar que:Lema 3.1 O sistema de reescrita RA e redutor e confluente.
Prova. E claro que o sistema e redutor. Para a confluencia, supomos que
x00−→x01−→ . . .−→x0n,
x00−→x10−→ . . .−→xm0,
sao duas sequencias de transicoes em RA. Basta mostrar a confluencia localmente, construindo agrelha
x00 //
��
x01 //
�����
. . . // x0n
�����
x10
��
//___ x11
�����
//___ . . . //___ x1n
�����
......
...
�� �����
�����
xm0 //___ xm1 //___ . . . //___ xmn
17
passo a passo (onde cada seta //___ pode representar uma reducao elementar ou igualdade mesmo).Para completar cada quadrado, basta mostrar a confluencia para qualquer caso da forma
u //
��
x1y1
x2y2
onde u = x1a1a−11 y1 = x2a2a
−12 y2 com xi, yi ∈ A∗ e ai ∈ A. Se as ocorrencias de a1a
−11 e a2a
−12
forem disjuntas, podemos reproduzir a reducao de tipo alternativo em cada uma das palavras x1y1
e x2y2. Caso as ocorrencias se sobreponham, resulta imediatamente x1y1 = x2y2. Logo e valida aconfluencia local, que implica a confluencia no sentido geral do termo. �
Seja RA = Irr(RA). As palavras de RA dizem-se reduzidas. Sao precisamente as palavras em Asem fatores do tipo aa−1 (a ∈ A). Pela Proposicao 2.10 e pelo Lema 3.1, obtemos:Lema 3.2 Seja A um alfabeto. Dada u ∈ A∗, existe uma unica palavra reduzida u ∈ RA tal queu−→∗RA
u.
Definimos uma relacao de equivalencia ρA em A∗ por
u ρA v se u = v
Designando por uρA a classe de equivalencia de u ∈ A∗, definimos
FA = A∗/ρA = {uρA | u ∈ A∗}.
Mostramos em seguida que FA e um grupo que satisfaz a propriedade universal:Teorema 3.3 Seja A um alfabeto. Entao:
(i) FA e um grupo para a operacao binaria (uρA)(vρA) = (uv)ρA.
(ii) A funcaoι : A→ FA
a 7→ aρA
e injetiva.
(iii) Seja ϕ : A→ G uma funcao de A num grupo G qualquer. Entao existe um unico homomorfismode grupos Φ : FA → G tal que ιΦ = ϕ:
Aϕ //
� _
ι
��
G
FA
Φ
>>}}
}}
Prova. (i) Primeiro ha que mostrar que a operacao esta bem definida. Suponhamos que u ρA u′ ev ρA v
′. Sera que (uv)ρA(u′v′)? Efetivamente, de u = u′ e v = v′ resulta (pela unicidade no Lema3.2) que
uv = u v = u′ v′ = u′v′,
18
logo (uv)ρA(u′v′) e a operacao esta bem definida.E imediato que a operacao e associativa e tem elemento neutro 1ρA. Como para todo u ∈ A∗ se
tem uu−1 = 1, resulta que (uρA)(u−1ρA) = (uu−1)ρA = 1ρA. Analogamente, (u−1ρA)(uρA) = 1ρA,logo FA e um grupo.
(ii) Como todas as letras sao palavras reduzidas, a injetividade resulta do Lema 3.2.(iii) Comecamos por estender a funcao ϕ : A → G a uma funcao ϕ′ : A → G fazendo a−1ϕ′ =
(aϕ)−1 (a ∈ A). Pela propriedade universal (Proposicao 2.1), existe um unico homomorfismo demonoides Φ′ : A∗ → G que estende ϕ′. Note-se que este homomorfismo e involutivo.
Dado u ∈ A∗, e facil ver que uΦ′ = uΦ′, logo u ρA v implica uΦ′ = vΦ′. Podemos entao definiruma funcao Φ : FA → G atraves de
(uρA)Φ = uΦ′ (u ∈ A∗).
E facil verificar que Φ e na realidade um homomorfismo de grupos. Designando por θ : A∗ → FA aprojecao canonica, obtemos um diagrama
Aϕ //
� _
��
G
A
ϕ′
??������������������ � // A∗ θ
//
Φ′
OO
FA
Φ
``@@@@@@@@@@@@@@@@@
que e composto de tres diagramas comutativos. Logo ιΦ = ϕ. Finalmente, a unicidade de Φ resultado fato de Aθ gerar o grupo FA, pelo que Φ vem determinado por ϕ. �
Face ao Teorema 3.3, podemos dizer que FA e o grupo livre sobre A. E simples verificar que RAcom a operacao binaria (u, v) 7→ uv constitui um grupo e que
FA→RAuρA 7→ u
e um isomorfismo de grupos. Por isso e muito comum identificar o grupo livre com o conjunto daspalavras reduzidas. Nos tambem faremos isso quando for conveniente. Usaremos tambem a notacaouρA = u para todo u ∈ A∗.
Alem do mais, estendemos a FA varios dos conceitos introduzidos na Subseccao 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 basicas
A primeira consequencia da existencia 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 oproprio G!). Pela propridade universal, a inclusao A ↪→ G induz um homomorfismo de gruposΦ : FA → G, que e sobrejetivo dado que G = 〈A〉. Logo G ∼= FA/Ker(Φ) pelo Teorema 1.5(iii). �
19
Em seguida vamos determinar quando dois grupos livres sao isomorfos.Teorema 3.5 Sejam A e B conjuntos. Entao as condicoes seguintes sao equivalentes:
(i) FA ∼= FB;
(ii) |A| = |B|.
Prova. (i) ⇒ (ii). Seja ϕ : FA → FB um isomorfismo. Seja C |A|2 o produto direto de |A| copias dogrupo cıclico C2. Suponhamos que A = {a1, . . . , am}. Para i = 1, . . . ,m, designamos por |u|ai a somados expoentes das ocorrencias de a/a−1 na palavra u ∈ A∗. Note-se que |u|ai = |u|ai , logo isto permitedefinir |g|ai para todo g ∈ FA. Seja πA : FA → C
|A|2 a funcao definida por gπA = (|g|a1 , . . . , |g|am).
E rotina verificar que πA e um homomorfismo sobrejetivo de grupos. Definindo de forma analogaπB : FB → C
|B|2 , temos tambem um homomorfismo sobrejetivo.
Suponhamos que g ∈ Ker(πA). Entao |g|ai e par para i = 1, . . . ,m. Daqui resulta que |gϕ|b e parpara todo b ∈ B, logo gϕ ∈ Ker(πB) e portanto Ker(πA) ⊆ Ker(ϕπB). Pelo Teorema 1.5(ii), existeum homomorfismo Φ : FA/Ker(πA)→ C
|B|2 tal que o diagrama
FAϕ //
��
FB
πB
��FA/Ker(πA)
Φ//______ C|B|2
comuta. Note-se que Φ e sobrejetivo porque ϕπB e sobrejetivo. Como FA/Ker(πA) ∼= C|A|2 pelo
Teorema 1.5(iii), resulta a existencia de um homomorfismo sobrejetivo C |A|2 → C|B|2 . Como |C |A|2 | =
2|A| e |C |B|2 | = 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 bijecao 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 nao existe nenhumapalavra reduzida nao vazia bε11 . . . bεn
n no alfabeto B que seja igual a 1 em G. Isto equivale a dizerque a inclusao B ↪→ G induz um isomorfismo FB → G. Em particular, G tem que ser um grupolivre. E claro que A e uma base de FA, mas existem muitas mais (como veremos na Seccao 4), aocontrario do caso dos monoides livres. Podemos entao concluir do Teorema 3.5 que todas as basesde um mesmo grupo livre possuem o mesmo numero de elementos. Este numero diz-se a dimensaodo grupo livre (logo dim(FA) = |A|). E comum designar por Fn o grupo livre de dimensao n (que eunico 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.
Quando um grupo e definido como quociente (e o caso do grupo livre FA = A∗/ρA), e importantesaber resolver o problema da palavra, isto e, saber em que condicoes (algoritmicamente, isto e,queremos ser capazes de dizer SIM ou NAO!) duas palavras representam o mesmo elemento. Dizemosentao que o problema da palavra e decidıvel. No caso dos grupos livres, e muito facil: u, v ∈ A∗
representam o mesmo elemento se e so se u = v.
20
O problema da conjugacao constitui um desafio menos obvio. Aqui o objetivo e determinaralgoritmicamente se dois elementos g, h ∈ G sao ou nao conjugados, isto e, se existe algum x ∈ G talque g = xhx−1. E facil ver que a relacao de conjugacao e uma relacao de equivalencia.
Uma palavra reduzida u ∈ RA diz-se ciclicamente reduzida se nao for da forma u = ava−1 coma ∈ A.Lema 3.6 Seja u ∈ RA. Entao existem x, v ∈ RA tais que u = xvx−1 e v e ciclicamente reduzida.Alem disso, x e v sao unicas.
Prova. A existencia e facil. Suponhamos agora que u = xvx−1 = ywy−1 com v, w ciclicamentereduzidas. Se |x| < |y|, entao y = xz para alguma z ∈ RA nao vazia, logo v = zyz−1, contradizendov ciclicamente reduzida. Por simetria, |x| > |y| tambem esta excluıda, logo |x| = |y| e obtemossucessivamente x = y e v = w. �
Dizemos que a palavra v no enunciado anterior e o nucleo cıclico de u.Um grupo diz-se:
• de torsao se todos seus elementos tiverem ordem finita;
• livre de torsao se o elemento neutro for o unico elemento de ordem finita.
Corolario 3.7 FA e livre de torsao.
Prova. Seja g ∈ FA \{1}. Pelo Lema 3.6, podemos escrever g = xvx−1 com x ∈ RA e v ciclicamentereduzida. Dado n ≥ 1, temos gn = (xvx−1)nρA = (xvnx−1)ρA. Como g 6= 1, tambem v 6= 1 e logoxvnx−1 e reduzida. Logo gn = xvnx−1 6= 1 e portanto gn tem ordem infinita. �
Se u = vw for uma palavra ciclicamente reduzida, entao a palavra wv e tambem ciclicamentereduzida. Diz-se um conjugado cıclico de u. Note-se que u = w−1(wv)w, logo os conjugados cıclicossao de fato conjugados no grupo livre.
E claro que so existe um numero finito de conjugados cıclicos para uma dada palavra. E facil verque a relacao “ser conjugado cıclico de” e uma relacao de equivalencia.Teorema 3.8 Seja A um alfabeto e g, h ∈ FA. Entao as condicoes seguintes sao equivalentes:
(i) g e h sao conjugados em FA;
(ii) os nucleos cıclicos de g e h sao conjugados cıclicos.
Prova. (i) ⇒ (ii). Como o unico conjugado de 1 e ele proprio, podemos assumir que g 6= 1. Sejag = xux−1 com u ciclicamente reduzido. Seja a ∈ A. Como ser conjugado cıclico e uma relacao deequivalencia, basta mostrar que o nucleo cıclico v de aga−1 e um conjugado cıclico de u.
Se x 6= 1, entao v = u, logo podemos assumir que x = 1. Se aua−1 for reduzida, entao maisuma vez u = v. Como u 6= 1 (pois g 6= 1), podemos assumir que au nao e reduzida (o outro caso eanalogo). Entao podemos escrever u = a−1w, logo
aga−1 = aua−1 = aa−1wa−1 = wa−1.
Como u e ciclicamente reduzida, nao pode terminar em a. Logo wa−1 ∈ RA e aga−1 = wa−1. Comow nao comeca por a (senao u = a−1w nao seria reduzida), resulta que wa−1 = v. Portanto v e umconjugado cıclico de u.
(ii)⇒ (i). No grupo livre, toda a palavra e conjugada do seu nucleo cıclico, e os conjugados cıclicossao conjugados. Agora basta recordar que a relacao de conjugacao e uma relacao de equivalencia. �
21
Daqui resulta a solucao do problema da conjugacao de FA, pois os nucleos cıclicos sao efetivamentecomputaveis, assim como os seus conjugados cıclicos.Exemplo 3.9 a−1(ba)2 e conjugado de b−1ab3 em F2, mas nao de ba3b−1a−1b−1.
Com efeito, os nucleos cıclicos destas tres palavras sao respetivamente bab, ab2 e a2b−1, donderesulta a afirmacao.
3.3 Automatos e subconjuntos racionais
Veremos em seguida alguns resultados classicos dos anos 60 e 70 que estabeleceram as primeirasrelacoes entre a teoria de grupos e a teoria de automatos.Lema 3.10 RA e uma linguagem racional.
Prova. Seja Q = A ∪ {1} e
E = {(p, a, a) | a ∈ A, p ∈ Q \ {a−1}}.
Definimos o A-automato finito A = (Q, 1, Q,E). Os caminhos bem-sucedidos neste automato sao daforma
1 a1−→a1a2−→a2
a3−→ . . .an−→an
com n ≥ 0, ai ∈ A e ai 6= a−1i−1. Daqui resulta que L(A) = RA, pelo que RA e racional. �
Exemplo 3.11 Se A = {a, b}, o automato construıdo na prova do Lema 3.10 e
aoob
--
b−1
a
��b
a
mm
a−1
b
//
1
b−1
~~~~~~~~~~~~~~~~~~
a−1
!!BBBBBBBBBBBBBBBBB
a
``AAAAAAAAAAAAAAAAA
b
==||||||||||||||||||oo //
b−1oo
a
LL
a−1
--
b−1
MM a−1
b
LL
b−1
mm
a−1
QQ//
Dada uma linguagem L ⊆ A∗, escrevemos L = {u | u ∈ L}. O resultado seguinte (Teoremade Benois) foi pioneiro nas relacoes entre grupos livres e automatos, e mostrou que a reducao depalavras nao consituıa um problema:
22
Teorema 3.12 (Benois 1969) Seja L uma A-linguagem racional. Entao L e tambem uma A-linguagem racional que pode ser calculada algoritmicamente a partir de L.
Prova. Seja A = (Q, I, T,E) um A-automato finito reconhecendo L. Definimos uma sucessao(An)n de automatos finitos com transicoes-1 do seguinte modo. Seja A0 = A. Assumindo queAn = (Q, I, T,En) ja esta definido, consideramos todas as instancias de pares ordenados (p, q) ∈ Q×Qtais que:
existe um caminho p aa−1
−−→q em An para algum a ∈ A, mas nenhum caminho p 1−→q. (1)
E claro que so existe um numero finito de instancias de (1) em An. Seja En+1 a uniao de Encom novas arestas da forma (p, 1, q), onde (p, q) ∈ Q × Q e uma instancia de (1) em An, e sejaAn+1 = (Q, I, T,En+1). Note que An = An+k para todo k ≥ 1 caso nao exista nenhuma instanciade (1) em An.
Como Q e finito, a sucessao (An)n tem que se tornar constante, digamos a partir de Am. Vamosmostrar que
L = L(Am) ∩RA. (2)
Seja u ∈ L. Entao existe uma sucessao de reducoes elementares
u = u0−→RAu1−→RA
. . . −→RAun = u.
Uma inducao simples mostra que ui ∈ L(Ai) para i = 0, . . . , n. Logo u ∈ L(Ak)∩RA ⊆ L(Am)∩RA.Resulta que L ⊆ L(Am) ∩RA.
Para a inclusao oposta, comecamos por notar que todo caminho p u−→q em Ai+1 da origem a umcaminho p v−→q em Ai, tal que v pode ser obtido a partir de u inserindo um numero finito de fatoresda 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 Proposicao 2.5, a linguagem L e racional. A natureza construtiva destes dois
resultados permite a construcao efetiva de um automato reconhecendo L a partir do automato A. �
A nocao de linguagem racional pode ser estendida a subconjuntos de outros monoides/grupos.Seja M um monoide. Podemos definir um M -automato ou automato sobre M como sendo umautomato em que os rotulos das arestas sao elementos de M . Entao L(A), o conjunto dos rotulosdos caminhos bem-sucedidos, e naturalmente um subconjunto de M . Um subconjunto X ⊆ Mdis-se racional se X = L(A) para algum M -automato finito A. O resultado seguinte generaliza aProposicao 2.9(i):Proposicao 3.13 Seja ϕ : M → N um homomorfismo de monoides e seja X ⊆M racional. EntaoXϕ e um subconjunto racional de N .
Prova. Seja A um M -automato tal que L(A) = X. Se substituirmos cada rotulo m ∈ M de umaaresta de A por mϕ, obtemos um N -automato A′ tal que L(A′) = Xϕ. Logo Xϕ e racional. �
No contexto dos grupos, a nocao de subconjunto racional e uma util generalizacao do conceito desubgrupo finitamente gerado. O resultado seguinte comprova a legitimidade deste perspetiva, mesmopara grupos arbitrarios:
23
Teorema 3.14 (Anisimov e Seifert 1975) Seja H um subgrupo de um grupo G. Entao as condicoesseguintes sao equivalentes:
(i) H e um subconjunto racional de G;
(ii) H e finitamente gerado.
Prova. (i) ⇒ (ii). Seja A = (Q, I, T,E) um G-automato tal que H = L(A). Podemos assumir queA e aparado (caso contrario suprimimos os vertices superfluos). Seja A ⊆ G o conjunto (finito) dosrotulos das arestas de A. Escrevendo m = |Q|, definimos
X = H ∩ (∪2m−1k=0 (A ∪A−1)k).
Como A e finito, X e um subconjunto finito de H. Vamos provar que H = 〈X〉.Dado h ∈ H, podemos escrever h = a1a2 . . . an para algum caminho
I 3 q0a1−→q1
a2−→ . . .an−→qn ∈ T
em A (logo a1, . . . , an ∈ A). Vamos mostrar que h ∈ 〈X〉 por inducao sobre n.Se n < 2m, entao h ∈ X por definicao de X. Logo podemos assumir que n ≥ 2m e que a hipotese
e valida para menos que n fatores. Seja u = a1 . . . an−m e v = an−m+1 . . . an. Eliminando ciclosdesnecessarios, podemos tomar um caminho qn−m
w−→qn de comprimento < m (isto e, com menos dem arestas). Logo uw ∈ L(A) = H e pela hipotese de inducao uw ∈ 〈X〉. Por outro lado,
w−1v ∈ ∪2m−1k=0 (A ∪A−1)k
e w−1v = (w−1u−1)(uv) ∈ H, logo w−1v ∈ X. Daqui resulta que h = (uw)(w−1v) ∈ 〈X〉, logoH = 〈X〉 e finitamente gerado.
(ii)⇒ (i). SejaH = 〈h1, . . . , hm〉. Definimos umG-automato com um so verticeA = ({q}, q, q, E),onde
E = {q} × {h1, . . . , hm, h−11 , . . . , h−1
m } × {q}.
E imediato que H = L(A), logo H e racional. �
3.4 Grafos de Cayley
A existencia de inversos nos grupos conduz naturalmentely ao conceito de automato inverso. Dadoum A-automato 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 ilustracao destes conceitos e dada pelos grafos de Cayley de grupos. Seja G um grupogerado por A. O grafo de Cayley ΓA(G) e um A-grafo que tem os elementos de G como vertices earestas da forma
ga−→ga (g ∈ G, a ∈ A).
24
Fixando a identidade 1 como o unico vertice inicial e terminal (num automato, chamamos um talvertice de ponto base), obtemos um automato inverso. Qual e a sua linguagem? Precisamente oconjunto das palavras u ∈ A∗ tais que u = 1 em G. Isto e, se π : A∗ → G designar o homomorfismoinvolutivo que estende a inclusao A ↪→ G (e que e sobrejetivo porque G = 〈A〉), entao a linguagemreconhecida pelo automato e 1π−1, linguagem de suma importancia para a compreensao da estruturade G! Esta linguagem esta intimamente ligada ao problema da palavra de G, discutido na Subseccao7.3.
Na representacao de automatos inversos (e grafos de Cayley) e habitual omitir a representacaodas arestas com rotulo em A−1.Exemplo 3.15 O grupo simetrico S3 (permutacoes do conjunto {1, 2, 3} e gerado pelas permutacoesa = (123) e b = (12). O respetivo grafo de Cayley e
•
b ++
a-- •
a
��
b
~~•
bkk
a
��1111111111111 •aoo b
>>
•
a
FF�������������
b
��•
a
VV
b
TT
Note-se que podemos omitir a designacao dos vertices devido a natureza simetrica dos grafos deCayley. Como G actua a esquerda no grafo por translacoes (isto e, cada elemento x ∈ G transformao vertice g ∈ G em xg e a aresta g a−→ga em xg
a−→xga), sempre tem um automorfismo deste grafolevando qualquer vertice p em qualquer vertice q. Dizemos que um tal grafo e transitivo nos vertices.
O grafo de Cayley de FA (relativamente a base canonica A) e facil de descrever. Como 1θ−1 = RApara o homomorfismo canonico θ : A∗ → FA, ΓA(FA) nao pode conter ciclos cujo rotulo seja umapalavra reduzida. Sendo assim, se omitirmos a representacao das arestas com rotulo em A−1, obtemosuma arvore infinita.
25
Exemplo 3.16 Se A = {a, b}, podemos descrever uma porcao de ΓA(FA) por
· · ·
· · ·a// •b
OO
a// · · ·
· · · · · ·
· · ·a// •
a//
b
OO
•a
//
b
OO
•b
OO
a// · · ·
· · ·b
OO
· · ·b
OO
· · · a // •
b
OO
a // · · ·
· · ·b
OO
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 = 〈anba−n | n ∈ N〉 ≤ F2. Mostre que H nao e finitamente gerado.
(3.4) Determine se os seguintes pares de palavras representam elementos conjugados de F2:
(a) b−1abb−1ab−1a−1ba−1baa−1 e bab−1aa−1aba−2bb−2;
(b) bababb−2a−1baa−2b−1 e b−3a−1a3b−1a−2ab2a−2b3.
(3.5) Seja A um alfabeto finito. Mostre que a linguagem das palavras ciclicamente reduzidas de A∗
e racional.
(3.6) Seja A o automato descrito por
// • a //
b
��•
a−1��~~~~~~~
bpp
•b−1
__@@@@@@@//
Construa a sucessao de automatos com transicoes-1 definida na prova do Teorema 3.12.
(3.7) Seja A um alfabeto finito. Mostre que:
(a) para todo X ⊆ FA, X e um subconjunto racional de FA se e so se X e uma A-linguagemracional;
26
(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)}.
27
4 Representacao de subgrupos
Os automatos finitos constituem hoje a forma mais eficiente de representar um subgrupo finitamentegerado H de um grupo livre FA. O algoritmo conhecido como construcao de Stallings constroi umautomato inverso S(H) que tem imensas aplicacoes (embora no artigo original de Stallings ele usasseimersoes de grafos, o que e mais complicado). Varias das ideias presentes eram ja conhecidas dematematicos como Reidemeister, Schreier, e sobretudo Serre.
4.1 Construcao de Stallings
Uma das maiores contribuicoes de Stallings e mesmo o algoritmo para construir S(H):
(1) Tomando um conjunto finito de geradores h1, . . . , hm de H em forma reduzida, comecamos porconstruir o chamado automato flor F(H), em que petalas rotuladas pelas palavras reduzidashi (e as arestas inversas, para que seja um automato involutivo) sao coladas a um ponto baseq0:
•h1
00
h2
��
hm
PP
(2) Numa segunda fasae, identificamos successivamente pares de arestas da forma q a←−p a−→r ateobtermos um automato determinıstico (inverso, de fato!), designado por S(H).
Note-se que, como o numero de arestas diminui a cada dobragem, acabamos sempre por obterum automato inverso, dito automato de Stallings de H.Exemplo 4.1 Construcao do automato de Stallings de H = 〈a2, ab−1c, c〉:
F(H):•
a
• q0OO
��
a
JJ
cdd
aoo
•
b
OO
c
??~~~~~~~~~~~~~~~~
28
1a dobragem:•
a
• q0 oo //
a
JJ
c
CCa,boo
2a dobragem e S(H):
•a
33 q0 oo //a,b
tt
c
Ha duas questoes naturais no que respeita a esta construcao:
• O resultado final depende da ordem em que as dobragens de arestas sao feitas?
• O resultado final depende do conjunto finito de geradores de H escolhido?
Veremos que a resposta e NAO a ambas as questoes. Para mostrar isso, precisamos de introduzirum novo conceito. Dizemos que um A-automato finito A e SFG se:
• A e inverso;
• A tem um ponto base (o vertice inicial e tambem o unico vertice terminal);
• todo vertice ocorre nalgum caminho bem-sucedido de rotulo reduzido.
Veremos mais adiante que estes automatos sao precisamente os automatos de Stallings de subgruposfinitamente gerados de FA (o que explica a designacao SFG).Lema 4.2 Sejam A e A′ A-automatos SFG. Entao as condicoes seguintes sao equivalentes:
(i) A ∼= A′;
(ii) L(A) ∩RA = L(A′) ∩RA.
Prova. (i) ⇒ (ii). Automatos isomorfos tem a mesma linguagem.(ii) ⇒ (i). Sejam A = (Q, q0, q0, E) e A′ = (Q′, q′0, q
′0, E
′). Definimos uma funcao ϕ : Q→ Q′ doseguinte modo. Seja q ∈ Q. Como A e SFG, possui um caminho q0
u−→q v−→q0 com uv ∈ RA. Logouv ∈ L(A′) ∩RA e A′ possui um caminho q′0
u−→q′ v−→q′0. Definimos qϕ = q′.Sera que ϕ esta bem definida? Suponhamos que q0
w−→q z−→q0 e um caminho alternativo comwz ∈ RA, e q′0
w−→p′ z−→q′0 e um caminho em A′. Pelo menos uma das palavras uz, uw−1 e reduzida,logo uz ∈ L(A′) ou uw−1 ∈ L(A′). Como A′ e determinıstico, resulta facilmente que ϕ esta bemdefinida. Note-se que q0ϕ = q′0 (considerando u = v = 1).
Sejam p, q ∈ Q. Tomemos caminhos q0u−→q v−→q0 e q0
w−→p z−→q0 em A com uv,wz ∈ RA. Sepϕ = qϕ = q′, entao existem caminhos q′0
u−→q′ v−→q′0 e q′0w−→q′ z−→q′0 em A′. Usando um argumento
analogo ao do paragrafo anterior, obtemos uw−1 ∈ L(A) ou uz ∈ L(A). Como A e determinıstico,resulta que p = q, logo ϕ e injetiva.
29
Suponhamos agora que (p′, a, q′) ∈ E′. Como A′ e SFG, possui caminhos q′0u−→p′ v−→q′0 e
q′0w−→q′ z−→q′0 com uv,wz ∈ RA. Logo uma das palavras uaw−1, uaz, v−1aw−1, v−1az e reduzida,
e pertencera a L(A). Assumindo que e uaw−1, obtemos um caminho q0u−→p a−→qw
−1
−→q0 em A,donde resulta que pϕ = p′ e qϕ = q′. Em particular, ϕ e sobrejetiva! Alem disso, mostramos que(pϕ, a, qϕ) ∈ E′ implica (p, a, q) ∈ E. A implicacao recıproca e analoga, logo ϕ e um isomorfismo deautomatos. �
Teorema 4.3 (Stallings 1983) Seja H ≤f.g. FA. Entao:
(i) S(H) e um automato 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 todoo vertice de F(H) ocorre nalgum caminho bem-sucedido de rotulo reduzido. Esta propriedade semantem ao longo do processo de dobragens, pois L(F(H)) ⊆ L(S(H)).
(ii) E facil ver que L(F(H)) ⊆ H. Por outro lado, se A′ resulta do automato involutivo A poruma dobragem de arestas, o argumento usado para provar (3) implica que L(A′) = L(A). Daqui seconclui 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 naconstrucao. Entao u = hε1i1 . . . h
εnin
para alguns n ≥ 0, i1, . . . , in ∈ {1, . . . ,m} e ε1, . . . , εn ∈ {1,−1}.E claro que hε1i1 . . . h
εnin∈ L(F(H)) ⊆ L(S(H)). Como uma palavra da forma aa−1 so pode ser rotulo
de ciclos num automato inverso, resulta que u = hε1i1 . . . hεnin∈ L(S(H)) e logo H ⊆ L(S(H))∩RA. �
Podemos finalmente provar o seguinte:Corolario 4.4 (Stallings 1983) Dado H ≤f.g. FA, o automato de Stallings S(H) nao depende nemda ordem em que as dobragens de arestas sao feitas, nem do conjunto finito de geradores de Hescolhido.
Prova. Pelo Teorema 4.3(ii), L(S(H))∩RA e independente destes dois fatores. Como S(H) e SFGpelo Teorema 4.3(i), segue do Lema 4.2 que L(S(H))∩RA determina S(H) a menos de isomorfismo.�
Observacao 4.5 Por vezes, a construcao de Stallings aparece definida de forma um pouco maisgeral, admitindo o uso de formas nao reduzidas dos geradores na construcao do automato flor F(H).Nesse caso, haveria que acrescentar uma terceira etapa a etapa das dobragens, eliminando sucessi-vamente todos os vertices diferentes do ponto base que apresentem grau 1 (o grau de um vertice deum automato e o numero de arestas que nele tem origem).Exemplo 4.6 Construcao do auomato de Stallings de H = 〈aa−1b2, bacaa−1c−1b〉 partindo de for-mas nao reduzidas dos geradores:
O automato flor e• a //
b ��???????? • • a // • c // •a
��•
b// q0OO
��
a``@@@@@@@@
b>>~~~~~~~•
boo
c// •
a// •
30
Depois de proceder a todas as dobragens, obtemos
• •aoo •
•a
<<
c
OO
b
33 q0
btt
a
OO
oo //
Eliminando sucessivamente todos os vertices diferentes de q0 que apresentem grau 1, obtemos final-mente o automato de Stallings
•a
<<b
33 q0
btt oo //
4.2 Aplicacoes
A primeira aplicacao da construcao de Stallings e a solucao simples e elegante do chamado problemada palavra generalizado. Para um grupo G, este problema consiste em encontrar um algoritmo quedecida, dados g ∈ G e H ≤f.g. G, se g ∈ H ou nao. No caso particular H = {1}, permite decidir seg = 1 e logo se g = g′ para g, g′ ∈ G (equivalente a g−1g′ = 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, paradeterminar se g ∈ H, basta construir S(H) e testar se a palavra g e aceite pelo automato. �
Exemplo 4.8 Podemos usar o automato de Stallings construıdo no Exemplo 4.1 para verificar queba ∈ H = 〈a2, ab−1c, c〉 mas ab /∈ H.
Os automatos de Stallings tambem permitem a construcao de bases para subgrupos finitamentegerados, como veremos em seguida.
Seja H ≤f.g. FA, e seja m o numero de vertices de S(H). Uma arvore geradora T de S(H)consiste em m−1 arestas e suas inversas que, juntas, conectam todos os vertices de S(H). Dado umvertice p de S(H), designamos por wp a T -geodesica conectando o ponto base q0 a p, isto e, q0
wp−→pe o caminho mais curto contido em T ligando q0 a p. Note-se que esta T -geodesica e unica, poiscaso contrario poderıamos dispensar uma das m− 1 arestas e continuar ligando todos os vertices, oque 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 vertices da primeira veze depois um novo vertice de cada vez!Teorema 4.9 Seja H ≤f.g. FA e seja T uma arvore geradora de S(H) = (Q, q0, q0, E). Seja E+ =E ∩ (Q×A×Q). Entao
Y = {wpaw−1q | (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 Teorema4.3(ii) que Y ⊆ H. Logo Y ⊆ H no grupo livre.
Seja agora h = a1 · · · ak ∈ H em forma reduzida (ai ∈ A). Pelo Teorema 4.3(ii), existe umcaminho bem-sucedido
q0a1−→q1
a2−→· · · ak−→qk = q0
31
em S(H). Para cada i = 1, . . . , k, ou wqi−1aiw−1qi ∈ Y ∪ Y −1 ou wqi−1aiw
−1qi = 1, esta ultima
possibilidade ocorrendo se (qi−1, ai, qi) ∈ T . Em qualquer caso, obtemos
h = a1 · · · ak = (wq0a1w−1q1 )(wq1a2w
−1q2 ) · · · (wqk−1
akw−1q0 ) ∈ 〈Y 〉
e logo H = 〈Y 〉.Para mostrar que Y e uma base, sejam y1, . . . , yk ∈ Y ∪ Y −1 com yi 6= y−1
i−1 para i = 2, . . . , k.Seja yi = wpiaiw
−1ri , onde ai ∈ A e o rotulo da aresta que nao pertence a T . Resulta facilmente de
yi 6= y−1i−1 e da definicao de arvore geradora que
y1 · · · yk = wp1a1w−1r1 wp2a2 · · · ak−1w
−1rk−1wpk
akwrk ,
uma palavra reduzida nao vazia se k ≥ 1. Logo Y e uma base de H. �
Como consequencia imediata, obtemos:Corolario 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 versao geral e conhecidacomo o Teorema de Nielsen-Schreier.
Note-se que o Teorema 4.9 mostra tambem que todo automato SFG e automato de Stallings dealgum subgrupo finitamente gerado, pois a construcao da base Y e valida para todo automato SFG.Observamos tambem que diferentes arvores geradoras produzem em geral bases distintas.Exemplo 4.11 Usando o automato de Stallings do Exemplo 4.1, podemos tomar como arvore ger-adora a aresta de rotulo b e sua inversa. Logo {ab−1, ba, c} constitui uma base de H = 〈a2, ab−1c, c〉.
Uma outra aplicacao da construcao de Stallings e a identificacao de subgrupos de ındice finito:Teorema 4.12 Seja H ≤f.g. FA. Entao as condicoes seguintes ao equivalentes:
(i) [FA : H] <∞;
(ii) S(H) e um automato completo.
Prova. (i) ⇒ (ii). Suponhamos que S(H) = (Q, q0, q0, E) nao e completo. Entao existem q ∈ Q ea ∈ A tais que (q, a, p) /∈ E para todo p ∈ Q. Seja q0
u−→q um caminho em S(H). Como S(H) einverso, podemos assumir que u ∈ RA. Vamos mostrar que
Huam 6= Huan se m− n > |u|. (4)
De fato, Huam = Huan implica uam−nu−1 ∈ H e logo uam−nu−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−1u−1 =uam−nu−1 ∈ L(S(H)), pois u−1 nao tem comprimento suficiente para apagar todos os a’s. Masentao, como S(H) e determinıstico, tem que existir uma aresta (q, a, p), contradicao. Logo (4) evalida e logo [FA : H] =∞.
(ii) ⇒ (i). Para cada q ∈ Q, fixamos uma geodesica q0wq−→q (isto e, caminho de comprimento
mınimo). Seja g ∈ FA em forma reduzida. Como S(H) e completo, existe um caminho q0g−→q
para algum q ∈ Q. Logo gw−1q ∈ H e portanto g = gw−1
q wq ∈ Hwq. Logo FA = ∪q∈Q(Hwq) e[FA : H] <∞. �
32
Corolario 4.13 Seja H ≤f.g. FA com ındice finito. Entao [FA : H] e o numero de vertices de S(H).
Prova. Vimos na prova do Teorema 4.12 que FA = ∪q∈Q(Hwq), logo basta mostrar que as classesHwq sao todas distintas. Suponhamos que Hwp = Hwq para p, q ∈ Q. Entao wpw
−1q ∈ H e logo
pelo Teorema 4.3(ii) existe um caminhoq0
wpw−1q−−−→q0
em S(H), e logo um caminhoq0
wpw−1q wq−−−−−→q.
Como S(H) e inverso e wpw−1q wq = wp (os rotulos das geodesicas sao palavras reduzidas), obtemos
um caminho q0wp−→q. Logo p = q como pretendıamos. �
Exemplo 4.14 Como o seu automato de Stallings nao e completo, o subgrupo H = 〈a−1ba, ba2〉 naotem ındice finito em F2.Corolario 4.15 Se H ≤f.g. FA tem ındice n, entao dim(H) = 1 + n(|A| − 1).
Prova. Pelo Teorema 4.12, o automato S(H) tem n vertices e n|A| arestas positivas. Uma arvoregeradora tem n− 1 arestas positivas, logo dim(H) = n|A| − (n− 1) = 1 + n(|A| − 1) pelo Teorema4.9. �
Consideramos em seguida a relacao de conjugacao a nıvel de subgrupos. Dois subgruposH,K ≤ Gdizem-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 automato SFG, o ponto base q0 e ounico vertice que pode ter grau 1. Seja S0(H) = (Q,E). Trata-se de um grafo orientado em que asarestas tem rotulos em A. Se q0 tiver grau 6= 1, seja S1(H) = S0(H). Se q0 tiver grau 1, S1(H) eobtido a partir de S0(H) eliminando sucessivamente todos os vertices de grau 1.Teorema 4.16 Sejam H,K ≤f.g. FA. As condicoes seguintes sao equivalentes:
(i) H e K sao conjugados;
(ii) S1(H) ∼= S1(K).
Prova. Vamos esbocar apenas a prova, apelando a intuicao. E facil compreender que S(H) temuma das duas formas seguintes:
• e S1(H) com um ponto base designado;
• e obtido a partir de S1(H) “colando” uma cauda q0u−→q (sendo a colagem feita identificando
q com um vertice de S1(H)) e sendo q0 o ponto base.
Esta segunda opcao so e possıvel se S1(H) tiver mais que um vertice.Consideremos a igualdade K = g−1Hg. Seja X um subconjunto gerador de H em forma reduzida.
Usando a versao mais geral da construcao de Stallings referida na Observacao 4.5, poderıamos con-struir S(K) usando o subconjunto gerador g−1Xg. Aplicando as dobragens na ordem conveniente,o processo de dobragens seria equivalente a colar a cauda
p0g−1
−−→p
33
em S(H) (sendo a colagem feita identificando p com o ponto-base de S(H)), passando p0 a ser onovo ponto base, e dobrando a cauda se for necessario. Haveria que aplicar em seguida a terceirafase do algoritmo referida na Observacao 4.5, o que pode conduzir a varias possibilidades, quecriam/alteram/suprimem a cauda e/ou alteram o ponto base (ilustradas no Exemplo 4.17), mas quemantem 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 = 〈ab2ab−1a−1〉 ≤ F2. Entao:
OO
��
OO
��q0 a
// •b// •
b(( •
ahh q0
b// •
b(( •
ahh
S(H) S(a−1Ha)
OO
��
OO
��q0 •
aoo •
aoo •
aoo
b(( •
ahh q0
b(( •
aii
S(a−3b−1a−1Haba3) S(b−1a−1Hab)
OO
��
OO
��•
b )) q0a
hh •b(( •
ahh
b// q0
S(b−2a−1Hab2) S(b−3a−1Hab3)
Podemos caraterizar facilmente os automatos de Stallings dos subgrupos normais finitamentegerados:Corolario 4.18 Seja H ≤f.g. FA. Entao H E FA se e so se verifica uma das condicoes seguintes:
(i) H = {1};
(ii) [FA : H] <∞ e S1(H) e transitivo nos vertices.
Prova. Podemos assumir que H 6= {1}. Ora H e normal se e so se S(gHg−1) ∼= S(H) para todog ∈ FA. Isto nao pode acontecer se existir a possibilidade de S(gHg−1) ter uma cauda. Logo S(H) ecompleto e [FA : H] <∞ pelo Teorema 4.12. Mas entao, pelo Teorema 4.16, os automatos S(gHg−1)correspondem a todas as versoes de S(H) com o ponto base alterado. Como S(gHg−1) ∼= S(H) seso se S1(H) admite um automorfismo levando o ponto base q0 em q (onde
q0g−1
−−→q
e um caminho em S(H)), isto e equivalente a dizer que S1(H) e transitivo nos vertices. �
34
Vamos agora usar os automatos de Stallings para dar uma prova simples do Teorema de Howson:Teorema 4.19 (Howson 1954) Sejam H,K ≤f.g. FA. Entao H ∩K ≤f.g. FA.
Prova. O produto direto S(H)×S(K) reconhece L(S(H))∩L(S(H)) pela Proposicao 2.6. Seja A acomponente conexa de S(H)×S(K) contendo o novo ponto base (isto e, removemos todos os verticese arestas que nao estao ligados ao ponto base). Entao temos tambem L(A) = L(S(H)) ∩ L(S(K)).Se removermos de A eventuais vertices de grau 1 que nao sejam o ponto base (ver Observacao 4.5),obtemos um automato inverso SFG A′. Vejamos que A′ ∼= S(H ∩K).
Pelo Lema 4.2 e pelo Teorema 4.3, basta mostrar que L(A′)∩RA = H ∩K. Como L(A′)∩RA =L(A) ∩RA e H ∩K = H ∩K, isto equivale a mostrar que
L(S(H)) ∩ L(S(K)) ∩RA = H ∩K,
uma consequencia imediata do Teorema 4.3(ii).Logo S(H ∩K) ∼= A′, sendo em particular finito. Daqui resulta que H ∩K e finitamente gerado.
�
O Teorema de Howson esta estreitamente ligado ao que foi durante muitos anos um dos maisfamosos 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 conjeturafoi finalmente provada em 2011 por Friedman e Mineyev (de forma independente).
4.3 A metrica profinita
Ha varias metricas de grande interesse que podem ser definidas em FA. Apresentaremos em seguidaa primeira delas, mas primeiro precisamos de provar que FA e residualmente finito. Um grupo Gdiz-se residualmente finito se
∩{H ≤ G | [G : H] <∞} = {1}.
Proposicao 4.20 FA e residualmente finito.
Prova. Seja g ∈ FA \ {1}. Seja g = a1 . . . am com ai ∈ A. Consideremos o automato inverso
oo // q0a1 // q1
a2 // . . . am // qm
E facil verificar que podemos acrescentar arestas a este automato para obter um automato inversocompleto (e SFG), que sera o automato de Stallings de algum H ≤f.g. FA. Pelo Teorema 4.12, Htem ındice finito, e pelo Teorema 4.3(ii), g /∈ H. Logo g /∈ H e portanto FA e residualmente finito.�
Vamos necessitar tambem do seguinte lema:
35
Lema 4.21 Sejam H,K ≤ G de ındice finito. Entao H ∩K tem ındice finito.
Prova. Suponhamos que G = Ha1 ∩ . . . Ham = Kb1 . . .Kbn. Entao
G =m⋃i=1
n⋃j=1
(Hai ∩Kbj).
Basta-nos mostrar quec ∈ Hai ∩Kbj ⇒ Hai ∩Kbj ⊆ (H ∩K)c. (5)
Com efeito,(Hai ∩Kbj)c−1 ⊆ Haic−1 ⊆ Haia−1
i H = H,
e analogamente (Hai∩Kbj)c−1 ⊆ K. Logo (Hai∩Kbj)c−1 ⊆ H∩K e (5) e valido como pretendıamos.�
Uma metrica (ou distancia) num conjunto X e uma funcao d : X × X → R satisfazendo osaxiomas 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 entao um espaco metrico. Se substituirmos o axioma (M4) pelo axiomamais forte
(M4’) d(x, z) ≤ max {d(x, y), d(x, z)},
temos o que se chama de ultrametrica.Definimos uma funcao 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 numero de elementos de um grupo finitoF tal que gϕ 6= hϕ para algum homomorfismo ϕ : FA → F .Lema 4.22 A funcao d e uma ultrametrica em FA.
Prova. Primeiro ha que mostrar que d esta bem definida. Suponhamos que g 6= h. Entao gh−1 6= 1e pela Proposicao 4.20 existe H ≤ FA de ındice finito tal que gh−1 /∈ H. Seja
K =⋂x∈G
xHx−1.
Como xHx−1 = (xH)(Hx−1) = (Hx−1)−1(Hx−1) e [FA : H] < ∞, K e na realidade intersecao deum numero finito de subgrupos da forma xHx−1. Cada um deles tem naturalmente ındice finito,logo [FA : H] <∞ pelo Lema 4.21.
E facil confirmar que K e um subgrupo normal, logo FA/K e um grupo finito. Como gh−1 /∈ Himplica gh−1 /∈ K, a projecao canonica FA → FA/K envia g e h em elementos distintos de FA/K.Logo d esta bem definida.
36
Os axiomas (M1) – (M3) sao obviamente satisfeitos. Falta verificar (M4’). Sejam x, y, z ∈ FA.Sem perda de generalidade, podemos assumir que os tres elementos sao 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 valido e d e uma ultrametrica.�
A funcao d diz-se a metrica profinita.Podemos provar agora o famoso Teorema de Marshall Hall:
Teorema 4.23 (Marshall Hall 1950) Seja H ≤f.g. FA. Entao H e fechado para a metrica profinita.
Prova. Seja g ∈ FA \ H. Pelo Teorema 4.3(ii), g /∈ L(S(H)). Caso exista um caminho da formaq0
g−→ . . . em S(H), seja A = S(H). Caso contrario, A e o automato inverso obtido acrescentandovertices e arestas a S(H) de forma a que passe a existir um caminho q0
g−→r (sendo r um novovertice). Agora, tal como na prova da Proposicao 4.20, acrescentamos arestas a A ate obter umautomato inverso completo (e SFG), que sera o automato de Stallings de algum K ≤f.g. FA. PeloTeorema 4.12, K tem ındice finito, e pelo Teorema 4.3(ii), g /∈ K. Logo g /∈ K. Seja
J =⋂x∈G
xKx−1.
Tal como na prova do Lema 4.22, temos J E FA e [FA : J ] < ∞. Seja π : FA → FA/J a projecaocanonica.
Suponhamos que gπ = hπ para algum h ∈ H. Entao gh−1 ∈ J ⊆ K. Como H ⊆ K, resulta queg ∈ Kh = K, contradicao. Logo gπ 6= hπ e portanto d(g, h) ≥ 2−[FA:J ] para todo h ∈ H. Designandopor Bε(g) a bola aberta de centro g e raio ε no espaco metrico (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 construcao da prova do Teorema 4.23 para H = 〈a2〉 ≤ F2 e g = ab.Obtemos
S(H) : oo // q0
a )) q1aii
A : oo // q0
a )) q1aii
b // r
S(K) : oo // q0
a ))
b
MM q1aii
b(( r
b
ii
app
Logo K tem tres conjugados, correspondendo a cada uma das tres escolhas possıveis para ponto base.Utilizando a construcao descrita na prova do Teorema 4.19, baseada no produto direto (ver tambem
37
a Proposicao 2.6), acabamos obtendo
S(J) : oo // q0 oob //
OO
a
��
• oo a // •OOb
��• oo
b// • oo
a// •
4.4 Exercıcios
(4.1) Para cada um dos seguintes subgrupos de F2,
H1 = 〈a2b−1a−2, a2b−2a−2〉,H2 = 〈a2, a−1baba2〉,H3 = 〈a3, ba2, b−2, baba〉,H4 = 〈a3, b3, aba−1, a(ba)2, bab−1, b−1ab〉:
(a) Construa S(Hi).
(b) Determine quais das palavras a2b−1a, a7bab, a2b99a−2, (ab)100 representam elementos deHi.
(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 = 〈a2, aba, b2, bab〉 e K = 〈a2, b, aba〉 subgrupos de F2.
(a) Construa os automatos 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 numero finito deK ≤ 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 = 〈aba−1〉 ≤ 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′, x ∈ FA e H ≤f.g. FA. Mostre que:
(a) d(xg, xg′) = d(gx, g′x) = d(g, g′);
(b) Hg e gH sao fechados em (FA, d).
38
5 Bordo de um grupo livre
Nesta secao estudamos uma segunda metrica do grupo livre que nos conduz a uma compactificacaofamosa: o bordo, que pode ser descrito usando palavras infinitas.
5.1 Palavras infinitas
Uma palavra infinita no alfabeto A e uma sequencia infinita de letras de A do tipo a1a2a3 . . ..Designamos por Aω o conjunto de todas as palavras infinitas no alfabeto A e usamos tambem anotacao A∞ = A∗ ∪Aω.
Podemos associar tambem palavras infinitas a um A-automatoA = (Q, I, T,E). Se (pi−1, ai, pi) ∈E para todo i ≥ 1, temos definido um caminho infinito
p0a1−→p1
a2−→p2a3−→ . . .
O seu rotulo e a palavra infinita a1a2a3 . . . ∈ Aω. Designamos por Lω(A) o conjunto dos rotulosde todos os caminhos infinitos da forma I 3 q0
α−→ . . . em A. Note-se que os estados terminais naodesempenham qualquer papel no calculo de Lω(A)! Ha outras formas de associar uma linguagem depalavras infinitas a A (por exemplo, exigindo uma infinidade de passagens por um estado terminal(Buchi)), mas nao nos interessam no presente contexto.
Dada L ⊆ A+, designamos por Lω o conjunto de todas as palavras infinitas da forma u1u2u3 . . .(ui ∈ L). Em particular, se a ∈ A, aω designa a palavra infinita aaa . . .Exemplo 5.1 Seja A o automato
oo // •
a
��
b// •
c
��
Entao L(A) = a∗ e Lω(A) = aω ∪ a∗bcω.Nao podemos concatenar duas palavras infinitas, mas podemos concatenar u = a1 . . . an e α =
b1b2b3 . . . (ai, bj ∈ A) poruα = a1 . . . anb1b2b3 . . .
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 tambem 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 propria x caso |x| < n).
5.2 A metrica dos prefixos e o espaco de Cantor
A metrica dos prefixos e definida em A∗ do seguinte modo. Dadas u, v ∈ A∗, seja u∧ v o mais longoprefixo comum de u e v. Definimos
d′(u, v) ={
2−|u∧v| se u 6= v0 se u = v
39
Exemplo 5.2 Sejam u = a3b, v = a3b3 e v = b2. Entao d′(u, v) = 2−4 e d′(u,w) = d′(v, w) = 1.Lema 5.3 A funcao d′ e uma ultrametrica em A∗.
Prova. Os axiomas (M1) – (M3) sao obviamente satisfeitos. Falta verificar (M4’) para u, v, w ∈ A∗.Sem perda de generalidade, podemos assumir que as tres palavras sao distintas, pelo que nos bastamostrar que
|u ∧ w| ≥ min {|u ∧ v|, |v ∧ w|}.
Esta desigualdade e valida por transitividade, pois se u e v tem um prefixo comum de comprimentom, e o mesmo se passa com v e w, entao u e w vao ter tambem um prefixo comum de comprimentom. �
E facil ver que o espaco metrico (A∗, d′) e discreto, isto e, todo ponto e aberto. Com efeito, dadau ∈ A∗, temos
B2−|u|(u) = {u} :
se v ∈ B2−|u|(u)\{u}, entao |u∧v| > |u|, absurdo. Isto quer dizer que (A∗, d′) nao e muito interessanteenquanto espaco metrico. Mas o seu completado vai ser!
Uma sucessao (xn)n num espaco metrico (X, d) dix-se de Cauchy se
∀ε > 0 ∃p ∈ N ∀m,n ≥ p d(xm, xn) < ε.
A sucessao diz-se convergente para x ∈ X se
∀ε > 0 ∃p ∈ N ∀n ≥ p d(xn, x) < ε.
Dizemos entao que x e o limite da sucessao (xn)n. Resultados bem conhecidos da topologia afirmamque o limite de uma sucessao convergente e unico e que toda sucessao convergente e de Cauchy. Noentanto, o recıproco nao e necessariamente verdade: por exemplo, a sucessao ( 1
n)n e de Cauchy em]0,+∞[ (para a metrica usual) mas nao e convergente. Um espaco metrico em que toda a sucessaode Cauchy e convergente diz-se completo.
Suponhamos agora que (X, d) e um espaco metrico mas nao e completo. Um outro resultado detopologia afirma que podemos mergulhar (X, d) num espaco metrico completo (Y, d′) (com d′|X×X =d). Se escolhermos Y menor possıvel (isto e, se todo elemento de Y for limite de alguma sucessaoem (X, d)), dizemos que (Y, d′) e o completado de (X, d). E um outro resultado de topologia afirmaque o completado e unico a menos de homeomorfismo. E designado por X.
Por exemplo, para a metrica usual, R e o completado de Q.A construcao do completado e em geral tecnicamente complicada, mas isso nao acontece com
o completado de (A∗, d′). Comecamos por estender d′ a A∞ com a mesma definicao (e a mesmadesignacao d′!). E facil ver que d′ e uma ultrametrica em A∞. Mas ha mais:Teorema 5.4 (A∞, d′) e o completado de (A∗, d′).
Prova. Seja (αn)n uma sucessao de Cauchy em (A∞, d′). Entao
∀k ∈ N ∃pk ∈ N ∀m,n ≥ pk d′(αm, αn) < 2−k.
Logo∀k ∈ N ∃pk ∈ N ∀m,n ≥ pk α[k]
m = α[k]n . (6)
40
Podemos assumir que a sucessao (pk)k e nao decrescente. Daqui resulta facilmente que
α[1]p1 ≤ α
[2]p2 ≤ α
[3]p3 ≤ . . .
E claro que existe uma unica palavra α ∈ A∞ tal que α[k] = α[k]pk para todo k ∈ N: e finita se a
sucessao (α[k]pk )k for estacionaria e infinita caso contrario. Vejamos que α = limn→+∞ αn:
Seja ε > 0 e seja k ∈ N tal que 2−k < ε. Tomemos n ≥ pk. Por (6), temos α[k]n = α
[k]pk . Por outro
lado, α[k] = α[k]pk , logo α[k]
n = α[k] e portanto d′(αn, α) ≤ 2−k < ε. Logo α = limn→+∞ αn e portanto(A∞, d′) e completo.
Como α = limn→+∞ α[n] para toda α ∈ Aω, (A∞, d′) e o completado de (A∗, d′). �
Um espaco metrico (X, d) e compacto se toda a sucessao em X admite umasubsucessao conver-gente. Ha muitas outras definicoes equivalentes. Argumentos ditos de compacidade sao usados comgrande eficacia em topologia e logica, e por virtude destas duas disciplinas, na algebra.Teorema 5.5 (A∞, d′) e compacto.
Prova. Seja (αn)n uma sucessao em (A∞, d′). Se existir algum p ∈ N tal que {αn : |αn| ≤ p} sejainfinito, entao ha alguma palavra de comprimento ≤ p a repetir-se infinitamente na sucessao, o queresolve imediatamente a questao. Por isso podemos assumir que {αn : |αn| ≤ p} e finito para todop ∈ N.
Como A e finito, existe algum a1 ∈ A tal que α[1]n = a1 para uma infinidade de n. Mas entao existe
algum a2 ∈ A tal que α[2]n = a1a2 para uma infinidade de n, existe algum a3 ∈ A tal que α[2]
n = a1a2a3
para uma infinidade de n, e assim sucessivamente. Construimos assim uma palavra infinita a1a2a3 . . .Consideremos agora a subsucessao (αin)n definida do seguinte modo: seja i1 o primeiro ındice n talque α[1]
n = a1, seja i2 o primeiro ındice n > i1 tal que α[2]n = a1a2, seja i3 o primeiro ındice n > i3
tal que α[3]n = a1a2a3, e assim sucessivamente. E facil verificar que a subsucessao esta bem definida
e converge para a1a2a3 . . . ∈ Aω. �
Os espacos metricos (A∞, d′) dizem-se espacos de Cantor. Quem ja ouviu falar de conjunto deCantor pode ficar algo confuso... entao o conjunto de Cantor C nao e esse conjunto estranho que seobtem removendo o terco interior ]1
3 ,23 [ do intervalo [0, 1] e seguindo removendo o terco interior de
cada um dos pequenos intervalos que vao aparecendo, ate ao infinito? Qual e a relacao com (A∞, d′)?Ha de fato uma relacao, pois o conjunto de Cantor descrito acima, com a metrica usual herdada
de R, e homeomorfo a (A∞, d′) se |A| = 2. Consideremos os numeros reais de [0, 1] escritos na base3. Cada numero e uma dızima, finita ou infinita, composta pelos algarismos 0, 1, 2. Tal como nabase 10, ha um pequeno problema de dupla representacao. Por exemplo, as dızimas 0, 1 e 0, 0222 . . .representam o mesmo numero real. Se for possıvel, optaremos pela dızima que nao contenha 1. Se naofor possıvel, tanto faz... Tudo isto porque o conjunto de Cantor corresponde precisamente a todas asdızimas que nao contem o algarismo 1: eliminar o terco interior de cada intervalo corresponde semprea eliminar as dızimas contendo 1! Logo existe uma bijecao entre C e {0, 2}∞. E pode verificar-seque e um homeomorfismo (ver o Exercıcio 5.2).
5.3 Construcao do bordo
Introduzimos agora uma segunda ultrametrica em FA: a metrica dos prefixos de FA e definida apartir da metrica dos prefixos de A∗ por
d′(g, h) = d′(g, h) (g, h ∈ FA).
41
Resulta imediatamente do Lema 5.3 queLema 5.6 A funcao d′ e uma ultrametrica em FA.
Analogamente, o espaco metrico (FA, d′) e discreto, ao contrario do que acontece com a metricaprofinita d. Efetivamente, e facil confirmar que
d(an!, 1) < 2−n
para todo n ∈ N: se ϕ : FA → F e um homomorfismo de grupos e |F | ≤ n, entao (aϕ)|F | = 1 implicaan!ϕ = (aϕ)n! = 1, logo precisamos no mınimo de |F | = n+ 1 para separar 1 de an!. Logo {1} nao eaberto e (FA, d) nao e discreto.
Qual e o completado de (FA, d′)?Uma palavra α ∈ Aω sem fatores do tipo aa−1 (a ∈ A) diz-se uma palavra infinita reduzida.
Designamos por ∂FA o conjunto de todas as palavras infinitas reduzidas. Estendemos a ultrametricad′ : FA × FA → R a FA = FA ∪ ∂FA da forma obvia, adaptando o que fizemos para A∞. Os mesmosargumentos permitem mostrar que:Teorema 5.7 (FA, d′) e o completado de (FA, d′).
Teorema 5.8 (FA, d′) e compacto.O espaco ∂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 vertice. Um raio e umageodesica infinita, isto e, um caminho infinito em que cada seccao finita e uma geodesica.
Dado um subconjunto Y de um espaco metrico X, designamos por Fec(Y ) o fecho de Y , quepode ser definido como o menor fechado contendo Y , ou o conjunto dos pontos de X que sao limitede sucessoes em Y .
O resultado seguinte mostra que os automatos de Stallings podem desempenhar tambem umpapel em relacao ao bordo.Proposicao 5.9 Seja H ≤f.g. FA e seja Fec(H) o fecho de H em FA. Entao
Fec(H) = H ∪ (Lω(S(H)) ∩ ∂FA).
Prova. Como (FA, d′) e discreto, temos Fec(H) ∩ FA = H. Seja α ∈ ∂FA. Temos que provar que
α ∈ Fec(H)⇔ α ∈ Lω(S(H)). (7)
Suponhamos que α ∈ Fec(H). Entao α = limn→+∞ hn para alguma sucessao (hn)n em H.Suponhamos que α /∈ Lω(S(H)). Entao podemos fatorizar α = uaβ com u ∈ A∗ e a ∈ A taisque q0
u−→q e um caminho em S(H) mas nao existe nenhuma aresta da forma qa−→ . . .. Como
α = limn→+∞ hn, existe p ∈ N tal que d′(hn, α) < 2−|u| para todo n ≥ p. Mas entao |α ∧ hp| > |u|,logo ua ≤ hp. Pelo Teorema 4.3(ii), isto implica a existencia de uma aresta q
a−→ . . . em S(H),contradicao. Logo α ∈ Lω(S(H)).
Reciprocamente, seja α = a1a2a3 · · · ∈ Lω(S(H)), com ai ∈ A. Seja m o numero de vertices deS(H). Para cada n ≥ 1, existe alguma palavra wn ∈ RA de comprimento < m tal que a1 · · · anwn ∈L(S(H)). Logo a1 · · · anwn ∈ L(S(H)) ∩ RA = H pelo Teorema 4.3(ii), e portanto a1 · · · anwn ∈ H.Como |wn| < m, temos |a1 · · · anwn ∧ α| ≥ n − m para todo n ∈ N, logo resulta facilmente queα = limn→+∞ a1 · · · anwn e α ∈ Fec(H). Logo (7) e valido como pretendıamos. �
42
5.4 Exercıcios
(5.1) Seja A o automato descrito por
// •a
** •c
jj
b
��//
Calcule L(A) e Lω(A).
(5.2) Seja A = {0, 2} e seja ϕ : A∞ → C a bijecao definida no final da Subseccao 5.2. Mostre que:
(a) 3−|α∧β|−1 ≤ |αϕ− βϕ| ≤ 3−|α∧β| para todas α, β ∈ A∞ distintas;
(b) ϕ e um homeomeorfismo (para a metrica d′ em A∞ e a metrica usual em C).
(5.3) No espaco metrico (FA, d′),
(a) calcule d′(abaω, aba−1b−1);
(b) determine B 14(abaω).
(5.4) Calcule os seguintes limites em (FA, d′):
(a) limn→+∞ anb2n;
(b) limn→+∞(ab2a−1)n.
(5.5) Calcule Fec(H) para cada um dos seguintes subgrupos de F2:
(a) H = 〈a, bab−1〉;(b) H = 〈a, b2, bab−1〉.
(5.6) Seja H ≤f.g. FA e g ∈ G. Mostre que, para a metrica d′,
Fec(Hg) = Hg ∪ (Lω(S(H)) ∩ ∂FA).
43
6 Pontos fixos de endomorfismos
Nesta seccao usamos os automatos 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 pontofixo 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 atraves de uma propriedade, a primeira questao que se poee saber se ele e finitamente gerado ou nao, pois nesse caso podemos ambicionar a construcao dorespetivo automato de Stallings, com todas as vantagens que lhe estao inerentes. Vamos ver que essee o caso dos endomorfismos de um grupo livre:Teorema 6.1 (Goldstein e Turner 1986) Seja ϕ um endomorfismo de FA. Entao Fix(ϕ) e finita-mente gerado.
Prova. Para todo g ∈ FA, seja pg = g−1(gϕ) ∈ FA. Note-se que 1 = p1 e g ∈ Fix(ϕ) se e so sepg = 1. Definimos um A-automato A = (P, 1, 1, E) por
P = {pg | g ∈ FA};
E = {(pg, a, pga) | g ∈ FA, a ∈ A}.
Provamos em seguida uma serie le lemas intermedios que nos ajudarao a demonstrar o teorema:Lema 6.2 A e um automato inverso e L(A) = (Fix(ϕ))θ−1.
Prova. E imediato que A e determinıstico. Sejam g ∈ FA e a ∈ A. Como pgaa−1 = pg, resulta que(pga, a−1, pg) e tambem uma aresta de A, logo A e involutivo.
Dado u = a1 . . . an ∈ A∗, com ai ∈ A, existe um caminho (unico) do tipo 1 u−→ . . ., a saber:
1 = p1a1−→pa1θ
a2−→p(a1a2)θa3−→ . . .
an−→puθ.
Logo, para todo g ∈ FA, existe um caminho bem-sucedido 1g−→pg
g−1
−−→1 e A e aparado.Finalmente,
u ∈ L(A)⇔ puθ = 1⇔ uθ ∈ Fix(ϕ)⇔ u ∈ (Fix(ϕ))θ−1.
�
No entanto, o automato A e infinito caso ϕ 6= 1FA: se aϕ 6= a para algum a ∈ A, entao e facil
ver que akϕ 6= ak para todo k ∈ N (usando o Lema 3.6), donde resulta que os vertices pak sao todosdistintos. Como proceder? A estrategia e apontada pelo seguinte lema:Lema 6.3 Se A possuir um subautomato finito A′ tal que Fix(ϕ) ⊆ L(A′), entao Fix(ϕ) e finita-mente gerado.
Prova. Se Fix(ϕ) ⊆ L(A′), entao Fix(ϕ) ⊆ L(A′) ⊆ L(A). Pelo Lema 6.2, temos
L(A) = (Fix(ϕ))θ−1 = Fix(ϕ),
logo Fix(ϕ) ⊆ L(A′) ⊆ Fix(ϕ) e portanto L(A′) = Fix(ϕ). Daqui resulta que Fix(ϕ) = (L(A′))θ.Como A′ e finito, L(A′) e uma A-linguagem racional, e logo Fix(ϕ) e um subconjunto racional
de FA pela Proposicao 3.13. Logo Fix(ϕ) e finitamente gerado pelo Teorema 3.14. �
44
Sejahϕ = max {|aϕ| : a ∈ A}
e fixemosP ′ = {pg ∈ P : |pg| ≤ 2hϕ + 1}.
Como A e finito, P ′ tambem o e. No entanto, pode haver uma infinidade de elementos g ∈ FA a darorigem ao mesmo vertice pg.
Dado g ∈ FA, seja gι = g[1]. Por outras palavras, gι e a primeira letra de g caso g 6= 1, e e iguala 1 caso contrario. Dizemos que uma aresta (q, a, q′) ∈ E e:
• central se q, q′ ∈ P ′;
• compatıvel se nao for central e qι = a.
O proximo lema recolhe algumas propriedades elementares envolvendo estes conceitos:Lema 6.4 (i) So existe um numero finito de arestas centrais em A.
(ii) Se (q, a, q′) ∈ E e nao central, entao (q, a, q′) ou (q′, a−1, q) e compatıvel.
(iii) Para cada q ∈ P , existe no maximo uma aresta compatıvel com origem em q.
Prova. (i) Porque A e P ′ sao ambos finitos.(ii) Suponhamos que (q, a, q′) nao e nem central nem compatıvel. Entao podemos escrever qι =
b ∈ A \ {a}. Suponhamos que |q| ≤ hϕ. Entao |q′| = |a−1q(aϕ)| ≤ 2hϕ + 1 e (q, a, q′) seria central,absurdo. Logo |q| > hϕ.
Escrevendo q = bg, obtemos q′ = a−1q(aϕ) = a−1bg(aϕ). Como b 6= a e |g| ≥ hϕ, obtemosq′ = a−1bg(aϕ). Logo q′ι = a−1 e (q′, a−1, q) e compatıvel.
(iii) Porque uma aresta compatıvel com origem em q tem necessariamente rotulo qι, e A edeterminıstico. �
Um caminho (possivelmente infinito) q0a1−→q1
a2−→ . . . em A diz-se:
• central se todos os seus vertices estiverem em P ′;
• compatıvel se todas as suas arestas forem compatıveis e nenhum vertice intermedio pertencera P ′.
Lema 6.5 Seja u ∈ Fix(ϕ). Entao existe em A um caminho
1 = q′0u0−→q′′0
v1−→q1w−1
1−→q′1u1−→q′′1
v2−→ . . .vn−→qn
w−1n−→q′n
un−→q′′n = 1 (8)
tal que:
(i) u = u0v1w−11 u1 . . . vnw
−1n un;
(ii) os caminhos q′juj−→q′′j sao centrais;
(iii) os caminhos q′′j−1
vj−→qj e q′jwj−→qj sao compatıveis;
(iv) qj /∈ P ′ se vj e wj forem ambas 6= 1.
45
Prova. Como 1 ∈ P ′ e u ∈ L(A) pelo Lema 6.2, existe um caminho
1 = q′0u0−→q′′0
x1−→q′1u1−→q′′1
x2−→ . . .xn−→q′n
un−→q′′n = 1
em A tal que u = u0x1u1 . . . xnun e os caminhos q′juj−→q′′j (que podem ser triviais!) recolhem todas
as occorrencias de vertices em P ′ (sendo consequentemente caminhos centrais).Pelo Lema 6.4(ii), se uma aresta (r, a, s) ocorre num caminho q′′j−1
xj−→q′j , entao (r, a, s) ou(s, a−1, r) e compatıvel. Por outro lado, como xj e reduzida, resulta do Lema 6.4(iii) que q′′j−1
xj−→q′jse pode fatorizar como
q′′j−1
vj−→qjw−1
j−→q′jcom q′′j−1
vj−→qj e q′jwj−→qj compatıveis. Note-se que a condic ao (iv) e valida porque nenhum vertice
intermedio de q′′j−1
xj−→q′j pode pertencer a P ′. �
Dizemos que um caminho compatıvel q0a1−→q1
a2−→ . . . e maximal se for infinito ou nao puder serprolongado (a direita) continuando compatıvel.Lema 6.6 Para cada q ∈ P ′, existe em AT um unico caminho compatıvel maximal Mq com origemem q.
Prova. E claro que qualquer caminho compatıvel pode ser estendido a um caminho compatıvelmaximal. A unicidade resulta do Lemma 6.4(iii). �
Definimos agora
P ′1 = {q ∈ P ′ |Mq so tem um numero finito de arestas distintas}
e P ′2 = P ′ \ P ′1. Logo Mq nao contem ciclos se q ∈ P ′2. Pelo Lema 6.6, se os caminhos Mq e Mq′ seintersetarem num vertice rqq′ , entao eles vao coincidir a partir de rqq′ . Em particular, se Mq e Mp′
se intersetarem, entao q ∈ P ′1 se e so se q′ ∈ P ′1. Seja
Y = {(q, q′) ∈ P ′2 × P ′2 | Mq interseta Mq′}.
Para cada (q, q′) ∈ Y , seja Mq \Mq′ o subcaminho (finito) q−→rqq′ de Mq. Note-se que se q′ = q,entao Mq \Mq′ e o caminho trivial no vertice q.
Seja A′ o subautomato de A contendo:
• todos os vertices em P ′ e todas as arestas centrais;
• todos os vertices e arestas nos caminhos Mq (q ∈ P ′1) e as respetivas arestas inversas;
• todos os vertices e arestas nos caminhos Mq \Mq′ ((q, q′) ∈ Y ) e as respetivas arestas inversas.
Segue facilmente do Lema 6.4(i) e das definicoes de P ′1 e Mq \Mq′ que A′ e um subautomato finitode A. Pelo Lema 6.3, basta mostrar que Fix(ϕ) ⊆ L(A′).
Seja u ∈ Fix(ϕ). Consideremos o caminho fatorizado (8) fornecido pelo Lema 6.5. Como A′contem todas as arestas centrais de A, basta mostrar que todos os subcaminhos
q′′j−1
vj−→qjw−1
j−→q′j
aparecendo em (8) sao caminhos em A′.
46
Se perda de generalidade, podemos assumir que vj 6= 1. Se wj = 1, entao q′′j−1 ∈ P ′1 e temos opretendido pois A′ contem o caminho Mq′′j−1
, logo podemos assumir que wj 6= 1 tambem. Se um dosvertices q′′j−1, q
′j estiver em P ′1, o outro tambem esta e de novo obtemos o pretendido. Logo podemos
assumir que q′′j−1, q′j ∈ P ′2.
Daqui resulta que qj = rq′′j−1,q′j: como vjw−1
j ∈ RA, e facil ver que os caminhos Mq′′j−1e Mq′j
nao sepodem encontrar antes de pj . Logo q′′j−1
vj−→qj e precisamente Mq′′j−1\Mq′j
e q′jwj−→qj e precisamente
Mq′j\Mq′′j−1
. Portanto sao ambos caminhos em A′ como necessitavamos. �
Em geral, o problema de construir efetivamente S(Fix(ϕ)) (equivalente a calcular uma base paraFix(ϕ)) e muito difıcil, mesmo para automorfismos de FA. Maslakova publicou uma prova paraautomorfismos em 2003, que se descobriu mais tarde conter erros. Recentemente, foram anunciadosresultados que cobrem o caso de todos os endomorfismos de FA, mas estao ainda sendo verificados.
O exemplo seguinte mostra um caso em que e facil calcular todos os pontos fixos:Exemplo 6.7 Seja ϕ o automorfismo de F2 definido por aϕ = aba−1 e bϕ = a. Entao Fix(ϕ) = 〈ab〉.
Antes de proceder ao calculo, confirmamos que ϕ e um automorfismo tomando o endomorfismoψ de F2 definido por aψ = b e bψ = b−1ab. Como ϕψ = ψϕ = 1, entao ϕ e ψ sao automorfismos.
E imediato que (ab)ϕ = aba−1a = ab, logo ab ∈ Fix(ϕ) e 〈ab〉 ⊆ Fix(ϕ). Reciprocamente, sejau ∈ Fix(ϕ), digamos
u = an0bm1an1bm2an2 . . . bmk−1ank−1bmkank
com k ≥ 0, m1, . . . ,mk, n1, . . . , nk−1 6= 0. Se k = 0, entao u = 1, logo podemos assumir que k > 0 eescrever
uϕ= (abn0a−1)am1(abn1a−1)am2(abn2a−1) . . . amk−1(abnk−1a−1)amk(abnka−1)= (abn0a−1)am1+1bn1am2bn2 . . . amk−1bnk−1amk−1(abnka−1).
Comparando as series de b’s em u = uϕ, concluimos que n0 6= 0 = nk ou n0 = 0 6= nk.Suponhamos que n0 6= 0 = nk. Entao u = uϕ traduz-se por
an0bm1an1bm2an2 . . . bmk−1ank−1bmk = abn0am1bn1am2bn2 . . . amk−1bnk−1amk−1,
logo obtemos sucessivamente
1 = n0 = m1 = n1 = . . . = mk−1 = nk−1 = mk
e u = (ab)k ∈ 〈ab〉.Caso n0 = 0 6= nk, podemos substituir u por u−1 e usar o caso anterior. Logo Fix(ϕ) = 〈ab〉.
6.2 Pontos fixos no bordo
Vamos agora apresentar alguns resultados sobre pontos fixos no bordo, sem demonstracao.Como (FA, d′) e um espaco metrico discreto, toda funcao de domınio FA e contınua. Mas ha
uma versao mais forte da continuidade que e ainda mais util, em que as constantes na condicao decontinuidade nao dependem do ponto considerado. Mais precisamente, uma funcao ϕ : (X, d) →(X ′, d′) entre espacos metricos diz-se uniformemente contınua se:
∀ε > 0 ∃δ > 0 ∀x, y ∈ X (d(x, y) < δ ⇒ d(xϕ, yϕ) < ε).
47
A grande vantagem e que se ϕ for uniformente contınua, existe uma (unica) extensao contınuaΦ : X → Y de ϕ aos completados de X e Y . A extensao e definida por
αΦ = limn→+∞
(xnϕ),
onde (xn)n e uma sucessao de X que converge para α.Nem todos os endomorfismos de FA sao uniformente contınuos, mas os endomorfismos injetivos
tem essa propriedade. Logo todo o endomorfismo injetivo ϕ de FA admite uma unica extensaocontınua Φ : FA → FA (e por restricao, ao bordo ∂FA). Os pontos fixos α ∈ Fix(Φ) ∩ ∂FA dizem-seos pontos fixos infinitos de φ.Exemplo 6.8 Seja ϕ o endomorfismo de F2 definido por aϕ = aba−1 e bϕ = a2. Entao Fix(ϕ) = {1}mas α = aba2b2a4b4 . . . a2n
b2n. . . ∈ Fix(Φ).
Procedendo analogamente ao Exemplo 6.7, mostramos que Fix(ϕ) = {1}.Para todo n ∈ N, seja un = Πn
i=0a2ib2
i. E claro que α = limn→+∞ un, logo uΦ = limn→+∞(unϕ).
Temos(a2i
b2i)ϕ = (aba−1)2i
(a2)2i= (ab2
ia−1)a2i+1
= ab2ia2i+1−1,
logo
unϕ =n∏i=0
ab2ia2i+1−1 = a(
n∏i=0
b2ia2i+1
)a−1 = (n∏i=0
a2ib2i)a2n+1−1 = una
2n+1−1.
Como una2n+1−1 ∈ RA, resulta facilmente que
αΦ = limn→+∞
(unϕ) = limn→+∞
una2n+1−1 = α,
logo α e um ponto fixo infinito de ϕ.
Que se pode dizer sobre os pontos fixos infinitos de ϕ? E facil ver que Fec(Fix(ϕ)) ⊆ Fix(Φ): seα = limn→+∞(xnϕ) para alguma sucessao em Fix(ϕ), entao
αΦ = limn→+∞
(xnϕ) = limn→+∞
xn = α.
Tais pontos fixos infinitos dizem-se singulares. Os restantes dizem-se regulares. Seja Fixr(ϕ) oconjunto dos pontos fixos infinitos regulares de ϕ. O resultado seguinte mostra que Fixr(ϕ) e numcerto sentido finitamente gerado:Teorema 6.9 (Silva 2010) Seja ϕ um endomorfismo injetivo de FA. Entao existem α1, . . . , αm ∈Fixr(ϕ) tais que
Fixr(ϕ) = Fix(ϕ)α1 ∪ . . . ∪ Fix(ϕ)αm.
Este resultado foi provado para automorfismos por Cooper em 1987.Se ϕ for um automorfismo de FA (com extensao contınua Φ a FA), e tambem possıvel proceder a
classificacao dos pontos fixos infinitos regulares do ponto de vista da teoria dos sistemas dinamicos.Dizemos que α ∈ Fixr(ϕ) e um:
• atrator se∃ε > 0 ∀β ∈ FA (d′(α, β) < ε⇒ lim
n→+∞(βΦn) = α);
48
• repulsor se for um atrator para ϕ−1.
Noutros sistemas dinamicos, podem existir outros tipos (hiperbolico, degenerado), mas nao no nossocaso:Teorema 6.10 (Gaboriau, Jaeger, Levitt e Lustig 1998) Seja ϕ um automorfismo de FA. Entaotodo α ∈ 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 fixosde ϕ 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.
(b) Calcule Fix(Φ).
(c) Mostre que os pontos fixos infinitos de ϕ sao 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 periodico se hϕn = h paraalgum n ≥ 1. Seja A = {a, b, c, d} e seja ϕ o endomorfismo de FA definido por
aϕ = b, bϕ = a, cϕ = c2, dϕ = d2.
Calcule o conjunto dos pontos periodicos de ϕ.
49
7 Apresentacoes de grupos
Nesta seccao deixamos para tras o grupo livre e procuramos ferramentas para lidar com grupos maisgerais.
7.1 Geradores e relatores
Dado um grupo G, sabemos pelo Teorema 3.4 que G e isomorfo a algum quociente de um grupo livreFA. Isto equivale a dizer que existe um homomorfismo sobrejetivo ϕ : FA → G. Pelo Teorema 1.5,temos Ker(ϕ)EFA e G ∼= FA/Ker(ϕ), logo G e determinado por A e Ker(ϕ), a menos de isomorfismo.
Como Aϕ gera G, dizemos por extensao que A e um conjunto de geradores de G. Quanto aKer(ϕ), qual a forma mais simples de descreve-lo?
Na Subseccao 1.4, definimos subgrupo gerado por um subconjunto. De forma analoga, dado umsubconjunto X de um grupo G, definimos o subgrupo normal gerado por X como sendo o conjuntodos elementos da forma
(a1xε11 a−11 ) . . . (anxεn
n a−1n ),
onde n ≥ 0, ai ∈ G, xi ∈ X e εi ∈ {1,−1} para i = 1, . . . , n. E facil verificar que este e efetivamenteo menor subgrupo normal de G contendo X, sendo representado por 〈〈X〉〉.
Voltando a representacao de G ∼= FA/Ker(ϕ), podemos entao descrever Ker(ϕ) atraves de umsubconjunto R tal que Ker(ϕ) = 〈〈R〉〉. A vantagem e que R pode ser muito mais pequeno e facil dedescrever que Ker(ϕ)! Dizemos que um tal R e um conjunto de relatores de G, e a expressao formal〈A | R〉 diz-se uma apresentacao de G.
Inversamente, podemos comecar com um conjunto A e um subconjunto R ⊆ FA quaisquer. Entao〈A | R〉 constitui uma apresentacao de FA/〈〈R〉〉, bem como de qualquer grupo que lhe seja isomorfo.
7.2 Grupos finitamente apresentaveis
Uma apresentacao 〈A | R〉 diz-se finita se A e R forem ambos finitos. Um grupo diz-se finitamenteapresentavel se admitir uma apresentacao finita.
As apresentacoes mais simples sao as da forma 〈A | ∅〉, que definem os grupos livres FA. O exemploseguinte envolve uma apresentacao com um unico relator. Introduzimos a notacao [g, h] = ghg−1h−1
para quaisquer elementos g, h ∈ G. Um elemento desta forma diz-se um comutador de G.Exemplo 7.1 〈a, b | [a, b]〉 e uma apresentacao de Z× Z.
Para mostrar isto, definimos um homomorfismo ϕ : F2 → Z× Z por aϕ = (1, 0) e bϕ = (0, 1). Eclaro que ϕ e sobrejetivo e [a, b] ∈ Ker(ϕ). Seja N = 〈〈[a, b]〉〉. Entao N ⊆ Ker(ϕ) e pelo Teorema1.5 ϕ induz um homomorfismo (sobrejetivo) Φ : F2/N → Z × Z definido por (aN)Φ = (1, 0) e(bN)Φ = (0, 1).
Por outro lado, definimos Ψ : Z× Z→ F2/N por (m,n)Ψ = ambnN . Como abN = baN , resultafacilmente que ambnN = bnamN 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 〈a, b | [a, b]〉 e uma apresentacao de Z× Z.
Vejamos em seguida que todos os grupos finitos sao finitamente apresentaveis:
50
Proposicao 7.2 Todo grupo finito e finitamente apresentavel.
Prova. Seja G um grupo finito. Seja A = {ag | g ∈ G} um alfabeto em bijecao com G e seja
R = {agaha−1gh | g, h ∈ G}.
Vamos mostrar que 〈A | R〉 e uma apresentacao de G.Seja ϕ : FA → G o homomorfismo sobrejetivo definido por agϕ = g e seja N = 〈〈R〉〉. Como
R ⊆ Ker(ϕ), resulta do Teorema 1.5 que ϕ induz um homomorfismo (sobrejetivo) Φ : FA/N → Gdefinido por (agN)Φ = g.
Como a1a1a−11 ∈ R, obtemos a2
1N = a1N e logo a1N = N . Por outro lado, como agag−1a−11 ∈ R,
obtemos a−1g N = (ag−1N)(a−1
1 N) = ag−1N . Junto com as relacoes agahN = aghN e a1N = N ,isto implica que todo elemento de FA/N se pode escrever na forma agN 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 existencia de uma apresentacao finita e independente do conjunto(finito) de geradores considerado:Proposicao 7.3 Seja G um grupo finitamente apresentavel e seja ψ : FB → G um homomorfismosobrejetivo de grupos com B finito. Entao G admite uma apresentacao finita da forma 〈B | S〉.
Prova. Seja 〈A | R〉 uma apresentacao finita de G, e seja ϕ : FA → G o correspondente homomor-fismo 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,existe um homomorfismo β : FB → FA tal que o diagrama
FAϕ // G
FB
ψ
>>~~~~~~~~~~~~~~~~
β
OO������
comuta.Seja
S = Rα ∪ {b−1(bβα) | b ∈ B}
e N = 〈〈S〉〉. Como bN = (bβα)N para todo b ∈ B, resulta facilmente que
uN = (uβα)N para todo u ∈ FB. (9)
51
E facil verificar que S ⊆ Ker(ψ), logo N ⊆ Ker(ψ). Reciprocamente, seja u ∈ Ker(ψ). Comouβϕ = uψ = 1 e Kerϕ = 〈〈R〉〉, obtemos
uβα ∈ 〈〈R〉〉α ⊆ 〈〈Rα〉〉 ⊆ N.
Aplicando (9), resulta que u ∈ N e logo Ker(ψ) ⊆ N . Logo Ker(ψ) = N = 〈〈S〉〉 e 〈B | S〉 e umaapresentacao finita de G. �
7.3 Decidibilidade
O problema da palavra ganha generalidade no contexto as apresentacoes: dizemos que a apresentacao〈A | R〉 tem problema da palavra decidıvel se existir um algoritmo que determine se um elementoarbitrario de FA pertence a N = 〈〈Rθ〉〉. Como uN = vN se e so se u−1v ∈ N , isto equivale a poderdeterminar quando dois elementos de FA representam o mesmo elemento de FA/N .
Tal como na Proposicao 7.3, a decidibilidade do problema da palavra nao depende da apresentacaoconsiderada para o grupo:Proposicao 7.4 Sejam 〈A | R〉 e 〈B | S〉 apresentacoes finitas de um grupo G. Entao 〈A | R〉 temproblema da palavra decidıvel se e so se 〈B | S〉 tem problema da palavra decidıvel.
Prova. Suponhamos que 〈A | R〉 tem problema da palavra decidıvel. Tal como na prova daProposicao 7.3, consideramos o diagrama comutativo
FAϕ // G
FB
ψ
>>~~~~~~~~~~~~~~~~
β
OO������
onde ϕ e ψ sao sobrejetivos, Ker(ϕ) = 〈〈R〉〉 e Ker(ψ) = 〈〈S〉〉. Dado u ∈ FB, temos
u ∈ 〈〈S〉〉 ⇔ uψ = 1⇔ uβϕ = 1⇔ uβ ∈ 〈〈R〉〉.
Como podemos decidir se uβ ∈ 〈〈R〉〉, entao 〈B | S〉 tem problema da palavra decidıvel. Por simetria,obtemos o resultado. �
Gracas a Proposicao 7.4, podemos dizer que um grupo finitamente apresentavel tem problemada palavra decidıvel ou indecidıvel sem especificarmos a apresentacao (finita).
O resultado seguinte foi demonstrado de forma independente por Novikov e Boone durante aGuerra Fria, numa epoca em que a matematica produzida em cada um dos blocos era pouco divulgadano outro:Teorema 7.5 (Novikov 1955, Boone 1957) Existem grupos finitamente apresentaveis com problemada palavra indecidıvel.
A prova deste teorema e complexa e pode ser obtida codificando uma das estruturas mais geraisda teoria da computacao (a maquina de Turing) atraves de uma apresentacao finita de um grupo! A
52
indecidibilidade do chamado problema da paragem da maquina de Turing implica entao a indecidi-bilidade do problema da palavra do grupo.
Como consequencia do Teorema 7.5, todos os problemas algebricos nao triviais se revelam inde-cidıveis para apresentacaoes finitas arbitrarias de grupos. Por exemplo:Teorema 7.6 (Adjan 1955, Rabin 1958) E indecidıvel se um grupo finitamente apresentavel ar-bitrario e trivial, finito, infinito, livre.
7.4 Diagramas de van Kampen
Os diagramas de van Kampen constituem uma das ferramentas geometricas classicas para estudarapresentacoes de grupos.
Um grafo Γ = (V,E) diz-se planar se puder ser realizado geometricamente num plano, isto e, sepudermos representar V e E como conjuntos de pontos e linhas no plano de forma a que as linhasnao se intersetem fora dos vertices. Por exemplo, o grafo completo com 4 vertices (K4) e planar poisadmite a representacao
•
��������������
//////////////
•
~~~~~~~
@@@@@@@
• •enquanto K5 constitui o mais pequeno exemplo (em termos de vertices) de grafo nao planar
•
oooooooooooooo
OOOOOOOOOOOOOO
��������������
//////////////
•
@@@@@@@
UUUUUUUUUUUUUUUUUUUU •
~~~~~~~
iiiiiiiiiiiiiiiiiiii
• •
e o grafo bipartido K3,3
•
@@@@@@@
OOOOOOOOOOOOOO •
~~~~~~~
@@@@@@@ •
oooooooooooooo
~~~~~~~
• • •e o grafo nao planar com menor numero de arestas.
O conceito de planaridade estende-se da maneira obvia a grafos orientados e a A-grafos. UmA-grafo diz-se conexo se for conexo enquanto grafo nao orientado.
Note-se que um grafo (grafo orientado, A-grafo) planar finito divide o plano num numero finitode regioes (incluindo a regiao exterior). A fronteira de uma regiao e o conjunto dos vertices e dasarestas que lhe sao adjacentes. No caso de um A-grafo conexo, o bordo de uma regiao e uma palavraw ∈ A∗ obtida lendo sucessivamente o rotulo das arestas da sua fronteira, comecando num verticequalquer e seguindo o sentido horario ou anti-horario. Para este efeito, lemos o rotulo das arestascomo se o automato fosse involutivo. Note-se que o bordo de uma regiao pode ser representado porvarias palavras, mas cada uma delas sera sempre um conjugado cıclico ou o inverso de um conjugadocıclico da outra.
53
Exemplo 7.7 Seja A = {a, b} e seja Γ o A-grafo descrito por
• b //
a
��@@@@@@@ •
a��@@@@@@@ •aoo
•
a??~~~~~~~
• b //a
oo •a
??~~~~~~~
b��~~~~~~~
•b
__@@@@@@@
As 4 regioes interiores de Γ tem bordo a3 (duas vezes), aba−1b−1 e b3, enquanto a regiao exteriortem bordo ba−2b2a2.
Seja P = 〈A | R〉 uma apresentacao de grupos. E claro que podemos sempre assumir que osrelatores de R estao na forma reduzida. Como u = 1 se e so se xux−1 = 1 em qualquer grupo,podemos ate assumir que os relatores sao palavras ciclicamente reduzidas. Sob esta suposicao,definimos diagrama de van Kampen de P como sendo um A-grafo conexo finito em que:
• cada regiao interior admite como bordo um relator de R;
• o bordo da regiao exterior e ciclicamente reduzido.
Note-se que, para ler o relator de R, temos o direito de escolher o vertice inicial e o sentido nocalculo do bordo da regiao interior. O bordo da regiao exterior diz-se o bordo do diagrama. Maisuma vez, um diagrama pode admitir como bordo varias palavras, mas cada uma delas sera sempreum conjugado cıclico ou o inverso de um conjugado cıclico da outra. A dimensao do diagrama e onumero de regioes interiores.
E imediato que o A-grafo do Exemplo 7.7 e um diagrama de van Kampen da apresentacao〈a, b | a3, b3, [a, b]〉 com bordo ba−2b2a2.
O resultado seguinte explica a importancia dos diagramas de van Kampen no estudo do problemada palavra. Note-se que para resolver o problema da palavra, basta considerar palavras ciclicamentereduzidas!Teorema 7.8 (van Kampen 1933) Seja P = 〈A | R〉 uma apresentacao de grupos com relatoresciclicamente reduzidos e seja w ∈ FA ciclicamente reduzida. Entao as condicoes seguintes sao equiv-alentes:
(i) w = (x1r1x−11 ) . . . (xkrkx−1
k ) para alguns k ≥ 0, ri ∈ R ∪R−1 e xi ∈ FA;
(ii) existe um diagrama de van Kampen de P de dimensao k e bordo w.
Alem disso, se R for finito e M = max {|r| : r ∈ R}, podemos assumir que
|xi| ≤12
(k|w|+ k2M) para i = 1, . . . , k. (10)
Prova. (i) ⇒ (ii). Consideramos o A-grafo involutivo descrito por
•rk%% • x1 //
x2
��@@@@@@@
x3
��
xkoo • r1ee
. . . •
r3
DD •r2
54
ao qual removemos em seguida todas as arestas com rotulo em A−1. Obtemos assim um A-grafoplanar conexo com k regioes interiores. O ultimo passo consiste em executar a dobragem sucessivade arestas da forma
•
��� •
���
a
&&MMMMMMMMMMMMM
•
a
88pppppppppppppa
// • ou •a
//
quando nao exista nenhuma aresta no meio! Esta versao da dobragem de arestas preserva a pla-naridade do grafo, a conexidade e o numero de regioes interiores, bem como os seus bordos (quepermanecem relatores de R). Quando o processo terminar, poderemos ler no bordo a palavra(x1r1x
−11 ) . . . (xkrkx−1
k ), isto e, w. Logo construımos um diagrama de van Kampen de P de di-mensao k e bordo w.
(ii) ⇒ (i). Procedemos por inducao sobre a dimensao do diagrama de van Kampen. O unicodiagrama de dimensao 0 e o diagrama trivial que contem apenas um unico vertice e tem como bordoa palavra vazia. Logo a implicacao e valida para k = 0. Alem disso, se R for finito entao (10) etrivialmente verificada.
Suponhamos agora que D e um diagrama de dimensao k > 0 e bordo w, e que a implicacao (ii)⇒ (i) e valida para diagramas de dimensao k − 1. Supomos ainda que (10) e verificada para k − 1quando R e finito.
Para efeitos de representacao de rotulos de regioes e caminhos, encaramos D como um A-grafoinvolutivo. Nesse caso, temos um loop em D
p wdd
que da origem ao bordo. Entre os vertices deste loop adjacentes a uma regiao interior, seja q o maisproximo de p. Trocando w por w−1 se necessario, podemos assumir que o loop de rotulo w se fatorizacomo
pu
** qv
jj
com uv = w e |u| ≤ |w|2 . Podemos assumir que a regiao interior I adjacente a q tem bordo v′z−1 deacordo com a figura
p u // qv′
++I q′z
kk v′′ // p
onde v′v′′ = v e q v′−→q′ e a parte da fronteira de I contıgua a regiao exterior. Seja D′ o A-grafoobtido removendo de D as arestas e os vertices intermedios do caminho q
v′−→q′. E facil verificarque D′ e um diagrama de van Kampen de P com bordo uz−1v′′ se z 6= 1 pois nesse caso uz−1v′′ eciclicamente reduzida. E se z = 1? Entao pode acontecer que uv′′ nao seja reduzida – por exemplo,se D for da forma
• p q
Nesse caso, se y e o nucleo cıclico de uv′′ = hyh−1, eliminamos as arestas de D′ correspondentes aorotulo h (e que estao totalmente imersas na face exterior do A-grafo). Logo podemos sempre afirmarem qualquer caso que existe um diagrama de van Kampen D′′ de P de dimensao k−1 que tem comobordo o nucleo cıclico y de uz−1v′′ = hyh−1. Note-se que |h| ≤ |w|2 e |y| ≤ |w|+M .
55
Pela hipotese de inducao, podemos escrever y = (x1r1x−11 ) . . . (xk−1rk−1x
−1k−1) para alguns ri ∈
R ∪ R−1 e xi ∈ FA. Alem disso, se R for finito, temos |xi| ≤ 12((k − 1)|y| + (k − 1)2M) para
i = 1, . . . , k − 1. Logo
w= uv = uv′v′′ = (u(v′z)u−1)(uz−1v′′) = (u(v′z)u−1)(hyh−1)= (u(v′z)u−1)((hx1)r1(hx1)−1) . . . ((hxk−1)rk−1(hxk−1)−1).
Como v′z e um conjugado cıclico de algum r ∈ R ∪R−1, (i) e valido.Suponhamos agora que R e finito. Podemos escrever u(v′z)u−1 = (ut)r(ut)−1 para algum t ∈ FA
tal que |t| ≤ M2 . Logo
|ut| ≤ |u|+ |t| ≤ |w|2
+M
2≤ 1
2(k|w|+ k2M).
Por outro lado, para i = 1, . . . , k − 1, temos
|hxi| ≤ |h|+ |xi| ≤ |w|2 + 12((k − 1)|y|+ (k − 1)2M)
≤ |w|2 + 12((k − 1)|w|+ (k − 1)M + (k − 1)2M) ≤ 1
2(k|w|+ k2M).
Logo (10) e valido e a prova esta completa. �
7.5 Funcoes isoperimetricas
Seja P = 〈A | R〉 uma apresentacao finita de um grupo G e seja ϕ : FA → G o correspondentehomomorfismo sobrejetivo. Dado w ∈ 1ϕ−1, definimos a area de w como sendo o menor k ≥ 0 talque
w = (x1r1x−11 ) . . . (xk−1rk−1x
−1k−1)
para alguns ri ∈ R ∪R−1 e xi ∈ FA. Designamo-la por Area(w).Uma funcao Iso : N→ [0,+∞[ diz-se uma funcao isoperimetrica para P se
Area(w) ≤ Iso(|w|)
para todo w ∈ 1ϕ−1.Certos tipos de funcoes sao particularmente importantes. Dizemos que uma funcao Iso : N →
[0,+∞[ e:
• linear se existir K > 0 tal que Iso(n) = Kn para todo n ∈ N;
• quadratica 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) = Kn para todo n ∈ N;
• recursiva se existir um algoritmo que calcula efetivamente Iso(n) para todo n ∈ N.
56
Exemplo 7.9 A apresentacao P = 〈a, b | [a, b]〉 de Z × Z admite uma funcao isoperimetricaquadratica.
Consideremos o homomorfismo ϕ : F2 → Z × Z definido por aϕ = (1, 0) e bϕ = (0, 1). SejamIso(n) = n2
4 e w ∈ 1ϕ−1. Vamos mostrar que Area(w) ≤ Iso(w) por inducao sobre |w|.Temos Area(w) = 0 quando |w| < 4 pois a unica palavra reduzida de comprimento < 4 em 1ϕ−1
e a palavra vazia. Suponhamos agora que |w| = n ≥ 4 e que a desigualdade Area(w′) ≤ Iso(w′) evalida para elementos w′ ∈ 1ϕ−1 de comprimento < n.
Podemos fatorizar w = uaεbma−εv (em forma reduzida) para alguns ε ∈ {1,−1} e m 6= 0.Entao w = (uaεbma−εb−mu−1)(ubmv). Como ambos os fatores desta fatorizacao pertencem a 1ϕ−1,podemos escrever
Area(w) ≤ Area(uaεbma−εb−mu−1) + Area(ubmv). (11)
Ora Area(xyx−1) = Area(y) para todos x ∈ FA e y ∈ 1ϕ−1, logo
Area(uaεbma−εb−mu−1) = Area(aεbma−εb−m).
Como existe um diagrama de van Kampen
• b // • b // • b // . . . b // •
•b//
a
OO
•b//
a
OO
•a
OO
b// . . .
b// •a
OO
de bordo aεbma−εb−m e dimensao m, resulta do Teorema 7.8 que Area(aεbma−εb−m) ≤ m < n2 . Por
outro lado, Area(ubmv) ≤ (n−2)2
4 por hipotese de inducao, logo resulta de (11) que
Area(w) <n
2+
(n− 2)2
4=
2n+ n2 − 4n+ 44
=n2 − 2n+ 4
4<n2
4
e portanto Iso e uma funcao isoperimetrica para P.
O seguinte resultado e uma das consequencias importantes do Teorema 7.8:Corolario 7.10 Seja P = 〈A | R〉 uma apresentacao finita. Entao as condicoes seguintes saoequivalentes:
(i) P tem problema da palavra decidıvel;
(ii) P admite uma funcao isoperimetrica recursiva.
Prova. (i) ⇒ (ii). Seja
Dehn(n) = max {Area(w) | w ∈ 〈〈R〉〉, |w| = n}.
E claro que a funcao Dehn constitui uma funcao isoperimetrica para P, dita funcao de Dehn de P.Note-se que Dehn(n) ≤ Iso(n) para toda outra funcao isoperimetrica Iso.
Para mostrar que a funcao Dehn e recursiva, tomamos w ∈ FA com |w| = n. Podemos utilizar(i) para decidir se w pertence ou nao a 〈〈R〉〉. Suponhamos que pertence. Agora basta mostrar queArea(w) e computavel, para o que utilizamos o seguinte algoritmo:
57
Para k = 0, 1, 2, . . ., vamos testar se Area(w) = k verificando se a igualdade
w = (x1r1x−11 ) . . . (xkrkx−1
k ) (12)
e valida em FA para alguma escolha de xi ∈ FA e ri ∈ R ∪ R−1. Pelo Teorema 7.8, so temos quetestar um numero finito de xi, e o mesmo acontece com os ri visto que R e finito. Como w ∈ 〈〈R〉〉,acabaremos inevitavelmente por encontrar um valor de k para o qual (12), se verifique. Esse valor eArea(w). Logo a funcao Dehn e uma funcao isoperimetrica recursiva para P.
(ii)⇒ (i). Seja Iso uma funcao isoperimetrica recursiva para P. Seja w ∈ FA. Queremos mostrarque e decidıvel se w ∈ 〈〈R〉〉. Como Area(w) ≤ Iso(|w|), isto equivale a ter a igualdade (12) paraalguns k ≤ Iso(|w|), xi ∈ FA e ri ∈ R∪R−1. Mais uma vez, resulta do Teorema 7.8 que so temos quetestar um numero finito de xi, e o mesmo acontece com os ri. Logo so temos de testar um numerofinito de igualdades do tipo (12) em FA, donde resulta a decidibilidade do problema da palavra. �
Dado um grupo finitamente apresentavel, a existencia de uma funcao isoperimetrica de um de-terminado tipo nao depende da apresentacao finita escolhida, sendo pois um invariante do grupo:Proposicao 7.11 Sejam P = 〈A | R〉 e P ′ = 〈A′ | R′〉 apresentacoes finitas de um grupo G.Se P admite uma funcao isoperimetrica recursiva (respetivamente linear, quadratica, polinomial,exponencial), o mesmo acontece com P ′.
Prova. O caso recursivo segue da Proposicao 7.4 e do Corolario 7.10. Os restantes casos podem serdemonstrados usando argumentos analogos aos desenvolvidos na prova da Proposicao 7.3. �
7.6 Exercıcios
(7.1) (a) Mostre que S3 e gerado pelo subconjunto de permutacoes A = {(123), (12)}.(b) Construa uma apresentacao finita de S3 com dois geradores.
(7.2) Dados m,n ∈ N, construa uma apresentacao finita de Cm × Cn com 3 relatores.
(7.3) Dado n ∈ N, construa uma apresentacao finita de Z× Cn.
(7.4) Mostre que os grafos seguintes sao planares:
(a)•
oooooooooooooo
OOOOOOOOOOOOOO
��������������
//////////////
•
@@@@@@@
UUUUUUUUUUUUUUUUUUUU •
~~~~~~~
iiiiiiiiiiiiiiiiiiii
• •
(b)•
@@@@@@@
OOOOOOOOOOOOOO •
~~~~~~~
@@@@@@@ •
oooooooooooooo
~~~~~~~
• • •
58
(7.5) Para cada uma das apresentcoes dos grupos S3, C3 × C3 e Z × C2 construıdas nos Exercıcios7.1 – 7.3, construa um diagrama de van Kampen com 5 regioes interiores e calcule o respetivobordo.
(7.6) Seja G o grupo definido pela apresentacao P = 〈a, b, c | a2c−1, a2b−2〉.
(a) Mostre que
•
c��@@@@@@@
a // •a
��
b // •b��
•a
��
c
��@@@@@@@
•
c��@@@@@@@
a // •a
��
c // •a//
b��
•a
��• •
b// •
e um diagrama de van Kampen de P.
(b) Determine se bca−1cab−2c−1ac−2ab = 1 em G.
(7.7) Determine se existe algum diagrama de van Kampen da apresentacao 〈a, b | [a, b]〉 com bordoaba−1b−2.
(7.8) Mostre que o grupo cıclico Cn admite uma funcao isoperimetrica linear para todo n ≥ 1.
59
8 Produto livre e generalizacoes
As apresentacoes revelam-se particularmente uteis no estudo de certos operadores, como e o caso doproduto livre e suas generalizacoes, que incluem casos tao importantes como os produtos livres comamalgamacao 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 unicohomomorfismo Φ : H → K tal que o diagrama
G1ι1 //
ϕ1 BBBBBBBB H
����� G2
ι2oo
ϕ2~~||||||||
K
comuta.Lema 8.1 Sejam G1 e G2 grupos. O produto livre de G1 e G2, a existir, e unico a menos deisomorfismo.
Prova. Suponhamos que H e o produto livre de G1 e G2 para os homomorfismos ιi : Gi → H(i = 1, 2), e H ′ e o produto livre de G1 e G2 para os homomorfismos ι′i : Gi → H ′ (i = 1, 2). Entaoexistem homomorfismos Φ : H → H ′ e Ψ : H ′ → H tais que ιiΦ = ι′i e ι′iΨ = ιi (i = 1, 2). Mas entao
G1ι1 //
ι1
AAAAAAAAAAAAAAAA H
1H
ΦΨ
��
G2ι2oo
ι2
~~~~~~~~~~~~~~~~~~
H
e um diagrama comutativo. Pela unicidade do homomorfismo na definicao de produto direto, obtemosΦΨ = 1H . Analogamente, ΨΦ = 1H′ , logo Φ e Ψ sao isomorfismos e H ∼= H ′. �
Para demonstrar a existencia do produto livre, vamos proceder a seguinte construcao. Dado umgrupo 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 = {(agag′ , agg′) | g, g′ ∈ G1} ∪ {(bhbh′ , bhh′) | h, h′ ∈ G2}∪ {(a1, 1), (b1, 1)}.
60
Lema 8.2 Sejam G1 e G2 grupos. Entao RG1,G2 e um sistema de reescrita redutor e confluente.
Prova. E evidente que RG1,G2 e redutor, e a confluencia prova-se analogamente a demonstracao doLema 3.1: so temos que testar a confluencia local para situacoes do tipo
xagag′ag′′y //
��
xagg′ag′′y xaga1y //
��
xagy xa1agy //
��
xagy
xagag′g′′y xag1y xa1gy
e as versoes analogas para G2, o que se confirma facilmente. �
Seja G1 ∗G2 = Irr(RG1,G2). Entao G1 ∗G2 consiste na palavra vazia e em todas as palavras quealternam letras da forma ag (g ∈ G1) com letras da forma bh (h ∈ G2).
Definimos uma operacao binaria ◦ em G1 ∗G2 do seguinte modo: Dados u, v ∈ G1 ∗G2, u ◦ v e aforma reduzida da palavra uv em RG1,G2 . A confluencia garante que esta operacao e associativa, ea palavra vazia e o elemento neutro. E facil verificar a existencia de inversos: por exemplo,
(ag1bh1 . . . agnbhn) ◦ (bh−1nag−1
n. . . bh−1
1ag−1
1) = 1
e todos os outros casos sao analogos. Logo (G1 ∗ G2, ◦) e um grupo. Note-se que existe um homo-morfismo injetivo ι1 : G1 → G1 ∗G2 definido por
gι1 ={ag se g 6= 11 se g = 1
Analogamente definimos ι2 : G2 → G1 ∗G2.Teorema 8.3 Sejam G1 e G2 grupos. Entao G1 ∗ G2 e o produto livre de G1 e G2 relativamenteaos homomorfismos ιi : Gi → G1 ∗G2 (i = 1, 2).
Prova. Seja A = AG1,G2 eR = RG1,G2 . SejaK um grupo e seja ϕi : Gi → K um homomorfismo parai = 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 ∈ G1, 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 verificarque 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 estarunivocamente determinado. �
Habitualmente, simplificamos a representacao dos elementos de G1 ∗G2 escrevendo g1h1 . . . gnhnem vez de ag1bh1 . . . agnbhn e assim sucessivamente. E a representacao do produto livre em formanormal.
Podemos afirmar que o produto livre G1 ∗G2 e o maior grupo, gerado por G1∪G2, pois qualqueroutro grupo K nestas condicos sera necessariamente imagem homomorfa de G1 ∗G2.
Vamos ver em seguida como o produto livre se traduz em termos de apresentacoes:
61
Teorema 8.4 Seja 〈Ai | Ri〉 uma apresentacao do grupo Gi para i = 1, 2, com A1 ∩A2 = ∅. Entao〈A1 ∪A2 | R1 ∪R2〉 e uma apresentacao de G1 ∗G2.
Prova. Sem perda de generalidade, podemos assumir que Gi = FAi/〈〈Ri〉〉. Sejam A = A1 ∪ A2 eR = R1∪R2. Seja H = FA/〈〈R〉〉. Pelo Teorema 1.5, podemos definir um homomorfismo ιi : Gi → Hpara i = 1, 2 por (g〈〈Ri〉〉)ιi = g〈〈R〉〉.
Dado um grupo K e homomorfismos ϕi : Gi → K (i = 1, 2), consideremos os homomorfismoscanonicos πi : FAi → Gi. E facil construir um homomorfismo ϕ : FA → K tal que ϕ|FAi
= πiϕi parai = 1, 2. Ora Ri ⊆ Ker(πi) ⊆ Ker(ϕ) para i = 1, 2 implica R ⊆ Ker(ϕ), logo pelo Teorema 1.5 existeum homomorfismo Φ : H → K tal que (g〈〈R〉〉)Φ = gϕ.
Para todo g ∈ FAi , temos
(g〈〈Ri〉〉)ιiΦ = (g〈〈R〉〉)Φ = gϕ = gπiϕi = (g〈〈Ri〉〉)ϕi,
logo ιiΦ = ϕi para i = 1, 2. A unicidade de Φ resulta do fato de im(ι1) ∪ im(ι2) gerar H. Logo H eo produto livre de G1 e G2 e portanto 〈A1 ∪A2 | R1 ∪R2〉 e uma apresentacao de G1 ∗G2. �
8.2 Generalizacoes
Os produtos livres com amalgamacao constituem uma das generalizacoes mais importantes do pro-duto livre pelo seu significado geometrico. Suponhamos que G1 e G2 sao grupos com subgruposH1, H2 (respetivamente), e existe um isomorfismo ϕ : H1 → H2. Seja
N = 〈〈(hϕ)h−1 : h ∈ H1〉〉EG1 ∗G2.
O grupo quociente (G1 ∗G2)/N diz-se o produto livre com amalgamacao de G1 e G2 (relativamenteao isomorfismo ϕ). O produto livre corresponde ao caso particular H1 = H2 = {1}.
O produto livre com amalgamacao aparece por exemplo no famoso Teorema de van Kampen. Emtopologia algebrica, o chamado grupo fundamental e o mais importante dos invariantes topologicosassociados a um espaco topologico (isto e, espacos topologicos homeomorfos tem grupos fundamentaisisomorfos). Ora no estudo das variedades, as tecnicas ditas de cirurgia sao muito importantes poiselas permitem decompor/construir variedades mais complexas a partir de variedades mais simples.O Teorema de van Kampen (1933) explica que, nas condicoes apropriadas, o grupo fundamental dauniao de duas variedades e um produto livre com amalgamacao dos grupos fundamentais das duavariedades mais simples.
Esta e mais um resultado brilhante do belga Egbert van Kampen. Infelizmente ele morreu comapenas 33 anos!
Outra generalizacao e o chamado produto de grafo. Suponhamos que G1, . . . , Gn sao 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 existeuma aresta i −− j em Γ.
Note-se que o produto livre e na realidade uma operacao associativa (ver o Exercıcio 8.2), o quepermite falar do produto livre G1 ∗G2 ∗ . . . ∗Gn. Formalmente, o Γ-produto de G1, . . . , Gn e o grupoquociente
Γ(G1, . . . , Gn) = (G1 ∗G2 ∗ . . . ∗Gn)/N,
ondeN = 〈〈[gi, gj ] : gi ∈ Gi, gj ∈ Gj , (i −− j) ∈ E〉〉EG1 ∗ . . . ∗Gn.
62
Se E = ∅, entao Γ(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 facil ver queΓ(G1, G2, G3, G4) ∼= (G1 ∗G4)× (G2 ∗G3).
Os produtos de grafos permitem assim introduzir elementos de comutatividade parcial num op-erador tao ferozmente anti-comutativo como o produto livre. Estas ideias de comutatividade parcialsao muito importantes tambem na teoria da computacao, onde sao usadas na construcao de modelospara a computacao em paralelo.
8.3 Grupos de grafo
Os grupos de grafo sao 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 apresentacao
〈a1, . . . , an | [ai, aj ] ((i −− j) ∈ E)〉. (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, tambem chamados de grupos de Artin ortogonais, partilham com os gruposlivres muitas das suas boas propriedades. Por exemplo:Teorema 8.5 Todo grupo de grafo tem problema da palavra decidıvel.
Prova. Seja Γ = (V,E) um grafo com V = {1, . . . , n} e seja G o grupo definido pela apresentacao(13). Seja A = {a1, . . . , an}. Definimos um sistema de reescrita em A por
R = {(aa−1, 1) | a ∈ A} ∪ {(aδiaεj , aεjaδi ) | 1 ≤ i < j ≤ n; (i −− j) ∈ E; δ, ε ∈ {−1, 1}}.
Para mostrar que R e um sistema de reescrita noetheriano, definimos uma funcao ζ : A∗ → N doseguinte modo: se w = aε1i1 . . . a
εkik
com i1, . . . ik ∈ {1, . . . , n} e ε1, . . . , εk ∈ {−1, 1}, seja
wζ =k∑j=1
jij .
E facil verificar que u−→Rv implica uζ > vζ, logo R e noetheriano.Note-se que o fato de R ser finito e noetheriano implica que o numero de descendentes de uma
dada palavra w e necessariamente finito: se representassemos todos os descendentes de w atraves deuma arvore (genealogica), o fato de cada palavra ter apenas um numero finito de descendentes diretos(porque R e finito) garante que se a arvore fosse infinita haveria algum ramo infinito... contradizendonoetheriano.
63
Para mostrar que R e confluente, adaptamos a prova do Lema 3.1. Uma vez mais, comecamospor provar a confluencia local para diagramas do tipo
u //
��
x1s1y1
x2s2y2
onde u = x1r1y1 = x2r2y2 com xi, yi ∈ A∗ e (r1, s1), (r2, s2) ∈R.Se as ocorrencias de r1 e r2 forem disjuntas, podemos reproduzir a reducao de tipo alternativo
em cada uma das palavras x1s1y1 e x2r2y2. So temos pois que nos preocupar com o caso em que asocorrencias se sobrepoem. Isto conduz-nos a quatro casos distintos:
va−δi aδia−δi w //
��
v1a−δi w va−δi aδiaεjw
//
��
vaεjw
va−δi 1w va−δi aεjaδiw
vaδiaεja−εj w //
��
vaδiw vaδiaεjaγkw
//
��
vaεjaδiaγkw
vaεjaδia−εj w vaδia
γka
εjw
E facil verificar que em cada um dos quatro casos podemos conseguir a confluencia para as palavras
va−δi w, vaεjw, vaδiw, vaγkaεjaδiw
respetivamente, gastando no pior dos casos 2 reducoes elementares. Logo temos confluencia local.Podemos agora construir a grelha de confluencia tal como na prova do Lema 3.1. E certo que
aqui, ao completar cada quadrado, corremos o risco de aumentar o numero de reducoes elementares...no entanto, como o sistema e noetheriano, o numero total de descendentes de uma mesma palavra efinito e isto garante que a construcao da grelha acaba por terminar!
Logo R e noetheriano e confluente, e pela Proposicao 2.10, para cada w ∈ A∗, existe uma unicapalavra wξ ∈ Irr(R) tal que w−→Rwξ (forma normal). Vamos mostrar que
w = 1 em G se e so se wξ = 1. (14)
Suponhamos que w = 1 em G. Como G e definido pela apresentacao (13), podemos escrever
w = (x1[ai1 , aj1 ]x−11 ) . . . (xn[ain , ajn ]x−1
n )
para alguns xs ∈ A∗ e (is −− js) ∈ E. Como
((x1[ai1 , aj1 ]x−11 ) . . . (xn[ain , ajn ]x−1
n ))ξ = 1,
resulta da unicidade da forma normal que
wξ = ((x1[ai1 , aj1 ]x−11 ) . . . (xn[ain , ajn ]x−1
n ))ξ = 1.
64
A implicacao recıproca resulta do fato da igualdade w = wξ ser valida em G, que e uma con-sequencia de termos rξ = sξ para todo (r, s) ∈R.
Logo (14) e valida. Como wξ e efetivamente calculavel a partir de w, G tem problema da palavradecidıvel. �
Mas seria prematuro pensar que todas as boas propriedades dos grupos livres sao herdadas pelosgrupos 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 constroi um certo H ≤f.g. F2 × F2 tal que e indecidıvel , para g ∈ F2 × F2
arbitrario, se g ∈ H ou nao.
8.4 Exercıcios
(8.1) Sejam G e H grupos nao triviais. Mostre que:
(a) os elementos de ordem finita de G ∗H sao os conjugados dos elementos de ordem finitade 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 nao triviais e seja K o conjunto dos elementos de G ∗H da forma
g1h1 . . . gnhn (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 g1h1 . . . gnhn ∈ K sao da forma gihi . . . gnhng1h1 . . . gi−1hi−1;
(c) se G e H tem problema da conjugacao 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 unicogrupo H com a seguinte propriedade: existem homomorfismos πi : H → Gi (i = 1, 2) tais que:para todo grupo K e homomorfismos ϕ1 : K → Gi (i = 1, 2), existe um unico homomorfismoΦ : K → H tal que o diagrama
G1 Hπ1oo π2 // G2
K
ϕ1
``BBBBBBBB ϕ2
>>||||||||Φ
OO���
comuta.
65
(8.5) Exprima (Z× Z) ∗ (Z× Z) como um grupo de grafo.
(8.6) Mostre que todo grupo de grafo e livre de torsao.
[Sugestao: dentro de cada classe de conjugacao, trabalhe com o elemento da forma maisconveniente.]
66
9 Grupos hiperbolicos
Os grupos hiperbolicos constituem certamente um dos temas mais belos da moderna teoria de grupos,e devem-se a uma ideia revolucionaria de Gromov nos anos 80: usar a geometria local do grafo deCayley para resolver problemas algorıtmicos.
9.1 Grafos hiperbolicos
Seja Γ = (V,E) um grafo conexo. Podemos definir uma metrica d em V do seguinte modo: dadosp, q ∈ V , d(p, q) e o comprimento mınimo de um caminho ligando p a q em Γ. Um tal caminho diz-seuma geodesica de Γ.
Note-se que d esta bem definida porque o grafo e conexo, e satisfaz efetivamente os axiomas (M1)– (M4). Diz-se a metrica geodesica de Γ.
Dado p ∈ V e W ⊆ V nao vazio, escrevemos
d(p,W ) = min {d(p, q) | q ∈W}.
Se X ⊆ V ∪ E, escrevemos d(p,X) = d(p,X ∩ V ).Um triangulo geodesico em Γ e um conjunto de 3 geodesicas
X : p −− q, Y : q −− r, Z : r −− p
formando um triangulop
??????? q
r
�������
Designamos um tal triangulo geodesico por ∆[XY Z]. Note-se que o triangulo pode ser degenerado,uma vez que um caminho trivial e tambem uma geodesica.
Dada uma constante δ ≥ 0, dizemos que Γ e δ-hiperbolico se, para todo o triangulo geodesico∆[XY Z] em Γ e todo vertice x em X, se tem
d(x, Y ∪ Z) ≤ δ.
Dizemos que Γ e hiperbolico se for δ-hiperbolico para algum δ ≥ 0. A designacao e inspirada pelanatureza dos triangulos no espaco hiperbolico, que tem curvatura negativa:
Discutimos em seguida a condicao em alguns casos simples. Dado um grafo conexo Γ = (V,E),o seu diametro e definido por
diam(Γ) = sup{d(p, q) | p, q ∈ V }.
67
Lema 9.1 (i) Se Γ e um grafo conexo finito, entao Γ e δ-hiperbolico para δ = diam(Γ).
(ii) Se Γ e uma arvore, entao Γ e 0-hiperbolico.
(iii) Se Γ e o grafo descrito por
......
...
. . . • • • . . .
. . . • • • . . .
. . . • • • . . .
......
...
entao Γ nao e hiperbolico.
Prova. (i) Imediato.(ii) Se ∆[XY Z] e um triangulo geodesico numa arvore Γ, entao os vertices de X ocorrem todos
em Y ∪ Z.(iii) Vamos identificar os vertices de Gamma com Z × Z da forma obvia. Para cada n ≥ 1,
definimos as geodesicas
Xn : (0, 0) −− (0, n), Yn : (0, n) −− (n, n) −− (n, 0), Zn : (n, 0) −− (0, 0)
e consideramos o triangulo geodesico ∆[YnZnXn]. Temos que (n, n) ocorre em Yn e d((n, n), Zn ∪Xn) = n. Como n pode ser arbitrariamente grande, concluimos que Γ nao e hiperbolico. �
Vamos agora introduzir o importante conceito de quasi-isometria. Dois espacos metricos (X, d)e (X ′, d′) dizem-se isometricos se existir uma bijecao ϕ : X → X ′ tal que
d′(xϕ, yϕ) = d(x, y) para todos x, y ∈ X.
Se aplicarmos este conceito ao espaco dos vertices de um grafo conexo, com a distancia geodesica,verificamos facilmente que a isometria corresponde precisamente ao isomorfismo de grafos: se ϕ :V → V ′ e uma bijecao que preserva a distancia geodesica, entao preserva a relacao de adjacencia elogo os grafos sao isomorfos, e vice-versa.
Por isso e muito mais interessante enfraquecer um pouco as exigencias. Dois espacos metricos(X, d) e (X ′, d′) dizem-se quase-isometricos se existirem funcoes ϕ : X → X ′ e ψ : X ′ → X econstantes λ,C ≥ 0 tais que, para todos x, y ∈ X e x′, y′ ∈ X ′. as condicoes seguintes sao verificadas:
(Q1) d′(xϕ, yϕ) ≤ λd(x, y) + C;
(Q2) d(x′ψ, y′ψ) ≤ λd′(x′, y′) + C;
68
(Q3) d(xϕψ, x) ≤ C;
(Q4) d′(x′ψϕ, x′) ≤ C.
Dizemos que dois grafos sao quase-isometricos se os respetivos conjuntos de vertices, munidos dadistancia geodesica, constituem espacos metricos isometricos.
Podemos provar o seguinte resultado:Lema 9.2 (i) Todos os grafos conexos de diametro finito sao quase-isometricos.
(ii) Nenhum grafo conexo de diametro finito e quase-isometrico a um grafo conexo de diametroinfinito.
Prova. (i) Tomamos C igual ao maximo dos diametros dos dois grafos, e λ, ϕ, ψ arbitrarios.(ii) Sejam Γ = (V,E), Γ′ = (V ′, E′) e ϕ : V → V ′, ψ : V ′ → V funcoes satisfazendo os axiomas
(Q1) – (Q4) para as metricas geodesicas. Suponhamos que Γ tem diametro finito M . Para todosx′, y′ ∈ V ′, temos
d′(x′, y′)≤ d′(x′, x′ψϕ) + d′(x′ψϕ, y′ψϕ) + d′(y′ψϕ, y′) ≤ C + λd(x′ψ, y′ψ) + C + C≤ 3C + λM,
logo Γ′ tem diametro finito ≤ 3C + λM . �
O teorema seguinte mostra a robustez do conceito de grafo hiperbolico:Teorema 9.3 Sejam Γ e Γ′ grafos conexos quase-isometricos. Entao Γ e hiperbolico se e so se Γ′ ehiperbolico.
A demonstracao usa argumentos geometricos complexos envolvendo o conceito de quase-geodesica,que nao vamos introduzir neste curso. Atencao que as constantes de hiperbolicidade de Γ e Γ′ podemser muito diferentes!
9.2 Grafos de Cayley hiperbolicos
Suponhamos agora que G e um grupo gerado por um subconjunto finito A. O grafo de Cayley ΓA(G)nao e um grafo no sentido formal da palavra, e na realidade um A-grafo (conexo), mas as ideias e osresultados apresentados na subseccao anterior podem ser aplicadas tambem neste contexto.
Como G e o conjunto dos vertices de ΓA(G), podemos em particular definir uma metrica dA emG, tal que dA(g, h) e o comprimento da mais curta palavra u ∈ A∗ tal que h = gu em G. DizemosquedA e a metrica geodesica de G (relativamente ao conjunto A de geradores).
E facil verificar que
dA(xg, xh) = dA(g, h) para todos g, h, x ∈ G. (15)
Note-se tambem que, sendo ΓA(G) involutivo (a cada aresta ga−→ga corresponde uma aresta
gaa−1
−→g), a orientacao das arestas e irrelevante no calculo da distancia, o que elimina qualquerduvida sobre a sua simetria... Temos igualmente o conceito de triangulo geodesico e a definicao dehiperbolicidade e a mesma. Mas a hiperbolicidade do grafo de Cayley podera depender do conjuntofinito de geradores escolhido? O resultado seguinte mostra que nao:
69
Teorema 9.4 Sejam A e B conjuntos finitos de geradores de um mesmo grupo G. Entao os grafosde Cayley ΓA(G) e ΓB(G) sao quase-isometricos.
Prova. Ambos os grafos tem G como conjunto dos vertices, 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) sao satisfeitos. Sejam g, h ∈ G. Se dA(g, h) = n, entao existem a1, . . . , an ∈ Atais que ga1 . . . an = h. Em virtude de (15), temos dB(ai, 1) = dB(a−1
i , 1) e tambem
dB(ga1 . . . ai−1, ga1 . . . ai) = dB(1, ai) ≤ λ,
logo
dB(g, h) ≤n∑i=1
dB(ga1 . . . ai−1, ga1 . . . ai) ≤ λn = λdA(g, h)
e (Q1) e valido. Por simetria, obtemos tambem (Q2), logo os dois grafos de Cayley sao isometricos.�
Em consequencia, podemos dizer que um grupo finitamente gerado e hiperbolico se ΓA(G) forhiperbolico 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.Entao G e hiperbolico se e so se H e hiperbolico.
Prova. Suponhamos que [G : H] = m+ 1. Podemos escrever G como uma uniao disjunta
G = Hb0 ∪Hb1 ∪ . . . ∪Hbm
para alguns b0, . . . , bm ∈ G. Podemos assumir tambem 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} unicos tais quebiaj = wijb(i,j)α. Seja
W = {wij | i = 0, . . . ,m; j = 1, . . . , n}.
Seja h ∈ H. Como h ∈ G = 〈A〉, existem i1, . . . , ik ∈ {1, . . . , n} tais que h = ai1 . . . aik . Sejar0 = 0.Para j = 1, . . . , k, seja rj = (rj−1, ij)α. Daqui resulta que
h= b0h = br0ai1 . . . aik = wr0i1br1ai2 . . . aik=wr0i1wr1i2br2ai3 . . . aik = . . .=wr0i1 . . . wrk−1ikbrk .
Como h ∈ H, obtemos rk = 0, logo h ∈ 〈W 〉 e portanto W e um conjunto finito de geradores de H.Alem disso,
dW (h, 1) ≤ dA(h, 1). (16)
Seja B = W ∪ {b1, . . . , bm}. Entao B e tambem um conjunto finito de geradores de G, e resultada demonstracao do Teorema 9.4 que
dA(h, h′) ≤ λdB(h, h′) para todos h, h′ ∈ H, (17)
70
ondeλ = max ({dA(b, 1) | b ∈ B} ∪ {dB(a, 1) | a ∈ A}).
Podemos assumir que G e nao trivial, logo λ ≥ 1. Seja ϕ : H → G a inclusao e seja ψ : G → Hdefinida por (hbi)ψ = h. Vamos mostrar que ΓA(G) e ΓW (H) sao quase-isometricos verificando queos axiomas (Q1) – (Q4) sao satisfeitos para C = 2λ.
Sejam h, h′ ∈ H e i, j ∈ {0, . . . ,m}. Entao (17) e W ⊆ B implicam
dA(hϕ, h′ϕ) = dA(h, h′) ≤ λdB(h, h′) ≤ λdW (h, h′) ≤ λdW (h, h′) + C.
Por outro lado, dW (hϕψ, h) = dW (h, h) = 0 ≤ C, logo (Q1) e (Q3) sao validos.Temos tambem, gracas a (16) e (15),
dW ((hbi)ψ, (h′bj)ψ) = dW (h, h′) ≤ dA(h, h′) ≤ dA(h, hbi) + dA(hbi, h′bj) + dA(h′bj , h′)= dA(1, bi) + dA(hbi, h′bj) + dA(bj , 1) ≤ λdA(hbi, h′bj) + C,
edA((hbi)ψϕ, hbi) = dA(h, hbi) = dA(1, bi) ≤ λ < C,
logo (Q2) e (Q4) sao validos.Concluimos assim que ΓA(G) e ΓW (H) sao quase-isometricos e aplicamos o Teorema 9.3. �
Podemos clarificar agora a questao da hiperbolicidade para varias classes de grupos. Um grupodiz-se virtualmente livre se tiver um subgrupo livre de ındice finito. Por exemplo, Fn ×G e virtual-mente livre para todo n ≥ 1 e todo grupo finito G.Teorema 9.6 (i) Os grupos finitos sao hiperbolicos.
(ii) Os grupos livres de dimensao finita sao hiperbolicos.
(iii) Os grupos virtualmente livres finitamente gerados sao hiperbolicos.
(iv) O grupo abeliano livre Z× Z nao e hiperbolico.
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 hiperbolicos e a dos grupos fundamentais de variedadesriemannianas compactas com curvatura negativa. Foi esta classe de grupos que motivou Gromov acriar o conceito de grupo hiperbolico.
9.3 Propriedades
Num dos resultados mais extraordinarios da teoria dos grupos hiperbolicos, geometria e complexidadese encontram de forma inesperada:Teorema 9.7 (Gromov 1987) Seja G um grupo finitamente apresentavel. Entao as condicoes seguin-tes sao equivalentes:
(i) G e hiperbolico;
71
(ii) G admite uma funcao isoperimetrica linear;
(iii) G admite uma funcao isoperimetrica subquadratica.
Aqui subquadratica significa “melhor que quadratica”! Pelo Corolario 7.10, concluimos que todogrupo hiperbolico finitamente apresentavel tem problema da palavra decidıvel. Veremos na Seccao10 que todo grupo hiperbolico e automatico e logo finitamente apresentavel, bem como uma solucaomais construtiva do problema da palavra.
Seja G um grupo hiperbolico gerado pelo conjunto finito A. Isto equivale a considerar umhomomorfismo involutivo sobrejetivo ϕ : A∗ → G. Designamos por GeoA(G) o conjunto dos rotulosde geodesicas em ΓA(G). Note-se que, como ΓA(G) e transitivo nos vertices, todas estas palavrassao rotulo de geodesicas iniciando em qualquer vertice. E habitual chamar tambem de geodesicas aspalavras de GeoA(G).
Dados L ⊆ A∗ e ε > 0, dizemos que L e ε-lipschitziana (relativamente a ΓA(G)) se, para todasu, v ∈ L,
dA(uϕ, vϕ) ≤ 1 implica dA(u[n]ϕ, v[n]ϕ) ≤ ε para todo n ∈ N.
Esta propriedade e tambem conhecida como a propriedade dos dois viajantes: imaginemos doisviajantes que, partindo do mesmo sıtio, vao percorrer dois caminhos em ΓA(G) com rotulos u e v,respetivamente. O ritmo e uma aresta por dia! Se eles terminarem seus caminhos a distancia ≤ 1,entao em cada dia da viagem eles nunca estarao a distancia > ε.
Dizemos que L e lipschitziana se for ε-lipschitziana para algum ε > 0.Teorema 9.8 Seja G um grupo hiperbolico e seja ϕ : A∗ → G um homomorfismo involutivo sobreje-tivo com A finito. Suponhamos que ΓA(G) e δ-hiperbolico. Entao GeoA(G) e (2δ + 2)-lipschitziana.
Prova. Consideremos um triangulo geodesico
p
w
��q0 v
//
u
55kkkkkkkkkkkkkkkkkk q
com |w| ≤ 1 em ΓA(G). Temos que mostrar que dA(u[n]ϕ, v[n]ϕ) ≤ 2δ + 2 para todo n ∈ N.Consideremos as geodesicas no diagrama fatorizadas na forma
q0u[n]
−−→pnun−→p, q0
v[n]
−−→qnvn−→q.
Suponhamos que vn = 1. Como |u| ≤ |v| + 1 (caso contrario q0v−→qw
−1
−→p seria uma alternativamais curta a q0
u−→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 analogo, logo podemos assumir que un, vn 6= 1. Como ΓA(G) e δ-hiperbolico,existe algum m ≤ |u| tal que dA(v[n]π, u[m]) ≤ δ+1. Logo existe um caminho qn
z−→pm com |z| ≤ δ+1.Suponhamos que m > n+ δ + 1. Entao
q0v[n]
−−→qnz−→pm
72
e uma alternativa mais curta a geodesica q0u[m]
−−→pm pois
|v[n]|+ |z| ≤ n+ δ + 1 < m = |u[m]|.
Por outro lado, se m < n− δ − 1, entao
q0u[m]
−−→pmz−1
−−→qn
e uma alternativa mais curta a geodesica q0v[n]
−−→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. �
O resultado seguinte mostra que o conjunto das geodesicas dum grupo hiperbolico tem umaestrutura simples:Teorema 9.9 Seja G um grupo hiperbolico e seja ϕ : A∗ → G um homomorfismo involutivo sobre-jetivo com A finito. Entao GeoA(G) e uma linguagem racional.
Prova. Suponhamos que ΓA(G) e δ-hiperbolico e seja ε = 2δ + 2. Consideremos a bola abertaB = Bε(1) no espaco metrico (G, dA). Como A e finito, B e finita. Alem disso, 1 ∈ B. Definimosum A-automato finito A = (Q, {1}, Q,E) por:
Q = {X ⊆ B | 1 ∈ X};
E = {(X, a, ((a−1ϕ)X(Aϕ ∪ {1})) ∩B) | X ∈ Q, a ∈ A \ (Xϕ−1)}.
Note-se que 1 ∈ X implica 1 ∈ (a−1ϕ)X(Aϕ ∪ {1}), logo E ⊆ Q × A × Q e A esta bem definido.Alem disso, A e determinıstico. Vamos mostrar que L(A) = GeoA(G).
Comecamos por mostrar que
se {1} u−→X e um caminho em A, entao X ⊆ (u−1ϕ)(Aϕ ∪ {1})|u|. (18)
Usamos inducao sobre |u|. O caso u = 1 e trivial. Suponhamos que (18) e valido para u e que{1} u−→X a−→X ′ e um caminho em A com a ∈ A. Entao
X ′ ⊆ (a−1ϕ)X(Aϕ ∪ {1}) ⊆ (a−1ϕ)(u−1ϕ)(Aϕ ∪ {1})|u|(Aϕ ∪ {1}) = (ua)−1ϕ(Aϕ ∪ {1})|ua|
e por inducao (18) e valido para todo u.Seja u ∈ GeoA(G). Vamos mostrar que u ∈ L(A) por inducao sobre |u|. O caso |u| = 0 e trivial,
logo assumimos que |u| > 0 e que a implicacao e valida para palavras mais curtas. Seja u = va coma ∈ A. Como v ∈ GeoA(G), existe um caminho {1} v−→X em A pela hipotese de inducao. Temosque mostrar que existe uma aresta da forma X a−→X ′ em A, e para isso basta que aϕ /∈ X.
Suponhamos que aϕ ∈ X. Por (18), temos
X ⊆ (v−1ϕ)(Aϕ ∪ {1})|v|,
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).
73
Suponhamos que GeoA(G) ⊂ L(A). Seja u ∈ L(A) \ GeoA(G) de comprimento mınimo. Como1 ∈ GeoA(G), podemos escrever u = va para alguma a ∈ A. Logo v ∈ GeoA(G) por minimalidadede u. Como u /∈ GeoA(G), existe algum caminho 1 w−→uϕ em ΓA(G) com |w| < |u|. Logo
vϕ
a
��1 w
//
v
55kkkkkkkkkkkkkkkkkkk uϕ
e um triangulo geodesico em ΓA(G). Note-se que |w| = |v| ou |w| = |v| − 1 pois qualquer outrahipotese contradiz |w| < |u| ou v ∈ GeoA(G).
Como v ∈ GeoA(G) ⊆ L(A), existe em A um caminho {1} v[i]−−→Xi para i = 0, . . . , |v|. Vamosusar inducao sobre i para mostrar que
((v[i])−1w[i])ϕ ∈ Xi (19)
para i = 0, . . . , |v|. O caso i = 0 e trivial, logo assumimos que 0 < i ≤ |v| e que (19) e valido parai − 1. Seja v[i] = v[i−1]c. Como (Xi−1, c,Xi) ∈ E, temos Xi = ((c−1ϕ)Xi−1(Aϕ ∪ {1})) ∩ B, logo((v[i−1])−1w[i−1])ϕ ∈ Xi−1 implica
((v[i])−1w[i])ϕ ∈ (c−1(v[i−1])−1w[i−1])ϕ(Aϕ ∪ {1}) ⊆ (c−1ϕ)Xi−1(Aϕ ∪ {1}).
Por outro lado,dA(((v[i])−1w[i])ϕ, 1) = dA(w[i]ϕ, v[i]ϕ) ≤ ε
pois GeoA(G) e ε-lipschitziana pelo Teorema 9.8. Logo ((v[i])−1w[i])ϕ ∈ B e portanto
((v[i])−1w[i])ϕ ∈ ((b−1ϕ)Xi−1(Aϕ ∪ {1})) ∩B = Xi,
provando (19).Em particular, para i = |v|, obtemos (v−1w)ϕ ∈ X|v|. Como u = va e uϕ = wϕ, obtemos
aϕ = (v−1w)ϕ ∈ X|v|, pelo que nao existe nenhuma aresta da forma X|v|a−→ . . . em A. Como
{1} v−→X|v| e um caminho emA eA 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 canonico a para os grupos cıclicos C2 e C3, com grafos de Cayley
•a
��@@@@@@@
•a
** •a
jj •
a??~~~~~~~
•a
oo
obtemosGeoa(C2) = {1, a, a−1} = Geoa(C3).
74
9.4 Exercıcios
(9.1) Mostre que o grafo. . . • • • • . . .
. . . • • • • . . .
. . . • • • • . . .
e 2-hiperbolico.
(9.2) Considere o grafo do exercıcio (9.1) e os grafos
. . . • • • • . . .
e...
......
...
. . . • • • • . . .
. . . • • • • . . .
. . . • • • • . . .
......
......
Quais destes grafos sao quase-isometricos?
(9.3) Sejam H um grupo hiperbolico e F um grupo finito. Mostre que H × F e hiperbolico.
(9.4) Sejam A = {a, b} e D4 o grupo diedral infinito definido pela apresentacao 〈A | a4, b2, bab−1a〉.
(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 apresentacao〈A | bab−1a〉.
(a) Construa o grafo de Cayley ΓA(G).
(b) Mostre que G nao e hiperbolico.
(9.6) Mostre que o grupo C2 ∗ C2 e virtualmente livre.
[Sugestao: Considere o subgrupo cıclico gerado pelo produto ab, onde a (respetivamente b)gera o primeiro (respetivamente segundo) C2.]
75
(9.7) Mostre que Iso(n) = n2 define uma funcao isoperimetrica para a apresentacao 〈a, b | a2, b2〉 de
C2 ∗ C2.
(9.8) Seja A = {a, b} o conjunto canonico de geradores de G = Z×Z e considere a linguagem racional
L =⋃
δ,ε=±1
(aδbε)∗((aδ)∗ ∪ (bε)∗).
Mostre que:
(a) L ⊆ GeoA(G);
(b) dado g ∈ G, existe um e um so caminho em ΓA(G) da forma 1 u−→g (u ∈ L);
(c) L e 2-lipschitziana (relativamente a ΓA(G)).
76
10 Grupos automaticos
Os grupos automaticos foram oficialmente introduzidos por Cannon, Epstein, Holt, Levy, Patersone Thurston num livro publicado em 1992! Esta teoria procura descrever a estrutura de um grupoutilizando automatos finitos, e admite tambem uma abordagem geometrica que generaliza num certosentido a teoria dos grupos hiperbolicos.
10.1 Estruturas automaticas
Seja A um alfabeto finito e seja ϕ : A∗ → G um homomorfismo sobrejetivo. Isto equivale a dizer queA pode ser visto como um conjunto que gera G enquanto monoide. Uma linguagem L ⊆ A∗ diz-seuma seccao de ϕ se Lϕ = G. Se ϕ|L : L→ G e bijetiva, L diz-se uma transversal de ϕ.
Naturalmente, uma seccao nao determina a estrutura do grupo. Mas podemos complementaressa informacao do modo que passamos a descrever.
Dada w ∈ A∗, estamos interessados em exprimir a relacao
{(u, v) ∈ L× L | vϕ = (uw)ϕ}
sob a forma de uma linguagem. Como proceder? Uma forma simples de o conseguir e usando aconvolucao.
Seja $ um sımbolo que assumimos nao pertencer a A. Definimos o alfabeto
A$ = (A×A) ∪ (A× {$}) ∪ ({$} ×A).
Dadas u, v ∈ A∗, a convolucao u � v e a (unica) palavra de A∗$ cuja projecao na primeira (respetiva-mente 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 sao alinhadas a esquerda para produzir uma palavra de A∗$ eo sımbolo $ e usado para compensar a possıvel diferenca de comprimento entre u e v.
Para todo w ∈ A∗, definimos entao
Lw = {u � v | u, v ∈ L, vϕ = (uw)ϕ} ⊆ A∗$.
Dizemos que L ⊆ A∗ e uma estrutura automatica para ϕ : A∗ → G se:
(E1) L e uma seccao racional de ϕ;
(E2) La e racional para todo a ∈ A ∪ {1}.
Se substituirmos (E1) pela condicao mais forte
(E1’) L e uma transversal racional de ϕ,
dizemos que L e uma estrutura automatica com unicidade para ϕ.Logo uma estrutura automatica envolve uma colecao (finita) de |A| + 2 automatos finitos. Se
a estrutura tiver unicidade, podemos prescindir do automato reconhecendo L1, pois este automatopode ser facilmente obtido a partir do automato reconhecendo L substituindo cada rotulo a ∈ A por(a, a).
77
Vamos ver em seguida que a existencia de uma estrutura automatica implica a existencia deuma estrutura automatica com unicidade. Mas antes precisamos de introduzir a chamada ordemlexicografica:
Seja A um alfabeto finito que supomos totalmente ordenado por <. Definimos uma relacao <lem A∗ do seguinte modo: dados u, v ∈ A∗,
u <l v se
|u| < |v|
ou
|u| = |v| e u = wau′, v = wbv′ com a, b ∈ A e a < b
E facil verificar que esta relacao e transitiva e tricotomica (isto e, dados u, v ∈ A∗, ocorre precisamenteum dos casos u = v, u <l v ou v <l u). Logo <l e uma ordem total. Como qualquer subconjuntonao 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}.
Entao 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 tambem provar o seguinte lema:Lema 10.2 Sejam K,L A-linguagens racionais. Entao
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 se a ∈ A1 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π−11 ∩ Lπ
−12 ∩ (A∗ �A∗),
resulta das Proposicoes 2.5 e 2.9(ii) que K � L e racional. �
78
Podemos agora provar o resultado anunciado:Proposicao 10.3 Sejam A um alfabeto finito, G um grupo e ϕ : A∗ → G um homomorfismosobrejetivo. Se existir uma estrutura automatica para ϕ, entao existe uma estrutura automatica comunicidade para ϕ.
Prova. Seja L uma estrutura automatica para ϕ. Para cada g ∈ G, seja wg o mınimo de L ∩ gϕ−1
para a ordem lexicografica. Definimos
W = {wg | g ∈ G}.
Vamos mostrar que W e uma estrutura automatica com unicidade para ϕ.Seja π2 : A∗$ → A∗ o homomorfismo definido na prova do Lema 10.2. Entao (L1 ∩ Ol)π2 e o
conjunto de todas as palavras v ∈ L que admitem uma representacao alternativa u <l v, logo
W = L \ (L1 ∩Ol)π2.
Como L e uma estrutura automatica para ϕ, resulta das Proposicoes 2.5 e 2.9(i) e do Lema 10.1 que(L1 ∩Ol)π2 e uma A-linguagem racional. Mas entao
W = L ∩ (A∗ \ (L1 ∩Ol)π2),
e resulta da Proposicao 2.5 que W e racional.Resulta da construcao 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 automatica com unicidade para ϕ. �
Tal como em casos anteriores, e possıvel mostrar que a existencia de uma estrutura automaticanao depende do conjunto de geradores:Teorema 10.4 Seja G um grupo admitindo uma estrutura automatica para o homomorfismo so-brejetivo ϕ : A∗ → G, onde A e um alfabeto finito. Seja ψ : B∗ → G um outro homomorfismosobrejetivo, onde B e um alfabeto finito. Entao G admite uma estrutura automatica para ψ.
A prova e bastante tecnica e nao sera apresentada aqui.
10.2 Caraterizacao geometrica
A parte mais tecnica da manipulacao dos grupos automaticos envolve naturalmente as linguagensLa ⊆ A∗$. Isso pode ser evitado recorrendo ao grafo de Cayley ΓA(G), atraves da metrica dA e doconceito de linguagem lipschitziana definida na Subseccao 9.3:Teorema 10.5 Sejam A um alfabeto finito, G um grupo e ϕ : A∗ → G um homomorfismo sobreje-tivo. Seja L ⊆ A∗ uma seccao racional de ϕ. Entao as condicoes seguintes sao equivalentes:
(i) L e uma estrutura automatica para ϕ;
(ii) L e lipschitziana.
79
Prova. (i) ⇒ (ii). Para cada a ∈ A∪ {1}, seja Aa um A$-automato finito reconhecendo La. Seja Ko maior numero de vertices existente nalgum destes automatos. Vamos mostrar que L e (2K − 1)-lipschitziana.
Sejam u, v ∈ L tais que dA(uϕ, vϕ) ≤ 1. No grafo de Cayley as arestas tem rotulos em A,mas podemos afirmar que existe a ∈ A tal que vϕ = (ua)ϕ ou uϕ = (va)ϕ. Trocando u com vse necessario, podemos assumir que vϕ = (ua)ϕ, logo u � v ∈ La. Logo existe em Aa um caminhobem-sucedido da forma
→ q0u�v−−−→t→ (20)
Seja n ∈ N e seja w = u[n] � v[n]. Podemos fatorizar (20) como
→ q0w−→q w′−→t→
Seja q z−→t uma geodesica de Aa. Entao |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
→ q0w−→q z−→t→
em Aa, resulta facilmente que wz e necessariamente da forma (u[n]z1) � (v[n]z2), logo (u[n]z1a)ϕ =(v[n]z2)ϕ e portanto
dA(u[n]ϕ, v[n]ϕ) ≤ |z1az−12 | ≤ 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ϕ)−1p(xπ2ϕ)}.
Seja a ∈ A e consideremos o A$-automato finito (determinıstico) Aa = (Q, 1, aϕ,E). Vamosmostrar que
La = L(Aa) ∩ (L � L). (21)
Seja w ∈ La. Entao w = u � v para alguns u, v ∈ L tais que vϕ = (ua)ϕ, logo w ∈ L � L. Para0 ≤ n ≤ max {|u|, |v|}, seja un a n-esima 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
q0x1−→q1
x2−→ . . .xn−→qn (22)
e um caminho em Aa.Como L e ε-lipschitziana, temos qk ∈ Q para todo k. Alem disso, se 1 ≤ k ≤ n, entao
qk = (u[k]ϕ)−1(v[k]ϕ) = (ukϕ)−1(u[k−1]ϕ)−1(v[k−1]ϕ)(vkϕ) = (xkπ1ϕ)−1qk−1(xkπ2ϕ),
logo (qk−1, xk, qk) ∈ E e portanto (22) e um caminho em Aa. Como q0 = 1 e qn = (uϕ)−1(vϕ) = aϕ,resulta que (22) e bem-sucedido e logo x1x2 . . . xn ∈ L(Aa), isto e
w = u � v = x1x2 . . . xn ∈ L(Aa).
LogoLa ⊆ L(Aa) ∩ (L � L).
80
Reciprocamente, seja x ∈ L(Aa) ∩ (L � L). Entao temos x = u � v para alguns u, v ∈ L e x e orotulo de um caminho bem-sucedido em Aa da forma (22). Como qk = (xkπ1ϕ)−1qk−1(xkπ2ϕ) parak = 1, . . . , n, obtemos
aϕ= qn = (xnπ1ϕ)−1 . . . (x1π1ϕ)−1q0(x1π2ϕ) . . . (xnπ2ϕ)= (xπ1ϕ)−1(xπ2ϕ) = (uϕ)−1(vϕ)
e logo (ua)ϕ = vϕ. Resulta que x = u � v ∈ La e logo (21) e valido.Pela Proposicao 2.5 e pelo Lema 10.2, La e racional e logo L e uma estrutura automatica para
ϕ. �
Corolario 10.6 Todo grupo hiperbolico e automatico.
Prova. Seja G um grupo hiperbolico. Como G e finitamente gerado, podemos tomar um homomor-fismo sobrejetivo de monoides ϕ : A∗ → G para algum alfabeto finito A. Podemos estender ϕ a umhomomorfismo involutivo (sobrejetivo) A∗ → G, que designamos tambem por ϕ.
Pelo Teorema 9.9, GeoA(G) e racional, e e obviamente uma seccao de ϕ. Por outro lado, oTeorema 9.8 implica que GeoA(G) e lipschitziana. Logo, pelo Teorema 10.5, GeoA(G) e uma estruturaautomatica para ϕ e portanto G e automatico. �
Usaremos o Teorema 10.5 para provar a existencia de grupos automaticos nao hiperbolicos.Comecamos pelo seguinte lema:Lema 10.7 Sejam A um alfabeto finito, G um grupo e ϕ : A∗ → G um homomorfismo sobrejetivo.Seja L uma estrutura automatica com unicidade para ϕ. Entao existe K > 0 tal que∣∣|u| − |v|∣∣ ≤ KdA(uϕ, vϕ)
para todos u, v ∈ L.
Prova. Para cada a ∈ A, seja Aa um A$-automato finito reconhecendo La. Seja K o maior numerode vertices existente nalgum destes automatos.
Sejam u, v ∈ L. O caso dA(uϕ, vϕ) = 0 e trivial pois a estrutura tem unicidade. Suponhamosque dA(uϕ, vϕ) = 1. Trocando u e v se necessario, podemos assumir que vϕ = (ua)ϕ para alguma ∈ A. Logo u � v ∈ L(Aa). Suponhamos que |v| > |u| + K. Seja v = v′v′′ com |v′| = |u|. Entaotemos em Aa um caminho bem-sucedido da forma
→ iu�v′−−−→q 1�v′′−−−→t→
Como |v′′| > K, existe algum vertice repetido no caminho q 1�v′′−−−→t. Logo podemos eliminar um loope obter u �w ∈ L(Aa) = La para algum w ∈ L \ {v}. Mas entao wϕ = (ua)ϕ = vϕ, contradizendo aunicidade da estrutura.
Analogamente se exclui o caso |u| > |v| + K, logo∣∣|u| − |v|∣∣ ≤ K e o resultado e valido quando
dA(uϕ, vϕ) = 1.Finalmente, suponhamos que dA(uϕ, vϕ) = n > 1. Entao existe uma sucessao 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∣∣|u| − |v|∣∣ =
∣∣ n∑i=1
|wi−1| − |wi|∣∣ ≤ n∑
i=1
∣∣|wi−1| − |wi|∣∣ ≤ Kn = KdA(uϕ, vϕ)
como pretendıamos. �
81
Vamos agora discutir o produto direto:Proposicao 10.8 O produto direto de grupos automaticos e um grupo automatico.
Prova. Para i = 1, 2, seja Li uma estrutura automatica com unicidade para o homomorfismo sobre-jetivo ϕ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 L1L2 e uma estrutura automatica para ϕ.
Pela Proposicao 2.7, L1L2 e racional, e e claro que L1L2 e uma transversal de ϕ. Logo, peloTeorema 10.5, basta mostrar que L1L2 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 L1L2 e ε-lipschitziana.
Sejam ui, vi ∈ Li (i = 1, 2) com dA((u1u2)ϕ, (v1v2)ϕ) ≤ 1. Se (u1u2)ϕ = (v1v2)ϕ, entao u1 = v1
e u2 = v2 pois Li e uma estrutura automatica com unicidade para i = 1, 2, logo podemos assumirsem perda de generalidade que (v1v2)ϕ = (u1u2a)ϕ para algum a ∈ A.
Suponhamos primeiro que a ∈ A2. Entao (v1v2)ϕ = (u1u2a)ϕ implica v1ϕ1 = u1ϕ1 e v2ϕ2 =(u2a)ϕ2, logo v1 = u1 e u2 � v2 ∈ (L2)a. Logo
dA(((u1u2)[n])ϕ, ((v1v2)[n])ϕ) =
{0 se n ≤ |u1|dA(u[n−|u1|]
2 ϕ, v[n−|u1|]2 ϕ) ≤ ε2 ≤ ε se n > |u1|
Suponhamos agora que a ∈ A1. Entao (v1v2)ϕ = (u1u2a)ϕ implica v1ϕ1 = (u1a)ϕ1 e v2ϕ2 =u2ϕ2, logo u1 �v1 ∈ (L1)a e v2 = u2. Temos pois a seguinte situacao no grafo de Cayley ΓA(G1×G2):
• u2 //
a
��
a
��
a
��
•
a
��
•
u1
55kkkkkkkkkkkkkkkkkk
v1))SSSSSSSSSSSSSSSSSS · · ·
•v2=u2
// •
Se n ≤ |u1|, |v1|, entao
dA(((u1u2)[n])ϕ, ((v1v2)[n])ϕ) = dA(u[n]1 ϕ, v
[n]1 ϕ) ≤ ε1 ≤ ε.
Por outro lado, se n ≥ |u1|, |v1|, entao
dA(((u1u2)[n])ϕ, ((v1v2)[n])ϕ) = dA((u1u[n−|u1|]2 )ϕ, (v1v
[n−|v1|]2 )ϕ) ≤ K + 1
pois∣∣|u1| − |v1|
∣∣ ≤ K por definicao de K e pela figura anterior.Suponhamos agora que |v1| < n < |u1|. Entao
dA(((u1u2)[n])ϕ, ((v1v2)[n])ϕ) = dA(u[n]1 ϕ, (v1v
[n−|v1|]2 )ϕ)
≤ dA(u[n]1 ϕ, v1ϕ) + dA(v1ϕ, (v1v
[n−|v1|]2 )ϕ)
≤ dA(u[n]1 ϕ, v
[n]1 ϕ) + n− |v1|
< ε1 + |u1| − |v1|< ε1 +K < ε.
O caso |u1| < n < |v1|, e analogo, logo L1L2 e ε-lipschitziana e G1 ×G2 e automatico. �
82
Corolario 10.9 Todo grupo abeliano livre finitamente gerado Z× . . .× Z e automatico.
Prova. O grupo livre Z e automatico pelo Teorema 9.6 e pelo Corolario 10.6. Aplicando sucessiva-mente a Proposicao 10.8, obtemos o pretendido. �
Pelo Teorema 9.6(iv), comprovamos que a classe dos grupos automaticos contem estritamente ados grupos hiperbolicos.
10.3 Propriedades
Terminamos estudando algumas propriedades dos grupos automaticos. Comecamos pelo problemada palavra:Teorema 10.10 Todo grupo automatico tem problema da palavra decidıvel.
Prova. Seja G um grupo e seja L uma estrutura automatica para o homomorfismo sobrejetivoϕ : A∗ → G, onde A e finito. Estendemos ϕ a um homomorfismo involutivo (sobrejetivo) A∗ → G,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 provado Lema 10.2, basta tomar vi ∈ (Lai ∩ vi−1π
−11 )π2. Pelas Proposicoes 2.5 e 2.9, (Lai ∩ vi−1π
−11 )π2 e
uma linguagem racional e nos podemos calcular efetivamente um dos seus elementos.Em particular, calculamos vn ∈ L∩ (v0u)ϕ−1. Agora, para determinar se uϕ = 1, basta verificar
se v0 � vn ∈ L1 ou nao.Para provar o caso geral, temos que saber lidar com letras da forma a−1 (a ∈ A). Para comecar,
podemos utilizar o caso anterior para determinar w1 ∈ L ∩ 1ϕ−1: se for necessario, testamos todasas palavras u ∈ L (que e bem ordenado pela ordem lexicografica) ate encontrar a desejada. Agorae facil encontrar wa−1 ∈ L ∩ a−1ϕϕ−1: basta tomar wa−1 ∈ (Lai ∩ w1π
−12 )π1. Assim, dada u ∈ A∗
qualquer, comecamos por substituir cada letra a−1 (a ∈ A) em u por wa−1 , obtendo assim umapalavra u′ ∈ A∗. Como uϕ = u′ϕ, basta usar o caso anterior para determinar se u′ϕ = 1. �
Vamos agora usar a caraterizacao geometrica para provar o seguinte resultado. A prova e longae por vezes tecnica, mas interessante:Teorema 10.11 Todo grupo automatico:
(i) e finitamente apresentavel;
(ii) admite uma funcao isoperimetrica quadratica.
Prova. (i) Seja G um grupo e seja L uma estrutura automatica com unicidade para o homomorfismosobrejetivo ϕ : A∗ → G, onde A e finito. Estendemos ϕ a um homomorfismo involutivo (sobrejetivo)A∗ → G, que designamos ainda por ϕ. Entao existe um homomorfismo sobrejetivo Φ : FA → G talque o diagrama
A∗ϕ //
�
G
FA
Φ
>>~~~~~~~~
83
comuta, onde θ : A∗ → FA designa a projecao canonica. Para cada g ∈ G, seja wg o unico elementode L ∩ gϕ−1.
Pelo Teorema 10.5, L e ε-lipschitziana para algum ε > 0. Seja
R = {u ∈ 1ϕ−1∣∣ |u| ≤ 2ε+ 2} ∪ {w1}
e N = 〈〈Rθ〉〉. E claro que Rθ e um subconjunto finito de Ker(Φ), logo N ⊆ Ker(Φ). Para mostrarque P = 〈A | R〉 e uma apresentacao finita de G, basta mostrar que KerΦ ⊆ N .
Comecamos por fazer um esboco da prova de que
u � v ∈ La ⇒ (uav−1)θ ∈ N (23)
para todos u, v ∈ L e a ∈ A.Seja m = max {|u|, |v|}. Para cada n ∈ {1, . . . ,m}, seja u[n]ϕ
zn−→v[n]ϕ uma geodesica em ΓA(G).E claro que |zn| ≤ ε para todo n. Usando estas geodesicas e os caminhos 1 u−→uϕ e 1 v−→vϕ, podemosconstruir um diagrama de van Kampen (generalizado) de P de bordo uav−1. Este diagrama diz-segeneralizado porque os relatores de Rθ nao sao necessariamente palavras ciclicamente reduzidas, e omesmo acontece com o bordo. Mas a sua existencia garante igualmente que a imagem do bordo porθ esta em N . Exemplificamos a construcao do diagrama para u = a1a2a3 e v = b1b2b3b4:
• a2 //
z1
��
• a3 //
z2
��
uϕ
z3
��
z4
!!DDDDDDDD
1
a1
@@�������� b1 // • b2 // • b3 // • b4 // vϕ
Em geral, cada um dos diagramas interiores tem como bordo uma palavra que e rotulo de um loopem ΓA(G) e tem comprimento ≤ 2ε+ 2, logo pertence a R. Logo (23) e valido.
Em seguida mostramos que(uw−1
uϕ)θ ∈ N (24)
para todo u ∈ A∗. Usamos inducao sobre |u|.O caso |u| = 0 resulta de w1 ∈ R. Suponhamos entao que |u| = n > 0 e que (24) e valido para
palavras mais curtas. Podemos escrever u = vb para algum b ∈ A. Logo
(uw−1uϕ)θ = (vbw−1
(vb)ϕ)θ = (vw−1vϕ )θ(wvϕbw−1
uϕ)θ. (25)
Como (vw−1vϕ )θ ∈ N por hipotese de inducao, basta mostrar que
(wvϕbw−1uϕ)θ ∈ N. (26)
Se b ∈ A, usamos diretamente (23), logo podemos assumir que b = a−1 para algum a ∈ A, isto e,u = va−1. Mas entao (wuϕaw−1
vϕ )θ ∈ N por (23) e logo
(wvϕbw−1uϕ)θ = ((wuϕaw−1
vϕ )θ)−1 ∈ N.
Concluimos assim que (26) e valido e portanto (24) tambem.Finalmente, seja g ∈ Ker(Φ). Entao (24) e w1 ∈ R implicam
g = gθ = (gw−1gΦ)θ(wgΦθ) = (gw−1
gϕ )θ(w1θ) ∈ N,
84
logo Ker(Φ) ⊆ N e P e uma apresentacao finita de G.(ii) Mantendo toda a notacao de (i), tomamos a constante K > 0 dada pelo Lema 10.7. Comeca-
mos por mostrar queArea((uw−1
uϕ)θ) ≤ (K + |w1|+ 1)|u|2 (27)
para todo u ∈ A+. Usamos inducao sobre |u|.Suponhamos que |u| ≥ 1 e (27) e valida para palavras mais curtas. Escrevemos u = vb com
b ∈ A. Por (25), temos(uw−1
uϕ)θ = (vw−1vϕ )θ(wvϕbw−1
uϕ)θ.
Se v = 1, temosArea((vw−1
vϕ )θ) = Area(w−11 θ) = 1.
Se v 6= 1, obtemosArea((vw−1
vϕ )θ) ≤ (K + |w1|+ 1)|v|2
pela hipotese de inducao, logo em qualquer caso
Area((uw−1uϕ)θ) ≤ (K + |w1|+ 1)|v|2 + 1 + Area((wvϕbw−1
uϕ)θ). (28)
Resulta da prova de (23) (substituindo wvϕbw−1uϕ por wuϕb−1w−1
vϕ se necessario) que
Area((wvϕbw−1uϕ)θ) ≤ max {|wvϕ|, |wuϕ|}.
Como∣∣|w1| − |wuϕ|
∣∣ ≤ KdA(1, uϕ) ≤ K|u| pelo Lema 10.7, obtemos |wuϕ| ≤ K|u|+ |w1|. Analoga-mente, |wvϕ| ≤ K|v|+ |w1|, logo
Area((wvϕbw−1uϕ)θ) ≤ K|u|+ |w1|
e logo por (28) e facil verificar que
Area((uw−1uϕ)θ)≤ (K + |w1|+ 1)|v|2 + 1 +K|u|+ |w1|
≤ (K + |w1|+ 1)(|u| − 1)2 + (K + |w1|+ 1)|u|≤ (K + |w1|+ 1)|u|2.
Logo (27) e valido para todo u ∈ A+.Seja agora g ∈ Ker(Φ). Se g 6= 1, resulta de (27) que
Area(g) = Area((gw−1gΦwgΦ)θ) ≤ Area((gw−1
gϕ )θ) + Area(w1θ) ≤ (K + |w1|+ 1)|g|2 + 1≤ (K + |w1|+ 2)|g|2.
Como esta desigualdade e trivialmente valida quando g = 1, entaoG admite uma funcao isoperimetricaquadratica. �
Notamos que, contrariamente ao que acontece com os grupos hiperbolicos, o recıproco de (ii) naoe valido, pois existem grupos nao automaticos admitindo uma funcao isoperimetrica quadratica.
De fato, nem tudo sao sucessos na teoria dos grupos automaticos... por exemplo, ainda hoje sedesconhece se todo grupo automatico tem problema da conjugacao decidıvel! Para contornar esseproblema, os criadores do conceito de grupo automatico inventaram tambem os grupos biautomaticos.Na versao automatos, exige-se que as linguagens aL (onde a convolucao e feita a direita em vez de ser
85
a esquerda) sejam tambem racionais. Na versao geometrica, considera-se uma versao da propriedadedos dois viajantes em que os caminhos a percorrer no grafo de Cayley devem comecar a distancia≤ 1 e terminar a distancia ≤ 1.
O problema da conjugacao e decidıvel para todo grupo biautomatico... mas ignora-se se os doisconceitos sao ou nao equivalentes, pois todos os exemplos conhecidos de grupos automaticos saotambem biautomaticos!
Um outro frustrante problema em aberto e o da existencia de um recıproco para a Proposicao10.8: sera que G×H automatico implica G e H automaticos?
10.4 Exercıcios
(10.1) Construa uma estrutura automatica L para Z, produzindo explicitamente automatos finitosreconhecendo L e as linguagens La.
(10.2) Um grupo diz-se de Burnside se for infinito, finitamente gerado e de torsao. Mostre que umgrupo de Burnside nao pode ser automatico.
[Sugestao: Considere um loop nao trivial num automato reconhecendo uma estrutura au-tomatica 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 sao racionais, entao X ◦ Y e racional.
[Sugestao: Use projecoes πij : (A ∪ {$})3 → (A ∪ {$})2 para i, j ∈ {1, 2, 3} distintos.]
(10.4) Seja L uma estrutura automatica para ϕ : A∗ → G. Mostre que Lw e racional para todow ∈ A∗.
[Sugestao: Use o Exercıcio (10.3).]
(10.5) Indique uma estrutura automatica para Z× Z× C3.
(10.6) Mostre que o produto livre de grupos automaticos e automatico.
86
Bibliografia
1. L. Bartholdi e P. V. Silva, Rational subsets of groups, Chapter 23 of the handbook AutoMathA(aguarda publicacao), arXiv:1012.1532, 2010.
2. L. Bartholdi e P. V. Silva, Groups defined by automata, Chapter 24 of the handbook Au-toMathA (aguarda publicacao), 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’apres 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, Elements de Theorie 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 Sys-tems (DCFS 2012), volume 7386 of LNCS (2012) 50–63.
87
Indice de conceitos
alfabeto, 9apresentacao, 50
finita, 50area, 56aresta
central, 45compatıvel, 45de um automato, 11de um grafo, 10
arvore geradora, 31atrator, 48automato, 11
aparado, 12com transicoes-1, 12completo, 12de Stallings, 28determinıstico, 11finito, 11flor, 28inverso, 24involutivo, 24SFG, 29sobre um monoide M , 23
automorfismode grafos, 10de grupos, 5
baseem FA, 20em A∗, 9
bordode um diagrama de van Kampen, 54de uma regiao, 53do grupo livre, 42
caminhobem-sucedido, 11central, 45compatıvel, 45
maximal, 46infinito, 39nao trivial, 11trivial, 11
completado, 40composicao de relacoes, 12comprimento
em A∗, 9em FA, 19
comutador, 50concatenacao, 9, 39Conjetura de Hanna Neumann, 35conjugado, 21
cıclico, 21construcao de Stallings, 28convolucao, 77
diametro, 67diagrama de van Kampen, 54
bordo de um, 54diagrama de van Kampen
dimensao de um, 54dimensao
de um diagrama de van Kampen, 54de um grupo livre, 20
endomorfismo, 44espaco de Cantor, 41espaco metrico, 36
compacto, 41completado de um, 40completo, 40discreto, 40
estrutura automatica, 77com unicidade, 77
fatorem A∗, 10em Aω, 39
fecho, 42funcao
de Dehn, 57isoperimetrica, 56
exponencial, 56linear, 56polinomial, 56quadratica, 56
88
recursiva, 56subquadratica, 72
uniformemente contınua, 47
geodesicanum automato, 32num grafo, 67, 72numa arvore geradora, 31
grafo, 10A-, 11
conexo, 53δ-hiperbolico, 67bipartido, 53completo, 53conexo, 10de Cayley, 24diametro de um, 67finito, 10hiperbolico, 67orientado, 10planar, 53transitivo nos vertices, 25
grupo, 4cıclico, 7de Artin ortogonal, 63de Burnside, 86de grafo, 63de permutacoes, 4de torsao, 21finitamente apresentavel, 50finitamente gerado, 7fundamental, 62hiperbolico, 70livre, 19livre de torsao, 21quociente, 6residualmente finito, 35simetrico, 4virtualmente livre, 71
homomorfismode grupos, 5de monoides, 5involutivo, 17nucleo de um, 6
inverso formal, 17involucao, 17isometria, 68isomorfismo
de automatos, 11de grafos, 10de grupos, 5
letra, 9linguagem, 10
ε-lipschitziana, 72de um automato, 11lipschitziana, 72racional, 11
loop, 11
maquina de Turing, 52metrica, 36
dos prefixosem A∗, 39em FA, 41
geodesicanum grafo, 67num grupo, 69
profinita, 37monoide, 5
livre, 9
nucleo cıclico, 21
operadores booleanos, 13ordem, 7
boa, 78lexicografica, 78total, 78
palavra, 9ciclicamente reduzida, 21infinita, 39
reduzida, 42irredutıvel, 15reduzida, 18
permutacao, 4ponto base, 25ponto fixo, 44
infinito, 48regular, 48
89
singular, 48prefixo
em A∗, 9em Aω, 39em FA, 19
problema da conjugacao, 21problema da palavra, 20
decidıvel, 20, 52generalizado, 31
produtoΓ-, 62de grafo, 62direto
de automatos, 13de grupos, 7
livre, 60com amalgamacao, 62forma normal do, 61
propriedade dos dois viajantes, 72propriedade universal
em A∗, 9em FA, 18
quase-isometriade espacos metricos, 68de grafos, 69
raio, 42reducao, 15
elementar, 15regiao, 53
bordo de uma, 53exterior, 53fronteira de uma, 53
relator, 50repulsor, 49rotulo
de um caminho, 11infinito, 39
de uma aresta, 10
seccao, 77sistema de reescrita, 15
confluente, 15noetheriano, 15redutor, 15
subconjunto racional, 23subgrupo, 5
conjugado, 33de ındice finito, 7gerado por um subconjunto, 7ındice de um, 7normal, 6
gerado por um subconjunto, 50sucessao
convergente, 40de Cauchy, 40limite de uma, 40
sufixoem A∗, 9em Aω, 39
Teoremade Benois, 22de Cayley, 5de Howson, 35de Marshall Hall, 37de Nielsen-Schreier, 32de van Kampen, 62
transversal, 77triangulo geodesico, 67
ultrametrica, 36
verticeadjacente, 10de um automato, 11de um grafo, 10inicial, 11terminal, 11
90
![Análise de Algoritmoscris/aulas/17_2_338/slides/aula19.pdf · Algoritmo de Prim PRIM (G,c) 1 seja s um vértice arbitrário de G 2 para v ∈V(G)\{s}faça key[v] ←∞ 3 key[s]](https://img.document.onl/doc/110x75/5fb58630bfc0cc48ca637944/anlise-de-algoritmos-crisaulas172338slides-algoritmo-de-prim-prim-gc.jpg)
![Prova Final de Matemática - matematica.pt · A classificação da prova deve respeitar integralmente ... – seja omitido qualquer elemento da sequência ... Desenhar [AB] com um](https://img.document.onl/doc/110x75/5c0020aa09d3f28a0c8bbb77/prova-final-de-matematica-a-classificacao-da-prova-deve-respeitar-integralmente.jpg)
![&hH tal que F cij seja mínimo [Parker e Rardin, 121 . (i,] E H Formula@o por programagão linear inteira: Seja C = (c,) uma matriz n x n onde cada elemento c, representa a distância](https://img.document.onl/doc/110x75/6097b166d4a4f5028c2aec30/h-h-tal-que-f-cij-seja-mnimo-parker-e-rardin-121-i-e-h-formulao-por.jpg)
