Computational Complexity

Wednesday, January 20, 2010

 
Two Theorems this blog missed

Posted by GASARCH

I warned Lance to wait until early Jan to post 2009 Complexity Year in Review. It was my fear that by posting it on Dec 28, 2009 he may miss out if someone proves P &ne NP on Dec 29, 30, or 31st during 2009.

That did not happen and the review was fine. However, we did miss out on two of the biggest math stories of 2009. Not because they happened on Dec 29,30, or 31, 2009. Not sure why we missed them. But here they are.

1. The Fundamental Lemma was proven. I won't embarrass myself by even trying to blog on it, but will instead point to a blog that did report on it: here. I found out about it when I saw it listed in Time Magazine as one of the top science stories of the year. The results seems to be really important.
2. The Fundamental Pizza was proven. This was proven in 2009 but seems to have gotten attention on some blogs recently. Unlike The Fundamental Lemma this one I can state. Can I prove it? I doubt it--- it was conjectured 40 years ago. The paper is here. Here is the result:
   
   A waiter picks a point on a pizza and makes N slices through that point. Each slice has the same angle. One player gets every other slice and the other gets the other every other slice. Will they each get the same amount? This problem has now been completely solved:
   1. If the point is in the center then yes.
   2. If any of the slices happens to go through the center then yes. (Henceforth assume that no slice goes through the center.)
   3. If N=1 or N=2 or N &equiv 3 mod 4 then the person who gets the slice that has the center gets more.
   4. If N ≥ 5 and N &equiv 1 mod 4 then the person who gets the slice that has the center gets less.
   5. If N ≥ 4 and even then each person gets the same. (NOTE- I added this later, I omited it the first time by accident.)

This result did not make Time magazines list of one of the top science stories of the year. It wasn't even reported on this blog which it should have been. However, I can state it and I suspect I can read the paper if I brush up on my High School Trig. Hence its one of my favorite theorems of the year.

9:58 AM # 5 comments

1.  Anonymous says:  
   
   The fundamental lemma was proved in 2004.
   

   11:01 AM, January 20, 2010

2.  GASARCH says:  
   
   The article in TIME
   (reliable?) said
   
   "When it was checked this year (2009) and found to be correct, mathematicians around the globe breathed a sigh of relief."
   
   So ANON 1- you are CORRECT
   that its was proven in 2004.
   It was verified in 2009.
   Which is the proper date to give it?
   

   11:23 AM, January 20, 2010

3.  Chad Groft says:  
   
   Note also: if N ≥ 4 and N is even, then both get the same amount. Which is not obvious to me.
   

   3:04 PM, January 20, 2010

4.  Anonymous says:  
   
   It was proved in 2004 and appeared in 2009 in Annals of Mathematics
   

   9:49 AM, January 21, 2010

5.  Anonymous says:  
   
   "When it was checked this year (2009) and found to be correct, mathematicians around the globe breathed a sigh of relief."
   
   This a typical misrepresentation in popular media of how mathematics (and science in general) works in practice. In reality, there is no "eureka" moment. It is not that the opinion of the experts about this proof in 2009 is drastically different than their opinion in 2008 or 2007. Acceptance of the paper in the Annals is also no fool-proof guarantee of its correctness. The confidence in such a result builds up over time and is more of a social process. It certainly does not have a sharp threshold that the article is suggesting.
   

   11:03 AM, January 23, 2010

Comment Feeds: This Post All