Tuesday, October 21, 2014
My Account  | Login
Nashua;54.0;http://forecast.weather.gov/images/wtf/small/nbkn.png;2014-10-21 21:33:48
Monday, April 29, 2013

Proving the four-color theorem with computers made the most famous mathematician in N.H. history

David Brooks

Take an outline map of the lower 48 U.S. states and four crayons. Can you shade in the map so that every state is a different color than each of its neighbors, without resorting to a fifth color?

This sounds like a silly question but it’s the heart of the very first mathematical proof solved in part by a computer, back in 1976. ...

Sign up to continue

Print subscriber?    Sign up for Full Access!

Please sign up for as low as 36 cents per day to continue viewing our website.

Digital subscribers receive

  • Unlimited access to all stories from nashuatelegraph.com on your computer, tablet or smart phone.
  • Access nashuatelegraph.com, view our digital edition or use our Full Access apps.
  • Get more information at nashuatelegraph.com/fullaccess
Sign up or Login

Take an outline map of the lower 48 U.S. states and four crayons. Can you shade in the map so that every state is a different color than each of its neighbors, without resorting to a fifth color?

This sounds like a silly question but it’s the heart of the very first mathematical proof solved in part by a computer, back in 1976.

It’s also the question that made Kenneth Appel, a former UNH math department head who died this month at age 80, the most famous mathematician ever associated with New Hampshire – assuming “famous” and “mathematician” belong in the same sentence.

The answer to the map-coloring question is “yes.” Amazingly, it would be “yes” even if the U.S. had 48,000 states, or 48 million, or 48 googol of them.

We know that because Appel and colleague Wolfgang Haken proved with mathematical certainty that any possible flat map can always be filled in with exactly four colors, without ever having the same color in adjacent shapes.

This issue has relevance not just in cartography but in a variety of other applications including network design and mathematical graph theory, which involves connections between objects. It’s far more important than it sounds.

Appel and Haken’s four-color proof was a blockbuster, but not because it answered a century-old question. It became one of the most famous mathematical works in the 20th century because it depended on a computer to the point that no person could manually check the work.

That digital intrusion into the most cerebral of human activities generated so much angst and debate in the scientific community that it made the front page of the New York Times, led to an infamous Scientific American cover story titled “The Death of Proof,” and has been the subject of several books.

In “Four Colors Suffice,” author Robin Wilson recounts how one math department head was so incensed by Appel and coauthor Wolfgang Haken using a computer to crank through thousands of possibilities that he wouldn’t let them meet his graduate students.

“The problem had been taken care of by a totally inappropriate means” the department head said in justifying his embargo of Appel and Haken. “A decent proof might be delayed indefinitely.”

Appel came to UNH long after the famous proof, which he made while at the University of Illinois. He headed the UNH math department from 1993 to 2002.

I interviewed Appel twice, once for The Telegraph in the 1990s and once for a 2002 profile in UNH Magazine, and found him a pleasant guy. But he got a tad impatient when the discussion turned to peers’ reaction to the four-color proof; he had obviously gotten tired of that debate.

“Most mathematicians, even as late as the 1970s, had no real interest in learning about computers. It was almost as if those of us who enjoyed playing with computers were doing something non-mathematical or suspect,” he told me in 2002.

I received my bachelor’s degree in math in 1976 and can attest to this. The math department at my little liberal arts college never went anywhere near the school’s computer lab. Heck, most of my professors were still mourning the death of the slide rule.

The debate seems silly now, when computers have revolutionized the Queen of Sciences in ways unimaginable in 1976. (Appel and Haken used an IBM 360 mainframe with just 64K of memory, less than your smartphone uses to shoot a single Angry Bird.)

But even Appel admitted that there was some justification for the poor reception, because the four-color proof didn’t point in any new mathematical direction.

Mathematicians usually prove theorems not because they want to find out whether the theorem is correct – generally a proof isn’t worth their time unless it’s pretty clear the theorem is true – but because proving something with mathematical certainty can lead to new insights or new mathematical tools.

In turn, those can crack other problems or even create entire fields.

A proof that solves a problem but doesn’t inspire new work isn’t much of a proof, and the four-color proof turned out to be that variety – it really wasn’t, in the words of that hot-headed mathematician quoted earlier, a “decent proof.”

Appel and Haken developed formulas to describe possible maps in mathematical terms, using numbers and algorithms to express relationships between neighboring “countries.”

They assumed a map exists which requires five colors, and then reduced all possible maps to their simplest configuration – which is the part that required the computer. When none of those configurations equaled the five-color configuration, they had showed that four colors was sufficient. It’s classic proof by contradiction.

But neither their formulas nor their computer programs ended up being used much in other proofs.

It’s not even clear that the four-color proof made it easier for fellow mathematicians to embrace computers; the negative reaction may have scared them away.

It took a later generation, raised on desktop PCs, to create today’s digital world of fractals and chaos theory and what is sometimes called experimental mathematics.

One other note about Appel’s death: It reminds us, if reminding is needed, about how foreign mathematics remains to the outside world.

Appel’s obituary in Foster’s Daily Democrat, the local daily newspaper, mentions his three years on the Dover School Board in the opening paragraph. The four-color proof? That’s much further down.

GraniteGeek runs Mondays in The Telegraph and online at granitegeek.org. David Brooks can be contacted at 594-5831 or dbrooks@nashuatelegraph.com.