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

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$.

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

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

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}.$$

share|cite|improve this answer

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.

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

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.