Namespaces
Variants
Actions

Difference between revisions of "Polynomial and exponential growth in groups and algebras"

From Encyclopedia of Mathematics
Jump to: navigation, search
m (MR/ZBL numbers added)
m (tex encoded by computer)
Line 1: Line 1:
Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p0737001.png" /> be a set of generators for a finitely-generated group <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p0737002.png" />. Consider <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p0737003.png" />. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p0737004.png" /> be the collection of all elements of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p0737005.png" /> which can be written as a word in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p0737006.png" /> of length <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p0737007.png" />, and let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p0737008.png" /> be the number of elements of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p0737009.png" />. The function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p07370010.png" /> is called the growth function of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p07370011.png" /> (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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p07370012.png" /> and relates this to group-theoretic properties of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p07370013.png" />.
+
<!--
 +
p0737001.png
 +
$#A+1 = 209 n = 2
 +
$#C+1 = 209 : ~/encyclopedia/old_files/data/P073/P.0703700 Polynomial and exponential growth in groups and algebras
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
  
Consider a non-negative function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p07370014.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p07370015.png" /> for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p07370016.png" />. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p07370017.png" /> be such "growth functions" . The function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p07370018.png" /> is of lesser growth than <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p07370019.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p07370020.png" />, if there exist a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p07370021.png" /> and an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p07370022.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p07370023.png" /> for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p07370024.png" />. Two growth functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p07370025.png" /> are of the same order of growth if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p07370026.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p07370027.png" />. The equivalence class of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p07370028.png" /> for this relation is denoted by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p07370029.png" /> and is called the growth of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p07370030.png" />. As in analytic function theory, one considers
+
{{TEX|auto}}
 +
{{TEX|done}}
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p07370031.png" /></td> </tr></table>
+
Let  $  S  ^  \prime  = \{ g _ {1} \dots g _ {n} \} $
 +
be a set of generators for a finitely-generated group  $  G $.
 +
Consider  $  S = \{ g _ {1} \dots g _ {n} , g _ {1}  ^ {-} 1 \dots g _ {n}  ^ {-} 1 \} $.
 +
Let  $  S  ^ {(} n) $
 +
be the collection of all elements of  $  G $
 +
which can be written as a word in  $  S $
 +
of length  $  \leq  n $,
 +
and let  $  f _ {G} ( n) = \# S  ^ {(} n) $
 +
be the number of elements of  $  S  ^ {(} n) $.
 +
The function  $  f _ {G} ( n) $
 +
is called the growth function of  $  G $(
 +
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  $  f _ {G} ( n) $
 +
and relates this to group-theoretic properties of  $  G $.
  
the order of growth of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p07370032.png" />, which only depends on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p07370033.png" />. The function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p07370034.png" /> 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p07370035.png" /> is of polynomial growth, or power growth, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p07370036.png" /> if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p07370037.png" />. Given that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p07370038.png" />, the polynomial growth power <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p07370039.png" /> is found from
+
Consider a non-negative function  $  f:  \mathbf N \rightarrow \mathbf R $,
 +
$  f( n) \geq  0 $
 +
for all  $  n $.  
 +
Let  $  f, g $
 +
be such "growth functions" . The function $  f $
 +
is of lesser growth than  $  g $,
 +
$  f < g $,
 +
if there exist a  $  c > 0 $
 +
and an  $  m \in \mathbf N = \{ 1, 2 ,\dots \} $
 +
such that $  f( n) \leq  cg( nm) $
 +
for all  $  n \in \mathbf N $.  
 +
Two growth functions  $  f, g $
 +
are of the same order of growth if $  f < g $
 +
and  $  g < f $.  
 +
The equivalence class of  $  f $
 +
for this relation is denoted by  $  [ f  ] $
 +
and is called the growth of  $  f $.  
 +
As in analytic function theory, one considers
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p07370040.png" /></td> </tr></table>
+
$$
 +
\rho ( f  )  = { {\lim\limits  \sup } } _ {n \rightarrow \infty } \
  
If the growth of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p07370041.png" /> satisfies the inequalities <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p07370042.png" /> for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p07370043.png" />, the function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p07370044.png" /> is said to be of intermediate growth.
+
\frac{ \mathop{\rm log}  \mathop{\rm log}  f( n) }{ \mathop{\rm log}  n }
 +
,
 +
$$
  
The growth function for a finitely-generated group was defined above. The growth of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p07370045.png" /> does not depend on the chosen system of generators and is hence an invariant of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p07370046.png" />. The growth of a finitely-generated free group on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p07370047.png" /> generators is exponential. A finitely-generated nilpotent group has polynomial growth.
+
the order of growth of  $  f $,
 +
which only depends on  $  [ f  ] $.  
 +
The function  $  n \mapsto 2  ^ {n} $
 +
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  $  f $
 +
is of polynomial growth, or power growth,  $  r $
 +
if  $  f \in [ n  ^ {r} ] $.  
 +
Given that  $  \rho ( f  ) = 0 $,
 +
the polynomial growth power  $  r $
 +
is found from
  
For an algebra <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p07370048.png" /> over a field <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p07370049.png" /> (associative, Lie, etc.) the definition is as follows.
+
$$
 +
r( ) =  {\lim\limits  \sup } _ {n \rightarrow \infty } \
  
Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p07370050.png" /> be a set of generators of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p07370051.png" /> over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p07370052.png" />, so that every <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p07370053.png" /> is a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p07370054.png" />-linear combination of monomials in the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p07370055.png" />. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p07370056.png" /> be the vector space spanned by the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p07370057.png" />. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p07370058.png" /> be the vector subspace of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p07370059.png" /> of all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p07370060.png" />-linear combinations of products <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p07370061.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p07370062.png" />. Then the function
+
\frac{ \mathop{\rm log}  f( n) }{ \mathop{\rm log}  n }
 +
.
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p07370063.png" /></td> </tr></table>
+
If the growth of  $  f $
 +
satisfies the inequalities  $  [ 2  ^ {n} ] > [ f  ] > [ n  ^ {r} ] $
 +
for all  $  r > 0 $,
 +
the function  $  f $
 +
is said to be of intermediate growth.
  
is the growth function of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p07370064.png" /> (with respect to the generating subspace <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p07370065.png" />). The growth of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p07370066.png" /> does not depend on the choice of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p07370067.png" />. The growth of the group algebra <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p07370068.png" /> is the growth of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p07370069.png" />.
+
The growth function for a finitely-generated group was defined above. The growth of $  [ f _ {G} ] $
 +
does not depend on the chosen system of generators and is hence an invariant of $  G $.  
 +
The growth of a finitely-generated free group on  $  \geq  2 $
 +
generators is exponential. A finitely-generated nilpotent group has polynomial growth.
  
If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p07370070.png" /> is a graded vector space, one defines the series
+
For an algebra  $  A $
 +
over a field  $  k $(
 +
associative, Lie, etc.) the definition is as follows.
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p07370071.png" /></td> </tr></table>
+
Let  $  a _ {1} \dots a _ {r} $
 +
be a set of generators of  $  A $
 +
over  $  k $,
 +
so that every  $  a \in A $
 +
is a  $  k $-
 +
linear combination of monomials in the  $  a _ {i} $.
 +
Let  $  V $
 +
be the vector space spanned by the  $  a _ {i} $.
 +
Let  $  V  ^ {k} $
 +
be the vector subspace of  $  A $
 +
of all  $  k $-
 +
linear combinations of products  $  v _ {1} \dots v _ {k} $,
 +
$  v _ {i} \in V $.
 +
Then the function
 +
 
 +
$$
 +
f _ {A} ( n)  = \sum _ { i= } 1 ^ { n }  \mathop{\rm dim}  V  ^ {i}
 +
$$
 +
 
 +
is the growth function of  $  A $(
 +
with respect to the generating subspace  $  V $).
 +
The growth of  $  f _ {A} $
 +
does not depend on the choice of  $  V $.
 +
The growth of the group algebra  $  k[ G] $
 +
is the growth of  $  G $.
 +
 
 +
If  $  W = \oplus _ {n=} 0  ^  \infty  W  ^ {n} $
 +
is a graded vector space, one defines the series
 +
 
 +
$$
 +
h _ {W} ( z)  = \sum _ { n= } 0 ^  \infty 
 +
\mathop{\rm dim} ( W  ^ {n} ) z  ^ {n} .
 +
$$
  
 
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
 
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
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p07370072.png" /></td> </tr></table>
+
$$
 +
g _ {W} ( n)  = \sum _ { i= } 0 ^ { n }
 +
\mathop{\rm dim} ( W  ^ {i} ).
 +
$$
  
If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p07370073.png" /> 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.
+
If $  A = \oplus _ {n=} 0 ^  \infty  A  ^ {(} n) $
 +
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p07370074.png" /> be a finite oriented graph, possibly with loops and multiple edges. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p07370075.png" /> be the number of paths of length <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p07370076.png" />. Then the Poincaré series of the graph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p07370077.png" /> is
+
For graphs one also defines a growth function. Let $  G = ( V, E) $
 +
be a finite oriented graph, possibly with loops and multiple edges. Let $  c _ {G} ( m) $
 +
be the number of paths of length $  m $.  
 +
Then the Poincaré series of the graph $  G $
 +
is
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p07370078.png" /></td> </tr></table>
+
$$
 +
P _ {G} ( z)  = \sum _ { m= } 0 ^  \infty  c _ {G} ( m) z  ^ {m} ,
 +
$$
  
and the growth function of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p07370079.png" /> is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p07370080.png" />. Here a path of length <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p07370081.png" /> is a sequence of vertices and edges <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p07370082.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p07370083.png" /> goes from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p07370084.png" /> to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p07370085.png" />.
+
and the growth function of $  G $
 +
is $  f _ {G} ( m) = \sum _ {i=} 0 ^ {m} c _ {G} ( m) $.  
 +
Here a path of length $  m $
 +
is a sequence of vertices and edges $  v _ {1} e _ {1} v _ {2} \dots e _ {m-} 1 v _ {m} $
 +
such that $  e _ {i} $
 +
goes from $  v _ {i} $
 +
to $  v _ {i+} 1 $.
  
 
There are two central questions concerning Poincaré series and growth functions.
 
There are two central questions concerning Poincaré series and growth functions.
Line 45: Line 153:
 
A positive answer to i) (in the graded case) implies a positive answer to ii).
 
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p07370086.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p07370087.png" />, the reciprocal polynomial to the minimal polynomial <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p07370088.png" /> of the incidence matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p07370089.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p07370090.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p07370091.png" /> is the number of edges from vertex <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p07370092.png" /> to vertex <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p07370093.png" />. In particular, the growth of a graph is either polynomial or exponential, [[#References|[a13]]].
+
The Poincaré series of a graph is a rational function of the form $  P _ {G} ( z) = q( z) p( z)  ^ {-} 1 $
 +
with $  p( z) = 1- a _ {1} z - \dots - a _ {n} z  ^ {n} $,  
 +
the reciprocal polynomial to the minimal polynomial $  m( z) = z  ^ {n} - a _ {1} z  ^ {n-} 1 - \dots - a _ {n} $
 +
of the incidence matrix $  B $
 +
of $  G $,  
 +
where $  b _ {ij} $
 +
is the number of edges from vertex $  i $
 +
to vertex $  j $.  
 +
In particular, the growth of a graph is either polynomial or exponential, [[#References|[a13]]].
  
There are many algebras for which the associated growth functions and Poincaré series have been considered. For instance, for a local ring, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p07370094.png" />, the Poincaré series of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p07370095.png" />, cf. [[Local ring|Local ring]]. For an associative nilpotent ring over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p07370096.png" /> one considers the graded algebra <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p07370097.png" />, the Yoneda <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p07370099.png" />-algebra, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700100.png" /> is the algebra over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700101.png" /> obtained by adjoining a unit. For a local ring <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700102.png" /> one also considers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700103.png" />, where now <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700104.png" /> is the residue field of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700105.png" />. In topology one consider the graded algebra of the homology (or cohomology) of the loop space <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700106.png" /> of a space <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700107.png" />. 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 many algebras for which the associated growth functions and Poincaré series have been considered. For instance, for a local ring, $  ( A, m) $,  
 +
the Poincaré series of $  \oplus m  ^ {i} / m  ^ {i+} 1 $,  
 +
cf. [[Local ring|Local ring]]. For an associative nilpotent ring over $  k $
 +
one considers the graded algebra $  \mathop{\rm Ext} _ {\widetilde{N}  }  {}  ^ {*} ( k , k) $,  
 +
the Yoneda $  \mathop{\rm Ext} $-
 +
algebra, where $  \widetilde{N}  = N \oplus k $
 +
is the algebra over $  k $
 +
obtained by adjoining a unit. For a local ring $  R $
 +
one also considers $  \mathop{\rm Ext} _ {R}  ^ {*} ( k, k) $,  
 +
where now $  k $
 +
is the residue field of $  R $.  
 +
In topology one consider the graded algebra of the homology (or cohomology) of the loop space $  \Omega X $
 +
of a space $  X $.  
 +
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. [[#References|[a1]]], [[#References|[a13]]]–[[#References|[a15]]].
 
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. [[#References|[a1]]], [[#References|[a13]]]–[[#References|[a15]]].
  
The growth problem for commutative local rings is settled by the following result. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700108.png" /> be a local ring and consider its Betti numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700109.png" />, i.e. the coefficients of its Poincaré series. Then there are two possibilities, [[#References|[a16]]]: either <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700110.png" /> is a polynomial in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700111.png" />, which happens if and only if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700112.png" /> is a complete intersection, or there exist integers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700113.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700114.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700115.png" /> for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700116.png" />. 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700117.png" />. Indeed one has, [[#References|[a16]]], [[#References|[a17]]], that the radius of convergence is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700118.png" /> if and only if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700119.png" /> is regular (cf. [[Local ring|Local ring]]), that it is precisely 1 if and only if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700120.png" /> is an irregular complete intersection and that it is strictly between 0 and 1 otherwise.
+
The growth problem for commutative local rings is settled by the following result. Let $  ( R, \mathfrak m ) $
 +
be a local ring and consider its Betti numbers $  b _ {i} ( R) = \mathop{\rm dim} _ {k} (  \mathop{\rm Ext} _ {R}  ^ {i} ( k, k)) = \mathop{\rm dim} _ {k}  \mathop{\rm Tor} _ {i}  ^ {R} ( k, k) $,  
 +
i.e. the coefficients of its Poincaré series. Then there are two possibilities, [[#References|[a16]]]: either $  b _ {i} $
 +
is a polynomial in $  i $,  
 +
which happens if and only if $  R $
 +
is a complete intersection, or there exist integers $  N $
 +
and  $  d > c > 1 $
 +
such that $  c  ^ {i} < b _ {i} < d  ^ {i} $
 +
for all $  i \geq  N $.  
 +
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 $  \geq  1 $.  
 +
Indeed one has, [[#References|[a16]]], [[#References|[a17]]], that the radius of convergence is $  \infty $
 +
if and only if $  R $
 +
is regular (cf. [[Local ring|Local ring]]), that it is precisely 1 if and only if $  R $
 +
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700121.png" /> of codimension <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700122.png" /> determined by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700123.png" /> equations. In algebraic terms this can be described as follows.
+
The concept of a complete intersection local ring corresponds to a complete intersection in algebraic geometry, i.e. varieties in $  \mathbf P  ^ {N} $
 +
of codimension $  i $
 +
determined by $  i $
 +
equations. In algebraic terms this can be described as follows.
  
Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700124.png" /> be a commutative Noetherian local ring, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700125.png" /> (sometimes called the embedding dimension of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700126.png" />). Choose a basis for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700127.png" /> and consider the corresponding [[Koszul complex|Koszul complex]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700128.png" />. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700129.png" />. The local ring <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700130.png" /> is a complete intersection if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700131.png" />. A Noetherian local ring is a complete intersection if and only if its completion <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700132.png" /> is a complete intersection, and this is the case if and only if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700133.png" /> is a quotient of a complete regular local ring <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700134.png" /> by an ideal generated by a regular <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700135.png" />-sequence (cf. [[Koszul complex|Koszul complex]]). For commutative Noetherian local rings one has the chain of implications: regular <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700136.png" /> complete intersection <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700137.png" /> Gorenstein <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700138.png" /> Cohen–Macaulay. Cf. also [[Gorenstein ring|Gorenstein ring]] and [[Cohen–Macaulay ring|Cohen–Macaulay ring]].
+
Let $  ( R, \mathfrak m ) $
 +
be a commutative Noetherian local ring, $  n = \mathop{\rm dim} _ {k}  \mathfrak m / \mathfrak m  ^ {2} $(
 +
sometimes called the embedding dimension of $  R $).  
 +
Choose a basis for $  \mathfrak m / \mathfrak m  ^ {2} $
 +
and consider the corresponding [[Koszul complex|Koszul complex]] $  E _ {*} $.  
 +
Let $  \epsilon _ {j} = \mathop{\rm dim} _ {k}  H _ {j} ( E _ {*} ) $.  
 +
The local ring $  ( R, \mathfrak m ) $
 +
is a complete intersection if $  e _ {1} = n-  \mathop{\rm dim}  R $.  
 +
A Noetherian local ring is a complete intersection if and only if its completion $  ( \widehat{R}  , \widehat{ {\mathfrak m }}  ) $
 +
is a complete intersection, and this is the case if and only if $  \widehat{R}  $
 +
is a quotient of a complete regular local ring $  \widetilde{R}  $
 +
by an ideal generated by a regular $  \widetilde{R}  $-
 +
sequence (cf. [[Koszul complex|Koszul complex]]). For commutative Noetherian local rings one has the chain of implications: regular $  \Rightarrow $
 +
complete intersection $  \Rightarrow $
 +
Gorenstein $  \Rightarrow $
 +
Cohen–Macaulay. Cf. also [[Gorenstein ring|Gorenstein ring]] and [[Cohen–Macaulay ring|Cohen–Macaulay ring]].
  
 
Cf. [[#References|[a1]]] for a recent survey concerning these and other results on growth and rationality for algebras and spaces.
 
Cf. [[#References|[a1]]] for a recent survey concerning these and other results on growth and rationality for algebras and spaces.
Line 69: Line 229:
 
Tits' theorem: A finitely-generated subgroup of a connected Lie group has either exponential growth or is almost nilpotent (and hence has polynomial growth), [[#References|[a7]]].
 
Tits' theorem: A finitely-generated subgroup of a connected Lie group has either exponential growth or is almost nilpotent (and hence has polynomial growth), [[#References|[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, [[#References|[a5]]]. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700139.png" /> be a connected compact manifold with fundamental group <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700140.png" />. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700141.png" /> be the universal covering space of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700142.png" />. Give <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700143.png" /> a Riemannian metric <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700144.png" /> and consider the induced metric <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700145.png" /> on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700146.png" />. (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700147.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700148.png" /> are locally the same.) Take an arbitrary point <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700149.png" /> and let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700150.png" /> be the volume of the ball of radius <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700151.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700152.png" /> with centre <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700153.png" />. The growth of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700154.png" /> does not depend on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700155.png" /> or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700156.png" /> and is hence an invariant of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700157.png" />. It is called the volume invariant, [[#References|[a4]]]. The Shvarts theorem now says that the volume invariant of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700158.png" /> is the growth of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700159.png" />.
+
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, [[#References|[a5]]]. Let $  M $
 +
be a connected compact manifold with fundamental group $  G = \pi _ {1} ( M) $.  
 +
Let $  \widetilde{M}  $
 +
be the universal covering space of $  M $.  
 +
Give $  M $
 +
a Riemannian metric $  g $
 +
and consider the induced metric $  \widetilde{g}  $
 +
on $  \widetilde{M}  $.  
 +
( $  M $
 +
and $  \widetilde{M}  $
 +
are locally the same.) Take an arbitrary point $  \widetilde{p}  \in \widetilde{M}  $
 +
and let $  v( s) $
 +
be the volume of the ball of radius $  s $
 +
in $  \widetilde{M}  $
 +
with centre $  \widetilde{p}  $.  
 +
The growth of $  v $
 +
does not depend on $  g $
 +
or $  \widetilde{p}  $
 +
and is hence an invariant of $  M $.  
 +
It is called the volume invariant, [[#References|[a4]]]. The Shvarts theorem now says that the volume invariant of $  M $
 +
is the growth of $  \pi _ {1} ( M) $.
  
A mapping <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700160.png" /> from a metric space <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700161.png" /> to another <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700162.png" /> is called globally expanding if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700163.png" /> for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700164.png" />. It is called locally expanding, or just expanding, if each point has an open neighbourhood on which <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700165.png" /> is globally expanding. The mapping <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700166.png" /> 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. [[#References|[a6]]].
+
A mapping $  \phi $
 +
from a metric space $  ( M, d) $
 +
to another $  ( M  ^  \prime  , d  ^  \prime  ) $
 +
is called globally expanding if $  d  ^  \prime  ( \phi ( x), \phi ( y)) > d( x, y) $
 +
for all $  x \neq y $.  
 +
It is called locally expanding, or just expanding, if each point has an open neighbourhood on which $  \phi $
 +
is globally expanding. The mapping $  z \mapsto z  ^ {2} $
 +
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. [[#References|[a6]]].
  
The Milnor fundamental group growth theorems are the following, [[#References|[a3]]]. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700167.png" /> is a complete <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700168.png" />-dimensional Riemannian manifold with an everywhere positive semi-definite mean curvature tensor <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700169.png" />, then the growth of every finitely-generated subgroup of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700170.png" /> is polynomial. On the other hand, if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700171.png" /> is a compact Riemannian manifold with all sectional curvatures less than zero, then the fundamental group is of exponential growth.
+
The Milnor fundamental group growth theorems are the following, [[#References|[a3]]]. If $  M $
 +
is a complete $  n $-
 +
dimensional Riemannian manifold with an everywhere positive semi-definite mean curvature tensor $  R _ {ij} $,  
 +
then the growth of every finitely-generated subgroup of $  \pi _ {1} ( M) $
 +
is polynomial. On the other hand, if $  M $
 +
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|Class field theory]] and [[Tower of fields|Tower of fields]]. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700172.png" /> be a group and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700173.png" /> the field of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700174.png" /> elements, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700175.png" /> a prime number. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700176.png" /> be the group algebra of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700177.png" /> over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700178.png" /> and let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700179.png" /> be the augmentation ideal of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700180.png" />, i.e. the ideal generated by the elements <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700181.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700182.png" />. The Zassenhaus filtration is the sequence of characteristic subgroups <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700183.png" />. The sequence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700184.png" /> is also called the lower <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700186.png" />-central series of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700187.png" />. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700188.png" /> be the associated graded ring defined by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700189.png" />, i.e.
+
One application of growth theory was to the class field tower problem, cf. [[Class field theory|Class field theory]] and [[Tower of fields|Tower of fields]]. Let $  G $
 +
be a group and $  \mathbf F _ {p} $
 +
the field of p $
 +
elements, p $
 +
a prime number. Let $  A = \mathbf F _ {p} [ G] $
 +
be the group algebra of $  G $
 +
over $  \mathbf F _ {p} $
 +
and let $  \mathfrak a $
 +
be the augmentation ideal of $  A $,  
 +
i.e. the ideal generated by the elements $  g- 1 \in R $,  
 +
$  g \in G $.  
 +
The Zassenhaus filtration is the sequence of characteristic subgroups $  G _ {n} = \{ {g \in G } : {g- 1 \in \mathfrak a  ^ {n} } \} $.  
 +
The sequence $  \{ G _ {n} \} $
 +
is also called the lower p $-
 +
central series of $  G $.  
 +
Let $  \widehat{A}  $
 +
be the associated graded ring defined by $  \mathfrak a $,  
 +
i.e.
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700190.png" /></td> </tr></table>
+
$$
 +
\widehat{A}  = \oplus _ { n= } 0 ^  \infty  {\widehat{A}  } _ {n} ,\ \
 +
{\widehat{A}  } _ {n}  = \mathfrak a  ^ {n} / \mathfrak a  ^ {n+} 1 .
 +
$$
  
Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700191.png" /> be the associated Hilbert series
+
Let $  f _ {G} ( z) $
 +
be the associated Hilbert series
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700192.png" /></td> </tr></table>
+
$$
 +
f _ {G} ( z)  = \sum _ { n= } 0 ^  \infty 
 +
\mathop{\rm dim} ( {\widehat{A}  } _ {n} ) z  ^ {n} ,
 +
$$
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700193.png" /> and it is assumed that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700194.png" />, which is guaranteed if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700195.png" />. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700196.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700197.png" /> is a free group on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700198.png" /> generators, and let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700199.png" /> be a set of defining words for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700200.png" />. For each <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700201.png" />, let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700202.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700203.png" /> is the Zassenhaus filtration of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700204.png" />. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700205.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700206.png" />. Then the Golod–Shafarevich theorem says: 1) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700207.png" />; and 2) if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700208.png" /> for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700209.png" />, then the algebra <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700210.png" /> is infinite dimensional, [[#References|[a11]]], [[#References|[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.
+
where $  \mathop{\rm dim} = \mathop{\rm dim} _ {\mathbf F _ {p}  } $
 +
and it is assumed that $  \mathop{\rm dim}  {\widehat{A}  } _ {n} < \infty $,  
 +
which is guaranteed if $  \mathop{\rm dim}  {\widehat{A}  } _ {1} < \infty $.  
 +
Let $  G = F/R $,  
 +
where $  F $
 +
is a free group on $  d \geq  2 $
 +
generators, and let $  S $
 +
be a set of defining words for $  G $.  
 +
For each $  s \in S $,  
 +
let $  d ( s) = \sup \{ {n } : {s \in F _ {n} } \} $,  
 +
where $  F _ {n} $
 +
is the Zassenhaus filtration of $  F $.  
 +
Let $  l _ {n} = \# \{ {s \in S } : {d( s) = n } \} $,  
 +
$  l _ {0} = 1 $.  
 +
Then the Golod–Shafarevich theorem says: 1) $  \mathop{\rm dim}  {\widehat{A}  } _ {n} \geq  d(  \mathop{\rm dim} ( {\widehat{A}  } _ {n-} 1 )) - \sum _ {k=} 0 ^ {n-} 1 l _ {n-} k $;  
 +
and 2) if $  l _ {n} \leq  ( d- 1)  ^ {2} /4 $
 +
for all $  n $,  
 +
then the algebra $  A $
 +
is infinite dimensional, [[#References|[a11]]], [[#References|[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 [[#References|[a10]]], which provides a criterion for the analyticity of a pro-<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700211.png" />-group in terms of the Hilbert series of the associated algebra.
+
Still another application is Lazard's theorem [[#References|[a10]]], which provides a criterion for the analyticity of a pro- p $-
 +
group in terms of the Hilbert series of the associated algebra.
  
 
====References====
 
====References====
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top"> 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 {{MR|0842162}} {{ZBL|0607.55007}} </TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top"> 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 {{MR|712546}} {{ZBL|}} </TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top"> J. Milnor, "A note on curvature and fundamental group" ''J. Diff. Geom.'' , '''2''' (1968) pp. 1–7 {{MR|0232311}} {{ZBL|0162.25401}} </TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top"> 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 {{MR|}} {{ZBL|0152.39201}} </TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top"> A. Shvarts, "A volume invariant of coverings" ''Dokl. Akad. Nauk SSSR'' , '''105''' (1955) pp. 32–34 (In Russian) {{MR|}} {{ZBL|0066.15903}} </TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top"> M. Gromov, "Groups of polynomial growth and expanding maps" ''Publ. Math. IHES'' , '''53''' (1981) pp. 53–73 {{MR|0623535}} {{MR|0623534}} {{ZBL|0474.20018}} </TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top"> J. Tits, "Free subgroups in linear groups" ''J. of Algebra'' , '''20''' (1972) pp. 250–270 {{MR|0286898}} {{ZBL|0257.20031}} {{ZBL|0236.20032}} </TD></TR><TR><TD valign="top">[a8]</TD> <TD valign="top"> J.A. Wolf, "Growth of finitely generated solvable groups and curvature of Riemannian manifolds" ''J. Diff. Geom.'' , '''2''' (1968) pp. 421–446 {{MR|}} {{ZBL|0207.51803}} </TD></TR><TR><TD valign="top">[a9]</TD> <TD valign="top"> J.W. Milnor, "Growth of finitely generated solvable groups" ''J. Diff. Geom.'' , '''2''' (1968) pp. 447–449 {{MR|0244899}} {{ZBL|0176.29803}} </TD></TR><TR><TD valign="top">[a10]</TD> <TD valign="top"> M. Lazard, "Groupes analytiques <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700212.png" />-adiques" ''Publ. Math. IHES'' , '''26''' (1965) pp. 389–603 {{MR|209286}} {{ZBL|}} </TD></TR><TR><TD valign="top">[a11]</TD> <TD valign="top"> 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 {{MR|}} {{ZBL|0148.28101}} </TD></TR><TR><TD valign="top">[a12]</TD> <TD valign="top"> H. Koch, "Galoissche Theorie der <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700213.png" />-Erweiterungen" , Deutsch. Verlag Wissenschaft. (1970)</TD></TR><TR><TD valign="top">[a13]</TD> <TD valign="top"> 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</TD></TR><TR><TD valign="top">[a14]</TD> <TD valign="top"> 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 {{MR|563510}} {{ZBL|0415.13012}} </TD></TR><TR><TD valign="top">[a15]</TD> <TD valign="top"> C. Löfwall, "On the subalgebra generated by one dimensional elements in the Yoneda Ext-algebra" , ''Preprint Dept. Math.'' , Univ. Stockholm (1976) {{MR|}} {{ZBL|0429.13008}} </TD></TR><TR><TD valign="top">[a16]</TD> <TD valign="top"> L. Avramov, "Local algebra and rational homotopy" ''Astérisque'' , '''113–114''' (1984) pp. 15–43 {{MR|0749041}} {{ZBL|0552.13003}} </TD></TR><TR><TD valign="top">[a17]</TD> <TD valign="top"> L. Avramov, "Local rings of finite simplicial dimension" ''Bull. Amer. Math. Soc.'' , '''10''' (1984) pp. 289–291 {{MR|0733698}} {{ZBL|0552.13005}} </TD></TR></table>
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top"> 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 {{MR|0842162}} {{ZBL|0607.55007}} </TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top"> 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 {{MR|712546}} {{ZBL|}} </TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top"> J. Milnor, "A note on curvature and fundamental group" ''J. Diff. Geom.'' , '''2''' (1968) pp. 1–7 {{MR|0232311}} {{ZBL|0162.25401}} </TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top"> 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 {{MR|}} {{ZBL|0152.39201}} </TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top"> A. Shvarts, "A volume invariant of coverings" ''Dokl. Akad. Nauk SSSR'' , '''105''' (1955) pp. 32–34 (In Russian) {{MR|}} {{ZBL|0066.15903}} </TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top"> M. Gromov, "Groups of polynomial growth and expanding maps" ''Publ. Math. IHES'' , '''53''' (1981) pp. 53–73 {{MR|0623535}} {{MR|0623534}} {{ZBL|0474.20018}} </TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top"> J. Tits, "Free subgroups in linear groups" ''J. of Algebra'' , '''20''' (1972) pp. 250–270 {{MR|0286898}} {{ZBL|0257.20031}} {{ZBL|0236.20032}} </TD></TR><TR><TD valign="top">[a8]</TD> <TD valign="top"> J.A. Wolf, "Growth of finitely generated solvable groups and curvature of Riemannian manifolds" ''J. Diff. Geom.'' , '''2''' (1968) pp. 421–446 {{MR|}} {{ZBL|0207.51803}} </TD></TR><TR><TD valign="top">[a9]</TD> <TD valign="top"> J.W. Milnor, "Growth of finitely generated solvable groups" ''J. Diff. Geom.'' , '''2''' (1968) pp. 447–449 {{MR|0244899}} {{ZBL|0176.29803}} </TD></TR><TR><TD valign="top">[a10]</TD> <TD valign="top"> M. Lazard, "Groupes analytiques <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700212.png" />-adiques" ''Publ. Math. IHES'' , '''26''' (1965) pp. 389–603 {{MR|209286}} {{ZBL|}} </TD></TR><TR><TD valign="top">[a11]</TD> <TD valign="top"> 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 {{MR|}} {{ZBL|0148.28101}} </TD></TR><TR><TD valign="top">[a12]</TD> <TD valign="top"> H. Koch, "Galoissche Theorie der <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073700/p073700213.png" />-Erweiterungen" , Deutsch. Verlag Wissenschaft. (1970)</TD></TR><TR><TD valign="top">[a13]</TD> <TD valign="top"> 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</TD></TR><TR><TD valign="top">[a14]</TD> <TD valign="top"> 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 {{MR|563510}} {{ZBL|0415.13012}} </TD></TR><TR><TD valign="top">[a15]</TD> <TD valign="top"> C. Löfwall, "On the subalgebra generated by one dimensional elements in the Yoneda Ext-algebra" , ''Preprint Dept. Math.'' , Univ. Stockholm (1976) {{MR|}} {{ZBL|0429.13008}} </TD></TR><TR><TD valign="top">[a16]</TD> <TD valign="top"> L. Avramov, "Local algebra and rational homotopy" ''Astérisque'' , '''113–114''' (1984) pp. 15–43 {{MR|0749041}} {{ZBL|0552.13003}} </TD></TR><TR><TD valign="top">[a17]</TD> <TD valign="top"> L. Avramov, "Local rings of finite simplicial dimension" ''Bull. Amer. Math. Soc.'' , '''10''' (1984) pp. 289–291 {{MR|0733698}} {{ZBL|0552.13005}} </TD></TR></table>

Revision as of 08:06, 6 June 2020


Let $ S ^ \prime = \{ g _ {1} \dots g _ {n} \} $ be a set of generators for a finitely-generated group $ G $. Consider $ S = \{ g _ {1} \dots g _ {n} , g _ {1} ^ {-} 1 \dots g _ {n} ^ {-} 1 \} $. Let $ S ^ {(} n) $ be the collection of all elements of $ G $ which can be written as a word in $ S $ of length $ \leq n $, and let $ f _ {G} ( n) = \# S ^ {(} n) $ be the number of elements of $ S ^ {(} n) $. The function $ f _ {G} ( n) $ is called the growth function of $ G $( 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 $ f _ {G} ( n) $ and relates this to group-theoretic properties of $ G $.

Consider a non-negative function $ f: \mathbf N \rightarrow \mathbf R $, $ f( n) \geq 0 $ for all $ n $. Let $ f, g $ be such "growth functions" . The function $ f $ is of lesser growth than $ g $, $ f < g $, if there exist a $ c > 0 $ and an $ m \in \mathbf N = \{ 1, 2 ,\dots \} $ such that $ f( n) \leq cg( nm) $ for all $ n \in \mathbf N $. Two growth functions $ f, g $ are of the same order of growth if $ f < g $ and $ g < f $. The equivalence class of $ f $ for this relation is denoted by $ [ f ] $ and is called the growth of $ f $. As in analytic function theory, one considers

$$ \rho ( f ) = { {\lim\limits \sup } } _ {n \rightarrow \infty } \ \frac{ \mathop{\rm log} \mathop{\rm log} f( n) }{ \mathop{\rm log} n } , $$

the order of growth of $ f $, which only depends on $ [ f ] $. The function $ n \mapsto 2 ^ {n} $ 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 $ f $ is of polynomial growth, or power growth, $ r $ if $ f \in [ n ^ {r} ] $. Given that $ \rho ( f ) = 0 $, the polynomial growth power $ r $ is found from

$$ r( f ) = {\lim\limits \sup } _ {n \rightarrow \infty } \ \frac{ \mathop{\rm log} f( n) }{ \mathop{\rm log} n } . $$

If the growth of $ f $ satisfies the inequalities $ [ 2 ^ {n} ] > [ f ] > [ n ^ {r} ] $ for all $ r > 0 $, the function $ f $ is said to be of intermediate growth.

The growth function for a finitely-generated group was defined above. The growth of $ [ f _ {G} ] $ does not depend on the chosen system of generators and is hence an invariant of $ G $. The growth of a finitely-generated free group on $ \geq 2 $ generators is exponential. A finitely-generated nilpotent group has polynomial growth.

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

Let $ a _ {1} \dots a _ {r} $ be a set of generators of $ A $ over $ k $, so that every $ a \in A $ is a $ k $- linear combination of monomials in the $ a _ {i} $. Let $ V $ be the vector space spanned by the $ a _ {i} $. Let $ V ^ {k} $ be the vector subspace of $ A $ of all $ k $- linear combinations of products $ v _ {1} \dots v _ {k} $, $ v _ {i} \in V $. Then the function

$$ f _ {A} ( n) = \sum _ { i= } 1 ^ { n } \mathop{\rm dim} V ^ {i} $$

is the growth function of $ A $( with respect to the generating subspace $ V $). The growth of $ f _ {A} $ does not depend on the choice of $ V $. The growth of the group algebra $ k[ G] $ is the growth of $ G $.

If $ W = \oplus _ {n=} 0 ^ \infty W ^ {n} $ is a graded vector space, one defines the series

$$ h _ {W} ( z) = \sum _ { n= } 0 ^ \infty \mathop{\rm dim} ( W ^ {n} ) z ^ {n} . $$

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

$$ g _ {W} ( n) = \sum _ { i= } 0 ^ { n } \mathop{\rm dim} ( W ^ {i} ). $$

If $ A = \oplus _ {n=} 0 ^ \infty A ^ {(} n) $ 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 $ G = ( V, E) $ be a finite oriented graph, possibly with loops and multiple edges. Let $ c _ {G} ( m) $ be the number of paths of length $ m $. Then the Poincaré series of the graph $ G $ is

$$ P _ {G} ( z) = \sum _ { m= } 0 ^ \infty c _ {G} ( m) z ^ {m} , $$

and the growth function of $ G $ is $ f _ {G} ( m) = \sum _ {i=} 0 ^ {m} c _ {G} ( m) $. Here a path of length $ m $ is a sequence of vertices and edges $ v _ {1} e _ {1} v _ {2} \dots e _ {m-} 1 v _ {m} $ such that $ e _ {i} $ goes from $ v _ {i} $ to $ v _ {i+} 1 $.

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 $ P _ {G} ( z) = q( z) p( z) ^ {-} 1 $ with $ p( z) = 1- a _ {1} z - \dots - a _ {n} z ^ {n} $, the reciprocal polynomial to the minimal polynomial $ m( z) = z ^ {n} - a _ {1} z ^ {n-} 1 - \dots - a _ {n} $ of the incidence matrix $ B $ of $ G $, where $ b _ {ij} $ is the number of edges from vertex $ i $ to vertex $ j $. 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, $ ( A, m) $, the Poincaré series of $ \oplus m ^ {i} / m ^ {i+} 1 $, cf. Local ring. For an associative nilpotent ring over $ k $ one considers the graded algebra $ \mathop{\rm Ext} _ {\widetilde{N} } {} ^ {*} ( k , k) $, the Yoneda $ \mathop{\rm Ext} $- algebra, where $ \widetilde{N} = N \oplus k $ is the algebra over $ k $ obtained by adjoining a unit. For a local ring $ R $ one also considers $ \mathop{\rm Ext} _ {R} ^ {*} ( k, k) $, where now $ k $ is the residue field of $ R $. In topology one consider the graded algebra of the homology (or cohomology) of the loop space $ \Omega X $ of a space $ X $. 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 $ ( R, \mathfrak m ) $ be a local ring and consider its Betti numbers $ b _ {i} ( R) = \mathop{\rm dim} _ {k} ( \mathop{\rm Ext} _ {R} ^ {i} ( k, k)) = \mathop{\rm dim} _ {k} \mathop{\rm Tor} _ {i} ^ {R} ( k, k) $, i.e. the coefficients of its Poincaré series. Then there are two possibilities, [a16]: either $ b _ {i} $ is a polynomial in $ i $, which happens if and only if $ R $ is a complete intersection, or there exist integers $ N $ and $ d > c > 1 $ such that $ c ^ {i} < b _ {i} < d ^ {i} $ for all $ i \geq N $. 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 $ \geq 1 $. Indeed one has, [a16], [a17], that the radius of convergence is $ \infty $ if and only if $ R $ is regular (cf. Local ring), that it is precisely 1 if and only if $ R $ 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 $ \mathbf P ^ {N} $ of codimension $ i $ determined by $ i $ equations. In algebraic terms this can be described as follows.

Let $ ( R, \mathfrak m ) $ be a commutative Noetherian local ring, $ n = \mathop{\rm dim} _ {k} \mathfrak m / \mathfrak m ^ {2} $( sometimes called the embedding dimension of $ R $). Choose a basis for $ \mathfrak m / \mathfrak m ^ {2} $ and consider the corresponding Koszul complex $ E _ {*} $. Let $ \epsilon _ {j} = \mathop{\rm dim} _ {k} H _ {j} ( E _ {*} ) $. The local ring $ ( R, \mathfrak m ) $ is a complete intersection if $ e _ {1} = n- \mathop{\rm dim} R $. A Noetherian local ring is a complete intersection if and only if its completion $ ( \widehat{R} , \widehat{ {\mathfrak m }} ) $ is a complete intersection, and this is the case if and only if $ \widehat{R} $ is a quotient of a complete regular local ring $ \widetilde{R} $ by an ideal generated by a regular $ \widetilde{R} $- sequence (cf. Koszul complex). For commutative Noetherian local rings one has the chain of implications: regular $ \Rightarrow $ complete intersection $ \Rightarrow $ Gorenstein $ \Rightarrow $ 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 $ M $ be a connected compact manifold with fundamental group $ G = \pi _ {1} ( M) $. Let $ \widetilde{M} $ be the universal covering space of $ M $. Give $ M $ a Riemannian metric $ g $ and consider the induced metric $ \widetilde{g} $ on $ \widetilde{M} $. ( $ M $ and $ \widetilde{M} $ are locally the same.) Take an arbitrary point $ \widetilde{p} \in \widetilde{M} $ and let $ v( s) $ be the volume of the ball of radius $ s $ in $ \widetilde{M} $ with centre $ \widetilde{p} $. The growth of $ v $ does not depend on $ g $ or $ \widetilde{p} $ and is hence an invariant of $ M $. It is called the volume invariant, [a4]. The Shvarts theorem now says that the volume invariant of $ M $ is the growth of $ \pi _ {1} ( M) $.

A mapping $ \phi $ from a metric space $ ( M, d) $ to another $ ( M ^ \prime , d ^ \prime ) $ is called globally expanding if $ d ^ \prime ( \phi ( x), \phi ( y)) > d( x, y) $ for all $ x \neq y $. It is called locally expanding, or just expanding, if each point has an open neighbourhood on which $ \phi $ is globally expanding. The mapping $ z \mapsto z ^ {2} $ 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 $ M $ is a complete $ n $- dimensional Riemannian manifold with an everywhere positive semi-definite mean curvature tensor $ R _ {ij} $, then the growth of every finitely-generated subgroup of $ \pi _ {1} ( M) $ is polynomial. On the other hand, if $ M $ 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 $ G $ be a group and $ \mathbf F _ {p} $ the field of $ p $ elements, $ p $ a prime number. Let $ A = \mathbf F _ {p} [ G] $ be the group algebra of $ G $ over $ \mathbf F _ {p} $ and let $ \mathfrak a $ be the augmentation ideal of $ A $, i.e. the ideal generated by the elements $ g- 1 \in R $, $ g \in G $. The Zassenhaus filtration is the sequence of characteristic subgroups $ G _ {n} = \{ {g \in G } : {g- 1 \in \mathfrak a ^ {n} } \} $. The sequence $ \{ G _ {n} \} $ is also called the lower $ p $- central series of $ G $. Let $ \widehat{A} $ be the associated graded ring defined by $ \mathfrak a $, i.e.

$$ \widehat{A} = \oplus _ { n= } 0 ^ \infty {\widehat{A} } _ {n} ,\ \ {\widehat{A} } _ {n} = \mathfrak a ^ {n} / \mathfrak a ^ {n+} 1 . $$

Let $ f _ {G} ( z) $ be the associated Hilbert series

$$ f _ {G} ( z) = \sum _ { n= } 0 ^ \infty \mathop{\rm dim} ( {\widehat{A} } _ {n} ) z ^ {n} , $$

where $ \mathop{\rm dim} = \mathop{\rm dim} _ {\mathbf F _ {p} } $ and it is assumed that $ \mathop{\rm dim} {\widehat{A} } _ {n} < \infty $, which is guaranteed if $ \mathop{\rm dim} {\widehat{A} } _ {1} < \infty $. Let $ G = F/R $, where $ F $ is a free group on $ d \geq 2 $ generators, and let $ S $ be a set of defining words for $ G $. For each $ s \in S $, let $ d ( s) = \sup \{ {n } : {s \in F _ {n} } \} $, where $ F _ {n} $ is the Zassenhaus filtration of $ F $. Let $ l _ {n} = \# \{ {s \in S } : {d( s) = n } \} $, $ l _ {0} = 1 $. Then the Golod–Shafarevich theorem says: 1) $ \mathop{\rm dim} {\widehat{A} } _ {n} \geq d( \mathop{\rm dim} ( {\widehat{A} } _ {n-} 1 )) - \sum _ {k=} 0 ^ {n-} 1 l _ {n-} k $; and 2) if $ l _ {n} \leq ( d- 1) ^ {2} /4 $ for all $ n $, then the algebra $ A $ 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- $ p $- 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
How to Cite This Entry:
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=23927