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

Adam Sheffer
HARRY BATEMAN INSTRUCTOR IN MATHEMATICS
276 Sloan, 626-395-4347,
adamsh@caltech.edu

## 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

## READING

The following is a list of papers for students who give a talk in class. You may also suggest papers that are not on this list.

• New sum-product type estimates over finite fields by Roche-Newton, Rudnev, and Shkredov. This is the current best sum-product bound over finite fields. It has a short proof that is based on an incidence bound, so if you present it you should also discuss this incidence bound.
• Higher moments of convolutions by Schoen and Shkredov. This paper uses several techniques to study a generalization of the concept of energy. Since it is too long for one class, you can either present a part of it, or two students can do it together during two class.
• 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}$$.
• A new bound on partial sum-sets and difference-sets, and applications to the Kakeya conjecture by Katz and Tao. Obtaining a bound for the Kakeya problem by examining sums and difference of sets. If you talk about this paper, you should also describe the Kakeya problem and the connection to it.
• On additive doubling and energy by Katz and Koester. Studying a property of sets that is called smoothing, and connecting it to doubling.
• If you are interested in connections between additive combinatorics and theoretical computer science, you can find many relevant papers in Lovett's survey.
• In class we will prove the original bound for Roth's theorem. If you would like a more analysis-oriented paper, you are welcome to present any later bound for the problem. For a list of these bound, see for example here (the latest bound by Bloom is probably too much for one class).
• A low-energy decomposition theorem by Balog and Wooley. Proving that "any finite set of real numbers can be split into two parts, one part being highly non-additive and the other highly nonmultiplicative".
• Further improvements to incidence and Beck-type bounds over prime finite fields by Jones. Using a sum-product bound to obtain incidence bound in finite fields.
• A probabilistic technique for finding almost-periods of convolutions by Croot and Sisask. Introduces a powerful tool concerning convolutions of sets. We will introduce a special case of this result in class, and then you will talk about the general case.