Finite structures, combinatorial regularity, and measuring semirings

This is a proposal in model theory, a branch of mathematical logic which investigates objects of mathematics such as graphs and groups in terms of expressibility in formal logical languages. The focus of the project is on `definable sets' (solution sets of formulas of first order logic), especially in finite structures. The proposal has connections to combinatorics and to group representation theory. A famous 1954 paper of Lang and Weil gives estimates for the number of solutions in a finite field of a system of polynomials over the field. This was generalised by Chatzidakis, van den Dries and Macintyre (1992) to solutions in finite fields of arbitrary logical formulas. Their theorem became the motivating example of an `asymptotic class' of finite structures in any first order language, a concept introduced by Elwes, Macpherson and Steinhorn around 2007-8. The latter was enriched to the much broader and more flexible framework of `multidimensional asymptotic class' (m.a.c.) of finite structures, with wide-ranging examples, in a recent preprint of Anscombe, Macpherson, Steinhorn and Wolf. There is a stronger notion of multidimensional exact class (m.e.c.) where sizes of solution sets are given exactly. Just as the Elwes-Macpherson-Steinhorn work yielded a notion of infinite `measurable’ structure, with examples arising from asymptotic classes via the model-theoretic ultraproduct construction, there are notions of `generalized measurable’ and `ring-measurable’ infinite structure, whereby definable sets are assigned values in an ordered `measuring semiring' or ring. Examples are given by ultraproducts of m.a.c.s and m.e.c.s respectively. There is an interesting interplay between properties of the m.a.c./m.e.c and of the ultraproduct. The above work has opened three new directions for exploration in this project. We aim for initial results in each direction, opening up their potential. First, existence problems about m.e.c.s with specified ultraproducts lead to natural questions about combinatorial regularity properties, akin to conditions arising with the Weisfeiler-Leman algorithm; the latter is important for example for algorithms which verify whether two finite graphs are isomorphic. Lachlan in the 1980s developed a beautiful description of finite structures (in a finite relational language) which are `homogeneous’; we will explore whether Lachlan’s structure theory can be developed just under combinatorial regularity conditions, without symmetry/homogeneity assumptions. (`Regularity' of a graph -- the property that all vertices have the same number of neighbours -- is an example of a (weak) combinatorial regularity property; it is implied by the much stronger symmetry condition that the automorphism group is vertex-transitive.) Second, motivated by representation theory, Harman, Snowden and coauthors have developed a rich theory around measures on omega-categorical structures and on their automorphism groups (which are `oligomorphic' groups) and we will investigate several possible connections of their work to generalised measurable structures; in particular whether certain vector space structures endowed with multilinear forms with `linear oligomorphic’ automorphism groups are generalized measurable and have other good model-theoretic and group-theoretic properties. Third, Evans and later Marimon have recently shown that the 2008 Macpherson-Steinhorn notion of measurable structure has strong model-theoretic consequences (higher amalgamation). We will explore the model-theoretic content of generalized and ring measurability (e.g. n-amalgamation, and generalised stability conditions) under natural assumptions on the measuring semiring or ring. Furthermore, recent work of Chevalier and Hrushovski shows that measurability has interesting consequences related to piecewise-interpretable Hilbert spaces, and we will explore this under the much more flexible setting of generalised measurability.