Tuesday, July 06, 2004

Gems of Additive Number Theory

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.

  1. Erdös-Szemerédi: Let A be a subset of the reals. Either |A+A|≥m5/4 or |AxA|≥m5/4.
  2. Ruzsa: For all k, if |A+B|≤km then |A+A|≤k2m.
  3. Gowers: Let E be a set of pairs (a,b) with a in A and b in B. Let A+EB be the set of values a+b with (a,b) in E. For any δ and k, if |E|≥δm2 and |A+EB|≤km then there is an A'⊆A and B'⊆B with |A'|,|B'|≥δ2m and |A'+B'|≤mk35.
Later Russell Impagliazzo showed how to use finite field versions of these results in his upcoming FOCS paper with Barak and Wigderson. They show how to convert poly(1/δ) independent sources of distributions with δn min entropy to n nearly uniform random bits.

No comments:

Post a Comment