Arithmetic progressions in sumsets

Abstract.

We prove several results concerning arithmetic progressions in sets of integers. Suppose, for example, that $\alpha$ and $\beta$ are positive reals, that N is a large prime and that $C,D \subseteq {\Bbb Z}/N{\Bbb Z}$ have sizes $\gamma N$ and $\delta N$ respectively. Then the sumset C + D contains an AP of length at least $e^{c \sqrt{\rm log} N}$, where c > 0 depends only on $\gamma$ and $\delta$. In deriving these results we introduce the concept of hereditary non-uniformity (HNU) for subsets of ${\Bbb Z}/N{\Bbb Z}$, and prove a structural result for sets with this property.