Tiling to infinity: the surprising solution to a tiling problem provides new insights into unusual forms of crystal growth.

Tiling to Infinity

In its simplest form, a tiling problem in mathematics is not unlike the practical task of covering a floor or wall with ceramic tiles. Square tiles, for instance, fall into neat rows and columns to fill an area of any size. In contrast, tiles in the shape of pentagons leave gaps that can't be filled.

In the mid-1970s, mathematical physicist Roger Penrose of Oxford University in England found he could assemble tiles shaped like fat and skinny diamonds into patterns that fill any area yet don't repeat themselves at regular intervals. Like pentagons, the resulting tiling patterns have a fivefold symmetry. Unlike pentagons, the diamond tiles, when properly placed, leave no gaps.

Initially just a playful creation, Penrose's tilings took on added significance with the unexpected discovery of crystalline materials showing evidence of fivefold symmetry (SN: 3/23/85, p.188). Penrose's tilings, with their intriguing blend of order and disorder, became a simple geometric model for how groups of atoms may be arranged within these novel materials, now known as quasicrystals.

However, the Penrose model had a serious flaw. His tiling scheme requires fitting the diamond tiles together in specific ways. These matching-edge rules, indicated by arrows on the tiles (see diagram), specify which sides and vertices are allowed to meet. But the rules aren't sufficient to guarantee that any number of tiles will fit together to create a flawless pattern. It's easy to place a tile properly yet run into trouble many moves later -- ending up with a gap that tiles of neither shape can fill. That makes it hard to picture how atoms or molecules, influenced largley by their nearest neighbors, would have enough information to arrange themselves into such patterns on a large scale.

This led most physicists interested in the problem to consider alternative models for quasicrystalline materials. Many who studied the Penrose tilings concluded no such rules would be found.

Last year, George Y. Onoda, a ceramics expert at the IBM Thomas J. Watson Research Center in Yorktown Heights, N.Y., took up the challenge. "I didn't know that you weren't supposed to be able to do this," he says.

Onoda started playing with a pile of about 200 diamond-shaped tiles. With practice, he found that, by eye, he could put together flawless structures using up all his tiles. He developed a list of empirical rules for "growing" perfect tilings. For example, fat tiles always seemed to end up in chains or rings. Skinny tiles were by themselves or in pairs.

Onoda demonstrated his scheme to quasicrystal theorist Paul J. Steinhardt of the University of Pennsylvania in Philadelphia and an IBM colleague, David P. DiVincenzo, who had experience in using computers to study tilings. Steinhardt and DiVincenzo helped Onoda convert his long laundry list of visual rules into a simple statement about vertices -- a catalog of the eight ways in which tiles can be allowed to meet at a vertex (see diagram). These constraints include but go beyond Penrose's original edge rule.

In this scheme, a new tile can be added to an edge of a given cluster of tiles only if each shared vertex matches one of the eight allowed arrangements. Tiles are placed first wherever there is only one possible way to complete a vertex not yet entirely surrounded. Such "forced" moves can be done in any order. If there are no forced moves available, then a fat or a skinny tile, consistent with the vertex rule, is added to a randomly chosen edge.

"I thought that Onoda's scheme would fail if the tiling got big enough," says DiVincenzo. "But to our surprise, when we put it on the computer, it ran as long as anyone would like."

Steinhardt and a student, Joshua E.S. Socolar, now at Harvard University, worked out a mathematical proof that these rules, with one exception, are sufficient to guarantee the creation of perfect Penrose tilings of any size. The exception arose when Socolar discovered in his mathematical proof that with more than 2.sup.50 tiles -- a number much larger than any computer can handle -- a rare combination of random selections during unforced moves could lead to a tiling defect. That required a small rule changes: In an unforced move, tiles can't be placed randomly. Instead, a fat tile must be added to either side of any 108 [deg.] corner. The rules and proof appear in the June 20 PHYSICAL REVIEW LETTERS.

"It was a complete surprise to us that we ended up with rules that worked perfectly" Steinhardt says. "Nobody expected this. It seemed to be totally counterintuitive."

The discovery suggests a hos of new mathematical questions and scientific possibilities. For example, "the results provide new insights as to how materials with only short-range atomic interactions can grow large, nearly perfect quasicrystal grains," the researchers say.

In ordinary crystal growth, some crystal surfaces are known to have sites that are "stickier" than others, encouraging atoms or molecules to settle in those locations rather than others. Steinhardt suggests that if any quasicrystalline systems mimic the kind of growth rules now known for Penrose tilings, then these materials may have sticky and nonsticky sites corresponding to the forced and unforced moves in the Penrose model.

If that model holds, then the most common approach for growing quasicrystals -- solidifying the molten alloy quickly, then slowly heating the solid to get larger crystals with fewer defects -- is inappropriate. "We should be trying to do the quenching as slowly as possible," says Steinhardt, to give the atoms more time to find the "sticky" spots. "You'd like to have a grain isolated in a liquid to give it a chance to grow."

Steinhardt and his colleagues also discovered it is possible to build a practically perfect Penrose tiling if the pattern starts around a particular kind of defect -- an unfillable void at the pattern's core. With such a defect, all moves are forced, and the tiling pattern proceeds flawlessly to infinity.

"What that means physically is that if one of these defects is present, the growing crystal will always have sticky points on its surface," says Steinhardt. "If you could isolate one of these defects, it would be a great feature around which to grow quasicrystals quickly."

The researchers want to generalize their rules to other tilings with fivefold symmetry, to tilings with eightfold and twelvefold symmetries and into three dimensions. So far, that task has proved surprisingly difficult.

"We're still at the stage of having to begin with empirical rules," Steinhardt says. "We don't have a firm grasp of what the essential features are."

Says DiVincenzo, "I get the feeling that there's some branch of mathematics we need to do this kind of work, but we don't know what it is yet." It's like working with compass and straightedge in an age of computers.