Math 595: Expander Graphs in Number Theory

Fall 2015

MWF 3-3:50PM, 441 Altgeld Hall

Professor: Elena Fuchs
Office: 359 Altgeld Hall
Email: lenfuchs at illinois dot edu
Office hours: by appointment

This course will explore various aspects of expander graphs, with a view towards applications in number theory, specifically that of the Affine Sieve developed by Bourgain-Gamburd-Sarnak in 2009. We will give three definitions of expander graphs and show that they are equivalent, we will then explore the application of expander graphs in the Affine Sieve, and, finally, we will prove that certain concrete families of graphs (obtained as Cayley graphs connected to certain finitely generated subgroups of SL_2(Z)) are indeed expanders.

Textbook and Prerequisites:

We have no official textbook but a good reference for the expander graphs section is E. Kowalski's lecture notes on expander graphs. We will also be going into aspects of Bourgain-Gamburd-Sarnak's first paper on the affine sieve, as well as some papers on the number theory of Apollonian packings. Please see the list of useful links below for the most relevant literature.

The prerequisite for this course is a knowledge of linear algebra and the group theory part of a first semester graduate algebra course.

Grading:

Your grade for the course is based on a project which you can do together with one other student (some topics are better suited for collaboration than others). The project will be to select one of the following topics and to present it in class. I have posted some suggested references, but you may supplement those that I have suggested with others if you wish. Topics are:

Probabilistic existence of expanders. Reference: Section 4 of these notes by Terence Tao.
Multiplicative combinatorics section of E. Kowalski's notes. Reference: Appendix A in Kowalski's notes.
Zig-zag product construction of expanders. Reference: section on zig-zag in Hoory-Lineal-Widgerson's survey article.
Expander graphs in error-correcting codes. Reference: section 4.1 in Kowalski's lecture notes.
Ramanujan graphs. Reference: a survey by M. Ram Murty.
Brun Sieve. Reference: Some notes by Kiran Kedlaya. These notes by Kedlaya could also be of interest.
Role of expander graphs in Bourgain-Kontorovich's theorem on density one in Apollonian packings and Zhang's thesis on Apollonian 3-packings. Reference: Xin Zhang's thesis.
Selberg's 1/4 conjecture and implications for expansion constants of the relevant families of graphs. Reference: Chapter 4 and, more specifically, section 4.4 in Alex Lubotzky's book "Discrete groups, expanding graphs, and invariant measures."
Prime number conjecture in "Some experiments with integral Apollonian packings" by Fuchs-Sanden. Reference: the paper can be found here.

Detailed Plan:

The following is a rough outline of what we will be doing in lecture every day. It will be updated on a regular basis.

8/24: Introduction to the course, motivation for constructing expanders in number theory.
8/26: Graph theoretic terminology, examples, measuring connectedness/sparsity.
8/28: Expansion constant, relation to diameter.
8/31: Definition of expanders, more about diameter in relation to expander graphs.
9/2: Maps of graphs preserving expander property, random walks on graphs.
9/4: Random walks on graphs continued: Markov averaging operator, equidistribution radius, and absolute expanders.
9/7: Labor Day (no class).
9/9: Proof of spectral theorem for Markov averaging operator.
9/11: Equidistribution radius and its role in convergence to equilibrium in a random walk on a graph.
9/14: Wrapping up discussion of equidistribution radius, proving that expanders are absolute expanders.
9/16: Absolute expanders as expanders, Cheeger inequality.
9/18: Cheeger inequality continued, discrete Laplace operator and a "new" definition of expanders.
9/21: Cayley graphs as expanders, perturbation of graph edges and effect on spectral gap.
9/23: Bounds in terms of diameter on spectral gap for Cayley graphs; esperantist graph families.
9/25: An example of an esperantist family which is not expander; beginning investigating the question of which families of Cayley graphs are expander families, leading into Bourgain-Gamburd theorem.
9/28: Interpreting trace of Markov operator as probability of return to identity after n steps in a random walk: reducing expander problem to getting satisfactory upper bound on this probability.
9/30: Representation theory and other facts about SL_2(F_p), a useful equivalent statement of Bourgain-Gamburd's theorem.
10/2: Return probabilities: writing rp(X_1,X_2) in terms of max(rp(X_1), rp(X_2)) for two G-valued random variables X_1,X_2. Introducing multiplicative energy of two subsets of a group.
10/5: Some upper bounds on multiplicative energy, beginning to consider what various ranges of values of normalized multiplicative energy e(A,B) say about the sets A,B: e.g. e(A,B)=1 iff A and B are left and right cosets of a subgroup of G.
10/7: Fine-tuning results on e(A,B) from last time: Tao's theorem and approximate subgroups.
10/9: L^2-flattening argument.
10/12: No class.
10/14: Finishing L^2 flattening, reducing Bourgain-Gamburd's theorem to proving Helfgott's theorem and showing that a random walk on G will "likely" escape from cosets of proper subgroups "quickly."
10/16: Proving escape from cosets of proper subgroups in SL_2(F_p) given that the generating set that we are given generates some subgroup of SL_2(Z) freely. Margulis's girth bounds.
10/19: Continuing from previous lecture, utilizing Dickson's classification of subgroups of SL_2(F_p) and explaining why we can reduce our study to free groups.
10/21: George Shakan talking on multiplicative combinatorics.
10/23: Starting proof of Helfgott's theorem. First steps: showing that for "very large" generating sets H of SL_2(F_p), HHH=SL_2(F_p).
10/26: Trying and failing to find counterexample to Helfgott's theorem, which gives us a hint of how to go about the proof. Proving Ruzsa's lemma which will allow us to consider k-fold products of H for k>3 rather than 3-fold products and still prove Helfgott.
10/28: Maximal tori and some theorems about them. Showing that at least one maximal torus is involved with HHH for large enough primes p.
10/30: Two key lemmas of Helfgott and deducing proof of Helfgott's theorem from these lemmas.
11/2: Sketching proofs of above lemmas.
11/4: Byron Heersink talking on expander graphs in error correcting codes.
11/6: Anton Bernshteyn proving existence of expander graphs probabilistically.
11/9: Michael Oyengo talking on the Brun and Selberg sieves.
11/11: The Affine Sieve: setup and role of expanders.
11/13: Continuing role of expanders in Affine Sieve.
11/16: Strong approximation and its role in the sieve.
11/18, 11/20, 11/30: Sneha Chaubey, Amita Malik, and Xianchang Meng talk about the prime number theorem and local to global principle for ACPs from Fuchs-Sanden paper.
12/2: Claire Merriman talks about Bourgain-Fuchs paper on positive density in ACP's.
12/4: Kyle Pratt talks about Bourgain-Kontorovich paper on local to global in ACP's.
12/7: Junxian Li presents on Selberg's 1/4 conjecture and what it implies about combinatorial spectral gaps.
12/9: Xin Zhang presents on Bourgain-Gamburd-Sarnak's generalization of Selberg's 3/16 conjecture to thin groups.

Some useful links, in alphabetical order:

J. Bourgain, A. Gamburd: Uniform expansion bounds for Cayley graphs of SL_2(F_p). We will go through several proofs from this paper in detail in this course.
J. Bourgain, A. Gamburd, P. Sarnak: Affine linear sieve, expanders, and sum-product: expander graphs in sieving.
H. Helfgott: Growth and generation in SL_2(Z/pZ). The techniques in this paper are crucial in Bourgain-Gamburd's arguments in the paper above.
S. Hoory, N. Linial and A. Wigderson: Expander graphs and their applications. This is one of the best survey papers on expander graphs, and goes into fascinating applications beyond sieve theory.
E. Kowalski: Sieve in Expansion. This is a great survey of how expansion is relevant in sieves. A good companion to Bourgain-Gamburd-Sarnak's paper.
E. Kowalski's lecture notes on expander graphs is the closest thing we have to a textbook for this course.
A. Lubotzky: Expander graphs in pure and applied mathematics. Another wonderful survey on expander graphs, including their application to sieve theory.

Instructions in event of emergency