One way to study structures of uncountable cardinality κ is to generalize the notion of computation. Saying that a subset of κ is κ-c.e. if it is Σ⁰₁ definable (with parameters, in the language of set theory) over L_κ provides the notion of κ-computability. We may also quantify over subsets of L_κ, providing a notion of a κ-analytic set (here we assume V=L). In this setting, we consider the difficulty of recognizing free groups and the complexity of their bases. For example, if κ is a successor cardinal, the set of free abelian groups of size κ is Σ¹₁-complete. If κ is the successor of a regular cardinal which is not weakly compact, there is a computable free abelian group of cardinality κ, all of whose bases compute ∅”, and this is the best coding result possible. The resolution of questions of this type is more complex for other κ, and a few questions remain open. This is joint work with Greenberg and Turetsky.

How much information about a group G is contained in the group ring K(G) for an arbitrary field K? Can one recover the algebraic or geometric structure of G from the ring? Are the algorithmic properties of K(G) similar to that of G? I will discuss all these questions in conjunction with the classical Kaplansky-type problems for some interesting classes of groups, in particular, for limit, hyperbolic, and solvable groups. At the end I will touch on the solution to the generalized 10th Hilbert problem in group rings and how equations in groups are related to equations in the group rings. The talk is based on joint results with O. Kharlampovich.

We say that a class of finite structures for a finite first-order signature is R-compressible for an unbounded function R on the natural numbers if each structure G in the class has a first-order description of size at most O(R(|G|)). We show that the class of finite simple groups is log-compressible, and the class of all finite groups is log-cubed compressible.

The results rely on the classification of finite simple groups, the bi-interpretability of the twisted Ree groups with finite difference fields, the existence of profinite presentations with few relators for finite groups, and group cohomology. We also indicate why the results are close to optimal.

This is joint work with Katrin Tent, to appear in IJM, available here.

Let G be a countably infinite group and let Sub_G be the compact space of subgroups H≤G. Then a probability measure ν on Sub_G which is invariant under the conjugation action of G on Sub_G is called an invariant random subgroup. In this talk, I will discuss the invariant random subgroups of inductive limits of finite alternating groups. (This is joint work with Robin Tucker-Drob.)

The three topics in the title have been inextricably linked since the famous 1912 paper of Max Dehn. In recent years the asymptotic-generic point of view of geometric group theory has given rise to new areas of computability and computational complexity. I will discuss how this arose and then focus on one recent development in computability theory, namely, coarse computability and the coarse computability bound.

For any computable abelian group, the collection of possible linear orderings on the group can be represented as a Π⁰₁ class. However, not all Π⁰₁ classes can occur in this way, and we investigate the possible Turing degrees of their members. First, we describe the connection between orders for a group and bases for the group. Additionally, we extend a previously known result regarding the Turing degrees not represented in the space of orders of some group.

We consider maximal independent sets within various sorts of groups and fields freely generated by countably many generators. The simplest example is the free divisible abelian group, which is just an infinite-dimensional rational vector space. As one moves up to free abelian groups, free groups, and “free fields” (i.e. purely transcendental field extensions), maximal independent sets and independent generating sets both become more complicated, from the point of view of computable model theory, but sometimes in unpredictable ways, and certain questions remain open. We present the topic partly for its own sake, but also with the intention of introducing the techniques of computable model theory and illustrating some of its possible uses for an audience to which it may be unfamiliar.

This is joint work with Charles McCoy.