September 24, 1994

SECTION: Science, Pg. 14

LENGTH: 1374 words

HEADLINE: Bathroom tiling to drive you mad

BYLINE: IAN STEWART

BODY:

An American mathematician has come up with what is probably the strangest way ever of covering a floor or wall with tiles. The set of tiles which has been devised by Charles Radin of the University of Texas at Austin can only be assembled in a highly complex way (Annals of Mathematics, vol 109, p 661).

The usual way of assembling tiles is in a periodic pattern, one that starts with a basic unit, which is repeated at regularly spaced intervals. However, more complex patterns of tiling are perfectly possible and the subject of aperiodic tilings was created by the philosopher Hao Wang in 1961. Wang was studying the existence or otherwise of certain 'decision procedures' in mathematical logic - ways of working out in advance whether certain problems have solutions - when he came to the surprising conclusion that the problem could be reformulated in terms of tiles.

Choose a finite collection of shapes and call them prototiles. A tiling is then a way to assemble perfect copies of those prototiles so that they cover the entire infinite plane without any gaps or overlaps. Wang discovered that he could design prototiles that corresponded to various logical statements, in such a way that the rules for fitting prototiles together corresponded exactly to the rules of logical deduction. So, in effect, a tiling pattern corresponded to a logical proof. This new viewpoint led Wang to ask whether there existed a set of prototiles that could tile the plane, but could not tile it periodically.

Tiling a plane aperiodically turns out to be easy. It can be done with a single domino-shaped prototile. First, however, it is necessary to tile the plane with squares. Then each square is divided into two dominos by splitting it in half in either the vertical or horizontal direction. If the pattern of verticals and horizontals is aperiodic, so too is the tiling: the easiest method is to vary the directions randomly. However, dominos can also tile the plane periodically - for example, by making all splits point the same way.

Wang wanted something much more subtle: a set of prototiles that produced only aperiodic tilings. Such a set of tiles was found in 1966 by his student Robert Berger. The best known of such sets are the Penrose tilings, introduced by Roger Penrose of the University of Oxford in 1977; these produce tilings with fivefold 'almost' symmetries.

Radin notes that: 'All published examples . . . have the feature that in every tiling each prototile only appears in finitely many orientations.' For instance, dominos can be laid down horizontally or vertically but not oriented at any other angle; and Penrose tiles rotate only through multiples of an angle of 36 degree. This means that if the set of prototiles is expanded so that it includes a copy of each prototile in each orientation, then the new prototiles can tile the whole plane without being rotated. Only translations of these 'oriented prototiles' are then needed.

Radin's new discovery is a set of prototiles that are forced to appear in an infinite number of orientations. Because periodic tilings involve only a finite num-ber of directions - the ones in the basic repeating unit - Radin's tilings are necessarily aperiodic.

His starting point is an idea thought up by John Horton Conway of Princeton University in New Jersey. Begin with a 'half-domino' prototile, a right triangle of sides 1 and 2 units (whose hypotenuse is 5 units). This can be surrounded by four copies of itself in order to create a triangle of the same shape, but larger and rotated through an angle (see Figure). The process can be thought of as defining a 'level-l' tiling of part of the plane with five triangular tiles. The construction can now be repeated, surrounding the level-1 set of five tiles with four copies of those sets to make an even larger and further rotated triangle that is composed of 25 of the original prototiles: this is known as the level-2 tiling.

Continuing this 'expansion' process indefinitely from each level to the next leads to a strange, random-looking tiling of the infinite plane by half-dominos (see Figure), called the Conway tiling. Because the angle of rotation at each stage does not exactly divide into an integer number of full turns, the half-domino appears in an infinite number of different orientations throughout the plane.

However, this particular prototile can also tile the plane periodically. This can be done if two half-dominos are stuck together to make a domino and the plane is tiled periodically with those. To eliminate these periodic possibilities, Radin modifies the construction so that certain features of the Conway tiling, in particular its hierarchical structure into levels, cannot be avoided.

The essential idea is an old one: the edges of prototiles can be 'labelled' with marks or symbols, with the extra rule that adjacent tiles must have matching labels along their common edges. This produces a larger set of labelled prototiles with more restrictive tiling rules. The point is that the labels can be realised by making notches in the edges of one tile and adding protruding lugs to match them in the adjacent tile. By using a different shaped notch/lug pair for each symbol used as a label, we can convert labelled prototiles into ordinary ones of more complicated shapes.

It is, of course, easier to think about simple shapes that have labelled edges, and this is the way in which Radin proceeds. His prototiles are labelled half-dominos, and he invents a complicated range of different labels whose matching rules cleverly force the appearance of the same structure as the Conway tiling.

It is astonishing that such a simple shape as half a domino can have such curious implications, and it shows that even in today's complex world mathematics can still advance by looking at a simple idea in a new way.