Thursday, November 11, 2010

Mathematical Problems Solved, or Maybe Not.

Conventional wisdom is that mathematics is the one area of certainty in the world. 2+2 is always four. Set theory is consistent. Well, maybe not. Let me describe two iconic mathematical problems.

The most famous and intriguing problems in mathematics tend to be the ones that share two features. First they have been around for a really long time - which means that many people have tried to solve them and failed - and second they must be easy to explain. Curiously, they often lead to controversy - have they been solved or not? I want to describe two mathematical chestnuts that, on balance, mathematicians agree are solved. But...

Pierre de Fermat
The first problem is known as Fermat's Last Theorem. Pierre de Fermat was a brilliant self-taught seventeenth century mathematician who solved a variety of deep number theory problems in his spare time for his own amusement the way you or I might attack an 'extreme' Sudoku. The most famous of these is his so-called Last Theorem.  He explained his ideas and mathematics by writing them up in notebooks. After his death these notebooks proved a treasure trove to mathematicians. In one of them he wrote a theorem in the margin and commented: "I have a truly remarkable proof of this theorem, but it is too long to fit here". Mathematicians worked on it flat out for the next 358 years. The consensus is that, despite being a great genius, he actually didn't have a correct proof. (But maybe that's not true after all, because Lisbeth Salander solves it in her head - while being shot at - in The Girl who Played with Fire, so maybe Fermat managed it too!)
Here is the problem:

There are many triples of positive whole numbers x,y,z so that the equation x2 + y2 = z2 is true.  For example x=3, y=4, z=5. Or x=5, y=12, z=13. Fermat’s last theorem says that this cannot be done for any higher order equation.  That means x3 + y3 = z3 has no solutions using positive whole numbers. Neither does the equation where we use the power 4 or 5 or... In general xn + yn = zn has no solution in whole numbers for ANY whole number n greater than 2.
Andrew Wiles

The problem was finally solved by Andrew Wiles in 1995. Or was it? Mathematicians fell upon his proof like hyenas, gulping down the exciting ideas and the new areas of mathematics it opened up. (By the way it took him years and he created whole new fields of mathematics in the process, but he's not really smart like Salander!) And one of them found a mistake. It took another year to fix the mistake. Are there others? Probably not. But it's possible. Most mathematicians don't come close to understanding his proof. I certainly don't. Could the ones who do have a blind spot? It's really easy to fool yourself when you want something to be true. When I was a graduate student, one of my professors produced an incredibly slick proof of the four color map problem. We were all in awe. Here was a man on his way to a Fields Medal. (The Fields Medal is the Nobel Prize for mathematicians. The story goes that Nobel's wife had an affair with a mathematician. He never forgave the profession and excluded it from his largesse.)  Our professor always illustrated his proof with a key diagram when he explained it. The first expert who read the proof without the author there to describe it, drew it differently and realized at once that it was wrong. None of us had spotted that alternative way of drawing it.

Here's the problem:

Kenneth Appel & Wolfganh Haken

If you want to color a map in such a way that no two countries with a common border have the same color, then you only need four different colors. The problem was posed in 1852. Ten minutes playing around will convince you that this is so reasonable, it's obviously true. It took mathematicians until 1976 to come up with a proof, and even then...
Four colors is enough for the US
Of course the problem has no practical interest. Every real map is colored to distinguish the countries using plenty of colors. After all there is no shortage of them! And no one has ever come across a map requiring more than four colors anyway. In fact proving that five colors is enough is easy - usually included in undergraduate mathematics graph theory courses. But four

Well, the proof was curious. The authors reduced the problem to a large number of different cases which required checking. A very large number. A number so large that it could only be checked by computer. They wrote the program, ran it, and the results were that all the cases checked correctly. So what's the problem? Well, a recent article in the Chronicle of Higher education suggests that only 20% of scientific programs are completely correct. So if you're checking millions of cases...well.

The proof has been replicated in other ways since then. But do we know if the original proof was correct? Maybe. Maybe not.

Michael - Thursday.


4 comments:

  1. Michael, you lost me after 2+2+4. I was that student who never asked any questions because I didn't understand enough to formulate one.

    Because I can use my fingers, I can handle addition and subtraction. Because I was taught by nuns who carried a pointer and roamed the aisles, I learned the multiplication tables (we never knew where the pointer was going to point, so we had to be ready). Beyond that I am lost.

    I am sure that there are many people who will appreciate your careful explanations, but, alas, I am not one.

    Beth

    ReplyDelete
  2. Only 20% correct? Sounds like my differential equations test score...in my wildest dreams...back to imagining murder and mayhem.:)

    Jeff

    ReplyDelete
  3. Hi Beth,
    I didn't mean to get technical. I thought it was interesting that nothing is certain in the world - not even mathematical proofs! (Well, there's death and taxes, of course.) Maybe I was light on the philosophy and heavy on the problems. These two problems have been popular amongst non-mathematicians for a while also. (Stamps and mystery novels!)
    Anyway no more maths for a while. I promise.
    Michael.

    ReplyDelete
  4. Hi Michael - I really liked this post. Bring on the math!

    ReplyDelete