Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Let $F_m$ be the free group with $m$ generators $S:=\{x_1,\dots, x_m\}$. I am interested in the following quantity $$ F(n):=\frac{|\{w\in [F_m:F_m]: \|w\|_S\leq n\}|}{|B_S(n)|} $$ where $B_S(n):=\{w\in F_m: \|w\|_S\leq n\}$ and $\|w\|_S$ is the word metric of $w$, and $[F_m,F_m]$ is the commutator subgroup of $F_m$. Do we know how $F(n)$ growth as a function of $n$? Presumably this a classic problem in group theory.

I would be thankful if you please mention a reference that consider this function.

share|improve this question
    
I imagine that this ratio should tend to one since the number of words of length $n$ on the quotient ${\mathbb Z}^n$ must tend to infinity much slower than the number $B_S(n)$. –  Venkataramana Jan 22 '13 at 7:21
    
I meant the quotient ${\mathbb Z}^m$. –  Venkataramana Jan 22 '13 at 7:23
    
This seems like something you could analyze as a random walk: to generate a word of length $n$, take a random walk on the lattice $\mathbb{Z}^m$, where you're not allowed to reverse the last step you made. Then $F(n)$ is the probability you end up at the origin after $n$ steps (well, it's almost that: $F(n)$ also includes words of length less than $n$). –  Eric Wofsey Jan 22 '13 at 7:39
    
@Eric: Your analysis seems right to me. -- As the simple random walk on $\mathbb{Z}^m$ is recurrent if and only if $m \leq 2$, this means that $\sum_{n = 1}^\infty F(n)$ diverges if and only if $m \leq 2$ -- correct? –  Stefan Kohl Jan 22 '13 at 9:10
3  
it looks very similar to the probability of return of the random walk on, so the probability of return should be in $n^{-m/2}$. There are a lot of paper on probabilities of return of random walk on f.g. groups, including those by Pittet and Saloff-Coste. –  YCor Jan 22 '13 at 10:30

1 Answer 1

up vote 11 down vote accepted

The question is indeed very close to the one about the return probabilities on the abelian group $\mathbb Z^m$. Still, as Benjamin has noticed, there is some difference, since here one has to consider the non-backtracking paths only.

There is a standard way to deal with it which is based on the so-called random walks with internal degrees of freedom (also known under numerous other names). In this concrete context this is the Markov chain on the product of the free group $F_m$ by the set $A$ of generators and their inverses with the transition probabilities $$ p( (g,a), (ga',a') ) = 1/(2m-1) \;, \qquad a'\neq a^{-1} \;. $$ This particular chain is called non-backtracking simple random walk in the paper MR2342439 (2007) by Kaimanovich, Kapovich and Schupp. Its sample paths are precisely non-backtracking paths in the free group, and its time $n-1$ distribution for the initial distribution uniform on the set of $(a,a):a\in A$ is precisely the uniform measure on the words of length $n$ in the free group.

In the same way one can define the quotient of the above chain on $\mathbb Z^m$. Then the original question is precisely the question about an asymptotic of transition probabilities of this quotient chain. In the abelian case such chains have been extensively studied since early 80s, one of the earliest papers being the one by Krámli and Szász MR0699788 (1983). The asymptotic the OP is asking about is of course $n^{-m/2}$, which was later rediscovered and generalized in numerous other publications. However, I will refrain from going into the detailed history.

share|improve this answer

Your Answer

 
discard

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.