Ma 191c-sec6:  Additive combinatorics (Spring 2015-16)

## ANNOUNCEMENTS

• If you are giving a talk in class, please first go over the lecture tips.

## COURSE DESCRIPTION

"Additive combinatorics" is a very active subfield of mathematical research, which combines combinatorics, number theory, and harmonic analysis. Since it is difficult to define additive combinatorics in a clear short way, we instead present a few examples of main problems in this field:

• How large can a subset of $$\{1,2,3,...,n\}$$ be without containing a 3-term arithmetic progression in it; equivalently, showing that every subset that is sufficiently dense must contain such a progression (Roth's theorem)
• What subsets $$A \in \{1,2,3,...,n\}$$ have a small sum set $$A+A=\{a+a' : a,a' \in A\}$$ (the polynomial Freiman-Ruzsa conjecture).
• Are there subsets $$A \in \{1,2,3,...,n\}$$ have both a small sum set $$A+A=\{a+a' : a,a' \in A\}$$ and a small product set $$AA=\{aa' : a,a' \in A\}$$ (the Erdős–-Szemerédi conjecture).

Detailed lecture notes would be uploaded before each class (for example, see last year's polynomial method lecture notes). Other sources for additive combinatorics material are the book of Tao and Vu, lecture notes by Gowers, Ruzsa, Green, Soundararajan, and others, and surveys of Shachar Lovett (one and two).

Each course participant is expected to read one related paper and to present it in class. This webpage will contain a list of possible papers. If more than a few students enroll, some of the undergrad participants would instead submit 3 homework assignments. Students are also expected to attend most of the classes.

## PREREQUISITES

The class requires a basic mathematical understanding, such as basic familiarity with combinatorics, probability, and groups. For other topics, such as the Fourier transform, we will go over the basics in class.

## SCHEDULE

MWF 15:00 - 15:55, 103 Downs.

## INSTRUCTORS

HARRY BATEMAN INSTRUCTOR IN MATHEMATICS
276 Sloan, 626-395-4347,

## TA's

- Pooya Vahidi, pvahidif@caltech.edu.

## LECTURE NOTES

Date Description Notes
---- Preliminaries Chapter 0
March 28th Sets with small doubling Chapter 1
March 30th Ruzsa's inequality and Plünnecke's inequality Chapter 1
April 1st Freiman's theorem with bounded order and intro to the sum-product problem Chapter 2
April 4th Elekes' sum-product proof and related results Chapter 2
April 6th Solymosi's sum-product bound and related results Chapter 2
April 8th One final sum-product variant and introduction to Balog-Szemeredi-Gowers Chapter 3
April 11th Schoen's BSG proof Chapter 3
April 13th BSG variants and beginning the proof of Sudakov, Szemerédi, and Vu Chapter 3
April 15th Introduction to progressions in dense sets, Behrend's construction Chapter 4
April 18th Basics of the Fourier transform over finite fields Chapter 4
April 20th Meshulam's theorem Chapter 4
April 22nd Roth's theorem Chapter 4
April 25th Completing Roth and beginning Sanders' quasi-polynomial Freiman-Ruzsa Chapter 5
April 27th The Bogolyubov-Ruzsa lemma Chapter 5
April 29th No class today ---
May 2nd Completing Sanders' quasi-polynomial Freiman-Ruzsa (almost) Chapter 5
May 4th Rich translations via convolutions Chapter 5
May 6th Gaurav Sinha presents the paper "A new bound on partial sum-sets and difference-sets, and applications to the Kakeya conjecture" by Katz and Tao ---
May 9th No class today. ---
May 11th No class today. ---
May 13th Ryan Yoo presents the paper "Integer sets containing no arithmetic progressions" by Heath-Brown. ---
May 16th Laura Shou presents the paper "A trilinear maximal inequality via arithmetic combinatorics" by Demeter, Tao, and Thiele. ---
May 18th Cosmin Pohoata presents the paper "Progression-free sets in $$Z^n_4$$ are exponentially small" by Croot, Lev, and Pach. ---
May 19th
10:30am, SLN 151
(Make-up class) Third moment energy. Chapter 6
May 20th Pooya Vahidi presents the paper "Near optimal bounds in Freiman's theorem" by Schoen. ---
May 23rd Bella Guo presents the paper "Embeddability properties of difference sets" by Di Nasso ---
May 25th Karlming Chen presents the paper "A probabilistic technique for finding almost-periods of convolutions" by Croot and Sisask ---
May 27th Angad Singh presents the paper "New counterexamples for sums-differences" by Lemm. ---
June 3rd (Make-up class) Alex McDonald presents the paper "A low-energy decomposition theorem" by Balog and Wooley. ---

## HOMEWORK

Due Date Homework
April 14th Assignment 1
April 26th Assignment 2
May 25th Assignment 3

• Near optimal bounds in Freiman’s theorem by Schoen. The title is self explanatory. In class we will prove a stronger bound for the special case of $${\mathbb F}^n_2$$, while this paper focuses on $${\mathbb Z}$$.