Generative complexity in algebra
by
Pawel M. Idziak
(Jagiellonian University, Krakow, Poland)
Coauthors: Joel Berman (University of Illinois, Chicago, IL, USA), Ralph McKenzie (Vanderbilt University, Nashville, TN, USA), Matthew Valeriote (McMaster University, Hamilton, ON, Canada)

The generative complexity of a class of models is the function that counts, up to isomorphism, the number of at most k-generated models in the class.

The infinite counterpart of the problem of counting non-isomorphic models is widely studied in Model Theory, and is one of the fundamental topics for Shelah's classification theory and for stability theory. Note that in the infinite realm (and for a countable language) being k-generated and having k elements are the same.

However in the finite setting it is enormously hard to count models, especially algebras, with a given number of elements. There are many reasons for those difficulties. One reason that interests us is that algebras are often described by means of a set of generators. Once we know the generators of an algebra A in a given class V and some of the conditions that these generators satisfy, our freedom in building the rest of the model is heavily restricted. This effect is widely used in group theory where a group is usually presented by a (finite) set of generators and a set of relations the generators must obey. The constraints put on the behavior of the generators place restrictions on the structure of the entire algebra A. However, there is in general no obvious or transparent way to determine the cardinality of A. This makes the counting of all n-element or at most n-element algebras difficult, if at all possible, even if we content ourselves with an asymptotic estimate.

One possible way to overcome these difficulties is to count k-generated models instead of k-element ones. This is a more tractable problem when the classes are varieties of algebras, and we believe is the proper setting for asymptotic probabilities in algebra. Note however that these numbers are the same for purely relational languages.

Two main results of our work are:

• a full characterization of locally finite varieties with polynomial generative complexity as varietal products of an affine variety over a ring of finite representation type and several varieties that are matrix powers of pointed G-sets,
• a full characterization of finitely generated congruence modular varieties (or, in fact, omitting TCT type 1) with singly exponential generative complexity.

The characterization of locally finite varieties with polynomial generative complexity was obtained by P. Idziak, R. McKenzie and M. Valeriote. The conditions in this situation are very simple and easily stated. The conditions involved in the second characterization, obtained by J. Berman and P. Idziak, are more complicated, although they also have a natural algebraic meaning. In both cases we know that the bound for the number of algebras implies a very transparent and manageable structure. For example, when specializing our results to groups we get the following:

• every finitely generated variety of groups has at most doubly exponential generative complexity,
• a finitely generated variety of groups has singly exponential generative complexity if and only if it is nilpotent,
• a finitely generated variety of groups has polynomial generative complexity if and only if it is Abelian,

• every finitely generated variety of rings has at most doubly exponential generative complexity,
• a finitely generated variety of commutative rings with unit has singly exponential generative complexity if and only if the Jacobson radical in the generating ring squares to 0,
• no nontrivial variety of rings with unit has polynomial generative complexity.

Date received: December 31, 2001

Copyright © 2001 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # caig-33.