Kudryavtsev V.B., Rosenberg I.G. Structural Theory of Automata, Semigroups, and Universal Algebra

Подождите немного. Документ загружается.

Completeness of uniformly delayed op erations 143

d<p. This contradiction shows that λ

∈{ι

, k

} for all x ∈ k. We show that ρ

⊃ ι

.If

= ι

,thenλ

= ρ

∗ ι

= ρ

where ι

⊂ ρ

⊂ k

. This contradiction shows ρ

⊃ ι

for

all d ∈ p proving (1). Now for all x ≥ 0wehaveλ

= ρ

∗ ρ

x+d

⊇ ρ

⊃ ι

and so λ

= k

proving (3). 2

8.5 We need the following deﬁnitions and notations. Denote by E the set of all equivalence

relations on k distinct from ι

(note that k

∈ E) and put

:= {ρ ∈ M

| ρ

∈ E for all n ≥ 0}.

Let ξ be a symmetric and reﬂexive binary relation on k.Asusual,apath of length n from

i ∈ k to j ∈ k in ξ is a sequence v

,...,v

 in k such that i = v

, j = v

and v

i+1

∈ ξ for

all i =0,...,n−1. The relation ξ is connex if for all i, j ∈ k there is a path from i to j.The

relation ξ is disconnected if it is not connex. We need:

8.6 Lemma If there exists λ ∈ [ρ] ∩ M with all λ

⊃ ι

and some λ

disconnected then ρ is

dominated by some σ ∈ M

Proof Put σ

:= (λ

)

(= λ

◦···◦λ

, k times) for all n ≥ 0. It is easy to see that σ

∈ E

for all n ≥ 0andσ

= k

.Thusσ ∈ M

. 2

8.7 Lemma If ρ ∈ M

\ M

then every ρ

distinct from k

is central.

Proof For i =2,...,k and n>0 put

:= {x

···x

| x

u,...,x

u ∈ ρ

for some u ∈ k}. (8.1)

Suppose to the contrary that the polyrelation τ

is proper. Then clearly τ

∈ [ρ] ∩ M ,the

period of τ

is at most p and τ

⊇ ρ

for all n ≥ 0. Applying Lemma 8.3 we obtain τ

= ρ

i.e. ρ

= ρ

◦ ˘ρ

= τ

= ρ

for all n ≥ 0. It can be easily seen that ρ

is an equivalence

relation on k and so ρ ∈ M

contrary to our assumption. Thus τ

is improper. Since ρ

⊃ ι

by Lemma 8.4 (1), we have τ

= k

for all n ≥ 0.

By induction on i =2,...,k we prove that τ

= k

. Wehavejustproveditfori =2.

Suppose 2 ≤ i<kand τ

= k

for all n ≥ 0. It is easy to see from (8.1) that τ

i+1

is totally

symmetric. To show that it is also totally reﬂexive let x

,...,x

∈ k be arbitrary. Then

...x

∈ k

= τ

and hence x

u,...,x

u ∈ ρ

for some u ∈ k. Clearly x

u,...,x

u ∈ ρ

and hence from (8.1) we get x

...x

∈ τ

i+1

.Nowτ

i+1

is totally symmetric and reﬂex-

ive. Applying Theorem 4.2 we obtain τ

i+1

= k

i+1

. This concludes the induction step. In

particular, we have τ

= k

and so ρ

= k

or ρ

is central. 2

Denote by C the set of proper, binary and periodic polyrelations (ρ

,ρ

,...)onk such

that each ρ

= k

is central.

8.8 Theorem The set Σ

:= V

∪ A

∪P

∪ M

∪ C is B-generic.

8.9 Remark Itisshownin[Hi78]thatfork =3andρ ∈ M

∪C the uniformly delayed clone

Pold ρ is never precomplete. We know that for nontrivial equivalence relations θ

,...,θ

p−1

on k that are pairwise commuting (i.e., θ

◦ θ

= θ

◦ θ

for all 0 ≤ i<j<p) and satisfy

∩···∩θ

p−1

= ι

the polyrelation θ =(θ

,...,θ

p−1

,θ

,...) with period p, the uniformly

delayed clone Pold θ is precomplete.

144 T.HikitaandI.G.Rosenberg

9 Conclusion

It remains to show that for each ρ ∈ V

∪ A

∪P

the uniformly delayed clone D =Poldρ is

precomplete. This could be done directly (by showing that D ∪{(f,δ)} is complete for each

(f,δ) ∈U\D) or by showing that Pold σ = U or Pold σ is complete for each σ ∈ [ρ].

The main remaining problem is the elimination within M

∪ C; i.e., ﬁnding proper peri-

odic polyrelations ρ consisting of either (i) equivalence relations on k, or (ii) binary central

relations or k

such that Pold ρ is precomplete. So far we have several partial results but the

problem seems to be complex.

References

[Ba67] R. A. Ba˘ıramov, On the question of functional completeness in many-valued

logics, Diskret. Analiz 11 (1967), 3–20 (Russian).

[BW79] N. L. Biggs and A. T. White, Permutation Groups and Combinatorial Struc-

tures, London Math. Soc. Lecture Note Series 33, Cambridge Univ. Press, 1979.

[BK70] L. A. Biryukova and V. B. Kudryavtsev, On completeness of functions with

delays, Problemy Kibernet. 23 (1970), 5–25 (Russian); Systems Theory Research

23 (1973), 3–24.

[BKKR69] V. G. Bodnarchuk, L. A. Kaluzhnin, V. N. Kotov, and B. A. Romov, The Galois

theory for Post algebras I–II, Kibernetika (Kiev) 3 (1969), 1–10, 5 (1969), 1–9

(Russian); Systems Theory Research 3.

[Bu80] V. A. Buevich, On the t-completeness in the class of automata maps, Dokl.

Akad. Nauk. SSSR 252 (1980), 1037–1041 (Russian).

[Da81] J. Dassow, Completeness Problems in the Structural Theory of Automata,

Akademie-Verlag, Berlin, 1981.

[Ge68] D. Geiger, Closed systems of functions and predicates, Paciﬁc J. Math. 27 (1)

(1968), 95–100.

[Go68] D. Gorenstein, Finite Groups, second ed., Chelsea Pub., 1968, 1980.

[Hi78] T. Hikita, Completeness criterion for functions with delay deﬁned over a domain

of three elements, Proc. Japan Acad. 54 (1978), 335–339.

[Hi81a] T. Hikita, Completeness properties of k-valued functions with delays: Inclusions

among closed spectra, Math. Nachr. 103 (1981), 5–19.

[Hi81b] T. Hikita, On completeness for k-valued functions with delay, in: Finite Algebra

and Multiple-Valued Logic (B. Cs´ak´any and I. Rosenberg, eds.), Coll. Math. Soc.

J´anos Bolyai 28, North-Holland, 1981, 345–371.

[HN77] T. Hikita and A. Nozaki, A completeness criterion for spectra, SIAM J. Comput.

6 (1977), 285–297. Corrigenda, ibid., 8 (1979), 656.

Completeness of uniformly delayed op erations 145

[HR98] T. Hikita and I. G. Rosenberg, Completeness for uniformly delayed circuits, a

survey, Acta Applic. Math. 52 (1998), 49–61.

[Ia58] S. V. Iablonskiˇı, Functional constructions in the k-valued logic, Trudy Mat. Inst.

Steklov. 51 (1958), 5–142 (Russian).

[Ib68] K. Ibuki, A study on universal logical elements , NTT — Inst. of Electrocomm.

Report, 3747 (1968) (Japanese).

[In82] K. Inagaki, t

-completeness of sets of delayed logic elements, Trans. IECE Japan

J63-D (1982), 827–834 (Japanese).

[Kr59] R. E. Krichevskiˇı, The realization of functions by superpositions, Problemy

Kibernet. 2 (1959), 123–138 (Russian); Probleme der Kybernetik 2 (1963), 139–

159 (German).

[Ku60] V. B. Kudryavtsev, Completeness theorem for a class of automata without

feedback couplings, Dokl. Akad. Nauk SSSR 132 (1960), 272–274 (Russian);

Soviet Math. Dokl. 1 (1960), 537–539.

[Ku62] V. B. Kudryavtsev, Completeness theorem for a class of automata without

feedback couplings, Problemy Kibernet. 8 (1962), 91–115 (Russian); Probleme

der Kybernetik 8 (1965), 105–136 (German).

[Ku65] V. B. Kudryavtsev, The power of sets of precomplete sets for certain functional

systems connected with automata, Problemy Kibernet. 13 (1965), 45–74 (Rus-

sian).

[Ku73] V. B. Kudryavtsev, On functional properties of logical nets, Math. Nachr. 55

(1973), 187–211 (Russian).

[Ku82] V. B. Kudryavtsev, Functional Systems, Monograph, I.M.U., Moscow, 1982

(Russian).

[Lo65] H. H. Loomis, Jr., Completeness of sets of delayed-logic devices, IEEE Trans.

Electron. Comput. EC-14 (1965), 157–172.

[MRR78] L. Martin, C. Reischer, and I. G. Rosenberg, Completeness problems for

switching circuits constructed from delayed gates, Proc. 8th Internat. Symp.

Multiple-Valued Logic, 1978, 142–148; Elektron. Informationsverarb. Kybernet.,

19 (1983), 415, 171–186 (in French); An expanded French version appeared in:

R´eseaux modulaires, Monographies de l.U.Q.T.R. 11 1980.

[Ma59] N. M. Martin, On the completeness of sets of gating functions with delay,

in: Sympos. on Gating Algebra, Proc. Internat. Congr. Information Process-

ing, Paris, 1959.

[Mi84] M. Mili˘ci´c, Galois connections for closed classes of functions with delays Publ.

de l’Inst. Math´ematique Nouvelle S´erie 36 (50) (1984), Part I: 119–124; Part II:

125–136 (Russian).

146 T.HikitaandI.G.Rosenberg

[Mi88] M. Mili˘ci´c, On Galois connections for one place functions with delays, Publ. de

l’Inst. Math´ematique Nouvelle S´erie 44 (58) (1988), 147–150 (Russian).

[MSHMF88] M. Miyakawa, I. Stojmenovi´c, T. Hikita, H. Machida, and R. Freivalds, Sheﬀer

and symmetric Sheﬀer Boolean functions under various functional constructions,

J. Inform. Process. Cybernet. EIK,(formerly: Elektron. Informationsverarb.

Kybernet.) 24 (6) (1988), 251–266.

[No70a] A. Nozaki, Functional studies of automata I–II, Sci. Papers College Gen. Ed.

Univ. Tokyo 20 (1970), 21–36, 109–121.

[No70b] A. Nozaki, R´ealisation des fonctions deﬁnies dans un ensemble ﬁni `a l’aide des

organes ´el´ementaires d’entr´ee-sortie, Proc. Japan Acad. 46 (1970), 478–482.

[No72] A. Nozaki, Complete sets of switching elements and related topics, First USA-

Japan Computer Conference, 1972, 393–396.

[No78] A. Nozaki, Functional completeness of multi-valued logical functions under uni-

form compositions, Rep. Fac. Eng. Yamanashi Univ. 29 (1978), 61–67.

[No81] A. Nozaki, Completeness criteria for a set of delayed functions with or with-

out non-uniform compositions, in: Finite Algebra and Multiple-Valued Logic

(B. Cs´ak´any and I. Rosenberg, eds.), Coll. Math. Soc. J´anos Bolyai 28,North-

Holland, 1981, 489–519.

[No82] A. Nozaki, Completeness of logical gates based on sequential circuits, Trans.

IECE Japan J65-D (1982), 171–178 (Japanese).

[PK79] R. P¨oschel and L. A. Kaluzhnin, Funktionen- und Relationenalgebren,VEB

Deutscher Verlag der Wissenschaften, Berlin, 1979.

[Po21] E. L. Post, Introduction to a general theory of elementary propositions, Amer.

J. Math. 43 (1921), 163–185.

[Ro65] I. G. Rosenberg, La structure des fonctions de plusieurs variables sur un ensem-

ble ﬁni, C.R. Acad. Sci. Paris S´er. A–B, 260 (1965), 3817–3819.

[Ro70] I. G. Rosenberg,

Uber die funktionale Vollst¨andigkeit in dem mehrwertigen

Logiken (Struktur der Funktionen von mehreren Ver¨anderlichen auf endlichen

Mengen), Rozpravy

Ceskoslovensk´e Akad. Vˇed., Ser. Math. Nat. Sci., 80 (1970),

3–93.

[Ro73] I. G. Rosenberg, The number of maximal closed classes in the set of functions

over a ﬁnite domain, J. Comb. Theory 14 (1973), 1–7.

[Ro77] I. G. Rosenberg, Completeness properties of multiple-valued logic algebras,

in: Computer Science and Multiple-Valued Logic, Theory and Applications

(D.

C. Rine, ed.), North-Holland, 1977, 144–186; 2nd edition: ibid, 1984, 150–

194.

Completeness of uniformly delayed op erations 147

[Ro83] I. G. Rosenberg, The multi-faceted completeness problem of the structural the-

ory of automata, preprint, CRMA-1197, Universit´edeMontr´eal, 1983.

[RH83] I. G. Rosenberg and T. Hikita, Completeness for uniformly delayed circuits,

Proceedings 13th Internat. Sympos. on Multiple-Valued Logic, IEEE, Kyoto,

1983, 2–10; Proofs: Preprint, Tokyo Metropolitan Univ., 1983.

[RS84] I. G. Rosenberg and L. Szab´o, Local completeness I, Algebra Universalis 18

(1984), 308–326.

[Sl39] J. Slupecki, A completeness criterion in many-valued propositional calculi, C.R.

S´eance Soc. Sci. Varsovie 32 (1939), 102–109 (Polish); Studia Logica (1972),

153–157.

[Sz86]

A. Szendrei, Clones in universal algebras, Les Presses de l’Universit´ede

Montr´eal, SMS, 1986.

Classiﬁcation in ﬁnite model theory:

counting ﬁnite algebras

PawelM.IDZIAK

Computer Science Department

Jagiellonian University

Nawojki 11, PL-30-072 Krak´ow

Poland

Abstract

The G-spectrum or generative complexity of a class C of algebraic structures is the

function G

(k) that counts the number of non-isomorphic models in C that are generated

by at most k elements. We consider the behavior of G

(k) when C is a locally ﬁnite

equational class (variety) of algebras and k is ﬁnite. We are interested in ways that

algebraic properties of 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. Much of our work is

motivated by a desire to know which locally ﬁnite varieties have polynomially many or

singly exponentially many 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. In particular, we show that a ﬁnitely generated variety of groups has singly

exponentially many models if and only if it is nilpotent and has polynomially many

models if and only if it is Abelian.

1 Introduction

Given a class C of structures two basic questions about the class C are:

• What are the cardinalities of structures in C?

• How many non-isomorphic structures of a given cardinality are in C?

The ﬁrst question is the problem of determining the spectrum Spec(C)oftheclassC,that

is, the class of cardinalities that occur as sizes of structures in C. This problem appears in all

sorts of contexts in mathematics. For example, if C is the class of models of a ﬁrst order theory

in a countable language then, by the L¨owenheim-Skolem theorems, every inﬁnite cardinality

is in Spec(C). Thus, Spec(C) is usually deﬁned to be the set of sizes of ﬁnite models in C.

Let us mention here a result of R. Fagin [12] that characterizes those sets of integers that

can be expressed as Spec(C), where C is the class of all models of a ﬁrst order sentence in

a ﬁrst order language. They are exactly the sets that can be recognized in nondeterministic

exponential time. He also proved a similar connection between nondeterministic polynomial

time and what are called generalized spectra.

149

V. B. Kudryavtsev and I. G. Rosenberg (eds.),

Structural Theory of Automata, Semigroups, and Universal Algebra, 149–158.

150 P. M. Idziak

Thesecondbasicquestionisabouttheﬁne spectrum of the class C, i.e., about the function

that assigns to each cardinal k the number I(C,k) of non-isomorphic k-element structures in

C. The problem of determining the ﬁne spectrum of a class, either exactly or asymptotically,

is a natural one, and is a problem that has been considered for various classes C and in various

contexts over the years. Combinatorial enumeration problems, such as ﬁnding the number

of k-vertex graphs in some speciﬁc class of graphs, are familiar examples of such ﬁne spectra

problems.

In Model Theory one of the fundamental topics is Shelah’s classiﬁcation theory. Given

a ﬁrst order theory T we are interested in the number of non-isomorphic models of T of

a given (inﬁnite) cardinality k. Moreover we want to classify theories with the number of

non-isomorphic models of inﬁnite cardinality k given by a prescribed function f (k). Some of

the results here say that not every function f can be realized. For example an early result of

M. Morley says that if T is a complete theory in a countable language and T is κ-categorical

for some uncountable cardinal κ then T is categorical in all uncountable powers.

When we are interested in ﬁnite models only, i.e., restricting k to be ﬁnite, and in integer

valued functions f, then the situation changes dramatically. For any function f : ω −→ ω

there is a ﬁrst order theory T having exactly f (k)modelswithk elements. Simply let T be

axiomatized by sentences expressing:

If a model has k elements then it is isomorphic with one of the f (k) choices given

by their diagrams.

Even restricting the language to be ﬁnite leaves a lot of room for possible ﬁne spectra. A

function f : ω −→ ω counts non-isomorphic models of a ﬁrst order theory in a ﬁnite language

if and only if log f (k) is bounded from above by a polynomial in k.

The

refore the ﬁnite part of the ﬁne spectrum problem is much more interesting in the

case of restricted theories, eg. in equational theories of algebras. Actually the terminology

“ﬁne spectrum” was introduced by W. Taylor in [31] in the case where C is a variety, that

is, a class of algebraic structures or algebras closed under the formation of homomorphisms,

subalgebras and direct products. Among the results of Taylor’s paper is a characterization

of those varieties that have exactly one model of size 2

for each ﬁnite k and no other ﬁnite

models. All such varieties must be generated by a 2-element algebra. Subsequent papers by

R. Quackenbush [27] and D. Clark and P. Krauss [9] extended Taylor’s work to n-element

algebras that generate varieties having minimal ﬁne spectra.

Despite this work on minimal ﬁne spectra there has been relatively little success on general

problems involving ﬁne spectra of varieties. In [32] Taylor writes of ﬁne spectra functions that

“characterizations of such functions seems hopeless” and Quackenbush states in his survey

on enumeration problems for ordered structures [28] that the ﬁne spectrum problem here “is

usually hopeless”.

There are many reasons for the diﬃculties in determining the ﬁne spectra of varieties. 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 variety V and some of the conditions that

these generators satisfy, our freedom in building the rest of the model is heavily restricted.

This eﬀect is widely used in group theory where a group is usually presented by a (ﬁnite)

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

Counting ﬁnite algebras 151

A. This makes the counting of all n-element or at most n-element algebras diﬃcult, if at all

possible, even if we content ourselves with an asymptotic estimate.

Another area of research in which ﬁne spectra appear is in ﬁnite model theory. When

investigating asymptotic probabilities in ﬁnite model theory, some of the results rely on

counting all ﬁnite models, up to isomorphism, for a given theory T . This usually is not hard

when T has no axioms. However there are only a few results on zero-one (or more generally

on limit) laws for speciﬁc theories T . One reason is that for such counting deep insight into

the structure of ﬁnite models of T is required. The counting is even more diﬃcult if the

language of T contains function symbols. Except for unary functions [23] (in which case the

models behave much more like relational structures than algebras) and Abelian groups [10]

(where we completely understand the structure) there are only a few other results on limit

laws for algebras to report. The reader may wish to consult [4, 5, 6, 7, 8, 22] for related work.

Again, there are various reasons for the diﬃculties here with ﬁne spectra for classes

arising from theories in a language containing function symbols. Some important techniques

for asymptotic probabilities rely on extension axioms. These techniques work perfectly well

for purely relational structures when often the resulting random structure is model complete.

However (randomly) adding a new element a to the universe of an algebra A in a variety V

and keeping the resulting extended algebra in V requires a much bigger extension A

∗

of A.

The number and the behavior of all those new elements in A

∗

is fully determined by the old

algebra A and the interaction of the new element a with the elements of A. Thus, in vector

spaces, by adding a new element we actually increase the dimension.

One possible way to overcome these diﬃculties 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.

Thus, we introduce the G-spectrum,orgenerative complexity,ofaclassC,whichisthe

function G

(k) that counts the number of non-isomorphic (at most) k-generated models in C.

We concentrate on the case where C is a variety of algebras and restrict ourselves to ﬁnite

k. Even in this new setting the counting remains hard. It requires an understanding of the

‘generating power’ in a given variety V. This is related to the old problem of determining

the free spectrum of V, that is, the sizes of free algebras F

(k)inV with k =1, 2,...

free generators. This is because every k-generated algebra in V is isomorphic to a quotient

of F

(k) by a congruence relation. However, two diﬀerent congruences may give rise to

isomorphic quotients. Thus, the second problem we meet here is to measure the amount of

homogeneity in F

(k). One cannot hope to solve these two problems without understanding

the structure of algebras from V.

As we have already mentioned the inﬁnite 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 classiﬁcation theory and for stability theory. Note that in the inﬁnite realm (and

for a countable language), being κ-generated and having κ elements are the same.

For example, the celebrated Vaught conjecture says that the number I(C,ω)ofnon-

isomorphic countable models of any ﬁrst order theory in a countable language is either count-

able or 2

. In [18] and [17] B. Hart, S. Starchenko, and M. Valeriote have been able to prove

this conjecture for varieties of algebras. They actually determined the possible inﬁnite ﬁne

spectra (which, in this case, are the same as inﬁnite G-spectra) of varieties and correlated

them with algebraic properties of varieties. A characterization of locally ﬁnite varieties with

152 P. M. Idziak

strictly less than 2

non-isomorphic countable models can be easily inferred from deep work

on decidability done by R. McKenzie and M. Valeriote [25].

The general project of determining the ﬁne spectra of theories has a long history, going

back at least to the Lo´s conjecture, which stated that the uncountable ﬁne spectrum of

any countable theory that is categorical in some uncountable cardinal must be identically

equal to 1. The conjecture was conﬁrmed by M. Morley [26] in 1965; but already in 1957,

A. Ehrenfeucht [11] had provided some of the methods which were later developed by S. Shelah

to show that unstable theories have many models. In Shelah’s classiﬁcation theory [29], the

countable theories with a prescribed ﬁne spectrum for uncountable cardinals are described

and classiﬁed. Some of the results here, like the mentioned Lo´s conjecture, say that not

every function f can be realized as the uncountable ﬁne spectrum of a countable theory.

In fact, it is proved in [29] that restricted to suﬃciently large κ, there are precisely eight

possible functions I(C,κ). B. Hart, E. Hrushovski, and M. Laskowski [16] completed Shelah’s

classiﬁcation theory by resolving a conjecture of Shelah and computing the spectrum function

for small (uncountable) values of κ.

However, one cannot easily (if at all) transfer inﬁnite methods and results into the ﬁnite

world. Thus, we focus on the G-spectrum of a variety rather than its ﬁne spectrum. We

further restrict ourselves to locally ﬁnite varieties, i.e., varieties in which all ﬁnitely generated

algebras are ﬁnite. This gives that the G-spectrum of the variety V is integer-valued. Even

with this ﬁniteness restriction G-spectra can be arbitrarily large: for any sequence (p

)

k∈ω

of integers there is a locally ﬁnite variety V of groupoids such that G

(k) ≥ p

for all k [2,

Example 5.9]. On the other hand, if V is a ﬁnitely generated variety of ﬁnite type then easily

established upper bounds for the G-spectrum, free spectrum and ﬁne spectrum of V are 2

,and2

, respectively, for some constants c and s.

2 Results

The main problems that stimulate our research in this area are:

• How does the growth of the G-spectrum of a locally ﬁnite variety V aﬀect the structure

of algebras in V?

• In what way do algebraic properties of V inﬂuence the behavior of G

(k)?

• For a given variety V, can an explicit formula for G

(k) be found?

• Can the asymptotic behavior of G

(k) be determined?

For some V,thevalueofG

(k) is easily determined, as the following examples show.

2.1 Example For the variety V of sets, that is algebras with no fundamental operations,

(k)=k. In [2, Section 3] a full description of G-spectra for varieties generated by arbitrary

multi-unary algebras is given.

2.2 Example Let V be the variety of vector spaces over a ﬁxed ﬁeld. A k-generated algebra

here is a vector space of dimension at most k.SoG

(k)=k +1. If A

is the variety

generated by the p-element group for a prime p,thenak-generated group in A

has size p

Counting ﬁnite algebras 153

for 0 ≤ m ≤ k.SoG

(k)=k + 1. In [2, Example 6.7] the function G

(k)forV an arbitrary,

ﬁnitely generated variety of Abelian groups is determined.

2.3 Example For the variety B of Boolean algebras we have |F

(k)| =2

.Everyk-

generated member of B is a Boolean algebra with m atoms, 0 ≤ m ≤ 2

.ThusG

(k)=1+2

2.4 Example In contrast to these varieties that have small G-spectra, [2, Section 4] shows

that semilattices and distributive lattices have G

(k) that are doubly exponential functions

of k. Actually it is shown that G

(k)=2

(

k/2

)

(1+o(1))

for the variety S of semilattices and

(k)=2

(1+o(1))

for the variety D of distributive lattices.

Moreover [2, Section 5] contains examples of locally ﬁnite varieties with arbitrarily large

G-spectra.

To report the results on G-spectra we introduce some classes of functions that are helpful

in describing the possible behavior of the G

(k).

2.5 Deﬁnition Let f be a real-valued function of the positive integers.

• We say f is at most 0-fold exponential if there exists a polynomial p such that f (k) ≤

p(k) for all k.

• For m>0 the function f is at most m-fold exponential if there is an at most (m−1)-fold

exponential function g such that f(k) ≤ 2

g(k)

for all k.

• The function f is called at least 0-fold exponential if there exists a constant c>0such

that f (k) ≥ ck for all but ﬁnitely many k.

• For m>0 the function f is at least m-fold exponential if there is an at least (m−1)-fold

exponential function g such that f(k) ≥ 2

g(k)

for all but ﬁnitely many k.

• The function f is of m-fold exponential complexity if f is both at most and at least

m-fold exponential.

• AclassC of structures has m-fold exponential generative complexity if the function

(k)isofm-fold exponential complexity.

We usually write polynomial, exponential, doubly exponential, and triply exponential in

place of 0-fold exponential, 1-fold exponential, 2-fold exponential, and 3-fold exponential.

2.6 Deﬁnition Let V be a locally ﬁnite variety.

•Vhas many models if G

(k) is at least doubly exponential.

•Vhas few models if G

(k)isatmostexponential.

•Vhas very few models if G

(k) is at most polynomial.