MATH/CMSC 38405: Arithmetic Combinatorics
Spring 20: Tuesday, Thursday 2pm-3:20pm
-
Office hours. By appointment (send me e-mail).
-
Literature. Much of the material can be found in the monograph [1]. For older results,
particularly in the first part of the course, see also [2]. References to more specific sources covering individual topics will
be also posted here as we are making 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.
- N. N. Bogolyubov, On some arithmetic properties of quasi-periods (French and Ukranian), Ann.
Chaire Phys. Math. Acad. Sci. Ukraine (Kiev), 4, 1939, 195-205.
-
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.
-
B. Green, Notes on the polynomial Freiman-Ruzsa conjecture.
-
T. Sanders, On the Bogolubov-Ruzsa lemma, Analysis & PDE, 5(3): 627-655, 2012.
-
G. Shakan, On higher energy decompositions and the sum-product
phenomenon.
-
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.
- M.-C. Chang, Product theorems in SL_2 and SL_3, J. Inst. Math. Jussieu, 7: 1-25,
2008.
- 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.
-
B. Green, T. Tao, The primes contain arbitrarily long arithmetic progressions, Annals of Mathematics, 167, 2008, 481-547.
-
D. Conlon, David, J. Fox, Y. Zhao, The Green-Tao theorem: an exposition, EMS Surveys in
Mathematical Sciences, 1 (2), 2014, 249–282.
-
L, Babai, N. Nisan, M. Szegedy, Multiparty protocols, pseudorandom generators for logspace, and
time-space trade-offs, Journal of Computer and System Sciences, 45 (2), 1992, 204–232,
-
E. Viola, Correlation bounds for polynomials over {0,1},
ACM SIGACT News, 40(1), 2009.
-
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, Flag Algebras, Journal of Symbolic Logic, 72(4), 2007, 1239-1282.
-
L. Coregliano, A. Razborov, Semantic
Limits of Dense Combinatorial Objects, 2019.
-
Ongoing syllabus and additional references. This section will be updated regularly, normally at the end of
a week.
- First week: introduction. |A+B|>= |A|+|B|-1 over integers: [1, Lemma 5.3]. Inverse result: [1,
Proposition 5.8]. e-transforms and their properties: [1, Lemma 5.2]. Cauchy-Davenport theorem: [1,
Theorem 5.4]. Kneser's theorem (without proof): [1, Theorem 5.5]. Vosper's theorem (without
proof):[1, Theorem 5.9]. (3k-3) theorem (without proof): [1, Theorem 5.11]. Frankl's proof of
Kruskal-Katona Theorem: [3]. Doubling constants: [1, Chapter 2.2 ].
-
Second week: Freiman's theorem: discussion. Doubling constants and multi-dimensional arithmetic progressions,
proper progressions. "Properization" ("outer" version, without proof): [1, Theorem 3.40]. Freiman's theorem
(statements): torsion-free case [1, Theorem 5.32], torsion case [1, Theorem 5.27]. 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]. The idea of Bogolyubov-Ruzsa lemma goes back to [4]. Ruzsa's covering
lemma: [1, Lemma 2.14]. Ruzsa triangle inequality: [1, Lemma 2.6]. Ruzsa distance: [1,
Definition 2.5]. Plunnecke-Ruzsa estimates (Petridis's proof): [5]. Freiman's isomororphisms: [1, Section 5.3].
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:
[6, Section 3.2] (torsion case), [1, Lemma 5.26] (torsion-free case).
-
Third week: good modelling cntd. 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]
and [7] (characteristic 2). Both sources also contain all basic facts
we reviewed. Very Important Characters: [1, Definition 4.34]. Bohr sets: [1, Section 4.4]. Bohr sets are in 2A-2A:
[1, Proposition 4.39]; note that we worked under the stronger assumption of good modelling hence our proof is
much simpler. Geometry of numbers: [1, Sections 3.1.1, 3.1.2, 3.5]. Minkowski's second theorem:
[1, Theorem 3.30]. Bohr sets contain large generalized arithmetic progressions: [1, Proposition 4.23]. Collision
numbers (aka additive energy): [1, Definition 2.8]. Statistical version of Plunnecke-Ruzsa estimates (without proof):
[8, Section 6]. Balog-Szemeredi-Gowers theorem (without proof): [1, Theorems 2.31, 2.29]. For an extended
discussion of the Polynomial Freiman-Rusza conjecture see e.g. [9]. Quasi-Polynomial Freiman-Rusza: [10];
our proof for $\mathbb Z_2^n$ closely follows the exposition in [6].
-
Fourth week: Quasi-Polynomial Freiman-Rusza cntd. Our account of Erdos-Szemeredi'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-Szemeredi's
conjecture: [11]. Bourgain-Katz-Tao theorem (sum-product estimates in finite fields): [1, Theorem 2.55].
Katz-Tao lemma: [1, Lemma 2.53]. 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.
- Fifth week: Construction of ordinary Ramsey graphs from bipartite ones. 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)$ [14] and in the free group [8]. Szemeredi's theorem
and its different proofs is covered in two sections of [1]: Section 11 and Section 12. Behrend's example:
[1, Exercise 10.1.4]. 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 latest paper on Grothendieck inequality is [15]. 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 [16]. More
recent proof with a slightly better bound: [17]. The induced matchings theorem: [1, Proposition 10.45].
(6,3)-theorem: [1, Exercise 10.6.2].
-
Sixth week: (6,3)-theorem cntd. Induced removal lemmas and property testing: [18]. Lower
bounds for Szemeredi's regularity lemma: [19] and the literature cited therein. 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)]. Recursive definition of
Gowers norms: [1, Definition 11.2]. Gowers inner product, Gowers-Cauchy-Shwarz inequality and Gowers
triangle nequality: [1, pages 419-420]. Generalized von Neumann theorem: [1, Lemma 11.4].
- Seventh week: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]. Inverse Theorem for $U^3$ (without proof): [1, Theorem 11.9]. "Erdos-Turan conjecture": Wikipedia
article. Green-Tao theorem on arithmetic progressions in primes: [20], see also exposition in [21].
Multi-party communication complexity: [22], see also Wikipedia
article and the literature cited therein. A survey on polynomial correlation bounds: [23].
Quasi-randomness: [24].
- Eighth week: Quasi-randomness cntd. Graph limits: [25]. Flag algebras: [26]. Unified theory
for general combinatorial objects: [27]. Projects: Testing of Monotone Graph Properties (Yu).
- Ninth week (short):
Projects. Basic Results Using Flag Algebras (Asness). Minkowski's Second Theorem (Getzelman).