Sum-Product Theorems

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