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 |
[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 |
[a3] | J. Milnor, "A note on curvature and fundamental group" J. Diff. Geom. , 2 (1968) pp. 1–7 |
[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 |
[a5] | A. Shvarts, "A volume invariant of coverings" Dokl. Akad. Nauk SSSR , 105 (1955) pp. 32–34 (In Russian) |
[a6] | M. Gromov, "Groups of polynomial growth and expanding maps" Publ. Math. IHES , 53 (1981) pp. 53–73 |
[a7] | J. Tits, "Free subgroups in linear groups" J. of Algebra , 20 (1972) pp. 250–270 |
[a8] | J.A. Wolf, "Growth of finitely generated solvable groups and curvature of Riemannian manifolds" J. Diff. Geom. , 2 (1968) pp. 421–446 |
[a9] | J.W. Milnor, "Growth of finitely generated solvable groups" J. Diff. Geom. , 2 (1968) pp. 447–449 |
[a10] | M. Lazard, "Groupes analytiques ![]() |
[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 |
[a12] | H. Koch, "Galoissche Theorie der ![]() |
[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 |
[a15] | C. Löfwall, "On the subalgebra generated by one dimensional elements in the Yoneda Ext-algebra" , Preprint Dept. Math. , Univ. Stockholm (1976) |
[a16] | L. Avramov, "Local algebra and rational homotopy" Astérisque , 113–114 (1984) pp. 15–43 |
[a17] | L. Avramov, "Local rings of finite simplicial dimension" Bull. Amer. Math. Soc. , 10 (1984) pp. 289–291 |
Polynomial and exponential growth in groups and algebras. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Polynomial_and_exponential_growth_in_groups_and_algebras&oldid=14356