Random walks on Coxeter groups - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T16:15:44Z http://mathoverflow.net/feeds/question/114205 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/114205/random-walks-on-coxeter-groups Random walks on Coxeter groups Teo B 2012-11-23T02:08:44Z 2012-11-24T19:05:49Z <p>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$.</p> http://mathoverflow.net/questions/114205/random-walks-on-coxeter-groups/114311#114311 Answer by Andy Putman for Random walks on Coxeter groups Andy Putman 2012-11-24T04:12:21Z 2012-11-24T04:12:21Z <p>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).</p> <p>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</p> <p>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.</p> <p>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 <a href="http://www.math.rice.edu/~andyp/ParisCoxeter.djvu" rel="nofollow">here</a>.</p> http://mathoverflow.net/questions/114205/random-walks-on-coxeter-groups/114364#114364 Answer by Agol for Random walks on Coxeter groups Agol 2012-11-24T19:05:49Z 2012-11-24T19:05:49Z <p>For the case $N=3$, this is the random walk on the honeycomb lattice: <img src="http://euler.slu.edu/escher/upload/thumb/a/a8/Honeycomb.svg/292px-Honeycomb.svg.png" alt="alt text"></p> <p>Lemma 2.1 in <a href="http://www.jstor.org/stable/2684723?origin=crossref" rel="nofollow">this paper</a> 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}.$$ </p>