OFFSET
0,2
COMMENTS
The process of expressing a word in generators as a sorted word in generators and commutators is Marshall Hall's 'collection process'.
Since this monoid 'lives in' a nilpotent group, it inherits the growth restriction of a nilpotent group. So according to a result of Bass, a(n) = O( n^8).
It seems this is the correct growth rate. This sequence may well have a rational generating function, though, according to a result of M Stoll, the growth function of a nilpotent group need not be rational, or even algebraic.
Computations on a free nilpotent group, or on submonoids, may be aided by using matricies. I. D. MacDonald describes how to do this in an American Mathematical Monthly article and he gives a recipe explicitly for the nil-2, 3 generator case.
LINKS
H. Bass, The degree of polynomial growth of finitely generated nilpotent groups, Proc. London Math. Soc. 25 (1972).
I. D. MacDonald, Commutators and Their Products, The American Mathematical Monthly, Vol. 93, No. 6, (Jun. - Jul., 1986), pp. 440-444.
Michael Stoll, Rational and transcendental growth series for the higher Heisenberg groups, Inventiones Mathematicae Volume 126, Number 1 / September, 1996.
EXAMPLE
Suppose the generators are a,b,c and their commutators are q,r,s, so:
ba = abq, ca = acr, cb = bcs;
nil-2 means that q,r,s commute with everything.
Now there are 81 different words of length 4 on a,b,c, but there are three equations:
abba = baab ( = aabbqq)
acca = caac ( = aaccrr)
bccb = cbbc ( = bbccss)
and these are the only equations, so instead of 81 distinct words we have 78 distinct words, a(4)=78.
CROSSREFS
KEYWORD
nonn,more
AUTHOR
David S. Newman and Moshe Shmuel Newman, May 29 2008
STATUS
approved