# When finitely generated free algebras are finite

The variety (in the sense of universal algebra) of Boolean algebras, for example, has the property that finitely generated free algebras have finite cardinality; in that case specifically $|F_n|=2^{2^n}$, in the obvious notation.

Can one usefully characterize varieties whose finitely generated free algebras have finite cardinality?

Can one characterize natural number sequences arising as $|F_n|$ in association with such varieties?

-
I don't understand the title. –  Mariano Suárez-Alvarez Jan 31 '12 at 4:13
The key words to use are "locally finite" and "free spectra". When you have more specific questions to ask after searching, we will be here awaiting those questions. Gerhard "Ask Me About System Design" Paseman, 2012.01.30 –  Gerhard Paseman Jan 31 '12 at 5:14
For example, a good question would start with "What other (locally finite) varieties have free spectra whose growth rate is like that of the free spectra of (the variety of) Boolean algebras?", and include appropriate motivation and background. Gerhard "Ask Me About System Design" Paseman, 2012.01.30 –  Gerhard Paseman Jan 31 '12 at 5:21
I agree with Mariano and Gerhard, but this is an interesting topic (imho) and I hope you will reformulate your question and ask a new one with a better title. Something your question leads me to wonder about (though I'm not sure this would make a "good" question): for which varieties are there alternative characterizations of "locally finite?" See, for example, jstor.org/pss/2040508 –  William DeMeo Jan 31 '12 at 7:41
I replaced "free" by "finite" in the title, because I'm sure it was meant this way. I hope that this clears up some confusion. –  Martin Brandenburg Jan 31 '12 at 10:11

The Burnside problem for groups asks whether the variety $x^n=1$ is locally finite. By work of Adian and Novikov they are not locally finite for $n$ odd and large enough (I think at least 667) and in the even case results are by Ivanov and Lysenok. For n=2,3,4,6 local finiteness is known. For n=5 it is unknown. Mark Sapir classified locally finite semigroup varieties modulo the group case.

Varieties generated by a finite algebra are locally finite by a result of Birkhoff.

Added. By Zelmanov's solution to the restricted Burnside problem a variety of groups is locally finite iff it is generated by a set of finite groups with uniformly bounded exponent. The analogue is false for semigroups.

-

I asked George McNulty, and here is his answer. It partially coincides with my answer here, but is much more complete.

========

I think the first result of this kind is an immediate if unstated consequence of a result in Peter Perkins dissertation

P. Perkins, Decision Problems of Equational Theories of Semigroups and General Algebras'', University of California, Berkeley 1966.

In a signature with two binary operation symbols and two constant symbols, Perkins proves (his Theorem 36) that the collection of finite sets of equations that are bases of finite algebras is undecidable. He does this by reducing the word problem on a particular finitely presented semigroup to this question. Loosely, if the word w is a consequence of the semigroup presentation, then the associated finite set of equations will be a base of a finite algebra, whereas if w is not a consequence then the free algebra on one generator in the variety based on the set of equations will be infinite. Of course, this also shows that the locally finiteness problem is also undecidable. This part of Perkins dissertation was published as

P. Perkins, Unsolvable problems for equational theories'', Notre Dame Journal of Formal Logic, vol. 8 (1967) 175--185.

One of the things I did in my 1972 dissertation was to establish various extensions of Perkins work on this topic. In particular, I showed that the above result holds for any finite signature that has an operation symbol of rank at least two. I had a rather long list of properties of finite sets of equations or of the varieties based on finite sets of equations that I could prove to be undecidable, but I didn't put all the proofs even in my dissertation. By the time I came to write it up for publication, I had figured out a handful of results from which most of the undecidability results I knew would follow. I published these in

G. McNulty, Undecidable properties of finite sets of equations''. Journal of Symbolic Logic, vol. 41 (1976) 589-604.

You can find in that paper a long list of such properties, but local finiteness is not on the list, while being the base of a finite algebra is. The local finiteness business follows in the same way as it did from Perkins result.

There are only a handful of other papers that address undecidable properties of finite sets of equations (mostly, I think, because undecidability seems to prevail---although some result like the Adjan-Rabin Theorem is unknown). Here they are:

V.L. Murskii, Nondiscernible properties of finite system of identity relations'', Doklady Akademii Nauk SSSR vol. 196 (1971) 520--522.

This paper is independent of my work or Perkins work. There is a large overlap between Murskii's findings and what is in my dissertation, although this 3 page account of Murskii's work is, of course, very terse. I don't think Muskii's work covers either being the base of a finite algebra or being the base of a locally finite variety, but it is very interesting. Murskii was the first to frame a general condition on collections of finite sets of equations that would ensure undecidability. It was Murskii's paper that spurred me to frame other general conditions that you can find in the paper of mine above. (I also include there a second proof of Murskii's general condition.

Douglas Smith in his 1972 Penn State dissertation found another undecidability result. It is in

D. Smith, the non-recursiveness of the set of finite sets of equations whose theories are one-based.'' Notre Dame Journal of Formal Logic, vol. 13 (1972) 135--138.

Ralph McKenzie wrote

R. McKenzie, On spectra and the negative solution of the decision problem for identities having a nontrivial finite model.'' Journal of Symbolic Logic, vol. 40 (1975) 186--196.

Don Pigozzi wrote

D. Pigozzi, Base-undecidable properties of universal varieties.'' Algebra Universalis, vol. 6 (1976), no. 2, 193–223.

Among other things, Pigozzi shows that it is undecidable whether the variety based on a finite set of equations has the amalgamation property or the Schreier property (subalgebras of free algebras are free).

C. Kalfa, Decision problems concerning properties of finite sets of equations. Journal of Symbolic Logic, vol. 51 (1986) 79--87.

Here Cornelia Kalfa shows that the joint embedding property is undecidable, as is whether the elementary theory of the infinite models is model complete.

The latest paper I know about is

C. O'Dunlaing, Undecidable questions related to Church-Rosser Thue systems.'' Theoretical Computer Science, vol. 23 (1983) 339--345.

Here it is shown that it is undecidable whether of finite set of equations is logically equivalent of a finite confluent set of equations.

Recently Ralph Freese and some collaborators have found fairly quick algorithms for a lot of the kind of properties above when the equations examined have certain restricted forms.

=================

George also wrote:

=================

Also I noticed the interest expressed about free spectra in the original posting. There are a lot of papers on this (and related topics). Perhaps Joel Berman is the person who knows all about it.

-
Thank you. Somehwat off topic, I think it was Berman who wrote an article which was a catalog on the (isomorphism types of) three element binary groupoids , which Burris and Berman later analyzed and grouped by a variety of properties, e.g. Abelian. Is there an online version of the catalog that is not behind a paywall? I was hoping to refer another poster to such a copy regarding a commutative idempotent groupoid they posted. Gerhard "Wants It For Himself, Too" Paseman, 2012.02.16 –  Gerhard Paseman Feb 16 '12 at 21:18

In general a variety can be given in two different ways. First - by a finite (or recursive) set of identities and second - by a generating algebra. In the first case, the local finiteness of a variety is undecidable in general. But in some cases (for example, for semigroups with "nice" subgroups) the algorithm exists. In the second case, the generating algebra should be "uniformly locally finite" (say, finite, as in the case of Boolean algebras). See the survey "Algorithmic problems in varieties" here http://www.math.vanderbilt.edu/~msapir/ftp/pub/survey/survey.pdf .

Edit. The undecidability result not exactly in my survey but can be deduced from it. Here is a correct reference: Perkins, Peter Unsolvable problems for equational theories. Notre Dame J. Formal Logic 8 1967 175–185. Perkins proves that there is no algorithm that, given a finite system of identities, says whether it is a basis of identities of a finite algebra (theorem 13). In fact he proves more. He constructs an algebra $E$ with undecidable word problem, and for every two terms $u,v$ of $E$ he constructs a finite set of identities $I(u,v)$ such that if $u=v$ in $E$ then the set $I(u,v)$ is the set of identities of a finite algebra, and if $u\ne v$, $I(u,v)$ holds on an infinite 1-generated algebra. Since we cannot decide whether $u=v$, we cannot decide, given a finite set of identities, it is a basis of a locally finite variety.

If you are interested in just one free object, the situation is even easier. It is known (Markov) that the finiteness of a 2-generated semigroup is undecidable. Now consider the signature consisting of the semigroup operation plus two 0-ary operations giving the generators. Then any finitely presented semigroup becomes a relatively free object in a variety given by a finite number of identities (involving the 0-ary operations). Thus it is undecidable, given a finite number of identities in that signature whether the 2-generated free algebra in the variety given by these identities is finite (that is almost exact quote from the survey).

-
I am interested in the first case, and will peruse your survey to find more about undecidability of local finiteness given a recursive equational theory. Would you please mention an author or a reference where this result appeared? (Also, to make sure I do not get confused, the first case is NOT, or not closely related to, Tarski's problem which McKenzie solved by 1994. Right?) Gerhard "Still Unsure About Undecidability Methods" Paseman, 2012.02.09 –  Gerhard Paseman Feb 9 '12 at 15:46
Thank you. I will follow up. Slightly off topic, I am looking at some decidability issues related to hyperidentities. I have not seen anything in my searches. If you even half remember something about this, I would be grateful for a name besides Denecke or Wismath who worked on it as well. Thanks again. Gerhard "Appreciates The Kindness Of Others" Paseman, 2012.02.09 –  Gerhard Paseman Feb 9 '12 at 18:19
@Gerhard: I modified the answer, including a precise reference. I know very little about hyperidentities. Only the papers by Movsisyan. For example: Movsisyan, Yu. Hyperidentities and hypervarieties. Sci. Math. Jpn. 54 (2001), no. 3, 595–640. –  Mark Sapir Feb 9 '12 at 20:22