Describing a wallpaper group by its generators

1One group, all its generating sets

$\mathrm{o}$: the generating pairs are the bases of the lattice

Write the translations of $\mathrm{o}$ in lattice coordinates, so the group is $\mathbb Z^2$ under addition. Two translations $u=(a,b)$ and $v=(c,d)$ generate it exactly when

that is, exactly when they are a basis. If ${|ad-bc|}=n\ge2$, they generate a sublattice holding one point in $n$ (its index is $n$); if ${ad-bc}=0$, only points on a single line.

What "all" means when there are infinitely many. A recipe that names each one exactly once. Fix one basis $(e_1,e_2)$. Every basis is $(e_1,e_2)\,M$ for exactly one matrix $M=\left(\begin{smallmatrix}a&c\\b&d\end{smallmatrix}\right)$ with integer entries and $\det M=\pm1$; these matrices form the group $\mathrm{GL}(2,\mathbb Z)$. Or by hand: take any $u=(a,b)$ with $\gcd(a,b)=1$. Euclid gives whole numbers with $ax+by=1$, and the partners of $u$ are exactly $\pm(-y,x)+k\,u$ for whole $k$.

How few kinds remain. An automorphism of a group is a relabelling of its motions that keeps how they combine. Every automorphism of $\mathbb Z^2$ is such a matrix, and the matrices carry any basis to any other. So up to relabelling, $\mathrm{o}$ has one kind of generating pair. Allow only the relabellings that keep orientation ($\det M=+1$) and the ordered bases split in two, right-handed and left-handed; swapping $u$ and $v$ flips the hand.

Checked by checks/o_bases.py: all 6,561 pairs with entries from $-4$ to $4$, every verdict proved; the recipe, the one kind, and the moves of §2 as well.

$333$: three kinds of generating pair

$333$ has two kinds of motion besides doing nothing: slides, and thirds of a turn, either way, about a 3-fold centre. The centres come in three kinds, the three 3s of the symbol: the clocks (the lattice points), the centres of the up-triangles and the centres of the down-triangles. The closest two centres can be is $1/\sqrt3$ of the clock spacing, and two centres that close are always of different kinds. Call them neighbours. Write $x_p$ for the anticlockwise third about a centre $p$.

Up to relabelling, every generating pair of $333$ is one of three kinds, or four if the order matters (a turn then a slide, or a slide then a turn):

A relabelling here is any affine map $g$ that carries the group $G=333$ to itself, $gGg^{-1}=G$. It turns thirds into thirds and slides into slides, and it may swap the kinds of centre or mirror the picture: sixth-turns about any centre, mirrors through a centre that carry the triangular lattice to itself, and slides from one kind of centre to another. By Bieberbach's theorem these maps are exactly the automorphisms of $333$. None of them turns one kind of pair into another: they keep a slide in the pair, and they keep two turns going the same way, or opposite ways.

The failure to remember is the smallest: turns about two adjacent clocks, one clock spacing apart ($d=1$), make a $333$ of index 3. Section 4 shows it is exactly the clocks film's symmetries with no delay.

Checked by checks/p3_pairs.py: all 6,670 pairs from 116 motions near a clock. The 924 that generate are proved by explicit words and fall into the three kinds, 204 + 204 + 516 (four kinds as ordered pairs); every other pair is shown to fail by a finite image of $333$ (§5) that it does not fill, with the index as stated.

2Do the generators form a group?

No. A generating set is a subset, and it is not closed under composition: $x$ and $y$ are in $\{x,y\}$, and $xy$ is not. But three things close by are groups, and each answers part of the question.

1. The moves from one generating set to another. For $\mathrm{o}$, $\mathrm{GL}(2,\mathbb Z)$ acts on the bases, and exactly one matrix takes a given basis to another. So call one basis standard, and every other basis becomes a matrix: the bases are a copy of the group, with no basis marked as the start. For any group, Nielsen's moves (swap two, invert one, or multiply one by another or by its inverse) turn a list of generators into another list of the same length, and they generate $\mathrm{Aut}(F_n)$, the automorphisms of the free group of item 3. For $\mathrm{o}$ they reach every basis: they are Euclid's algorithm. Taking $v$ from $u$ twice, then $u$ from $v$, then $v$ from $u$ walks $(3,5),(1,2)$ home in 4 moves, the fewest there are:
   $$\begin{aligned}(3,5),(1,2)&\to(2,3),(1,2)\\&\to(1,1),(1,2)\\&\to(1,1),(0,1)\\&\to(1,0),(0,1).\end{aligned}$$
   For $333$ they join every generating pair checked, and they cross between the kinds of §1: inverting $y$ turns $(x,y)$ into $(x,y^{-1})$, and multiplying turns it into $(x,\,yx^{-1})=(x,t_1)$. For a general group they need not join every pair. In $\mathbb Z/5\times\mathbb Z/5$ the pairs $(e_1,e_2)$ and $(2e_1,e_2)$ are never joined, since a move changes the determinant mod 5 only by its sign. So a group's generating pairs can fall into several Nielsen classes.
2. The relabellings (automorphisms). They act on generating sets too, and a relabelling that fixes each generator fixes every element. The kinds in §1 are what is left of the generating pairs once relabellings are allowed: one for $\mathrm{o}$, three for $333$.
3. The free group, with the relations as its kernel. The free group $F_2$ is all words in two letters, multiplied by writing one word after another. A generating pair $(g,h)$ is the same thing as a homomorphism, a map that respects multiplication, from $F_2$ onto the group, sending the letters to $g$ and $h$. The words that come out as no motion at all are the relations; they make up the kernel $N$, and the group is $F_2/N$. A presentation is a short list of relations whose consequences make up all of $N$: their products, their inverses, and their conjugates $w\,r\,w^{-1}$ by any word $w$. Change the generating set and $N$ changes, and so does the Cayley graph; the group does not. (The fable site's torus page draws one group with two generating sets.)

Checked by checks/o_bases.py (one matrix between any two bases; Euclid on every basis with entries up to 6; the walk above is a shortest one; the two Nielsen classes of $\mathbb Z/5\times\mathbb Z/5$) and checks/p3_pairs.py (the moves between the kinds, and that they join every generating pair of its sample).

3Generators against orbifold notation

Your guess is right: the map from generators to groups is many to one. The Two Dollars of Symmetry tutorial on SymmHub starts from the same contrast: "The classical way to study the group is to list generators and relations." The orbifold way folds the pattern up instead. It helps to separate three levels of description.

Two presentations of one group can look nothing alike, and in general no algorithm can decide whether two presentations give the same group (Adian and Rabin, in the 1950s). For wallpaper groups the question is easy, because you can compute the symbol. That is the symbol's job: it is the invariant that collapses the many to one.

The symbol also reads off one standard presentation. Each feature of the symbol gives generators and relations, and one last relation says that going once round everything is no motion at all.

The last relation lets you drop one generator: $z=(xy)^{-1}$, so $x$ and $y$ already generate $333$, and $D=(ABC)^{-1}$, so $2222$ needs only $A$, $B$ and $C$. Section 5 shows that even then the symbol's count can be too high: ${*}632$'s symbol names three mirrors, and two motions are enough (section 6 builds them).

The dollars are Conway's Magic Theorem: a gyration point $n$ costs $\tfrac{n-1}{n}$, a corner $n$ costs $\tfrac{n-1}{2n}$, a star or a $\times$ costs 1, an $\mathrm{o}$ costs 2, and every wallpaper symbol totals 2.

Checked by checks/presentations.py: every relation holds for the actual motions, each set generates, and each symbol totals 2 dollars (all 17). That no further relations are needed is the theorem behind the notation (Conway and Huson 2002; Coxeter and Moser, chapter 4); the script does not test it.

For animations, generators sometimes do what the symbol can't. The fable site's notation page says the decorated symbol is a complete name for forward groups on a primitive lattice. But four pairs of forward groups on time-centred lattices share a symbol, and so do some groups that reverse time. The catalogue tells them apart by a superscript and by their generator lists, "which are always complete and disambiguate".

4What it buys for time symmetries

A homomorphism here is a price list that adds up along any sequence of moves. It is fixed by where it sends the generators, and a price for each generator extends to the whole group exactly when it respects the relations. A price in time, $\tau$, is such a homomorphism: it gives every symmetry a delay, counted in periods, and two symmetries in a row are priced at the sum of their delays. For $333$:

• $x^3=1$ forces $3\,\tau(x)$ to be a whole number of periods, so $\tau(x)\in\{0,\tfrac13,\tfrac23\}$, and the same for $y$ and $z$: 27 lists.
• $xyz=1$ forces $\tau(x)+\tau(y)+\tau(z)$ to be whole: 9 lists survive, and each of the 9 is a genuine price list on all of $333$.

Is this your price rule? Yes, the same thing. "A turn done three times is no turn" is $x^3=y^3=z^3=1$. "The three turns together make no motion at all" is $xyz=1$. "Their prices add up to a whole number" is what a homomorphism has to do with that relation. And 9 is the size of $333$'s abelianisation, $(\mathbb Z/3)^2$, which is what is left of the group when you count the moves and ignore their order. A delay adds up, so it sees only that.

The 4 animations are the 9 lists up to the relabellings that keep orientation, which permute the three kinds of centre:

$1+1+1+6=9$. Allow mirror images too and the twins merge, leaving 3 classes; the catalogue counts the twins apart, so 4. (All four, and a fifth, $333/1'$, whose film looks the same run backwards, sit on the fable site's page for $333$; its notation page explains the subscripts.)

The symmetries with no delay are the pair that fails

For the clocks' prices $(0,\tfrac13,\tfrac23)$, the film's symmetries with no delay are exactly the subgroup made by turns about two adjacent clocks: the pair that §1 said fails. They are the ones that already hold in each frozen frame, read as in the caption. It is a $333$ with a lattice three times sparser, and its three kinds of centre are the three families of clocks, the hands at $0^\circ$, $120^\circ$ and $240^\circ$ on the repelling clocks page. Two clocks that a delay-free slide carries one to the other show the same hand.

The recipe, send each generator anywhere and keep the assignments that respect the relations, is also how Grünbaum and Shephard enumerate colourings. The fable site's hierarchy page says why it is the same problem. It already writes a clock as a homomorphism $\chi:\Gamma\to\mathbb R/\mathbb Z$, so that a clock of order $N$ is a perfect $N$-colouring, and it counts $333$'s three cyclic colourings against its four clockwork groups: the mirror twins colour the plane the same way. Its subgroups page matches each colouring that reaches every colour (a clock does) with a subgroup. Here the subgroup is the one above, and the three colours are the three families of clocks.

Checked by checks/time_costs.py: the 27 lists; the 9 homomorphisms, each tested on all 5,625 products of 75 motions as well as proved; the abelianisation; the 4 classes (3 with mirrors); and the subgroup with no delay, with its three families.

5All 17, by their fewest generators

Every wallpaper group needs at least 2 generators, since it contains $\mathbb Z^2$ and so is not cyclic. To show that more are needed, use a finite image: the group with slides $n$ lattice steps apart treated as equal, $G/n\Lambda$. If no $k$ elements generate that image, no $k$ elements generate the group. Each lower bound below comes from searching all of one such image. Where a row says nearest or shortest, a farther choice of the same kind fails, except for the lengths of ${\times}{\times}$'s glides: along two nearest glide lines, glides of $\tfrac a2$ and $\tfrac b2$ generate exactly when $a$ and $b$ have no common factor, so $\tfrac12$ and $\tfrac32$ still do.

Ten need 2, six need 3, and ${*}2222$ needs 4.

${*}442$: a mirror group needs three

The symbol's generators are the reflections $a$, $b$, $c$ in the three sides of its triangle. A quicker lower bound than the search is the abelianisation, what is left of the group when you count the moves and ignore their order. For ${*}442$ it is $(\mathbb Z/2)^3$, three independent parities, one for each side of the triangle, and two elements cannot produce three independent parities. Two of the triangle's mirrors make only a kaleidoscope: $a$ and $b$, or $b$ and $c$, make the 8 motions at a 4-corner; $c$ and $a$ make the 4 at the 2-corner.

Checked by checks/presentations.py.

One surprise

${*}632$ needs only 2, while ${*}333$, which sits inside it with index 2, needs 3. It is not a mistake: section 6 builds the pair and says why it looks wrong.

Checked by checks/seventeen.py: the 17 groups are built from the coset lists of the International Tables, each identified from its own mirrors, glides and centres, each generating set proved by words, each lower bound found by exhaustive search, and, in the rows that say nearest or shortest, every choice of that kind in a box tried by its exact index, ${\times}{\times}$'s glide lengths included.

6Why ${*}632$ needs only two, and ${*}333$ three

It is not a mistake. Two motions make all of ${*}632$: the sixth-turn $r$ about a 6-centre $O$, and the mirror $c$ halfway to the next 6-centre $O'$. Your three is right for mirrors alone: two mirrors that cross make only the kaleidoscope where they cross, as with ${*}442$ in section 5, and two parallel ones only mirrors parallel to them and slides across them. The pair trades two of the symbol's mirrors, $a$ and $b$, for their turn $r=ba$, and the steps below get both back.

1. Turns and flips. Ignore where a motion happens and keep what it does to directions, its linear part: $r$ turns directions by $60^\circ$ and $c$ flips them, and together they give all 12 of ${*}632$'s, the symmetries of a hexagon.
2. Slides. Follow $O$ through $rcrc$, right to left: $c$ takes it to $O'$, $r$ turns $O'$ up to the 6-centre $P$ on $c$, $c$ leaves $P$ where it is, and $r$ turns $P$ to the 6-centre at the tip of $u$. The linear part of $rc$ is a flip, and a flip done twice changes nothing, so $(rc)^2$ is a slide, and since it takes $O$ to the tip of $u$, it is $u$, a shortest one. Turned by $r$, as $r^k(rc)^2r^{-k}$, it gives all six shortest slides, and those make every slide.
3. Everything. Any motion $g$ of ${*}632$ has the linear part of some $h$ that $r$ and $c$ make, so $gh^{-1}$ is a slide, which they make too; so they make $g=(gh^{-1})\,h$.

Why it looks wrong

A subgroup can need more generators than its group. ${*}333$ is half of ${*}632$: what the mirrors through the 3-centres, such as $b$ and $c$, make. Schreier's bound says that a subgroup of index $n$ in a group made by $d$ motions is made by at most $n(d-1)+1$. Here that is $2(2-1)+1=3$, and ${*}333$ needs all three.

Odd corners tie mirrors together. A parity calls each motion even or odd, and adds up like the prices of section 4. Where two mirrors meet at a corner $n$ with $n$ odd, the turn there carries one onto the other, so every parity gives them the same value; an even corner ties nothing. Each kind of mirror left untied has a parity of its own: count, mod 2, the mirrors of that kind crossed on the way from a point to where the motion takes it. Any way will do, since a round trip crosses every mirror an even number of times.

With three free parities, two motions are not enough: some parity makes both even, and then all they make is even, though that parity makes some mirror odd. ${*}632$'s pair passes this test: $r=ba$ is odd for both of its parities, and $c$ only for the one it shares with $b$.

${*}333$'s three shows on a small torus. Treat as nothing the slides of section 4's lattice three times sparser, whose shortest steps are $\sqrt3$ long. Then 18 motions are left: 9 that keep orientation (nothing, two slides, six thirds), which commute and are nothing done three times, and 9 flips; each flip $s$ reverses each $x$ of the 9, $sxs=x^{-1}$. So two of the 9 make no flip, and a flip with any other motion makes at most 6: no two make all 18.

Checked by checks/p6m_two.py: each step, the words, the parities three ways and by counting crossed mirrors, Schreier's three, and the tori of 18, 24 and 54 motions.