Generative Complexity in Algebra (eBook)

The G-spectrum or generative complexity of a class $/mathcal{C}$ of algebraic structures is the function $/mathrm{G}_/mathcal{C}(k)$ that counts the number of non-isomorphic models in $/mathcal{C}$ that are generated by at most $k$ elements. We consider the behavior of $/mathrm{G}_/mathcal{C}(k)$ when $/mathcal{C}$ is a locally finite equational class (variety) of algebras and $k$ is finite. We are interested in ways that algebraic properties of $/mathcal{C}$ lead to upper or lower bounds on generative complexity. Some of our results give sharp upper and lower bounds so as to place a particular variety or class of varieties at a precise level in an exponential hierarchy. We say $/mathcal{C}$ has many models if there exists $c>0$ such that $/mathrm{G}_/mathcal{C}(k) /ge 2^{2^{ck}}$ for all but finitely many $k$, $/mathcal{C}$ has few models if there is a polynomial $p(k)$ with $/mathrm{G}_/mathcal{C}(k) /le 2^{p(k)}$, and $/mathcal{C}$ has very few models if $/mathrm{G}_/mathcal{C}(k)$ is bounded above by a polynomial in $k$. Much of our work is motivated by a desire to know which locally finite varieties have few or very few models, and to discover conditions that force a variety to have many models. We present characterization theorems for a very broad class of varieties including most known and well-studied types of algebras, such as groups, rings, modules, lattices. Two main results of our work are: a full characterization of locally finite varieties omitting the tame congruence theory type 1 with very few models as the affine varieties over a ring of finite representation type, and a full characterization of finitely generated varieties omitting type 1 with few models. In particular, we show that a finitely generated variety of groups has few models if and only if it is nilpotent and has very few models if and only if it is Abelian.