# Asymptotics of the growth rate of a group

Let $\Gamma$ be a finitely generated group of exponential growth and $gr(S)=\lim_{k\rightarrow \infty} \sqrt[k]{|B_k(S)|}$ be the growth rate of $\Gamma$ with respect to the generating set $S$. I am confused with the following question: Does there always exist a generating set $S'$ such that $$\frac{|B_k(S')|}{gr(S')^k}\rightarrow 1, \text{ when }k\rightarrow \infty$$

-
Shouldn't any $S^\prime$ which is conjugate to $S$ have this property? Or am I missing something? –  ARupinski May 15 '12 at 23:46
Do you mean: does there ALWAYS exist such a set? –  Igor Rivin May 15 '12 at 23:46
@ARupinski: I think what the OP means is that the limit of the ratio can tend to zero or infinity (for example, $B_k(S) = k 3^k.$) –  Igor Rivin May 15 '12 at 23:49
@Igor... thanks for clarifying, now I understand the ambiguity. –  ARupinski May 16 '12 at 0:09
@Igor... If I'm not mistaken, the ratio cannot converge to anything less than 1: We have $|B_{j+k}|<=|B_j||B_k|$. So that by sub-multiplicativity, gr$(S)=\inf_k |B_k|^{1/k}$, so that in particular $|B_k|\ge$gr$(S)^k$. –  Anthony Quas May 16 '12 at 3:40

There is never a (finite) generating set with that property.

Consider a generating set $S=\{x_1,\ldots,x_{\ell}\}$ of cardinality $\ell$. Let $B_k := B_k(S)$, $S_k := B_k \setminus B_{k-1}$, and $g := gr(S)$. Let $b_k := |B_k|$ and $s_k: = |S_k|$. Assume for simplicity that $L := \lim_{k \to \infty} \frac{b_k}{g^k}$ exists (although it shouldn't be difficult to get general liminf bounds). Also set $$L' := \lim_{k \to \infty} \frac{s_k}{g^k} = \lim_{k \to \infty} \frac{b_k-b_{k-1}}{g^k} = \left(1-\frac{1}{g}\right)L.$$

For the spheres, there's a trivial inequality $s_{m+n} \leq s_m s_n$. (Any word of minimal length $m+n$ in the generators may be written at least one way as a product of two words of minimal length $m$ and $n$.) This is already enough to give $L' \geq 1$, and thus $$L \geq \frac{1}{1-\frac{1}{g}} > 1.$$

This is unsatisfying and still leaves the possibility that $L'=1$. Thus, I eliminate that possibility as well, by improving the trivial bound $s_{2k} \leq s_k^2$ to $s_{2k} \leq \left(1-\frac{1}{2\ell}\right)s_k^2$. This improvement (unlike the trivial improvement above) does not hold for monoids, so the extra cancellation comes (unsurprisingly) from the existance of inverses.

Specifically, fix $k$, let $E_i$ be the set of all elements of $S_k$ which may be written as a word of length $k$ ending in $x_i$, and let $E_{\ell+i}$ be the set of all elements of $S_k$ which may be written as a word of length $k$ ending in $x_i^{-1}$. Set $$F_i = E_i \setminus \bigcup_{j < i} E_j,$$ so the $F_i$ are disjoint. Let $F_i'$ be the image of $F_i$ under the inversion map, and let $n_i = |F_i|$. The product of an element of $F_i$ and an element of $F_i'$ may be written with $2k-2$ letters (because the $x_i$ and $x_i^{-1}$ cancel), so those $n_i^2$ products are not in $S_{2k}$. Thus, we have $$s_{2k} \leq s_k^2 - \sum_{i=1}^{2\ell} n_i^2.$$ By the Hölder inequality, we have $$s_k = \sum_{i=1}^{2\ell} n_i \leq \sqrt{\sum_{i=1}^{2\ell} 1^2} \sqrt{\sum_{i=1}^{2\ell} n_i^2}$$ $$\frac{s_k^2}{2\ell} \leq \sum_{i=1}^{2\ell} n_i^2.$$ Combining the inequalities gives $$s_{2k} \leq \left(1-\frac{1}{2\ell}\right)s_k^2.$$ Dividing by $g^{2k}$ and sending $k \to \infty$ gives $$L' \geq \frac{1}{1-\frac{1}{2\ell}} > 1.$$ For balls, we obtain the bound $$L \geq \frac{1}{\left(1-\frac{1}{g}\right)\left(1-\frac{1}{2\ell}\right)}.$$ This bound is optimal for free generating sets of free groups.

I'd be interested in seeing what Kate's limit says (or don't say) about the underlying group. Can the lower bound I just gave be achieved for non-free groups? Can the limit generally be made arbitrarily close to $1$ by increasing the number of generators appropriately (as Misha speculated in the comments)? I'm far from an expert in combinatorial/asymptotic group theory, so I don't have good intuition for what intrinsic information this value holds.

-
Very nice argument! –  Igor Rivin May 24 '12 at 1:55
How delightfully simple. –  Lee Mosher May 25 '12 at 18:06
This is indeed very nice. @Kate: My current guess is that for (at least some) groups which fail the Rapid Decay property, the limits of ratios in your question are always infinite. –  Misha May 25 '12 at 21:58

I think there may be examples which are limits of hyperbolic groups. Here's a suggested construction:

Take an infinitely presented group $G=\langle x,y | R_1, R_2, R_3, \ldots \rangle$ such that $G_n=\langle x,y | R_1, \ldots, R_n \rangle$ is hyperbolic, and $G_n \neq G_{n+1}$, such that $G$ has exponential growth (for example, it can contain a non-trivial free subgroup). This can be achieved by Gromov's small-cancellation theory over hyperbolic groups. Then I believe that for any generating set $\langle S\rangle=\langle x,y\rangle$, the growth rate $\phi_n$ of $G_n$ with respect to $S$ ought to be strictly decreasing, with limit the growth rate $\phi$ of $G$. Moreover, I think that one should find that $|B_k(S)|/\phi^k \to \infty$. Roughly, I think this should hold because for a fixed $k$, there are only finitely many loops in $B_k(S)$, which are in the normal subgroup generated by $R_j$, $j\leq n$, so the growth should look like the growth of $G_n$, which should be larger than $\phi_n^k > \phi^k$. But I don't know if this argument can be made precise. By a result of Cannon, the growth of a hyperbolic group is rational, so one might have to analyze more precisely the growth functions of each hyperbolic group $G_n$ to determine the growth of $G$.

-
@Ian: I am not sure you understand the question (or I do not understand your answer). Even if for some $S$ the limit is infinity, it may be that for another generating set the limit is 1: functions $2^n$ and $n2^n$ are equivalent. –  Mark Sapir May 16 '12 at 9:31
I think that a potential counterexample is suggested in the deleted Igor Rivin's answer. The free group cannot have a generating set with limit equal top 1. He did not have a proof, though. –  Mark Sapir May 16 '12 at 9:33
Igor Rivin was deleted?!? –  Lee Mosher May 16 '12 at 12:42
@Lee: Yes, he deleted himself - very sad. –  Mark Sapir May 16 '12 at 13:55
@Mark: I think I understand the question. I'm trying to show that $|B_k(S)|/\phi^k \to \infty$ for any choice of generating set $S$. To make the heuristic precise, one would have to have some idea of the relative growth of the ratio $\phi_n^k/\phi^k$, which might require some explicit construction of the relators $R_j$ and the growth rates $\phi_n$. I suspect if one could show this for one generating set, it ought to hold for any other generating set. But I certainly am not an expert on growth of groups. –  Ian Agol May 16 '12 at 15:51