MATH/CMSC 38405: Arithmetic Combinatorics
Course description
Spring18: Tuesday, Thursday 9:30am-10:50am (Ec 308)
-
Office hours. By appointment.
-
Literature. Most of the material pertaining to this course can be found in the monograph [1], for older results see also [2].
References to more specific sources covering individual topics will be also posted here as we make progress.
-
T. Tao and V. H. Vu, Additive Combinatorics, Cambridge University Press, 2009.
-
M. B. Nathanson, Additive Number Theory: Inverse Problems and the Geometry of Sumsets, Springer-Verlag, 1996.
-
P. Frankl, A new short proof for the Kruskal-Katona theorem, Discrete Mathematics, 48, 1984, 327-329.
-
B. Green, Notes on the polynomial Freiman-Ruzsa conjecture.
-
T. Sanders, On the Bogolubov-Ruzsa lemma, Analysis & PDE, 5(3): 627-655, 2012.
-
G. Petridis, New proofs of Plunnecke-type estimates for product sets in groups,
Combinatorica, 32, No 6, 2012, 721-733.
-
S. Lovett, An exposition of Sanders' Quasi-Polynomial Freiman-Ruzsa Theorem, Theory of Computing, Graduate Surveys 6 (2015), pp. 1-14
-
R. O'Donnell, Analysis of Boolean functions, Cambridge University Press, 2014.
-
A. Razborov, A product theorem in free groups, Annals of Mathematics, 179, No 2, 2014, 405-429.
-
M.-C. Chang, Product theorems in SL_2 and SL_3, J. Inst. Math. Jussieu, 7: 1-25, 2008.
-
J, Solymosi, An upper bound on the multiplicative energy, 2008.
-
B. Barak, R, Impagliazzo, A. Wigderson, Extracting randomness using few independent sources, SIAM Journal on Computing, 36(4): 1095-1118, 2006.
-
B. Barak, G. Kindler, R. Shaltiel, B. Sudakov and A. Wigderson, Simulating independence: New constructions of condensers, Ramsey graphs, dispersers, and extractors, Journal of the ACM, 57(4), April 2010.
-
E. Ben-Sasson, N. Ron-Zewi, M. Tulsiani and J. Wolf, Sampling-based proofs of almost-periodicity results and algorithmic applications, 2012.
-
T. Sanders, The structure theory of set addition revisited, 2012.
-
L. Lovasz, Large networks and graph limits, American Mathematical Society, 2012.
-
M. Braverman, K. Makarychev, Y. Makarychev, A. Naor, The Grothendieck constant is strictly smaller than Krivine's bound, Forum of Mathematics, Pi, 2013.
-
I. Ruzsa and A. Szemeredi, Triple systems with no six points carrying three triangles, Colloq. Math. Soc. J. Bolyai 18 (1978), 939-945.
-
J. Fox, A new proof of the graph removal lemma, Annals of Mathematics, 174, 2011, 561-579.
-
N. Alon, E. Fisher, M. Krivelevich and M. Szegedy, Efficient Testing of large Graphs, Combinatorica, 20(4), 2000, 451-476.
-
J. Fox, L. M. Lovasz, A tight lower bound for Szemeredi's regularity lemma, Combinatorica, 37(5), 2017, 911-951.
-
E. Viola, Correlation bounds for polynomials over {0,1},
ACM SIGACT News, 40(1), 2009.
-
B. Green, T. Tao, The primes contain arbitrarily long arithmetic progressions, Annals of Mathematics, 167, 2008, 481-547.
-
F. Chung, R. Graham and R. Wilson, Quasi-Random Graphs, Combinatorica, 9(4), 1989, 345-362.
-
L. Lovasz, Large networks and graph limits, American Mathematical Society, 2012.
-
A. Razborov, What is a Flag Algebra?, Notices of the American Mathematical Society, 60(10), 2013, 1324-1327.
-
Ongoing syllabus and additional references. This section will be updated regularly, normally at the end of
a week.
-
First week: administrative and introduction. |A+B|>= |A|+|B|-1 over integers: [1, Lemma 5.3]. Inverse result: [1, Proposition 5.8]. Cauchy-Davenport theorem: [1, Theorem 5.4].
Inverse result: Vosper's theorem (without proof), [1, Theorem 5.9]. e-transforms and their properties: [1, Lemma 5.2]. Kneser's theorem: [1, Theorem 5.5]. As I said in class, we do not work under the assumption e=0 (and when $e$ gets resurrected on page 202, we use the letter $h$ for it).
-
Second week: Inverse theorem for doubling constant <3/2: [1, Corollarey 5.6 ]. Frankl's proof of Kruskal-Katona Theorem: [3]. (3k-3) theorem (statement): [1, Theorem 5.11]. Freiman's theorem: discussion.
Doubling constants and multi-dimensional arithmetic progressions, proper progressions. "Properization" (statement): [1, Theorem 3.40]. Freiman's theorem:
torsion-free case [1, Theorem 5.32], torsion case [1, Theorem 5.27]. Freiman's isomororphisms: [1, Section 5.3]. For an extended discussion of the Polynomial Freiman-Rusza conjecture see e.g. [4]. Sanders's result confirming the quasi-polynomial version of it: [5].
Proof of Freiman's theorem: a (partial) overview. The dimension bound: [1, Lemma 5.13]. Plunnecke-Ruzsa estimates (statement): [1, Corollary 6.29]; for the old-fashioned proof read [1, Section 6.5] or [2, Section 7]. Ruzsa triangle inequality: [1, Lemma 2.6].
Ruzsa distance: [1, Definition 2.5].
Plunnecke-Ruzsa estimates (proof): [6].
- Third week: Plunnecke-Ruzsa estimates cntd. Ruzsa's covering lemma: [1, Lemma 2.14]. Reduction to Bobolubov-Ruzsa lemma. Freiman's isomorphisms preserve the structure of
"objects": [1, Proposition 5.24] (torsion case is similar and easier). Good (dense) modelling: [7, Section 3.2] (torsion case), [1, Lemma 5.26] (torsion-free). For general Pontryagin duality
see e.g. Wikipedia article, but we will use Fourier analysis
only on finite groups. Slightly different notational systems for it can be found in [1, Section 4.1] (close to ours, the main difference is that we prefer to call the torus by its
given name) and [8] (characteristic 2 which is the case of interest in Theory). Both sources also contain all basic facts we reviewed. Important characters:
[1, Definition 4.34]. Bohr sets (corresponding to dimensions of "boxes"): [1, Section 4.4].
-
Fourth week: Bohr sets are in 2A-2A: [1, Proposition 4.39]; note that we worked under the stronger assumption of good (dense) modelling. You can learn more about geometry of numbers from [1, Sections 3.1.1, 3.1.2, 3.5]; in particular, Minkowski's second theorem is [1, Theorem 3.30]. Bohr sets contain large generalized arithmetic progressions: [1, Proposition 4.23]. Quasi-Polynomial Freiman-Rusza: [5]; our proof for $\mathbb Z_2^n$ closely followed the exposition in [7].
-
Fifth week: Collision numbers (aka additive energy): [1, Definition 2.8]. Statistical version of Plunnecke-Ruzsa estimates (without proof):
[9, Section 6]. Balog-Szemeredi-Gowers theorem (without proof): [1, Theorems 2.31, 2.29]. Non-commutative analogues: [1, Section 2.7]; a partial generalization of the Plunnecke-Rusza theory: [1, Proposition 2.40]. Inverse theorems (without proofs): in $SL_2(\mathbb C)$ [10] and in the free group [9]. Our account of Erdos-Szemeredy's
conjecture ([1, Conjecture 8.13]) and related topics follows [1] rather closely. Elekes's bound: [1, Theorem 8.14]. Szemeredi-Trotter theorem: [1, Theorem 8.3].
Lower bounds on the crossing number: [1, Theorem 8.1]. The best known bound for Erdos-Szemeredy's
conjecture: [11]. Bourgain-Katz-Tao theorem (sum-product estimates in finite fields): [1, Theorem 2.55]. Katz-Tao lemma: [1, Lemma 2.53].
-
Sixth week: Bourgain-Katz-Tao theorem cntd. The quotient set: [1, Definition 2.49]. Quotient sets are sub-fields: [1, Corollary 2.52]. Applications to pseudo-randomness and constructive Ramsey theorems were worked out in a series of papers starting with [12]; the latest of them seems to be [13] and contains all relevant references. Szemeredi's theorem and its different proofs is covered in two sections of [1]: Section 11 and Section 12. Behrend's example (statement): [1, Exercise 10.1.4]. Guest lecturer: Madhur Tultsiani. A (slightly) different proof of the Croot-Sisask lemma: [14]. Asymmetric version of the lemma and Konyagin's trick: [15].
-
Seventh week: Behrend example cntd. Triangle Removal Lemma: [1, Lemma 10.46]. Our direct (i.e., bypassing [1, Proposition 10.45]) reduction of the case $k=3$ to this statement seems to be a part of folklore. Our definition of $\epsilon$-regular (known in certain circles as quasi-random) bipartite graphs is slightly different from [1, Definition 10.41] but is equivalent to the latter up to a polynomial increase in $\epsilon$. The standard reference on graph limits (of which quasi-random graphs make a first step) is [16]. The latest paper on Grothendieck inequality is [17]. Szemeredi's Regularity Lemma (without proof): [1, Lemma 10.42], a proof can be found in any advanced book on graph theory. The proof of Triangle Removal Lemma (as well as much of the following material) is from the seminal paper [18]. More recent proof with a slightly better bound: [19]. The induced matchings theorem: [1, Proposition 10.45]. (6,3)-theorem: [1, Exercise 10.6.2]. Induced removal lemmas and property testing: [20]. Almost tight bounds for Szemeredi's regularity lemma: [21]. Our sketch of the proof of the general version of Szemeredi's theorem follows Gowers's argument [1, Sections 11.1-11.4] rather closely. We defined Gowers uniformity norm via the expanded formula [1, (11.1)].
-
Eighth week: Recursive definition of Gowers norms: [1, Definition 11.2]. Generalized von Neumann theorem:[1, Lemma 11.4]. Gowers inner product, Gowers-Cauchy-Shwarz inequality and Gowers triangle inequality: [1, pages 419-420]. The general strategy of the proof of Szemeredi's theorem is discussed throughout [1, Sections 11.1-11.4]. Density Increment Theorem (without proof): [1, Proposition 11.10]. Characterization of $U^2$-norm via Fourier coefficients: [1, (11.3)]. $u^d$ norms and
their relations to $U^d$: [1, page 426]. A survey on polynomial correlation bounds: [22]. Inverse Theorem for $U^3$ (just mentioned): [1, Theorem 11.9]. "Erdos-Turan conjecture", analytical form: Wikipedia article. Green-Tao theorem on arithmetic progressions in primes (a discussion): [23]. Quasi-randomness: [24].
-
Nineth week: Quasi-randomness cntd. Graph limits: [25] and Flag algebras: [26]. Projects: A fun proof of
Szemeredi's regularity lemma (Bejarano).
-
Tenth week: Projects cntd. Geometry of Numbers (Zimmerman). The Polynomial Method (Sapoval).
Ergodic theory and Szemeredi's theorem (Chen). Expander Graphs (Jafarov).