Saturday, May 12, 2012

Cayley graphs and the algebra of groups

Cayley graphs and the algebra of groups:
This is a sequel to my previous blog post “Cayley graphs and the geometry of groups“. In that post, the concept of a Cayley graph of a group {G} was used to place some geometry on that group {G}. In this post, we explore a variant of that theme, in which (fragments of) a Cayley graph on {G} is used to describe the basic algebraic structure of {G}, and in particular on elementary word identities in {G}. Readers who are familiar with either category theory or group homology/cohomology will recognise these concepts lurking not far beneath the surface; we wil remark briefly on these connections later in this post. However, no knowledge of categories or cohomology is needed for the main discussion, which is primarily focused on elementary group theory.
Throughout this post, we fix a single group {G = (G,\cdot)}, which is allowed to be non-abelian and/or infinite. All our graphs will be directed, with loops and multiple edges permitted.
In the previous post, we drew the entire Cayley graph of a group {G}. Here, we will be working much more locally, and will only draw the portions of the Cayley graph that are relevant to the discussion. In this graph, the vertices are elements {x} of the group {G}, and one draws a directed edge from {x} to {xg} labeled (or “coloured”) by the group element {g} for any {x, g \in G}; the graph consisting of all such vertices and edges will be denoted {Cay(G,G)}. Thus, a typical edge in {Cay(G,G)} looks like this:


Figure 1.

One usually does not work with the complete Cayley graph {Cay(G,G)}. It is customary to instead work with smaller Cayley graphs {Cay(G,S)}, in which the edge colours {g} are restricted to a smaller subset of {G}, such as a set of generators for {G}. As we will be working locally, we will in fact work with even smaller fragments of {Cay(G,G)} at a time; in particular, we only use a handful of colours (no more than nine, in fact, for any given diagram), and we will not require these colours to generate the entire group (we do not care if the Cayley graph is connected or not, as this is a global property rather than a local one).
Cayley graphs are left-invariant: for any {a \in G}, the left translation map {x \mapsto ax} is a graph isomorphism. To emphasise this left invariance, we will usually omit the vertex labels, and leave only the coloured directed edge, like so:


Figure 2.

This is analogous to how, in undergraduate mathematics and physics, vectors in Euclidean space are often depicted as arrows of a given magnitude and direction, with the initial and final points of this arrow being of secondary importance only. (Indeed, this depiction of vectors in a vector space can be viewed as an abelian special case of the more general depiction of group elements used in this post.)
Let us define a diagram to be a finite directed graph {H = (V,E)}, with edges coloured by elements of {G}, which has at least one graph homomorphism into the complete Cayley graph {Cay(G,G)} of {G}; thus there exists a map {\phi: V \rightarrow G} (not necessarily injective) with the property that {\phi(w) = \phi(v) g} whenever {(v,w)} is a directed edge in {H} coloured by a group element {g \in G}. Informally, a diagram is a finite subgraph of a Cayley graph with the vertex labels omitted, and with distinct vertices permitted to represent the same group element. Thus, for instance, the single directed edge displayed in Figure 2 is a very simple example of a diagram. An even simpler example of a diagram would be a depiction of the identity element:

Figure 3.

We will however omit the identity loops in our diagrams in order to reduce clutter.
We make the obvious remark that any directed edge in a diagram can be coloured by at most one group element {g}, since {y=xg, y=xh} implies {g=h}. This simple observation provides a way to prove group theoretic identities using diagrams: to show that two group elements {g, h} are equal, it suffices to show that they connect together (with the same orientation) the same pair of vertices in a diagram.

Remark 1 One can also interpret these diagrams as commutative diagrams in a category in which all the objects are copies of {G}, and the morphisms are right-translation maps. However, we will deviate somewhat from the category theoretic way of thinking here by focusing on the geometric arrangement and shape of these diagrams, rather than on their abstract combinatorial description. In particular, we view the arrows more as distorted analogues of vector arrows, than as the abstract arrows appearing in category theory.

Just as vector addition can be expressed via concatenation of arrows, group multiplication can be described by concatenation of directed edges. Indeed, for any {x,g,h \in G}, the vertices {x, xg, xgh} can be connected by the following triangular diagram:

Figure 4.

In a similar spirit, inversion is described by the following diagram:


Figure 5.

We make the pedantic remark though that we do not consider a {g^{-1}} edge to be the reversal of the {g} edge, but rather as a distinct edge that just happens to have the same initial and final endpoints as the reversal of the {g} edge. (This will be of minor importance later, when we start integrating “{1}-forms” on such edges.)
A fundamental operation for us will be that of gluing two diagrams together.

Lemma 1 ((Labeled) gluing) Let {D_1 = (V_1,E_1), D_2 = (V_2,E_2)} be two diagrams of a given group {G}. Suppose that the intersection {D_1 \cap D_2 := (V_1 \cap V_2, E_1 \cap E_2)} of the two diagrams connects all of {V_1 \cap V_2} (i.e. any two elements of {V_1,V_2} are joined by a path in {D_1 \cap D_2}). Then the union {D_1 \cup D_2 := (V_1 \cap V_2, E_1 \cap E_2)} is also a diagram of {G}.

Proof: By hypothesis, we have graph homomorphisms {\phi_1: D_1 \rightarrow Cay(G,G)}, {\phi_2: D_2 \rightarrow Cay(G,G)}. If they agree on {D_1 \cap D_2} then one simply glues together the two homomorphisms to create a new graph homomorphism {\phi: D_1 \cup D_2 \rightarrow Cay(G,G)}. If they do not agree, one can apply a left translation to either {\phi_1} or {\phi_2} to make the two diagrams agree on at least one vertex of {D_1 \cap D_2}; then by the connected nature of {D_1 \cap D_2} we see that they now must agree on all vertices of {D_1 \cap D_2}, and then we can form the glued graph homomorphism as before. \Box
The above lemma required one to specify the label the vertices of {D_1,D_2} (in order to form the intersection {D_1 \cap D_2} and union {D_1 \cup D_2}). However, if one is presented with two diagrams {D_1, D_2} with unlabeled vertices, one can identify some partial set of vertices of {D_1} with a partial set of vertices of {D_2} of matching cardinality. Provided that the subdiagram common to {D_1} and {D_2} after this identification connects all of the common vertices together, we may use the above lemma to create a glued diagram {D}.
For instance, if a diagram {D} contains two of the three edges in the triangular diagram in Figure 4, one can “fill in” the triangle by gluing in the third edge:


Figure 6.

One can use glued diagrams to demonstrate various basic group-theoretic identities. For instance, by gluing together two copies of the triangular diagram in Figure 4 to create the glued diagram


Figure 7.

and then filling in two more triangles, we obtain a tetrahedral diagram that demonstrates the associative law {(gh)k = g(hk)}:


Figure 8.

Similarly, by gluing together two copies of Figure 4 with three copies of Figure 5 in an appropriate order, we can demonstrate the Abel identity {(gh)^{-1} = h^{-1} g^{-1}}:


Figure 9.

In addition to gluing, we will also use the trivial operation of erasing: if {D} is a diagram for a group {G}, then any subgraph of {D} (formed by removing vertices and/or edges) is also a diagram of {G}. This operation is not strictly necessary for our applications, but serves to reduce clutter in the pictures.
If two group elements {g, h} commute, then we obtain a parallelogram as a diagram, exactly as in the vector space case:


Figure 10.

In general, of course, two arbitrary group elements {g,h} will fail to commute, and so this parallelogram is no longer available. However, various substitutes for this diagram exist. For instance, if we introduce the conjugate {g^h := h^{-1} g h} of one group element {g} by another, then we have the following slightly distorted parallelogram:


Figure 11.

By appropriate gluing and filling, this can be used to demonstrate the homomorphism properties of a conjugation map {g \mapsto g^h}:


Figure 12.



Figure 13.

Another way to replace the parallelogram in Figure 10 is to introduce the commutator {[g,h] := g^{-1}h^{-1}gh} of two elements, in which case we can perturb the parallelogram into a pentagon:


Figure 14.

We will tend to depict commutator edges as being somewhat shorter than the edges generating that commutator, reflecting a “perturbative” or “nilpotent” philosophy. (Of course, to fully reflect a nilpotent perspective, one should orient commutator edges in a different dimension from their generating edges, but of course the diagrams drawn here do not have enough dimensions to display this perspective easily.) We will also be adopting a “Lie” perspective of interpreting groups as behaving like perturbations of vector spaces, in particular by trying to draw all edges of the same colour as being approximately (though not perfectly) parallel to each other (and with approximately the same length).
Gluing the above pentagon with the conjugation parallelogram and erasing some edges, we discover a “commutator-conjugate” triangle, describing the basic identity {g^h = g [g,h]}:


Figure 15.

Other gluings can also give the basic relations between commutators and conjugates. For instance, by gluing the pentagon in Figure 14 with its reflection, we see that {[g,h] = [h,g]^{-1}}. The following diagram, obtained by gluing together copies of Figures 11 and 15, demonstrates that {[h,g^{-1}] = [g,h]^{g^{-1}}},


Figure 16.

while this figure demonstrates that {[g,hk] = [g,k] [g,h]^k}:


Figure 17.

Now we turn to a more sophisticated identity, the Hall-Witt identity

\displaystyle [[g,h],k^g] [[k,g],h^k] [[h,k],g^h] = 1,

which is the fully noncommutative version of the more well-known Jacobi identity for Lie algebras.
The full diagram for the Hall-Witt identity resembles a slightly truncated parallelopiped. Drawing this truncated paralleopiped in full would result in a rather complicated looking diagram, so I will instead display three components of this diagram separately, and leave it to the reader to mentally glue these three components back to form the full parallelopiped. The first component of the diagram is formed by gluing together three pentagons from Figure 14, and looks like this:

Figure 18.

This should be thought of as the “back” of the truncated parallelopiped needed to establish the Hall-Witt identity.
While it is not needed for proving the Hall-Witt identity, we also observe for future reference that we may also glue in some distorted parallelograms and obtain a slightly more complicated diagram:


Figure 19.

To form the second component, let us now erase all interior components of Figure 18 or Figure 19:


Figure 20.

Then we fill in three distorted parallelograms:


Figure 21.

This is the second component, and is the “front” of the truncated praallelopiped, minus the portions exposed by the truncation.
Finally, we turn to the third component. We begin by erasing the outer edges from the second component in Figure 21:


Figure 22.

We glue in three copies of the commutator-conjugate triangle from Figure 15:


Figure 23.

But now we observe that we can fill in three pentagons, and obtain a small triangle with edges {[[g,h],k^g] [[k,g],h^k] [[h,k],g^h]}:


Figure 24.

Erasing everything except this triangle gives the Hall-Witt identity. Alternatively, one can glue together Figures 18, 21, and 24 to obtain a truncated parallelopiped which one can view as a geometric representation of the proof of the Hall-Witt identity.
Among other things, I found these diagrams to be useful to visualise group cohomology; I give a simple example of this below, developing an analogue of the Hall-Witt identity for {2}-cocycles.


— 1. A Hall-Witt identity for {2}-cocycles —

It is instructive to start interpreting the basic building blocks of group homology and group cohomology in terms of these diagrams; among other things, this interpretation highlights the close relationship between group cohomology and other types of cohomology, such as simplicial cohomology and de Rham cohomology. We will not do so systematically here, but present just a small fragment of group cohomology in this setting, to give the flavour of things.
To warm up, let’s begin with the easy theory of {1}-cohomology. Fix some coefficient ring {U} (e.g. the integers {{\bf Z}}, the reals {{\bf R}}, or a cyclic group such as {{\bf Z}/2{\bf Z}}; for the elementary cohomology topics we will be presenting here, the exact choice of the coefficient ring {U} will not be important). A {1}-cochain is just a map {f: G \rightarrow U}. Using our diagram perspective, we can interpret a {1}-cochain in a “de Rham” way as a “{1}-form” that assigns the element {\int_e f := f(g)} of {U} to any oriented edge {e} in a diagram that has colour {g}. By definition, we also define the integral {\int_{-e} f} along the reversal of an oriented edge {e} in a diagram by {\int_{-e} f := - \int_e f}. Note though that the integral along a {g^{-1}} edge is not necessarily the negation of the integral along a {g} edge, since we may have {f(g^{-1}) \neq -f(g)}. This explains the previous remark that we do not view a {g^{-1}} edge as the reversal of a {g} edge. Similarly, since {f(1)} need not equal {0}, the integral of {f} on a loop need not be non-zero. Thus one has to take a little bit of care with the analogy between group cohomology and de Rham cohomology. However, if the {1}-chain is normalised in the sense that {f(1)=0} and {f(g^{-1})=-f(g)} (which is for instance the case with the {1}-cocycles discussed below), then the analogy becomes more accurate.
Given any oriented path {\gamma} in a diagram consisting of a sequence {e_1,\ldots,e_k} of edges (which either are aligned with, or have the opposite orientation from, the edge in the diagram), we can then define the “ line integral” {\int_\gamma f} of a {1}-cochain {f} as the sum of the individual edge integrals {\int_{e_1} f, \ldots, \int_{e_k} f}. A key point here is that of translation invariance; if two paths {\gamma, \gamma'} are translates of each other, in the sense that they have the same length and the colours of their edges match, then they have the same line integral with respect to {f}.

Remark 2 One can of course more generally integrate {1}-cocycles against {1}-chains, namely formal linear combinations of oriented edges with coefficients in {U}, which is the starting point for the diagrammatic interpretation of group homology, but we will not use this formalism here.

A {1}-cocycle is a {1}-cochain {f: G \rightarrow U} which obeys the identity

\displaystyle f(g) - f(gh) + f(h) = 0

for all {g,h \in G}. Of course, this equation is nothing more than the assertion that {f} is a group homomorphism from {G} to {U}; but let us pretend that we are unaware of this interpretation of {1}-cocycles, and instead interpret the {1}-cocycle condition diagramatically, as the fact that the line integral around any triangle (Figure 4) vanishes. Because any closed loop in a diagram can be triangulated (possibly after first filling in some more edges), we see more generally that a {1}-cocycle is nothing more than a {1}-cochain which is closed in the sense that its integral on any closed loop is zero. On the other hand, we also have translation invariance of the {1}-cocycle, which leads to some additional cancellations. For instance, by integrating a {1}-cocycle against the pentagon in Figure 14, the contribution of the edges of matching colour cancel each other out, leaving one with the conclusion that

\displaystyle f([g,h]) = 0 \ \ \ \ \ (1)


for all {g,h} and any {1}-cocycle {f}. Of course, this fact was already obvious from the group homomorphism interpretation, but the point is that it can also be observed “geometrically” by inspection of a relevant diagram. Similarly, from Figure 11 we have {f(g) = f(g^h)} for any {g,h \in G} and any {1}-cocycle {f}.
Next, we define a {2}-cochain to be a function {\rho: G \times G \rightarrow U}. Just as {1}-cochains can be viewed as “{1}-forms” that can be integrated on oriented edges and thus oriented paths, we can view {2}-cochains as “{2}-forms” that can be integrated on oriented triangles and thus triangulated surfaces, though we make the technical restriction that our triangles must be of the form in Figure 4, i.e. not all arrows are oriented in the same direction. We can then interpret {\rho(g,h)} as the integral {\int_\Delta \rho} of {\rho} on the triangle in Figure 4, endowed with the clockwise orientation; reversing the orientation of this triangle leads to a negation of the integral. One can then integrate {\rho} on any oriented triangulated surface (or, more generally, {2}-chains, as mentioned previously) in a diagram in the obvious fashion, provided that in each triangle, the arrows are not all oriented in the same direction.
A {2}-cocycle is a {2}-cochain which obeys the identity

\displaystyle \rho(g,h) - \rho(g,hk) + \rho(gh,k) - \rho(h,k) = 0 \ \ \ \ \ (2)


for all {g,h,k \in G}. As we will recall later, {2}-cocycles can be viewed as coordinatisations of central {U}-extensions of {G}, but we will again pretend that we are unaware of this interpretation of {2}-cocycles, and instead take a diagrammatic interpretation (which has the advantage over the central extension interpretation that it extends much more readily to higher orders of cohomology than {2}-cohomology). The cocycle identity (2) is then asserting that the integral of {\rho} on the tetrahedron in Figure 8 (or, in fact, any other tetrahedron) vanishes. Because any closed oriented triangulated {2}-surface on a diagram can be broken up into tetrahedra (again after filling in some edges if necessary), we conclude that a {2}-cocycle is nothing more than a {2}-cochain which is closed in the sense that its integral on any closed triangulated {2}-surface vanishes. Among other things, this now allows one to define the integral {\int_S \rho} of a {2}-cocycle on any oriented surface {S} (not necessarily closed or triangulated) which is bordered by some closed loop {\gamma} in a diagram, by replacing {S} by some triangulated oriented surface with the same oriented boundary {\gamma} as {S}. For instance, we can integrate a {2}-cocycle {\rho} on the pentagon {P} in Figure 14 with the clockwise orientation to obtain an element {\int_P \rho} of {\rho}; by selecting a suitable triangulation of this pentagon, this integral can be expressed explicitly as

\displaystyle \int_P \rho = \rho(h,g) + \rho(hg, [g,h]) - \rho(g,h) \ \ \ \ \ (3)


but we can choose other triangulations to obtain other representations of the same integral, e.g.

\displaystyle \int_P \rho = - \rho(g, g^{-1} h) + \rho(g^{-1}, h) + \rho(h^g, [g,h]).

Again, a key point is translation invariance: if two surfaces {S, S'} are translates of each other in the sense that their boundaries are translates of each other, then their integrals against any {2}-cocycle {\rho} will agree.
A special case of a {2}-cocycle is a {2}-coboundary, defined as a {2}-cochain {df} of the form

\displaystyle df(g,h) := f(g) - f(gh) + f(h)

for some {1}-cochain {f: G \rightarrow U}. In other words, the integral of {df} on any (oriented) triangle such as that in Figure 4 is equal to the integral of {f} on the boundary of that triangle, and more generally we have the “Stokes theorem”

\displaystyle \int_S df = \int_{\partial S} f

for any oriented surface {S} in a diagram with boundary {\partial S}. One can quotient the space {Z^2(G,U)} of all {2}-cocycles (which is a {U}-module) by the space of all {2}-coboundaries {B^2(G,U)}, leading to the {2}-cohomology group {H^2(G,U)}, which is then seen to be closely analogous to the {2}-cohomology group in either simplicial cohomology or de Rham cohomology. (One can of course perform the same construction for any order. For instance, in the case of {1}-cohomology, the space of {1}-coboundaries turns out to be trivial in group cohomology, and so the first cohomology group {H^1(G,U)} is isomorphic to the space {Z^1(G,U)} of {1}-cocycles, or in other words the space {Hom(G,U)} of homomorphisms from {G} to {U}.)
We will need to integrate a {2}-cocycle {\rho} on triangles {\Delta} in which all arrows point in the same direction, such as in Figure 25:


Figure 25.

This can be done by adding another point to decompose the triangle into one which we can already integrate:


Figure 26.

Thus we see (if we give {\Delta} the clockwise orientation) that

\displaystyle \int_\Delta \rho = \rho(g,h) + \rho(1,g) + \rho(gh, (gh)^{-1}); \ \ \ \ \ (4)


of course, other expressions for {\int_\Delta \rho} are possible by performing other oriented triangulations of Figure 25. In practice we can simplify these sorts of expressions by normalising the {2}-cocycle to the conditions

\displaystyle \rho(1,g)=\rho(g,1)=\rho(g,g^{-1})=0 \ \ \ \ \ (5)


by subtracting the coboundary {df}, where {f(g) := (\rho(g,g^{-1}) + \rho(1,1)) / 2}; a brief calculation using the cocycle equation (2) reveals that any {2}-cocycle will obey (5) after subtracting off {df}. When one achieves this normalisation, then the integral of {\rho} on the triangle {\Delta} is simply {\rho(g,h)}; also, the integral on triangles in which one of the edges is the identity is automatically zero, and the integral on the loop in Figure 5 is also zero. Thus, {2}-cocycles which are normalised by (5) can be viewed as being quite analogous to closed {2}-forms in de Rham cohomology.
Now we apply the above formalism to the truncated parallelopiped used to prove the Hall-Witt identity. We glue together Figures 18, 21, and 24 to obtain a closed {2}-surface. If {\rho} is a {2}-cocycle normalised by (5), the integral on this surface vanishes. On the other hand, we see that there is a lot of cancellation in this integral; in particular, all of the distorted parallelograms and triangles that appear in Figure 18, also appear (with the opposite orientation) in either Figure 21 or Figure 24. Cancelling out these faces, we are left with the three distorted parallelograms in Figure 24, together with the central triangle in Figure 24. Evaluating these integrals, we conclude the Hall-Witt identity for (normalised) {2}-cocycles:

\displaystyle (\rho(g^h,[h,k]) + \rho(g^h [h,k], [[h,k],g^h]) - \rho([h,k],g^h))


\displaystyle +(\rho(h^k,[k,g]) + \rho(h^k [k,g], [[k,g],h^k]) - \rho([k,g],h^k))


\displaystyle +(\rho(k^g,[g,h]) + \rho(k^g [g,h], [[g,h],k^g]) - \rho([k,g],g^h))


\displaystyle +\rho( [[h,k],g^h], [[k,g],h^k] )


\displaystyle = 0.

Thus, for instance, if {g,h} and {g,k} commute (so that {g, [h,k]} also commute), the Hall-Witt identity tells us that

\displaystyle \rho(g, [h,k]) = \rho( [h,k], g ),

or in other words that the integral of {\rho} on any parallelogram with edges {g, [h,k]} vanishes. This can also be seen by noting how the Hall-Witt truncated parallelopiped degenerates in the presence of so much commutativity.
The Hall-Witt identity for cocycles can also be derived from the group extension interpretation of a {2}-cocycle. Observe that if {\rho: G \times G \rightarrow U} is a {2}-cocycle, then we can form a new group {G'} whose elements are pairs {(g,u)} with {g \in G} and {u \in U}, and whose group multiplication law is given by

\displaystyle (g,u) (h,v) := (gh, u+v+\rho(g,h));

one can easily verify that this law is associative when {\rho} is a {2}-cocycle, and defines a group structure on {G'} with identity {(1,-\rho(1,1))} and inverse map

\displaystyle (g,u)^{-1} := (g^{-1}, -u-\rho(g,g^{-1})-\rho(1,1)).

(If we normalise {\rho} to obey (5), then the identity simplifies to {(1,0)}, and the inverse operation simplifies to {(g,u)^{-1}=(g^{-1},-u)}.) The group {G'} is then a central group extension of {G} by {U}, and indeed it is not difficult to see that all central group extensions of {G} by {U} arise in this manner (with the extensions being isomorphic relative to the base group {G} if the underlying {2}-cocycles differ by a {2}-coboundary). One can then deduce the Hall-Witt identity for cocycles {\rho \in Z^2(G,U)} by applying the ordinary Hall-Witt identity to the elements {(g,0), (h,0), (k,0)} in the extended group {G'}; we omit the details. However, it appears that the group extension interpretation of {2}-cohomology does not easily extend to higher cohomology (unless perhaps one works with more general notions than groups, such as {n}-groups), whereas the simplicial approach given in this post has a more obvious extension to higher cohomology.

Filed under: expository, math.AT, math.GR Tagged: Cayley graphs, commutators, group cohomology, Hall-Witt identity

ICT4PE&D

No comments:

Post a Comment

Thank's!