# Groups with a rational generating function for the word problem

This question comes more from curiosity than a specific research problem. Let G be a group and S a finite symmetric generating set. By the WP(G,S) I mean the set of all words in the free monoid on S mapping to the identity of G.

A classical result of Anissimov says that WP(G,S) is a regular language iff G is finite. Regular languages have rational generating functions, so I am asking:

Dooes rationality of the generating function of WP(G,S) imply G is finite?

I believe, but didn't check, that rationality doesn't depend on the choice do S.

I guess that my motivation is when is the generating function for probability of return to the origin at step n of a random walk rational?

-

I hope I'm also not misinterpreting the question, but it seems to me that the answer is yes. In fact the property of having a rational "walk generating function" characterizes finite graphs not only among Cayley graphs as in your question but also among the larger class of regular quasitransitive connected graphs (quasitransitive here means that the automorphism group acts with finitely many orbits). This is theorem 3.10 in "Counting Paths in Graphs" by L. Bartholdi, published in Enseign. Math. 45 (1999) 83-131. It is mentioned in the paper that the analogous question for arbitrary connected regular graphs is open.

-
This would seem to answer my question. Do you have a reference for the published version? –  Benjamin Steinberg Dec 23 '11 at 14:39
I edited that in the answer. –  Gjergji Zaimi Dec 23 '11 at 20:20
Thanks Gjergji. –  Benjamin Steinberg Dec 24 '11 at 18:57
I think the generating function that is rational for automatic groups is not the generating function being asked about here. For example $\mathbb{Z}$ is automatic with respect to the symmetric generating set $\\{ 1, -1 \\}$ but the word problem generating function is $\frac{1}{\sqrt{1 - 4x^2}}$. –  Qiaochu Yuan Oct 21 '11 at 18:16
@Igor: yes, you understood the question incorrectly. The question asks for the number of all monoid words (hence possibly with cancelation) of length $n$ in the symmetric generators of the group that are equal to 1 in the group. For example, for the free group, it is the number of Dyke words. In the case of $\mathbb{Z}$ it is the number of simple walks in $\mathbb{Z}$ that start and end at 0, i.e. the Catalan number. In both cases the generating function is not rational. I think the answer to the general question should be "no". –  Mark Sapir Oct 21 '11 at 19:58