Asymptotics of the growth rate of a group - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T07:10:09Z http://mathoverflow.net/feeds/question/97060 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/97060/asymptotics-of-the-growth-rate-of-a-group Asymptotics of the growth rate of a group Kate Juschenko 2012-05-15T22:26:33Z 2012-05-24T00:46:25Z <p>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$$</p> http://mathoverflow.net/questions/97060/asymptotics-of-the-growth-rate-of-a-group/97088#97088 Answer by Agol for Asymptotics of the growth rate of a group Agol 2012-05-16T04:58:56Z 2012-05-16T04:58:56Z <p>I think there may be examples which are limits of hyperbolic groups. Here's a suggested construction:</p> <p>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, <a href="http://www.ams.org/mathscinet-getitem?mr=758901" rel="nofollow">the growth of a hyperbolic group is rational</a>, so one might have to analyze more precisely the growth functions of each hyperbolic group $G_n$ to determine the growth of $G$. </p> http://mathoverflow.net/questions/97060/asymptotics-of-the-growth-rate-of-a-group/97805#97805 Answer by Gene S. Kopp for Asymptotics of the growth rate of a group Gene S. Kopp 2012-05-24T00:46:25Z 2012-05-24T00:46:25Z <p>There is never a (finite) generating set with that property.</p> <p>Consider a generating set <code>$S=\{x_1,\ldots,x_{\ell}\}$</code> 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.$$</p> <p>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.$$</p> <p>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.</p> <p>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 &lt; 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.</p> <p>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.</p>