Polynomial and exponential growth in groups and algebras

Let be a set of generators for a finitely-generated group . Consider . Let be the collection of all elements of which can be written as a word in of length , and let be the number of elements of . The function is called the growth function of (with respect to the chosen generators). A similar definition can be given for algebras, cf. below. The subject of growth functions for algebras and groups studies the order of growth of functions like and relates this to group-theoretic properties of .

Consider a non-negative function , for all . Let be such "growth functions" . The function is of lesser growth than , , if there exist a and an such that for all . Two growth functions are of the same order of growth if and . The equivalence class of for this relation is denoted by and is called the growth of . As in analytic function theory, one considers

the order of growth of , which only depends on . The function has order of growth 1, or exponential growth. This is the highest that is of interest (and can occur) in the present context. A function is of polynomial growth, or power growth, if . Given that , the polynomial growth power is found from

If the growth of satisfies the inequalities for all , the function is said to be of intermediate growth.

The growth function for a finitely-generated group was defined above. The growth of does not depend on the chosen system of generators and is hence an invariant of . The growth of a finitely-generated free group on generators is exponential. A finitely-generated nilpotent group has polynomial growth.

For an algebra over a field (associative, Lie, etc.) the definition is as follows.

Let be a set of generators of over , so that every is a -linear combination of monomials in the . Let be the vector space spanned by the . Let be the vector subspace of of all -linear combinations of products , . Then the function

is the growth function of (with respect to the generating subspace ). The growth of does not depend on the choice of . The growth of the group algebra is the growth of .

If is a graded vector space, one defines the series

This series is called the Hilbert series, Poincaré series, Hilbert–Poincaré series, or Poincaré–Betti series, depending on the context. There is an associated growth function

If is a finitely-generated graded algebra, then the growth function coming from the grading and any growth function defined by a finite-dimensional generating vector space have the same growth.

For graphs one also defines a growth function. Let be a finite oriented graph, possibly with loops and multiple edges. Let be the number of paths of length . Then the Poincaré series of the graph is

and the growth function of is . Here a path of length is a sequence of vertices and edges such that goes from to .

There are two central questions concerning Poincaré series and growth functions.

i) In the graded case: Is the Poincaré series rational?

ii) In all cases: Is it true for a suitable class of algebras or groups that all objects either have polynomial or exponential growth?

A positive answer to i) (in the graded case) implies a positive answer to ii).

The Poincaré series of a graph is a rational function of the form with , the reciprocal polynomial to the minimal polynomial of the incidence matrix of , where is the number of edges from vertex to vertex . In particular, the growth of a graph is either polynomial or exponential, [a13].

There are many algebras for which the associated growth functions and Poincaré series have been considered. For instance, for a local ring, , the Poincaré series of , cf. Local ring. For an associative nilpotent ring over one considers the graded algebra , the Yoneda -algebra, where is the algebra over obtained by adjoining a unit. For a local ring one also considers , where now is the residue field of . In topology one consider the graded algebra of the homology (or cohomology) of the loop space of a space . In all these cases there are relations (established or conjectured) between the properties of the Poincaré series (such as rationality, rate of convergence, etc.) and properties of the algebras or topological spaces involved.

There are a variety of constructions associating graphs to algebras, spaces to algebras, algebras to spaces, algebras to graphs, and corresponding relations between the associated growth functions and Poincaré series, cf. [a1], [a13]–[a15].

The growth problem for commutative local rings is settled by the following result. Let be a local ring and consider its Betti numbers , i.e. the coefficients of its Poincaré series. Then there are two possibilities, [a16]: either is a polynomial in , which happens if and only if is a complete intersection, or there exist integers and such that for all . This implies immediately a positive solution to the Golod–Gulliksen conjecture, which stated that a local ring is a complete intersection if and only if the radius of convergence of its Poincaré series is . Indeed one has, [a16], [a17], that the radius of convergence is if and only if is regular (cf. Local ring), that it is precisely 1 if and only if is an irregular complete intersection and that it is strictly between 0 and 1 otherwise.

The concept of a complete intersection local ring corresponds to a complete intersection in algebraic geometry, i.e. varieties in of codimension determined by equations. In algebraic terms this can be described as follows.

Let be a commutative Noetherian local ring, (sometimes called the embedding dimension of ). Choose a basis for and consider the corresponding Koszul complex . Let . The local ring is a complete intersection if . A Noetherian local ring is a complete intersection if and only if its completion is a complete intersection, and this is the case if and only if is a quotient of a complete regular local ring by an ideal generated by a regular -sequence (cf. Koszul complex). For commutative Noetherian local rings one has the chain of implications: regular complete intersection Gorenstein Cohen–Macaulay. Cf. also Gorenstein ring and Cohen–Macaulay ring.

Cf. [a1] for a recent survey concerning these and other results on growth and rationality for algebras and spaces.

For groups there are, among others, the following theorems.

The Milnor–Wolf theorem: A finitely-generated solvable group is either of polynomial growth or of exponential growth. In the first case it is polycyclic and almost nilpotent (i.e. has a nilpotent subgroup of finite index), [a8], [a9].

The Gromov–Milnor theorem: A finitely-generated group is of polynomial growth if and only if it is almost nilpotent, [a9], [a6].

There are groups of intermediate growth [a2].

Tits' theorem: A finitely-generated subgroup of a connected Lie group has either exponential growth or is almost nilpotent (and hence has polynomial growth), [a7].

There are relations between the geometry of manifolds and the growth of its fundamental group. Probably the oldest one is due to A.S. Shvarts, [a5]. Let be a connected compact manifold with fundamental group . Let be the universal covering space of . Give a Riemannian metric and consider the induced metric on . ( and are locally the same.) Take an arbitrary point and let be the volume of the ball of radius in with centre . The growth of does not depend on or and is hence an invariant of . It is called the volume invariant, [a4]. The Shvarts theorem now says that the volume invariant of is the growth of .

A mapping from a metric space to another is called globally expanding if for all . It is called locally expanding, or just expanding, if each point has an open neighbourhood on which is globally expanding. The mapping from the circle into itself is locally expanding (but not globally). Franks' polynomial growth theorem says that if a compact manifold admits an expanding self-mapping, then its fundamental group is of polynomial growth, cf. [a6].

The Milnor fundamental group growth theorems are the following, [a3]. If is a complete -dimensional Riemannian manifold with an everywhere positive semi-definite mean curvature tensor , then the growth of every finitely-generated subgroup of is polynomial. On the other hand, if is a compact Riemannian manifold with all sectional curvatures less than zero, then the fundamental group is of exponential growth.

One application of growth theory was to the class field tower problem, cf. Class field theory and Tower of fields. Let be a group and the field of elements, a prime number. Let be the group algebra of over and let be the augmentation ideal of , i.e. the ideal generated by the elements , . The Zassenhaus filtration is the sequence of characteristic subgroups . The sequence is also called the lower -central series of . Let be the associated graded ring defined by , i.e.

Let be the associated Hilbert series

where and it is assumed that , which is guaranteed if . Let , where is a free group on generators, and let be a set of defining words for . For each , let , where is the Zassenhaus filtration of . Let , . Then the Golod–Shafarevich theorem says: 1) ; and 2) if for all , then the algebra is infinite dimensional, [a11], [a12]. This theorem was a main ingredient in the negative solution of the class field tower problem; that is, in the construction of infinite class field towers.

Still another application is Lazard's theorem [a10], which provides a criterion for the analyticity of a pro--group in terms of the Hilbert series of the associated algebra.

References

[a1]	I.K. Babenko, "Problems of growth and rationality in algebra and topology" Russian Math. Surv. , 41 : 2 (1986) pp. 117–175 Uspekhi Mat. Nauk , 41 : 2 (1986) pp. 95–142 MR0842162 Zbl 0607.55007
[a2]	R.I. Grigorchuk, "On Milnor's problem of group growth" Soviet Math. Dokl. , 28 (1983) pp. 23–26 Dokl. Akad. Nauk SSSR , 271 (1983) pp. 30–33 MR712546
[a3]	J. Milnor, "A note on curvature and fundamental group" J. Diff. Geom. , 2 (1968) pp. 1–7 MR0232311 Zbl 0162.25401
[a4]	V. Efremovich, "On proximity geometry of Riemannian manifolds" Transl. Amer. Math. Soc. (2) , 39 (1964) pp. 167–170 Uspekhi Mat. Nauk , 8 (1953) pp. 189–191 Zbl 0152.39201
[a5]	A. Shvarts, "A volume invariant of coverings" Dokl. Akad. Nauk SSSR , 105 (1955) pp. 32–34 (In Russian) Zbl 0066.15903
[a6]	M. Gromov, "Groups of polynomial growth and expanding maps" Publ. Math. IHES , 53 (1981) pp. 53–73 MR0623535 MR0623534 Zbl 0474.20018
[a7]	J. Tits, "Free subgroups in linear groups" J. of Algebra , 20 (1972) pp. 250–270 MR0286898 Zbl 0257.20031 Zbl 0236.20032
[a8]	J.A. Wolf, "Growth of finitely generated solvable groups and curvature of Riemannian manifolds" J. Diff. Geom. , 2 (1968) pp. 421–446 Zbl 0207.51803
[a9]	J.W. Milnor, "Growth of finitely generated solvable groups" J. Diff. Geom. , 2 (1968) pp. 447–449 MR0244899 Zbl 0176.29803
[a10]	M. Lazard, "Groupes analytiques -adiques" Publ. Math. IHES , 26 (1965) pp. 389–603 MR209286
[a11]	E.S. Golod, I.R. Shafarevich, "On class field towers" Transl. Amer. Math. Soc. (2) , 48 (1965) pp. 91–102 Izv. Akad. Nauk SSSR Ser. Mat. , 28 (1964) pp. 261–272 Zbl 0148.28101
[a12]	H. Koch, "Galoissche Theorie der -Erweiterungen" , Deutsch. Verlag Wissenschaft. (1970)
[a13]	V.A. Ufnarovskii, "A criterion for the growth of graphs and algebras defined by words" Math. Notes , 31 (1982) pp. 238–241 Mat. Zametki , 31 (1982) pp. 465–472
[a14]	J.-E. Roos, "Relations between the Poincaré–Betti series of loop spaces and of local rings" M.P. Malliavin (ed.) , Sem. Alg. P. Dubreil , Lect. notes in math. , 740 , Springer (1979) pp. 285–322 MR563510 Zbl 0415.13012
[a15]	C. Löfwall, "On the subalgebra generated by one dimensional elements in the Yoneda Ext-algebra" , Preprint Dept. Math. , Univ. Stockholm (1976) Zbl 0429.13008
[a16]	L. Avramov, "Local algebra and rational homotopy" Astérisque , 113–114 (1984) pp. 15–43 MR0749041 Zbl 0552.13003
[a17]	L. Avramov, "Local rings of finite simplicial dimension" Bull. Amer. Math. Soc. , 10 (1984) pp. 289–291 MR0733698 Zbl 0552.13005