MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
up vote 8 down vote accepted

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.

share|cite|improve this answer
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

Maybe I don't understand the question, but automatic groups have rational growth functions, and are frequently infinite. I believe that it is not known whether or not automaticity depends on the choice of generating set. For more info, see Cannon, Epstein, Thurston, Holt, Levy "Word processing on groups", or several papers of Jim Cannon and/or Bill Floyd. EDIT As many have pointed out I did not, in fact, understand the question. There is a related conjecture of Sarnak, to the effect that the spectral gap of the associated operator on surface groups is algebraic (which could be strengthened to conjecture that the function you are interested is algebraic). The function is known for free groups (Harry Kesten's thesis), but, as far as I know, it is not known for too many other groups.

share|cite|improve this answer
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
Btw, if the auto attic structure of an automatic group is not the language of geodesics (like in the hyperbolic case) then the growth generating function need not be rational as far as I can see. – Benjamin Steinberg Oct 22 '11 at 4:33
Igor: For groups automaticity is independent of generating set. – Derek Holt Oct 22 '11 at 12:00
For free groups the word problem is a context-free language and so has an algebraic generating function by Schutzenberger-Chomsky theorem. Of course the Kesten viewpoint is different and earlier. – Benjamin Steinberg Oct 22 '11 at 14:06

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.