HOME    »    SCIENTIFIC RESOURCES    »    Volumes
Abstracts and Talk Materials
Additive and Analytic Combinatorics
September 29 - October 3, 2014

Tim Austin (Courant Institute of Mathematical Sciences)

Seminorms and Inverse Theorems in Additive Combinatorics and Ergodic Theory

Keywords of the presentation: Szemeredi's Theorem, multiple recurrence, Gowers seminorms, Host-Kra seminorms, inverse theorems

This course will be a gentle introduction to some of the technical tools that underlie recent approaches to Szemeredi's Theorem in additive combinatorics and associated questions about multiple averages in ergodic theory.

We will begin with a synopsis of Furstenberg's work relating Szemeredi's Theorem to the ergodic theoretic phenomenon of multiple recurrence, and with some of the technical background needed for this connection to bear fruit.

We will then quickly sketch Gowers' approach to Szemeredi's Theorem, which yielded the best-known bounds and pointed towards various extensions, such as the Green-Tao result for the primes. A key tool introduced by Gowers is a family of seminorms for functions on Z/n, together with an `inverse theorem' describing the structure of those functions for which these seminorms take large values. These seminorms have counterparts in ergodic theory, introduced by Host and Kra for their work on convergence of multiple averages, also along with an inverse theorem (closely related to another analysis by Ziegler, not in terms of seminorms). These ideas will be summarized with an emphasis on their commonalities. In both settings, the known inverse theorems give not only proofs of new or tightened results, but a much improved understanding of the structures responsible for them.

Having done this, the course will go into more detail about the ergodic-theoretic inverse theorems. The classical case of triple averages will be treated carefully, and its generalization covered more tersely.

Finally, we will sketch the difficulties of extending the above work, either additive combinatorial or ergodic theoretic, to results for higher-rank Abelian groups. Here the desired inverse theorems remain quite mysterious. Depending on time, we will finish with a sketch of some recent work on a simple `extremal' version of the inverse problem in higher dimensions, where one already finds considerable new structure.

Vitaly Bergelson (The Ohio State University)

Ramsey Theory at the Junction of Additive and Multiplicative Combinatorics

By analogy with the classical notions of density in the set N of natural numbers, one can introduce notions of density which are geared towards the multiplicative structure of N. Various combinatorial results involving additively large sets in (N,+) ( such as, for instance, Szemeredi's theorem on arithmetic progressions and its polynomial extensions) have natural analogs in the multiplicative semigroup (N,x). For example, muItiplicatively large sets in N contain arbitrarily long geometric progressions. One can show, that, somewhat surprisingly, multiplicatively large sets contain also arbitrarily long arithmetic progressions. The goal of this talk is to discuss some known results, open problems and conjectures pertaining to the interaction of the additive and multiplicative structures in N.

Boris Bukh (Carnegie-Mellon University)

Subsequences in Words and Oscillations

Given a set of t words made of 0's and 1's, we wish to find a pair of them with a long common subsequence. How long a subsequence can be guarantee? It turns out that this question naturally leads to a decomposition of words into pieces that oscillate at approximately the same frequency. I will explain the solution to the problem above, and to some of the related questions. Based on the the joint works with J. Ma and L. Zhou.

Mei-Chu Chang (University of California)

Incomplete Character Sums and Applications

Keywords of the presentation: character sums, primitive roots, quadratic residues, Paley Graph conjecture

In the talk, we survey various results on incomplete multiplicative character sums obtained over recent years and some of their applications. The relation with sum-product goes back as far as Vinogradov's shifted product technique and Burgess work. Methods from arithmetic combinatorics and geometry of numbers play a role in extending Burgess results to various multi-dimensional settings but unfortunately did not allow to break the 1/4 threshold so far. We also discuss a unified treatment of the Graham-Ringrose and Postnikov argument for very short character sums when the modulus has only small prime factors and give an application to integral points on Markoff-Hurwitz and Dwork hypersurfaces.

Bob Guralnick (University of Southern California)

Products of Conjugacy Classes

Keywords of the presentation: products of conjugacy classes, simple groups, algebraic groups

Let G be a finite or algebraic group. Given a multiset of conjugacy classes of G, we are interested in the product of such. This is some normal subset of G. In particular, one is interested in the size of this product and when is the product all of G. There are some nice results about the asymptotics of this situation, but we will focus on the case of two conjugacy classes. In particular if C, D are conjugacy classes of G, what is CD and when is CD=G. The key to studying this problem is a basic formula using character theory (and is not unrelated to Gower's triple product theorem). We will discuss some interesting consequences using this setup including finite simple groups admitting Beauville surfaces, fixed point spaces of elements in linear groups, products of centralizers in simple finite and algebraic groups, the Arad-Herzog conjecture and a generalization of the Baer-Suzuki theorem. On the other hand, the state of knowledge here is far from complete.

Akos Magyar (University of British Columbia)

A Relative Hypergraph Removal Lemma

Removal lemmas for hypergraphs play an important role in some problems of additive combinatorics, in particular in the multidimensional extension of Szemeredi's theorem on arithmetic progressions. We describe a removal lemma for hypergraphs with weights attached possibly to any of its edges, assuming certain randomness conditions on the weight system. As an application we obtain an essentially self-contained proof of the existence of arbitrary constellations in relative dense sets of P^d (the d-tuples of primes). If time permits we discuss certain quantitative variants and some related results. This is joint work with B. Cook and T. Titichetrakun.


Lilian Matthiesen (Institut de Mathematiques de Jussieu)

Counting Rational Points via Additive Combinatorics

In this talk we shall explain how methods introduced by Green and Tao can be used to study rational points (Hasse principle and weak approximation) on varieties defined by an equation of the form "norm form = split polynomial", where the norm form comes from a finite extension of Q and the polynomial splits into linear factors over Q. This is joint work with Tim Browning.

Jozsef Solymosi (University of British Columbia)

On the Sum-Product Problem

Let A be a finite set of integers. The sum set, A+A, is the set of pairwise sums from A and the product set, AA, is the set of pairwise products. Erdos and Szemeredi conjectured that either the sum set or the product set should be large, |A+A|+|AA| is (almost) quadratic in |A| for any subset of integers. This problem (and some of its variants) became one of the central problems in additive combinatorics.In this talk we will survey the related works and present some recent results.

Terence Tao (University of California, Los Angeles)

An Introduction to Inverse Littlewood-Offord Theory

Littlewood-Offord theory is the study of random signed sums of n integers (or more generally, vectors), being particularly concerned with the probability that such a sum equals a fixed value (such as zero) or lies in a fixed set (such as the unit ball). Inverse Littlewood-Offord theory starts with some information about such probabilities (e.g. that a signed sum equals 0 with high probability) and deduces structural information about the original spacings (typically, that they are largely contained within a progression). We give examples of such theorems and describe some of the applications to random matrix theory. Our focus will be on the simplest applications, rather than the most recent ones.

Melanie Matchett Wood (University of Wisconsin, Madison)

The Distribution of Sandpile Groups of Random Graphs

Keywords of the presentation: sandpile groups, random graphs, random matrices, random symmetric matrices, Cohen-Lenstra distribution, random matrices over finite fields

We determine the distribution of the sandpile group (a.k.a. Jacobian) of the Erdős–Rényi random graph G(n,q) as n goes to infinity. Since any particular abelian group appears with asymptotic probability 0 (as we show), it is natural ask for the asymptotic distribution of Sylow p-subgroups of sandpile groups. We prove the distributions of Sylow p-subgroups converge to specific distributions conjectured by Clancy, Leake, and Payne. These distributions are related to, but different from, the Cohen-Lenstra distribution. Our proof involves first finding the expected number of surjections from the sandpile group to any finite abelian group (the "moments" of a random variable valued in finite abelian groups). To achieve this, we show a universality result for the moments of cokernels of random symmetric integral matrices that is strong enough to handle dependence in the diagonal entries. We then show these moments determine a unique distribution despite their p^{k^2}-size growth.

Yufei Zhao (Massachusetts Institute of Technology)

The Green-Tao Theorem and a Relative Szemerédi Theorem

Keywords of the presentation: Relative Szemeredi theorem, Green-Tao theorem, arithmetic progressions, transference, counting lemma

The celebrated Green-Tao theorem states that there are arbitrarily long arithmetic progressions in the primes. In this talk, I will explain the ideas of the proof and discuss our recent simplifications.

One of the main ingredients in the proof is a relative Szemerédi theorem, which says that every relatively dense subset of a pseudorandom set of integers contains long arithmetic progressions. Our main advance is both a simplification and a strengthening of the relative Szemerédi theorem, showing that a much weaker pseudorandomness condition suffices.

Based on joint work with David Conlon and Jacob Fox.

Connect With Us: