Nomember 15 (wednesday, unusual day)
14.00-14.45 Simon André (Paris VI) « Sharply 2-transitive infinite finitely generated simple groups ».
15.00-15.45 Ruiwen Dong (Saarland University) « Decision problems in sub-semigroups of metabelian groups ».
16.00-16.45 Emmanuel Rauzy (Munich University) « Groups with presentations in EDT0L ».
Simon André « Sharply 2-transitive infinite finitely generated simple groups ».
A group G is said to be sharply 2-transitive if it has an action on a set X with at least 2 elements such that, for all pairs (x, x’) and (y, y’) of distinct elements in X, there exists a unique element g in G such that g(x, x’) = (y, y’). For example, the affine group AGL(1, K) over a field K is sharply 2-transitive (for its natural action on K), and quite surprisingly, the following question remained open for a long time: does there exist a sharply 2-transitive group that is not isomorphic to some AGL(1, K)? A few years ago, Rips, Segev, and Tent constructed the first example of a sharply 2-transitive group that is not affine. In my talk, I will explain that we can go further and construct various sharply 2-transitive groups that are radically different from affine groups. These results were obtained in collaboration with Marco Amelio, Vincent Guirardel, and Katrin Tent.
Ruiwen Dong « Decision problems in sub-semigroups of metabelian groups ».
Algorithmic problems in metabelian groups have been studied as early as the 1950s since the work of Hall. In the 1970s Romanovskii proved decidability of the Group Membership problem (given the generators of a subgroup and a target element, decide whether the target element is in the subgroup) in metabelian groups. However, Semigroup Membership (same as Group Membership, but with sub-semigroups) has been shown to be undecidable in several instances of metabelian groups using embeddings of either the Hilbert’s tenth problem or two-counter automata.
In this talk we consider two « intermediate » decision problems: the Identity Problem (deciding if a sub-semigroup contains the neutral element) and the Group Problem (deciding if a sub-semigroup is a group). We reduce them to solving linear equations over the polynomial semiring N[X] and show decidability using an extension of a local-global principle by Einsiedler (2003).
Emmanuel Rauzy « Groups with presentations in EDT0L »
There are numerous connections between group theory and language theory, which for the most part stem from the fact that elements of a finitely generated group are commonly represented by words on the generators.
Out of these connections, one of the least studied ones is the notion of a group that admits a presentation in a given class of languages. Indeed, while the notions of finite presentations and of recursive presentations are commonly invoked, finite languages and recursive languages correspond to the two extremes of the Chomsky hierarchy -there is much in between!
We show that the groups that admit an L-presentation, a notion introduced by Bartholdi in 2000, correspond exactly to those that admit EDT0L presentations, a class of language which has been the focus of much attention in group theory following work of Ciobanu and Elder.
We present a uniform proof for the fact that one can compute finite, nilpotent, metabelian and free quotients of a group described by an EDT0L presentation, extending results of Bartholdi, Eick, Hartung. This proof relies on subgroup functors that satisfy some Noetherianity conditions.
Finally, we explain how these results allow us to produce examples of recursively presented groups that do not admit EDT0L presentations.
This is joint work with Laurent Bartholdi and Leon Pernak.