September 29 - October 3, 2014
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
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
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
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.
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.
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.
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.
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.
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.Read More...
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.
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.
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.
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
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.