# Does a group have polynomial growth of the same degree under all generating sets?

(a) Let $$G$$ have polynomial growth of degree d. Let the polynomial growth function of G under the generating set S given by $$\gamma_S(n)\leq c_1n^d$$. Does this imply that under any other generating set T, $$\gamma_T(n)\leq c_2n^d$$, possibly with $$c_2 \neq c_1$$?

Suppose not, then $$\gamma_S(n)\leq c_2n^d<\gamma_T(n)\leq c_1n^d$$ I'm trying to find something here that will lead to contradiction.

All I have from this is that for some fixed $$n$$, $$\mid B_S(n)\mid\leq \mid B_T(n)\mid$$ where $$B_S(n)$$ is the ball of radius $$n$$ under $$S$$. This implies that $$\exists g\in G: g\in B_T(n) \text{ and } g\notin B_S(n)$$ Thus $$g=t_1t_2...t_n$$ for $$t_i\in T$$, but $$g$$ requires more than $$n$$ elements to be described as a word in $$S$$.

I also know that $$l_S(g)\leq max\{l_S(y):y\in T\}*l_T(g)=max\{l_S(y):y\in T\}*n$$ where $$l_s(g)$$ is the length of a word with respect to $$S$$. Perhaps this can lead to a contradiction since it puts a bound on the length of $$g$$ w.r.t $$S$$. But I don't see one.

• You do not an equality such as $\gamma(n)=cn^d$, only an 2-sided inequality. This is already the case when $d=0$, i.e. $G$ is finite. – Moishe Kohan Jan 11 '19 at 1:03
• @MoisheCohen Thanks, that is actually one of the misunderstandings I had about the definitions that stood in the way of understanding the answer below, I'll edit it. – Mike Jan 11 '19 at 1:05
• The revised version is correct for any growth rate (polynomial, exponential, intermediate), you can find a proof in any textbook on geometric group theory. – Moishe Kohan Jan 11 '19 at 1:34
• (b) "same question": it's unclear what you mean by "same question". Depending on how you formulate the statement in the exponential case, the answer would be yes or no. – YCor Jan 11 '19 at 2:13
• @YCor Yeah, I think the proof below is fine for both polynomial and exponential growth, with small changes, so I'll just edit this to only be for polynomial growth. – Mike Jan 11 '19 at 2:21

Let $$T$$ be any other finite generating subset. There exists some integer $$N$$ such that every $$g \in S$$ is the product of at most $$N$$ elements of $$T$$ and vice-versa.
Then, for any integer $$k \geq N^2$$, $$c_Nk^d\leq B_S(\left\lfloor{k/N}\right \rfloor) \subset B_T(k) \subset B_S(kN) \leq C_Nk^d$$ for constants $$0 < c_N < C_N$$.
• I am not sure I follow the 'vice-versa' part in the second line. I agree that since $T$ is also a generator, for some $N$ we will be able to get $s=t_1...t_N$ for every $s$ in $S$. But wouldn't the vice versa statement imply that every element g=$t'_1...t'_N$ of $N$ elements in $T$ would have to be in $S$? Is that necessary? – Mike Jan 10 '19 at 23:41
• No: the vice versa is that every element of $T$ is the product of at most $N$ elements in $S$. This is true if $N$ is large enough. – Mindlack Jan 10 '19 at 23:59
• Ah, thanks, I see that. So for large enough $N$ both $S$ and $T$ can describe each other in less than $N$ letters. And I see how the set inclusions follow. However, I don't see how the result follows: that the growth of $G$ under $T$ is also of order $d$. Does $d$ in your answer correspond with $d$ in my question? – Mike Jan 11 '19 at 0:11
• I'm having a hard time getting your first inequality: $c_nk^d\leq B_S(k/N)$ How do you get this polynomial to be under the cardinality of this neighborhood? For the last inequality I assume you do: $B_S(kN)\leq C_1(kN)^d=(C_1 N^d) k^d=C_N k^d$ but in this case the inequality is given by the definition of polynomial growth. I also see that by assuming $T$ doesn't have degree $d$ growth, we can get $\mid B_T(k) \mid > c_1k^d$ for some $c_1$, but how can you sneak that $\mid B_S(k/N) \mid$ in between? Do we even need that part? – Mike Jan 11 '19 at 1:22