Free Groups and Tiling

Introduction

Consider the following simple problem.

Prove that the shape on the left cannot be completely tiled by 20 polygons of the types shown on the right.

hexagon_tiling

The solution is rather simple: colour the shape in the following manner.

hexagon_tiling_colouring

This gives 18 green hexagons, 21 orange hexagons and 21 blue hexagons. On the other hand, each triangular piece must cover three hexagons of distinct colours. Hence, if we could tile the figure completely with 20 pieces, we would have 20 hexagons of each colour, which is a contradiction. Thus such a tiling is impossible. ♦

Harder Variation

Now suppose we replace the above shape with the following.

big_triangular_tiling

It is still impossible to tile it with the two types of pieces as above. However, the colouring method fails to prove it since we would obtain an equal number of hexagons of each colour. Thus we need a better method.

The following technique can be generalized to prove that a similar shape of size N is tileable if and only if

N \equiv 0, 2, 9, 11 \pmod{12}.

blue-lin

Conway-Lagarias Method

Here, we will present the solution by John H. Conway and Jeffrey C. Lagarias in their paper “Tiling with polyominoes and combinatorial group theory” (1990). First we convert the problem to an equivalent one with polyominoes. We need to show that it is impossible to tile the left polyomino with the two triangular ones on the right (no rotation allowed).

equivalent_tiling

Free Group on Two Generators

Let F be the free group on the two-element set {xy}. To describe it concretely, we consider the set of all words in \{x, y, x^{-1}, y^{-1}\}. Reduction in a word occurs when we remove two neighbouring occurrences of \{x, x^{-1}\} and \{y, y^{-1}\}. E.g.

xyyx^{-1}y^{-1}\overbrace{xx^{-1}}yy \mapsto xyyx^{-1}\overbrace{y^{-1}y}y \mapsto xyyx^{-1}y.

A word is said to be reduced if no further reduction is possible. Now we can write F as the set of all reduced words in \{x, y, x^{-1}, y^{-1}\}.

  • Group composition in F corresponds to concatenation of words with reduction. For instance,

g = x^{-1}y xx y^{-1}, g' = yx^{-1}yy x \implies gg' = (x^{-1}y xx y^{-1})(yx^{-1}yy x) = x^{-1}yxyy x.

  • The group identity is the empty word.
  • To obtain the inverse of a word, we reverse the order and replace each x (resp. y) by x^{-1} (resp. y^{-1}) and vice versa. E.g. (xyxx y^{-1})^{-1} = yx^{-1}x^{-1}y^{-1}x^{-1}.

For convenience, we write x^m for m neighbouring copies of x and x^{-m} for m neighbouring copies of x^{-1}, and similarly for y^m, y^{-m}. Thus x^2 y^{-3} x is shorthand for xxy^{-1}y^{-1}y^{-1}x.

blue-lin

Polyominoes and Words

Now for each polyomino above, we obtain an element of F as follows. Start with a base point on the perimeter. We trace around the perimeter in a counter-clockwise direction, write x, x^{-1}, y, y^{-1} for the directions of right, left, up, down respectively, and record the loop as a word upon returning to the base point.

polygons_and_words

For the large triangular figure, we pick the bottom-left corner as the base point and obtain the following word:

c := x^{8} (y x^{-1})^{8}y^{-8}.

Change of Base Points

Now our definition of a, b, c\in F depends on our choice of base points. Let’s see what happens to a\in F when we switch to a different point on the perimeter. Let g\in F correspond to the path from the old base point to the new along the perimeter, and let a' \in F be the new loop. Then from the diagram:

basepoint_change_tiling

we have a' = g^{-1}ag in the group F.

In other words, if we change the base point, the new loop is a conjugate of the old one.

blue-lin

Tiling

The process of tiling can be converted to a statement about group product. Suppose we place the two figures together as follows:

diagram_composition_tiling

The perimeter for A is represented by ag (or a conjugate) while that for B is represented by g^{-1}b. Hence the resulting diagram has perimeter ab which is the product of the words for A and B in the group F.

Summary.

Suppose polygons P_1, P_2, \ldots are represented by words w_1, w_2, \ldots. Upon tiling P_1, P_2, \ldots, the resulting perimeter is represented by a word which can be obtained from w_1, w_2, \ldots via conjugation and composition.

Example

diagram_composition_tiling_v2

Thus, if our large triangular polyomino can be tiled by the smaller pieces, then c = x^{8} (y x^{-1})^{8}y^{-8} \in F lies in the normal subgroup N generated by a and b. This will be exploited in our proof.

blue-lin

Proving Our Main Result

We will construct a normal subgroup K of F such that N\le K \le F.

Step 1: Map each word in F to a computer program.

Suppose we have a robot which starts by facing a certain direction (e.g. north). For each element in F, we turn it into a computer program by reading the word from left to right:

  • x: turn right 60°, walk forward 1m, then turn right 60° again.
  • x^{-1}: turn left 60°, walk backward 1m, then turn left 60° again.
  • y: turn left 60°, walk forward 1m, then turn left 60° again.
  • y^{-1}: turn right 60°, walk backward 1m, then turn right 60° again.

Let K be the set of all words in F which bring the robot back to its original position and orientation. Note that K is closed under composition and inverse so it is a subgroup of F.  Furthermore, it is a normal subgroup since if g\in F and h\in K, then ghg^{-1} is the program which does g, then (which has no nett effect on the robot), then the reverse of g.

Step 2: Show that ab and c are in K.

Indeed, for a and b we have:

hexagon_robot

Likewise it is easy to verify that x^3, y^3, (yx^{-1})^3 \in K.

hexagon_robot_v2

For c, we let \pi : F \to F/K be the canonical homomorphism. Since \pi(x^3) = \pi(y^3) = \pi(yx^{-1})^3= \pi(a) = \pi(b) = e we have:

\begin{aligned}\pi(c) &= \pi(x)^{8}\left(\pi(yx^{-1})\right)^{8}\pi(y)^{-8}\\ &= \pi(x)^2 \pi(yx^{-1})^2\pi(y)^{-2}\\ &= \pi(a) = e.\end{aligned}

In particular, we have N\le K.

Step 3: Plot possible paths for the robot.

One easily sees that the robot must travel along the following lines:

robot_tiling_path

The robot’s direction is indicated by the arrow in each disc; thus, it can only face in at most one direction at any spot. If the next instruction is x, the robot travels on the perimeter of a yellow triangle, along the given x orientation. If it is x-1, the robot travels along the perimeter of a yellow triangle, counter to the given x orientation. The same holds for y and y-1, but with the blue triangle.

Step 4: Define a homomorphism \Phi : K \to \mathbb{Z}.

Since each g\in K is a closed path, we may define \Phi(g) to be the number of hexagons enclosed by the path. Here, the counting is oriented counter-clockwise – a loop which encloses a hexagon is counted +1 if the loop is counter-clockwise and -1 otherwise. This gives the desired homomorphism \Phi : K \to \mathbb{Z}. We have

\Phi(x^3) = \Phi(y^3) = 0,\quad \Phi((yx^{-1})^3) =-1,

\Phi(a) = -1,\quad \Phi(b) = +1,

and thus we have

\begin{aligned}\Phi(c) &= \overbrace{\Phi(x^6)}^0 + \Phi(x^2 (yx^{-1})^8 y^{-2}) +\overbrace{\Phi(y^{-6})}^0 = \Phi(y^{-2}x^2(yx^{-1})^8) \\ &= \Phi(y^{-2} x^2 (yx^{-1})^2) - 2= -3\end{aligned}.

Now if the original tiling were possible, we would require \frac 1 3 \frac{8 \times 9}2 = 12 pieces. Hence c is obtained from the product of 12 conjugates of a and b (in F). Since K is normal in F, each conjugate a’ of a lies in K and furthermore \Phi(a') = \Phi(a) = -1. Likewise \Phi(b') = \Phi(b) = +1 for any conjugate b’ of b in F. From this, it follows that \Phi(c) is even, which contradicts \Phi(c) = -3.

Thus our proof is complete. ♦

blue-lin

This entry was posted in Uncategorized and tagged , , , , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s