American Scientist

Adventures in Group Theory: Rubik's Cube, Merlin's Machine, and Other Mathematical Toys. David Joyner. xviii + 262 pp. Johns Hopkins University Press, 2002. $69.95, cloth; $22.95, paper.

In 1974, a young Hungarian lecturer in interior design was contemplating an exercise he had given his students, namely to draw and study a cube bisected by its three mid-planes into eight smaller cubes. "How can I make the faces move?" he asked himself. Within a few weeks, Ernő Rubik had devised a more complicated version derived from a trisected cube, which soon became one of the greatest puzzle crazes of all time. It also was the most mathematically sophisticated toy ever produced, requiring and popularizing a branch of mathematics rarely seen in earlier mathematical toys, namely the theory of groups.

Since its development in the early 19th century, the notion of a group has become recognized as one of the archetypes of mathematical structure. Although its beginnings were in the field of algebra, a group is most clearly seen as a set of transformations of some object that preserve some aspect of its structure. For example, there are certain rigid motions of an unmarked cube—the 24 rotations about its various symmetry axes (including the null rotation by zero degrees) that leave it unchanged. One can combine these by doing first one motion, then another. If we denote these motions as A, B, C, ..., we denote the result of applying A, then B, as AB. Note that AB and BA may be quite different. For transformations, the "associative law" (AB)C = A(BC) naturally holds. The motion of doing nothing (that is, leaving the cube as it is), which we denote as I, acts as an "identity"—that is, AI = IA = A. Further, each motion A has an "inverse" motion A', such that AA' = A'A = I. These are the defining properties of a group. Groups are ubiquitous in mathematics—all the number systems have various group structures within them, and groups of transformations are the basic tool for the study of spaces and shapes.

Quite early in the study of Rubik's Cube, people realized that the terminology and tools of group theory are needed to understand it. It was the first mathematical toy to exemplify much of the theory of groups in a concrete way. One could actually hold a group in one's hand! Even experienced mathematicians found that they gained fresh insights into group theory as they struggled to solve the Cube and to make sense of what they were doing.

Numerous books about the Cube appeared from 1979 to 1986. Most of these were simple solution manuals, but a few authors tried (as I myself did in Notes on Rubik's Cube) to set forth the rich mathematical structure of the Cube. These works did not exhaust the subject; new ideas and findings have arisen, and many basic questions that were raised in the initial investigations remain unsolved.

David Joyner has been a Rubik's Cube enthusiast for many years. In Adventures in Group Theory: Rubik's Cube, Merlin's Machine, and Other Mathematical Toys, he brings the subject up to date and shows how group theory is used in related problems. Ostensibly, he starts with high school mathematics, introducing logic, set theory and algebra in the first two chapters, but a reader really needs to have met these ideas already to go over them at such speed.

Other chapters touch on such topics as bell ringing (an excuse to discuss permutations); the basics of group theory; "binary button puzzles" (arrays of buttons with associated lights that are toggled between on and off when you press the buttons); graph theory and the graph of Rubik's Cube (the set of all possible patterns, with a connection between two patterns if one is obtained from the other by a single move of the Cube); the symmetry of the Platonic solids; "illegal" moves of the Cube (which involve disassembling it); "conservation laws" followed by the Cube; the Fifteen Puzzle (a popular permutation puzzle with 15 numbered sliding blocks and one blank square that the blocks can slide into); card-shuffling; and a few of the many other Rubik-like puzzles.

Joyner gallops through a vast amount of material, giving at least two, if not three, semesters of undergraduate mathematics a once-over, with many proofs omitted. In group theory he gets up to wreath products; material on linear algebra, finite fields and computational complexity is also covered. Generally he introduces topics by giving examples first, but sometimes he is keen to get on with the theory and whizzes through rather more theory than necessary for the understanding of the puzzles being studied.

The principal unsolved problem of Cube theory is finding the maximum number of moves to restore a Cube to its initial or solved state. This is called the length of "God's Algorithm," or the diameter of the graph of the Cube. (A "move" may be a single quarter-turn of a face, or it may be what is called a face turn—that is, either a quarter-turn or a half-turn of a single face. Turning the entire Cube or other kinds of moves may also be permitted.) So far as we understand, determining this requires examining something like all the positions of the Cube, and there are 43,252,003,274,489,856,000 (or ≈ 4.3 X 10¹⁹) such patterns. If we could examine one pattern every microsecond, this would take about 1.4 million years. Since there are many millions of computers and computer speed is still increasing significantly, this computation is now approaching feasibility, and I suspect the answer will be known by 2010 or 2020. At present, we know there are solution methods that take at most 29 face turns or at most 42 quarter-turns, and there is a position that takes 21 face turns or 26 quarter-turns. For simpler puzzles that have been completely solved, there are very few starting positions that require the maximum number of moves to solve. For the Cube, it is quite possible that only 24 or 48 positions are "antipodal" to the solved position, and we will have to do a lot of searching to find these. Surprisingly, the diameter of the graph of the Fifteen Puzzle, which is much simpler than Rubik's Cube, also remains unknown.

Adventures in Group Theory grew out of Joyner's lecture notes. This fact, in combination with the great range of material covered, has resulted in occasional disjointedness of the narrative and a number of misprints, missing references and the like, which will strain a nonexpert reader.

Nonetheless, Joyner does convey some of the excitement and adventure in picking up knowledge of group theory by trying to understand Rubik's Cube. Enthusiastic students will learn a lot of mathematics from this book but must have the sense to skip bits which get too hard and return to them later or discuss them with others.—David Singmaster, Mathematics, South Bank University, London