Computational Complexity

Friday, September 19, 2008

 
Sum-Product Theorems

Posted by GASARCH

At a guest talk at COMPLEXITY a few years ago Avi Wigderson gave a great talk on SUM-PRODUCT theorems. The slides are the last item on this page His talk applied SUM-PRODUCT theorems to a variety of places, in both mathematics and theoretical computer science. He mostly used SUM-PRODUCT theorems over finite fields.

This talk inspired me to look up the proof of SUM-PRODUCT theorems over the reals (which are easier), and do a writeup of the best known results, which is here. (It includes references to the theorems stated below.) If you find any typos or thing to fix, let me know (by email- would not make for interesting comments.)

What is a sum-product theorem? Let A be a set of reals.
A+A = { x+y | x,y &isin A}

A TIMES A = { x TIMES y | x,y &isin A}
A SUM-PRODUCT theorem says that they can't both be small. The following is known and is in the order of quality of result (not quite the same as date of PUBLICATION--- note that this is not the same as order of discovery).

1. Erdos and Szemeredi (1983) proved that there exists an &epsilon such that, if A is a set of n integers, then either A+A or A TIMES A is at least &Omega(n^1+&epsilon) (All subsequent results are for A a n reals.)
2. Nathanson (1997) proved &epsilon>1/31.
3. Chen (1999) proved &epsilon>1/20
4. Ford (1998) proved &epsilon>1/15.
5. Elekes (1997) proved &epsilon>1/4. (My writeup includes this result.)
6. Solymosi (2005) proved &epsilon>3/11. (Actually he has a slightly stronger result. My writeup includes the slightly stronger result.)

10:09 AM # 4 comments

1.  LazyToReadTheSurvey says:  
   
   Is there an easy construction of A that establishes an upper bound on epsilon that is bounded away from 1?
   

   2:08 PM, September 19, 2008

2.  Anonymous says:  
   
   Is there an easy construction of A that establishes an upper bound on epsilon that is bounded away from 1?
   
   It obviously can't be more than n^2.
   

   6:49 PM, September 19, 2008

3.  Anonymous says:  
   
   please ignore last comment, I'm retarded.
   

   6:50 PM, September 19, 2008

4.  Kevin says:  
   
   Solymosi recently posted an elegant proof on the ArXiv that improves his bound in the real case from 3/11 to 1/3.
   
   The paper is "An Upper Bound on the Multiplicative Energy" and is at http://arxiv.org/abs/0806.1040
   

   4:22 PM, September 25, 2008

Comment Feeds: This Post All