Combinatorial expansion, regularity and model theoretic independence

Model theory is the branch of mathematical logic that deals with the relationship between formal languages and mathematical objects . The first applications, in 1940s, were the results of quantifier elimination and decidability for algebraically closed fields and real closed fields (Tarski). Since the 1970s, several classes of theories have been identified by combinatorial conditions; for the restricted class of stable theories Saharon Shelah developed a notion of independence that generalizes linear independence in vector spaces and algebraic independence in algebraically closed fields. Then, Zilber and Hrushovski established links between certain geometric configurations and the existence of definable algebraic objects interpreting geometrically this independence concept.

In 2009 Hrushovski noted a parallel between stability-theoretic techniques and methods in additive combinatorics. This led to an importation of model-theoretic tools into combinatorics, and a model-theoretic interest in combinatorial questions. The context is that pseudo-finite structures model the limit behaviour of the corresponding finite objects studied in combinatorics. They are endowed with the pseudo-finite counting measure, which can play the role of stability-theoretic dimension.

Now, let P be a polynomial in k variables over F, a finite field. Given k 'non-trivial' subsets of F, an interest of number theory and combinatorics is to describe the image set of them given by P. A common phenomenon is that it tends to be bigger than the original sets. The initial aim of this PhD thesis is to study this phenomenon expanding the results of [1] and, in particular, solving some open questions. In this context, it is convenient to study the asymptotic behaviour while the cardinal of F tends to be infinite but the degree of P and k still bounded and the size of the k subsets is controlled. This study is naturally realized by model theoretic techniques when F is replaced by a pseudo-finite field.
The asymptotic behaviour may show diverse orders of increase. Many different expansion properties for polynomials could be defined. For example, P could be a weak expander or a moderate asymmetric expander. The definitions of these properties are the initial point of [1].

For some of these expansion properties it has been found a precise classification when k=2, but there are still some open questions. These classifications are the main results of [1], proved by a new algebraic regularity lemma. However, in the case of almost strong asymmetric expanders, the theorem remains some open questions. In particular, we wonder whether the statement can be simplified.

It might be interesting to find results and techniques for more cases. Indeed, [1] only describes 3 of the 10 defined expanders in the case k=2. Furthermore, there are not strong results for k>2. The majority of these expansion properties are not completely characterised.

On the other hand, the algebraic regularity lemma, which is a fundamental element of [1], is particularly interesting. It is related with combinatorics, improving upon the Szemerédi regularity lemma [2]. Also, it has a qualitative version akin to differential geometry. Therefore, we wonder whether there are more applications of this result.

Another related topic which this thesis will investigate is the extension given in [8] of sum set theory to metric groups, replacing cardinals for the metric entropy. Again, the model theoretic approach seems to produce relevant results, in particular applying [9].

Initially, the main references will be [1] and Hrushovski's comments of [1], but also it will be studied the theory of pseudo-finite fields and some advanced model theoretic results. For the sum metric entropy theory, the main references will be [8], [9] and Hrushovski's comments on metrically approximate subgroups.

This project falls within the EPSRC research area of Logic and Combinatorics.