Sphere-Packing

Is there a way to pack more than 4 disks of diameter 1 into a 2-by-2 square?

Obviously not. But is there a way to pack more than 4000 disks of diameter 1 into a 2-by-2000 rectangle?

Again, obviously not — except that there is a way! (See my essay “Believe It, Then Don’t” for details.) So packing problems can be tricky.

If you’re packing equal-size disks into a large region, it’s intuitive that the best way to pack them is six-around-one. This is the hexagonal packing, and László Fejes Tóth showed in 1940 that it’s the best way to pack the infinite plane. Here the word “best” needs to be unpacked (pardon the pun), since both the hexagonal packing and the square packing fit infinitely many disks into the plane.

The way in which the hexagonal packing beats the square packing is that the former fills about 91% of the plane (more precisely π sqrt(3) / 6) while the latter fills only about 79% of the plane (more precisely π/4). That is, the hexagonal packing has a larger packing fraction. To compute the packing fraction of the square packing, divide the plane into 2r-by-2r squares where r is the radius of the disks.

Each square has area (2r)² = 4r² and contains a disk of area πr², so the packing fraction in each square is (πr²) / (4r²) = π/4 (notice that the radius drops out of the formula). Likewise you can compute the packing fraction of the hexagonal packing by dividing the plane into hexagons.

What about packing spheres in three-dimensional space?

Let’s write points as triples of numbers. If we take all the points (a,b,c) for which a, b, and c are integers, no two of the points are closer than distance 1, so we can put spheres of radius 1/2 around each of them and the spheres don’t overlap. (If two points are at distance d from one another, spheres of radius d/2 centered at the two points will touch but won’t overlap.) The sphere centered at (a,b,c) is tangent to the spheres centered at the six points (a±1,b,c), (a,b±1,c), and (a,b,c±1). This gives us the cubical packing, and it covers about 52% (more precisely π/6) of 3-dimensional space.

Not bad! But it turns out that if you throw out half of the spheres and inflate the rest, you can get a bigger packing fraction.

Here’s how it works. Imagine painting those spheres red and blue, where a sphere centered at (a,b,c) is red if a+b+c is even and blue if a+b+c is odd. Each red sphere touches six blue spheres. If we cull the blue spheres, then no red sphere touches any other sphere, so there’s room for us to expand the radii of the red spheres. By how much? The nearest neighbors of the red sphere centered at (a,b,c) are now the twelve red spheres centered at (a±1,b±1,c), (a±1,b,c±1), and (a,b±1,c±1); these twelve points are all at distance sqrt(2) from the point (a,b,c), so we can expand the radii of the red spheres from 1 to sqrt(2)/2 and the red spheres still won’t overlap (though they will graze each other). This is a win because the volume of a sphere grows like the cube of radius. That is, even though the packing fraction went down by a factor of 2 when we culled the blue spheres, it went up by a factor of (sqrt(2))³ = 2 sqrt(2) > 2 when we inflated the red spheres. So our new culled-and-inflated packing has a bigger packing fraction (bigger by a factor of sqrt(2)), namely π sqrt(2) / 6, or about 74%.

Is this packing the best possible? Johannes Kepler thought it was, and for centuries, nobody could find a better packing but nobody could prove that there wasn’t one. It wasn’t until 2005 that Thomas Hales published a proof that Kepler’s packing fraction can’t be improved.

What about packing spheres in four-dimensional space? What would that even mean? If we relinquish visualization and rely on analogy, we can just define four-dimensional space as the set of quadruples (a,b,c,d) of real numbers, and define the distance between two quadruples (a,b,c,d) and (a’,b’,c’,d’) as

and so on. Then we can use the same trick that worked in three dimensions. Take a hypersphere centered at each point (a,b,c,d) where a,b,c,d are integers, and paint it red or blue according to whether a+b+c+d is even or odd. If we cull the blue hyperspheres and inflate the red hyperspheres by a factor of sqrt(2), we get a packing that’s exactly twice as dense as the 4-dimensional hypercubical packing. This is called the D₄ packing, and it’s believed to be optimal, but nobody has proved it.

You might think you can guess how the rest of the story goes: 5-dimensional packing is even harder than 4-dimensional packing, 6-dimensional packing is harder still, and so on, forever. But no! That’s the thing I find most amazing about this story. For two special values of n, mathematicians have been able to prove that the densest known way to pack n-dimensional hyperspheres is in fact the densest possible way. These exceptional dimensions are n=8 and n=24. The proof for n=8 was found by in 2016 by Maryna Viazovska, and the proof for n=24 was found a week later by Viazovska in collaboration with Henry Cohn, Abhinav Kumar, Stephen Miller, and Danylo Radchenko. Erica Klarreich’s article is a great place to look if you want to know more. Or check out Kelsey Houston-Edwards’ Infinite Series video about sphere-packing.

One thing I love about this topic is that despite the sophistication of the methods used by Viazovska and her collaborators, the subject is still in its infancy. The only dimensions we understand right now are 1, 2, 3, 8, and 24. I’m guessing that the 4-dimensional case is the one somebody will solve next, but who knows?

Calculus is Deeply Irrational

You’re lying on a beautiful beach when you feel a tap on your shoulder, and suddenly you’re not at the beach at all — you’re in a classroom. The student who woke you looks apologetic, and from the front of the room the teacher is staring at you expectantly. He points at the blackboard on which he has written the function f(x) = 6x − x³ next to its graph. “I said: how can we find the maximum value achieved by this function on the interval from 0 to 2?”

A pleasant dream has been replaced by your worst nightmare. But into your still-sleep-fogged conscious mind rises a catchphrase, your only chance for salvation. “Um… Take the derivative and set it equal to zero?”

My Favorite Theorem

2019 is a great year to learn some calculus. Not only are there the videos of Robert Ghrist and Grant Sanderson, but there’s a wonderful new book out by Steven Strogatz. Strogatz has spent the last thirty years growing into the kind of writer who could produce the book about calculus that the world needs, and now he’s produced it. In a few months Ben Orlin will be coming out with a book of his own, and the chapters I’ve seen make me wish I had the power to magically forget calculus (temporarily), so I could have the experience of encountering the subject for the first time through Orlin’s delightful combination of lively prose and cutely inept drawings. And as if that weren’t enough, this year we also have David Bressoud‘s clarion call for teachers to improve the pedagogy of calculus by putting its standard topics back into something like the order in which they were discovered. Calculus is having a gala year.

The celebration is long overdue.¹ Calculus is one of the triumphs of the human spirit, and a demonstration of what perfect straight things (and perfect curvy things) can be made from the crooked timber of humanity. It’s given us a way of seeing order amidst the variety and confusion of reality, hand-in-hand with the expectation that when things happen, they happen for a reason, and that when surprising things happen, it’s time to look for new forces or additional variables.

One of my favorite theorems is a calculus theorem, but it’s not a theorem anyone talks about very much. It may seem mundane (if you’re mathematically sophisticated) or silly (if you’re not). It’s seldom stated, and when it is stated, it’s a lowly lemma, a plank we walk across on the way to our true destination. But it’s a crucial property that holds the real number line together and makes calculus predictive of what happens in the world (as long as we stay away from chaotic and/or quantum mechanical systems). It’s called the Constant Value Theorem, and it can be stated as a succinct motto: “Whatever doesn’t change is constant.” (This is not to be confused with the motto “Change is the only constant”, which happens to be the title of Orlin’s book.) I’ll tell you four things about this theorem that I find surprising and beautiful.

Mathematical Flimflam

[Audio version available at http://mathenchant.org/050.mp3.]

I’m a pure mathematician with no background in applied mathematics. But lately I’ve been striving to make a name for myself in the less-crowded field of mis-applied mathematics, and bogus science more broadly.

Now you may be asking yourself, is bogus science really less crowded a field than good science? After all, if Sturgeon’s law (“Ninety percent of everything is crap”) applies to science, then we can expect crappy science to predominate over the good kind. But bogosity transcends mere crappiness. For something to be bogus, I think there must be an attempt to deceive. Or at least, there must be the appearance of an attempt to deceive. Sometimes the appearance is itself a sham, and that’s the kind of second-order bogosity I enjoy practicing, when I try my hardest to act like someone who genuinely believes (and wants others to believe) a nonsensical theory.

My forum is the Festival of Bad Ad Hoc Hypotheses (BAHFest), held periodically in various locations around the world (San Francisco, Seattle, Cambridge, Sydney, and London). It’s a celebration of well-argued and thoroughly researched but completely incorrect scientific theories. BAHFest is dedicated to the proposition that no matter how absurd a premise is, you can find a way to abuse the tools of science to support your cause and make people laugh in the process. (Or make nerds laugh, anyway.)

BAHFest was the brainchild of Zach Weinersmith whose Infantapulting Hypothesis got the game going.

Carnival of Mathematics #170

I’m hosting issue number 170 because I have a thing for the number’s largest prime factor, but it turns out there’s a reason for a Martin Gardner fan like me to appreciate the number itself: 170 is the number of steps¹ needed to solve a classic mechanical puzzle called The Brain invented by computer scientist Marvin H. Allison, Jr., described by Martin Gardner in his Scientific American essay “The Binary Gray Code”, and still available from Amazon.

The Brain, aka The Brain Puzzle, aka The Brain Puzzler.

Here’s what Gardner says about The Brain:

It consists of a tower of eight transparent plastic disks that rotate horizontally around their centers. The disks are slotted, with eight upright rods going through the slots. The rods can be moved to two positions, in or out, and the task is to rotate the disks to positions that permit all the rods to be moved out. The Gray code supplies a solution in 170 moves.

A Mathematician in the Jury Box, or, “But how should we define ‘intoxicated’?”

Back in the 1990s, when I was serving on a jury in a one-day trial, my mathematical temperament got me in hot water with my fellow jurors; fortunately, my outside-the-classroom mathematical training got me out of it. But that doesn’t come in until the end of the story.

The case featured a couple of surprising twists — which is in itself surprising, since even a single twist is unusual in a one-day trial. It had seemed at first like a very straightforward drunk-driving charge. The defendant went to a party, drank some alcohol, left the party feeling unwell, got into his car, drove off, and blacked out, though with enough advance warning of his impending unconsciousness that he was able to pull over to the side of the road and turn on his hazard lights before passing out. A police officer found him slumped over the wheel of his car. The officer smelled his breath and it smelled of alcohol. The District Attorney presented these facts confidently, as if this was going to be an open-and-shut case. But then, in the kind of surprise you see only on television, the defense attorney asserted (with medical records to support his assertion) that in fact the defendant was diabetic, that someone with diabetes can go into hypoglycemic shock if they ingest a little bit of alcohol on an empty stomach, that the breath of someone in hypoglycemic shock is often nearly indistinguishable from the breath of someone who is drunk, and that the amount of alcohol that the defendant had drunk at the party was, according to witnesses, well under the amount that would cause blood alcohol concentration to reach .08% (the legal definition of “too much”).

Mazes, Puzzles, and Proofs

Many family restaurants offer paper placemats that entice children into solving puzzles as an alternative to kicking each other under the table, blowing bubbles in their beverages, and so on. I remember those placemats from my own childhood and I recall mazes in particular. The mazes weren’t large, but the designers, in their quest to keep us kids occupied as long as possible, would put long dead-ends near the start of the maze. I quickly hit on a strategy that the emphatically named Thomas T. Thomas also found, as he later recounted in his charming essay “Working Backward“: 

One of the most valuable techniques in problem solving I learned in the third grade. But it certainly wasn’t a lesson my teacher intended.