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,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

Table of n, a(n) for n=0..10.

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

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.

Sequence in context: A269488 A027027 A361845 * A139561 A152169 A370142

Adjacent sequences: A140345 A140346 A140347 * A140349 A140350 A140351

Keyword

nonn,more

Author

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

Status

approved