ISRAEL JOURNAL OF MATHEMATICS xx (1996), 1–34

ON THE GROWTH OF ALGEBRAS WITH BIALGEBRA ACTION^{1}

BY

George M. Bergman^{∗}

Department of Mathematics, University of California Berkeley, CA 94720-3840, USA e-mail: gbergman@math.berkeley.edu

Dedicated to the memory of Shimshon Amitsur

ABSTRACT

If k is a field, A a k-algebra, and B a k-bialgebra which acts on A, we study the rate of growth of A under its algebra structure together with the action of B. We then briefly place our results in the more general context of a vector space A on which an operad acts, and sketch an application to a (still open) question on finitely generated subalgebras of free associative algebras.

Introduction Let A be a finitely generated associative unital algebra over a field k, and U a finite-dimensional k-subspace which generates A and contains 1. The classical theory of growth-rates of algebras [11] looks at the dimensions of the sets

U^{n} = span {x_{1} ⋯ x_{n}|x_{1}, …, x_{n} ∈ U}

as n grows, and studies measures of the resulting function of n which are invariant under change of the generating subspace.

11991 Mathematics Subject Classifications: Primary: 11N45, 16P90, 16W30; secondary: 08B20, 08C15, 11P99, 13N99, 17A01.

* Work done while the author held NSF contract DMS 93-03379. Received June 11, 1995

Now suppose A is a k-algebra given with an action of a bialgebra B – for instance, an action of a group G on A by automorphisms, corresponding to the case B = kG with its natural bialgebra structure, or an action of a Lie algebra L by derivations, in which case B is the universal enveloping algebra k[L]. Then given finite-dimensional subspaces U ⊆ A, V ⊆ B such that V generates B as an algebra, and U generates A as an algebra with B-action, it is natural to study how A grows when we start with the subspace U and generate the whole algebra A by successive applications of the algebra operations, together with the actions of elements of V.

In this situation, it is not obvious how best to organize the simultaneous “feeding in” of elements of U and of V as we measure the growth of A. We will introduce two ways of doing this. One of these, which leads to what I will call the “length” growth function, is the obvious generalization of what is done in the classical case; but we will see that the other, the “depth” growth function, gives some information that the length growth function misses (though the reverse is also true).

In the classical study of growth of algebras, “unrestrained growth” corresponds to the exponential growth rate. As we shall see, the same is true for our length growth function; but for the depth growth function, “unrestrained growth” corresponds to doubly exponential growth, i.e., to functions like 2^{2^{n}} (roughly speaking, because a string of “depth n” can have length up to 2^{n}). For each of our growth functions, we shall see that the maximal growth rate can occur either as a result of unrestrained growth of A alone (for instance, if B is trivial and A is a free associative algebra), or mainly as a result of unrestrained growth of B (for instance if A is commutative, while B is the group algebra of a free group). However, in Section 2, we will find that simultaneous restrictions on A as an algebra and B as a bialgebra can yield restrictions on the growth of A under the action of B.

In Section 4, we show that our two measures of growth are not merely invariants of A as an algebra with action of the bialgebra B, but of A as a vector space with an “operad” of multilinear maps, namely, the operad of derived multilinear operations generated by the bilinear multiplication of A and the linear operations of the elements of B. In Section 5 that observation is applied to the problem that originally led me to look at these matters: the question of whether, in a free associative algebra k < X >, every finitely generated subalgebra is finitely related within the quasivariety generated by all free associative k-algebras. The role of the results of Sections 1–4 is actually to shoot down an idea that I had thought might prove this statement; but perhaps they will nonetheless lead to a better understanding of the problem. (The material in those last two sections is only sketched.)

1. General definitions and results A field k will be assumed fixed throughout this paper.

We begin by recalling some standard concepts [11, p.5].

Definition 1.1: Let Φ denote the set of nondecreasing sequences (d(1), …, d(n), …) of nonnegative real numbers, and let us define a preordering (a reflexive transitive binary relation) “≤” on Φ by writing

(d(1), …, d(n), …) ≤ (e(1), …, e(n), …) if and only if there exists a positive integer r such that d(n) ≤ e(rn) for all positive integers n.

Then the equivalence classes of Φ under the relation

d ≤ e and e ≤ d

will be called growth rates (of sequences of nonnegative real numbers). The equivalence class of a sequence d = (d(1), …, d(n), …) will be denoted G((d(1), …, d(n), …)) or G(d) or, most often, G(d(n)); in the last case, the integer-valued variable will always be named n.

The set of growth rates will be taken to be partially ordered by defining

G(d) ≤ G(e) if and only if d ≤ e under the preordering defined above.

By the exponential growth rate we will mean the common value of the growth rates G(c^{n}) for all c > 1, and by the double exponential growth rate, the common value of the growth rates G(c^{d^{n}}) for all c, d > 1.

The reader can easily verify that all functions of the form c^{n} indeed have the same growth rate, and that the same is true of functions of the form c^{d^{n}}.

We now turn to the growth of an algebra A on which another algebra B acts linearly. We will eventually want A to satisfy some identities, and B to be a bialgebra acting on A by a bialgebra action, but in this section we will not need to make these assumptions. In the statement of the next definition, we follow the usual notational convention that if U_{1} and U_{2} are k-subspaces of a k-algebra, or U_{1} is a subspace of a k-algebra and U_{2} a subspace of a module over this algebra, then

(1.2)  U_{1}U_{2} = span_{k}{xy | x ∈ U_{1}, y ∈ U_{2}}.

Definition 1.3: Let A be a k-algebra (not necessarily associative or unital) and B an associative unital k-algebra, and assume that a B-module structure compatible with the k-vector-space structure is given on the underlying k-vector-space of A.

Then for any k-subspaces U ⊆ A and V ⊆ B such that 1_{B} ∈ V, we define the k-subspaces U^{length,n,V} ⊆ A and U^{depth,n,V} ⊆ A (n = 1, 2, …) recursively, taking

U^{length,1,V} = U,
U^{depth,1,V} = U,

and for n > 1,

U^{length,n,V} = V (U^{length,n−1,V} + Σ_{0<m<n}(U^{length,m,V})(U^{length,n−m,V})),
U^{depth,n,V} = V (U^{depth,n−1,V} + (U^{depth,n−1,V})(U^{depth,n−1,V})).

(Note that if A is unital and 1_{A} ∈ U, the initial summands U^{length,n−1,V} and U^{depth,n−1,V} can be dropped from the above definitions, since they will be contained in the terms that follow. In any case, the presence of those initial terms guarantees that the above families of subspaces of A are ascending chains, as functions of n.)

We shall occasionally want to speak of the growth of a k-algebra A not given with an additional module structure. In that situation, we define

U^{length,n} = U^{length,n,k},
U^{depth,n} = U^{depth,n,k},

using the k-module structure of the k-algebra A.

Lemma 1.4: Let A, B, U, V be as in the above definition. Then (i) For every positive integer n, one has

U^{length,n,V} ⊆ U^{depth,n,V} ⊆ U^{length,2^{n−1},V} .

(ii) The union over n of the chain of subspaces U^{length,n,V} and the union over n of the chain of subspaces U^{depth,n,V} are both equal to the least subalgebra of A that contains U and is closed under the action of elements of V.

(iii) For all positive integers m and n,

(U^{depth,m,V})^{depth,n,V} = U^{depth,m+n−1,V} .

(iv.a) If r > 0 and U′ is a subspace of U^{length,r,V}, then for all n,

U^{′ length,n,V} ⊆ U^{length,rn,V} .

(iv.b) If r > 0 and U′ is a subspace of U^{depth,r,V}, then for all n,

U^{′ depth,n,V} ⊆ U^{depth,n+r−1,V} ⊆ U^{depth,rn,V} .

(v) If r > 0 and V′ is a subspace of V^{length,r} ⊆ B, then for all n,

U^{length,n,V′} ⊆ U^{length,rn,V} and U^{depth,n,V′} ⊆ U^{depth,rn,V} .

Proof: Both inclusions of (i) are immediate by induction.

The unions of the chains referred to in (ii) are clearly contained in the indicated subalgebra; on the other hand, these unions are closed under the multiplication of A and the action of V, giving equality. (In getting closure under multiplication, one uses the hypothesis 1_{B} ∈ V, and in getting closure under the action of V, one uses the left-hand summands in the recursive definitions of these spaces.)

(iii) is clear, since the depth construction works by iterating a single unchanging operation.

(iv.a) is proved by induction from the case n = 1, while (iv.b) is immediate from (iii). (The final inclusion in (iv.b) is recorded simply to make a later application of Definition 1.1 easier.)

The verification of (v) is again by induction: in going from n to n + 1 in the first assertion, we apply the recursive definition of U^{length,rn+1,V}, followed by r − 1 applications of the observation U^{length,m+1,V} ⊇ V U^{length,m,V} to show that U^{length,r(n+1),V} contains all summands in the definition of U^{length,n+1,V^{length,r}}; the depth case works the same way.

Letting “dim” denote “dimension as a k-vector-space”, we see that parts (iv.a), (iv.b) and (v) of the above Lemma immediately give Corollary 1.5:

(i) Suppose A, B, U, V are as in Definition 1.3, and U and V are finitedimensional. Let U′ be any finite-dimensional subspace of the least subalgebra of A that contains U and is closed under the action of V, and V′ any finite-dimensional subspace of the subalgebra of B generated by V. Then (for G as defined in Definition 1.1), we have

G(dim(U^{′ length,n,V′})) ≤ G(dim(U^{length,n,V})),
G(dim(U^{′ depth,n,V′})) ≤ G(dim(U^{depth,n,V})).

Hence, (ii) If B is finitely generated as a k-algebra, and A is finitely generated as a

k-algebra with action of B, then, letting U and V be finite-dimensional k-subspaces which generate A and B in these senses, the growth rates G(dim(U^{length,n,V})) and G(dim(U^{depth,n,V})) are invariants of the pair (A, B).

Hence we may make

Definition 1.6: Let B be a finitely generated associative unital k-algebra, and A a not necessarily associative k-algebra given with a B-module structure compatible with its k-vector-space structure, such that A is finitely generated with respect to the combined k-algebra and B-module structures. Then we shall define

G^{length}(A, B) = G(dim(U^{length,n,V})),
G^{depth}(A, B) = G(dim(U^{depth,n,V})),

where U and V are any finite-dimensional k-subspaces which generate A and B in these senses.

We may also write G^{length}(A) and G^{depth}(A) for the corresponding growth-rates of a k-algebra A without additional structure (cf. last paragraph of Definition 1.3).

Lemma 1.7: For A, B, U, V as above, G^{length}(A, B) is at most exponential (i.e., is ≤ the exponential growth rate, defined in the last paragraph of Definition 1.1) and G^{depth}(A, B) is at most doubly exponential (i.e., is ≤ the double exponential growth rate).

Sketch of Proof: Choose bases of U and V, and let us write elements of U^{length,n,V}, respectively U^{depth,n,V}, as linear combinations of expressions in elements of these bases. Each such expression can be represented by a string built from an alphabet of symbols for elements of these bases, and parentheses. If c is the number of symbols in the alphabet, then the number of such strings of length ≤ r (counting punctuation) is bounded by (c + 1)^{r} (the “+1” corresponding to the adjunction to our alphabet of one more symbol, “whitespace”, to pad strings of smaller length to length r).

Now it is easy to verify by induction that U^{length,n,V} is spanned by a set of elements represented by strings whose lengths have a bound linear in n, giving an exponential bound for the number of such strings, and that the lengths of strings similarly denoting a set of elements spanning U^{depth,n,V} have an exponential bound, giving a doubly exponential bound for their number.

Let us note some cases where these upper bounds are achieved.

Example 1.8: Let A be a free associative unital k-algebra on two generators, k <x, y >, and B the k-algebra k, and let us make A a B-module via its k-vector-space structure. Then if we take for U the span of {x, y}, and V = B, we see that U^{length,n,V} contains all monomials in x and y of length n, of which there are 2^{n}, so its dimension grows exponentially, and that U^{depth,n,V} contains all monomials in x and y of length 2^{n−1}, of which there are 2^{2^{n−1}}, so its dimension grows doubly exponentially.

The above example shows that the bounds of Lemma 1.7 can be achieved “without any help from B”. The next example will show that we can also get such growth with B “doing most of the work”, namely, with an A that is commutative, and hence intrinsically “slow growing” ([11, Corollary 7.5]).

Example 1.9: This time let B be the free algebra k < x, y >, and for A let us take the commutative polynomial ring on a set of indeterminates t_{S}, where S runs over < x, y >, the free semigroup-with-1 (monoid) on {x, y}. If we let this semigroup act on the above set of indeterminates by defining St_{T} = t_{ST} for S, T ∈<x, y >, this induces an action of <x, y > by k-algebra endomorphisms on A, which we extend k-linearly to get a B-module structure on A. (In fact, that module structure is a bialgebra action, under the standard bialgebra structure of the semigroup algebra B, but we are not considering bialgebra structures in this section.)

Let us now take for U the span of the singleton {t_{1}} (where 1 is the identity element of < x, y >, the empty string of x’s and y’s), and for V the span of {1, x, y} ⊆ B. We shall construct a set of 2^{2^{n}} linearly independent elements in U^{depth,n+3,V}. Namely, to each string of 2^{n} x’s and y’s,

(1.10)  z_{1}, …, z_{2^{n}} (z_{i} ∈ {x, y}),

we shall associate a certain monomial in the indeterminates t_{S} which lies in U^{depth,n+3,V}, in such a way that distinct strings yield distinct monomials.

Since t_{1} ∈ U = U^{depth,1,V}, we have t_{x}, t_{y} ∈ U^{depth,2,V}. (Here we have used the action of V, but not the multiplication of A.) Hence given (1.10) we can form the sequence of elements

t_{z_{1}}, t_{z_{2}}, …, t_{z_{2^{n}−1}}, t_{z_{2^{n}}} ∈ U^{depth,2,V} .

Moving up to depth 3, let us once again use the action of V but not the multiplication of A, this time applying x to all elements in odd positions in the above sequence, and y to all elements in even positions, getting

t_{xz_{1}}, t_{yz_{2}}, …, t_{xz_{2^{n}−1}}, t_{yz_{2^{n}}} ∈ U^{depth,3,V} .

At the next step, our construction settles into the form of all subsequent steps: Assuming n > 0, we turn our sequence of 2^{n} elements of depth 3 into a sequence of 2^{n−1} elements of depth 4, by multiplying them together in pairs, and applying x to those products appearing in odd positions in the resulting sequence, and y to those appearing in even positions:

t_{xxz_{1}}t_{xyz_{2}}, t_{yxz_{3}}t_{yyz_{4}}, …, t_{yxz_{2^{n}−1}}t_{yyz_{2^{n}}} ∈ U^{depth,4,V} .

We then pass in the same way to a sequence of 2^{n−2} elements of depth 5, and so on, until we arrive at a single monomial in U^{depth,n+3,V}. Now I claim that despite the commutativity of A, we can recover from this monomial the original sequence z_{1}, …, z_{2^{n}}. The point is that if we look at the subscript on the ith of the 2^{n} factors in our description of this monomial, a string of n + 2 x’s and y’s, the middle n terms in this string “encode” i, while the last term of the string is z_{i}, so this monomial indeed determines the map i ↦ z_{i}.

Thus, for n ≥ 3, dim(U^{depth,n,V}) ≥ 2^{2^{n−3}}. This shows that G^{depth}(A, B) is the doubly exponential growth rate. Moreover, combined with the right-hand inclusion of Lemma 1.4(i), the same inequality gives dim(U^{length,2^{n−1},V}) ≥ 2^{2^{n−3}}, from which one can deduce that G^{length}(A, B) is the exponential growth rate.

In the above two examples, both our measures of growth assumed their maximum values. The next example will show, however, that G^{depth} can detect some restrictions on growth that G^{length} misses.

Example 1.11: Let A, B, U, V be as in the preceding example, and let A′ be the factor-ring obtained from A by imposing the relations t_{S}^{2} = t_{S} for all S, and t_{S}t_{T} = 0 for S ≠ T. By abuse of notation, we will use the same symbols for elements of A and their images in A′. (A′ may be identified with the algebra of k-valued functions on <x, y > spanned by k and the functions of finite support, with each t_{S} corresponding to the function equal to 1 at S and 0 elsewhere.) The action of B on A clearly induces an action on A′; we will write U′ for the image of the space U in A′.

Since in A′, multiplication of monomials never yields new monomials, we see that on spaces spanned by monomials, the operators ( )^{length,n,V} and ( )^{depth,n,V} are both simply the operation of applying V n − 1 times. From this it is easy to verify that dim(U^{′ length,n,V}) = dim(U^{′ depth,n,V}) = 2^{n} − 1. So G^{length}(A′, B) and G^{depth}(A′, B) are both the exponential growth rate, which is the greatest possible growth rate for G^{length}, but not for G^{depth}.

The difference between the “length” and “depth” constructions that this example brings out is that U^{length,n,V} is spanned by products of ≤ n elements of U that have each been acted on by n − 1 elements of V, so elements of U and of V are being brought in at essentially the same rate, while U^{depth,n,V} is spanned by products of ≤ 2^{n−1} elements of U, on each of which only n − 1 elements of V have acted, so V is having relatively less effect than U. (Nevertheless, each of the terms that span U^{depth,n,V} involves essentially the same number of choices of elements of V as of elements of U; the difference is that only a small fraction of these elements act on each element of U.)

2. Bialgebra actions

Recall ([13], [17]) that a k-bialgebra means a k-algebra B which has, in addition, a structure of k-coalgebra, that is, a k-linear map

Δ : B → B ⊗_{k} B

satisfying certain compatibility conditions which we will not record here. An action of B as a bialgebra on a k-algebra A means a structure of B-module (as usual, respecting the k-vector-space structure) such that for every y ∈ B, if Δ(y) = Σ_{i} y′_{i} ⊗ y′′_{i}, then the action of y on A satisfies the identity

(2.1)  y(x_{1}x_{2}) = ∑_{i} y′_{i}(x_{1})y′′_{i}(x_{2}) (x_{1}, x_{2} ∈ A).

A familiar class of examples are group rings B = kG, which become bialgebras on setting Δ(g) = g ⊗ g for all g ∈ G. In this case, (2.1) says that the action of each element of g is a k-algebra endomorphism of A (hence, as it is invertible, a kalgebra automorphism). As a result, a bialgebra action of kG on A is equivalent to an action of the group G on A by k-algebra automorphisms. Similarly, if L is a Lie algebra over k, then its universal enveloping algebra k[L] has a comultiplication under which Δ(y) = y ⊗ 1 + 1 ⊗ y for all y ∈ L, and an action of this bialgebra on A is equivalent to an action of L on A by derivations. (For the general theory of actions of bialgebras on algebras, see [13]; for a thumbnail introduction to the concept, see [1]. An algebra A given with an action of a bialgebra B in the above sense is often called a “B-module algebra”, but we shall not use that term here, to avoid confusion with the more general situation of the preceding section.)

Let us make

Convention 2.2: All bialgebras will here be assumed to have underlying kalgebra structure that is associative and unital. (Coassociativity of the coalgebra structure and other additional conditions will be specified when required. As usual, algebras other than bialgebras will not be assumed associative or unital unless this is specified.)

We recall that a variety of algebras means a class of algebras defined by a set of identities.

Lemma 2.3: Let A be a k-algebra belonging to a variety A of (unital or nonunital, possibly nonassociative) k-algebras, and B a k-bialgebra acting as a bialgebra on A.

For every positive integer r, let F_{A}(r) denote the free algebra in A on r generators, and U(r) ⊆ F_{A}(r) the r-dimensional subspace spanned by these generators. For each r and n, let

f(r, n) = dim(U(r)^{depth,n}).

Then for any finite-dimensional subspace U ⊆ A, any finite-dimensional subcoalgebra V ⊆ B containing 1_{B}, and any n > 1, we have

(2.4)  dim(U^{depth,n,V}) ≤ f(dim(V^{length,n−1}) · dim(U), n).

Proof: The assumption that V is a subcoalgebra of B means that when (2.1) is applied with y ∈ V, the terms y′_{i} and y′′_{i} on the right can also be taken to lie in V; hence for any subspaces U_{1}, U_{2} ⊆ A,

(2.5)  V (U_{1}U_{2}) ⊆ (V U_{1})(V U_{2}).

From this it easily follows that

(2.6)  V (U^{depth,n}) ⊆ (V U)^{depth,n},

and from this, an easy induction using Lemma 1.4(iii) shows that

(2.7)  U^{depth,n,V} ⊆ ((V^{length,n−1})U)^{depth,n}.

Since (V^{length,n−1})U is a linear image of V^{length,n−1} ⊗_{k} U, its dimension is ≤ dim(V^{length,n−1}) · dim(U). Mapping the free algebra in A on dim(V^{length,n−1}) · dim(U) indeterminates onto this subspace of A, and recalling the definition of f(r, n), we see that the dimension of the right-hand side of (2.7) is bounded by f(dim(V^{length,n−1}) · dim(U), n), giving the desired inequality.

To apply this in a concrete case, let A be the variety of commutative associative unital k-algebras. Thus f(r, n) is the number of commutative monomials of degree ≤ 2^{n} in r indeterminates. This is less than or equal to the number of monomials in r indeterminates in which each indeterminate has exponent ≤ 2^{n}, which is (2^{n})^{r} = 2^{nr}, allowing us to prove

Theorem 2.8: Let B be a coassociative bialgebra which is finitely generated as a k-algebra, and let A be an associative commutative unital k-algebra on which B acts as a bialgebra, and which is finitely generated as a k-algebra with B-action.

Let G^{length}(B) = G(d(n)). Then

G^{depth}(A, B) ≤ G(2^{nd(n)}).

In particular, if the length growth rate of B as an algebra is less than exponential, the depth growth rate of A as an algebra with B-action is less than doubly exponential.

Proof: Because B is coassociative, it is locally finite-dimensional as a coalgebra ([17, Corollary 2.2.2]), so letting V_{0} be any finite-dimensional subspace generating B as an algebra and containing 1_{B}, and V the subcoalgebra that it generates, V will also be a finite-dimensional generating subspace; hence G^{length}(B) = G(dim(V^{length,n})).

Now given sequences d(n) and e(n) such that G(d(n)) = G(e(n)), it is easily verified that G(nd(n)) = G(ne(n)), and hence that G(2^{nd(n)}) = G(2^{ne(n)}). This means that it will suffice to prove our theorem with the arbitrary representative d(n) of the equivalence class G^{length}(B) replaced by any other representative thereof; in particular, by the sequence dim(V^{length,n}).

Now let U be a finite-dimensional subspace that generates A as a k-algebra with B-action. Then (2.4), combined with the above observation that for A the variety of commutative associative k-algebras, f(r, n) ≤ 2^{nr}, tells us that

dim(U^{depth,n,V}) ≤ 2^{n·dim(V^{length,n−1})·dim(U)}.

When we pass to growth rates, the linear factor n at the beginning of the exponent can “absorb” the constant factor dim(U) at the end, since G(n dim(U)) = G(n), while the n−1 can clearly be replaced by n. This gives us the desired bound.

We could have made similar estimates for G^{length}(A, B), but these would not have been very useful, as shown by

Example 2.9: Let B = k[x], and let us regard this as the semigroup algebra of the free semigroup on one generator x, with its usual bialgebra structure, so that when B acts as a bialgebra on an algebra A, x acts by an endomorphism of A. Let A be the polynomial ring in indeterminates t_{0}, t_{1}, t_{2}, … and let B act so that x^{i}t_{j} = t_{i+j}. (Thus, the difference between this and Example 1.9 is just that we are now using a free semigroup on one generator instead of two.)

Let U be spanned by {t_{0}}, and V by {1, x}. I claim that we can find 2^{n} linearly independent monomials in U^{length,n+1,V}. Indeed, given ε(1), …, ε(n) ∈ {0, 1}, consider the element

x^{ε(1)}(t_{0}(x^{ε(2)}(t_{0} ⋯ (x^{ε(n−1)}(t_{0}x^{ε(n)}t_{0})) ⋯))) ∈ U^{length,n+1,V} .

This equals

t_{ε(1)}t_{ε(1)+ε(2)} ⋯ t_{ε(1)+···+ε(n)}.

The indeterminates in the above monomial are arranged in ascending order of their subscripts, hence this sequence of subscripts is uniquely determined by the monomial. From the sequence of subscripts we can clearly recover the sequence ε(1), …, ε(n), hence the 2^{n} possible choices of that sequence yield distinct monomials.

Thus, with B having the lowest possible growth rate among finitely generated algebras that are not finite-dimensional ([11, Proposition 1.4]), and (assuming k is infinite) A belonging to the smallest nontrivial variety of unital k-algebras, G^{length}(A, B) can still be the largest possible growth rate. (If k is a finite field, the variety of commutative associative k-algebras does have proper subvarieties; for instance, when k = Z_{2}, the variety of Boolean rings. But the above example can be adapted even to these varieties, by letting ε be {1, 2}-valued rather than {0, 1}-valued, and using the fact that these varieties satisfy no identities in which each indeterminate has exponent everywhere ≤ 1.)

However, the next Theorem will show that if we put restrictions not only on the growth rate of B as an algebra, but also on its coalgebra structure, we can get a nontrivial bound on G^{length}(A, B); though this bound (which we will see is best possible) is still surprisingly high.

The proof of the Theorem uses a result from the theory of partitions of ntuples of nonnegative integers, obtained by analytic methods in [15]. However, in addition to citing that reference, I will include below a self-contained argument that yields a slightly weaker bound, with G(n^{n^{r/(r+1)}}) in place of G(2^{n^{r/(r+1)}}). (To see that this is close to the latter bound, note that it implies the bound G(2^{n^{c}}) for all c strictly greater than r/(r + 1).)

Theorem 2.10: Let L be a Lie algebra over k, with 0 < dim(L) = r < ∞; let B = k[L] be its universal enveloping algebra, with the standard bialgebra structure, and let A be a commutative associative k-algebra on which B acts as a bialgebra (equivalently, on which the Lie algebra L acts by derivations), which is finitely generated as a k-algebra with B-action. Then

(2.11)  G^{length}(A, B) ≤ G(2^{n^{r/(r+1)}}).

Proof: Let us take

V = k + L ⊆ k[L].

We recall that for y ∈ L we have Δ(y) = y ⊗ 1 + 1 ⊗ y. From this we see that for subspaces U_{1}, U_{2} ⊆ A,

V (U_{1}U_{2}) ⊆ (V U_{1})(U_{2}) + (U_{1})(V U_{2})

(contrast (2.5)). It follows that for U ⊆ A and n > 0, U^{length,n,V} is a sum of products

(V^{p(1)}U)(V^{p(2)}U) ⋯ (V^{p(m)}U)

satisfying not only the condition

(2.12)  m ≤ n,

but also

(2.13)  p(1) + p(2) + ⋯ + p(m) < n.

Let us take a k-basis X for U and a k-basis Y = Y_{0} ∪ {1} for V, where Y_{0} is a basis for L. Then any member of V^{p(i)}U is a linear combination of expressions of the form y_{1} ⋯ y_{p(i)}x (y_{j} ∈ Y, x ∈ X). Now if we put any total ordering on the basis Y_{0}, then by the Poincaré–Birkhoff–Witt Theorem (the easy direction thereof), we can express any product y_{1} ⋯ y_{p} (y_{i} ∈ Y) as a linear combination of products of elements of Y_{0}, in each of which the factors occur in monotone nondecreasing order with respect to our ordering, and the number of factors is still ≤ p. It follows that U^{length,n,V} is spanned by products

(2.14)  (y_{1,1} ⋯ y_{1,p(1)}x_{1}) ⋯ (y_{m,1} ⋯ y_{m,p(m)}x_{m})

(y_{i,j} ∈ Y_{0}, x_{i} ∈ X) subject to (2.12), (2.13), and the condition that each sequence y_{i,1}, …, y_{i,p(i)} is monotone nondecreasing. Recall that A is commutative, so that the order of the m factors in (2.14) is irrelevant. To complete the proof of (2.11) it will suffice to show that as a function of n, the number of distinct products (2.14), subject to these conditions, has growth ≤ G(2^{n^{r/(r+1)}}).

Let us first note that (2.14) can be written as a product, over x ∈ X, of the subproducts formed of those terms (y_{i,1} ⋯ y_{i,p(i)}x_{i}) with x_{i} = x. Each of those subproducts still satisfies (2.12) and (2.13), so if we can show that for each x, the growth rate of the number of such products (2.14) in which all x_{i} equal x is bounded by G(2^{n^{r/(r+1)}}), then by taking the product over X, we will get the bound G(2^{card(X)n^{r/(r+1)}}) for the number of products (2.14) without that restriction. But the factor n^{r/(r+1)} in the exponent can “absorb” the constant factor card(X) (since for any α > 0 and any real number c, one has G(cn^{α}) = G(n^{α})), so this will yield the desired estimate.

It is at this point that one can either use a self-contained argument leading to the weaker bound

(2.15)  G(n^{n^{r/(r+1)}}),

or cite a result in the literature from which the precise bound G(2^{n^{r/(r+1)}}) can be deduced. I shall first give the former argument, then the latter.

Explicit argument leading to the bound (2.15). To count expressions (2.14) in which all x_{i} have a given value x, let us again factor each such expression, this time into

(2.16)  the product of those terms of (2.14) with p(i) < n^{1/(r+1)}

times

(2.17)  the product of those terms of (2.14) with p(i) ≥ n^{1/(r+1)}.

As above, it will suffice to show that each of these factors has growth rate bounded by (2.15). Roughly, this will hold because, though there may be a large number of factors (y_{i,1} ⋯ y_{i,p(i)}x_{i}) in (2.16), each is short, so they are chosen from a relatively small set of possibilities; while though there are a large number of possibilities for each factor in (2.17), there are relatively few such factors, in view of (2.13).

Let us begin by estimating the number of possibilities for each factor (y_{i,1} ⋯ y_{i,p(i)}x_{i}) of (2.16) or (2.17). We use the general observation that for any d, the number of distinct products y_{1} ⋯ y_{p} such that p < d and such that the sequence of y’s is nondecreasing under our ordering on Y_{0} is at most d^{r}, since such a product is determined by the exponents on the r elements y ∈ Y_{0}, and each of these exponents is < d. Thus, each factor in the product (2.16) is chosen from among ≤ (n^{1/(r+1)})^{r} = n^{r/(r+1)} possibilities, while in (2.17), where we can merely say, on the basis of (2.13), that each p(i) is < n, the number of choices for each factor is ≤ n^{r}; in fact, < n^{r}, since the case p(i) = 0 is excluded.

In estimating the number of distinct products (2.16), we use the same principle again: (2.12) says such a product has ≤ n terms, we have seen that each term is chosen from among ≤ n^{r/(r+1)} possibilities; the product depends only on the total exponent of each factor, so the number of products is bounded by (n + 1)^{n^{r/(r+1)}}, which has the same growth rate as n^{n^{r/(r+1)}}, as required.

In the case of (2.17), we see from (2.13) that any possible value for this product will have < n/n^{1/(r+1)} = n^{r/(r+1)} factors, which is small compared with what we know about the number of choices for each factor, namely that it is < n^{r}. In this situation, it is not to our advantage to collect multiple occurrences, or even to use the commutativity of A; we simply throw in factors “1” to bring the number of factors up to precisely the greatest integer in n^{r/(r+1)}, note that in each position in the resulting product there are at most n^{r} possibilities (we had < n^{r} before we threw in the possibility “1”), and conclude that the total number of possibilities for such products is bounded by (n^{r})^{n^{r/(r+1)}} = n^{rn^{r/(r+1)}}. Here the n^{r/(r+1)} in the exponent can absorb the constant factor r, giving the desired bound G(n^{n^{r/(r+1)}}).

We now give the alternative completion of our proof.

Argument by reference to the literature. Let N denote the additive semigroup of nonnegative integers. Given any product (2.14) subject to (2.12), (2.13), and the conditions that each sequence y_{i,1}, …, y_{i,p(i)} be monotone nondecreasing and that all x_{i} have a given value x, we may associate to each factor (y_{i,1} ⋯ y_{i,p(i)}x_{i}) the element of N^{r} whose components are the exponents appearing on the r members of Y_{0} in this expression, and thus associate to the whole product (2.14) the “family” (set with multiplicity) of these elements of N^{r}. Note that by (2.12), this family has ≤ n occurrences of the zero element (0, …, 0) ∈ N^{r}; hence if we drop zero elements, the resulting map from products (2.14) to families of elements of N^{r} − {(0, …, 0)} is at most (n + 1)-to-one.

Now by (2.13), the family of elements of N^{r} − {(0, …, 0)} that we get from each product (2.14) has the property that summing its elements gives a member of N^{r} whose components sum to < n. The set of such families is clearly contained in the set of families of elements of N^{r} − {(0, …, 0)} with the property that each component of the sum of the family is < n. I claim, further, that this last set can be mapped injectively into the set of families with the property that each component of the sum of the family is precisely 2n. Indeed, there is a unique way to adjoin to such a family a single additional element of N^{r} − {(0, …, 0)} so as to get this sum, and the original family can be recovered from the enlarged family by deleting the unique element having components > n.

Now families of this sort are known as partitions of the element (2n, …, 2n) ∈ N^{r} − {(0, …, 0)}, and the asymptotics of the number of such partitions is studied in [15]. In particular, if in the second display on p. 25 of [15] we set r = 1 (which in the notation of [15] specifies “partitions into vectors which may have zero entries, and such that repeated summands are allowed”), and put (2n, …, 2n) for (n_{1}, …, n_{j}), the resulting formula says that the initial term in the asymptotic expansion of the logarithm of the number of such partitions is (r + 1)(T_{10}(2n)^{r})^{1/(r+1)}. (Having substituted the value 1 for the r of [15], I am now giving r the sense it has in the present discussion.) Here T_{10} is a constant (because its second subscript is 0; for its value, see [15, (2.14) p. 21]). Hence the logarithm of the number of partitions is approximated by a constant times (n^{r})^{1/(r+1)} = n^{r/(r+1)}; so the number of partitions grows as the exponential of that expression. We have mapped the set of products (2.14) into the set of such partitions in a way that is at most (n + 1)-to-one; but a factor n + 1 may be absorbed by our growth-rate function. This completes the proof of (2.11).

I am indebted to George Andrews for referring me to [15].

The next example shows that the above result is sharp. The idea is to construct an A such that the monomials (2.14) are linearly independent.

Example 2.18: Given any finite-dimensional Lie algebra L, let B = k[L] as in the preceding Theorem, and let A be the symmetric algebra on the underlying vector space of B. For each y ∈ B, we shall write t_{y} for the corresponding element of the canonical generating subspace of A. (Thus, if we take any basis S of B = k[L], we can describe A as the polynomial ring on {t_{y} | y ∈ S}.) For each y ∈ L, the linear map t_{y′} ↦ t_{yy′} of this generating subspace into itself can be extended uniquely to a derivation of A, by general properties of derivations on polynomial rings, and it is easy to verify that this family of derivations constitutes an action of the Lie algebra L on A, equivalently, a bialgebra action of B on A. (In fact, it is not hard to see that in the class of commutative associative k-algebras with action of L by derivations, equivalently, with bialgebra action of B, our A is the free algebra on the one generator t_{1}.)

Now let V = k + L ⊆ B, and let U be the subspace of A spanned by t_{1}. We shall sketch, very briefly this time, how for each positive integer n which is an (r + 1)st power, one can construct in U^{length,rn,V}, a linearly independent family of cardinality 2^{n^{r/(r+1)}}.

As in the proof of the preceding Theorem, let Y_{0} be a k-basis of L (hence of cardinality r), let us order Y_{0}, and let us consider products y_{1} ⋯ y_{p} of elements of Y_{0} such that the sequence of factors is nondecreasing under our ordering. The number of such products in which each member of Y_{0} appears < n^{1/(r+1)} times is (n^{1/(r+1)})^{r} = n^{r/(r+1)}; moreover, since each of these products has length < rn^{1/(r+1)}, the corresponding indeterminate t_{y_{1}···y_{p}} ∈ A lies in U^{length,n′,V}, where n′ = rn^{1/(r+1)}. We now let T ⊆ U^{length,n′,V} be the set of these n^{r/(r+1)} algebraically independent elements, and consider all products of subsets of T. There are 2^{n^{r/(r+1)}} such products; since each of these has at most n^{r/(r+1)} factors, it lies in U^{length,n′′,V}, where n′′ = (rn^{1/(r+1)})(n^{r/(r+1)}) = rn, as claimed. When we pass to growth rates, the factor r can be ignored (by the equivalence relation used in the definition of growth rate), while the fact that our estimate has only been made for values of n that are (r + 1)st powers causes no difficulty, because successive integers of that form have ratios which approach 1, and which are therefore, in particular, bounded above. We conclude that G^{length}(A, B) ≥ G(2^{n^{r/(r+1)}}), complementing the estimate of Theorem 2.10.

Let us consider next what happens if B “stops growing” altogether.

Proposition 2.19: Let B be any bialgebra that is finite-dimensional as a kvector-space, and A a k-algebra (not necessarily associative) on which B acts as a bialgebra, and which is finitely generated as a k-algebra with this B-action.

Then A is in fact finitely generated as a k-algebra, and

G^{length}(A, B) = G^{length}(A),
G^{depth}(A, B) = G^{depth}(A).

Moreover, if A is associative, and if we write G^{length}(A) = G(d(n)), then

G^{depth}(A) = G(d(2^{n})).

Proof: Let U_{0} be a finite-dimensional subspace of A which generates it as an algebra with B-action, and let V = B. Then taking U = V U_{0}, we see that U will again be a finite-dimensional subspace generating A as an algebra with B-action, and moreover, it will be invariant under the action of V. From this and (2.1) we can see that the definition of U^{length,n,V} reduces to that of U^{length,n} and similarly for U^{depth,n,V}. This gives the first set of assertions of our Proposition.

If A is associative, so that we can drop parentheses, we see that U^{depth,n} is just the span of all products of strings of ≤ 2^{n−1} elements of U, which is the same as U^{length,2^{n−1}}, from which the final formula follows.

This formula shows that in the case of associative algebras without bialgebra action, the depth growth rate provides no information not given by the length growth rate. However, the formula and this conclusion fail for nonassociative A, as shown by

Example 2.20: Let A be the variety of nonunital nonassociative k-algebras defined by the identity

(uv)w = 0.

When we apply the recursive step in the definitions of U^{length,n} and U^{depth,n} to algebras in A, we see that this reduces to U^{length,n} = U^{length,n−1}+U(U^{length,n−1}) and U^{depth,n} = U^{depth,n−1} + U(U^{depth,n−1}) respectively. Hence these two chains of subspaces coincide, and we see that the nth term of each is the sum of all right-nested products U(U(⋯ (UU) ⋯)) with ≤ n U’s.

Thus, for any finitely generated algebra A ∈ A, we get G^{depth}(A) = G^{length}(A), which, if A is infinite-dimensional, is strictly smaller than the expression for G^{depth}(A) in the final statement of the above Proposition. For instance, if A is the free algebra in A on one generator x, then for U the space spanned by this generator we have U^{length,n} = U^{depth,n} = n, and if A is the free algebra on two generators and U the space spanned by these, U^{length,n} = U^{depth,n} = 2^{n+1} − 2.

Turning back for a moment to Theorem 2.8, let us note that although it assumes no conditions on the coalgebra structure of B, it becomes false if we drop the assumption that B have such a structure with respect to which its action on A is an action as a bialgebra (i.e., satisfies (2.1)):

Example 2.21: Let A be the (commutative associative) polynomial algebra k[t_{1}, t_{2}, …], let B be the 2-dimensional algebra k[x | x^{2} = x], and make A a B-module by letting x fix all monomials of degree ≤ 1, and letting it take each monomial s of degree > 1 to the indeterminate t_{f(s)}, where f(s) is the integer whose binary expansion has a 1 in the nth position from the right (the position with value 2^{n−1}) if and only if some indeterminate appears in s with exponent exactly n. This operation is idempotent, so it indeed makes A a B-module. Let U ⊆ A be the span of {1, t_{1}}, and let V = B. We will sketch a proof that we can find 2^{2^{n}−1} distinct monomials within U^{depth,n′,V}, where n′ is bounded by a linear function of n, hence that G^{depth}(A, B) is doubly exponential.

First, in essentially log_{2} n iterations of the depth construction, using only multiplications and not the operator x ∈ V, we can get the first n powers of t_{1}. Hence, by applying x at the next step, we get the indeterminates t_{2}, t_{2^{2}}, …, t_{2^{n−1}}. Let us now form all monomials in t_{1}, t_{2}, t_{2^{2}}, …, t_{2^{n−1}} having the property that each t_{2^{i}} occurs either with exponent i + 1 or with exponent 0. The largest degree of such a monomial, 1 + 2 + ⋯ + n, is on the order of n^{2}, so this takes about log_{2} n^{2} = 2 log_{2} n iterations of the depth construction. Applying x for the second and last time, we get from these monomials all indeterminates t_{N} with N < 2^{n}. Now in n iterations of the depth construction, again using only multiplication, we can form all monomials of total degree ≤ 2^{n} in these 2^{n} − 1 indeterminates, in particular, all 2^{2^{n}−1} monomials which are products of a subset of this set of indeterminates, as claimed.

Thus, though B has trivial growth, and A is commutative, G^{depth}(A, B) is doubly exponential.

It is interesting that by using an action of B that was not a bialgebra action, we have not only gotten much faster growth than can occur in the bialgebra action case; we were able to do so with only two applications of the action of V. In contrast, if B is a coassociative bialgebra acting as a bialgebra on A, it is not hard to show (from (2.6) and the corresponding statement for the length growth rate) that inserting into the definition of G^{length}(A) or of G^{depth}(A) a fixed number of occurrences of V cannot increase this growth rate.

For the final topic of this section, recall ([13, Chapter 4], [17, Chapter VII]) that when B is a coassociative bialgebra with a bialgebra action on an associative unital algebra A, one can construct the smash product A#B, a certain associative unital k-algebra generated by embedded copies of the algebras A and B, such that, if we write “·” for the multiplication of this algebra, to avoid confusion with the notation for the action of B on A, the linear map A ⊗_{k} B → A#B taking x ⊗ y to x · y is an isomorphism of vector spaces. To finish specifying the multiplication of A#B, I need to give a formula for y · x (x ∈ A, y ∈ B). To do this, let Δ(y) = Σ_{i} y′_{i} ⊗ y′′_{i} (cf. (2.1)); then the formula is

(2.22)  y · x = Σ_{i} y′_{i}(x) · y′′_{i}.

The next Proposition studies the growth of this algebra A#B and its subalgebras in terms of the growths of B, and of A under the action of B. In stating points (ii) and (iii), we use “multiplication” of growth rates, defined by G(d(n))G(e(n)) = G(d(n)e(n)). In point (iii) and its proof, we assume familiarity with the definition of Hopf algebras, and some of their properties.

Proposition 2.23: Let B be a coassociative bialgebra, and A an associative unital k-algebra on which B acts as a bialgebra. Then (i) If U is a subspace of A, and V a subcoalgebra of B containing 1_{B}, then in

A#B one has

(U · V)^{length,n} ⊆ (U^{length,n+1,V}) · (V^{length,n}).

(ii) If B is finitely generated as a k-algebra, and A is finitely generated as a kalgebra with B-action, then every finitely generated subalgebra C ⊆ A#B satisfies

G^{length}(C) ≤ G^{length}(A, B)G^{length}(B).

(iii) Under the hypotheses of (ii), if B is a Hopf algebra, then A#B is itself finitely generated as a k-algebra, and we have

G^{length}(A#B) = G^{length}(A, B)G^{length}(B).

Sketch of Proof: It is easy to deduce from (2.22) that if U_{1}, U_{2} are subspaces of A, and V_{1}, V_{2} subcoalgebras of B, then in A#B we have

(2.24)  (U_{1} · V_{1}) · (U_{2} · V_{2}) ⊆ (U_{1}(V_{1}U_{2})) · (V_{1}V_{2}).

Also, since A#B is associative, the sum in the recursive step of the definition of (U ·V)^{length,n} can be replaced by its m = 1 term; i.e., one can nest parentheses on the right. Applying (2.24) repeatedly to these nested products (but resisting the temptation to apply (2.1)), we easily get (i). This implies (ii), since any finitedimensional generating subspace for C will be contained in a finite-dimensional subspace of the form U · V.

If, further, B is a Hopf algebra with antipode S, then in the smash product A#B, the action of B on A becomes “inner” in the sense of [13, Chapter 6], so that for any subspaces U ⊆ A and V ⊆ B we have

(2.25)  V U ⊆ V · U · SV.

Hence if V is finite-dimensional and generates B as an algebra, and U is finitedimensional and generates A as an algebra with B-action, then from the subspace U + V + SV ⊆ A#B we can get all the elements of A, as well as all the elements of B; thus, this finite-dimensional subspace generates A#B. We find that using this subspace we get elements of A essentially “as fast” as we get them within A using its structure of k-algebra with B-action. (Precisely, we can write them using strings of elements of U + V + SV ⊆ A#B whose length is bounded by a constant multiple of the lengths of strings needed to get them in A under the action of B.) We also obviously get elements of B as fast in A#B as in B; this shows that the left-hand-side of the equation of (iii) is ≥ the right-hand-side; (ii) gives the reverse inequality.

Example 2.26: Applying (iii) above to Example 2.18, we get associative algebras A#B with length growth rates G(2^{n^{r/(r+1)}}) for r = 1, 2, . . .. (Here the length growth rates of the algebras B = k[L] are polynomial, so when we apply (iii) above, these are absorbed by the much larger length growth rates of the algebraswith-B-action A.) The simplest case, where r = 1, so that L is the unique 1dimensional Lie algebra, turns out to give the algebra described in [16] and in [6, §2.7], the first known example of an algebra with less than exponential but greater than polynomial growth.

In the development of that example in [16], the algebra we are calling A#B was described as the universal enveloping algebra of a Lie algebra. In fact, one can so describe A#B in the general case of the present example: Given A and B as in Example 2.18, the smash product A#B is the universal enveloping algebra of the (trivial) extension of the Lie algebra L by the free L-module on one generator, which is the underlying L-module of k[L]. It is interesting that though B is finitely presented as an associative algebra, and A as a commutative associative algebra with B-action, the finitely generated algebra A#B is not finitely related as an associative algebra: infinitely many relations are required to make the k-algebra generators of A commute with one another.

Example 2.27: Taking the A#B of the preceding example for the “A” of Proposition 2.19, and k for the finite-dimensional bialgebra “B”, and applying the last equation of that Proposition, we find that G^{depth}(A#B) = G(2^{(2^{n})^{r/(r+1)}}) = G(2^{2^{nr/(r+1)}}) = G(2^{2^{n}}). Thus, though these algebras A#B have less than maximal length growth rate, they have maximal depth growth rate. (Contrast Example 1.11.) Note also that by Theorem 2.8, G^{depth}(A, B) ≤ G(2^{n^{r+1}}), showing that the analog of Proposition 2.23 (in particular, part (iii)) does not hold for depth.

Since we have noted that A#B is a universal enveloping algebra of a Lie algebra, and a universal enveloping algebra has a structure of bialgebra, we may look at the growth of algebras on which this bialgebra A#B acts. Surprisingly, Theorem 2.8 tells us that if C is a commutative k-algebra finitely generated under an action of the bialgebra A#B, then G^{depth}(C, A#B) is less than doubly exponential, since G^{length}(A#B) is less than exponential—even though G^{depth}(A#B) is doubly exponential.

It would be interesting to characterize the class of bialgebras B such that for every commutative algebra A on which B acts and which is finitely generated under this action, G^{length}(A, B) is less than exponential. Theorem 2.10 showed that universal enveloping algebras of finite-dimensional Lie algebras belong to this class; comparison of that Theorem with Example 2.9 shows that membership in this class is a function of the bialgebra structure of B, and not just its algebra structure. It is not hard to deduce from Proposition 2.19 that all finitedimensional bialgebras also belong to this class. A plausible conjecture is that this class consists of those finitely generated bialgebras B which (as coalgebras) have finite-dimensional coradical [13, Chapter 5].

3. Digressions and remarks

3.1. The arithmetic of growth rates. In the above development, we have used various “obvious” facts about growth rates in an ad hoc way. A systematic development of this subject should begin by noting some general results on growth rates of sequences, and perhaps setting up some notation.

Note that one can operate on the set Φ of nondecreasing sequences of nonnegative real numbers by composition on the right with nondecreasing functions from the positive integers to the positive integers, and on the left by composition with nondecreasing functions from the nonnegative reals to the nonnegative reals. Since our preordering on Φ is based on looking at right composition with functions n ↦ rn, and right composition with one function commutes with left composition with any other function, that preordering is invariant under the above left composition operations. Hence, if f is a nondecreasing function on nonnegative real numbers, the operation on growth rates G(d(n)) ↦ G(f(d(n))) is well-defined. More generally, a function f of r variables that is nondecreasing in each variable may be seen to induce a well-defined map from r-tuples of growth rates to growth rates. Thus, after setting up appropriate notation, one could write the displayed inequality in Theorem 2.8 more cleanly as G^{depth}(A, B) ≤ 2^{G(n)G^{length}(B)}.

On the other hand, for f a nondecreasing function from positive integers to positive integers, the definition G(d(n)) ↦ G(d(f(n))) does not generally give a well-defined function; the necessary and sufficient condition on f for this to hold is that

G(f(n)) = G(rf(n))

for all positive integers r, equivalently, for some r > 1. When this holds, we find that the map G(d(n)) ↦ G(d(f(n))) depends only on G(f). An example of a function satisfying the above displayed equation is f(n) = 2^{n}; consequently, one could set up notation under which the last equation of Proposition 2.19 would take the form G^{depth}(A) = G^{length}(A) ∘ G(2^{n}).

3.2. On length and depth. The growth function of a nondecreasing sequence d(n) is in fact determined by the “sample” of its values one gets by letting n run over the powers of 2 (or over any other sequence in which the ratio of successive terms is bounded above). Indeed, if d(2^{m}) = e(2^{m}) for all m, then for any n, since there is a power of 2 between n and 2n, we find d(n) ≤ e(2n) and e(n) ≤ d(2n), hence G(d(n)) = G(e(n)). It follows that for A an associative algebra (without bialgebra action) and U a finite-dimensional generating subspace, the numbers dim(U^{depth,n}) = dim(U^{length,2^{n−1}}) (see Proposition 2.19) determine G(dim(U^{length,n−1})) = G^{length}(A). This does not say, however, that G^{depth}(A) determines G^{length}(A); it turns out that in passing from the sequence dim(U^{depth,n}) = dim(U^{depth,2^{n−1}}) to its growth rate G^{depth}(A), one discards too much information. Indeed, if dim(U^{length,n}) grows like n^{d}, we see that dim(U^{depth,n}) grows like (2^{n})^{d} = 2^{nd}, whose growth rate is the same for all d. (Roughly, one cannot recover G^{length}(A) from G^{depth}(A) because the logarithm function, unlike the exponential function, does not satisfy the displayed condition of 3.1.)

This may lead one to wonder whether we have been too crude in defining G^{depth}(A) as the growth rate of dim(U^{depth,n}). Could we have done better by using the common growth rate of all monotone functions d(n) satisfying d(2^{m}) = dim(U^{depth,m})?

¿From what we have just noted, this would have given an invariant for algebras without bialgebra action—which would have been identical with the length growth rate. But when we bring in a bialgebra action, we find that this proposed “sharpened” depth growth rate is not invariant under change of generating subspace for these bialgebras. (Cf., in Lemma 1.4, the difference between the first inclusion of (iv.b), and the right hand inclusion of (v).) Hence we cannot in general refine our definition as suggested.

3.3. GK and BK dimensions. In [6], W. Borho and H. Kraft introduced the concept of the Gel’fand–Kirillov dimension (or GK dimension) of a finitely generated algebra A. The idea is to define a function which, when applied to an algebra which grows like a polynomial of degree r, will report the value of r. The invariant they constructed, in our language a function of G^{length}(A), is obtained from any finite-dimensional generating subspace U of A as

lim sup_{n} (log_{n} dim(U^{length,n})),

a nonnegative real number or +∞.

In retrospect, they made one tactical error: they used “lim sup”, to make this value well-defined even in pathological cases, without making the name of the function reflect this somewhat arbitrary choice. (Recall that for a sequence d(n), lim sup_{n} d(n), the “limit superior” of the sequence, means lim_{n→∞}(sup_{m>n} d(m)).) This makes one tend to think of the above value as the actual limit, resulting in at least one incorrect claim, [6, Lemma 3.1(a)], where the authors assumed that this construction was additive when applied to a product of growth functions. (For counterexamples see [18], [12].) The present author suggested in [4, last paragraph] that we call the above invariant the upper Gel’fand–Kirillov dimension, the corresponding lim inf the lower Gel’fand– Kirillov dimension, and speak of A as having Gel’fand–Kirillov dimension only when these are equal. (That equality is established for some large classes of algebras in [18]. The distinction between upper and lower dimensions was in fact noted in [6, §2.12], but the upper dimension was simply called the “dimension”.)

The authors of [6] also consider algebras whose dimensions grow like 2^{n^{c}} (0 < c ≤ 1). To extract from the growth function of such an algebra the constant c, they define the “superdimension”,

lim sup_{n} (log_{n}(ln dim(U^{length,n}))).

For all algebras A, this gives a real number in [0,1], which we will here rename the Borho–Kraft or BK dimension of A. One can in fact prove that for associative algebras (without bialgebra action) the sequence in question has a limit; however, in the nonassociative case, or when generalizing to algebras with bialgebra action, we should again distinguish “upper” and “lower” dimensions when this equality is not known.

As we noted in point 3.2, the depth growth rate introduced in this note is in some ways cruder than the length growth rate. In particular, it follows from Proposition 2.19 that all associative algebras with finite nonzero Gel’fand–Kirillov dimension have the single depth growth rate of exponential growth, and all associative algebras with positive Borho–Kraft dimensions have the single depth growth rate of doubly exponential growth.

However, Theorem 2.8 suggests that the depth growth rates of certain algebras with bialgebra action will belong to classes from which one can extract nontrivial numerical invariants. If we list these invariants, in their “upper” and “lower” forms, and also the classical-type invariants based on the length growth rates, we get eight possible combinations: upper and lower, Gel’fand–Kirillov and Borho– Kraft, length and depth dimensions:

\{ \begin{matrix}lim & sup \\ lim & inf \end{matrix} \} \{ \begin{matrix}log & n \\ log & n & ln \end{matrix} \} \{ \begin{matrix}dim(U^{length,n,V}) \\ ln dim(U^{depth,n,V}) \end{matrix} \} .

Fortunately, this is not quite the Babel of concepts that it appears. First, upper and lower dimensions differ only in pathological cases; when they agree, one does not have that distinction to deal with. Secondly, the GK and BK dimensions are in something like what linguists call “complementary distribution”: when one is relevant, the other is not, since if we say that an algebra has some finite (length or depth) GK dimension, its corresponding BK dimension is necessarily zero, while if an algebra has positive BK dimension, its GK dimension is necessarily infinite. So for any algebra A with B-action, we really have two phenomena, length growth rate and depth growth rate, to describe in GK or BK terms as may be appropriate. (There is one case where we have to mention both the GK and the BK dimension: when the former is +∞ and the latter is 0, since in that case, neither determines the other.)

One minor embellishment to the definitions of the above BK dimensions might be useful. If the value of one of these dimensions is c ∈ [0, 1], Example 2.18 suggests that we should look at c/(1 − c) ∈ [0, +∞], since in that example, this recovers the dimension r of L. I suggest calling c/(1 − c) the renormalized BK dimension.

The reader interested in these dimension functions might now examine the various bounds we have obtained on growth rates in our results and examples, to see what statements about these dimensions they imply, and look for further results to complete our picture on how these dimensions can behave.

We remark that these dimension functions do not, in general, determine the corresponding growth rates of an algebra. For example, algebras with growth rates G(n^{d}) and G(n^{d} ln n) both have GK dimension d.

3.4. Growth of non-finitely-generated algebras. We have defined the above dimension functions in the case where the pair (A, B) is finitely generated (in the appropriate sense). In the non-finitely-generated case one can, as in the classical theory of Gel’fand–Kirillov dimension, define the value of each of these dimensions to be the supremum of its values over all finitely generated substructures of (A, B).

Note, however, that we cannot make similar definitions for our growth rate functions G^{length}(A), G^{length}(A, B), G^{depth}(A), G^{depth}(A, B), since an infinite chain of growth rates usually does not have a least upper bound. For instance, there is no least growth rate greater than the family of growth rates G(n^{d}) (d = 1, 2, …). Indeed, if f has greater growth rate than all these functions, then f([n^{1/2}]) (where brackets denote the “greatest integer” function) also grows faster than all these functions, but grows slower than f. If we want to extend the “growth rate” concept to infinitely generated algebras, the extended function should probably take values in some completion of the partially ordered set G(Φ) of growth rates of sequences.

4. The operad viewpoint

My original motivation for proving some of the results of Section 2 came out of a problem on how fast an algebra A with B-action could grow under some set of derived multilinear operations of its multiplication and the actions of the elements of B. I will say more about that problem in the next section; let us stop here and look at this concept of derived multilinear operation.

In General algebra (a.k.a. “Universal algebra”, but that name is out of favor with people in the field), if one is given a family of operations on a set (e.g., the operations comprising a structure of group), one can say, roughly, that one constructs derived operations (e.g., the binary and higher commutator operations, and the unary nth power operations) by repeatedly substituting various operations for the variables in other operations, and using arbitrary arrangements of variables, with repetitions allowed. A family of operations on a set which is closed under these constructions is called a clone of operations ([2], [7]).

When one considers the related situation of multilinear operations on a vector space, one can still substitute one such operation into another, and permute the variables, but one cannot repeat variables, since this generally results in operations that are not multilinear. In fact, whenever the base field is infinite, one can show that the only derived operations of a set of multilinear operations that are themselves multilinear are those obtained as in the following definition. (Over a finite field there are exceptions; in particular, the qth-power operation on an associative commutative k-algebra, where k is the field of q elements, is linear.)

Definition 4.1: Let A be a k-vector-space. A family B of multilinear maps y : A^{n(y)} → A (where each n(y) is a nonnegative integer, called the arity of y, and where a zeroary multilinear operation is understood to specify an element of A) will be called an operad of multilinear maps on A if the following conditions are satisfied:

(i) The unary identity map A → A belongs to B. (ii) If y ∈ B, n(y) = r, and y_{1}, …, y_{r} ∈ B, then the n(y_{1}) + ⋯ + n(y_{r})-ary

composite operation

A^{n(y_{1})+···+n(y_{r})} ⟶^{(y_{1},...,y_{r})} A^{r} →^{y} A

belongs to B. (Note that since some of the y_{i} may be zeroary, this composite may have arity less than that of y.)

(iii) If y ∈ B, and π is a permutation of {1, …, n(y)}, then the composite map

A^{n(y)} →^{π} A^{n(y)} →^{y} A also belongs to B.

(iv) For each n, the set of n-ary operations in B is closed under addition and

under multiplication by elements of k. The relation between the above definition and the definition of an operad given

in [9, (1.2.1)] is like that between the definitions of a group of permutations of a set, and of an abstract group. The abstract concept of operad is important for deeper study, but for our present purposes, the above “concrete” version suffices.

Note that in view of (iv), it would be most natural to consider an operad B of multilinear maps on A not as a set, but as a family of vector spaces, B_{0}, B_{1}, …, indexed by arity. Again, this is done in [9]; but to avoid setting up a language for graded vector spaces, we will here just speak of B as a set. Note, however, that in a graded-vector-space context, the analog, for an operad, of the (generally finite-dimensional) subspaces V ⊆ B of Sections 1 and 2 should be an appropriate graded subspace of B. But since we are not speaking of graded vectors spaces, we will break with Sections 1 and 2, and take our V ’s to be (generally finite) subsets of B, as in the next definition. In that definition, we will use the analog of the notational convention (1.2), namely, given a multilinear operation y on a vector space A, and subspaces U_{1}, …, U_{n(y)} of A, we define

y(U_{1}, …, U_{n(y)}) = span_{k}{y(x_{1}, …, x_{n(y)}) | x_{i} ∈ U_{i}} ⊆ A.

Definition 4.2: Let A be a k-vector-space, and B an operad of multilinear maps on A. Then given any subspace U ⊆ A, and any subset V ⊆ B containing the identity map of A, let us define k-subspaces U^{length,n,V} ⊆ A and U^{depth,n,V} ⊆ A (n = 1, 2, …) recursively, taking

U^{length,1,V} = U,
U^{depth,1,V} = U,

and for n > 1,

U^{length,n,V} = Σ_{y∈V, m(i)<n, Σm(i)≤n} y(U^{length,m(1),V} , …, U^{length,m(n(y)),V}),
U^{depth,n,V} = Σ_{y∈V} y(U^{depth,n−1,V} , …, U^{depth,n−1,V}) (n(y) arguments).

Most of Lemma 1.4 goes over essentially unchanged to this context. An adjustment is needed in the rightmost term of point (i) thereof: we have to assume there that the arities of elements of V are bounded by some integer b, and replace 2^{n−1} by b^{n−1}. Point (v) needs more adjustment: V′ ⊆ V^{length,r} makes sense and is the right hypothesis only in the case where all our operations are unary. In general, distinct hypotheses are appropriate for getting the indicated conclusions for G^{length} and G^{depth}, and we leave it to the interested reader to work these out; but it is easily verified that if V′ is a finite subset of the operad generated by V, then there exists some integer r such that both conclusions hold, and this gives us the analog of Corollary 1.5.

Thus, if B is a finitely generated operad of multilinear maps on a vector space A, and A is finitely generated under the action of these maps, we again get two growth rates which are invariants of the pair (A, B), which we will denote G^{length}(A, B) and G^{depth}(A, B). As in Lemma 1.7, we find that the first of these is at most exponential, and the second at most doubly exponential. (One again proves this by counting expressions for “monomials” in U^{length,n,V} and U^{depth,n,V}, and verifying that the lengths of such expressions can be bounded by linear and exponential functions of n, respectively. The reader thinking through this verification should note that it is most easily done by a direct induction; the alternative of looking for syntactic characterizations of such expressions, and then estimating their lengths, seems more difficult.)

These new growth functions are not merely analogs of our old ones, but subsume them as special cases:

Proposition 4.3: Let A be a (not necessarily associative) k-algebra and B an associative unital k-algebra, and assume a B-module structure is given on A, compatible with its k-vector-space structure.

Let Ā denote the underlying vector space of A, and B̄ the operad of multilinear operations on Ā generated by the bilinear multiplication of A, together with the linear operations on A given by the actions of the elements of B. Then

(i) A subspace U ⊆ A generates A as a k-algebra with B-module structure if and only if it generates Ā as a k-vector-space with action of the operad B̄.

(ii) If a subset V ⊆ B generates B as a unital k-algebra, then its image in the set of linear elements of B̄, together with the bilinear element coming from the multiplication of A, generate B̄ as an operad. (The converse can fail if A is not a faithful B-module.)

(iii) If A and B are each finitely generated in the above senses, so that, by the above observations, Ā and B̄ are as well, then

G^{length}(A, B) = G^{length}(Ā, B̄)  and  G^{depth}(A, B) = G^{depth}(Ā, B̄).

Thus, the growth rates G^{length}(A, B) and G^{depth}(A, B) are invariants of A not only as a k-algebra with B-module structure, but as a vector space with an operad of k-multilinear maps.

5. The source of these questions: an elusive chain condition

I will sketch below the considerations that led me to these growth-rate questions. Detailed formulations and arguments are given in [5, §65], except for the actual growth-rate computations; on that point, it is the preceding sections of this paper which have developed in detail some relevant results, of which only one was briefly sketched in [5].

If F is a free semigroup, it is known that a finitely generated subsemigroup S ⊆ F need not be finitely related. (For example, for S free on {x, y}, the subsemigroup generated by {x, xy, y^{2}, yx} is not.) Nevertheless, it can be proved that in this situation, if R is the set of all relations holding on some finite generating set for S, there is always a finite subset R_{0} ⊆ R which “implies” all the rest, in the sense that whenever the set of relations R_{0} holds in a family of elements of a free semigroup, the whole set of relations R holds there. This can be formalized as saying that any finitely generated subsemigroup of a free semigroup is finitely related within the quasivariety generated by all free semigroups; a slightly stronger version of this result is that in any free semigroup on finitely many generators, the class of congruences which are intersections of congruences induced by homomorphisms into free semigroups has ascending chain condition.

The truth of this last assertion is not hard to deduce from three observations:

(1) A free semigroup on finitely many generators can be embedded in the multiplicative semigroup of 2 × 2 matrices over a commutative ring. (For example, the two matrices x = ( \begin{matrix}1 & 2 \\ 0 & 1 \end{matrix} ) and y = ( \begin{matrix}1 & 0 \\ 2 & 1 \end{matrix} ) over Z generate a free semigroup.) (2) Any semigroup relation satisfied by a family of matrices is equivalent to a family of polynomial equations in their entries. (3) A polynomial ring in finitely many indeterminates over Z is Noetherian. (See [5, §65] for details, and references to related literature.)

Now from the example of a finitely generated subsemigroup of a free semigroup that is not finitely related, one gets, on forming semigroup algebras, an example of a finitely generated but non-finitely-related subalgebra of a free associative algebra. It is natural to ask whether the analog of the above positive result also holds for associative algebras; i.e., whether every free associative algebra on finitely many generators has ascending chain condition on ideals which are intersections of kernels of homomorphisms into free associative algebras.

Might such a result in fact be proved in a similar way, by embedding a free associative algebra in some associative algebra whose elements are determined by n-tuples (for some fixed n) of elements of an algebraic structure of another sort, such that finitely generated objects of that latter sort have ascending chain condition on congruences? (In [5], a precise formulation is given of the type of embedding in question.)

The first difficulty is to find the “other sort of algebra”. Results to the effect that the finitely generated algebras in a variety have ascending chain condition on congruences are not very numerous. Aside from the result about commutative rings, the one result I am aware of that concerns a variety with a rich enough structure to make the existence of the desired embedding plausible is for the variety of commutative differential algebras, that is, commutative associative kalgebras given with a single derivation d, equivalently, with a bialgebra action of k[L], where L is the 1-dimensional Lie algebra. If the field k has characteristic 0, the finitely generated algebras in this variety are known to have ascending chain condition on semiprime (= radical) d-invariant ideals ([14, Theorem in §I.12], [10, Theorem 7.1]), and this would be enough to prove our desired result on associative algebras, if we could get an appropriate representation of free associative algebras using commutative differential algebras.

However, my attempts to construct such representations failed, leading me to try to prove that no such representations existed. Assuming one had such a construction in which the k-vector-space structure of the constructed associative algebra F (A, d) was inherited from that of the given differential k-algebra (A, d), the multiplication of F (A, d) would have to be built out of derived multilinear operations of the multiplication of A and the derivation d. Assuming k not a finite field, these derived multilinear operations would lie in the operad generated by the multiplication and the derivation. But comparing the exponential length-growth-rate of a free associative algebra, noted in Example 1.8 above, with the lower length-growth-rates of associative commutative algebras with action of a finitedimensional Lie algebra, obtained in Theorem 2.10, and applying Proposition 4.3, one can conclude that such an embedding is not possible.

This argument in fact shows that one cannot get such embeddings even using generalized differential algebras, having a fixed finite-dimensional Lie algebra L of derivations. Using the depth growth rate and the bound of Theorem 2.8, instead of the length growth rate and Theorem 2.10, one can exclude a still larger class of possible representing varieties, including commutative algebras with action of any group of less than exponential growth. (It was the search for such a wider nonrepresentability result, which seemed empirically true, that led me to the concept of the depth growth rate.)

Embeddings of free associative algebras using commutative algebras A with actions of bialgebras of exponential growth, such as that of Example 1.9, seem not to be excluded by growth-rate considerations. Whether they exist, or are impossible for other reasons, I don’t know. If they do exist, then to use them, we would have to prove a chain condition for appropriate ideals of algebras with such action; but this seems unlikely to hold in most cases. In any case, the reader is welcome to try his or her hand at such approaches.

I will mention one other method of attack on the above question that occurred to me—also unsuccessful. A free associative algebra is known to be embeddable in a division algebra (cf. [8, p. 487]), so the kernel of a homomorphism into a free associative algebra is the kernel of a homomorphism into a division algebra. Is it possible that finitely generated free associative algebras (and hence all finitely generated associative algebras) have ascending chain condition on intersections of kernels of maps into division algebras?

Alas, no. The free group on two generators x and y has an infinite ascending chain of normal subgroups whose factor-groups are orderable groups ([3]). The group algebras of these factor-groups are therefore embeddable in division algebras ([8, Cor. 8.7.6]), and this yields an infinite ascending chain of ideals of the group algebra k < x, x^{−1}, y, y^{−1} > which are kernels of homomorphisms into division algebras.

References

[1] George M. Bergman, Everybody knows what a Hopf algebra is, in Group Actions on Rings (Proceedings of a Conference on Group Actions, Bowdoin College, Bowdoin, Maine, July 18–24, 1984) (S. Montgomery, ed.), Contemporary Mathematics 43 (1985), 25–48. MR 87e: 16024.

[2] George M. Bergman, An Invitation to General Algebra and Universal Constructions, Berkeley Mathematics Lecture Notes, #7, 1995.

[3] George M. Bergman, Chains of kernels of maps of orderable groups, unpublished note, 4 pp., 1996.

[4] George M. Bergman, Gel’fand–Kirillov dimensions of factor rings, Communications in Algebra 16 (1988), 2555–2567. MR 89g: 16033.

[5] George M. Bergman and Adam O. Hausknecht, Cogroups and Co-rings in Categories of Associative Rings, American Mathematical Society Mathematical Surveys and Monographs series, Volume 45, 1996.

[6] W. Borho and H. Kraft, Über die Gelfand–Kirillov Dimension, Mathematische Annalen 220 (1976), 1–24. MR 54#367.

[7] P. M. Cohn, Universal Algebra, second ed., Reidel, Dordrecht, 1981. MR 82j: 08001.

[8] P. M. Cohn, Free Rings and Their Relations, second ed., London Mathematical Society Monograph #19, Academic Press, New York, 1985. MR 87e: 16006.

[9] V. Ginzburg and M. Kapranov, Koszul duality for operads, Duke Mathematical Journal 76 (1994), 203–272. (Erratum regarding §2.2 at 80 (1995), p.90.) MR 96a: 18004.

[10] Irving Kaplansky, An Introduction to Differential Algebra, Publications de l’Institut de Mathématiques de l’Université de Nancago, Vol. V, Hermann, Paris, 1957, 1976. MR 20#177, 57#297.

[11] G. R. Krause and T. H. Lenagan, Growth of Algebras and Gelfand–Kirillov Dimension, Pitman Advanced Publishing Program, Research Notes in Mathematics #116, 1985. MR 86g: 16001.

[12] Jan Krempa and Jan Okniński, Gelfand–Kirillov dimensions of a tensor product, Mathematische Zeitschrift 194 (1987), 487–494. MR 88b: 16048.

[13] Susan Montgomery, Hopf Algebras and Their Actions on Rings, American Mathematical Society Regional Conference Series in Mathematics, No. 82 (1993). MR 94i: 16019.

[14] Joseph Fels Ritt, Differential Algebra, American Mathematical Society Colloquium Publication No. 33, 1950. MR 12, p. 7.

[15] M. M. Robinson, Partitions of large multipartites, American Journal of Mathematics 84 (1962), 16–34. MR 25 #3919.

[16] Martha K. Smith, Universal enveloping algebras with subexponential but not polynomially bounded growth, Proceedings of the American Mathematical Society 60 (1976), 22–24. MR 54 #7555.

[17] Moss E. Sweedler, Hopf Algebras, Mathematics Lecture Note Series, Benjamin, New York, 1969. MR 40 #5705.

[18] Robert B. Warfield, The Gelfand–Kirillov dimension of a tensor product, Mathematische Zeitschrift 185 (1984), 441–447. MR 85f: 17006.