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

  • 1
    $\begingroup$ 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. $\endgroup$ – Moishe Kohan Jan 11 '19 at 1:03
  • $\begingroup$ @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. $\endgroup$ – Mike Jan 11 '19 at 1:05
  • 1
    $\begingroup$ The revised version is correct for any growth rate (polynomial, exponential, intermediate), you can find a proof in any textbook on geometric group theory. $\endgroup$ – Moishe Kohan Jan 11 '19 at 1:34
  • $\begingroup$ (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. $\endgroup$ – YCor Jan 11 '19 at 2:13
  • $\begingroup$ @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. $\endgroup$ – 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$.

That should give you the answer, I think.

| cite | improve this answer | |
  • $\begingroup$ 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? $\endgroup$ – Mike Jan 10 '19 at 23:41
  • $\begingroup$ 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. $\endgroup$ – Mindlack Jan 10 '19 at 23:59
  • $\begingroup$ 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? $\endgroup$ – Mike Jan 11 '19 at 0:11
  • $\begingroup$ No, that’s an unfortunate notation. I’ll edit it to make it clearer. $\endgroup$ – Mindlack Jan 11 '19 at 0:12
  • $\begingroup$ 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? $\endgroup$ – Mike Jan 11 '19 at 1:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.