Re: [NTG-context] Buggy source code--> references disappears when I put sections and If I put subjects, \completecontent has void list.

Ooops, the souce ;-) En/na Xan ha escrit:

Hi,

I'm desesperated. I have I source code (that I attached) that when I substitute any (for example the last) ocurrence of subject for section, then references appears in blank.

If I maintain the subjects (and subsubjects...), then \completecontent gives me a void list.

What happens?. Hans can you help me?. The last time you help me find me a trouble in my sources (redefine registers). Is this a buggy source....?

Thanks in advance, Xan.

PS: Yes, I know the source is big, but the error is simpl.

% interface=en output=pdftex %\environment capcalera.context % Capçalera % Regime \enableregime[utf] % Choose a font \setupbodyfont [cmr,11pt] % cmr, 11pt % Be tolerant with paragraph building \setuptolerance [horizontal,verytolerant,stretch] % Choose a language, and associated hyphenation rules. %\language [ca] \mainlanguage[ca] % Page number \setuppagenumbering [location={footer}] % White space between paragraphs %\setupwhitespace [big] % Paper size \setuppapersize [a4] % Margins %\setuplayout [grid=yes, footer=0.5\footerheight, header=0.5\headerheight] %\setuplayout[footer=2cm, header=2cm] %\showlayout %\showframe %\showsetups % Format de marges %\setuplayout[topspace=1.5cm, % marge d'adalt %margin=1.5cm, %marges dels costats %header=1.0cm,%separació entre adalt i primera línia %footer=1.0cm,%separació entre abaix i darrera línia %width=fit,height=fit,backspace=2cm] % Enable colors and activate hyperlinks \setupcolors [state=start] \definecolor[lightblue][r=0.5, g=0.5, b=1.0] %\setupinteraction [state=start, color=lightBlue] %\setupurl[style=small, space=yes] \setupurl[space=yes] % Enumerate the URLs %\useURL[wiki][http://wiki.contextgarden.net][][\ConTeXt\ wiki] %\useURL[nagorko-pdf][http://www.math.bgu.ac.il/~barakw/probseminar/nagorko/slides.pdf][][http://www.math.bgu.ac.il/\~{}barakw/\quad\quad\quad\quad probseminar/nagorko/slides.pdf] %\useURL[govern-me][http://sgtrelinst.caib.es/llibrestil/00index.html][][http://sgtrelinst.caib.es/llibrestil/00index.html] %\useURL[context-manual-pdf][http://www.pragma-ade.com/general/manuals/cont-eni.pdf][][http://www.pragma-ade.com/general/manuals/ cont-eni.pdf] %\useURL [contextgarden] [{http://www.contextgarden.net}] %\useURL [mccammond][{http://www.math.ucsb.edu/~jon.mccammond/geogrouptheory/}][] [{\tf http://www.math.ucsb.edu/\~{}jon.mccammond/geogrouptheory/}] % Fonts %% Chapters... \setupheads[align=flushleft] \setuphead[chapter][style={\bfd}] \setuphead[section][style={\bfc}, header=nomarking] \setuphead[subsection][style={\bfb}] \setuphead[subsubsection][style={\bfa}] %\setuphead[section][textstyle=bold] % Bibliography options % BIBTEX \usemodule[bib] %\usemodule[bibltx] \setupbibtex[database=memoria,sort=author] \setuppublications [alternative=ams,numbering=yes, sorttype=bbl, criterium=cite]% \setupheadtext[ca][pubs=Referències] \setuppublicationlist[authoretallimit=3] \setuppublicationlist[authoretaltext={\it\ et al.}] \setuppublicationlist[authoretaldisplay=1] %Indentation \setupheads[indentnext=yes] \setupindenting[yes,small,first] %\setupformulae[indentnext=yes] % Vertical spaces between paragraphs \setupwhitespace[small] %Itemize \setupitemize[each][indentnext=no,margin=2em] % [identnext=yes,margin=2em] \setupitemize[each][headstyle=bold] %\setupitemize[a][right=),stopper=] % Mathematical packets \usemodule[newmat] \usemodule[math-ams] % Heads and footers %\setupfootertexts[][{\tfxx \currentdate}] %\setupfootertexts[\pagenumber/\lastpage] %\setupfooter[text][before=\hrule] %\setupheader[text][after=\hrule] %\setupheadertexts[{\tfx Màster de Matemàtiques}][{\tfx \jobname.\ConTeXt{}.\currentdate}] %\setupheadertexts[][{\tfx \currentdate}] % hyphenating \hyphenation{do-cu-ment} \hyphenation{pro-ble-ma} \hyphenation{es-crip-tu-ra} \hyphenation{ge-ne-ra-lit-za-ció} \hyphenation{cor-res-po-nents} \hyphenation{pa-rells} \hyphenation{ge-ne-rat} \hyphenation{re-so-lu-ble} \hyphenation{ge-ne-ra-dors} \hyphenation{re-pre-sen-ta-rem} % Modules \usemodule[tikz] \usemodule[pgfmath] \usetikzlibrary[mindmap,arrows,calc,decorations.pathmorphing,decorations.markings] \usetikzlibrary[trees] % AMSTHM equivalent %% Exercici \defineenumeration [exercici] [text={Problema},headstyle=bold,between=\blank,titledistance=0em,textdistance=1em, stopper={.\space},location=serried,left={\bgroup\bf},right={\egroup},width=fit,before={\bgroup\startframedtext[background=screen,frame=off,width=broad]},after={\stopframedtext\egroup}] %% Lema \defineenumeration [mylema] [text={Lema}, % Què es mostra before={\blank[big]}, % abans de lema, un bigskip after={\blank[big]}, % després de lema, un bigskip headstyle=bold, % Negreta per la capçaleras %between=\blank, % Entre Lemmes una línia en blanc titledistance=.5em, % espai entre número i parèntesis. textdistance=.5em, % espai entre ) i text stopper={.\space}, % Com acaba. Després de parèntesis un '.' location=serried, width=fit, % que ocupi tot l'espai style=italic, % estil del text title=yes, % si puc posar o no arguments opcionals titlestyle=bf, % estil del títol way=bytext, % enumerar en tot el document conversion=numbers,indenting=yes] % enumera amb arabic %% Proposició, corol·laris, teoremes. %% Comparteix els nombres amb lema %% Si volem que vagin a part, hem de posar 'number=proposition' \defineenumeration [myproposition] [mylema] [text={Proposició}] \defineenumeration [mycorollary] [mylema] [text={Corol·lari}] \defineenumeration [mytheorem] [mylema] [text={Teorema}] %% Definició \defineenumeration [mydefinition] [mylema] [text={Definició},style=tf,titlestyle=bf,indenting=yes] \defineenumeration [mynotation] [mydefinition] [text={Notació},style=tf,titlestyle=bf,indenting=yes] \defineenumeration [mynota] [mydefinition] [text={Nota},style=tf,titlestyle=bf,indenting=yes] %% Demostració \defineenumeration[mydemo][text={Demostració.\space},number=no,location=serried,width=fit,headstyle=italic,indentnext=yes,between=\blank,textdistance=.5em,closesymbol={\mathematics{\Box}},style=normal,indenting=yes] % Table of contents %% dots between... and subsubsubsection are not listed \setupcombinedlist[content][level=4,alternative=c] %% section = bold. % width= 10mm --> less space between num-letter %% line break after section. \setuplist[section][style=bold,width=10mm] \setuplist[section][before=\blank] %% margin = 10 mm. Put the subsection just bottom section. \setuplist[subsection][margin=10mm,width=10mm] \setuplist[subsubsection][margin=20mm,width=10mm] %\setuplist[subsection] %[distance=1em] % section = bold. % % Això ho trec d'un manual: %\setuplist[subsection] % [margin=1em, % numbercommand=\NumCom] %\def\NumCom#1{\hbox to 2em{\hfill #1}} % Set "Índex" like "Índex de continguts" \setupheadtext [ca] [content=Índex] % Definitions/abbreviations \define[1]\dist{d(\sigma_g(#1), \sigma_h(#1))} \define[1]\imp{{\bgroup\startframedtext[background=screen,frame=on,width=broad]#1\stopframedtext\egroup}} %\define[1]\imp{{\bgroup\startframedtext[background=color,backgroundcolor=lightblue,frame=on,width=broad]#1\stopframedtext\egroup}} % SPLIT \def\startsplit {\startalign} % no number by default \def\stopsplit {&\doalignNR[+][]\crcr % for a number on last line \stopalign} % Other \setupunderbar[alternative=b] % Fix underline style % For putting underline with spaces: \underbar{\dorecurse{40}~} % Define new register for the Index of Symbols \defineregister[mysymbol][mysymbols] % Setup figures: %\setupfloat[figure][spacebefore=5*big,spaceafter=big] % Start the text \starttext \version[concept] %\title{Introducció} \title{Preliminars} En aquests preliminars s'introdueixen les definicions i notacions bàsiques que s'empraran al llarg d'aquesta memòria. La primera secció està dedicada a recordar les definicions i teoremes bàsics de la Teoria de Grups i a enunciar en què consisteix el problema de la paraula per a grups. A la segona secció, s'introdueixen els conceptes estàndard de la Teoria Geomètrica de Grups. Entre aquests es mencionen els conceptes de diagrames de van Kampen, grafs de Cayley i funcions de Dehn. \subject{Conceptes bàsics} \subsubject{Paraules sobre un alfabet} En aquest apartat farem memòria de la definició de paraula (sobre un alfabet) i introduirem certes notacions i operacions estàndards que farem servir posteriorment. Recordem que un {\em alfabet}\index{alfabet} és un conjunt qualsevol de símbols, els quals anomenarem {\em lletres}\index{lletres}. Si $A$ és un alfabet, aleshores una {\em paraula $w$ sobre $A$}\index{paraula} és una successió finita de lletres de $A$, que escriurem com $w = w_1 \ldots w_k$. Indicarem amb $\varepsilon$ la paraula que no té cap lletra, la qual anomenarem {\em paraula buida}\index{paraula+buida}. Quan $w$ consti de dues o més lletres iguals consecutives, per comoditat, podrem agrupar-les usant la notació multiplicativa. Per exemple si $A = \{a,b\}$, aleshores $ab^3a^2b$ denotarà la paraula $abbbaab$. La {\em concatenació}\index{concatenació de paraules} de dues paraules $w_1$, $w_2$ sobre $A$, que indicarem amb $w_1 \cdot w_2$, és la juxtaposició de $w_1$ i $w_2$, és a dir, si $w_1 = a_1 \ldots a_k$ i $w_2 = b_1 \ldots b_s$, aleshores \startformula w_1 \cdot w_2 = a_1 \ldots a_k b_1 \ldots b_s, \stopformula amb la convenció que $w_1 \cdot \varepsilon = \varepsilon \cdot w_1 = w_1$. Sovint ometrem el símbol $\cdot$ i escriurem $w_1 w_2$ per denotar $w_1 \cdot w_2$. Si $w$ és una paraula sobre $A$, aleshores $l(w)$\mysymbol{$l(w)$} denotarà la seva {\em longitud}\index{longitud+d'una paraula}, és a dir, el seu nombre de símbols. De forma clara, $l(u \cdot v) = l(u) + l(v)$, per a qualssevol paraules $u, v$ sobre $A$. D'altra banda, indicarem amb $w(t)$ el {\em prefix de $w$ de longitud $t$}\index{paraula+prefix de longitud $t$,}. Formalment, si $w = \varepsilon$, llavors $w(t) = \varepsilon$, per a tot $t \in \naturalnumbers$ i, si $w = w_1 \ldots w_k$, aleshores $w(t) = w_1 \ldots w_t$ per a tot $t \leq k$ i $w(t) = w$ per a tot $t > k$. Per últim, indicarem amb $A^*$ el {\em monoide lliure sobre $A$}\index{monoide lliure}, és a dir, el conjunt de totes les paraules sobre $A$. \subsubject{Grups lliures} En aquesta secció construirem el {\em grup lliure} de base $X$ un conjunt qualsevol i descriurem algunes de les seves propietats a mode de teoremes. Donat $X$ un conjunt qualsevol, agafem un conjunt d'inverses formals de $X$, que indicarem amb $X^{-1}$, format per símbols $x^{-1}$ per a cada $x \in X$. Formalment, $X^{-1}$ és un conjunt del mateix cardinal que $X$ juntament amb una funció bijectiva ${}^{-1} \colon X \to X^{-1}$, de manera que, per a tot $x \in X$, la imatge de $x$ per ${}^{-1}$ s'escriu $x^{-1}$. Amb aquests conjunts podem formar el monoide lliure ${(X \cup X^{-1})}^*$ els elements del qual són llistes finites d'elements de $X$ i de les seves inverses formals. Enfatitzem que els elements de $X^{-1}$ són inverses formals: si $X = \{a, b\}$, aleshores $b$, $aba^{-1}$, $ab$ i $aba^{-1}a$ són elements diferents en el monoide lliure ${(X \cup X^{-1})}^*$. Afegirem dues convencions: abusant del llenguatge, si $a \in X^{-1}$ i $a = x^{-1}$ per a algun $x \in X$, aleshores $a^{-1}$ denotarà $x$, o sigui, de manera informal, el que feim és fer involutiva la funció ${}^{-1}$. D'altra banda, estendrem les inverses formals a les paraules. Per a la paraula buida definim $\varepsilon^{-1} = \varepsilon$, i si \startformula w=x_1 x_2 \ldots x_{k-1}x_k \in {(X \cup X^{-1})}^*, \stopformula aleshores $w^{-1}$ indicarà la paraula \startformula w^{-1} = x_k^{-1}x_{k-1}^{-1}\ldots x_2^{-1} x_1^{-1} \in {(X \cup X^{-1})}^*. \stopformula En poques paraules, amb aquestes convencions, hem aconseguit que ${}^{-1}$ sigui un morfisme en ${(X \cup X^{-1})}^*$ respecte de la concatenació de paraules. Sobre ${(X \cup X^{-1})}^*$ definim la relació $\sim$ definida de la manera següent: dues paraules $u$, $v$ són equivalents, i.e., $u \sim v$, si, i només si, podem passar d'una a l'altra amb un nombre finit de passes del tipus següent: \startitemize[n] \item Reducció: l'eliminació d'una ocurrència de $xx^{-1}$, per a qualque $x \in X\cup X^{-1}$. \item Amplificació: l'afegit d'una ocurrència de $xx^{-1}$, per a qualque $x \in X \cup X^{-1}$. \stopitemize És clar que $\sim$ és una relació d'equivalència. A més, preserva l'estructura de ${(X \cup X^{-1})}^*$: si $u_1 \sim u_2$ i $v_1 \sim v_2$, aleshores $u_1 \cdot v_1 \sim u_2 \cdot v_2$ i $u_1^{-1} \sim u_2^{-1}$. Per tot això, es pot veure fàcilment que ${(X \cup X^{-1})}^*/\sim$ és un grup (l'element neutre és $[\varepsilon]_\sim$ i la inversa de $[w]_\sim$ és $[w^{-1}]_\sim$). Anomenarem a aquest grup el {\em grup lliure de base $X$}\index{grup+lliure}, i l'indicarem amb $F(X)$\mysymbol{$F(X)$}. Si $X$ té només un sol element, aleshores $F(X) \cong \integers$, el qual és l'únic grup lliure abelià no trivial. Si $X = \emptyset$, aleshores $F(X) \cong \{1\}$. Una paraula sobre $X \cup X^{-1}$ és {\em reduïda}\index{paraula+reduïda} si no conté cap ocurrència de la forma $xx^{-1}$, amb $x \in X \cup X^{-1}$. Qualsevol paraula que només conté una lletra i $aba^{-1}$ són paraules reduïdes. La paraula buida també és reduïda. En canvi $abb^{-1}b$ i $aba^{-1}abb^{-1}a^{-1}$ no són paraules reduïdes. Donada una paraula $w \in {(X \cup X^{-1})}^*$, existeix una paraula reduïda $u$ tal que $w \sim u$, obtinguda aplicant un nombre finit de passes de reducció \cite[extras={, Lema~6.1}][grillet], la qual indicarem amb $red(w)$\mysymbol{$red(w)$}. Per exemple, $red(aba^{-1}abb^{-1}a^{-1}) = aba^{-1}$, encara que hi ha diverses maneres d'obtenir-la a partir de la paraula original: $aba^{-1}abb^{-1}a^{-1} \sim abbb^{-1}a^{-1} \sim aba^{-1}$ i $aba^{-1}abb^{-1}a^{-1} \sim aba^{-1}aa^{-1} \sim aba^{-1}$. Aquesta paraula és única, o sigui, no existeix cap altra paraula reduïda dins la classe d'equivalència de $w$ \cite[right={; }, extras={, Lema~6.4}][grillet]\cite[left=,extras={, Teorema~2.1.2}][robinson]. Això fa que el grup lliure $F(X)$ sigui isomorf al grup format pel conjunt de paraules reduïdes sobre $X \cup X^{-1}$ amb l'operació binària consistent en la concatenació de dues paraules reduïdes seguida de la reducció (per exemple, l'aplicació que envia cada paraula reduïda $u$ a la classe d'equivalència $[u]_\sim$ és un isomorfisme entre aquests grups). Estrictament parlant $X$ no està inclòs dins $F(X)$, ara bé, tenim la inclusió natural $\eta$ de $X$ en $F(X)$ tal que $\eta(x) = [x]_\sim$, per a tot $x \in X$. A més, aquesta inclusió es pot estendre per a $X^{-1}$ de la forma $\eta(x^{-1}) = [x^{-1}]_\sim$, per a tot $x \in X$. Per construcció de $F(X)$, això fa que tot element de $F(X)$ es pugui posar com a producte de elements de $\eta(X)$ i els seus inversos, la qual cosa implica el resultat següent: \startmytheorem[thme:generacio-grup-lliure]{\cite[right={; }, extras={, Proposició~6.6}][grillet]\cite[left=,extras={, Proposició~1.6}][cgt]}El grup lliure $F(X)$ està generat per $\eta(X)$. \stopmytheorem Una propietat molt important que compleix el grup lliure, la qual el caracteritza, és la {\em propietat universal}\index{propietat universal}, que podem enunciar com el resultat següent: \startmytheorem[thme:propietat-universal]{\cite[extras={, Teorema~6.7}][grillet]} Sigui $\eta \colon X \to F(X)$ la inclusió natural. Per a tota funció $f$ de $X$ a un grup qualsevol $G$, existeix un únic morfisme $\nu \colon F(X) \to G$ tal que $\nu \circ \eta = f$. \stopmytheorem \startmycorollary[thme:gruplliure-imatge]{\cite[grillet, robinson]} Sigui $G$ un grup generat per un conjunt $X$. Aleshores existeix un homomorfisme exhaustiu de $F(X)$ a $G$, o sigui, tot grup és imatge del grup lliure per a qualque homomorfisme. \stopmycorollary Altres propietats interessants del grup lliure són les seguents: \startmytheorem{\cite[extras={, Teorema~2.1.3}][robinson]} Sigui $G$ un grup i $X$ un subconjunt de $G$. Si tot element $g$ de $G$ es pot escriure de forma única com a $g = x_1^{l_1} \ldots x_r^{l_r}$ amb $r \geq 0$, $x_i \in X$, $l_i \in \integers$ tals que $l_i \neq 0$ i $x_i \neq x_{i+1}$, per a tot $i \in \{0, \ldots, r\}$, aleshores $G$ és lliure de base $X$. \stopmytheorem \startmytheorem{\cite[extras={, Proposició~1.9}][cgt]} Sigui $X$ un subconjunt de $G$ tal que $X \cap X^{-1} = \emptyset$. Aleshores $X$ és una base d'un subgrup lliure de $G$ si, i només so, no hi ha cap producte de la forma $x_1 \ldots x_r$ que sigui trivial, amb $r \geq 1$, $x_i \in X \cup X^{-1}$ i $x_i \neq x_{i+1}^{-1}$, on $i \in \{0, \ldots, r\}$. \stopmytheorem \startmytheorem{\cite[robinson,cgt]}Siguin $X$, $Y$ conjunts qualssevol. Aleshores $F(X) \cong F(Y)$ si, i només si, $\lvert X \rvert = \lvert Y \rvert$. \stopmytheorem Aquest darrer teorema permet definir el {\em rang d'un grup lliure}\index{grup+lliure+rang,} com el cardinal de qualsevol de les seves bases. En aquest sentit, indicarem amb $F_n$\mysymbol{$F_n$} el {\em grup lliure de rang $n$}. Per últim, introduirem notació. Si $w$ és una paraula sobre $X \cup X^{-1}$, la {\em longitud reduïda} de $w$\index{longitud+reduïda d'una paraula}, que indicarem amb $\lvert w \rvert$\mysymbol{$\lvert w \rvert$}, és la longitud de la paraula reduïda de $w$, és a dir, $l(red(w))$. De forma òbvia tenim que, per a totes paraules $u, v$ sobre $X \cup X^{-1}$, $\lvert uv \rvert \leq \lvert u \rvert + \lvert v \rvert$. D'altra banda, si $v, w \in {(X \cup X^{-1})}^*$, aleshores direm que $v$ i $w$ són {\em iguals dins el grup lliure $F(X)$}\index{paraules+iguals dins el grup lliure} si $red(v) = red(w)$ o, equivalentment, si $[v]_\sim = [w]_\sim \in F(X)$. \subsubject{Presentacions de grups} Una presentació d'un grup és una generalització del concepte de taula de productes d'un grup. Donat un grup $G$, la seva taula de productes proporciona informació sobre el resultat del producte entre dos elements qualssevol. Però, en aquesta taula, hi ha valors que són obvis (per exemple, sempre $g g^{-1} = 1$, per a tot $g \in G$) o que es poden deduir d'altres productes (per exemple, si $g^3 = 1$, aleshores $g^2 = g^{-1}$ per a tot $g \in G$). Per tant, hi ha certes relacions {\em importants} entre els elements d'un grup que el determinen. Intuïtivament, per exemple, la relació $a^n = 1$ determina el grup $\integers_n$. Ara bé, així com és important especificar les relacions que governen el grup, també ho és especificar el seus elements, ja que el grup $\integers_n \oplus \integers$ amb $a = (1,0)$ i $b = (0,1)$ també compleix que $a^n = 1$. Per tant, informalment, una presentació no serà res més que un conjunt d'elements, que direm {\em generadors}, i un conjunt de {\em relacions} entre ells. Per definir formalment les presentacions de grups ens fa falta recordar què s'entèn per grup quocient. \startmydefinition Sigui $G$ un grup i $N$ un subgrup normal de $G$. El {\em grup quocient de $G$ per $N$} (també anomenat {\em grup quocient de $G$ mòdul $N$})\index{grup+quocient}, que indicarem amb $G/N$\mysymbol{$G/N$}, és el grup format pels cosets de $N$, $\{g N \mid g \in G\}$, i el producte $\cdot$ definit com \startformula a N \cdot b N = ab N. \stopformula A més, l'aplicació $x \mapsto xN = Nx$ és un morfisme exhaustiu entre $G$ i $G/N$ el nucli del qual és $N$. Aquesta aplicació s'anomena {\em projecció canònica dins el grup quocient $G/N$}\index{grup+quocient+projecció canònica,}.%\cite[grillet] \stopmydefinition D'ara en endavant, si $G$ és un grup i $X$ és un subconjunt de $G$, indicarem amb $\langle \langle X \rangle \rangle$\mysymbol{$\langle \langle X \rangle \rangle$} la {\em clausura normal de $X$ en $G$}\index{clausura normal}, és a dir, el subgrup normal més petit que conté $X$. La clausura normal de $X$ està caracteritzada pel resultat següent: \startmydefinition Donat un element $x$ d'un grup $G$, els {\em conjugats de $x$}\index{conjugat d'un element d'un grup} són els elements de $G$ de la forma $a^{-1} x a$, amb $a \in G$. \stopmydefinition \startmyproposition[thmi:clausuranormal] Donat un grup $G$ i $X$ un subconjunt de $G$, la clausura normal $\langle \langle X \rangle \rangle$ consisteix en tots els productes de conjugats d'elements de $X \cup X^{-1}$, i.e., \startformula \langle \langle X \rangle \rangle = \{a_1^{-1} x_1^{e_1} a_1 \cdots a_r^{-1} x_r^{e_r} a_r \mid a_i \in G, x_i \in X, e_i = \pm 1, r \geq 0, i \in \{1, \ldots, r\}\}. \stopformula \stopmyproposition \startmydemo Indiquem amb $Y$ el conjunt format pels productes de conjugats d'elements de $X \cup X^{-1}$. Hem de veure que $\langle \langle X \rangle \rangle = Y$. Com que $X \subseteq Y$ i $Y$ és normal (ja que, per a tot $g \in G$, $g^{-1} Y g \subseteq Y$), aleshores, per definició de clausura normal, tenim que $\langle \langle X \rangle \rangle \subseteq Y$. D'altra banda, per a tot $x \in X$, tenim que $x^{-1}$, $a^{-1} x a$, $a^{-1} x^{-1} a \in \langle \langle X \rangle \rangle$, perquè $X \subseteq \langle \langle X \rangle \rangle$ i la normalitat de $\langle \langle X \rangle \rangle$. Per tant, els productes d'aquests elements també hi pertanyen, la qual cosa implica que $Y \subseteq \langle \langle X \rangle \rangle$. \stopmydemo \startmydefinition Una {\em presentació {\cal P} amb generadors $X$ i relacions $R$}\index{presentació}, que indicarem amb ${\cal P} = \langle X \mid R \rangle$\mysymbol{${\cal P} = \langle X \mid R \rangle$}, és un parell ordenat $(X, R)$, on $X$ és un conjunt qualsevol i $R \subseteq F(X) \times F(X)$ és una relació binària sobre el grup lliure $F(X)$. Una presentació defineix el grup quocient $F(X)/\langle \langle R_* \rangle \rangle$, que indicarem amb $G({\cal P})$, on \startformula R_* = \{uv^{-1} \mid (u, v) \in R\} \subseteq F(X). \stopformula Dues presentacions ${\cal P}$ i ${\cal P'}$ són {\em equivalents}\index{presentació+equivalent} si els seus grups $G({\cal P})$ i $G({\cal P^\prime})$ són isomorfs. Freqüentment, per abús de llenguatge, s'identifica la presentació ${\cal P}$ i el seu grup $G({\cal P})$. \stopmydefinition Per exemple, si $X = \{a \}$ i $R = \{(a^8,1) \mid a \in X\}$, aleshores $\langle X \mid R \rangle = \integers_8$ (realment el que passa és que el grup que representa aquesta presentació és isomorf a $\integers_8$). Per comoditat, sovint s'abusa de la notació i s'escriuen els parells ordenats de la relació $R$ com una igualtat. Així, l'exemple anterior s'escriuria com $\langle a \mid a^8 = 1\rangle$. A més, moltes vegades les relacions del tipus $u = v$ són escrites en la forma $uv^{-1} = 1$. Per exemple, $\langle a, b \mid ab = ba \rangle = \langle a, b \mid aba^{-1}b^{-1} = 1\rangle$ i $\langle a \mid a^8 = a^3\rangle = \langle a \mid a^5 = 1\rangle$. \startmydefinition Sigui $G$ un grup i ${\cal P} = \langle X \mid R\rangle$ una presentació. Direm que ${\cal P}$ és una {\em presentació de $G$}\index{presentació+d'un grup} si $G({\cal P}) \cong G$. \stopmydefinition \startmydefinition Una presentació ${\cal P} = \langle X \mid R\rangle$ és {\em finita}\index{presentació+finita} quan $X$ i $R$ són ambdós finits. I un grup $G$ és {\em finitament presentable}\index{grup+finitament presentat} si existeix una presentació finita de $G$. \stopmydefinition Notem que, pel Corol·lari \in[thme:gruplliure-imatge], tenim que tot grup és imatge del grup lliure. Per tant, aplicant el Primer Teorema d'Isomorfia, tenim que tot grup és isomorf al grup d'una presentació. D'altra banda, la definició que hem donat és equivalent a una definició basada en relacions d'equivalència (amb una construcció anàloga del grup lliure): si $X$ és un conjunt qualsevol i $R$ és un subconjunt de ${(X \cup X^{-1})}^*$, es pot definir la relació d'equivalència $\approx$ definida de la manera següent: dues paraules $u, v \in {(X \cup X^{-1})}^*$ són tals que $u \approx v$ si, i només si, es pot passar d'una a l'altra amb un nombre finit de passes del tipus següent: \startitemize[n] \item Reducció: l'eliminació d'una ocurrència de $xx^{-1}$, per a qualque $x \in X\cup X^{-1}$, o d'una ocurrència d'una relació $r \in R$. \item Amplificació: l'afegit d'una ocurrència de $xx^{-1}$, per a qualque $x \in X \cup X^{-1}$, o d'una ocurrència d'una relació $r \in R$. \stopitemize Es pot veure que $\approx$ és d'equivalència i que $F(X)/\approx$ és un grup, que coincideix amb $G({\cal P})$ amb ${\cal P} = \langle X \mid R'\rangle$, on $R' = \{(red(r),1) \mid r \in R\} \subseteq F(X) \times F(X)$ \cite[magnus]. Tot seguit, oferim diverses presentacions dels grups més usuals: \startitemize[n] \item El grup lliure $F(X)$ té la presentació $\langle X \mid \emptyset\rangle$. En particular $\integers$ té $\langle a \mid \emptyset \rangle$ com a presentació (recordem que $\integers$ és isomorf al grup lliure $F_1$ de rang $1$). \item El grup $\integers$ (com els altres grups) també té altres presentacions menys {\em naturals}, com, per exemple, $\langle a, b \mid ababa = 1\rangle$ \cite[millerIII]. \item Qualsevol grup finit $G = \{a_1, \ldots, a_n\}$ té una presentació finita: la corresponent a agafar tots els seus elements com a generadors i totes les relacions de la taula de productes de $G$ (aquestes tenen la forma $a_i a_j = a_k$ i n'hi ha $n^2$). \item $\integers_n \cong \langle a \mid a^n = 1 \rangle$. \item $\integers \oplus \integers$ té $\langle a, b \mid ab = ba\rangle$ com a presentació. \item Una presentació de $\integers_n \oplus \integers$ és $\langle a, b \mid a^n = 1\rangle$. \item El grup dièdric $D_n$ d'ordre $2n$ té com a presentació \startformula \langle a, b \mid a^2 = 1, b^n = 1, a^{-1}ba = b^{-1} \rangle. \stopformula \item El grup trivial té com a presentacions \startformula \langle a, b \mid a^{-1} b a = b^2, b^{-1}a b=a^2 \rangle \stopformula i \startformula \langle a, b \mid a^{-1} b^n a = b^{n+1}, a = w \rangle, \stopformula on $w$ és una paraula sobre $\{a, b\}$ tal que la suma dels exponents de $a$ és 0 i $n > 0$ \cite[millerIII, millerIII-article]. Per tant, no és gens senzill saber si una presentació correspon al grup trivial. \item Siguin $m, n \in \integers$. El {\em grup de Baumslag-Solitar}\index{grup+Baumslag-Solitar,}, que indicarem amb $BS(m,n)$\mysymbol{$BS(m,n)$}, és el subgrup del grup $\text{Homeo}(\reals)$ de les funcions homeomorfes de $\reals$ generat per les funcions lineals $a(x) = nx$ i $b(x) = x + m$ \cite[meier]. Aquest grup té com a presentació $\langle a, b\mid ab^m a^{-1}= b^n \rangle$. \stopitemize \indentation Finalment, notem que si ${\cal P} = \langle X \mid R\rangle$ és una presentació, aleshores tenim l'aplicació $\iota \colon X \rightarrow G({\cal P})$ definida com la composició $p \circ \eta$ de la inclusió natural $\eta \colon X \to F(X)$, tal que $\eta(x) = [x]$ per a tot $x \in X \cup X^{-1}$, i la projecció canònica $p \colon F(X) \to F(X)/N$, on $N = \langle \langle R_* \rangle \rangle$, tal que $p([w]) = [w]N$, per a tot $[w] \in F(X)$. Aquesta aplicació es pot estendre a ${(X \cup X^{-1})}^*$ com \startformula \iota(w) = \iota(w_1) \cdots \iota(w_r) \in G({\cal P}), \stopformula per a tota paraula $w = w_1 \ldots w_r$ sobre $X \cup X^{-1}$. Amb aquestes notacions, tenim el resultat següent: \startmytheorem Per a tota presentació {\cal P} = \langle X \mid R \rangle, $\iota(X)$ genera $G({\cal P})$. \stopmytheorem \startmydemo Sigui $g \in G({\cal P})$, aleshores $g = [w]N$ per a alguna paraula $w = w_1 \ldots w_r$ sobre $X \cup X^{-1}$. Per tant, \startformula g = [w_1 \ldots w_r]N = ([w_1]\cdots [w_r])N = [w_1]N \cdots [w_r]N. \stopformula Cada $w_i$ és de $X$ o de $X^{-1}$. Si $w_i = x^{-1}$ per a algun $x \in X$, aleshores $[w_i]N = [x^{-1}]N = [x]^{-1}N = \iota(x)^{-1}$. Per tant, $g$ es pot posar com a producte d'elements de $\iota(X)$ i els seus inversos. \stopmydemo De forma habitual s'identifica $X$ amb $\iota(X)$, denotant els seus elements amb els mateixos símbols i, per tant, de forma freqüent es diu que $X$ {\em genera} $G({\cal P})$. Per exemple, pel grup $\integers \oplus \integers = \langle a, b \mid ab = ba \rangle$, identifiquem $a$ i $b$ amb $\iota(a)=(1,0)$ i $\iota(b) = (0,1)$, respectivament. D'aquesta manera, tenim que $G$ és finitament generat si, i només si, $G$ té una presentació ${\cal P} = \langle X \mid R \rangle$ amb el conjunt de generadors $X$ finit. \subsubject{El problema de la paraula} Sigui $G$ un grup i $X$ un subconjunt de $G$. Aleshores l'aplicació $\pi \colon {(X \cup X^{-1})}^* \to G$\mysymbol{$\pi$} consistent a enviar cada lletra $x \in X$ a l'element corresponent $\pi(x) = x \in G$ es pot estendre de manera natural a totes les paraules de $X \cup X^{-1}$ de la forma següent: \startitemize[1] \item $\pi(x^{-1}) = \pi(x)^{-1}$ per a tot $x \in X$. \item Per a tota paraula $w = w_1 \ldots w_r$ sobre $X \cup X^{-1}$, \startformula \pi(w) = \pi(w_1) \cdots \pi(w_r) \in G. \stopformula \stopitemize Per tant, $\pi$ és un morfisme de monoides entre ${(X \cup X^{-1})}^*$ i $G$. De forma òbvia, si $X$ és un conjunt de generadors de $G$, aleshores $\pi$ és exhaustiva. En particular, si ${\cal P} = \langle X \mid R \rangle$ és una presentació, aleshores, com que $X$ és un conjunt de generadors de $G({\cal P})$, llavors $\pi \colon {(X \cup X^{-1})}^* \to G({\cal P})$ és un morfisme exhaustiu\footnote{Recordem que abusem del llenguatge, identificant $\iota(X)$ i $X$, i que, realment, $\iota(X)$ és el generador de $G({\cal P})$.}. \startmydefinition Sigui $G$ un grup i ${\cal P} = \langle X \mid R\rangle$ és una presentació de $G$. Una paraula $w$ sobre $X \cup X^{-1}$ és {\em nul-homotòpica per ${\cal P}$}\index{paraula+nul-homotòpica per una presentació} si, i només si, $\pi(w) = 1 \in G$. \stopmydefinition \startmydefinition Sigui $G$ un grup i ${\cal P} = \langle X \mid R\rangle$ una presentació de $G$. El {\em problema de la paraula per a {\cal P}}\index{problema de la paraula+per una presentació} consisteix en trobar un algorisme que, donada una paraula $w \in {(X \cup X^{-1})}^*$, decideixi si $\pi(w) = 1$ o $\pi(w) \neq 1$. \stopmydefinition Si $G$ és un grup i ${\cal P}$ i ${\cal P'}$ són presentacions {\em finites} de $G$, aleshores existeix un algorisme que decideixi si una paraula és nul-homotòpica per ${\cal P}$ si, i només si, n'existeix un altre per ${\cal P'}$ \cite[crm]. Per aquest motiu es parla del {\em problema de la paraula de $G$}\index{problema de la paraula+per un grup}, consistent en decidir la resolubilitat del problema de la paraula per a alguna (per a qualsevol) presentació de $G$. Donarem, tot seguit, un criteri per saber si una paraula és nul-homotòpica per una presentació {\em finita} donada. \startmytheorem Sigui ${\cal P} = \langle X \mid R \rangle$ amb $X = \{ x_1, \ldots, x_n \}$ i $R = \{ r_1 = 1, \ldots, r_k = 1\}$ una presentació finita i $w$ una paraula sobre $X \cup X^{-1}$. Llavors tenim que $w$ és nul-homotòpica per ${\cal P}$ si, i només si, $w$ compleix la igualtat següent dins el grup lliure $F(X)$: \startformula w = \prod_{i=1}^N u_i^{-1} r_i^{e_i} u_i, \stopformula per a alguns $N \in \naturalnumbers$, $r_i \in R$, $e_i = \pm 1$ i $u_i \in F(X)$, amb $i \in \{1, \ldots, N\}$. \stopmytheorem \startmydemo Sigui $N = \langle \langle r_1, \ldots, r_k \rangle \rangle \subseteq F(X)$. Si $w \in {(X \cup X^{-1})}^*$, aleshores $\pi(w) = 1 \iff w N = 1 \in G({\cal P}) \iff w \in N \subseteq F(X)$. Per la Proposició \in[thmi:clausuranormal], això vol dir que $w$ és producte de conjugats d'elements de $\{r_1, \ldots, r_k\}$ o dels seus inversos (dins el grup lliure $F(X)$). \stopmydemo Aquest darrer resultat ens dóna una aproximació natural al problema de la paraula per a presentacions finites. Donada una presentació finita ${\cal P} = \langle x_1, \ldots, x_n \mid r_1 = 1, \ldots, r_k = 1\}$, podem enumerar en una llista totes les expressions de la forma \placeformula[eq:llista-conjugats] \startformula u_1^{-1} r_1^{\pm 1} u_1 \cdots u_m^{-1} r_m^{\pm 1} u_m, \stopformula amb $u_i \in F(X)$ i $m \geq 0$. Si una paraula $w$ és tal que $\pi(w) = 1$, aleshores $w$ apareixerà, prest o tard, en aquesta llista. El problema és si $w$ {\em no} satisfà que $\pi(w)=1$: està clar que $w$ no apareixerà en la llista, però no ho podrem saber en un temps finit. Tècnicament, pareix que el conjunt de paraules nul-homotòpiques per ${\cal P}$ és recursivament enumerable però no recursiu (és a dir, el seu complement no és recursivament enumerable). Això fa que el problema de la paraula per una presentació pareixi indecidible. Aquest fet és, precisament, el que va establir Novikov el qual va ser el primer en demostrar, l'any 1955, que existeixen grups finitament presentables amb el problema de la paraula no resoluble \cite[novikov]. Des de la dècada de 1960 fins a mitjans dels anys vuitantes, s'introdueixen diverses tècniques noves que permeten simplificar la demostració original, de 143 pàgines. Es pot trobar una demostració curta de la tesi de Novikov a l'article de Stillwell \cite[stillwell]. D'altra banda, existeixen demostracions senzilles del fet que existeixen grups recursivament presentables (que admeten una presentació ${\cal P} = \langle X \mid R\rangle$ amb $X$ finit i $R$ recursivament enumerable) amb el problema de la paraula irresoluble \cite[extras={, pàg~110}][chiswell]. Hi ha diverses referències sobre el problema de la paraula que es poden consultar per obtenir-ne més informació \cite[magnus,stillwell,millerIIIa2]. Per mor d'aquest resultat negatiu, cal imposar condicions al grup $G$ per a què aquest tengui el problema de la paraula resoluble. Aquest és el cas, per exemple, de la classe de grups {\em residualment finits} \cite[magnus-residualment], tal com mostra el resultat següent: \startmydefinition Un grup $G$ és {\em residualment finit}\index{grup+residualment finit} si, donat $g \neq 1$ en $G$, existeix un subgrup normal $N$ de $G$ tal que $g \not \in N$ i $G/N$ és finit. \stopmydefinition \startmyproposition Sigui $G$ un grup residualment finit i finitament presentat. Aleshores $G$ té el problema de la paraula resoluble. \stopmyproposition \startmydemo Siguin ${\cal P} = \langle X \mid R \rangle$ amb $X = \{ x_1, \ldots, x_n\}$ i $ R = \{ r_1 =1, \ldots, r_k =1\}$ una presentació finita de $G$, $N = \langle \langle r_1, \ldots, r_k\rangle \rangle \subseteq F(X)$ i $w$ una paraula sobre $X \cup X^{-1}$. Hem de veure que existeix un algorisme que decideix si $w$ és nul-homotòpica o, de forma equivalent, si $w$ pertany o no a $N$. Per la discussió anterior, tenim que $N$ és recursivament enumerable, és a dir, que existeix un algorisme que s'atura quan $w \in N$. Només hem de proporcionar, doncs, un algorisme que s'aturi quan $w \not \in N$ (perquè d'aquesta manera $N$ sigui recursiu). Per a qualsevol $m \geq 0$, es poden determinar tots els grups amb exactament $m$ elements mitjançant les seves taules de productes (el nombre de possibles taules de productes amb $m$ elements és finit i, per tant, es pot decidir quines taules tenen l'estructura de grup). Per tant, es poden enumerar tots els grups finits. Donat un grup finit $H$, el conjunt de morfismes \startformula \{\varphi_H \colon F(X) \to H \mid \text{ morfisme }\} \stopformula és finit, ja que, pels teoremes \in[thme:generacio-grup-lliure] i \in[thme:propietat-universal], qualsevol morfisme $\varphi_H$ està determinat per una assignació $(x_1, \ldots, x_n) \mapsto (\varphi_1, \ldots, \varphi_n) \in H^n$ (de fet, això implica que com a màxim hi ha ${\lvert H \rvert}^n$ d'aquests morfirmes). En particular, el conjunt \startformula M_H = \{\varphi_H\colon F(X) \to H \text{ morfisme } \mid \varphi_H(r_i) = 1, \text{ per a tot } i \in \{1, \ldots, k\} \} \stopformula és finit. A més, notem que $M$ no és buit, ja que l'aplicació constant que ho envia tot a l'element trivial hi pertany. Dels dos fets anteriors es desprèn que poden enumerar el conjunt \startformula M = \{(H, \varphi) \mid \varphi \in M_H\}. \stopformula \indentation Si $w \not \in N$, aleshores $\pi(w) \neq 1 \in G({\cal P}) \simeq G$. Per tant, per ser $G$ residualment finit, existeix $L$ subgrup normal de $G({\cal P})$ tal que $\pi(w) \not \in L$ i $G({\cal P})/L$ és finit. Per tant, existeix un grup finit $H$ (igual a $G({\cal P})/L$) i $\varphi_H$ tals que $(H, \varphi_H) \in M$ i $\varphi_H(w) \neq 1$. D'altra banda, si existeix $(H, \varphi_H) \in M$ tal que $\varphi_H(w) \neq 1$, aleshores el nucli $\ker \varphi_H$ conté $N$, per contrucció, però $w \not \in \ker \varphi_H$. Per tant, $w \not \in N$. Per tant, enumerar el conjunt $M$ és un algorisme que s'atura si, i només si, $w \not \in N$, que és el que volíem veure. \stopmydemo Una altra manera d'aconseguir que un grup $G$ tengui el problema de la paraula resoluble és, donada una presentació ${\cal P}$ de $G$, fitar el nombre de productes de conjugats de les relacions de ${\cal P}$ i de les seves inverses que hem de llistar per saber que $w$ no és nul-homotòpica. És a dir, limitar el nombre de comprovacions per determinar que $w$ no pertany a la llista (\in[eq:llista-conjugats]). Això s'aconsegueix mitjançant les funcions de Dehn. La Proposició \in[thmi:WP-Dehn-recursiu] mostra la seva importància. \startmydefinition Sigui $G$ un grup i ${\cal P} = \langle X \mid R \rangle$ una presentació finita de $G$. \startitemize[a] \item Si $w$ és una paraula nul-homotòpica per ${\cal P}$, llavors l'{\em àrea algebraica de $w$ respecte de ${\cal P}$}\index{\`{a}rea+algebraica d'una paraula}\mysymbol{$\text{\tf area}_{a, {\cal P}}(w)$} és \startformula \text{\tf area}_{a, {\cal P}}(w) = \min \{ N \mid w = \prod_{i=1}^N x_i^{-1} r_i x_i \text{ dins } F(X), \text{ amb } x_i \in F(X), r_i \in R^{\pm 1}\}. \stopformula \item Una funció $f\colon \naturalnumbers \rightarrow \naturalnumbers$ és una {\em funció isoperimètrica per a ${\cal P}$}\index{funció isoperimètrica} si, per a tota paraula $w$ nul-homotòpica per ${\cal P}$ tal que $l(w) \leq n$, es té $\text{area}_{a, {\cal P}}(w) \leq f(n)$. El mínim, punt a punt, d'aquestes funcions és la {\em funció de Dehn de ${\cal P}$}\index{funció de Dehn}\mysymbol{$\delta_{{\cal P}}$}, i.e., la funció $\delta_{\cal P}\colon \naturalnumbers \rightarrow \naturalnumbers$ definida per \startformula \delta_{{\cal P}} = \max \{ \text{area}_{a, {\cal P}}(w) \mid \pi(w) = 1, l(w) \leq n\}. \stopformula \stopitemize \stopmydefinition De forma òbvia, si ${\cal P} = \langle X \mid R \rangle$ és una presentació finita de $G$ i $u, v$ són paraules nul-homotòpiques per ${\cal P}$, aleshores la seva concatenació $u v$ és nul-homotòpica per ${\cal P}$ ($\pi$ és un morfisme) i $\text{area}_{a, {\cal P}}(u v) \leq \text{area}_{a, {\cal P}}(u) + \text{area}_{a, {\cal P}}(v)$. \startmydefinition Siguin $f$, $g \colon \naturalnumbers \to \naturalnumbers$. Sigui $\preceq$ la relació definida com $f \preceq g$\mysymbol{$\preceq$} si, i només si, existeix $k > 0$ tal que \startformula f(x) \leq k g(kx + k) + kx + k, \stopformula per a tot $x \in \naturalnumbers$. Indicarem amb $f \simeq g$\mysymbol{$\simeq$} el fet que $f \preceq g$ i $g \preceq f$ simultàniament i, quan això passi, direm que $f$ i $g$ són {\em $\simeq$-equivalents}\index{funcions $\simeq$-equivalents}. \stopmydefinition Si ${\cal P}$ i ${\cal P}'$ són presentacions finites de $G$, $f$ és una funció isoperimètrica per a ${\cal P}$ i $g$ és una funció isoperimètrica per a ${\cal P}$, aleshores $f \simeq g$ \cite[bridson-tutorial]. En particular, si $f$ i $g$ són funcions de Dehn de ${\cal P}$ i ${\cal P}'$, respectivament. És per això que podem parlar, llevat de transformacions lineals, de {\em la} funció de Dehn {\em de $G$}, $\delta_G$, o de les funcions isoperimètriques {\em de $G$}. \startmyproposition[thmi:WP-Dehn-recursiu]{\cite[bridson-tutorial,gersten]} Sigui ${\cal P} = \langle X \mid R \rangle$ una presentació finita de $G$. Aleshores són equivalents: \startitemize[a] \item $G({\cal P})$ té el problema de la paraula resoluble. \item La funció de Dehn de ${\cal P}$ és recursiva. \item ${\cal P}$ admet una funció isoperimètrica recursiva. \stopitemize \stopmyproposition El problema de la paraula va sorgir de forma natural de la Topologia Algebraica a finals de segle XIX i principis de segle XX associat a problemes sobre grups fonamentals de superfícies \cite[stillwell]. Dehn va ser el primer a enunciar aquest problema, l'any 1911 \cite[dehn]. A part d'aquest problema, Dehn en va enunciar dos més que tracten de decidir sobre propietats locals i globals d'un grup. Les propietats locals d'un grup s'ocupen de determinar si certs elements compleixen o no determinades relacions i les propietats globals tracten d'esbrinar les característiques que té el grup sencer com a estructura: \startitemize[1] \item Problema dels conjugats. Donat un grup $G$ i una presentació ${\cal P} = \langle X \mid R \rangle$, deteminar si existeix un algorisme tal que decideixi si dues paraules $u$, $w$ sobre $X \cup X^{-1}$ són tals que $\pi(u)$ és un conjugat de $\pi(w)$. \item Problema de l'isomorfisme. Donats dos grups, trobar un algorisme que determini si són isomorfs o no. \stopitemize El problema de la paraula i dels conjugats són problemes de decissió sobre propietats locals mentre que el problema de l'isomorfisme és un problema sobre una relació global. El problema consistent en deteminar si un grup donat és isomorf al grup trivial és un cas particular del problema de l'isomorfisme, per tant, en principi, pot semblar que pugui tenir solució al contrari del problema general. Aquesta percepció és falsa: aquest problema torna a ser indecidible \cite[extras={, Corol·lari~3.4}][millerIIIa2]. Existeixen molts altres problemes indecidibles en la Teoria de Grups. Es poden consultar diverses fonts per obtenir més informació al respecte \cite[miller-llibre, millerIIIa2,seress,openproblems,sacerdote]. Finalment, hem de notar que els grups finitament presentables amb una sola relació tenen el problema de la paraula resoluble, fet que va establir Magnus, l'any 1932 \cite[cgt, magnus,bridson-tutorial,gersten]. \subject{Eines geomètrics per fer front al problema de la paraula} \subsubject{Grafs de Cayley} En aquesta secció principalment interpretarem un grup donat $G$ com un espai mètric, introduint els grafs de Cayley, que jugaran un paper important al llarg de tot el text. En primer lloc, començarem definint la {\em mètrica de la paraula}. \startmydefinition Sigui $G$ un grup i $X \subseteq G$ un conjunt de generadors {\em finit} de $G$. La {\em mètrica de la paraula de $G$ respecte de $X$}\index{mètrica de la paraula+d'un grup respecte d'un conjunt de generadors} és la distància $d_{G, X} \colon G \times G \rightarrow \naturalnumbers$\mysymbol{$d_{G, X}$} definida com \startformula d_{G, X} (g, h) = \min \{l(w) \mid w \in {(X \cup X^{-1})}^* \text{ tal que } \pi(w) = g^{-1}h \}. \stopformula \stopmydefinition Aquesta mètrica depèn en general del conjunt de generadors de $G$: si $X$ i $X'$ són conjunts de generadors finits de $G$ diferents, aleshores $d_{G, X} \neq d_{G, X'}$. Per exemple si $G = \integers$ i $X = \{1\}$, aleshores tenim que $d_{G, X}(n,m) = \lvert m-n \rvert $ i, en canvi, per a $X' = \{2, 3\}$, tenim que \startformula d_{G, X'}(n,m) = \startcases \NC \lvert s \rvert \MC \text{si } m-n = 3s \NR \NC \lvert s \rvert +1 \MC \text{si } m-n = 3s+1 \NR \NC \lvert s \rvert + 2 \MC \text{si } m-n = 3s +2. \NR \stopcases \stopformula Això és perquè, com que $\integers$ és commutatiu, aleshores el mínim s'aconsegueix amb paraules de la forma $2^l 3^k$, amb $l, k \in \integers$, i, com que $3 \cdot \underbar{2} = 2 \cdot \underbar{3}$ (hem subratllat els generadors de $\integers$), llavors ens podem restringir a paraules tals que $\lvert l \lvert \leq 2$. A més, com que $\underbar{3} \cdot k + \underbar{2} \cdot (-1) = \underbar {3} \cdot (k-2) + \underbar{2} \cdot 2$ i $\underbar{3} \cdot k + \underbar{2} \cdot (-2) = \underbar {3} \cdot (k-2) + \underbar{2} \cdot 1$, llavors, realment, podem restringir-nos a les paraules de la forma $2^l 3^k$ amb $ l \in \{0, 1, 2\}$. D'altra banda, però, aquestes distàncies no difereixen molt: si $X$ i $X'$ són conjunts finits de generadors de $G$ diferents, aleshores $d_{G, X}$ i $d_{G, X'}$ són {\em bilipschitz equivalents}\index{mètriques bilipschitz equivalents} \cite[extras={, Corol·lari~11.3}][meier], és a dir, existeix $k > 0$ tal que, per a tots $g, h \in G$, es compleix \startformula \frac{1}{k} d_{G, X} (g, h) \leq d_{G, X'}(g, h) \leq k d_{G, X} (g, h). \stopformula Per tant, aquestes distàncies són equivalents en el sentit topològic, és a dir, determinen la mateixa topologia. Aleshores és natural veure-les com una sola mètrica. És per aquest motiu que es parla de la {\em mètrica de la paraula de $G$}\index{mètrica de la paraula+d'un grup}, sense fer referència als seus generadors. Indicarem amb $d_G$\mysymbol{$d_G$} o, simplement, amb $d$\mysymbol{$d$} aquesta mètrica. La mètrica de la paraula fa que poguem veure $G$ com un espai mètric. Com que $d$ pren valors enters, aleshores $(G, d)$ és un espai mètric discret, el que pot fer pensar que aquest espai no té una interpretació geomètrica prou interessant. La definició següent mostra que aquest pensament no és del tot cert. \startmydefinition Sigui $G$ un grup i $X$ un conjunt finit de generadors. El {\em graf de Cayley de $G$ respecte de $X$}\index{graf de Cayley}, que indicarem amb $\Gamma_{G, X}$\mysymbol{$\Gamma_{G, X}$}, és el graf dirigit i etiquetat que té com a conjunt de vèrtexs $V(\Gamma_{G, X}) = G$, el conjunt d'arestes \startformula E(\Gamma_{G, X}) = \{ (g, gx) \mid g \in G, x \in X \cup X^{-1}\} \stopformula i cada aresta $(g, gx)$ té l'etiqueta $x$. Quan $G$ i $X$ estiguin clars pel context, simplement ens referirem al {\em graf de Cayley} i l'indicarem amb $\Gamma$\mysymbol{$\Gamma$}. \stopmydefinition Alguns exemples de grafs de Cayley són els següents: \startitemize[n] \item El graf de Cayley del grup trivial (respecte del conjunt de generadors trivial) consta simplement d'un vèrtex amb dues arestes que surten i entren d'aquest vèrtex (Figura {\in[fig:cayley-trivial]a}). De forma habitual, les arestes dels grafs de Cayley de la forma $(g, gx^{-1})$, amb $x \in X$, es dibuixen superposades sobre les arestes $(g, gx)$. Així només es dibuixen el sentit i les arestes de la forma $(g, gx)$, amb $x \in X$. D'ara en endavant representarem els grafs de Cayley d'aquesta manera. La Figura {\in[fig:cayley-trivial]b} mostra el graf de Cayley del grup trivial amb aquesta convenció. \setupcombinations[distance=1.5cm] \placefigure [here] [fig:cayley-trivial] {El graf de Cayley de $G = \{1\}$ respecte de $X = \{1\}$.} {\startcombination[2*1] { \starttikzpicture[scale=1] \filldraw[color=blue!50] (0,0) circle (2pt); \draw (0, -0.3) node {$1$}; \draw plot[domain=0:6.28,smooth,variable=\t] ({sin (\t r)},{1+cos(\t r)}); \draw[decorate,decoration={markings,mark=at position .4 with {\arrow[green!50,line width=1.5mm]{>}}}] plot[domain=0:6.28,smooth,variable=\t] ({sin (\t r)},{1+cos(\t r)}); \draw plot[domain=0:6.28,smooth,variable=\t] ({sin (\t r)},{-1+cos(\t r)}); \draw[decorate,decoration={markings,mark=at position .7 with {\arrow[green!50,line width=1.5mm]{<}}}] plot[domain=0:6.28,smooth,variable=\t] ({sin (\t r)},{-1+cos(\t r)}); \draw (1.3, 1) node {$1$}; \draw (-1.4, -1) node {$1^{-1}$}; \stoptikzpicture} {a} { \starttikzpicture[scale=1] \filldraw[color=blue!50] (0,0) circle (2pt); \draw (0, -0.3) node {$1$}; \draw plot[domain=0:6.28,smooth,variable=\t] ({sin (\t r)},{1+cos(\t r)}); \draw[decorate,decoration={markings,mark=at position .4 with {\arrow[green!50,line width=1.5mm]{>}}}] plot[domain=0:6.28,smooth,variable=\t] ({sin (\t r)},{1+cos(\t r)}); \draw (1.3, 1) node {$1$}; \stoptikzpicture} {b} \stopcombination} \item El graf de Cayley de $\integers_n$ respecte de $X = \{1\}$ és el que es representa a la Figura~\in[fig:graf-Cayley-Zn]. Per comoditat, no etiquetem les arestes en el graf de Cayley (totes les arestes tenen $1$ per etiqueta). \placefigure [here] [fig:graf-Cayley-Zn] {El graf de Cayley de $\integers_n$.} {\startcombination[1*1] { \starttikzpicture[scale=1] \filldraw[color=blue!50] (0,0) circle (2pt); \filldraw[color=blue!50] (1,0) circle (2pt); \filldraw[color=blue!50] (2,0) circle (2pt); \filldraw[color=blue!50] (3,0) circle (2pt); \filldraw[color=blue!50] (5,0) circle (2pt); \filldraw[color=blue!50] (6,0) circle (2pt); \draw (0, -0.3) node {$0$}; \draw (1, -0.3) node {$1$}; \draw (2, -0.3) node {$2$}; \draw (6, -0.3) node {$n$}; \draw (4, 0) node {$\ldots$}; \draw (0,0) -- (1,0) -- (2,0) -- (3,0); \draw (5,0) -- (6,0); \draw[decorate,decoration={markings,mark=at position .6 with {\arrow[green!50,line width=1.5mm]{>}}}] (0,0) -- (1,0); \draw[decorate,decoration={markings,mark=at position .6 with {\arrow[green!50,line width=1.5mm]{>}}}] (1,0) -- (2,0); \draw[decorate,decoration={markings,mark=at position .6 with {\arrow[green!50,line width=1.5mm]{>}}}] (2,0) -- (3,0); \draw[decorate,decoration={markings,mark=at position .6 with {\arrow[green!50,line width=1.5mm]{>}}}] (5,0) -- (6,0); \draw (6,0) arc (0:-180:3cm and 1.5cm); \draw[decorate,decoration={markings,mark=at position .6 with {\arrow[green!50,line width=1.5mm]{>}}}] (6,0) arc (0:-180:3cm and 1.5cm); \stoptikzpicture} { } \stopcombination} \item El graf de Cayley del grup lliure $F_2$ respecte de $\{x, y\}$ és l'arbre infinit 4-ari orientat, tal com mostra la Figura \in[fig:graf-Cayley-F2] (pàgina \at[fig:graf-Cayley-F2]). Per conveniència, les arestes es representen de forma que la seva longitud disminueix, successivament, en la meitat. \placefigure [page] [fig:graf-Cayley-F2] {El graf de Cayley del grup lliure $F_2$. ({\bf No està acabada})} {\startcombination[1*1] { \starttikzpicture[scale=1] % punts \filldraw[color=blue!50] (0,0) circle (2pt); \filldraw[color=blue!50] (4,0) circle (2pt); \filldraw[color=blue!50] (4,2) circle (2pt); \filldraw[color=blue!50] (4,-2) circle (2pt); \filldraw[color=blue!50] (3,2) circle (2pt); \filldraw[color=blue!50] (5,2) circle (2pt); \filldraw[color=blue!50] (3,-2) circle (2pt); \filldraw[color=blue!50] (5,-2) circle (2pt); \filldraw[color=blue!50] (6,0) circle (2pt); \filldraw[color=blue!50] (7,0) circle (2pt); \filldraw[color=blue!50] (4,3) circle (2pt); \filldraw[color=blue!50] (0,4) circle (2pt); \filldraw[color=blue!50] (6,1) circle (2pt); \filldraw[color=blue!50] (6,-1) circle (2pt); \filldraw[color=blue!50] (4,-3) circle (2pt); \filldraw[color=blue!50] (-4,0) circle (2pt); \filldraw[color=blue!50] (0,-4) circle (2pt); \filldraw[color=blue!50] (0,6) circle (2pt); \filldraw[color=blue!50] (0,7) circle (2pt); \filldraw[color=blue!50] (2,4) circle (2pt); \filldraw[color=blue!50] (-2,4) circle (2pt); \filldraw[color=blue!50] (3,4) circle (2pt); \filldraw[color=blue!50] (2,3) circle (2pt); \filldraw[color=blue!50] (2,5) circle (2pt); \filldraw[color=blue!50] (-3,4) circle (2pt); \filldraw[color=blue!50] (-2,5) circle (2pt); \filldraw[color=blue!50] (-2,3) circle (2pt); \filldraw[color=blue!50] (1,6) circle (2pt); \filldraw[color=blue!50] (-1,6) circle (2pt); \filldraw[color=blue!50] (-6,0) circle (2pt); \filldraw[color=blue!50] (-7,0) circle (2pt); \filldraw[color=blue!50] (-6,1) circle (2pt); \filldraw[color=blue!50] (-6,-1) circle (2pt); \filldraw[color=blue!50] (0,-6) circle (2pt); \filldraw[color=blue!50] (0,-7) circle (2pt); \filldraw[color=blue!50] (2,-4) circle (2pt); \filldraw[color=blue!50] (-2,-4) circle (2pt); \filldraw[color=blue!50] (2,-3) circle (2pt); \filldraw[color=blue!50] (2,-5) circle (2pt); \filldraw[color=blue!50] (3,-4) circle (2pt); \filldraw[color=blue!50] (-3,-4) circle (2pt); \filldraw[color=blue!50] (-2,-3) circle (2pt); \filldraw[color=blue!50] (-2,-5) circle (2pt); \filldraw[color=blue!50] (1,-6) circle (2pt); \filldraw[color=blue!50] (-1,-6) circle (2pt); \filldraw[color=blue!50] (-4,2) circle (2pt); \filldraw[color=blue!50] (-4,-2) circle (2pt); \filldraw[color=blue!50] (-3,2) circle (2pt); \filldraw[color=blue!50] (-5,2) circle (2pt); \filldraw[color=blue!50] (-4,3) circle (2pt); \filldraw[color=blue!50] (-3,-2) circle (2pt); \filldraw[color=blue!50] (-5,-2) circle (2pt); \filldraw[color=blue!50] (-4,-3) circle (2pt); % Noms \draw (0.3, 0.3) node {$1$}; \draw (2, 0.3) node {$x$}; \draw (-0.3,2) node {$y$}; % Línies \draw (0,0) -- (4,0) -- (4,2) -- (3,2); \draw (4,2) -- (5,2); \draw (4,0) -- (4,-2) -- (5,-2); \draw (4,-2) -- (3,-2); \draw (4,0) -- (6,0); \draw (6,0) -- (7,0); \draw (6,0) -- (6,1); \draw (6,0) -- (6,-1); \draw (4,2) -- (4,3); \draw (0,0) -- (0,4); \draw (4,-2) -- (4,-3); \draw (0,0) -- (-4,0); \draw (0,0) -- (0,-4); \draw (0,4) -- (2,4); \draw (0,4) -- (-2,4); \draw (0,4) -- (0,6); \draw (0,6) -- (0,7); \draw (2,4) -- (2,5); \draw (2,4) -- (2,3); \draw (2,4) -- (3,4); \draw (-2,4) -- (-3,4); \draw (-2,4) -- (-2,5); \draw (-2,4) -- (-2,3); \draw (0,6) -- (1,6); \draw (-6,0) -- (-4,0); \draw (-6,0) -- (-7,0); \draw (0,6) -- (-1,6); \draw (-6,0) -- (-6,1); \draw (-6,0) -- (-6,-1); \draw (0,-4) -- (2,-4); \draw (0,-4) -- (-2,-4); \draw (0,-4) -- (0,-6); \draw (0,-6) -- (0,-7); \draw (0,-6) -- (1,-6); \draw (0,-6) -- (-1,-6); \draw (2,-4) -- (2,-5); \draw (2,-4) -- (2,-3); \draw (2,-4) -- (3,-4); \draw (-2,-4) -- (-2,-3); \draw (-2,-4) -- (-2,-5); \draw (-2,-4) -- (-3,-4); \draw (-4,2) -- (-3,2); \draw (-4,2) -- (-5,2); \draw (-4,2) -- (-4,3); \draw (-4,0) -- (-4,2); \draw (-4,0) -- (-4,-2); \draw (-4,-2) -- (-5,-2); \draw (-4,-2) -- (-3,-2); \draw (-4,-2) -- (-4,-3); \draw[decorate,decoration={markings,mark=at position .7 with {\arrow[green!50,line width=1mm]{angle 60}}}] (0,0) -- (4,0); \draw[decorate,decoration={markings,mark=at position .7 with {\arrow[green!50,line width=1mm]{angle 60}}}] (4,0) -- (4,2); \draw[decorate,decoration={markings,mark=at position .7 with {\arrow[green!50,line width=1mm]{angle 60}}}] (4,2) -- (5,2); \draw[decorate,decoration={markings,mark=at position .7 with {\arrow[green!50,line width=1mm]{angle 60}}}] (3,2) -- (4,2); \draw[decorate,decoration={markings,mark=at position .7 with {\arrow[green!50,line width=1mm]{angle 60}}}] (4,-2) -- (4,0); \draw[decorate,decoration={markings,mark=at position .7 with {\arrow[green!50,line width=1mm]{angle 60}}}] (4,-2) -- (5,-2); \draw[decorate,decoration={markings,mark=at position .7 with {\arrow[green!50,line width=1mm]{angle 60}}}] (3,-2) -- (4,-2); \draw[decorate,decoration={markings,mark=at position .7 with {\arrow[green!50,line width=1mm]{angle 60}}}] (4,2) -- (4,3); \draw[decorate,decoration={markings,mark=at position .7 with {\arrow[green!50,line width=1mm]{angle 60}}}] (6,0) -- (6,1); \draw[decorate,decoration={markings,mark=at position .7 with {\arrow[green!50,line width=1mm]{angle 60}}}] (6,-1) -- (6,0); \draw[decorate,decoration={markings,mark=at position .7 with {\arrow[green!50,line width=1mm]{angle 60}}}] (6,0) -- (7,0); \draw[decorate,decoration={markings,mark=at position .7 with {\arrow[green!50,line width=1mm]{angle 60}}}] (4,0) -- (6,0); % Com un fractal \draw[->] (5,2) -- (5.5,2); \draw[->] (5,2) -- (5,2.5); \draw[<-] (5,2) -- (5,1.5); \draw[->] (5.5,2) -- (5.75,2); \draw[->] (5.5,2) -- (5.5,2.25); \draw[<-] (5.5,2) -- (5.5,1.75); \draw[->] (5,2.5) -- (5.25,2.5); \draw[<-] (5,2.5) -- (4.75,2.5); \draw[->] (5,2.5) -- (5,2.75); \draw[->] (5,1.5) -- (5.25,1.5); \draw[<-] (5,1.5) -- (5,1.25); \draw[<-] (5,1.5) -- (4.75,1.5); \draw[->] (4,3) -- (4,3.5); \draw[->] (4,3) -- (4.5,3); \draw[<-] (4,3) -- (3.5,3); \draw[->] (4,3.5) -- (4.25,3.5); \draw[->] (4,3.5) -- (4,3.75); \draw[<-] (4,3.5) -- (3.75,3.5); \draw[->] (4.5,3) -- (4.5,3.25); \draw[->] (4.5,3) -- (4.75,3); \draw[<-] (4.5,3) -- (4.5,2.75); \draw[->] (3.5,3) -- (3.5,3.25); \draw[<-] (3.5,3) -- (3.5,2.75); \draw[<-] (3.5,3) -- (3.25,3); \draw[->] (3,2) -- (3,2.5); \draw[<-] (3,2) -- (2.5,2); \draw[<-] (3,2) -- (3,1.5); \draw[->] (3,2.5) -- (3.25,2.5); \draw[->] (3,2.5) -- (3,2.75); \draw[->] (2.75,2.5) -- (3,2.5); \draw[<-] (2.5,2) -- (2.25,2); \draw[->] (2.5,2) -- (2.5,2.25); \draw[<-] (2.5,2) -- (2.5,1.75); \draw[->] (3,1.5) -- (3.25,1.5); \draw[<-] (3,1.5) -- (2.75,1.5); \draw[<-] (3,1.5) -- (3,1.25); % 2n colflori \draw[->] (7,0) -- (7,0.5); \draw[<-] (7.5,0) -- (7,0); \draw[<-] (7,0) -- (7,-0.5); \draw[->] (7,0.5) -- (7.25,0.5); \draw[->] (7,0.5) -- (7,0.75); \draw[<-] (7,0.5) -- (6.75,0.5); \draw[->] (7.5,0) -- (7.75,0); \draw[->] (7.5,0) -- (7.5,0.25); \draw[<-] (7.5,0) -- (7.5,-0.25); \draw[->] (7,-0.5) -- (7.25,-0.5); \draw[<-] (7,-0.5) -- (6.75,-0.5); \draw[<-] (7,-0.5) -- (7,-0.75); \draw[->] (6,1) -- (6,1.5); \draw[->] (6,1) -- (6.5,1); \draw[<-] (6,1) -- (5.5,1); \draw[->] (6,1.5) -- (6.25,1.5); \draw[->] (6,1.5) -- (6,1.75); \draw[<-] (6,1.5) -- (5.75,1.5); \draw[->] (6.5,1) -- (6.75,1); \draw[->] (6.5,1) -- (6.5,1.25); \draw[<-] (6.5,1) -- (6.5,0.75); \draw[->] (5.5,1) -- (5.5,1.25); \draw[<-] (5.5,1) -- (5.5,0.75); \draw[<-] (5.5,1) -- (5.25,1); \draw[<-] (6,-1) -- (6,-1.5); \draw[->] (6,-1) -- (6.5,-1); \draw[<-] (6,-1) -- (5.5,-1); \draw[->] (6,-1.5) -- (6.25,-1.5); \draw[<-] (6,-1.5) -- (5.75,-1.5); \draw[<-] (6,-1.5) -- (6,-1.75); \draw[->] (6.5,-1) -- (6.75,-1); \draw[<-] (6.5,-1) -- (6.5,-1.25); \draw[->] (6.5,-1) -- (6.5,-0.75); \draw[<-] (5.5,-1) -- (5.5,-1.25); \draw[->] (5.5,-1) -- (5.5,-0.75); \draw[<-] (5.5,-1) -- (5.25,-1); \draw[->] (5,-2) -- (5,-1.5); \draw[->] (5,-2) -- (5,-2.5); \draw[->] (5,-2) -- (5.5,-2); \draw[->] (5,-1.5) -- (5.25,-1.5); \draw[->] (5,-1.5) -- (5,-1.25); \draw[<-] (5,-1.5) -- (4.75,-1.5); \stoptikzpicture} { } \stopcombination} \item El grup $\integers \oplus \integers = \langle a, b \mid aba^{-1}b^{-1} = 1\rangle$ respecte de $\{a, b\}$, amb $a = (1,0)$ i $b = (0,1)$, té el graf de Cayley (infinit) que es mostra a la Figura~\in[fig:graf-Cayley-Z2]. \placefigure [here] [fig:graf-Cayley-Z2] {El graf de Cayley de $\integers \oplus \integers$.} {\startcombination[1*1] { \starttikzpicture[scale=1] % punts %\filldraw[color=blue!50] (0,1) circle (2pt); \filldraw[color=blue!50] (1,1) circle (2pt); \filldraw[color=blue!50] (2,1) circle (2pt); \filldraw[color=blue!50] (3,1) circle (2pt); \filldraw[color=blue!50] (4,1) circle (2pt); \filldraw[color=blue!50] (5,1) circle (2pt); %\filldraw[color=blue!50] (6,1) circle (2pt); %\filldraw[color=blue!50] (0,2) circle (2pt); \filldraw[color=blue!50] (1,2) circle (2pt); \filldraw[color=blue!50] (2,2) circle (2pt); \filldraw[color=blue!50] (3,2) circle (2pt); \filldraw[color=blue!50] (4,2) circle (2pt); \filldraw[color=blue!50] (5,2) circle (2pt); %\filldraw[color=blue!50] (6,2) circle (2pt); %\filldraw[color=blue!50] (0,3) circle (2pt); \filldraw[color=blue!50] (1,3) circle (2pt); \filldraw[color=blue!50] (2,3) circle (2pt); \filldraw[color=blue!50] (3,3) circle (2pt); \filldraw[color=blue!50] (4,3) circle (2pt); \filldraw[color=blue!50] (5,3) circle (2pt); %\filldraw[color=blue!50] (6,3) circle (2pt); %\filldraw[color=blue!50] (0,4) circle (2pt); \filldraw[color=blue!50] (1,4) circle (2pt); \filldraw[color=blue!50] (2,4) circle (2pt); \filldraw[color=blue!50] (3,4) circle (2pt); \filldraw[color=blue!50] (4,4) circle (2pt); \filldraw[color=blue!50] (5,4) circle (2pt); %\filldraw[color=blue!50] (6,4) circle (2pt); %\filldraw[color=blue!50] (0,5) circle (2pt); \filldraw[color=blue!50] (1,5) circle (2pt); \filldraw[color=blue!50] (2,5) circle (2pt); \filldraw[color=blue!50] (3,5) circle (2pt); \filldraw[color=blue!50] (4,5) circle (2pt); \filldraw[color=blue!50] (5,5) circle (2pt); %\filldraw[color=blue!50] (6,5) circle (2pt); % Noms \draw (0.4, 1.3) node {$a$}; \draw (0.7, 0.4) node {$b$}; % Línies horitzontals \draw (0,1) -- (1,1) -- (2,1) -- (3,1) -- (4,1) -- (5,1) -- (6,1); \draw (0,2) -- (1,2) -- (2,2) -- (3,2) -- (4,2) -- (5,2) -- (6,2); \draw (0,3) -- (1,3) -- (2,3) -- (3,3) -- (4,3) -- (5,3) -- (6,3); \draw (0,4) -- (1,4) -- (2,4) -- (3,4) -- (4,4) -- (5,4) -- (6,4); \draw (0,5) -- (1,5) -- (2,5) -- (3,5) -- (4,5) -- (5,5) -- (6,5); \draw[decorate,decoration={markings,mark=at position .9 with {\arrow[green!50,line width=1.5mm]{>}}}] (0,1) -- (1,1); \draw[decorate,decoration={markings,mark=at position .9 with {\arrow[green!50,line width=1.5mm]{>}}}] (1,1) -- (2,1); \draw[decorate,decoration={markings,mark=at position .9 with {\arrow[green!50,line width=1.5mm]{>}}}] (2,1) -- (3,1); \draw[decorate,decoration={markings,mark=at position .9 with {\arrow[green!50,line width=1.5mm]{>}}}] (3,1) -- (4,1); \draw[decorate,decoration={markings,mark=at position .9 with {\arrow[green!50,line width=1.5mm]{>}}}] (4,1) -- (5,1); \draw[decorate,decoration={markings,mark=at position .9 with {\arrow[green!50,line width=1.5mm]{>}}}] (5,1) -- (6,1); \draw[decorate,decoration={markings,mark=at position .9 with {\arrow[green!50,line width=1.5mm]{>}}}] (0,2) -- (1,2); \draw[decorate,decoration={markings,mark=at position .9 with {\arrow[green!50,line width=1.5mm]{>}}}] (1,2) -- (2,2); \draw[decorate,decoration={markings,mark=at position .9 with {\arrow[green!50,line width=1.5mm]{>}}}] (2,2) -- (3,2); \draw[decorate,decoration={markings,mark=at position .9 with {\arrow[green!50,line width=1.5mm]{>}}}] (3,2) -- (4,2); \draw[decorate,decoration={markings,mark=at position .9 with {\arrow[green!50,line width=1.5mm]{>}}}] (4,2) -- (5,2); \draw[decorate,decoration={markings,mark=at position .9 with {\arrow[green!50,line width=1.5mm]{>}}}] (5,2) -- (6,2); \draw[decorate,decoration={markings,mark=at position .9 with {\arrow[green!50,line width=1.5mm]{>}}}] (0,3) -- (1,3); \draw[decorate,decoration={markings,mark=at position .9 with {\arrow[green!50,line width=1.5mm]{>}}}] (1,3) -- (2,3); \draw[decorate,decoration={markings,mark=at position .9 with {\arrow[green!50,line width=1.5mm]{>}}}] (2,3) -- (3,3); \draw[decorate,decoration={markings,mark=at position .9 with {\arrow[green!50,line width=1.5mm]{>}}}] (3,3) -- (4,3); \draw[decorate,decoration={markings,mark=at position .9 with {\arrow[green!50,line width=1.5mm]{>}}}] (4,3) -- (5,3); \draw[decorate,decoration={markings,mark=at position .9 with {\arrow[green!50,line width=1.5mm]{>}}}] (5,3) -- (6,3); \draw[decorate,decoration={markings,mark=at position .9 with {\arrow[green!50,line width=1.5mm]{>}}}] (0,4) -- (1,4); \draw[decorate,decoration={markings,mark=at position .9 with {\arrow[green!50,line width=1.5mm]{>}}}] (1,4) -- (2,4); \draw[decorate,decoration={markings,mark=at position .9 with {\arrow[green!50,line width=1.5mm]{>}}}] (2,4) -- (3,4); \draw[decorate,decoration={markings,mark=at position .9 with {\arrow[green!50,line width=1.5mm]{>}}}] (3,4) -- (4,4); \draw[decorate,decoration={markings,mark=at position .9 with {\arrow[green!50,line width=1.5mm]{>}}}] (4,4) -- (5,4); \draw[decorate,decoration={markings,mark=at position .9 with {\arrow[green!50,line width=1.5mm]{>}}}] (5,4) -- (6,4); \draw[decorate,decoration={markings,mark=at position .9 with {\arrow[green!50,line width=1.5mm]{>}}}] (0,5) -- (1,5); \draw[decorate,decoration={markings,mark=at position .9 with {\arrow[green!50,line width=1.5mm]{>}}}] (1,5) -- (2,5); \draw[decorate,decoration={markings,mark=at position .9 with {\arrow[green!50,line width=1.5mm]{>}}}] (2,5) -- (3,5); \draw[decorate,decoration={markings,mark=at position .9 with {\arrow[green!50,line width=1.5mm]{>}}}] (3,5) -- (4,5); \draw[decorate,decoration={markings,mark=at position .9 with {\arrow[green!50,line width=1.5mm]{>}}}] (4,5) -- (5,5); \draw[decorate,decoration={markings,mark=at position .9 with {\arrow[green!50,line width=1.5mm]{>}}}] (5,5) -- (6,5); % Línies verticals \draw (1,0) -- (1,1) -- (1,2) -- (1,3) -- (1,4) -- (1,5) -- (1,6); \draw (2,0) -- (2,1) -- (2,2) -- (2,3) -- (2,4) -- (2,5) -- (2,6); \draw (3,0) -- (3,1) -- (3,2) -- (3,3) -- (3,4) -- (3,5) -- (3,6); \draw (4,0) -- (4,1) -- (4,2) -- (4,3) -- (4,4) -- (4,5) -- (4,6); \draw (5,0) -- (5,1) -- (5,2) -- (5,3) -- (5,4) -- (5,5) -- (5,6); \draw[decorate,decoration={markings,mark=at position .9 with {\arrow[red!50,line width=1mm]{angle 60}}}] (1,0) -- (1,1); \draw[decorate,decoration={markings,mark=at position .9 with {\arrow[red!50,line width=1mm]{angle 60}}}] (1,1) -- (1,2); \draw[decorate,decoration={markings,mark=at position .9 with {\arrow[red!50,line width=1mm]{angle 60}}}] (1,2) -- (1,3); \draw[decorate,decoration={markings,mark=at position .9 with {\arrow[red!50,line width=1mm]{angle 60}}}] (1,3) -- (1,4); \draw[decorate,decoration={markings,mark=at position .9 with {\arrow[red!50,line width=1mm]{angle 60}}}] (1,4) -- (1,5); \draw[decorate,decoration={markings,mark=at position .9 with {\arrow[red!50,line width=1mm]{angle 60}}}] (1,5) -- (1,6); \draw[decorate,decoration={markings,mark=at position .9 with {\arrow[red!50,line width=1mm]{angle 60}}}] (2,0) -- (2,1); \draw[decorate,decoration={markings,mark=at position .9 with {\arrow[red!50,line width=1mm]{angle 60}}}] (2,1) -- (2,2); \draw[decorate,decoration={markings,mark=at position .9 with {\arrow[red!50,line width=1mm]{angle 60}}}] (2,2) -- (2,3); \draw[decorate,decoration={markings,mark=at position .9 with {\arrow[red!50,line width=1mm]{angle 60}}}] (2,3) -- (2,4); \draw[decorate,decoration={markings,mark=at position .9 with {\arrow[red!50,line width=1mm]{angle 60}}}] (2,4) -- (2,5); \draw[decorate,decoration={markings,mark=at position .9 with {\arrow[red!50,line width=1mm]{angle 60}}}] (2,5) -- (2,6); \draw[decorate,decoration={markings,mark=at position .9 with {\arrow[red!50,line width=1mm]{angle 60}}}] (3,0) -- (3,1); \draw[decorate,decoration={markings,mark=at position .9 with {\arrow[red!50,line width=1mm]{angle 60}}}] (3,1) -- (3,2); \draw[decorate,decoration={markings,mark=at position .9 with {\arrow[red!50,line width=1mm]{angle 60}}}] (3,2) -- (3,3); \draw[decorate,decoration={markings,mark=at position .9 with {\arrow[red!50,line width=1mm]{angle 60}}}] (3,3) -- (3,4); \draw[decorate,decoration={markings,mark=at position .9 with {\arrow[red!50,line width=1mm]{angle 60}}}] (3,4) -- (3,5); \draw[decorate,decoration={markings,mark=at position .9 with {\arrow[red!50,line width=1mm]{angle 60}}}] (3,5) -- (3,6); \draw[decorate,decoration={markings,mark=at position .9 with {\arrow[red!50,line width=1mm]{angle 60}}}] (4,0) -- (4,1); \draw[decorate,decoration={markings,mark=at position .9 with {\arrow[red!50,line width=1mm]{angle 60}}}] (4,1) -- (4,2); \draw[decorate,decoration={markings,mark=at position .9 with {\arrow[red!50,line width=1mm]{angle 60}}}] (4,2) -- (4,3); \draw[decorate,decoration={markings,mark=at position .9 with {\arrow[red!50,line width=1mm]{angle 60}}}] (4,3) -- (4,4); \draw[decorate,decoration={markings,mark=at position .9 with {\arrow[red!50,line width=1mm]{angle 60}}}] (4,4) -- (4,5); \draw[decorate,decoration={markings,mark=at position .9 with {\arrow[red!50,line width=1mm]{angle 60}}}] (4,5) -- (4,6); \draw[decorate,decoration={markings,mark=at position .9 with {\arrow[red!50,line width=1mm]{angle 60}}}] (5,0) -- (5,1); \draw[decorate,decoration={markings,mark=at position .9 with {\arrow[red!50,line width=1mm]{angle 60}}}] (5,1) -- (5,2); \draw[decorate,decoration={markings,mark=at position .9 with {\arrow[red!50,line width=1mm]{angle 60}}}] (5,2) -- (5,3); \draw[decorate,decoration={markings,mark=at position .9 with {\arrow[red!50,line width=1mm]{angle 60}}}] (5,3) -- (5,4); \draw[decorate,decoration={markings,mark=at position .9 with {\arrow[red!50,line width=1mm]{angle 60}}}] (5,4) -- (5,5); \draw[decorate,decoration={markings,mark=at position .9 with {\arrow[red!50,line width=1mm]{angle 60}}}] (5,5) -- (5,6); \stoptikzpicture} { } \stopcombination} \item[ex:Z] Els grafs de Cayley de $\integers$ amb conjunt de generadors $\{1\}$ i $\{1, 2\}$ es mostren a les figures \in[fig:graf-Cayley-Z-1] i \in[fig:graf-Cayley-Z-3], respectivament. \placefigure [here] [fig:graf-Cayley-Z-1] {El graf de Cayley de $\integers$ respecte de $\{1\}$.} {\startcombination[1*1] { \starttikzpicture[scale=1] \filldraw[color=blue!50] (0,0) circle (2pt); \filldraw[color=blue!50] (1,0) circle (2pt); \filldraw[color=blue!50] (2,0) circle (2pt); \filldraw[color=blue!50] (3,0) circle (2pt); \filldraw[color=blue!50] (4,0) circle (2pt); \filldraw[color=blue!50] (5,0) circle (2pt); \filldraw[color=blue!50] (6,0) circle (2pt); \draw (3, -0.3) node {$0$}; \draw (7.5, 0) node {$\ldots$}; \draw (-1.5, 0) node {$\ldots$}; \draw (-1,0) -- (0,0) -- (1,0) -- (2,0) -- (3,0) -- (4, 0) -- (5,0) -- (6,0) -- (7,0); \draw[decorate,decoration={markings,mark=at position .6 with {\arrow[green!50,line width=1.5mm]{>}}}] (-1,0) -- (0,0); \draw[decorate,decoration={markings,mark=at position .6 with {\arrow[green!50,line width=1.5mm]{>}}}] (0,0) -- (1,0); \draw[decorate,decoration={markings,mark=at position .6 with {\arrow[green!50,line width=1.5mm]{>}}}] (1,0) -- (2,0); \draw[decorate,decoration={markings,mark=at position .6 with {\arrow[green!50,line width=1.5mm]{>}}}] (2,0) -- (3,0); \draw[decorate,decoration={markings,mark=at position .6 with {\arrow[green!50,line width=1.5mm]{>}}}] (3,0) -- (4,0); \draw[decorate,decoration={markings,mark=at position .6 with {\arrow[green!50,line width=1.5mm]{>}}}] (4,0) -- (5,0); \draw[decorate,decoration={markings,mark=at position .6 with {\arrow[green!50,line width=1.5mm]{>}}}] (5,0) -- (6,0); \draw[decorate,decoration={markings,mark=at position .6 with {\arrow[green!50,line width=1.5mm]{>}}}] (6,0) -- (7,0); \stoptikzpicture} { } \stopcombination} \placefigure [here] [fig:graf-Cayley-Z-3] {El graf de Cayley de $\integers$ respecte de $\{1, 2\}$.} {\startcombination[1*1] { \starttikzpicture[scale=1] \filldraw[color=blue!50] (-2,0) circle (2pt); \filldraw[color=blue!50] (0,0) circle (2pt); \filldraw[color=blue!50] (2,0) circle (2pt); \filldraw[color=blue!50] (4,0) circle (2pt); \filldraw[color=blue!50] (-1,-2) circle (2pt); \filldraw[color=blue!50] (1,-2) circle (2pt); \filldraw[color=blue!50] (3,-2) circle (2pt); \filldraw[color=blue!50] (5,-2) circle (2pt); \filldraw[color=blue!50] (-3,-2) circle (2pt); \filldraw[color=blue!50] (6,0) circle (2pt); \draw (0, 0.3) node {$0$}; \draw (2, 0.3) node {$2$}; \draw (4, 0.3) node {$4$}; \draw (-2, 0.3) node {$-2$}; \draw (-1, -2.3) node {$-1$}; \draw (1, -2.3) node {$1$}; \draw (3, -2.3) node {$3$}; \draw (5, -2.3) node {$5$}; \draw (7, -1) node {$\ldots$}; \draw (-3.5, -1) node {$\ldots$}; \draw (-4, 0) -- (-2,0) -- (0,0) -- (2,0) -- (4,0) -- (6,0); \draw (-3, -2) -- (-1,-2) -- (1, -2) -- (3,-2) -- (5,-2) -- (7,-2); \draw (-2, 0) -- (-1,-2) -- (0, 0) -- (1,-2) -- (2,0) -- (3,-2) -- (4,0) -- (5, -2); \draw (-3,-2) -- (-2,0); \draw (5,-2) -- (6,0); \draw (6,0) -- (7,0); \draw (-3,-2) -- (-4,-2); \draw[decorate,decoration={markings,mark=at position .6 with {\arrow[green!50,line width=1.5mm]{>}}}] (-4,0) -- (-2,0); \draw[decorate,decoration={markings,mark=at position .6 with {\arrow[green!50,line width=1.5mm]{>}}}] (-2,0) -- (0,0); \draw[decorate,decoration={markings,mark=at position .6 with {\arrow[green!50,line width=1.5mm]{>}}}] (0,0) -- (2,0); \draw[decorate,decoration={markings,mark=at position .6 with {\arrow[green!50,line width=1.5mm]{>}}}] (2,0) -- (4,0); \draw[decorate,decoration={markings,mark=at position .6 with {\arrow[green!50,line width=1.5mm]{>}}}] (4,0) -- (6,0); \draw[decorate,decoration={markings,mark=at position .6 with {\arrow[green!50,line width=1.5mm]{>}}}] (-3,-2) -- (-1,-2); \draw[decorate,decoration={markings,mark=at position .6 with {\arrow[green!50,line width=1.5mm]{>}}}] (-1,-2) -- (1,-2); \draw[decorate,decoration={markings,mark=at position .6 with {\arrow[green!50,line width=1.5mm]{>}}}] (1,-2) -- (3,-2); \draw[decorate,decoration={markings,mark=at position .6 with {\arrow[green!50,line width=1.5mm]{>}}}] (3,-2) -- (5,-2); \draw[decorate,decoration={markings,mark=at position .6 with {\arrow[green!50,line width=1.5mm]{>}}}] (5,-2) -- (7,-2); \draw[decorate,decoration={markings,mark=at position .9 with {\arrow[red!50,line width=1mm]{angle 60}}}] (-2,0) -- (-1,-2); \draw[decorate,decoration={markings,mark=at position .9 with {\arrow[red!50,line width=1mm]{angle 60}}}] (-1,-2) -- (0,0); \draw[decorate,decoration={markings,mark=at position .9 with {\arrow[red!50,line width=1mm]{angle 60}}}] (0,0) -- (1,-2); \draw[decorate,decoration={markings,mark=at position .9 with {\arrow[red!50,line width=1mm]{angle 60}}}] (1,-2) -- (2,0); \draw[decorate,decoration={markings,mark=at position .9 with {\arrow[red!50,line width=1mm]{angle 60}}}] (2,0) -- (3,-2); \draw[decorate,decoration={markings,mark=at position .9 with {\arrow[red!50,line width=1mm]{angle 60}}}] (3,-2) -- (4,0); \draw[decorate,decoration={markings,mark=at position .9 with {\arrow[red!50,line width=1mm]{angle 60}}}] (4,0) -- (5,-2); \draw[decorate,decoration={markings,mark=at position .9 with {\arrow[red!50,line width=1mm]{angle 60}}}] (5,-2) -- (6,0); \draw[decorate,decoration={markings,mark=at position .9 with {\arrow[red!50,line width=1mm]{angle 60}}}] (-3,-2) -- (-2,0); \stoptikzpicture} { } \stopcombination} Moltes vegades, per comoditat, el graf de Cayley es representa mitjançant un graf no dirigit, donant-se implícita la orientació de les arestes quan s'explicita el conjunt finit de generadors. Per exemple, a la Figura \in[fig:graf-Cayley-Z-2], es mostra el graf de Cayley (no dirigit) de $\integers$ respecte de $\{2, 3\}$. \placefigure [here] [fig:graf-Cayley-Z-2] {El graf de Cayley de $\integers$ respecte de $\{2, 3\}$.} {\startcombination[1*1] { \starttikzpicture[scale=1] \filldraw[color=blue!50] (0,0) circle (2pt); \filldraw[color=blue!50] (1,0) circle (2pt); \filldraw[color=blue!50] (2,0) circle (2pt); \filldraw[color=blue!50] (3,0) circle (2pt); \filldraw[color=blue!50] (4,0) circle (2pt); \filldraw[color=blue!50] (5,0) circle (2pt); \filldraw[color=blue!50] (6,0) circle (2pt); %\draw (3, -0.3) node {$0$}; %\draw (7.5, 0) node {$\ldots$}; %\draw (-1.5, 0) node {$\ldots$}; \draw (3,0) arc (0:180:1cm); \draw (3,0) arc (180:0:1cm); \draw (4,0) arc (0:180:1cm); \draw (4,0) arc (180:0:1cm); \draw (5,0) arc (0:180:1cm); \draw (5,0) arc (180:0:1cm); \draw (2,0) arc (0:180:1cm); \draw (2,0) arc (180:0:1cm); \draw (1,0) arc (0:180:1cm); \draw (1,0) arc (180:0:1cm); \draw (0,0) arc (0:180:1cm); \draw (0,0) arc (180:0:1cm); \draw (6,0) arc (0:180:1cm); \draw (6,0) arc (180:0:1cm); \draw[loosely dashed] (3,0) arc (0:-180:1.5cm); \draw[loosely dashed] (3,0) arc (-180:0:1.5cm); \draw[loosely dashed] (4,0) arc (0:-180:1.5cm); \draw[loosely dashed] (4,0) arc (-180:0:1.5cm); \draw[loosely dashed] (5,0) arc (0:-180:1.5cm); \draw[loosely dashed] (5,0) arc (-180:0:1.5cm); \draw[loosely dashed] (2,0) arc (0:-180:1.5cm); \draw[loosely dashed] (2,0) arc (-180:0:1.5cm); \draw[loosely dashed] (1,0) arc (0:-180:1.5cm); \draw[loosely dashed] (1,0) arc (-180:0:1.5cm); \draw[loosely dashed] (0,0) arc (0:-180:1.5cm); \draw[loosely dashed] (6,0) arc (-180:0:1.5cm); \stoptikzpicture} { } \stopcombination} \indentation Seguint amb aquest afany de simplificació, molts cops, fins i tot, s'omet el conjunt finit de generadors i es representa un graf de Cayley no dirigit {\em del grup}. En aquest cas, el conjunt finit de generadors es {\em determina} amb aquest graf (realment el graf de Cayley no dirigit representa diversos grafs de Cayley dirigits: per exemple, si ometem el conjunt de generadors, aleshores el graf \in[fig:graf-Cayley-Z-2] és el graf de Cayley (no dirigit) de $\integers$ respecte de $\{2,3\}$, $\{-2,3\}$, $\{2,-3\}$ i de $\{-2,-3\}$). \item El graf que es mostra a la figura \in[fig:graf-Cayley-BS12] és el graf de Cayley del grup de Baumslag-Solitar $BS(1,2) = \langle a, b \mid ab = b^2 a\rangle$ respecte del conjunt de generadors $\{a, b\}$. \placefigure [here] [fig:graf-Cayley-BS12] {El graf de Cayley de $BS(1,2)$.} {\startcombination[1*1] { \starttikzpicture[scale=.5] %\draw (3, -0.3) node {$0$}; %\draw (7.5, 0) node {$\ldots$}; %\draw (-1.5, 0) node {$\ldots$}; % 0, 1.... \foreach \x in {0,1,...,24} { \ifnum \x < 24 \draw[decorate,decoration={markings,mark=at position .5 with {\arrow[green!70]{>}}}] (\x,0) -- (\x +1,0); \draw (\x, 0) -- (\x +1, 0); \fi \filldraw[color=blue!50] (\x,0) circle (2pt); } % 0,2 .... \foreach \x in {0,2,...,24} { \draw (\x, 0) -- (\x, 1); \draw[decorate,decoration={markings,mark=at position .9 with {\arrow[red!70]{angle 60}}}] (\x, 0) -- (\x, 1); \ifnum \x < 24 \draw (\x,1) -- (\x +2,1); \draw[decorate,decoration={markings,mark=at position .5 with {\arrow[green!70]{>}}}] (\x,1) -- (\x +2,1); \fi \filldraw[color=blue!50] (\x,1) circle (2pt); } % Torn a posar els punts sobre les línies \foreach \x in {0,1,...,24} { \filldraw[color=blue!50] (\x,0) circle (2pt); } % 0, 4, .... \foreach \x in {0,4,...,24} { \draw (\x, 1) -- (\x, 3); \draw[decorate,decoration={markings,mark=at position .9 with {\arrow[red!70, line width=1pt]{angle 60}}}] (\x, 1) -- (\x, 3); \ifnum \x < 24 \draw (\x,3) -- (\x +4,3); \draw[decorate,decoration={markings,mark=at position .5 with {\arrow[green!70, line width=1pt]{>}}}] (\x,3) -- (\x +4,3); \fi \filldraw[color=blue!50] (\x,3) circle (2pt); } % Torn a posar els punts sobre les línies \foreach \x in {0,4,...,24} { \filldraw[color=blue!50] (\x,1) circle (2pt); } % 0, 8, ... \foreach \x in {0,8,...,24} { \draw (\x, 3) -- (\x-2, 7); \draw[decorate,decoration={markings,mark=at position .95 with {\arrow[red!70, line width=1.5pt]{angle 60}}}] (\x, 3) -- (\x-2, 7); \ifnum \x < 24 \draw[decorate,decoration={markings,mark=at position .5 with {\arrow[green!70, line width=1.5pt]{>}}}] (\x-2,7) -- (\x +8 -2,7); \draw (\x -2,7) -- (\x +8 -2,7); \fi \filldraw[color=blue!50] (\x -2,7) circle (2pt); } % Les línies de l'altra fulla \foreach \x in {4,12,20} { \draw[dotted] (\x, 3) -- (\x, 8); \draw[decorate,decoration={markings,mark=at position .95 with {\arrow[red!70, line width=1pt]{angle 60}}}] (\x, 3) -- (\x, 8); \ifnum \x < 20 \draw[decorate,decoration={markings,mark=at position .5 with {\arrow[green!70, line width=1.5pt]{>}}}] (\x,8) -- (\x +8,8); \draw (\x, 8) -- (\x + 8, 8); \fi \filldraw[color=blue!50] (\x,8) circle (2pt); } \draw[decorate,decoration={markings,mark=at position .5 with {\arrow[green!70, line width=1.5pt]{>}}}] (-4,8) -- (4,8); \draw[loosely dashed] (-4, 8) -- (-1, 8); \draw (-1, 8) -- (4, 8); \draw (20, 8) -- (22, 8); \draw[loosely dashed] (22, 8) -- (24, 8); % Torn a posar els punts sobre les línies \foreach \x in {0,4,...,24} { \filldraw[color=blue!50] (\x,3) circle (2pt); } \filldraw[color=blue!50] (4,8) circle (2pt); \filldraw[color=blue!50] (20,8) circle (2pt); \stoptikzpicture} { } \stopcombination} \stopitemize \indentation El graf de Cayley $\Gamma_{G, X}$ és arc-connex (ja que $X$ genera $G$) i és localment finit (cada vèrtex té un grau d'incidència finit) perquè $X$ és finit. De fet, cada vèrtex és incident a $2 \lvert X \rvert$ arestes. Si indiquem amb $v_g$ el vèrtex corresponent a $g$, aleshores, per a tot $x \in X$, tenim que $v_g$ és el vèrtex inicial d'una única aresta (la que va de $v_g$ a $v_{g \cdot x}$) i és el vèrtex final d'una sola aresta (la que va de $v_{g \cdot x^{-1}}$ a $v_g$). Amb aquesta notació, $G$ actua per l'esquerra en el conjunt de vèrtexs $V(\Gamma_{G, X})$ mitjançant l'acció $g \cdot v_h \mapsto v_{g\cdot h}$. Recordem que una {\em acció per l'esquerra d'un grup $G$ en un conjunt $X$}\index{acció per l'esquerra d'un grup} és morfisme de grups entre $G$ i el conjunt $Sym(X)$ de bijeccions de $X$ en $X$ o, equivalentment, una aplicació $\cdot \colon G \times X \to X$ tal que \startitemize[1] \item $1 \cdot x = x$, per a tot $x \in X$. \item $ (g h) \cdot x = g \cdot (h \cdot x)$, per a tots $g, h \in G$ i $x \in X$. \stopitemize Si existeix una acció (per l'esquerra) de $G$ en $X$ es diu que $G$ {\em actua} (per l'esquerra) en $X$.\footnote{Pel context es distingeix de forma clara entre l'acció i l'operació del grup, encara que es denotin amb el mateix símbol.} Aquesta acció es pot estendre al conjunt d'arestes $E(\Gamma_{G, X})$ del graf de Cayley de la manera següent: per a cada aresta $(v_h, v_{hx})$ amb etiqueta $x$, $g$ envia aquesta aresta a l'aresta $(v_{gh}, v_{ghx})$ amb etiqueta $x$, i.e., $g \cdot (v_h, v_{hx}) \mapsto (v_{gh}, v_{ghx})$. Per tant, aquesta acció preserva l'orientació de les arestes dirigides dins el graf de Cayley i les seves etiquetes. El graf de Cayley $\Gamma_{G, X}$ indueix una mètrica sobre $G$, que indicarem amb $d_{\Gamma_{G, A}}$\mysymbol{$d_{\Gamma_{G, A}}$} (o amb $d_{\Gamma}$\mysymbol{$d_{\Gamma}$} quan $G$ i $X$ estiguin clars pel context), que correspon a associar a cada parell $(g, h)$ d'elements de $G$ l'ínfim de les longituds dels camins dins $\Gamma_{G, X}$ entre $g$ i $h$. Aquest ínfim realment és un mínim (perquè $\Gamma_{G, X}$ és localment finit) i, a més, és igual a la longitud d'un (de qualsevol) camí geodèsic entre $g$ i $h$. Per un {\em camí geodèsic entre dos vèrtexs $g$, $h$ de $\Gamma_{G, X}$}\index{camí+geodèsic dins el graf de Cayley} entenem un camí de longitud mínima entre $g$ i $h$. Per a tota paraula $w$ sobre $X \cup X^{-1}$, tenim associat un camí $\gamma_w$ dins el graf de Cayley $\Gamma_{G, X}$. Aquest camí comença al vèrtex $v_1$ corresponent a l'element neutre de $G$ i travessa les arestes de $\Gamma_{G, X}$ així com indiquen les lletres de $w$ fins arribar al vèrtex $v_{\pi(w)}$ corresponent a $\pi(w)$. Per exemple, considerem $\integers \oplus \integers$ generat per $\{x, y\}$ amb $x = (1, 0)$ i $y = (0,1)$. La paraula $w = xxy^{-1}x^{-1}yyyxxx$ descriu el camí que es mostra a la Figura \in[fig:path-1]. Amb altres paraules, si $w = w_1 \ldots w_r$, aleshores $\gamma_w$ és el camí determinat pels vèrtexs $v_1$, $v_{\pi(w_1)}$, $v_{\pi(w_1w_2)}$, \ldots, $v_{\pi(w)}$. \placefigure [here] [fig:path-1] {El camí $\gamma_w$ associat a la paraula $w = xxy^{-1}x^{-1}yyyxxx$.} {\startcombination[1*1] { \starttikzpicture[scale=1] % punts %\filldraw[color=blue!50] (0,1) circle (2pt); \filldraw[color=blue!50] (1,1) circle (2pt); \filldraw[color=blue!50] (2,1) circle (2pt); \filldraw[color=blue!50] (3,1) circle (2pt); \filldraw[color=blue!50] (4,1) circle (2pt); \filldraw[color=blue!50] (5,1) circle (2pt); %\filldraw[color=blue!50] (6,1) circle (2pt); %\filldraw[color=blue!50] (0,2) circle (2pt); \filldraw[color=blue!50] (1,2) circle (2pt); \filldraw[color=blue!50] (2,2) circle (2pt); \filldraw[color=blue!50] (3,2) circle (2pt); \filldraw[color=blue!50] (4,2) circle (2pt); \filldraw[color=blue!50] (5,2) circle (2pt); %\filldraw[color=blue!50] (6,2) circle (2pt); %\filldraw[color=blue!50] (0,3) circle (2pt); \filldraw[color=blue!50] (1,3) circle (2pt); \filldraw[color=blue!50] (2,3) circle (2pt); \filldraw[color=blue!50] (3,3) circle (2pt); \filldraw[color=blue!50] (4,3) circle (2pt); \filldraw[color=blue!50] (5,3) circle (2pt); %\filldraw[color=blue!50] (6,3) circle (2pt); %\filldraw[color=blue!50] (0,4) circle (2pt); \filldraw[color=blue!50] (1,4) circle (2pt); \filldraw[color=blue!50] (2,4) circle (2pt); \filldraw[color=blue!50] (3,4) circle (2pt); \filldraw[color=blue!50] (4,4) circle (2pt); \filldraw[color=blue!50] (5,4) circle (2pt); %\filldraw[color=blue!50] (6,4) circle (2pt); %\filldraw[color=blue!50] (0,5) circle (2pt); \filldraw[color=blue!50] (1,5) circle (2pt); \filldraw[color=blue!50] (2,5) circle (2pt); \filldraw[color=blue!50] (3,5) circle (2pt); \filldraw[color=blue!50] (4,5) circle (2pt); \filldraw[color=blue!50] (5,5) circle (2pt); %\filldraw[color=blue!50] (6,5) circle (2pt); \filldraw[color=blue!50] (6,1) circle (2pt); \filldraw[color=blue!50] (6,2) circle (2pt); \filldraw[color=blue!50] (6,3) circle (2pt); \filldraw[color=blue!50] (6,4) circle (2pt); \filldraw[color=blue!50] (6,5) circle (2pt); \filldraw[color=gray!50] (1,3) circle (4pt); \filldraw[color=gray!50] (5,5) circle (4pt); % Noms %\draw (1.5, 1.2) node {$x$}; %\draw (0.7, 1.4) node {$y$}; \draw (0.7, 3) node {$1$}; % Línies horitzontals \draw (1,1) -- (2,1) -- (3,1) -- (4,1) -- (5,1) -- (6,1); \draw (1,2) -- (2,2) -- (3,2) -- (4,2) -- (5,2) -- (6,2); \draw (1,3) -- (2,3) -- (3,3) -- (4,3) -- (5,3) -- (6,3); \draw (1,4) -- (2,4) -- (3,4) -- (4,4) -- (5,4) -- (6,4); \draw (1,5) -- (2,5) -- (3,5) -- (4,5) -- (5,5) -- (6,5); %\draw[decorate,decoration={markings,mark=at position .9 with {\arrow[green!50,line width=1mm]{>}}}] (1,1) -- (2,1); % Línies verticals \draw (1,1) -- (1,2) -- (1,3) -- (1,4) -- (1,5); \draw (2,1) -- (2,2) -- (2,3) -- (2,4) -- (2,5); \draw (3,1) -- (3,2) -- (3,3) -- (3,4) -- (3,5); \draw (4,1) -- (4,2) -- (4,3) -- (4,4) -- (4,5); \draw (5,1) -- (5,2) -- (5,3) -- (5,4) -- (5,5); \draw (6,1) -- (6,2) -- (6,3) -- (6,4) -- (6,5); %\draw[decorate,decoration={markings,mark=at position .9 with {\arrow[red!50,line width=1mm]{angle 60}}}] (1,1) -- (1,2); % Camí \draw[gray!50,line width=2.5pt] (1,3) -- (2,3) -- (3,3) -- (3,2) -- (2,2) -- (2,3) -- (2,4) -- (2,5) -- (3,5) -- (4,5) -- (5,5); \draw[decorate,decoration={markings,mark=at position .9 with {\arrow[gray!70,line width=.5mm]{angle 90}}}] (1,3) -- (2,3); \draw[decorate,decoration={markings,mark=at position .9 with {\arrow[gray!70,line width=.5mm]{angle 90}}}] (2,3) -- (3,3); \draw[decorate,decoration={markings,mark=at position .9 with {\arrow[gray!70,line width=.5mm]{angle 90}}}] (3,3) -- (3,2); \draw[decorate,decoration={markings,mark=at position .9 with {\arrow[gray!70,line width=.5mm]{angle 90}}}] (3,2) -- (2,2); \draw[decorate,decoration={markings,mark=at position .9 with {\arrow[gray!70,line width=.5mm]{angle 90}}}] (2,2) -- (2,3); \draw[decorate,decoration={markings,mark=at position .9 with {\arrow[gray!70,line width=.5mm]{angle 90}}}] (2,3) -- (2,4); \draw[decorate,decoration={markings,mark=at position .9 with {\arrow[gray!70,line width=.5mm]{angle 90}}}] (2,4) -- (2,5); \draw[decorate,decoration={markings,mark=at position .9 with {\arrow[gray!70,line width=.5mm]{angle 90}}}] (2,5) -- (3,5); \draw[decorate,decoration={markings,mark=at position .9 with {\arrow[gray!70,line width=.5mm]{angle 90}}}] (3,5) -- (4,5); \draw[decorate,decoration={markings,mark=at position .9 with {\arrow[gray!70,line width=.5mm]{angle 90}}}] (4,5) -- (5,5); \stoptikzpicture} { } \stopcombination} \noindentation En aquest sentit, $\gamma_w$ té associada l'aplicació $\gamma_w \colon [0, l(w)] \to \Gamma_{G, X}$ tal que $\gamma_w (0) = v_1$, $\gamma_w (l(w)) = v_{\pi(w)}$ i $\gamma_{w}(t) = v_{\pi(w(t))}$. Notem que aquesta aplicació es pot estendre de forma natural al nombres enters mitjançant $\gamma_w (t) = \gamma_w (0)$ si $t < 0$ i $\gamma_w (t) = \gamma_w (l(w))$ si $t > l(w)$. A partir d'ara indentificarem aquesta aplicació i el seu camí corresponent. Inversament, qualsevol camí $\gamma$ des del vèrtex corresponent a la identitat a un vèrtex qualsevol del graf de Cayley té associada una paraula $w$ sobre $X \cup X^{-1}$. Aquesta paraula està formada per les etiquetes de les arestes que segueix, tenint en compte el seu sentit ($s^{-1}$ correspondrà a travessar l'aresta $(g, gx)$ en sentit contrari). Per tant, hi ha una correspondència entre les paraules de ${(X \cup X^{-1})}^*$ i els camins des de $v_1$ dins el graf de Cayley $\Gamma_{G, X}$. Per aquesta raó, a partir d'ara: \startitemize[1] \item Identificarem els elements del grup $G$ amb els vèrtexs del graf de Cayley $\Gamma_{G, X}$. \item Donada una paraula $w \in {(X \cup X^{-1})}^*$, indicarem amb $\gamma(w)$\mysymbol{$\gamma(w)$} el seu {\em camí corresponent}\index{camí+corresponent a una paraula} des d'$1$ ($=v_1$) fins a $\pi(w)$. \stopitemize Seguint amb aquesta notació, donats un element $g \in G$ i una paraula $w \in {(X \cup X^{-1})}^*$, direm que {\em $w$ representa $g$}\index{representació d'un element d'un grup per una paraula} si, i només si $\gamma(w)$ és un camí que va fins a $g$ (des d'$1$), o que $g$ {\em està representat per $w$}. Notem que poden existir moltes paraules que representin el mateix element. \indentation Gràcies als grafs de Cayley, podem veure el producte de $G$ de forma geomètrica: si $g, h \in G$ i $w_g$ i $w_h$ són paraules de ${(X \cup X^{-1})}^*$ que representen $g$ i $h$, respectivament, aleshores $g \cdot h$ està representat per la concatenació $w_g w_h$. Notem que el camí $\gamma(w_g w_h)$ consisteix en anar des d'$1$ fins $g$ seguint el camí $\gamma(w_g)$ i, després, començant des de $g$ envers de $1$, seguir el camí $\gamma(w_h)$. Per tant, el producte d'elements de $G$ correspon a la concatenació de paraules dins ${(X \cup X^{-1})}^*$ i a la composició de camins dins el graf de Cayley $\Gamma_{G, X}$. Continuant amb l'exemple de $\integers \oplus \integers$, si $g = y^2 x^3$ i $h = y^{-3} x$, aleshores $g \cdot h = y^2 x^3y^{-3} x$ tal com es mostra a la Figura \in[fig:path-2]. D'aquesta figura és clar que $g \cdot h$ es pot expressar per $x^4 y^{-1}$. \placefigure [here] [fig:path-2] {La visualització del producte de $g = y^2 x^3$ i $h = y^{-3}x$.} {\startcombination[1*1] { \starttikzpicture[scale=1] % punts %\filldraw[color=blue!50] (0,1) circle (2pt); \filldraw[color=blue!50] (1,1) circle (2pt); \filldraw[color=blue!50] (2,1) circle (2pt); \filldraw[color=blue!50] (3,1) circle (2pt); \filldraw[color=blue!50] (4,1) circle (2pt); \filldraw[color=blue!50] (5,1) circle (2pt); %\filldraw[color=blue!50] (6,1) circle (2pt); %\filldraw[color=blue!50] (0,2) circle (2pt); \filldraw[color=blue!50] (1,2) circle (2pt); \filldraw[color=blue!50] (2,2) circle (2pt); \filldraw[color=blue!50] (3,2) circle (2pt); \filldraw[color=blue!50] (4,2) circle (2pt); \filldraw[color=blue!50] (5,2) circle (2pt); %\filldraw[color=blue!50] (6,2) circle (2pt); %\filldraw[color=blue!50] (0,3) circle (2pt); \filldraw[color=blue!50] (1,3) circle (2pt); \filldraw[color=blue!50] (2,3) circle (2pt); \filldraw[color=blue!50] (3,3) circle (2pt); \filldraw[color=blue!50] (4,3) circle (2pt); \filldraw[color=blue!50] (5,3) circle (2pt); %\filldraw[color=blue!50] (6,3) circle (2pt); %\filldraw[color=blue!50] (0,4) circle (2pt); \filldraw[color=blue!50] (1,4) circle (2pt); \filldraw[color=blue!50] (2,4) circle (2pt); \filldraw[color=blue!50] (3,4) circle (2pt); \filldraw[color=blue!50] (4,4) circle (2pt); \filldraw[color=blue!50] (5,4) circle (2pt); %\filldraw[color=blue!50] (6,4) circle (2pt); %\filldraw[color=blue!50] (0,5) circle (2pt); \filldraw[color=blue!50] (1,5) circle (2pt); \filldraw[color=blue!50] (2,5) circle (2pt); \filldraw[color=blue!50] (3,5) circle (2pt); \filldraw[color=blue!50] (4,5) circle (2pt); \filldraw[color=blue!50] (5,5) circle (2pt); %\filldraw[color=blue!50] (6,5) circle (2pt); \filldraw[color=blue!50] (6,1) circle (2pt); \filldraw[color=blue!50] (6,2) circle (2pt); \filldraw[color=blue!50] (6,3) circle (2pt); \filldraw[color=blue!50] (6,4) circle (2pt); \filldraw[color=blue!50] (6,5) circle (2pt); \filldraw[color=gray!50] (1,3) circle (4pt); \filldraw[color=gray!50] (4,5) circle (4pt); \filldraw[color=gray!70] (5,2) circle (4pt); % Noms \draw (5.3, 2.3) node {$gh$}; \draw (4, 5.3) node {$g$}; \draw (0.7, 3) node {$1$}; % Línies horitzontals \draw (1,1) -- (2,1) -- (3,1) -- (4,1) -- (5,1) -- (6,1); \draw (1,2) -- (2,2) -- (3,2) -- (4,2) -- (5,2) -- (6,2); \draw (1,3) -- (2,3) -- (3,3) -- (4,3) -- (5,3) -- (6,3); \draw (1,4) -- (2,4) -- (3,4) -- (4,4) -- (5,4) -- (6,4); \draw (1,5) -- (2,5) -- (3,5) -- (4,5) -- (5,5) -- (6,5); %\draw[decorate,decoration={markings,mark=at position .9 with {\arrow[green!50,line width=1mm]{>}}}] (1,1) -- (2,1); % Línies verticals \draw (1,1) -- (1,2) -- (1,3) -- (1,4) -- (1,5); \draw (2,1) -- (2,2) -- (2,3) -- (2,4) -- (2,5); \draw (3,1) -- (3,2) -- (3,3) -- (3,4) -- (3,5); \draw (4,1) -- (4,2) -- (4,3) -- (4,4) -- (4,5); \draw (5,1) -- (5,2) -- (5,3) -- (5,4) -- (5,5); \draw (6,1) -- (6,2) -- (6,3) -- (6,4) -- (6,5); %\draw[decorate,decoration={markings,mark=at position .9 with {\arrow[red!50,line width=1mm]{angle 60}}}] (1,1) -- (1,2); % Camí \draw[gray!50,line width=2.5pt] (1,3) -- (1,4) -- (1,5) -- (2,5) -- (3,5) -- (4,5); \draw[decorate,decoration={markings,mark=at position .9 with {\arrow[gray!70,line width=.5mm]{angle 90}}}] (1,3) -- (1,4); \draw[decorate,decoration={markings,mark=at position .9 with {\arrow[gray!70,line width=.5mm]{angle 90}}}] (1,4) -- (1,5); \draw[decorate,decoration={markings,mark=at position .9 with {\arrow[gray!70,line width=.5mm]{angle 90}}}] (1,5) -- (2,5); \draw[decorate,decoration={markings,mark=at position .9 with {\arrow[gray!70,line width=.5mm]{angle 90}}}] (2,5) -- (3,5); \draw[decorate,decoration={markings,mark=at position .9 with {\arrow[gray!70,line width=.5mm]{angle 90}}}] (3,5) -- (4,5); \draw[gray!70,line width=2.5pt] (4,5) -- (4,4) -- (4,3) -- (4,2) -- (5,2); \draw[decorate,decoration={markings,mark=at position .9 with {\arrow[gray!80,line width=.5mm]{angle 90}}}] (4,5) -- (4,4); \draw[decorate,decoration={markings,mark=at position .9 with {\arrow[gray!80,line width=.5mm]{angle 90}}}] (4,4) -- (4,3); \draw[decorate,decoration={markings,mark=at position .9 with {\arrow[gray!80,line width=.5mm]{angle 90}}}] (4,3) -- (4,2); \draw[decorate,decoration={markings,mark=at position .9 with {\arrow[gray!80,line width=.5mm]{angle 90}}}] (4,2) -- (5,2); \stoptikzpicture} { } \stopcombination} \bigskip D'altra banda, podríem dir que la distància $d_\Gamma$ és ``invariant respecte de la multiplicació''\footnote{Tècnicament es diu que l'acció és una isometria per la mètrica $d_\Gamma$ \cite[extras={, pàg.~163}][meier].}. Concretament, tenim el resultat següent: \startmyproposition Dins el graf de Cayley $\Gamma_{G, X}$ es compleix que \startformula d_\Gamma (g, h) = d_\Gamma(a \cdot g, a \cdot h), \stopformula per a tots $a, g, h \in G$. \stopmyproposition \startmydemo Com que l'acció definida anteriorment preserva les orientacions de les arestes i les seves etiquetes, aleshores $d_\Gamma (g, gx) = d_\Gamma (ag , agx)$, per a tots $g, a \in G$ i $x \in X \cup X^{-1}$. Sigui $w = w_1 \ldots w_r \in {(X \cup X^{-1})}^*$ una paraula tal que el camí $\gamma(w)$ partint des de $g$ arriba a $h$ i tal que $d_\Gamma(g, h) = l(w)$, és a dir, una paraula corresponent a un camí geodèsic entre $g$ i $h$ (Figura \in[fig:diagrama-invariant]). \placefigure [here] [fig:diagrama-invariant] {La distància del graf de Cayley és invariant per l'acció $g \cdot h \mapsto gh$.} {\startcombination[1*1] { \starttikzpicture[scale=1] % punts \filldraw[color=blue!50] (1,1) circle (2pt); \filldraw[color=blue!50] (1,2) circle (2pt); \filldraw[color=blue!50] (1,3) circle (2pt); %\filldraw[color=blue!50] (1,4) circle (2pt); \filldraw[color=blue!50] (1,5) circle (2pt); \filldraw[color=blue!50] (1,6) circle (2pt); \filldraw[color=blue!50] (6,1) circle (2pt); \filldraw[color=blue!50] (6,2) circle (2pt); \filldraw[color=blue!50] (6,3) circle (2pt); %\filldraw[color=blue!50] (6,4) circle (2pt); \filldraw[color=blue!50] (6,5) circle (2pt); \filldraw[color=blue!50] (6,6) circle (2pt); % Noms \draw (0.7, 6) node {$h$}; \draw (0.7, 1) node {$g$}; \draw (6.4, 1) node {$ag$}; \draw (6.4, 6) node {$ah$}; \draw (1, 4) node {$\vdots$}; \draw (6, 4) node {$\vdots$}; \draw (1, 2) node[left] {$gw_1$}; \draw (1, 3) node[left] {$gw_1w_2$}; \draw (1, 5) node[left] {$gw_1 \ldots w_{r-1}$}; \draw (6, 2) node[right] {$agw_1$}; \draw (6, 3) node[right] {$agw_1w_2$}; \draw (6, 5) node[right] {$agw_1 \ldots w_{r-1}$}; % Línies horitzontals \draw (1,1) -- (2,1) -- (3,1) -- (4,1) -- (5,1) -- (6,1); \draw (1,2) -- (2,2) -- (3,2) -- (4,2) -- (5,2) -- (6,2); \draw (1,3) -- (2,3) -- (3,3) -- (4,3) -- (5,3) -- (6,3); %\draw (1,4) -- (2,4) -- (3,4) -- (4,4) -- (5,4) -- (6,4); \draw (1,5) -- (2,5) -- (3,5) -- (4,5) -- (5,5) -- (6,5); \draw (1,6) -- (2,6) -- (3,6) -- (4,6) -- (5,6) -- (6,6); % Línies verticals \draw (1,1) -- (1,2) -- (1,3); \draw (1,5) -- (1,6); \draw (6,1) -- (6,2) -- (6,3); \draw (6,5) -- (6,6); % Camí \draw[decorate,decoration={markings,mark=at position .9 with {\arrow[gray!70,line width=.5mm]{angle 90}}}] (1,1) -- (1,2); \draw[decorate,decoration={markings,mark=at position .9 with {\arrow[gray!70,line width=.5mm]{angle 90}}}] (1,2) -- (1,3); \draw[decorate,decoration={markings,mark=at position .9 with {\arrow[gray!70,line width=.5mm]{angle 90}}}] (1,5) -- (1,6); \draw[decorate,decoration={markings,mark=at position .9 with {\arrow[gray!70,line width=.5mm]{angle 90}}}] (6,1) -- (6,2); \draw[decorate,decoration={markings,mark=at position .9 with {\arrow[gray!70,line width=.5mm]{angle 90}}}] (6,2) -- (6,3); \draw[decorate,decoration={markings,mark=at position .9 with {\arrow[gray!70,line width=.5mm]{angle 90}}}] (6,5) -- (6,6); \stoptikzpicture} { } \stopcombination} Llavors tenim que \startformula \startalign \NC d_\Gamma (g, gw_1) \NC = d_\Gamma (ag, agw_1) \NR \NC d_\Gamma (gw_1, gw_1w_2) \NC = d_\Gamma (agw_1, agw_1w_2) \NR \NC ... \NC ... \NR \NC d_\Gamma (gw_1\ldots w_{r-1}, gw_1 \ldots w_r) \NC = d_\Gamma (agw_1\ldots w_{r-1}, agw_1\ldots w_r) \NR \stopalign \stopformula Per tant, $d_\Gamma (g,h) = d_\Gamma (ag, ah)$. \stopmydemo Si suposem que cada aresta del graf de Cayley $\Gamma_{G, X}$ té longitud unitat, aleshores $d_{\Gamma_{G, X}}$ coincideix amb la mètrica de la paraula \cite[extras={, Cap.~4}][delaharpe]. Com a conseqüència òbvia, tenim que la mètrica de la paraula és invariant respecte de la multiplicació. També tenim que, si $X \neq Y$ són conjunts finits de generadors d'un grup $G$, aleshores les mètriques $d_{\Gamma_{G, X}}$ i $d_{\Gamma_{G, Y}}$ són bilipschitz equivalents. Això es pot observar a l'exemple \in[ex:Z] (pàg. \at[ex:Z]). Per tant, a partir d'ara, indicarem amb $d$, indistintament, la mètrica de la paraula $d_{G, X}$ de $G$ respecte de $X$ i la mètrica del graf de Cayley $d_{\Gamma_{G, X}}$. De fet, es pot parlar d'un altre aspecte més general (estrictament més general \cite[dymarz]) que ser bilipschitz equivalent: els grafs de l'exemple esmentat són força {\em semblants} (vist ``des de lluny'' semblen iguals). Es diu que són {\em quasi-isomètrics}: \startmydefinition Siguin $(X, d_X)$ i $(Y, d_Y)$ dos espais mètrics. Una {\em quasi-isometria}\index{quasi-isometria} és una aplicació $\phi \colon X \to Y$ tal que: \startitemize[1] \item Existeix una constant $\lambda \geq 1$ tal que, per a tots $x, x' \in X$, \startformula \frac{1}{\lambda} d_X (x, x') - \lambda \leq d_Y (\phi(x), \phi(x')) \leq \lambda d_X (x, x') + \lambda \stopformula \item Existeix una constant $C \geq 0$ tal que, per a tot $y \in Y$, existeix $x \in X$ tal que $d_Y (\phi(x), y) \leq C$. \stopitemize Dos espais mètrics $(X, d_X)$ i $(Y, d_Y)$ són {\em quasi-isomètrics}\index{espais mètrics+quasi-isomètrics} si existeix una quasi-isometria $\phi \colon X \to Y$ entre ells. En aquest cas, ho indicarem amb $X \sim_{QI} Y$\mysymbol{$\sim_{QI}$}. \stopmydefinition Fàcilment es pot veure que La relació $\sim_{QI}$ és una relació d'equivalència \cite[extras={, Proposició~11.39}][meier]. Tot seguit oferim alguns exemples d'espais quasi-isomètrics: \startitemize[1] \item Qualsevol grup finit (com a espai mètric) és quasi-isomètric a un punt \cite[extras={, pàg.~85}][delaharpe]. \item Si $H$ és un subgrup de $G$ amb índex finit $[G:H]$ i $G$ i $H$ són finitament generats, aleshores $G \sim_{QI} H$ \cite[extras={, Proposició~11.41}][meier]. \item Si $G$ és un grup i $X$, $Y$ són conjunts finits de generadors de $G$, aleshores $G$ respecte de la mètrica de la paraula respecte de $X$ és quasi-isomètric a $G$ respecte de la mètrica de la paraula respecte de $Y$ \cite[extras={, Lemma~11.37}][meier]. Aquest resultat té el seu anàleg per als grafs de Cayley (recordem que $d_{\Gamma_{G, X}} = d_{G, X}$): amb les mateixes condicions, $\Gamma_{G, X} \sim_{QI} \Gamma_{G, Y}$ \cite[extras={, Proposició~4.3}][crm]. \item Per a tot $n \geq 1$, $\integers^n \sim_{QI} \reals^n$, però $\integers^n \not \sim_{QI} \integers^m$, per a tots $n \neq m$.\footnote{Aquests fets són conseqüència de què si un grups $G$ actua ``prou regularment'' en un espai mètric $(X, d_X)$, llavors $G$ és quasi-isomètric a $X$. Hi ha diverses referències al respecte, on es poden consultar els detalls tècnics \cite[crm, delaharpe]. El resultat més destacable és el que es coneix com Teorema Fonamental de la Teoria Geomètrica de Grups (o Teorema de Milnor-\v{S}varc).} %\cite[extras={, Proposició~4.2}][bellaterra] \cite[extras={, Teorema~23}][delaharpe] \stopitemize El bo de les quasi-isometries és que preserven moltes de les propietats geomètriques entre els grafs de Cayley quan els seus grups són quasi-isomètrics. Per tant, les quasi-isometries fan invariants certes propietats entre els grups. En aquest sentit, una propietat ${\cal P}$ és {\em invariant per quasi-isometries}\index{propietat+invariant per quasi-isometries}, si, i només si, si $X \sim_{QI} Y$ i $X$ compleix ${\cal P}$, aleshores $Y$ compleix ${\cal P}$\footnote{En la literatura, de forma habitual es refereix a aquestes propietats com a {\em propietats geomètriques}, però hem preferit no emprar aquest terme per a no donar peu a confusió entre les propietats pròpiament geomètriques dels grups, enteses com aquelles que es poden definir mitjançant l'ús d'objectes geomètrics associats a aquests (com són els grafs de Cayley), i les propietats invariants per quasi-isometries. Per exemple, la propietat ${\cal P} \equiv $ ``Per a qualsevol $g_0 \in G$, si del graf de Cayley $\Gamma_{G, X}$ s'elimina el punt $g_0 \in G$, aleshores $\Gamma_{G, X}\setminus \{g_0\}$ no és arc-connex'' és geomètrica però no invariant per quasi-isometries (${\cal P}$ es compleix amb $X = \{1\}$ però no ho fa amb $X = \{1, 2\}$; figures \in[fig:graf-Cayley-Z-1] i \in[fig:graf-Cayley-Z-3]) \cite[whyte]. Una altra propietat geomètrica que no és invariant per quasi-isometries és la quasi-convexitat de Cannon \cite[meier].}. Existeixen moltes propietats invariants per quasi-isometries \cite[right={; }, extras={, pàg.~114}][delaharpe]\cite[left=,extras={, Teorema~11.46}][meier], com per exemple ser finit, però sens dubte les més destacables són les següents: \startitemize[1] \item Ser finitament presentable és una propietat invariant per quasi-isometries. \item Tenir el problema de la paraula resoluble és una propietat invariant per quasi-isometries. Concretament, tenim els resultats següents: \startmytheorem{\cite[extras={, Teorema~4.7}][crm]} Siguin $G$, $H$ grups, ${\cal P} = \langle X \mid R\rangle$ una presentació finita de $G$ i $Y$ un conjunt finit de generadors de $H$ tals que $\Gamma_{G, X} \sim_{QI} \Gamma_{H, Y}$. Aleshores existeix un conjunt finit de relacions $S$ de $H$ tal que ${\cal Q} = \langle Y \mid S \rangle$ és una presentació finita de $H$, i les funcions de Dehn de les presentacions ${\cal P}$ i ${\cal Q}$ són $\simeq$-equivalents. \stopmytheorem \startmycorollary{\cite[extras={, Corol·lari~4.8}][crm]} Si ${\cal P}$ i ${\cal Q}$ són presentacions finites d'un grup $G$ i el problema de la paraula és resoluble per ${\cal P}$, aleshores també ho és per ${\cal Q}$. \stopmycorollary \stopitemize \subsubsubject{Els grafs de Cayley i el problema de la paraula} A més de capturar certes propietats geomètriques dels grups (via quasi-isometries), un dels aspectes dels grafs de Cayley és la seva connexió directa amb el problema de la paraula. En primer lloc, notem que si $G$ és un grup i ${\cal P} = \langle X \mid R \rangle$ és una presentació de $G$, aleshores una paraula $w \in {(X \cup X^{-1})}^*$ és nul-homotòpica per ${\cal P}$ si, i només si, $\gamma(w)$ és un camí tancat dins el graf de Cayley, és a dir, un camí que comença i acaba a 1 \cite[extras={, Proposició~5.7}][meier]\footnote{Aquesta és una de les raons perquè $w$ es diu nul-homotòpica. Una altra és per la connexió entre paraules nul-homotòpiques i camins nul-homotòpics dins una varietat. Si $M$ és una varietat de Riemann tal que el grup fonamental $\pi_1 (M) = G$, llavors les paraules nul-homotòpiques de $G$ corresponen als camins nul-homotòpics dins la varietat $M$.}. Això fa pensar que si el graf de Cayley de $G$ es pot construir, aleshores el problema de la paraula serà resoluble (perquè podrem determinar els seus camins tancats des d'$1$). Com que la majoria dels grafs de Cayley són infinits, hem d'aclarir què s'entén per un graf de Cayley construïble. \startmydefinition Siguin $G$ un grup, $X$ un conjunt finit de generadors de $G$ i $g \in G$ un element qualsevol. L'{\em esfera de radi $n$ centrada a $g$ dins $\Gamma_{G, X}$}\index{esfera de radi $n$ dins el graf de Cayley}\mysymbol{$S(g,n)$} és el conjunt de vèrtexs \startformula S(g, n) = \{h \in V(\Gamma_{G, X}) \mid d_{\Gamma_{G, X}}(g,h) = n\}. \stopformula D'altra banda, la {\em bolla de radi $n$ centrada a $g$ dins $\Gamma_{G, X}$}\index{bolla de radi $n$ dins el graf de Cayley}\mysymbol{$B(g,n)$} és el conjunt de vèrtexs \startformula B(g, n) = \{h \in V(\Gamma_{G, X}) \mid d_{\Gamma_{G, X}}(g,h) \leq n\}. \stopformula És clar que $B(g, n)$ està format per la unió de $S(g, i)$ per a tots els $i \leq n$. \stopmydefinition \startmynotation Donada una bolla $B(g, n)$ dins el graf de Cayley $\Gamma_{G, X}$, indicarem amb $B_\Gamma (g, n)$\mysymbol{$B_\Gamma (g, n)$} el subgraf que té $B(g, n)$ com a conjunt de vèrtexs i, com a conjunt d'arestes, tots els camins de longitud $\leq n$ que comencen a $g$. \stopmynotation \startmydefinition Un graf de Cayley $\Gamma_{G, X}$ és {\em construïble}\index{graf de Cayley+construïble} si, i només si, podem construir en un temps finit $B_\Gamma(1,n)$ per a tot $n \geq 1$. \stopmydefinition Amb aquestes definicions tenim el teorema següent: \startmytheorem{\cite[extras={, Teorema~5.10}][meier]} Sigui $G$ un grup i $X$ un conjunt finit de generadors de $G$. Llavors $G$ té el problema de la paraula resoluble si, i només si, el graf de Cayley $\Gamma_{G, X}$ és construïble. \stopmytheorem \subsubsubject{Algunes propietats dels grafs de Cayley} He de posar quin és el graf de Cayley del producte lliure $G_1 \ast G_2$ i $\langle X \sqcup Y \mid R \sqcup Q\rangle$ \subsubject{Diagrames de van Kampen} En aquesta secció veurem en què consisteixen els diagrames de van Kampen. De forma general, donada una presentació ${\cal P}$ d'un grup, els diagrames de van Kampen són objectes geomètrics (presentats en forma de diagrama) associats a paraules sobre els generadors de ${\cal P}$. A l'igual que els grafs de Cayley, aquests tenen una estreta relació amb el problema de la paraula. De fet, donen una interpretació topològica\footnote{Realment aquesta interpretació serà geomètrica perquè encastarem els diagrames de van Kampen dins els grafs de Cayley.} de l'àrea algebraica d'una paraula. Hem de dir que hem adaptat la definició original \cite[extras={, pàg.~89}][crm], amb el propòsit de fer-la menys farragosa. Per aquesta raó, necessitam introduir algunes definicions. \startmydefinition Donat un alfabet $A$, una paraula $w$ sobre $A$ és {\em cíclicament reduïda}\index{paraula+cíclicament reduïda} si $w$ no acaba i comença simultàniament amb $a$ i $a^{-1}$, per a algun $a \in A \cup A^{-1}$. \stopmydefinition Per exemple, sobre $A = \{a, b\}$, les paraules $ababa$ i $abb$ són cíclicament reduïdes, però $aba^{-1}$ i $b^{-1}a^{-1}bab$ no ho són. La paraula buida és cíclicament reduïda. Notem que, donada una paraula $w$ sobre un alfabet $A$, sempre existeix una paraula $u$ cíclicament reduïda tal que $w = v^{-1} u v$, amb $v \in A^*$. A més existeix una única paraula tal que la longitud $l(v)$ sigui màxima. Aquesta paraula simplement s'obté per aplicació successiva de la transformació $a^{-1} w a \mapsto w$, per a tot $a \in A \cup A^{-1}$. Indicarem amb $cred(w)$\mysymbol{$cred(w)$} aquesta paraula. En l'exemple anterior, $cred(ababa) = ababa$, $cred(abb) = abb$, $cred(aba^{-1}) = b$, $cred(b^{-1}a^{-1}bab) = b$. \startmydefinition Donat un alfabet $A$, dues paraules $u$, $v \in A^*$ són {\em cíclicament conjugades}\index{paraules+cíclicament conjugades} si, i només si, existeixen paraules $w_1, w_2 \in A^*$ tals que $u = w_1 w_2$ i $v = w_2 w_1$. D'altra banda, donada una paraula $w$, direm que $u$ és un {\em conjugat cíclic de $w$}\index{conjugat cíclic d'una paraula} si $u$ i $w$ són cíclicament conjugades. \stopmydefinition Per exemple, $abbcc$ és un conjugat cíclic de $cc abb$ sobre l'alfabet $A = \{a, b, c\}$. \startmydefinition Sigui ${\cal P} = \langle X \mid R\rangle$, amb $R = \{r_i = 1 \mid i \in I\}$, una presentació. Direm que el conjunt de relacions $R$ és {\em simètric}\index{conjunt de relacions+simètric} si, i només si, per a tota relació $r = 1 \in R$: \startitemize[1] \item $r$ és cíclicament reduïda. \item $r^{-1} = 1$ pertany a $R$. \item Si $s$ és un conjugat cíclic de $r$, aleshore $s = 1 \in R$. \stopitemize \stopmydefinition Donada una presentació {\em finita} ${\cal P} = \langle X \mid R \rangle$, sempre podem trobar una presentació ${\cal P'} = \langle X \mid S\rangle$ finita amb $S$ simètric i tal que $G({\cal P}) = G({\cal P'})$. Aquest fet és el que estableix el resultat següent. \startmyproposition Sigui ${\cal P} = \langle X \mid R \rangle$, amb $R = \{r_1 = 1, \ldots, r_n = 1\}$, una presentació. Aleshores existeix ${\cal P'} = \langle X \mid S \rangle$ amb $S$ simètric tal que $G({\cal P}) = G({\cal P'})$. A més, $S$ és finit i és efectivament calculable. \stopmyproposition \startmydemo En primer lloc, considerem $T = \{cred(r_1), \ldots, cred(r_n)\} \subseteq F(X)$. Tenim que $\langle \langle T \rangle \rangle = \langle \langle r_1, \ldots, r_n \rangle \rangle$ perquè $\langle \langle x^{-1} r_1 x, r_2, \ldots, r_n \rangle \rangle = \langle \langle r_1, r_2, \ldots, r_n\rangle \rangle$, per a tot $x \in X \cup X^{-1}$, i perquè la paraula $cred(r_i)$ s'obté per reducció cíclica successiva. Considerem $S_0$ el conjunt obtingut de la manera següent: \startitemize[1] \item Per a tot $r \in T$: \startitemize[2] \item $r, r^{-1} \in S_0$. \item Si $s$ és un conjugat cíclic de $r$, llavors $s = 1 \in S_0$. \stopitemize \item Tot element de $S_0$ s'ha obtingut per aplicació d'un nombre finit dels passos anteriors. \stopitemize Aleshores considerem el conjunt de relacions $S = \{r = 1 \mid r \in S_0\}$. Aquest conjunt es diu la {\em relació simetritzada de $R$} \cite[cgt]. Com que $S_0 \supseteq T$, llavors $\langle \langle S_0 \rangle \rangle \supseteq \langle \langle T \rangle \rangle$. D'altra banda, perquè $\langle \langle T \rangle \rangle$ és normal, llavors, per a tot $r \in T$, $r^{-1} \in T$ i si $r = r_1 r_2 \in T$, llavors $r_2 r_1 = r_1^{-1} (r_1 r_2) r_1 \in T$. Per tant, $\langle \langle S_0 \rangle \rangle = \langle \langle T \rangle \rangle$. Aleshores $\langle \langle S_0 \rangle \rangle = \langle \langle r_1, \ldots, r_n \rangle \rangle$. Per això tenim que \placeformula[-] \startformula G({\cal P}) = F(X)/\langle \langle r_1, \ldots, r_n \rangle \rangle \cong F(X)/\langle \langle S_0 \rangle \rangle = G({\cal S}) . \stopformula \indentation Finalment notem que $S$ és finit i calculable de forma efectiva, perquè tot aquest procés és finit. \stopmydemo Arran d'aquesta proposició, a partir d'ara sempre suposarem que els conjunts de relacions són simètrics. D'altra banda, per comoditat, també suposarem que els conjunts de generadors són tancats per les seves inverses formals, és a dir, si $G$ és un grup i $X$ és un conjunt de generadors de $G$, aleshores $X^{-1} = X$ (això es pot fer simplement agafant $X = Y \cup Y^{-1}$ amb $Y$ un conjunt de generadors de $G$). Amb aquestes condicions, podem enunciar la definició corresponent als diagrames de van Kampen: \startmydefinition Siguin $G$ un grup, ${\cal P} = \langle X \mid R \rangle $, amb $R = \{r_1 = 1, \ldots, r_n = 1\}$, una presentació finita i $w$ una paraula sobre $X$. Un {\em diagrama de van Kampen ${\cal D}_w$ per a $w$ sobre ${\cal P}$}\index{diagrama+de van Kampen} és un CW-complex de dimensió 2, finit, planar i contractible amb un punt base $\star$ a la frontera (topològica) $\delta({\cal D}_w)$ de ${\cal D}_w$ que satisfà les propietats següents: \startitemize[1] \item Les seves arestes són dirigides i etiquetades amb elements de $X$. \item Les etiquetes de les arestes de $\delta({\cal D}_w)$ llegides des de $\star$ i en el sentit contrari de les agulles del rellotge formen la paraula $w$. \item Per a cada cara, les etiquetes de les arestes que l'envolten llegides consecutivament, en qualsevol ordre i en qualsevol sentit\footnote{És en aquesta condició on usem fortament que $R$ és simètrica. En cas contrari, les etiquetes de cada cara, llegides en el sentit contrari de les agulles del rellotge, serien conjugats cíclics de les paraules de $R$ o de les seves inverses \cite[extras={, pàg.~11}][riley-tesi].}, formen una paraula de $R$, és a dir, són iguals a algun $r_i$. \stopitemize Quan ${\cal P}$ sigui clara pel context, la podrem ometre, i parlarem d'un {\em diagrama de van Kampen per a $w$}. \stopmydefinition \startmydefinition Siguin ${\cal P} = \langle X \mid R \rangle$, $w \in X^*$ una paraula i ${\cal D}$ un diagrama de van Kampen per a $w$ sobre ${\cal P}$. L'{\em àrea combinatòria (o geomètrica) de ${\cal D}$}\index{\`{a}rea+combinatòria d'un diagrama de van Kampen}, que indicarem amb $area_{c, {\cal P}}({\cal D})$\mysymbol{$area_{c, {\cal P}}({\cal D})$}, és el nombre de cares de ${\cal D}$. \stopmydefinition De forma general, no explicitarem el punt base $\star$ de cap diagrama de van Kampen ${\cal D}$ per a $w$ sobre ${\cal P}$ i, per això, direm que ${\cal D}$ {\em té frontera $w$}. Tal com hem anticipat, els diagrames de van Kampen donen una interpretació topològica de l'àrea algebraica d'una paraula. Aquest fet és part del resultat que es coneix com a Lema de van Kampen i que enunciem tot seguit. Es poden trobar diverses referències al respecte \cite[crm, bridson-tutorial]. \startmytheorem{Lema de van Kampen} Siguin $G$ un grup, ${\cal P} = \langle X \mid R\rangle$ una presentació finita de $G$ i $w \in X^*$ una paraula. Aleshores: \startitemize[a] \item $w$ és nul-homotòpica per ${\cal P}$ si, i només si, existeix un diagrama de van Kampen per a $w$ sobre ${\cal P}$. \item Si $w$ és nul-homotòpica, llavors $area_{a, {\cal P}}(w)$ és igual al \startformula \min \{area_{c, {\cal P}}({\cal D}) \mid D \text{ és un diagrama de van Kampen per a } w \text{ sobre } {\cal P} \}. \stopformula \stopitemize \stopmytheorem El segon apartat d'aquest teorema és la raó per la qual es parla, simplement, de l'{\em àrea $area_{\cal P}(w)$ d'una paraula $w$ respecte d'una presentació ${\cal P}$}\index{\`{a}rea+d'una paraula}\mysymbol{$area_{\cal P}(w)$}. Per últim, notem que sempre podem encastar un diagrama de van Kampen ${\cal D}_w$ per a $w$ al graf de Cayley $\Gamma_{G, X}$ amb punt base $\star = 1$. Inversament, .... \subsubject{Quines funcions poden ser funcions de Dehn?} Una de les qüestions fonamentals relativa a les funcions isoperimètriques és la determinació de les funcions que, mòdul $\simeq$, poden ser funcions de Dehn d'un grup. En primer lloc, hem de notar que no totes les funcions $f \colon \naturalnumbers \to \naturalnumbers$ poden ser funcions de Dehn de qualque grup. Aquest fet s'estableix per arguments de cardinalitat: \startitemize[1] \item El conjunt de presentacions finites ${\cal P} = \langle x_1, \ldots, x_n \mid r_1 = 1, \ldots, r_k =1 \rangle$ és numerable, ja que trobar tots els seus elements és equivalent a llistar tots els subconjunts finits de $X \times X^*$ amb $X = \{x_i \mid i \in \naturalnumbers \}$ un conjunt numerable. Llavors també és numerable el conjunt de grups finitament presentables. Per tant, el conjunt \placeformula[-] \startformula \startsplit \NC \{ f\colon \naturalnumbers \to \naturalnumbers \mid \NC \text{existeix $G$ grup finitament presentable i ${\cal P}$ presentació de $G$}\NR \NC \NC \text{tals que $f$ és funció de Dehn de ${\cal P}$}\} \stopsplit \stopformula té cardinal igual a $\lvert \naturalnumbers \rvert$ (cada parell $(G, {\cal P})$, amb $G$ grup finitament presentat i ${\cal P}$ presentació de $G$, té una única funció de Dehn de ${\cal P}$ i tota funció de Dehn ho és d'alguna presentació). Llavors el conjunt de classes, mòdul $\simeq$, de les funcions de Dehn dels grups finitament presentables són formen un conjunt numerable. \item D'altra banda, el conjunt de les funcions $f \colon \naturalnumbers \to \naturalnumbers$ té cardinal $\lvert \naturalnumbers^{\naturalnumbers} \rvert = \lvert \reals \rvert$. \stopitemize Per tant, hi ha {\em moltes} funcions (de fet, en tenim $\lvert \reals \rvert$) que no són funcions de Dehn de qualque grup. \subsubsubject{L'espectre isoperimètric} El problema de determinació de quines són les funcions dels grups finitament presentables s'estudia, principalment, amb l'ajuda del conjunt conegut com {\em espectre isoperimètric}. \startmydefinition Un nombre real $\alpha$ es diu que és un {\em exponent isoperimètric}\index{exponent isoperimètric} si la funció $f(n) = n^{\alpha}$ és una funció de Dehn, per a qualque grup $G$. Indicarem per $IP$ el conjunt de exponents isoperimètrics i l'anomenarem {\em espectre isoperimètric}\index{espectre isoperimètric}. \stopmydefinition \completepublications[criterium=cite] %all per tots \title{Llista de símbols} \placemysymbol \title{Índex alfabètic} \placeindex \completecontent \stoptext