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
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.
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.
We show a Khintchine-type extension of the Roth theorem for amenable groups. Namely, if $T_1, T_2$ are two commuting probability measure-preserving actions of a countable amenable group such that the group spanned by these actions acts ergodically, then $mu(Acap T_{1}^{g}A cap T_{1}^{g}T_{2}^{g}A) > mu(A)^{4} - epsilon$ on a syndetic set for any measurable set $A$ and any $epsilon>0$. The proof uses the concept of a sated system introduced by Austin.
Keywords of the presentation: permutation patterns, random matrices, Stanley-Wilf limits
For a permutation p, let S_n(p) be the number of permutations on n letters avoiding p. Stanley and Wilf conjectured that S_n(p)^{1/n} tends to a finite limit L(p) for each permutation p. Marcus and Tardos proved the Stanley-Wilf conjecture by a remarkably simple argument. Backed by numerical evidence, it has been conjectured by various researchers over the years that L(p) is on the order of k^2 for every permutation p on k letters. We disprove this conjecture, showing that L(p) is exponential in a power of k for almost all permutations p on k letters. The proof uses tools from probabilistic and extremal combinatorics.
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.
We present a Rainbow Ramsey version of the well-known Ramsey-type theorem of Richard Rado. Specifically, we classify the "rainbow regular" matrices. A matrix with rational entries is rainbow regular if for all sufficiently large k, for all natural numbers n, for every equinumerous k-coloring of [kn], there exists a rainbow vector in the kernel of the matrix. The proof uses techniques from the Geometry of Numbers.
Let V be the common zero set of a family of r integral homogeneous forms of degree k in n variables.
We show, assuming V is smooth and n is sufficiently large with respect to r and k, that V contains the expected number of prime points. A crucial ingredient proof is a regularization process of the system of polynomials, motivated by similar arguments in combinatorics. This however makes the the bounds on n tower-exponential type in the parameters r and k.
Next, we study the number of almost prime points on V, where one can get lower bounds under less restrictive conditions on the number of variables n, which are in agreement with the case of integer solutions. The argument combines classical Hardy-Littlewood type methods with techniques developed by Goldston-Yildirim-Pintz for short divisor sums.
Read More...
Keywords of the presentation: sum-free,sumset,doubling
A simple argument of Erdos shows that every set of integers has a subset of relative density at least 1/3 that is sum-free, i.e. contains no solutions to x+y=z. He conjectured that the constant 1/3 is best possible.
This conjecture was recently proved by Sean Eberhard, Ben Green and the speaker. A key component of the proof is a structural result concerning sets of integers with doubling constant strictly less than 4.
We will attempt to outline the proof of the sum-free statement, with an emphasis on the role of this doubling 4 lemma.
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.
If A_1,A_2,..., A_h are nonempty subsets of a group G, then their product set is
A_1 A_2 ... A_h = { x_1 x_2 ... x_h : x_i in A_i for i=1, 2,..., h }.
If A_i = A for all i=1,..., h, then we denote the product set A_1A_2 ... A_h by A^h.
A nonempty subset A of a group G is a K-approximate group if
there exists a subset X of G such that |X| leq K and A^2 subseteq XA.
We do not assume that A contains the identity, nor that A is symmetric,
nor that A is finite. The set A is an asymptotic K-approximate group
if the product set A^h is a K-approximate group for all sufficiently large h.
Theorem 1: Every finite set of integers is an asymptotic 3-approximate group.
Theorem 2: Every finite subset of the additive group Z^n of n-dimensional
lattice points is an asymptotic K-approximate group.
Theorem 3: Every finite subset of an abelian group is an asymptotic K-approximate group.
These results suggest the following questions.
Problem 1: Is every finite subset of the Heisenberg group H_3(Z) an asymptotic K-approximate group?
Problem 2: Is every finite subset of a nilpotent group an asymptotic K-approximate group?
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.
We are interested in the Furstenberg-Katnelson-type results in the discrete setting: Finding a congruent copy of a sufficiently large dilate of a finite configuration in a set of positive density in integer lattice of sufficiently large dimensions. The simplest case, when the configuration has just 2 points, is to say that such a set contains all sufficiently large distances. We will discuss an approach to distance problem using convolutions of surface measures, making kernels less singular and apply the idea of characteristic factors from ergodic theory. This avoids the use of spectral measure and seems more generalizable to more complicated configurations.
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.
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.