Message #2479

From: Melinda Green <melinda@superliminal.com>
Subject: Re: [MC4D] Re: flaw in 4 color theorem "proof"
Date: Sun, 11 Nov 2012 18:36:04 -0800

Both Andrey and Norbert are correct and have now doubled the number of
solvers. Norber’s was sent to me privately and included a nice
counterexample. He was surprised with the dearth of solvers, but I think
that our group is much better equipped for this sort of puzzle than the
general puzzling community. Maybe one of you who also participate in the
speedsolving forums would like to post the puzzle there and we will see
if my guess is right? I have gotten lots of wrong answers over the years
and even fooled myself a few times in the first few years. Very few
people know much about topology, but we have seen a fair bit of it here,
especially in the last couple of years. If any of our younger members
have been interested in those message threads, I encourage you to take a
class in topology if you get the chance.

To Andrey’s point, I think I can safely say that the flaw cannot be
easily fixed. Pretty much all the great mathematicians over the last 350
years have tried and failed. That is not to say that it can’t be done;
it just can’t be done easily. The first real proof of the 4-color
conjecture relied very heavily on computer assistance and the result was
so long that it could never be checked by humans. Even if someone
succeeded in following the entire proof, the likelihood that they made a
mistake somewhere is so high that their result couldn’t be trusted. The
best they could do is examine the source code for holes or bugs. To make
matters worse, the form of the proof is called a statistical proof
<http://en.wikipedia.org/wiki/Statistical_proof>. I had never heard the
term before but it is like "deductive" and "inductive", or like our
false proof "by contradiction". My understanding is that a proper
statistical proof asserts that the odds that there is a counterexample
is vanishingly small. Such proofs are so unpleasant that nobody really
wants to use or accept them. They are the weakest form of proof but they
are definitely considered to be valid.

That proof by Appel and Haken was a landmark in mathematics which split
the mathematics community regarding the use of computers compared to the
traditional pencil and paper methods. These days everyone agrees that
computers play an essential role in pure mathematics, but many people
including myself feel a bit sad that such a beautiful problem didn’t
have an equally beautiful solution. There is still a great deal of fame
awaiting the first person who can find an elegant solution that can be
verified the old-fashioned way. The problem is that the goal of being
the first to solve it has already been reached, reducing the fame you
might get if you succeed. Personally, I believe that there will be
plenty of fame for doing that because the purists will be so happy to
see this beautiful problem wrapped up properly.

For a little background showing even more irony, it is helpful to know
that the problem is the same in the plane as it is on the sphere which
are equivalent. These surfaces have genus 0. The one holed torus has
genus 1, two holed 2, etc. for all of the orientable surfaces. Then
there are the non-orientable surfaces like the Klein bottle with genus 1
which are sort of like the negative integers assigned to the one holed
Klein bottle, the two holed bottle, etc. In modern history, little by
little people found solutions to the coloring problem for all of of this
infinite set of surfaces except for genus zero! A lot of really
important results came from that effort, but the one last surface simply
wouldn’t yield to those methods, and of course this was the one surface
that everyone cared about the most. I think that Appel and Haken deserve
far more credit than they got, but I still hope and even expect that
someday some hero will finish the job in a way that will satisfy
everyone. I will even offer a $5,000 prize right here and now to anyone
in our group who succeeds in fixing this false proof before anyone else
finds a proof that doesn’t require computers. If any of you do take the
prize, the money will probably be the least interesting that happens to
you as a result. Good luck!

-Melinda

On 11/11/2012 11:35 AM, Norbert Hantos wrote:
> Dear Melinda,
>
> I surprised that such a few solutions you get for the false proof of
> the 4-color theorem. Therefore I tried to find the flaw. I think I
> successed. :)
>
> I draw a counter-example graph, where you can not execute the
> recoloring described in 14) and 15).

On 11/11/2012 3:07 AM, Andrey wrote:
> Hi Melinda,
> I haven’t read bottom of your message, but in the proof I don’t like items 14-15: what if blue-green chain will intersect with red-green? In that case you can’t isolate both yellow areas, but I’m not sure if this case can be fixed easily.