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).
- 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.)
- Nathanson (1997) proved &epsilon>1/31.
- Chen (1999) proved &epsilon>1/20
- Ford (1998) proved &epsilon>1/15.
- Elekes (1997) proved &epsilon>1/4. (My writeup includes this result.)
- Solymosi (2005) proved &epsilon>3/11. (Actually he has a slightly stronger result. My writeup includes the slightly stronger result.)
Is there an easy construction of A that establishes an upper bound on epsilon that is bounded away from 1?
ReplyDeleteIs there an easy construction of A that establishes an upper bound on epsilon that is bounded away from 1?
ReplyDeleteIt obviously can't be more than n^2.
please ignore last comment, I'm retarded.
ReplyDeleteSolymosi recently posted an elegant proof on the ArXiv that improves his bound in the real case from 3/11 to 1/3.
ReplyDeleteThe paper is "An Upper Bound on the Multiplicative Energy" and is at http://arxiv.org/abs/0806.1040