Skip
# Kenneth I. Appel (1932-2013)

Yeah, I hear you, but sometimes analytic answers are just so damn...beautiful.

posted by Mental Wimp at 10:28 AM on April 29, 2013

I'm reasonably well acquainted with some of what's been done since. There was a proof simplifying things somewhat, but it still left hundreds of cases. Everything else I've seen has been working on equivalent statements, rather than graph colouring itself. Someone might manage a proof of one of those that's at least readable. Truly elegant might be too much to hope for, though elegance is different than not needing to check individual cases.

It's also not clear to what extent what's been done overlaps. I've seen at least three quasi-related approaches, but they all go off in different directions and it's hard to tell what's what.

posted by hoyland at 12:35 PM on April 29, 2013 [1 favorite]

Post

# Kenneth I. Appel (1932-2013)

April 29, 2013 8:38 AM Subscribe

Mathematician Kenneth Appel has died at the age of 80. He is best known for having proved, with Wolfgang Haken, the four-color theorem, which states that only four colors are needed to have a map in which no two adjacent countries have the same color.

Here is his Wikipedia page, as well as an article from the magazine of the University of New Hampshire, where Appel retired, on the four-color theorem, including the controversial method Appel used to prove it. Instead of traditional logical inference, e.g., Euclid's proof of the Pythagorean Theorem, Appel and Haken relied on computers to demonstrate the theorem's validity. Their efforts helped usher mathematics into the computer age, though some have decried (PDF) the move. Lastly, a parody of the four-color theorem.

Here is his Wikipedia page, as well as an article from the magazine of the University of New Hampshire, where Appel retired, on the four-color theorem, including the controversial method Appel used to prove it. Instead of traditional logical inference, e.g., Euclid's proof of the Pythagorean Theorem, Appel and Haken relied on computers to demonstrate the theorem's validity. Their efforts helped usher mathematics into the computer age, though some have decried (PDF) the move. Lastly, a parody of the four-color theorem.

Well, he's believed dead, but at current computing power it will take about 2 years to reach a confidence level of 95%

posted by leotrotsky at 8:54 AM on April 29, 2013 [3 favorites]

posted by leotrotsky at 8:54 AM on April 29, 2013 [3 favorites]

well, it is a constructive proof. If you enumerate all the possible configurations and show that it can/cannot happen, that's a proof. (or a proof by contradiction, but is the inverse property applicable to proofs ?) Wiki tells me this is called proof by exhaustion, but in our theory class the bigger deal was using a computer to do the proof.

posted by k5.user at 8:59 AM on April 29, 2013 [1 favorite]

posted by k5.user at 8:59 AM on April 29, 2013 [1 favorite]

He did not prove that a smaller, elegant proof does not exist. So there's still hope for us math cranks.

posted by vacapinta at 9:02 AM on April 29, 2013 [1 favorite]

posted by vacapinta at 9:02 AM on April 29, 2013 [1 favorite]

They turned it into a postmark (pdf).

posted by benito.strauss at 9:21 AM on April 29, 2013 [2 favorites]

posted by benito.strauss at 9:21 AM on April 29, 2013 [2 favorites]

My impression is that most people thought it was true prior to the proof, but the eminent H. S. M. Coxeter said he suspected it wasn't just a few years before, though I've never heard what made him doubt it.

posted by jamjam at 9:40 AM on April 29, 2013

posted by jamjam at 9:40 AM on April 29, 2013

I read once that, before they proved the four-color theorem for 2D maps, they proved the seven-color theorem for maps printed on a torus. Apparently it was easier to prove that, for some reason. It was then that decided math was 1. mind-bogglingly cool and 2. too fucking confusing for me.

posted by showbiz_liz at 10:02 AM on April 29, 2013

posted by showbiz_liz at 10:02 AM on April 29, 2013

I vaguely remember a piece about the Four Color Theorem in the Time-Life Science Encyclopedia, which was published a couple years before Appel/Haken's paper.

This makes me want to dig that up again to see what it said.

posted by ardgedee at 10:10 AM on April 29, 2013

This makes me want to dig that up again to see what it said.

posted by ardgedee at 10:10 AM on April 29, 2013

If, for some reason, you want to see their original papers, they're online. (I think they should be accessible, but I'm writing this from a university computer.)

posted by hoyland at 10:11 AM on April 29, 2013 [2 favorites]

posted by hoyland at 10:11 AM on April 29, 2013 [2 favorites]

The primary criticism of the computer proof that I appreciated was that it just wasn't

In my own small way I took inspiration from their work; in my 1994 undergraduate math thesis I included some half-ass proofs made by enumeration. I never was much of a mathematician, much happier to do constructive work via software. Why do analytic work when you can bash up a simulation or numerical approximation?

posted by Nelson at 10:15 AM on April 29, 2013

*elegant*. Disappointing that the best proof would be to just enumerate all the cases (albeit, after some nice work to narrow down the set of cases that needed consideration). Also a provocative question about whether no elegant proof could exist, that this particular theorem was just going to be ugly. I gather there has been refinements since the original proof; are any more elegant?In my own small way I took inspiration from their work; in my 1994 undergraduate math thesis I included some half-ass proofs made by enumeration. I never was much of a mathematician, much happier to do constructive work via software. Why do analytic work when you can bash up a simulation or numerical approximation?

posted by Nelson at 10:15 AM on April 29, 2013

.

posted by Mental Wimp at 10:25 AM on April 29, 2013

posted by Mental Wimp at 10:25 AM on April 29, 2013

*Why do analytic work when you can bash up a simulation or numerical approximation?*

Yeah, I hear you, but sometimes analytic answers are just so damn...beautiful.

posted by Mental Wimp at 10:28 AM on April 29, 2013

We have a strong prejudice in favor of elegance and simplicity, it seems. Suppose there turn out to be seventeen fundamental forces of nature. I bet people wouldn't like that. There should be at most three, from our elegance-loving point of view.

posted by thelonius at 10:42 AM on April 29, 2013

posted by thelonius at 10:42 AM on April 29, 2013

*Disappointing that the best proof would be to just enumerate all the cases (albeit, after some nice work to narrow down the set of cases that needed consideration). Also a provocative question about whether no elegant proof could exist, that this particular theorem was just going to be ugly. I gather there has been refinements since the original proof; are any more elegant?*

I'm reasonably well acquainted with some of what's been done since. There was a proof simplifying things somewhat, but it still left hundreds of cases. Everything else I've seen has been working on equivalent statements, rather than graph colouring itself. Someone might manage a proof of one of those that's at least readable. Truly elegant might be too much to hope for, though elegance is different than not needing to check individual cases.

It's also not clear to what extent what's been done overlaps. I've seen at least three quasi-related approaches, but they all go off in different directions and it's hard to tell what's what.

posted by hoyland at 12:35 PM on April 29, 2013 [1 favorite]

I remember the gist of a story about a mathematician whose elderly colleague came into work every morning, spent the day coloring pages in an attempt to disprove the four-color theorem, then left. Anyone remember who it was?

posted by Joe in Australia at 6:40 PM on April 29, 2013

posted by Joe in Australia at 6:40 PM on April 29, 2013

.

posted by equalpants at 8:08 PM on April 29, 2013

posted by equalpants at 8:08 PM on April 29, 2013

I once asked Haken if he believed his proof of the four color theorem, if he was sure it was true, and he said something like "yes, I think so. You see so many computations that confirm it."

This is the same Haken of Haken manifolds. A fine mathematician.

The only way I could let him get away with something like that is because I know the history of the problem. The four color problem was historically a refuge for dingbats. It's a problem any child can understand and no adult can solve. There were numerous incorrect proofs even by competent mathematicians, but the noise-level from the general public was tremendous.

And it's undoubtedly true. Numerous computations confirm it.

Appel and Haken did the great service of killing that beast, ending over a century of amateur speculation.

I hope they were right.

posted by twoleftfeet at 12:45 AM on April 30, 2013 [1 favorite]

This is the same Haken of Haken manifolds. A fine mathematician.

The only way I could let him get away with something like that is because I know the history of the problem. The four color problem was historically a refuge for dingbats. It's a problem any child can understand and no adult can solve. There were numerous incorrect proofs even by competent mathematicians, but the noise-level from the general public was tremendous.

And it's undoubtedly true. Numerous computations confirm it.

Appel and Haken did the great service of killing that beast, ending over a century of amateur speculation.

I hope they were right.

posted by twoleftfeet at 12:45 AM on April 30, 2013 [1 favorite]

By the way, if you're very bored, you can read the outline of the proof of the four color map theorem, which is 723 pages long. It's just an outline though.

posted by twoleftfeet at 12:51 AM on April 30, 2013

posted by twoleftfeet at 12:51 AM on April 30, 2013

Awww. The summer between my 6th and 7th grades (1984, I'm thinking?) I went to a stayover mathematics camp at University of Illinois in Champaign-Urbana, and Dr. Appel was one of the main instructors -- he introduced us to matrices, among other concepts, in a way that was engaging and clear enough to get them across to kids our age, and got us writing simple computer programs to work with them. He also talked about the 4-color map problem. For a mathematician of his stature to be so into working with younger kids as well was pretty awesome. Sorry to hear he's gone, fascinated by the math discussion in this thread (which is a great way to honor his memory, imo.)

.

posted by slappy_pinchbottom at 7:59 AM on April 30, 2013 [2 favorites]

.

posted by slappy_pinchbottom at 7:59 AM on April 30, 2013 [2 favorites]

« Older "I'm a 34-year-old NBA center. I'm black. And I'm... | The Disapproval Matrix Newer »

This thread has been archived and is closed to new comments

posted by Cash4Lead at 8:46 AM on April 29, 2013