Computer Science/Discrete Mathematics Seminar II

We describe four theorems from Combinatorial Number Theory, and sketch their proofs (as time permits). These theorems were important to the recent extractors and Ramsey graphs obtained in [Barak-Impagliazzo-Wigderson] and [Barak-Kindler-Sudakov-Shaltiel-Wigderson]. The extensive research area of Combinatorial Number Theory often deals with the structure of sets of (commutative) groups, and its evolution under the group operation. The theorems below are prime examples, not only being basic and powerful, but also due to their ingenious proofs. Let $A,B$ be subsets of size $m$ in an Abelian group. We use the notation $A+B = \{a+b a \in A, b \in B \}$ (here + is the group operation; later we'll use both addition and multipliciation over a field). Further if $G=(A,B;E)$ is a bipartite graph on $A,B$, we let $A+_G B = \{a+b a \in A, b \in B, (a,b) \in E \}$. The theorems below will hold for all choices of $m$ and sets $A,B$ (and $C$) of this size. Thm [Ruzsa, Plunneke]: For every $k$, if $|A+B|=km$, then $|A+A| \leq k^2 m$. Thm [Gowers, Balog-Szemeredi]: For every $k$ and bipartite graph $G=(A,B;E)$ with $|E| \geq m^2/k$, if |A+_G B| \leq km, then there exist subsest $A' \subseteq A$ and $B' \subseteq B$ such that $|A' + B'| \leq k^8 m$ Thm [Erdos-Szemeredi, Elekes]: Let $A$ be a subset of size $m$ of the real numbers. Then either $|A+A|$ or $|A \times A|$ is $ \geq m^{5/4}$ Thm [Bourgain-Katz-Tao]: Let $A$ be a subset of size $m$ of a prime field $GF(p)$, $p^{.01} \leq m \leq p^{.99}$. Then either $|A+A|$ or $|A \times A|$ is $\geq m^{1.0001}$