What Are Proofs For Anyway?

How to make a polygon convex and how not to prove it

Paul Cohen was one of the great logicians of the last century, who won the Fields Medal in 1966 for this brilliant work. He, of course, revolutionized set theory when he proved that the Axiom of Choice and the Continuum Hypothesis were both unprovable in the standard formal system called Zermelo–Fraenkel Set Theory. The theory’s history is a bit complex—but the main creators were Ernst Zermelo and Abraham Fraenkel.

Today I thought, with our Thanksgiving Holiday coming up, I would have a short discussion of “why we prove theorems?” It is related to Cohen, and contains a “tasty” result about polygons that I thought might be a good pre-holiday story.

I only met Paul Cohen once, when we both were at a Royal Society workshop on the nature of proof. The main questions discussed were: what is a proof? why do we prove things? and what is the role of machine proofs? It was a wonderful experience. I still do not know the answers to these questions—perhaps I will discuss them in more detail in the future.

I noticed two things about the workshop. First, the senior mathematicians present—including four Fields Medalists—all agreed that proofs were for explanation. They said: The goal of a proof is not to “check” that something is true, but rather to give insight into why it is true. Also they all disliked machine proofs. Cohen was probably the most extreme in his displeasure at the notion of a machine proof.

Second, I noticed how the presentation technologies changed over the two days of the workshop. Computer scientists spoke first, and we all used powerpoint. I even had a short video in my presentation, which included slides with elaborate pictures and diagrams. Then, the relatively young mathematicians spoke. They used powerpoint too, but no videos. Just simple slides, some with a small diagram. Finally, the more senior mathematicians gave their talks, using just plain overhead slides. I will not say anything about my talk, but all the other talks were great, even though the styles were so different.

Then, Paul Cohen spoke. He walked up to the overhead projector with one slide and one pen. He then gave a great lecture: he spoke and now and then wrote a formula on his single slide. It was a brilliant talk and performance. So much for powerpoint.

Convex Flips

The tasty result today is due to Paul Erdös who first conjectured it in 1935. I just stumbled across it recently, while doing some research on another problem. I think it may be connected to an old problem—a disease—that I have had for years. More on that in the future.

The problem Erdös raised, in the Math Monthly, was the following conjecture: Start with any simple polygon in the plane: that is a polygon that does not cross itself. Define a pocket as a maximal connected region interior to the convex hull of the polygon. A flip is the operation of reflecting the pocket across its line of support. The goal is to reach from any simple polygon, a convex polygon, by using just the flips across various pockets. Is that possible?

The following is a figure from a paper on the subject by Branko Grünbaum and Joseph Zaks:

Note, is the result of “flipping” the path from the vertex to .

Erdös’ conjecture was actually too strong, there was a trivial counter-example. Béla Szőkefalvi-Nagy made the statement weaker, proved it, and ever since it has been called the Erdös-Nagy Theorem:

Theorem 1 Starting with any simple polygon, any sequence of flips eventually stops, and the resulting polygon is always convex.

A pretty neat result—no?

Proof or Insight

The result has been rediscovered many times, and also re-proved many times. But these proofs are not proofs. Many, if not all, have subtle errors; it is also interesting to note that the errors made are not even all the same. When I read this, I immediately thought of the workshop on proof—where is the fundamental insight why this process stops at a convex polygon? Somehow, a large number of authors, some quite famous, had missed it.

There is a neat paper published in 2006, by Erik Demaine, Blaise Gassend, Joseph O’Rourke, and Godfried Toussaint on the Erdös-Nagy Theorem. They discuss the history of the problem, the gaps in all the previous proofs, and supply a correct proof. So the theorem is true: flipping a polygon stops at a convex polygon—always. Their paper is extremely well written and its title says it all: “Polygons Flip Finitely: Flaws and a Fix.”

There are many different problems with the existing proofs—see the paper by Demaine, Gassend, O’Rourke, and Toussaint for the details. One general approach is to look at the sequence of polygons that occur,

as the flips are performed. Most argue via a compactness argument that this sequence has a limit polygon . One difficulty is proving that this limit is reached in a finite number of steps. This reminds me of a similar problem I discussed before on the distributive law.

Another difficulty is proving that the limit is indeed a convex polygon: in some of the early proofs it is just stated without any justification, while others gave incorrect arguments.

Open Problems

Given any simple polygon there is a best sequence, and a worst sequence of flips that make it convex. I believe that getting the tight bounds on these is still open.

Have a safe and happy holiday.