Asymptotics of the growth rate of a group - MathOverflow

Asymptotics of the growth rate of a group

2012-05-15T22:26:33Z

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

Answer by Agol for Asymptotics of the growth rate of a group

2012-05-16T04:58:56Z

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

Answer by Gene S. Kopp for Asymptotics of the growth rate of a group

2012-05-24T00:46:25Z

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.