The group drawn as a map

A group of eight elements can be written as an eight-by-eight table of products. The table is complete — everything true of the group is in it — and it is nearly unreadable: sixty-four entries with no structure the eye can use, and no way to see at a glance which elements are close to which.

The alternative is to draw a map. Put one dot for each element, choose a few elements as generators, and draw an arrow from $g$ to $g s$ for each generator $s$. Multiplying by a generator becomes following an arrow, and a product of generators becomes a walk.

What the picture is #

Formally, the Cayley graph of a group $G$ with respect to a generating set $S$ has the elements of $G$ as vertices and an edge from $g$ to $gs$ for every $g$ in $G$ and every $s$ in $S$. When a generator is its own inverse the two directions coincide and the edge is drawn plain; otherwise it is drawn as an arrow.

Two properties make it a map rather than a diagram, and both are checked on every graph the figures draw.

The generators reach everything. That is what generating means, and the check is a walk outward from the identity that must arrive at every element. If it does not, the chosen elements generate a proper subgroup and the graph falls into pieces — one piece per coset, which is a picture of the blocks a subgroup cuts out.

Every vertex looks like every other. Multiplying everything on the left by a fixed element $a$ sends $g$ to $ag$ and $gs$ to $ags$, so it carries edges to edges: it is a symmetry of the graph. Since $a$ can be anything, the graph’s symmetry group acts transitively on its vertices, and there is no distinguished dot. The identity is marked in these figures for the reader’s benefit, and the graph does not know which one it is.

That second property is why the drawing deserves to be called a map of the group rather than of one element’s neighbourhood. The figures verify it by checking, for every pair of elements, that left multiplication carries each edge to an edge — a check over all $|G|^2|S|$ cases, which is only feasible because the groups here are small, and which is the sort of thing that ought to be checked once rather than assumed forever.

Distance, and the word metric #

With arrows in place, the natural notion of distance is the number of steps.

The word length of an element is the fewest generators needed to write it; the word metric is the resulting distance between elements. It is a genuine metric — symmetric because the generating set is closed under inverses, and satisfying the triangle inequality because concatenating words is allowed — and it turns a group into a geometric object.

For a finite group the whole thing fits in a picture and the interesting quantity is the diameter: the largest word length, which is how far apart two elements can be. For the eight motions of a square generated by a quarter turn and a flip, the diameter is three.

For infinite groups the word metric is where the subject becomes geometry. The integers generated by $1$ give a line; the integers generated by $2$ and $3$ give the same line with extra edges and a different metric; the free group on two generators gives an infinite tree with no loops at all. Asking which features of the metric survive a change of generating set is the founding question of geometric group theory, and the answer — the large-scale features do — is what makes the subject possible.

The choice of generators shows #

Nothing in the definition fixes the generating set, and different choices give genuinely different pictures of the same group.

That is worth being explicit about, because it is the standing caveat on every statement made about a Cayley graph. The graph is not an invariant of the group; it is an invariant of the group together with a choice. Two Cayley graphs of the same group can differ in degree, in diameter, in girth, in whether they are planar.

What survives the choice is the large scale. Two Cayley graphs of the same finitely generated group are always quasi-isometric — each can be mapped into the other with distances distorted by at most a fixed multiplicative and additive amount — because each generator of one set is a bounded word in the other. So questions about growth rate, about whether the group looks like a tree at large scales, and about the structure at infinity are questions about the group, while questions about the diameter or the degree are questions about the presentation.

The finite case has the same distinction in miniature. The diameter of the eight motions is three with one generating set and four with another, so diameter is not a property of the group; the number of elements at each distance depends on the choice too. What does not depend on it is which elements exist and how they compose, and that is what the table above carries and the map redraws.

What the loops say #

A closed walk in the graph is a product of generators equal to the identity — a relation. The short loops therefore are the group’s relations, and the graph is a picture of a presentation.

For the motions of a square generated by a quarter turn $r$ and a flip $m$: the four-cycles of rotation arrows say $r^4 = e$; the doubled flip edges say $m^2 = e$; and the squares alternating between the two rings say $rm = mr^{-1}$, the relation that makes the group non-commutative. Those three relations generate all the others, which is the statement that the group is presented by them, and a reader can find each of them as a loop in the drawing.

Reading relations off a picture is the only reason Cayley graphs are drawn by hand at all in modern practice. A group given by a presentation is an object nobody can see; drawing part of its Cayley graph is how one finds out whether it is what was intended, and the shapes of the loops are the relations one has actually imposed rather than the ones one meant to.

Subgroups as sub-pictures #

A subgroup shows up in the map twice over, once as a subgraph and once as a partition.

Take a subgroup $H$ and use only the generators lying inside it: the walks from the identity stay inside $H$, and the reachable set is $H$ exactly. Starting instead from another element $g$, the same walks reach $gH$ — a coset. So the graph made with only those generators falls into one connected piece per coset, all of them isomorphic, and their number is the index.

That picture is Lagrange’s theorem drawn: the group is partitioned into pieces of equal size, so the size of a subgroup divides the size of the group. The counting version is in the essay that proves it by counting; the graph version adds the observation that the pieces are not merely equal in size but identical as graphs, since left multiplication by $g$ carries one onto another.

The cyclic case, and what a ring can carry #

The smallest maps are worth looking at on their own, because they show how little a Cayley graph needs in order to say something.

A cyclic group generated by one element is a ring, and everything about the group is legible in it. The word length of $r^k$ is $k$; the diameter is one less than the order; and a subgroup is a sub-ring visited by taking every $d$th step, which is a picture of the fact that the subgroups of a cyclic group of order $n$ are one per divisor of $n$.

Change the generator and the ring changes shape while remaining a ring: generating the six rotations by $r^5$ instead of $r$ traverses them in the opposite order, and generating by $r^2$ fails, because the even powers form a proper subgroup and the walk never reaches the odd ones. That failure is the map’s way of saying that $2$ and $6$ share a factor — a divisibility fact appearing as a disconnected drawing.

Adding a second generator to a cyclic group is where the pictures start to differ from each other. The six rotations generated by $r^2$ and $r^3$ together are connected, since $3 - 2 = 1$, and the resulting graph has diameter two rather than five: two well-chosen generators shrink the map dramatically, which is the finite shadow of a phenomenon that matters enormously for infinite groups.

Where it fails, and what it costs #

The graph grows with the group. A group of order sixty has sixty vertices and, with two generators, a hundred and twenty edges, and a drawing of it is a mess. Cayley graphs are drawn for small groups and for infinite groups with a lot of symmetry, and for nothing in between.

A picture is not a proof about the group. Everything visible in the drawing is visible because of the chosen generators, and forgetting that is how false statements get made. This group is planar is not a statement about a group.

Nothing here concerns the cost of computing anything. The map makes multiplication look easy, and the ease is an illusion of scale: for a group given by a presentation, deciding whether two words are equal — which is asking whether two walks end at the same vertex — is undecidable in general, a result of Novikov and Boone that this essay names and does not develop.

What the pictures cannot show #

The graphs drawn here are finite and small, and the subject’s centre of gravity is infinite groups, whose Cayley graphs are unbounded and whose interesting features are asymptotic. Growth — how the number of elements within distance $r$ behaves as $r$ increases — is the fundamental invariant of the infinite theory, and it is invisible in any finite picture.

The layout is also a choice with no mathematical content. Putting rotations on an outer ring and flips on an inner one makes the structure of this particular group legible and is not part of the definition; a different layout of the same graph would look unrelated. A reader should take the adjacency seriously and the positions not at all.

And the transitivity — that the map looks the same from every dot — is a property no static drawing conveys, since the drawing plainly has a middle and an outside. It is stated in the caption and verified in the generator, and the honest picture of it would be an animation of the graph sliding onto itself.

The map of a group acting on something else #

One more reading, and it is the one that connects the construction to the rest of the subject.

A Cayley graph is the picture of a group acting on itself by multiplication. Nothing requires the thing acted on to be the group: given any set the group acts on, the same construction draws one dot per element of the set and one arrow per generator, and the result is a Schreier graph.

The difference shows immediately. The eight motions of a square acting on the square’s four corners give a graph with four dots rather than eight, because two motions can send a given corner to the same place; the map is a quotient of the Cayley graph, folded by the subgroup that fixes a corner. Acting on the two diagonals gives a graph with two dots, folded further.

That family of foldings is the whole content of the orbit–stabiliser relation drawn as pictures: the graph on a set of size $m$ is the Cayley graph with each coset of a stabiliser collapsed to a point, so $m$ times the size of the stabiliser is the size of the group. The same relation counts colourings that cannot be told apart, where the set acted on is a set of colourings and the orbits are what a reader would call the genuinely different ones.

Reading the arrows the other way gives the practical use. Given a set with a group acting on it, drawing the Schreier graph and finding it connected proves the action is transitive; finding the loops at a point identifies the stabiliser; and the sizes of the pieces are the orbit sizes. All three are questions about a group that become questions about a drawing.

Where it came from #

Arthur Cayley introduced the construction in 1878, in a paper making the case that a group should be understood through the way it is generated rather than through a table. The idea was ahead of its use: for finite groups the drawing is a convenience, and the theory of finite groups developed without leaning on it.

Its importance came a century later, when Gromov and others made the word metric the primary object and asked which properties of a group are visible at large scales. That programme — geometric group theory — takes the Cayley graph as the group, up to quasi-isometry, and its central theorems are about shapes: a group whose graph looks like a tree, a group whose growth is polynomial, a group that is hyperbolic in the sense of thin triangles — the same word, and nearly the same meaning, as in the plane where the parallel postulate fails. A construction invented as an illustration became the subject’s basic object.

The ladder from here #

Below: the eight motions of a square, which is the group these figures draw, and the blocks a subgroup cuts out, which is what the map shows when the generators are restricted. Sideways: the roots of unity, whose cyclic group is the simplest Cayley graph there is — a single ring — and the colourings nobody can tell apart, where the group acts on something else instead of on itself. Above: infinite groups, growth, and the geometry that the word metric makes available.

What is worth carrying away #

The construction turns an algebraic object into a metric one, and the value of that is not the picture but the new questions it makes askable.

A table supports questions of the form what is this product? A metric supports questions of the form how far apart are these?, how fast does the ball around the identity grow?, is this space more like a line or more like a tree? — none of which can even be posed about a table. That is the recurring pay-off of putting a structure on a set: the questions available are decided by the structure, and adding a distance to a group adds a whole vocabulary of them.

The cost is the choice of generators, and it is a real cost rather than a technicality: the fine detail of the answer depends on it, and only the coarse features do not. Knowing which of one’s conclusions survive the choice is the discipline the subject is built on.