15
$\begingroup$

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?

Improve this question
$\endgroup$
0

2 Answers 2

Reset to default
8
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ This would seem to answer my question. Do you have a reference for the published version? $\endgroup$
    – Benjamin Steinberg
    Dec 23, 2011 at 14:39
  • $\begingroup$ I edited that in the answer. $\endgroup$
    – Gjergji Zaimi
    Dec 23, 2011 at 20:20
2
$\begingroup$

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.

Improve this answer
$\endgroup$
10
  • 3
    $\begingroup$ 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}}$. $\endgroup$
    – Qiaochu Yuan
    Oct 21, 2011 at 18:16
  • 2
    $\begingroup$ @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". $\endgroup$
    – user6976
    Oct 21, 2011 at 19:58
  • 1
    $\begingroup$ 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. $\endgroup$
    – Benjamin Steinberg
    Oct 22, 2011 at 4:33
  • 2
    $\begingroup$ Igor: For groups automaticity is independent of generating set. $\endgroup$
    – Derek Holt
    Oct 22, 2011 at 12:00
  • 1
    $\begingroup$ 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. $\endgroup$
    – Benjamin Steinberg
    Oct 22, 2011 at 14:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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