Structure and Randomness: An Invitation to Additive Combinatorics

Mariah Hamel and Neil Lyall

Problems in the exciting and fast growing area of Additive Combinatorics combine aspects of number theory, analysis and combinatorics. A famous example is Szemer´edi's theorem, stating that if a set contains a "positive proportion" of the natural numbers, then it must contain arbitrary long arithmetic progressions. Several proofs of this deep theorem are now known. Although Szemer´edi's original proof used elaborate combinatorial methods, and the later proofs of Furstenberg and Gowers used dynamics and generalized Fourier analysis, respectively, the general strategy of each proof follows a similar outline. All three proofs are based on a fundamental dichotomy between structure and randomness, which in turn leads (roughly speaking) to a decomposition of any object into a structured component and a random component. One striking recent application of this dichotomy is the result of Green and Tao establishing that the prime numbers contain arbitrarily long arithmetic progressions (despite containing only a "zero proportion" of the integers).
The participants of this REU were:

Stephanie Bell (University of Montana)
Cliff Blakestad (Caltech)
Bryan Gillespie (Penn State)
Will Grodzicki (Pomona College)
Hans Parshall (Humboldt State)
Lucia Petito (University of Rochester)
Catherine Ha Ta (University of California, Irvine)
Frank Xiao (Princeton University)
The purpose of this REU was two-fold. First, we introduced students to the area of additive combinatorics through preliminary lectures, problems and exercise sheets focusing on combinatorial and discrete Fourier analytic methods. In contrast to the the usual lecture based learning, these exercise sheets allowed students to 'discover' known proofs of theorems such as van der Waerden's Theorem and Roth's Theorem on arithmetic progressions. Second, students completed individual and group, non computer-based, research projects.
For more detailed information, see our REU webpage.