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, ${f(P;A,B)}$ is the result of “flipping” the path from the vertex ${A}$ to ${B}$.

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,

$\displaystyle P_{1}, P_{2}, \dots$

as the flips are performed. Most argue via a compactness argument that this sequence has a limit polygon ${P^{\infty}}$. 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.

November 25, 2009 2:35 pm

I don’t see the difference between Erdos conjecture and Theorem 1 ?

• November 26, 2009 12:48 pm

From the paper, “Polygons Flip Finitely: Flaws and a Fix.”:

In 1939, Béla Nagy pointed out that flipping multiple pockets *simultaneously* may make the polygon nonsimple. Modifying the problem slightly, he argued that repeatedly flipping one pocket of the current polygon always convexifies the polygon after a finite number of flips.

So I’m guessing the difference between the theorem and the conjecture is that the conjecture required you to make all the flips simultaneously, whereas the theorem makes them (presumably with omissions) sequentially.

November 25, 2009 3:26 pm

As said by Lance, Thanksgiving was a month ago!

November 25, 2009 7:10 pm

Of course. Forgot.

November 25, 2009 4:23 pm

The original conjecture by Erdos seems to have been that by simultaneously flipping all pockets you always reach a convex polygon. However, there are trivial examples where simultaneously flipping pockets gives a self-intersecting polygon.

November 25, 2009 4:23 pm

Regarding bounds: Bounds based on what? Some measure of non-convexity? According to the linked paper, number of vertices won’t do, as even for a quadrilateral the number of flips required can be arbitrarily large.

November 25, 2009 7:07 pm

Yes, some measure. Or try a random polygon? Or in the use smooth analysis: allow the original vertices to be randomly moved a bit?

November 25, 2009 6:38 pm

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.
—-

I don’t understand how the limit can be a non-convex polygon. If it’s not convex you can keep flipping, so it’s not the limit.

November 25, 2009 7:12 pm

That is the point. Suppose the polygons go to a limit. You then flip the limit which is not the same as flipping the previous polygons that tended to the limit.

November 25, 2009 7:07 pm

So the sequence of papers on the Erdös-Nagy Theorem, P1, P2, …, has a limit!

7. November 26, 2009 1:08 am

There is a real interesting book covering some pretty nice background on the history of mathematics leading upto Paul Cohen’s work on the Continuum Hypothesis.

The book talks about the common thread connecting non-euclidean geometry and the development of logic following Cantor, Godel and Cohen.

Also another book that I find worth mentioning in the above context is Bill Dunham’s Journey Through Genius. Wonder how people write these works – writing a captivating mathematical story is in my opinion a real piece of art.

8. November 26, 2009 11:53 am

Davy Lunch: The difference is that the original conjecture (Erdos) did not require every possible of combinations of flips to resolve to a convex polygon. There only had to exist a single combination of flips. Theorem 1 says that this is true for any combination of flips.

RJ: Great post!

• November 28, 2009 7:38 am

That makes it seem like the theorem is stronger than the conjecture, while (evidently) the opposite is true. If I understand correctly, the conjecture requires simultaneous flips whereas the theorem is for a sequence of flips. I got this impression from the paper that was referred to.