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

Tim Austin (New York University)

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.

Qing Chu (The Ohio State University)

Lower Bound in the Roth Theorem for Amenable Groups

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.

Jacob Fox (Massachusetts Institute of Technology)

Stanley-Wilf Limits are Typically Exponential

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.

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.

Reuben Neamiah La Haye (University of California)

A Rainbow Ramsey Analogue of Rado's Theorem

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.

Akos Magyar (University of British Columbia)

Prime and Almost Prime Points on Homogeneous Varieties

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.


Frederick Robert William Meath Manners (University of Oxford)

Doubling Less Than 4 and Sets with no Large Sum-Free Subset

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.

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.

Melvyn Nathanson (City University of New York)

Asymptotically Approximate Groups

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?

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.

Tatchai Titichetrakun (University of British Columbia)

An Ergodic Approach to Furstenberg-Katnelson-Weiss Type Results

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.

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: