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

$\begingroup$ Shouldn't any $S^\prime$ which is conjugate to $S$ have this property? Or am I missing something? $\endgroup$– ARupinskiCommented May 15, 2012 at 23:46

$\begingroup$ Do you mean: does there ALWAYS exist such a set? $\endgroup$– Igor RivinCommented May 15, 2012 at 23:46

$\begingroup$ @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.$) $\endgroup$– Igor RivinCommented May 15, 2012 at 23:49

$\begingroup$ @Igor... thanks for clarifying, now I understand the ambiguity. $\endgroup$– ARupinskiCommented May 16, 2012 at 0:09

5$\begingroup$ @Igor... If I'm not mistaken, the ratio cannot converge to anything less than 1: We have $B_{j+k}<=B_jB_k$. So that by submultiplicativity, gr$(S)=\inf_k B_k^{1/k}$, so that in particular $B_k\ge $gr$(S)^k$. $\endgroup$– Anthony QuasCommented May 16, 2012 at 3:40
2 Answers
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_{k1}$, 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_kb_{k1}}{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 $2k2$ 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 nonfree 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.



$\begingroup$ 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. $\endgroup$– MishaCommented May 25, 2012 at 21:58

$\begingroup$ @Misha: The ratio in the question is bounded for the lamplighter group (see R. Lyons, R. Pemantle and Y. Peres, Random walks on the lamplighter group. Ann. Probab. 24(4):19932006, 1996), however, this group is amenable and not of polynomial growth so it does not have rapid decay. The same goes for solvable BS, see Collins, Edjvet and Gill, Growth series of the group $\langle x,y \mid x^{1}yx=y^\ell \rangle$, Arch. Math. 62:111, 1994. $\endgroup$– ARGCommented Apr 5, 2016 at 9:39
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 nontrivial free subgroup). This can be achieved by Gromov's smallcancellation 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$.

$\begingroup$ @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. $\endgroup$– user6976Commented May 16, 2012 at 9:31

$\begingroup$ 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. $\endgroup$– user6976Commented May 16, 2012 at 9:33


$\begingroup$ @Lee: Yes, he deleted himself  very sad. $\endgroup$– user6976Commented May 16, 2012 at 13:55

$\begingroup$ @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. $\endgroup$– Ian AgolCommented May 16, 2012 at 15:51