Combinatorial Aspects of Group and Semigroup Theory

This is a project at the crossroads of group/semigroup theory and combinatorics. It consists of three parts: I. A new approach to presentations for finite simple groups. II. Redeis structure theory of finitely generated commutative semigroups and equations over finite semigroups. III. Modular aspects of combinatorial sequences satisfying a polynomial recurrence. The first part aims at applying a new and powerful method for obtaining presentations from group actions on sets, recently developed by Basarab and the principal investigator, to the study of finite simple groups. This application is based on the analysis and precise description, from a combinatorial point of view, of permutation representations of finite simple groups. The purpose of Part II is to develop an enumerative theory of equations over a class of finite semigroups. More specifically, making use of (high-dimensional) real-analytic techniques as well as Redeis structure theory for finitely generated commutative semigroups, our goal is to obtain asymptotic information concerning the number of solutions to (systems of) semigroup equations in semigroups that are wreath products of a finite group and a full transformation semigroup. The third part deals with the problem of deriving congruences modulo prime powers for an important and substantial class of combinatorial sequences, including in particular various kinds of subgroup counting functions. Our goal is to design a flexible, sufficiently general, and systematic method for finding and proving such congruences which, at the same time, should be well adapted for implementation on a computer.

This project is situated at the crossroads of group theory and combinatorics. It focussed on two main topics: I. Presentations for finite simple groups. II. Modular aspects of combinatorial sequences. Concerning the first topic, a new and powerful method for obtaining presentations from group actions on sets, recently developed by Basarab and the principal investigator, was fur- ther strengthened and refined, leading to a reduction of the number and complexity of defining relations needed. In this improved form, the method was then applied among others to GL2 (O), the two-dimensional general linear group over a valuation ring O, to SL3 (k), the three-dimensional special linear group over an arbitrary field k, to the five Mathieu groups M11 , M12 , M22 , M23 , M24 , and to the Janko group J1 . In each case, new and structurally re- vealing presentations were obtained; in particular, the method leads to the first computer-free approach to presentations for the large Mathieu groups M23 and M24 . The original proof of the presentation method was based on tools from geometric group theory newly developed for this purpose. In the context of this Lise Meitner project, a new approach of independent interest was developed, based on the solution of a generalised Schreier-type group extension problem. The second main topic concerned the problem of deriving congruences modulo prime powers for important and substantial classes of combinatorial sequences, a significant and frequently investigated problem situated between combinatorics and number theory. In two articles prior to this Lise Meitner project, the project investigator together with co-investigator Christian Krattenthaler had introduced a semi-automatic approach based on generating functions for obtaining congruences for certain classes of combinatorial sequences modulo powers of 2 and 3. This idea has been further developed and extended during the runtime of this Lise Meitner project. The prior approach to congruences modulo powers of 2 was generalised to arbitrary prime powers. Applications include congruences for the numbers of non-crossing graphs modulo powers of 3, the numbers of Kreweras walks modulo powers of 3, as well as congruences for FußCatalan numbers and blossom tree numbers modulo powers of arbitrary primes. A further variant of the generating function approach was designed for determining the behaviour of the ubiquitous Motzkin numbers modulo powers of 2. Perhaps the most spectacular success of applications of the generating function method concerns the number of torsion-free subgroups of a finitely generated free group: a complete classification was given according to whether these numbers form an ultimately periodic sequence or not. In the second case, our congruence method is shown to apply, leading to explicit congruences in the non-periodic case. In a slightly different direction, truncated versions of Dworks celebrated p-adic lemma for exponentials of power series were developed and applied to give explicit and rather sharp lower bounds on the p-part of representation numbers of (mostly) finite groups. 1