‘Kissing’ tetrahedra break world record

PRINCETON (US)—Scientists have set a world record for how many tetrahedra they can jam into a confined space. The mathematical breakthrough could result in better ways to store data on compact discs as well as a better understanding of matter itself.

In the cover story of the Aug. 13 issue of Nature, Salvatore Torquato, a chemistry professor at Princeton University, and Yang Jiao, a graduate student in the Department of Mechanical and Aerospace Engineering, report that they have bested the world record, set last year by Elizabeth Chen, a graduate student at the University of Michigan.

Using computer simulations, Torquato and Jiao were able to fill a volume to 78.2 percent of capacity with tetrahedra. Chen, before them, had filled 77.8 percent of the space. The previous world record was set in 2006 by Torquato and John Conway, a Princeton professor of mathematics. They succeeded in filling the space to 72 percent of capacity.

Beyond setting a new world record, Torquato and Jiao have devised an approach that involves placing pairs of tetrahedra face-to-face, forming a “kissing” pattern that, viewed from the outside of the container, looks strangely jumbled and irregular.

“We wanted to know this: What’s the densest way to pack space?” says Torquato, who is also a senior faculty fellow at the Princeton Center for Theoretical Science. “It’s a notoriously difficult problem to solve, and it involves complex objects that, at the time, we simply did not know how to handle.”

Henry Cohn, a mathematician with Microsoft Research New England in Cambridge, Mass., says: “What’s exciting about Torquato and Jiao’s paper is that they give compelling evidence for what happens in more complicated cases than just spheres.”

The Princeton researchers, he adds, employ solid figures as a “wonderful test case for understanding the effects of corners and edges on the packing problem.”

Studying shapes and how they fit together is not just an academic exercise. The world is filled with such solids, whether they are spherical oranges or polyhedral grains of sand, and it often matters how they are organized.

Real-life specks of matter resembling these solids arise at ultra-low temperatures when materials, especially complex molecular compounds, pass through various chemical phases. How atoms clump can determine their most fundamental properties.

“From a scientific perspective, to know about the packing problem is to know something about the low-temperature phases of matter itself,” explains Torquato.

The whole topic of the efficient packing of solids is a key part of the mathematics that lies behind the error-detecting and error-correcting codes that are widely used to store information on compact discs and to compress information for efficient transmission around the world.

Beyond solving the practical aspects of the packing problem, the work contributes insight to a field that has fascinated mathematicians and thinkers for thousands of years. The Greek philosopher Plato theorized that the classical elements—earth, wind, fire, and water—were constructed from polyhedra. Models of them have been found among carved stone balls created by the late Neolithic people of Scotland.

The tetrahedron, which is part of the family of geometric objects known as the Platonic solids, must be packed in the face-to-face fashion for maximum effect. But, for significant mathematical reasons, all other members of the Platonic solids, the researchers found, must be packed as lattices to cram in the largest quantity, much the way a grocer stacks oranges in staggered rows, with successive layers nestled in the dimples formed by lower levels. Lattices have great regularity because they are composed of single units that repeat themselves in exactly the same way.

There’s a good reason why tetrahedra must be packed differently from other Platonic solids, according to the authors. Tetrahedra lack a quality known as central symmetry. To possess this quality, an object must have a center that will bisect any line drawn to connect any two points on separate planes on its surface. The researchers also found this trait absent in 12 out of 13 of an even more complex family of shapes known as the Archimedean solids.

The conclusions of the Princeton scientists are not at all obvious, and it took the development of a complex computer program and theoretical analysis to achieve their results. Previous computer simulations had taken virtual piles of polyhedra and stuffed them in a virtual box and allowed them to “grow.”

The algorithm designed by Torquato and Jiao, called “an adaptive shrinking cell optimization technique,” did it the other way. It placed virtual polyhedra of a fixed size in a “box” and caused the box to shrink and change shape.

There are tremendous advantages to controlling the size of the box instead of blowing up polyhedra, Torquato says. “When you ‘grow’ the particles, it’s easy for them to get stuck, so you have to wiggle them around to improve the density,” he adds. “Such programs get bogged down easily; there are all kinds of subtleties. It’s much easier and productive, we found, thinking about it in the opposite way.”

Many researchers have pointed to various assemblies of densely packed objects and described them as optimal. The difference with this work, Torquato notes, is that the algorithm and analysis developed by the Princeton team most probably shows, in the case of the centrally symmetric Platonic and Archimedean solids, “the best packings, period.”

Their simulation results are also supported by theoretical arguments that the densest packings of these objects are likely to be their best lattice arrangements. “This is now a strong conjecture that people can try to prove,” Torquato says.

The research was supported by the National Science Foundation.

Princeton University news: www.princeton.edu/main/news