[math-fun] No. of words of length n in certain group
To Math Fun, Seq Fan: I ran into my distinguished (former) colleague Colin Mallows yesterday, and he said that it would be nice if someone would extend his sequence A154638. Take the infinite reflection group with 5 generators S_1, ..., S_5, satisfying (S_i)^2 = (S_i S_j)^3 = I, and let a(n) be number of distinct elements whose minimal representation as a product of generators has length n: 1, 5, 20, 70, 240, 780, 2730, .. (for n>= 0) Can anybody help extend this sequence? Is there a generating function? What about other groups? This might be a gaping hole in the OEIS! There must be a huge literature on this problem. The books that I know about that might be related, Lyndom & Schupp, Combinatorial Group Theory, Magnus, Karrass, Solitar, same title, Johnson, Presentations of Groups, aren't exactly full of sequences, as far as I can tell. Can some expert please help? Neil
There's a handy program (or rather, a constellation of programs) kbmag by Derek Holt et al., which can be used as a package within GAP or as a free-standing program, to try to find an automatic structure for a group. I entered this presentation, and it produced an automatic structure, which implies the growth function is rational, (1 + 2*X + 2*X^2 + X^3)/(1 - 3*X - 3*X^2 + 6*X^3) as reported by kbgrowth. The first 20 coefficients are {1, 5, 20, 70, 240, 810, 2730, 9180, 30870, 103770, 348840, 1172610, 3941730, 13249980, 44539470, 149717970, 503272440, 1691734410, 5686712730, 19115706780, 64256852070} Bill Thurston On Nov 21, 2009, at 10:11 PM, N. J. A. Sloane wrote:
To Math Fun, Seq Fan:
I ran into my distinguished (former) colleague Colin Mallows yesterday, and he said that it would be nice if someone would extend his sequence A154638.
Take the infinite reflection group with 5 generators S_1, ..., S_5, satisfying (S_i)^2 = (S_i S_j)^3 = I, and let a(n) be number of distinct elements whose minimal representation as a product of generators has length n:
1, 5, 20, 70, 240, 780, 2730, .. (for n>= 0)
Can anybody help extend this sequence? Is there a generating function? What about other groups? This might be a gaping hole in the OEIS! There must be a huge literature on this problem.
The books that I know about that might be related, Lyndom & Schupp, Combinatorial Group Theory, Magnus, Karrass, Solitar, same title, Johnson, Presentations of Groups, aren't exactly full of sequences, as far as I can tell.
Can some expert please help?
Neil
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
On Nov 22, 2009, at 10:13 AM, Bill Thurston wrote:
What about other groups? This might be a gaping hole in the OEIS! There must be a huge literature on this problem.
I should have addressed this in my previous message. You're right, there is a substantial literature about growth functions, going back many years, but I'm not very current with it. It would be good to get some of these growth functions into the OEIS. I believe some of the earliest cases studied were reflection groups, where perhaps Serre showed many have rational growth functions. Jim Cannon, Bill Floyd, Matt Grayson and others had a further wave of results of groups that sometimes unexpectedly have rational growth functions, and somtimes unexpected coincidences in growth functions: there is a way to choose generators for alternating knot groups (=the fundamental group of its complement) so the growth function only depends on the number of crossings. The theory of automatic groups was developed to give a framework for some of these ideas about growth. An automatic group is one that can be navigated using finite state automata, working in ways akin to those used by regular expression analyzers such as grep. Our book "Word Processing in Groups" gave a systematic development of the theory of automatic groups, and computer programs were developed, first "automata" and then "kbmag" to actually compute finite state automata to describe and navigate many infinite groups. The easiest case is word hyperbolic groups, which Cannon showed have rational growth functions with respect to an arbitrary finite set of generators and are automatic. There are many groups that are automatic but not word hyperbolic. In these cases, the growth function might not be rational for every choice of generators. The braid groups (which I showed) and the mapping class groups (Lee Mosher) are interesting groups that are automatic but not word hyperbolic. There are groups with rational growth functions that are not automatic, such as the Fibonacci polycyclic extension < a, b, c: Cac = b, Cbc = ab >, where capitalization represents inverse (Matt Grayson). There are groups of intermediate growth, slower than exponential but faster than any polynomial, and a body of literature about these --- these of course can't have rational growth functions. Of course, a group has an unsolvable word problem <==> its growth function is non-recursive. There's a lot more known ... Bill
participants (2)
-
Bill Thurston -
N. J. A. Sloane