A Tight Squeeze - Mathematical Physics

Vol 460|13 August 2009

NEWS & VIEWS MATHEMATICAL PHYSICS

A tight squeeze Henry Cohn

How can identical particles be crammed together as densely as possible? A combination of theory and computer simulations shows how the answer to this intricate problem depends on the shape of the particles. We all know from experience with luggage just how difficult it is to pack objects efficiently into a limited space. These difficulties are even greater when huge numbers of objects, such as grains of wheat, are involved. From Luke the evangelist’s reference to “a good measure, pressed down, shaken together and running over” all the way to modern disclaimers that contents may have settled during shipping, nobody has been able to analyse how to achieve the densest possible packings. On page 876 of this issue, Torquato and Jiao describe1 remarkable computer-simulation results that show how subtle this problem can be, while offering new hope for understanding important cases. Identical, perfect spheres are among the simplest objects to pack. It is not difficult to guess how — just look at the way cannonballs are stacked at war memorials. But theoretical analysis of the problem presents profound difficulties that were overcome only recently by Thomas Hales2, nearly four centuries after the answer was conjectured by Johannes Kepler3. Of course, most granular materials do not consist of spherical grains, and this complicates matters tremendously. For most grain shapes we cannot guess or even closely approximate the answer, let alone prove it, and it is difficult to develop even a qualitative understanding of the effects of grain shape on packing density. Instead of perfect spheres, Torquato and Jiao study1 packings of the five Platonic solids: the tetrahedron, cube, octahedron, dodecahedron and icosahedron (see Fig. 1 on page 877). These are the simplest and most symmetrical polyhedra. Needless to say, nobody expects the grains in physical materials to have these precise shapes, but they are a beautiful test case for understanding the effects of corners and edges and the role of symmetry. The cube-packing problem is easy — cubes can fill space completely. But the densest packings of the other Platonic solids are much less obvious. They do not tile space — fill space with no gaps or overlaps — despite Aristotle’s incorrect assertion4 that tetrahedra do. In their simulations, Torquato and Jiao find a striking difference between two cases: the octahedron, dodecahedron and icosahedron have central symmetry (that is, each remains

a

b

Figure 1 | Two-dimensional view of packings. a, In a two-dimensional Bravais lattice packing, there is one particle per lattice cell, and the particles are all aligned with each other. In this illustration, the particle is represented by a triangle and is located in the upper left corner of the cell. b, In a general, non-Bravais lattice packing, there are multiple particles per cell, and they can be arbitrarily rotated. In their computer simulations, Torquato and Jiao1 show that the best packings of centrally symmetric Platonic solids turn out to be Bravais lattice packings, which is remarkable given how restricted such packings are.

unchanged by a 180° rotation about a point at its centre). But the tetrahedron does not have central symmetry, and this turns out to be the crucial distinction. In the centrally symmetric cases, Torquato and Jiao show that the highest-density packings belong to the simplest kind, called Bravais lattice packings (Fig. 1a), although this constraint is never directly imposed on their simulations. In such arrangements, all the particles are perfectly aligned with each other, and the packing is made up of lattice cells that each contain only one particle. The densest Bravais lattice packings had been determined previously 5,6, but it had seemed implausible that they were truly the densest packings, as Torquato and Jiao’s simulations and theoretical analysis now suggest. By contrast, for the tetrahedron it has long been known that Bravais lattice packings are far from optimal, and in this case the authors achieve a record density: they find a non-Bravais lattice configuration (Fig. 1b) that fills up 78.20% of the space available (an improvement over the previous record7 of 77.86%, or 36.73% for Bravais lattices8). To find their packings, Torquato and Jiao © 2009 Macmillan Publishers Limited. All rights reserved

use a powerful simulation technique. Starting with an initial guess at a dense packing, they gradually modify it in an attempt to increase its density. In addition to trying to rotate or move individual particles, they also perform random collective particle motions by means of deformation and compression or expansion of the lattice’s fundamental cell. With time, the simulation becomes increasingly biased towards compression rather than expansion. Allowing the possibility of expansion means that the particles are initially given considerable freedom to explore different possible arrangements, but are eventually squeezed together into a dense packing. The new tetrahedron packing is a variant of an ingenious construction found by Chen last year7. Using physical models, she observed that tetrahedra pack well when arranged in a form Torquato and Jiao call ‘wagon wheels’: wheels of five tetrahedra sharing an edge, with the wheels joined in pairs at right angles (see Fig. 3a on page 878). How best to arrange these pairs of wagon wheels is not clear, but Chen used a computer algebra system (a software program that manipulates mathematical formulae) 801

NEWS & VIEWS

to optimize their placement and achieved a density of 77.86%, which is a vast improvement over the previous record9 of 71.75%. The authors’ simulations1 suggest that Chen’s solution was nearly, but not quite, optimal. Although Torquato and Jiao’s improvement on Chen’s packing is noteworthy, perhaps the most intriguing implication of their work is the apparent optimality of Bravais lattice packings for the centrally symmetric Platonic solids (as well as generalizations such as Archimedean polyhedra). This part of the work may seem less exciting, because the densest packings turned out to be known already. However, in a field with few clear organizing principles, this latest insight into the part played by symmetry might take on the role of a twenty-first-century Kepler conjecture. It will surely inspire many future research papers, and with any

NATURE|Vol 460|13 August 2009

luck we won’t have to wait 400 years for a full understanding of it. ■ Henry Cohn is at Microsoft Research New England, One Memorial Drive, Cambridge, Massachusetts 02142, USA. e-mail: [email protected] 1. Torquato, S. & Jiao, Y. Nature 460, 876–879 (2009). 2. Hales, T. C. Ann. Math. 162, 1065–1185 (2005). 3. Kepler, J. Strena Seu de Nive Sexangula [A New Year’s Gift of Hexagonal Snow] (Godfrey Tampach, 1611). 4. Aristotle On the Heavens Book III, Pt 8 (transl. Guthrie, W. K. C.) (Harvard Univ. Press, 1939). 5. Minkowski, H. Nachr. Akad. Wiss. Göttingen Math. Phys. Kl. II, 311–355 (1904). 6. Betke, U. & Henk, M. Comput. Geom. 16, 157–186 (2000). 7. Chen, E. R. Discrete Comput. Geom. 40, 214–240 (2008). 8. Hoylman, D. J. Bull. Am. Math. Soc. 76, 135–137 (1970). 9. Conway, J. H. & Torquato, S. Proc. Natl Acad. Sci. USA 103, 10612–10617 (2006).

STEM CELLS

Escaping fates with open states Robert J. Sims III and Danny Reinberg The ability of embryonic stem cells to give rise to any cell type relies on a remodelling protein that maintains open chromatin. But the chromatin landscape of these cells may be more complex than previously thought. Embryonic stem (ES) cells are ideal models for studying the molecular principles that dictate cell fate. ES cells can self-renew and form every type of cell in an organism — a property called pluripotency. It is well established that DNAbinding proteins set the stage for determining cell-type specificity by orchestrating complex patterns of gene expression1. However, DNA is tightly assembled with accessory proteins into a structure called chromatin, which limits its accessibility to regulatory proteins. Chromatin can be loosely packed, or ‘open’, allowing DNA-binding proteins ready access to the genome. Alternatively, it can be densely compacted, or ‘closed’, making the DNA relatively inaccessible2. On page 863 of this issue, Gaspar-Maia et al.3 provide evidence that chromatin structure is intimately connected with cell fate by showing that highly accessible chromatin is essential for the unique properties of stem cells. ES cells have to achieve a delicate balance of gene regulation: they must suppress genes that result in premature differentiation, while maintaining expression of genes that allow self-renewal. Previous work4,5 has shown that ES cells maintain an open chromatin structure and express a large proportion of their genes. Differentiation of ES cells into mature cell types, such as neural cells, is accompanied by closing of chromatin4 and by widespread gene silencing5. As chromatin structure strongly dictates whether or not genes can be expressed, Gaspar-Maia and colleagues3 examined the 802

role of enzymes that can modify this structure in keeping ES cells pluripotent. The authors found that decreasing the amounts of a chromatin-remodelling protein called Chd1 impaired ES-cell proliferation and reduced expression of the DNA-binding transcription factor Oct4, which is a master regulator of ES-cell function. Chd1 has previously been shown to facilitate gene expression6, consistent with its role in Oct4 regulation. However, in this case3 its depletion did not result in a global decrease in gene activity, as would be expected for a factor widely associated with active gene transcription. Instead, ES cells lacking Chd1 upregulated the expression of genes involved in nervous-system development, and they tended to differentiate into cells of the neuronal lineage3. Whether chromatin structure is accessible or compact is determined in part by chemical modification of its core protein components, histones. For example, trimethylation of lysine 4 on histone H3 (H3K4me3) is a marker of open chromatin. Chd1 contains a motif that recognizes H3K4me3 (refs 7, 8) and indeed, when Gaspar-Maia and colleagues performed genome-wide studies of Chd1 localization on chromatin in normal ES cells, they found that Chd1 co-localizes with H3K4me3. When the authors depleted ES cells of Chd1, they observed an increase in the proportion of condensed chromatin in these cells. On the basis of their results, they surmise that Chd1 maintains an open chromatin structure in ES cells, © 2009 Macmillan Publishers Limited. All rights reserved

which is required for their pluripotency. The interplay between Chd1, H3K4me3 and open chromatin (Fig. 1) highlighted by Gaspar-Maia and colleagues3 is reinforced by findings from other studies9–13. H3K4me3 is incorporated into chromatin during active transcription9; therefore, promotion of gene expression by Chd1 might ensure that chromatin is rich in H3K4me3 and maintained in an open conformation. Chd1 has also been shown10 to regulate DNA-replicationindependent deposition of chromatin enriched in H3K4me3. Moreover, binding of Chd1 to chromatin may protect H3K4me3 from turnover through histone demethylation. This histone mark also prevents the binding of factors that mediate gene silencing, such as the NuRD histone-modifying complex11,12 and the DNA methyltransferase subunit DNMT3L13. Loss of H3K4me3 would therefore allow increased chromatin compaction induced by NuRD and DNA methylation, highlighting the need to maintain a correct balance of H3K4me3. In addition, the histone methyltransferase Suv39H1 facilitates the formation of silent chromatin domains by methylating lysine 9 on histone H3. Suv39H1 is known to act on histones that lack methylated H3K4 (Fig. 1); thus, open chromatin would serve to counteract this repressive activity. What Gaspar-Maia and colleagues’ work3 does not explain is how, despite depletion of Chd1, global ES-cell gene activation is largely unaffected while genes that drive differentiation towards the neuronal cell fate are upregulated. It is possible, though, to reconcile these findings by taking into account Chd1-mediated regulation of the distribution of H3K4me3. For instance, the p400/TIP60 complex, which turns genes on or off by changing the composition of chromatin, also seems to bind H3K4me3 (ref. 14). When the amount of H3K4me3 is reduced in ES cells, binding of p400/TIP60 to its chromatin targets is impaired14. In this way, the perturbation of H3K4me3 in the absence of Chd1 could impair gene silencing through its effects on factors such as p400/TIP60. Although unusual for somatic cells (non-gametes), in ES cells, H3K4me3 may be associated with silencing of genes at focal locations throughout chromatin15. Alternatively, widespread gene reactivation could be a consequence of indirect effects of the downregulation of ES-cell master regulatory factors such as Oct4. Studying differentiated cells undergoing reprogramming to a pluripotent state16 allows insight into the core properties of stem-cell chromatin. Cells that fail reprogramming reactivate subsets of stem-cell-related genes, but simultaneously fail to repress lineage-specific transcription factors16. Thus, the correct mix of gene expression to achieve stem-cell properties may depend more on local alterations in chromatin structure than on global chromatin reorganization. Gaspar-Maia et al.3 show that Chd1 loss prevents the reprogramming of somatic