Yesterday Avi Wigderson gave a talk entitled Gems of Additive/Combinatorial Number Theory where he presented three interesting results about the sizes of sets when you add all the possible numbers from one set with another. Let A and B be subsets of an Abelian group G and define A+B = {a+b | a in A and B in B}. We define AxB as the same with multiplication when we work over a field. Let |A|=|B|=m.

- Erdös-Szemerédi: Let A be a subset of the reals. Either
|A+A|≥m
^{5/4}or |AxA|≥m^{5/4}. - Ruzsa: For all k, if |A+B|≤km then |A+A|≤k
^{2}m. - Gowers: Let E be a set of pairs (a,b) with a in A and b in B. Let
A+
_{E}B be the set of values a+b with (a,b) in E. For any δ and k, if |E|≥δm^{2}and |A+_{E}B|≤km then there is an A'⊆A and B'⊆B with |A'|,|B'|≥δ^{2}m and |A'+B'|≤mk^{3}/δ^{5}.

--

Posted by Lance to My Computational Complexity Web Log at 7/6/2004 07:42:41 AM- Erdös-Szemerédi: Let A be a subset of the reals. Either
|A+A|≥m