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 was used to place some geometry on that group . In this post, we explore a variant of that theme, in which (fragments of) a Cayley graph on is used to describe the basic algebraic structure of , and in particular on elementary word identities in . 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 , 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 . 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 of the group , and one draws a directed edge from to labeled (or “coloured”) by the group element for any ; the graph consisting of all such vertices and edges will be denoted . Thus, a typical edge in looks like this:

Figure 1.

One usually does not work with the complete Cayley graph . It is customary to instead work with smaller Cayley graphs , in which the edge colours are restricted to a smaller subset of , such as a set of generators for . As we will be working locally, we will in fact work with even smaller fragments of 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 , the left translation map 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 , with edges coloured by elements of , which has at least one graph homomorphism into the complete Cayley graph of ; thus there exists a map (not necessarily injective) with the property that whenever is a directed edge in coloured by a group element . 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:

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 , since implies . This simple observation provides a way to prove group theoretic identities using diagrams: to show that two group elements are equal, it suffices to show that they connect together (with the same orientation) the same pair of vertices in a diagram.

Remark 1One can also interpret these diagrams as commutative diagrams in a category in which all the objects are copies of , 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 , the vertices can be connected by the following triangular diagram:

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 edge to be the reversal of the edge, but rather as a distinct edge that just happens to have the same initial and final endpoints as the reversal of the edge. (This will be of minor importance later, when we start integrating “-forms” on such edges.)

A fundamental operation for us will be that of *gluing* two diagrams together.

Lemma 1 ((Labeled) gluing)Let be two diagrams of a given group . Suppose that the intersection of the two diagrams connects all of (i.e. any two elements of are joined by a path in ). Then the union is also a diagram of .

*Proof:* By hypothesis, we have graph homomorphisms , . If they agree on then one simply glues together the two homomorphisms to create a new graph homomorphism . If they do not agree, one can apply a left translation to either or to make the two diagrams agree on at least one vertex of ; then by the connected nature of we see that they now must agree on all vertices of , and then we can form the glued graph homomorphism as before.

The above lemma required one to specify the label the vertices of (in order to form the intersection and union ). However, if one is presented with two diagrams with unlabeled vertices, one can identify some partial set of vertices of with a partial set of vertices of of matching cardinality. Provided that the subdiagram common to and after this identification connects all of the common vertices together, we may use the above lemma to create a glued diagram .

For instance, if a diagram 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 :

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 :

Figure 9.

In addition to gluing, we will also use the trivial operation of *erasing*: if is a diagram for a group , then any subgraph of (formed by removing vertices and/or edges) is also a diagram of . This operation is not strictly necessary for our applications, but serves to reduce clutter in the pictures.

If two group elements 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 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 of one group element 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 :

Figure 12.

Figure 13.

Another way to replace the parallelogram in Figure 10 is to introduce the commutator 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 :

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 . The following diagram, obtained by gluing together copies of Figures 11 and 15, demonstrates that ,

Figure 16.

while this figure demonstrates that :

Figure 17.

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

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:

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 :

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 -cocycles.

** — 1. A Hall-Witt identity for -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 -cohomology. Fix some coefficient ring (e.g. the integers , the reals , or a cyclic group such as ; for the elementary cohomology topics we will be presenting here, the exact choice of the coefficient ring will not be important). A *-cochain* is just a map . Using our diagram perspective, we can interpret a -cochain in a “de Rham” way as a “-form” that assigns the element of to any oriented edge in a diagram that has colour . By definition, we also define the integral along the reversal of an oriented edge in a diagram by . Note though that the integral along a edge is not necessarily the negation of the integral along a edge, since we may have . This explains the previous remark that we do not view a edge as the reversal of a edge. Similarly, since need not equal , the integral of 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 -chain is normalised in the sense that and (which is for instance the case with the -cocycles discussed below), then the analogy becomes more accurate.

Given any oriented path in a diagram consisting of a sequence 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” of a -cochain as the sum of the individual edge integrals . A key point here is that of *translation invariance*; if two paths 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 .

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

A *-cocycle* is a -cochain which obeys the identity

for all . Of course, this equation is nothing more than the assertion that is a group homomorphism from to ; but let us pretend that we are unaware of this interpretation of -cocycles, and instead interpret the -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 -cocycle is nothing more than a -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 -cocycle, which leads to some additional cancellations. For instance, by integrating a -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

for all and any -cocycle . 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 for any and any -cocycle .

Next, we define a *-cochain* to be a function . Just as -cochains can be viewed as “-forms” that can be integrated on oriented edges and thus oriented paths, we can view -cochains as “-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 as the integral of 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 on any oriented triangulated surface (or, more generally, -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 *-cocycle* is a -cochain which obeys the identity

for all . As we will recall later, -cocycles can be viewed as coordinatisations of central -extensions of , but we will again pretend that we are unaware of this interpretation of -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 -cohomology). The cocycle identity (2) is then asserting that the integral of on the tetrahedron in Figure 8 (or, in fact, any other tetrahedron) vanishes. Because any closed oriented triangulated -surface on a diagram can be broken up into tetrahedra (again after filling in some edges if necessary), we conclude that a -cocycle is nothing more than a -cochain which is *closed* in the sense that its integral on any closed triangulated -surface vanishes. Among other things, this now allows one to define the integral of a -cocycle on any oriented surface (not necessarily closed or triangulated) which is bordered by some closed loop in a diagram, by replacing by some triangulated oriented surface with the same oriented boundary as . For instance, we can integrate a -cocycle on the pentagon in Figure 14 with the counterclockwise orientation to obtain an element of ; by selecting a suitable triangulation of this pentagon, this integral can be expressed explicitly as

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

Again, a key point is translation invariance: if two surfaces are translates of each other in the sense that their boundaries are translates of each other, then their integrals against any -cocycle will agree.

A special case of a -cocycle is a *-coboundary*, defined as a -cochain of the form

for some -cochain . In other words, the integral of on any (oriented) triangle such as that in Figure 4 is equal to the integral of on the boundary of that triangle, and more generally we have the “Stokes theorem”

for any oriented surface in a diagram with boundary . One can quotient the space of all -cocycles (which is a -module) by the space of all -coboundaries , leading to the *-cohomology group* , which is then seen to be closely analogous to the -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 -cohomology, the space of -coboundaries turns out to be trivial in group cohomology, and so the first cohomology group is isomorphic to the space of -cocycles, or in other words the space of homomorphisms from to .)

We will need to integrate a -cocycle on triangles 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 the clockwise orientation) that

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

by subtracting the coboundary , where ; a brief calculation using the cocycle equation (2) reveals that any -cocycle will obey (5) after subtracting off . When one achieves this normalisation, then the integral of on the triangle is simply ; 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, -cocycles which are normalised by (5) can be viewed as being quite analogous to closed -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 -surface. If is a -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) -cocycles:

Thus, for instance, if and commute (so that also commute), the Hall-Witt identity tells us that

or in other words that the integral of on any parallelogram with edges 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 -cocycle. Observe that if is a -cocycle, then we can form a new group whose elements are pairs with and , and whose group multiplication law is given by

one can easily verify that this law is associative when is a -cocycle, and defines a group structure on with identity and inverse map

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

## 19 comments

Comments feed for this article

13 May, 2012 at 4:46 pm

David RobertsFigure 3 purports to show the identity element, but is labelled as g^[-1}

[Corrected, thanks – T.]13 May, 2012 at 4:56 pm

David RobertsOn a more mathematical note, figure 18 looks like it should be related to some sort of polytope, similar to the associahedron, permutahedron and so forth. But this may just be a random guess.

The full Cayley graph Cay(G,G) is the graph underlying the action groupoid for the action of G on itself. This groupoid is equivalent to the trivial groupoid, but is actually very interesting as it is the basis for the construction of the universal G-bundle by Segal. Additionally, this groupoid can be given the structure of a strict 2-group, and hence Cay(G,G) itself has the structure of a group object in the category of directed graphs.

13 May, 2012 at 7:33 pm

John JiangThis is the first time I understood higher order group cohomology. Thanks for the wonderful display of clarity!

14 May, 2012 at 8:04 am

Jérôme ChauvetDear Tao,

Very entertaining post : it could not be clearer. I guess it helps comprehending Connes’ non commutative quantum theory (I mean as a good start with co-cycles and stuffs)

Best,

15 May, 2012 at 2:25 am

chorasimilarity“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”

Do you see a way of turning this statement into a rigorous one? You have a family of labelled graphs, together with rules of decorating/gluing/erasing, so is there any way to turn this into a notion of proof?

15 May, 2012 at 4:11 am

Terence TaoYes, these diagrams form a proof system for verifying identities in the free group (which of course then also hold in any group). (Of course, such identities can also be easily verified by direct algebraic expansion, but then the underlying geometry and topology of the situation is lost.)

I think that with the obvious modifications, one could also make this into a proof system for verifying identities in a finitely presented group. On the other hand, showing that a given identity in such a group does NOT hold is known to be an undecidable problem, so there is no proof system in that case.

16 May, 2012 at 1:48 pm

Max BaroiHey Dr. Tao.

Really cool post.

I just have a quick suggestion considering for providing motivation behind one of your definitions.

Someone with exposure to only a little to amount of graph and group might find the definiton, “connect x to y by arrow g if y=xg” somehwat arbitrary. Maybe just a clarifying sentence explaining that using right multiplication implies that travelling along the arrow “g”, then travelling along the arrow “h” is equivalent to travelling along the arrow “gh”, while using left multiplication it is equivalent to travelling along the arrow “hg.” The choice of definiton is logically arbitrary, but right multiplication is somewhat clearer to read in a language you read left to right.

If you already gave motivation, and I simply missed it. Apologize, and disregard my comment.

Cheers,

Max

16 May, 2012 at 1:51 pm

Max BaroiOf course in additon to left invariance. I feel a little bit dumb.

21 May, 2012 at 6:53 am

Joerg GrandeLemma 1 has two minor issues: The explanation of “connects all of ” in parentheses should begin with “i.e. any two elements of “. There is a typo in the definition of the union .

[Corrected, thanks – T.]22 May, 2012 at 7:32 am

Gary MakHi Terry

A wonderful post – thank you. Just a quick question: is there anywhere a similar Cayley-graph-type exposition of the theory of group cohomology where you do not have trivial action of G on U?

Thanks!

Gary

25 May, 2012 at 1:16 pm

Terence TaoI think the main difference is that the translation invariance of the “k-forms” that model the k-cocycles has to be replaced by translation equivariance, thus each time one translates a simplex by some group element g, the value (in the G-module M that is taking as the space of coefficients) assigned to that simplex by a k-cocycle also gets rotated by g.

28 May, 2012 at 1:16 pm

Gary MakThanks! I’ll get busy working out the details ….

30 August, 2012 at 11:09 am

conjugate glue « Peter's ruminations[…] Both From Terry Tao website […]

23 November, 2012 at 9:31 am

WillUnless I am misunderstanding something, it looks like the directions of the arrows on the central triangle in Figure 24 ought to be reversed to be consistent with the earlier definition of the commutator. I also suspect that the last term on line 3 of the Hall-Witt identity for 2-cocycles should be . In the equation immediately following Equation (3), should the second term be ?

Finally, I may be laboring under some misconception about how the signs are determined, but I am puzzled about why the signs of the three terms on the right side of Equation (3) aren’t all the reverse of what is shown given that positive sign is associated with clockwise orientation. Likewise the three terms on the right side of the equation immediately following Equation (3). I’m also wondering about the sign of the term on line 4 of the Hall-Witt identity for 2-cocycles. (This query is related to my first question above about the direction of the arrows on the central triangle.)

23 November, 2012 at 12:37 pm

Terence TaoThanks for the corrections! Hopefully they should all be fixed now (I reversed the orientation of the pentagon P relating to (3)).

27 November, 2012 at 11:44 am

WillFigure 24 doesn’t look like it’s changed unless I click on it. When I do that I see an enlarged picture with the triangle arrows going the opposite way. At first I guessed that this was due to some weird caching effect that I couldn’t figure out how to get rid of, but I’ve now had the chance to view the page on a different computer at a different location and still see the same effect. I’m wondering whether it’s just me, or whether there is some issue with the new figure?

By the way, thanks for writing this article!

[Sorry, that was me trying to edit HTML by hand. Should be fixed now – T.]20 March, 2013 at 9:11 pm

Xaio-Gang WenNow, group cohomolgy theory become very useful in condensed matter physics, just group theory is very useful in physics.

(See http://arxiv.org/abs/1106.4772 )

21 September, 2015 at 3:29 am

Cayley graphs and the geometry of groups | Math Online Tom Circle[…] https://terrytao.wordpress.com/2012/05/11/cayley-graphs-and-the-algebra-of-groups/ […]

17 August, 2016 at 5:06 pm

SuganyaI want how to draw Cayley coloured graph with step by step…