into existence only in the last thirty years or so. This is like the fast-food outlet that serves billions of dull, repetitive burgers: It does the job, but not prettily. There are often some clever ideas, but their role is to reduce the problem to a massive—but in principle routine—calculation. This is then entrusted to a computer, and if the computer says “yes,” the proof is complete.
An example of this kind of proof turned up recently in relation to the Kepler problem. In 1611 Johannes Kepler was considering how spheres can be packed together. He came to the conclusion that the most efficient method—the one that packs as many balls as possible into a given region—is the one that greengrocers often use to stack oranges. Make a flat layer in a honeycomb pattern, then stack another such layer on top, with the oranges sitting in the depressions of the first layer, and continue like this forever. This pattern shows up in lots of crystals, and physicists call it the face-centered cubic lattice.
It is often said that Kepler’s statement is “obvious,” but anyone who thinks so does not appreciate the subtleties. For example, it is not even clear that the most efficient arrangement includes a flat plane of spheres. Greengrocers start stacking on a flat surface, but you don’t have to. Even the two-dimensional version of the problem—showing that a honeycomb pattern is the most efficient way to pack equal circles in the plane— wasn’t proved until 1947, when László Fejes Tóth finally did it. His proof is too complicated to belong in The Book, but it’s all we have.
In 1998, Thomas Hales announced a computer-assisted proof of the Kepler conjecture that involved hundreds of pages of mathematics plus three gigabytes of supporting computer calculations. It has since been published in the Annals of Mathematics , the world’s premiermath journal, with one important reservation: the referees state that they have not been able to check every single step in the computations.
Hales’s approach was to write down a list of all the possible ways to arrange suitable small clusters of spheres; then prove that whenever the cluster is not what you find in the face-centered cubic lattice, it can be “compressed” by rearranging the spheres. Conclusion: the only incompressible arrangement—the one that fills space most efficiently—is the conjectured one. This is how Tóth handled the two-dimensional case, and he needed to list about fifty possibilities. Hales had to deal with thousands, in three dimensions, and the computer had to verify an enormous list of inequalities—those three gigabytes of memory are what’s needed to tabulate them all.
One of the earliest proofs to use this brute-force computer method was the proof of the four color theorem. About a century ago Francis Guthrie asked whether every possible two-dimensional map containing any arrangement of countries can be colored using only four colors, so that neighboring countries always get different colors. It sounds simple, but the proof was highly elusive. Eventually, in 1976, Kenneth Appel and Wolfgang Haken proved the four color theorem. By trial and error and hand calculations, they first came up with a list of nearly two thousand configurations of “countries” and invoked the computer to prove that the list is “unavoidable,”meaning that every possible map must contain countries arranged in the same way as at least one configuration in the list.
The next step was to show that each of these configurations is “reducible.” That is, each configuration can be shrunk down until a part of it disappears, leaving a simpler map. Crucially, the shrinking must ensure that if the simpler map left behind can be colored with four colors, the original one can be as well. Now remember that every possible map must contain at least one of the two thousand configurations. So even the simpler map that you have just created by this process must have another
Deanna Chase
Leighann Dobbs
Ker Dukey
Toye Lawson Brown
Anne R. Dick
Melody Anne
Leslie Charteris
Kasonndra Leigh
M.F. Wahl
Mindy Wilde