cp's OEIS Frontend

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

%I A140348 #14 Jan 31 2018 18:10:19
%S A140348 1,3,9,27,78,216,568,1410,3309,7307,15303
%N A140348 Growth function for the submonoid generated by the generators of the free nil-2 group on three generators.
%C A140348 The process of expressing a word in generators as a sorted word in generators and commutators is Marshall Hall's 'collection process'.
%C A140348 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).
%C A140348 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.
%C A140348 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.
%H A140348 H. Bass, <a href="https://doi.org/10.1112/plms/s3-25.4.603">The degree of polynomial growth of finitely generated nilpotent groups</a>, Proc. London Math. Soc. 25 (1972).
%H A140348 I. D. MacDonald, <a href="http://www.jstor.org/stable/2323464">Commutators and Their Products</a>, The American Mathematical Monthly, Vol. 93, No. 6, (Jun. - Jul., 1986), pp. 440-444.
%H A140348 Michael Stoll, <a href="https://doi.org/10.1007/s002220050090">Rational and transcendental growth series for the higher Heisenberg groups</a>, Inventiones Mathematicae Volume 126, Number 1 / September, 1996.
%e A140348 Suppose the generators are a,b,c and their commutators are q,r,s, so:
%e A140348 ba = abq, ca = acr, cb = bcs;
%e A140348 nil-2 means that q,r,s commute with everything.
%e A140348 Now there are 81 different words of length 4 on a,b,c, but there are three equations:
%e A140348 abba = baab ( = aabbqq)
%e A140348 acca = caac ( = aaccrr)
%e A140348 bccb = cbbc ( = bbccss)
%e A140348 and these are the only equations, so instead of 81 distinct words we have 78 distinct words, a(4)=78.
%Y A140348 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.
%K A140348 nonn,more
%O A140348 0,2
%A A140348 _David S. Newman_ and _Moshe Shmuel Newman_, May 29 2008