The square net draws eleven groups

How fast a group grows started from a wallpaper group written as letters and relations, drew its Cayley graph, and found that the graph is a periodic net. Each element is a vertex, each generating operation joins an element to its product with that operation, and the translations of the group repeat the whole picture across the plane. Counting the elements spelled in at most $R$ letters turned out to be the same computation as counting the atoms within $R$ bonds of a given atom, which counting outwards had already done for crystal nets. That essay ended by saying the connection runs the other way too.

This essay runs it the other way. Start with a net, a periodic graph that a chemist would recognise, and ask whether it is the Cayley graph of some group. If it is, ask which groups, and how many ways each.

The answer for the eleven uniform nets, the edge graphs of the eleven tilings by regular polygons in which every vertex looks alike, is that every one of them is a Cayley graph. Most are Cayley graphs of several groups at once. The square net is the Cayley graph of eleven of the seventeen wallpaper groups. The kagome net is the Cayley graph of exactly one. And between them the eleven nets are Cayley graphs of all seventeen groups, so every wallpaper group has a picture of itself among the tilings by regular polygons.

A net is a group when nothing stays put #

The test is old and short. Gert Sabidussi proved in 1958 that a connected graph is the Cayley graph of a group $H$ exactly when $H$ acts on the graph’s vertices regularly. That means two things at once. The action is transitive, so some element of $H$ carries any vertex to any other. And it is free, so no element except the identity leaves any vertex where it was.

Given such an action the Cayley structure can be read straight off the graph. Pick one vertex and call it the identity. Every other vertex is reached by exactly one element of $H$, so it can be named by that element. The edges at the identity vertex lead to a handful of neighbours, and the elements that reach those neighbours are the generating operations. Every other edge is then a translate of one of these. If an edge joins the vertices named $g$ and $h$, then $g^{-1}h$ carries the identity vertex to one of its neighbours, so $h$ is $g$ followed by one of the generating operations.

The convention matters and it is worth stating. An edge joins $g$ to $gs$, with the generating operation $s$ multiplied on the right. The set of generating operations contains the inverse of each of its members, because an edge can be walked in either direction. An operation that is its own inverse, a half-turn or a mirror, therefore draws one edge rather than two. With a different convention the honeycomb below would come out with doubled edges, and the correspondence between groups and nets would be about multigraphs instead of the graphs a chemist draws.

The picture at the head of this essay shows the criterion met four ways on one net. The plain answer is the lattice itself. The two translations along the edges act freely and transitively on the vertices, and the square net is the Cayley graph of $\mathbb{Z}^2$ with those two translations as its generating operations. That is where the growth essay started.

The other three panels are less obvious and more instructive. Put a half-turn at the midpoint of each of the four edges around one vertex. Each half-turn swaps the two ends of its own edge, so each is an edge. The group the four generate is a p2, and its half-turn centres all sit at edge midpoints and square centres, never at a vertex. So it acts freely, and the square net is the Cayley graph of p2 with four involutions as its generating operations. Replace the half-turns by mirrors running halfway between the rows and columns and the same thing happens with pmm. Put quarter-turn centres in the middle of the squares and it happens with p4: a quarter-turn about the centre of one square carries a corner of that square to the next corner along, and the four neighbours of a vertex are reached by turning a quarter either way about either of two squares.

What is not allowed is for any of these groups to fix a vertex. The square net’s whole symmetry group, p4m, has quarter-turns and mirrors through every vertex, so seven of its eight cosets fix a vertex and it is not regular. The question is which of its subgroups escape.

Why there are finitely many to try #

The symmetry group $G$ of a net is infinite, and so is its set of subgroups. The search is made finite by an exact count.

Suppose $H$ is a subgroup of $G$ acting regularly. It has a point group $P_H$, the set of its linear parts, and a lattice of translations $L_H$ sitting inside the net’s own lattice $L$ with some index $m$. Count the vertices in one cell of $L_H$ in two ways. The net has $k$ vertices in each cell of $L$, so a cell of $L_H$ holds $km$ of them. On the other hand $H$ acts regularly, so the vertices in one cell of $L_H$ are matched one to one with the cosets of $L_H$ in $H$, and there are $|P_H|$ of those. So $m = |P_H|/k$. It is the index arithmetic of domains of a subgroup, where half the operations need twice as much of the cell, applied to vertices instead of area.

That settles almost everything. The point group of a plane net has at most twelve elements, so the index is at most twelve. Once the point group is chosen the index is fixed. The subgroups of a point group are few, the sublattices of a given index are finitely many, and only those carried onto themselves by every linear part in $P_H$ can serve. For each surviving pair, the translation parts of two generating operations of $P_H$ can be chosen in $m^2$ ways modulo $L_H$. The group they generate is closed modulo $L_H$ and kept only if it has exactly $|P_H|$ cosets, which rules out a choice that secretly generates extra translations. Then every coset is tested against every vertex for a fixed point. Freeness and the count $m = |P_H|/k$ together give transitivity, so what survives is exactly the set of regular subgroups.

The nets themselves were read off exact constructions of the eleven tilings. Twenty-one vertices, eleven tilings found which vertex types extend to a tiling, and eleven tilings, five groups named the group of each. Each net’s group was detected afresh from the graph alone, on its barycentric placement, and it came out as the same group the tiling has.

Every one of the eleven passes #

The census is in the matrix above. Every row has a filled dot, so every uniform net is a Cayley graph. Every column has one too, so every wallpaper group is drawn by at least one of these nets. There are ninety-one regular subgroups in all, falling into forty-six classes when subgroups related by the net’s own symmetries are counted once.

The distribution is very uneven. The square net has thirty-six regular subgroups of eleven types. The triangular net has twenty-four, of five types, and the honeycomb fourteen, of six. At the other end three nets have exactly one: the kagome net 3.6.3.6 (p3), the snub hexagonal net 3.3.3.3.6 (p6) and 4.6.12 (p6m). The 4.8.8 net has four, 3.12.12 two, 3.4.6.4 two, 3.3.3.4.4 four and 3.3.4.3.4 two.

Two of the nets are Cayley graphs of their own whole symmetry group. In 4.6.12 and in 3.3.3.3.6 no symmetry fixes a vertex at all. Twelve vertices to a cell and a point group of order twelve, or six and six, means the group is already regular and there is nothing to choose. These are the two nets in which every vertex sits at a general position of the group, and the uniqueness is forced: a proper subgroup with the same lattice would have too few cosets to reach every vertex, and one with a smaller lattice would have to have a larger point group than the net allows.

The square net and the triangular net sit at the opposite extreme, and the reason is that they have one vertex to a cell. Then $m = |P_H|$, so every point group the lattice allows can be tried at an index equal to its own order, and many of them find a way to keep their rotation centres and mirrors off the vertices.

The square net, eleven times #

Eleven of the seventeen is the square net’s count, and the six it misses are worth accounting for one by one.

Five of the six are the groups with three-fold or six-fold rotations: p3, p3m1, p31m, p6 and p6m. The square net’s lattice has no three-fold symmetry and no sublattice of it has either, so they are excluded before any vertex is examined.

The sixth is p4m, and its exclusion is a short argument. A regular p4 needs its quarter-turn centres away from the vertices, and on the square net the only places left for them are the centres of the squares. In a group of type p4m every quarter-turn centre lies on mirrors running in four directions, two along the lattice and two along its diagonals. A diagonal line through the centre of a square passes through two corners of that square, which are vertices. So any p4m containing a square-centre quarter-turn has a mirror through a vertex, and none can be regular. The p4g that the census does find is the way round it: its quarter-turn centres sit on no mirror, its mirrors run along the lattice directions halfway between rows, and its diagonal operations are glides.

The other eleven all occur, several of them more than once. There are two essentially different p2s: one generated by four half-turns, and one by two half-turns and a translation, which doubles the lattice in one direction only. There are two pgs and three pggs. A group of glides can carry a vertex to its four neighbours because a glide reflection along a line between two rows moves a vertex across the line and along it at once. Six groups are made of glides found the same freedom in the generating sets of the plane groups themselves.

Graphene’s net is a group, six ways #

The honeycomb is the net of graphene, of the boron layer in a diboride, and of every hexagonal mesh. It has two vertices to a cell and a symmetry group of type p6m whose point group has twelve elements, so a regular subgroup has a point group of even order and a lattice of index half that.

The plainest of its six types is on the left of the picture. Each edge of the honeycomb has a half-turn about its midpoint that swaps its two ends and preserves the whole net. Take the three at the edges around one vertex. They generate a p2 on the honeycomb’s own lattice, and its four half-turn centres per cell sit at the three edge midpoints and the centre of the hexagon, none of them at a vertex. So the honeycomb is the Cayley graph of p2 with three involutions, and graphene’s net can be described entirely by three half-turns and no translations at all. The translations are there, as products of two half-turns, but nothing needs to say so.

The other types use the same room in different ways. There are three p6s, three cms, three pmgs and three pggs, each trio carried into itself by the honeycomb’s own rotations and so counted as one class, and a single p3m1 generated by three mirrors. All fourteen keep their fixed points off the two vertices of each cell.

Four reflection groups draw four nets #

Four of the seventeen groups are generated by reflections alone: pmm, p3m1, p4m and p6m, the groups of the rectangle and of the three triangles whose angles are $\pi/3$ three times, $\pi/2, \pi/4, \pi/4$, and $\pi/2, \pi/3, \pi/6$. Four groups are made of mirrors derived that list from which closures of located mirrors stay discrete.

The census finds a striking thing about them. Each is the regular subgroup of exactly one uniform net, through its mirrors. The rectangle group pmm gives the square net. The equilateral group p3m1 gives the honeycomb. The $(2, 4, 4)$ group gives 4.8.8, and the $(2, 3, 6)$ group gives 4.6.12. The pictures above show why. The mirrors of a reflection group cut the plane into copies of one rectangle or triangle, its chambers, and the group carries any chamber to any other in exactly one way. Put one vertex inside each chamber and join two vertices when their chambers share a wall. Every vertex then has as many neighbours as its chamber has walls, and the reflection in a wall carries a vertex to its neighbour across that wall. So the graph is the Cayley graph of the reflection group, with the walls of one chamber as its generating operations. Every wall names a generator made that statement for any fundamental domain. What is new here is which nets it produces.

They are uniform tilings because the chamber is so symmetric. A vertex at the centre of each chamber of the square case of pmm gives the square net. In an equilateral triangle the centre gives the honeycomb. In the two right triangles the point equidistant from all three walls, the incentre, gives the truncated square tiling 4.8.8 and the truncated trihexagonal tiling 4.6.12. So the four uniform tilings dual to the chamber tilings of the four reflection groups are exactly the Cayley graphs of those groups, and the census confirms it without being told: for these four nets a regular subgroup generated by mirrors alone appears, and for the other seven none does.

Being generated by involutions is a weaker property, and the same four nets have it more often. The square net is also the Cayley graph of p2, pmg and cmm by involutions alone, mixing half-turns and mirrors; the honeycomb of p2 and pmg; 4.8.8 of cmm. The other seven nets have no regular subgroup generated by involutions at all, which the census finds case by case rather than by any single argument.

The kagome net admits one group #

The kagome net is the opposite case to the square net, and the arithmetic that limits it to one group can be read off the table in the picture.

Its vertices sit at the midpoints of a triangular net’s edges, three to a cell, and each lies on two mirrors and a half-turn axis of its group p6m. A regular subgroup needs a point group of order divisible by three, and the point group of the hexagonal lattice has five such subgroups. The rotation group of order three needs index $m = 1$, so it uses the kagome net’s own lattice, and the only way to place its third-turns there is at the centres of the triangles and hexagons. None of these is a vertex, so that p3 is regular.

The three subgroups of order six all need a sublattice of index two that a third-turn preserves. The hexagonal lattice has three sublattices of index two and a third-turn permutes them, so none survives, and the table’s column of sublattices reads zero. The whole point group of order twelve needs index four, and the one sublattice of index four that it preserves is the doubled lattice. On it four groups close, and every one of them puts a mirror or a half-turn through some vertex. So p3 is the only group whose Cayley graph is the kagome net. A net with this much symmetry still has only one way to be a group, because its symmetry is concentrated at the vertices, where a regular action may not put any.

Same shells, different groups #

A Cayley graph’s shells are its group’s word counts, so two nets with equal coordination sequences give two groups with equal growth. The census turns up one such pair among the eleven, and it is a striking one.

The square net counts $4n$ vertices at distance $n$. So does 3.4.6.4, the rhombitrihexagonal tiling, whose vertices each meet a triangle, two squares and a hexagon. Both are 4-regular, and both have exactly four, eight, twelve, sixteen vertices at distances one to four, and so on through every distance computed. The square net is a Cayley graph of $\mathbb{Z}^2$ with two translations. The 3.4.6.4 net is a Cayley graph of p6, with two third-turns about the centres of triangles and two sixth-turns about the centres of hexagons. It is also a Cayley graph of p31m, with two third-turns and two mirrors.

So the word counts of $\mathbb{Z}^2$ with its two obvious generating operations, and of p6 with this particular set of four, are identical sequences. Growth cannot separate these groups, and it cannot separate the graphs either, though the graphs are plainly different: one has squares at every vertex and the other has triangles and hexagons. How fast a group grows found pairs of groups that growth could not separate, p3m1 and p31m among them. The pair here is further apart. One group has no rotations at all and the other has a six-fold axis.

Counted twice #

A claim that a net is the Cayley graph of a group can be checked by a route that never looks at the net. Take the group’s generating operations as affine maps of the plane, with exact rational coefficients. Start from the identity, multiply by each generating operation, and keep every product not seen before. The new elements at each step are the sphere of that radius in the word metric. If the group’s Cayley graph really is the net, these counts must equal the net’s coordination sequence, which is found by a breadth-first search over the quotient graph that knows nothing of groups, operations or the plane.

The two counts agree for all ninety-one subgroups at every distance from one to eight. The agreement is a real check rather than a formality, and the refusals below show what it rejects. Drop one of the honeycomb’s three half-turns and the words count 2, 2, 2, 2: two half-turns generate an infinite dihedral group, whose Cayley graph is a line, against the honeycomb’s 3, 6, 9, 12.

What the picture cannot show #

The census covers the eleven uniform nets and no others. It shows that each is a Cayley graph, and of which groups. It says nothing about nets in which not every vertex looks alike, which cannot be Cayley graphs at all, since a Cayley graph is vertex-transitive by construction, or about vertex-transitive nets that are not uniform tilings.

The search also looks only inside each tiling’s own symmetry group. A regular group of graph automorphisms that are not symmetries of any drawing would be missed. For these eleven nets there are none. A planar graph with three independent paths between any two vertices has essentially one drawing in the plane, a theorem of Whitney’s for finite graphs that extends to these periodic ones, so every automorphism of the graph is a symmetry of the tiling. That fact is quoted here rather than checked.

The counts of regular subgroups depend on a convention too. A subgroup is counted as a subgroup of the net’s symmetry group, and two are put in one class when a symmetry of the net conjugates one onto the other. Counting abstract groups instead would merge different subgroups of one type and change the numbers, though not the matrix.

Cayley, Sabidussi and Coxeter #

Arthur Cayley drew the graph that carries his name in 1878, for finite groups, as a diagram of how generating operations act on group elements. The infinite version, with the plane groups as its main examples, became standard through the twentieth century, and a group in four letters uses it throughout.

The criterion for which graphs arise was Sabidussi’s, in a 1958 paper whose own examples were finite. Its most famous negative case is the Petersen graph: ten vertices, every one alike, and no group of order ten acting on it regularly. So vertex-transitive and Cayley are different properties, and the gap between them was found before anybody asked about periodic nets.

The reflection groups behind the four mirror nets were classified by H. S. M. Coxeter in 1934 for every dimension. The plane cases, the rectangle and the three triangles, are much older, and their chamber tilings were drawn as ornament long before anybody wrote down a group.

What the search must refuse #

Each step of the search can fail in a way that would leave every count plausible, so each has an input it must turn down. The square net’s whole group must be found not regular, and it is: seven of its eight cosets fix the vertex at the origin. A generating set missing one of the honeycomb’s half-turns must fail the word count, and it does. A vertex type that closes around a point and still extends to no tiling, 3.4.4.6 among them, must be refused as a net rather than constructed. And a sublattice of index two that a quarter-turn moves must not be offered as the lattice of a group containing quarter-turns.

Still open: a vertex-transitive net that is not a group #

All eleven uniform nets are Cayley graphs, and that invites the question whether every vertex-transitive periodic net in the plane is one. For finite graphs the answer is no, and the Petersen graph is the smallest witness. For periodic nets the regular-subgroup search used here would settle any one candidate. It needs only the net’s symmetry group and its vertices per cell, and it is finite for the reason given above. What it cannot do is produce the candidate.

The natural place to look is among nets whose vertices sit on high-symmetry sites with no room nearby, as the kagome net’s do. The kagome net escaped with one group because a third-turn could be placed at the triangle centres. A net whose vertex stabiliser meets every subgroup of the point group whose order is a multiple of the vertices per cell, and whose lattice has no sublattice of the needed index, would have no regular subgroup at all. Such a net would be vertex-transitive and still not the picture of any group. It would need several vertices to a cell, since a net with one vertex to a cell is always the Cayley graph of its own lattice, so every net in the census of one-vertex nets passes at once. Whether such a net exists in the plane, or among the nets of space, where the point groups are larger and the vertex sites more varied, has not been settled here.