MATH/CMSC 38405: Arithmetic Combinatorics
Spring 24: Tuesday, Thursday 2pm-3:20pm (Eckhart 308)
- Office hours. By appointment (send me e-mail). The easiest way is to talk right after class,
and the preferred way is to ask your question on Ed -- this way more people may benefit from the discussion.
-
Literature. Much of the material can be found in the monograph [1] which is the closest to "a textbook"
this course has. For older results, particularly in the first part of the course, see also [2], and you may
want to check out the most recent addition to the family [3]. References to more specific sources covering
individual topics will be 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.
- Y. Zhao, Graph Theory and Additive Combinatorics:
Exploring Structure and Randomness, Cambridge University Press, 2023.
- P. Frankl, A new short proof for the Kruskal-Katona theorem, Discrete Mathematics, 48, 1984, 327-329.
- P. Frankl, Extremal Set Systems, Chapter 24 in Handbook of Combinatorics, Elsevier, 1995.
-
T. Sanders, On the Bogolubov-Ruzsa lemma, Analysis & PDE, 5(3): 627-655, 2012.
-
W. Gowers, B. Green, F. Manners, T. Tao, On a conjecture of Morton, 2023.
-
W. Gowers, B. Green, F. Manners, T. Tao, Marton's Conjecture in abelian groups with bounded torsion, 2024.
- 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.
-
R. O'Donnell, Analysis of Boolean functions, Cambridge University Press, 2014.
-
M. Rudnev, S. Stevens, An update on the sum-product problem,
Mathematical Proceedings of the Cambridge Philosophical Society, 173(2):411-430, 2022.
- M.-C. Chang, Product theorems in SL_2 and SL_3, J. Inst. Math. Jussieu, 7: 1-25,
2008.
-
A. Razborov, A product theorem in free groups, Annals of Mathematics, 179, No 2, 2014, 405-429.
-
F. Chung, R. Graham and R. Wilson, Quasi-Random Graphs, Combinatorica, 9(4),
1989, 345-362.
-
L. Coregliano, A. Razborov, Natural Quasirandom Properties, Random Structures and Algorithms, 63(3), 2023, 624-688.
- I. Ruzsa and A. Szemeredi, Triple systems with no six points carrying three triangles,
Colloq. Math. Soc. J. Bolyai 18 (1978), 939-945.
-
A. Shapiro, M. Tyomkyn, A new approach for the Brown-Erdos-Sos problem, 2023.
-
N. Alon, E. Fisher, M. Krivelevich and M. Szegedy, Efficient Testing of large Graphs, Combinatorica, 20(4), 2000, 451-476.
-
L. Coregliano, A. Razborov, Semantic Limits of Dense Combinatorial Objects, Russian Mathematical Surveys, 75(4), 2020, 627-724.
-
J. Fox, L. M. Lovasz, A tight lower bound for Szemeredi's regularity lemma, Combinatorica, 37(5), 2017, 911-951.
- J. Fox, A new proof of the graph removal lemma, Annals of Mathematics, 174,
2011, 561-579.
- 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.
- E. Viola, Correlation bounds for polynomials over {0,1}, ACM SIGACT News,
40(1), 2009.
- 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.
-
Z. Dvir, On the size of Kakeya sets in finite fields, Journal of the American Mathematical Society, 22 (4), 2009, 1093-1097.
-
L. Lovasz, Large networks and graph limits, American Mathematical Society, 2012.
- A. Razborov, Flag Algebras, Journal of Symbolic Logic, 72(4), 2007, 1239-1282.
-
H. Hatami, S. Norin(e), Undecidability of linear inequalities in graph
homomorphism densities, Journal of the American Mathematical
Society, 24(2), 2011, 547-565.
-
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]. Vosper's theorem (without
proof): [1, Theorem 5.9]. Kneser's theorem (without proof): [1, Theorem 5.5]. "(3k-3) theorem" (without proof):
[1, Theorem 5.11]. Frankl's proof of Kruskal-Katona Theorem: [4]. For
other applications of the shifting technique in extremal combinatorics
see e.g. [5]. Doubling constants: [1, Chapter 2.2].
-
Second week: Discussion of doubling constants cntd. Discussion of
Freiman-Rusza type results, including recent breakthroughs [6,7,8]. Freiman's original theorem
(statements): torsion-free case [1, Theorem 5.32], torsion case [1, Theorem 5.27]. The dimension bound:
[1, Lemma 5.13]. The idea of Bogolyubov-Ruzsa lemma goes back to [9], and the term was (apparently) coined in [6]. Ruzsa's covering
lemma: [1, Lemma 2.14]. Reduction from Freiman's theorem to Bobolubov-Rusza lemma, modulo properization (needed only in torsion-free case) and Plunnecke-Ruzsa estimates. "Properization" ("outer" version, without proof) : [1, Theorem 3.40]. Ruzsa triangle inequality: [1, Lemma 2.6]. Ruzsa distance: [1,
Definition 2.5]. Plunnecke-Ruzsa estimates (Petridis's proof): [10]; for the old-fashioned proof see [1, Section 6.5] or [2, Section 7]. This concludes the reduction to Bobolubov-Ruzsa lemma. Freiman's isomorphisms preserve the structure of
"objects": [1, Proposition 5.24] (torsion case is similar and easier). Reduction to Z_N in the torsion-free case: [1, Lemma 5.26].
-
Third week: Reduction to Z_N 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 [11] (characteristic 2). Both sources also contain all basic facts
we reviewed, and I in particular recommend [11] if you want to learn about other applications of DFT in combinatorics and theoretical computer science. 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); the proof of Freiman's theorem in the torsion case conmpleted. 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], this concludes Ruzsa's proof of Freiman theorem in the torsion-free case.
- Fourth week: Polynomial Freiman-Rusza in the torsion case (main ideas): [7,8]. 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 record
bound for the Erdos-Szemeredi's conjecture: [12]. 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].
- Fifth week: Quotient sets are sub-fields: [1, Corollary 2.52]. 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)$ [13] and in the free group [14]. Szemeredi's theorem and its different proofs are 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 small increase in $\epsilon$. The theory of quasi-random graphs was started in [15]; for a far-reaching generalization to other combinatorial objects see [16]. For the Groethendick inequality and known bounds for the Groethendick constant see the Wkipedia article. 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 [17]. The induced matchings theorem: [1, Proposition 10.45].
-
Sixth week: (6,3)-theorem: [1, Exercise 10.6.2]. Its (k+3,k)-generalization is known
as the Brown-Erdos-Sos conjecture and [18] seems to be the latest word on it. Induced removal lemma: [19].
Simplex (aka hypergraph) removal lemma:
Wikipedia article. For a
very general (but non-constructive) version of the induced removal lemma see [20, Theorem 3.3].
Lower bounds for Szemeredi's regularity lemma: [21] and the literature cited therein.
The best known upper bound in the triangle removal lemma: [22]. Gowers's proof of Szemeredi's theorem is
sketched in [1, Sections 11.1-11.4]. We defined Gowers uniformity norms via the expanded formula [1, (11.1)],
its recursive definition: [1, Definition 11.2]. Cases d=0,1,2: [1, pages 418-419]. 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: von Neumann theorem cntd. The general strategy of the (analytical) proof of
Szemeredi's theorem is discussed throughout [1, Sections 11.1-11.4]. $u^d$ norms and their relations to
$U^d$: [1, page 426]. Density Increment Theorem (proved only for $d=2$): [1, Proposition 11.10].
Inverse Theorem
for $U^3$ (without proof): [1, Theorem 11.9]. "Erdos-Turan conjecture": Wikipedia
article. Green-Tao theorem on arithmetic progressions in primes: [23], our informal overview
mostly followed the exposition in [24]. A survey on polynomial correlation bounds: [25]. For
multi-party communication complexity see Wikipedia article, some
of its most important applications go back to [26].
-
Eighth week: "Inverse theorem" for multi-party communication complexity is also implicit in [26]. Combinatorial Nullstellensatz: [1, Theorem 9.2], and the forthcoming sections contain many of its applications in additive combinatorics proper. Kakeya sets over finite fields: [27]. Quasi-random graphs were introduced in [15]. For the account of relations between various counting options see [28, Sct. 5.2.3]. The "mega-theorem" on various characterizations of quasi-random graphs is essentially taken from [15] (there are a few more items in the paper).
-
Nineth week: "Mega-theorem" cntd. For the rest of the material see [28, 29, 20]. Convergent sequences. Graphons. Cut norm and cut distance for graphons and its significance [28, Chapter 8]. Uniqueness theorem (without proof): [28, Thm. 13.10]. Graphings (bounded degree case): [28, Part 4]. Flag algebras were introduced in [29], see also surprizingly detailed (I do not have anything to do with it :-) ) Wikipedia page. Undecidability result (without proof): [30].