# Random walks on Coxeter groups

Let $G_N$ be the group generated by elements $a_1,\ldots,a_N$ subject to the relations $a_i^2=1$ and $(a_ia_j)^3=1$. The growth function of $G_N$ is then $$f_N(t)=\frac{1+2t+2t^2+t^3}{1-Mt-Mt^2+\frac{M(M+1)}{2}t^3}$$ where $M=N-2$ (or at least, this seems to be the correct generalization of the $N=4,5$ known formulae, A154638 and A162740 @ OEIS). Question now: is the random walk function $$g_N(t)=\sum_{k=0}^\infty Card(i_1,\ldots,i_k|a_{i_1}\ldots a_{i_k}=1)\cdot t^k$$ known? Maybe related to $f_N$? I'd be actually interested in the $N\to\infty$ behavior of $g_N$.

-

## 2 Answers

For the case $N=3$, this is the random walk on the honeycomb lattice:

Lemma 2.1 in this paper computes the number of walks of length $2n$ on the honeycomb lattice which return to the origin, so $$g_3(t)=\sum_{n=0}^{\infty}\sum_{k=0}^n \binom{2k}{k}\binom{n}{k}^2 t^{2n}.$$

-

Not an answer, but too long for a comment. There is actually a general recipe for computing the growth function of any Coxeter group (which implies, in particular, that it is always a rational function). I haven't done the calculation, but your purported calculation of the growth function for the Coxeter group you wrote down can be derived from this (assuming that it is true).

This is very old stuff. It appears as an exercise in Bourbaki's book "Groups et algebres de Lie"; see exercises 15-26 of Section 4.1. The details of these exercises appear in the paper

MR1170370 (93g:20081) Paris, Luis(CH-GENV-SM) Growth series of Coxeter groups. Group theory from a geometrical viewpoint (Trieste, 1990), 302–310, World Sci. Publ., River Edge, NJ, 1991.

The book this paper appears in is extremely hard to track down; as far as I can tell, it is not available anywhere at any price. It contains a number of important papers in geometric group theory, so I scanned it a long time ago. I just posted a scan of the above paper here.

-
@Teo Banica : I don't know whether anyone has looked at the $N \rightarrow \infty$ behavior. My knowledge of this area comes via geometric group theory, where for a while there was a cottage industry proving that growth series for various kinds of group were rational or irrational (see the intro of my paper "The rationality of sol manifolds" from math.rice.edu/~andyp/papers for a bibliography). However, I'm not aware of a large literature for the sorts of finer questions you ask. – Andy Putman Nov 24 '12 at 16:18