New Titles  |  FAQ  |  Keep Informed  |  Review Cart  |  Contact Us Quick Search (Advanced Search ) Browse by Subject General Interest Logic & Foundations Number Theory Algebra & Algebraic Geometry Discrete Math & Combinatorics Analysis Differential Equations Geometry & Topology Probability & Statistics Applications Mathematical Physics Math Education

Generative Complexity in Algebra
Joel Berman, University of Illinois, Chicago, IL, and Paweł M. Idziak, Jagiellonian University, Krakow, Poland
 SEARCH THIS BOOK:
Memoirs of the American Mathematical Society
2005; 159 pp; softcover
Volume: 175
ISBN-10: 0-8218-3707-9
ISBN-13: 978-0-8218-3707-8
List Price: US$67 Individual Members: US$40.20
Institutional Members: US\$53.60
Order Code: MEMO/175/828

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.

• Introduction
• Background material
Part 1. Introducing Generative Complexity
• Definitions and examples
• Semilattices and lattices
• Varieties with a large number of models
• Upper bounds
• Categorical invariants
Part 2. Varieties with Few Models
• Types 4 or 5 need not apply
• Semisimple may apply
• Permutable may also apply
• Forcing modular behavior
• Restricting solvable behavior
• Varieties with very few models
• Restricting nilpotent behavior
• Decomposing finite algebras
• Restricting affine behavior
• A characterization theorem
Part 3. Conclusions
• Application to groups and rings
• Open problems
• Tables
• Bibliography