Imagine that you’re a stingy cartographer and that you want to make a colored map of the united states. Because you’re stingy, you want to avoid spending money on ink.
You have to color the map so that no two adjacent states are the same color—otherwise you wouldn’t be able to tell them apart! If you want to buy the fewest colored pens possible, how many colors must you use to make your map?
Very early on, mathematicians guessed that the answer was four colors. However, no one could prove it. An example map is in the tittle figure, taken from Wikipedia.
This was a long-standing problem in mathematics, first posed in 1852 by Francis Guthrie. A number of famous mathematicians including Arthur Cayley and Augustus De Morgan tried their hands at it. But the problem went unsolved until 1976, when Kenneth Appel and Wolfgang Haken tried something radical.
Appel and Haken used a computer to automatically attempt various calculations required for the proof. Although a human being is incapable doing the incredibly long and tedious calculations—the whole proof is well over 400 pages—a computer could handle it. The computer lacked the human judgement and intuition required to construct the proof, however. So when the computer reached an impasse, it asked Appel and Haken what to do.
The method worked, and Appel and Haken were able to prove the four color conjecture, now called the four color theorem. Moreover, Appel and Haken invented a whole new way of thinking about mathematics, and an enormous field of study emerged from their breakthrough. The technique is now called a computer-assisted proof and it has connections to artificial intelligence, the philosophy of mathematics, and more.
+Daniel Estrada shared this excellent article on the philosophical implications of computer-assisted proofs.
Kenneth Appel died of esophageal cancer on April 19, 2013, and the New York Times wrote a nice article on him. You can find it here. Thanks to +Sabrina Benton for pointing it out!
R.I.P., Kenneth Appel. The world has lost a great thinker.