A140348 Growth function for the submonoid generated by the generators of the free nil-2 group on three generators.

1, 3, 9, 27, 78, 216, 568, 1410, 3309, 7307, 15303

Offset: 0

Author

David S. Newman and Moshe Shmuel Newman, May 29 2008

Keywords

• nonn
• more

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.

Examples

			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.
		

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.

Crossrefs

Cf. sequence A000125 gives the analogous count for the 2 generator case. sequence A077028 refines A000125 by giving the number of words with k a's and (n-k)b's.