Packing tetrahedra

Last spring I saw a great colloquium talk on packing regular tetrahedra in space by Jeffrey Lagarias. He pointed out that in some sense the problem goes back to Aristotle, who apparently claimed that they tile space. Since Aristotle was thought to be infallible, this was repeated throughout the ages until someone (maybe Minkowski?) noticed that they actually don’t.

John Conway and Sal Torquato considered various quantitative questions about packing, tiling, and covering, and in particular asked about the densest packing of tetrahedra in space. They optimized over a very special kind of periodic packing, and in the densest packing they found, the tetrahedra take up about 72% of space.

Compare this to the densest packing of spheres in space, which take up about 74%. If Conway and Torquato’s example was actually the densest packing of tetrahedra, it would be a counterexample to Ulam’s conjecture that the sphere is the worst case scenario for packing.

But a series of papers improving the bound followed, and as of early 2010 the record is held by Chen, Engel, and Glotzer with a packing fraction of 85.63%.

I want to advertise two attractive open problems related to this.

(1) Good upper bounds on tetrahedron packing.

At the time of the colloquium talk I saw several months ago, it seemed that despite a whole host of papers improving the lower bound on tetrahedron packing, there was no upper bound in the literature. Since then Gravel, Elser, and Kallus posted a paper on the arXiv which gives an upper bound. This is very cool, but the upper bound on density they give is something like 1- 2.6 \times 10^{-25}, so there is still a lot of room for improvement.

(2) Packing tetrahedra in a sphere.

As far as I know, even the following problem is open. Let’s make our lives easier by discretizing the problem and we simply ask how many tetrahedra we can pack in a sphere. Okay, let’s make it even easier: the edge length of each of the tetrahedra is the same as the radius of the sphere. Even easier: every one of the tetrahedra has to have one corner at the center of the sphere. Now how many tetrahedra can you pack in the sphere?

It is fairly clear that you can get 20 tetrahedra in the sphere, since the edge length of the icosahedron is just slightly longer than the radius of its circumscribed sphere. By comparing the volume of the regular tetrahedron to the volume of the sphere, we get a trivial upper bound of 35 tetrahedra. But by comparing surface area instead, we get an upper bound of 22 tetrahedra.

There is apparently a folklore conjecture that 20 tetrahedra is the right answer, so proving this comes down to ruling out 21 or 22. To rule out 21 seems like a nonlinear optimization problem in some 63-dimensional space.

I’d guess that this is within the realm of computation if someone made some clever reductions. Oleg Musin settled the question of the kissing number in 4-dimensional space in 2003. To rule out kissing number of 25 is essentially optimizing some function over a 75-dimensional space. This sounds a little bit daunting, but it is apparently much easier than Thomas Hales’s proof of the Kepler conjecture. (For a nice survey of this work, see this article by Pfender and Ziegler.)

Coloring the integers

Here is a problem I composed, which recently appeared on the Colorado Mathematical Olympiad.

If one wishes to color the integers so that every two integers that differ by a factorial get different colors, what is the fewest number of colors necessary?

I might describe a solution, as well as some related history, in a future post. But for now I’ll just say that Adam Hesterberg solved this problem at Canada/USA Mathcamp a few summers ago, claiming the $20 prize I offered almost as soon as I offered it. At the time, I suspected but still did not know the exact answer.

Although the wording of the problem strongly suggests that the answer is finite, I don’t think that this is entirely obvious.

Along those lines, here is another infinite graph with finite chromatic number.

If one wishes to color the points of the Euclidean plane so that every two points at distance one get different colors, what is the fewest number of colors necessary?

This is one of my favorite unsolved math problems, just for being geometrically appealing and apparently intractably hard. After fifty years of many people thinking about it, all that is known is that the answer is 4, 5, 6, or 7. Recent work of Shelah and Soifer suggests that the exact answer may depend on the choice of set theoretic axioms.

This inspired the following related question.

If one wishes to color the points of the Euclidean plane so that every two points at factorial distance get different colors, do finitely many colors suffice?

More generally, if S is a sequence of positive real numbers that grows quickly enough (say exponentially), and one forbids pairs points at distance s from receiving the same color, one would suspect that finitely many colors suffice. On the other hand, if S grows slowly enough (say linearly), one might expect that infinitely many colors are required.

RIP Martin Gardner

Martin Gardner passed away yesterday, at 95; here is the NYTimes obituary.

I grew up with his puzzles and mathematical recreations, as I’m sure many mathematicians of my generation (and generations before) did. I am reminiscing this evening about interesting topics that Gardner introduced me to, and the following geometric gem comes to mind. The problem was apparently first proposed by Henri Lebesgue in 1914 and is still open, so it is almost 100 years old now.

Question: Find a universal cover C of least area in the plane, meaning a set having a subset congruent to every planar set of unit diameter.

If one restricts to convex C, then such a minimum is guaranteed to exist by the Blaschke selection theorem, a compactness result for sequences of bounded convex sets. A hexagon of unit width does the trick, but surprisingly, one can take off tiny pieces and still have a universal cover.

No one has ever exhibited such a minimum with proof, although there have been a few false claims of optimal solutions. I just searched and found an amusing 1992 Geometriae Dedicata article by H. C. Hansen in which the author shaves 4 \times 10^{-11} off the then reigning world record. I am not sure if anyone has improved on this result since, but this might be a fun thing to think about; indeed, Hansen suggests in the article how computers might help solve the problem, and computers have come a long way since 1992.

Gardner’s name came up in conversation just the other day. Tom Rokicki came to talk to my Rubik’s Cube class at Stanford about his work on “God’s algorithm” — Tom set a world record recently by proving that every Rubik’s Cube, no matter how scrambled, can be solved in 22 or fewer face turns. I asked him how long it would be until we have a proof of the conjectured answer of 20. He said he thought he might have 21 in the next few months, and then said that he wanted to have it down to 20 moves by Gathering for Gardner 2012. I hope that the Gatherings for Gardner continue, and it would be nice to see Tom succeed in his goal too.

I am not sure if anyone in history has ever made more people smile and shake their head about mathematical things than Martin Gardner. His writings illuminated it’s magical and mysterious qualities. Gardner was also famous as skeptic and a debunker, like many magicians before him. The NYTimes obituary reports:

He ultimately found no reason to believe in anything religious except a human desire to avoid “deep-seated despair.” So, he said, he believed in God.

Well godspeed to you Martin, and thanks for all the wonderful writings and beautiful thoughts.

Francisco Santos disproves Hirsch conjecture

The Hirsch conjecture has been around for over 50 years. The conjecture states that a d-dimensional polytope with n facets has diameter at most n-d. (The facets of a polytope are the maximal dimensional faces (i.e. the (d-1)-dimensional faces), and saying that the diameter is at most n-d is just saying that every pair of vertices can be connected by a path of length at most n-d.)

The upper bounds on diameter are very far away from n-d; in fact no bound that is even polynomial (much less linear) in n and d is known. It was considered substantial progress when Gil Kalai got the first subexponential upper bounds. This fact led many to speculate that the conjecture is false, and apparently Victor Klee encouraged many people to try disproving it over the years.

Francisco Santos has just announced an explicit counterexample to the Hirsch conjecture, in dimension d = 43 with n =86 facets. Details to be described at the Grünbaum–Klee meeting in Seattle this summer.

To researchers on polytopes, this result may not be too surprising. Nevertheless, it is an old problem and it is nice to see it finally resolved. And there is something pleasing about finding explicit counterexamples in higher dimensional spaces. It offers a concrete way to see how bad our intuition for higher dimensions really is. Kahn and Kalai’s spectacular counterexample to “Borsuk’s conjecture” (in dimension d = 1325) comes to mind. I look forward to seeing the details of Santos’s construction.

Many Markov components

In my recent preprint, I showed that once r \ge c / n the Metropolis Markov chain on configurations of hard discs is no longer ergodic. In particular, even for reasonably small radius there are stable configurations of discs. In this note the goal is to make a more quantitative statement about the number of Markov components in particular when r > c_2 / \sqrt{n} (which is the usual range of interest in statistical mechanics.

For the main construction, start with the following configuration of 24 discs in a square. (It is not relevant to the following discussion, but it is fun to point out that this is the densest packing of 24 equal sized discs in a square.)

This configuration of 24 discs is easily seen to be stable (meaning that each disc is individually held in place by its neighboring discs and the boundary of the square), and in fact it is still stable if we delete a carefully chosen set of four discs as follows.

By stacking k^2 of these together one has stable configurations with 20 k^2 discs.

Finally one can add discs in any of the “holes” in these kinds of configurations, leading to more and more possibilities for stable configurations. For example, here is one of the {36 \choose 18} \approx 9.08 \times 10^9 possibilities for dropping discs in 18 of the 36 holes in the previous illustration.

By continuing constructions like this for larger and larger k we observe two facts.

(1) As n \to \infty the number of components can grow quite fast. To make this quantitative we expand on the example. Suppose there are 20 k^2 discs to start out, then there are 4 k^2 holes. Suppose we drop 2 k^2 discs into those holes. Then the number of discs n = 22 k^2 in total, and then the number of Markov components is at least {4 k ^2 \choose 2 k^2 } = { 2n/11 \choose n/11 }. (This is for unlabeled discs. For labeled discs, multiply this by n!.) By Stirling’s formula, this number grows exponentially fast in n (something like 1.134^n).

In this particular example the discs have total area \pi r^2 n = \approx 0.67, but that could obviously adjusted by changing the ratio of extra discs to holes.

(2) For every \lambda \in (0.60, 0.75) there is an \alpha = \alpha(\lambda) > 1 and a sequence of configurations C_1, C_2, \ldots with C_i \in Config(i, r(i)), the number of Markov components greater than \alpha ^ i for sufficiently large i, and \pi r^2 n \to \lambda as i \to \infty.

It turns out that what are described here are only separate components in the sense that a Markov chain that only moves one disc at a time can not mix from one state to the other. (The four discs in the center of a square can rotate about the center of the square!) But a small modification of this construction would seem to give exponentially many components in the sense of \pi_0, each with small positive measure.

Is exponentially many components the maximal possible? The Milnor-Thom Theorem gives an upper bound much larger than this, something like O(e^{c n^2}) for some c > 0. It would also be very interesting to know any bounds on the topological complexity of these path components.

A young person’s guide to the Hopf fibration

I enjoyed this recent arXiv post by Zack Treisman, apparently notes for a summer course for high school students he taught. It leads a beginning mathematician by discovery through the basics of arithmetic of complex numbers, higher dimensional geometry, a word or two on knot theory, and then onto the main topic: the Hopf fibration. I wish someone had told me about these things when I was in high school.

Thanks to several beautiful illustrations by Lun-Yi Tsai and Zack’s charming writing style, it is fun to flip through for mathematicians who are already familiar with these ideas as well. I hope Zack and Lun-Yi make a coffee table book one day.


The foolproof cube – a study in symmetry

Besides being a fun toy, and perhaps the most popular puzzle in human history, the Rubik’s Cube is an interesting mathematical example. It provides a nice example of a nonabelian group, and in another article I may discuss some features of this group structure. This expository article is about an experiment, where I made Rubik’s cubes with two or three colors, instead of six. In particular, I want to mention an interesting observation made by Dave Rosoff about one of the specially colored cubes: It turns out to be foolproof, in the sense that no matter how one breaks it apart and reassembles the pieces, it is still solvable by twisting the sides. It is well known that this is not a property that stock Rubik’s Cubes have.

The first observation about the physical construction of the cube is that it is made out of 21 smaller plastic pieces: a middle piece with 6 independently spinning center tiles, 12 corner cubies, and 8 edge cubies.  The frame includes 6 of the stickers. Each corner cubie has 3, and each edge cubie has 2. (And this accounts for all of the 6 \times 9 =54 = 6+ 12 \times 3 + 8 \times 2 stickers. These stickers are on a solid piece of plastic, so they always stay next to each other, no matter matter how much you scramble it by twisting the sides. (I remember getting really mad as a kid, after figuring out that someone else had messed around with the stickers on my cube. Still a pet peeve, taking stickers off a cube is like fingernails on a chalkboard for me.)

So anyway, it’s impossible to get two yellow stickers on the same edge cubie, for example, because that would make the cube impossible to solve: you couldn’t ever get the two stickers onto the same side. But this is not the only thing that can’t happen. Let’s restrict ourselves from now on to just the positions you can get to by taking the cube apart into plastic pieces, and putting them back together. If you take it apart, and put it back together randomly, will you necessarily be able to solve it by only twisting sides? (Of course you can always solve it by taking it back apart and putting it back together solved!) I knew, empirically, as a kid that you might not be able to solve it if you put it together haphazardly. Someone told me in high school that if you put it together “randomly,” your chances that it was solvable were exactly 1 in 12, and explained roughly why: it is impossible to flip an edge (gives a factor of 2), rotate a corner (a factor of 3), or to switch any two cubies (another factor of 2).

This seemed plausible at the time, but it wasn’t until a graduate course in algebra that I could finally make mathematical sense of this. In fact, one of the problems on the take-home final was to prove that it’s impossible to flip any edge (leaving the rest of the cube untouched!), through any series of twists. I thought about it for a day or two, and was extremely satisfied to finally figure it out, how to prove something that I had known in my heart to be true since I was a kid. It is a fun puzzle, and one can write out a proof that doesn’t really use group theory in any essential way (although to be fair, group theory does provide a convenient language, and concise ways of thinking about things). For example, it is possible to describe a number 0 or 1 to every position, such that the number doesn’t change when you twist any side (i.e. it is invariant). Then provided that the property prescribes a 0 to a solved cube and a 1 to a cube with a flipped edge, the invariance gives  that the flipped edge cube is unsolvable.

Several years ago, I got inspired to try different colorings of a Rubik’s Cube, just allowing some of the sides to have the same color. I was picky about how I wanted to do it, however. Each color class should “look the same,” up to a relabeling. A more precise way to say this is that every permutation of the colors is indistinguishable from some isometry. (Isometries of the cube are its symmetries: reflections, and rotations, and compositions of these. There are 48 in total.)

It turns out that this only gives a few possibilities. The first is the usual coloring by 6-colors. Although there are several ways to put 6 colors on the faces of a cube,  for our purposes here there is really only one 6-color cube. There is also the “Zen cube,” with only one color. (“Always changing, but always the same.”) But there are a few intermediate possibilities that are interesting. First, with two colors, once can two-color the faces of a cube in essentially two different ways. Note that since we want each color class to look the same, each color gets three sides. The three sides of a color class either all three meet at a corner, or they don’t. And these are the only two possibilities, after taking into account all of the symmetries.

So I bought some blank cubes and stickers, and made all four of the mathematically interesting possibilities. (I keep meaning to make a nice Zen cube, perhaps more interesting philosophically than mathematically, but I still haven’t gotten around to it. ) My friend Dave Rosoff and I played around with all of these, and found them somewhat entertaining. A first surprise was that they seem harder to solve than a regular Rubik’s cube. Seems like it should be easier, in terms of various metrics: the number of indistinguishable positions being much smaller, or equiavalently, the number of mechanical positions which are indistinguishable from the “true” solved position being much bigger. However in practice, what happens for many experience cube solvers, is that they get into positions that they don’t recognize at the end: the same-colored stickers seem to mask your true position. Nevertheless, an experienced solver can handle all four of these cubes without too much difficulty.

When playing around with them, occasionally a cubie would pop out fall to the floor. The thing to do is to just pop the piece back in arbitrarily, and the solve it as far as you can. It is usually an edge that pops, so the probability of having a solvable cube is 1/2.  And if not, one can tell at the end, and then remedies the situation by flipping any edge back. Dave noticed something special about one of these four cubes, I think just from enough experience with solving it: no matter which piece got popped out, when he popped it back in randomly, the cube still seemed to be solvable. He thought it seemed too frequent to be a coincidence, so after a while of chatting about it, we convinced ourselves that this cube indeed had a special property: if one takes it apart into its 21 pieces, and reassembles it arbitrarily, it is always solvable by twists, a property we described as, “foolproof.” We talked it about it for a while longer, and convinced ourselves that this is the only foolproof cube, up to symmetry and permuting colors. (Well, the Zen cube is foolproof too.)

So which of these four cubes is foolproof? This puzzle yields to a few basic insights, and does not actually require making models of each type of cube, although I would encourage anyone to do so who has extra blank cubes and stickers around, or who wants a neat Cube variant for their collection.