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