Mixing
Does a group have polynomial growth of the same degree under all generating sets?
$begingroup$
(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)midleq mid B_T(n)mid$ where $B_S(n)$ is the ball of radius $n$ under $S$. This implies that $$exists gin G: gin B_T(n) text{ and } gnotin B_S(n)$$ Thus $g=t_1t_2...t_n$ for $t_iin 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):yin T}*l_T(g)=max{l_S(y):yin 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.
group-theory subgroup-growth
asked Jan 10 at 22:42
MikeMike
714415
$endgroup$
|
show 1 more comment
$begingroup$
(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)midleq mid B_T(n)mid$ where $B_S(n)$ is the ball of radius $n$ under $S$. This implies that $$exists gin G: gin B_T(n) text{ and } gnotin B_S(n)$$ Thus $g=t_1t_2...t_n$ for $t_iin 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):yin T}*l_T(g)=max{l_S(y):yin 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.
group-theory subgroup-growth
asked Jan 10 at 22:42
MikeMike
714415
$endgroup$
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 Cohen
Jan 11 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 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 Cohen
Jan 11 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 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 at 2:21
|
show 1 more comment
$begingroup$
(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)midleq mid B_T(n)mid$ where $B_S(n)$ is the ball of radius $n$ under $S$. This implies that $$exists gin G: gin B_T(n) text{ and } gnotin B_S(n)$$ Thus $g=t_1t_2...t_n$ for $t_iin 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):yin T}*l_T(g)=max{l_S(y):yin 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.
group-theory subgroup-growth
asked Jan 10 at 22:42
MikeMike
714415
$endgroup$
(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)midleq mid B_T(n)mid$ where $B_S(n)$ is the ball of radius $n$ under $S$. This implies that $$exists gin G: gin B_T(n) text{ and } gnotin B_S(n)$$ Thus $g=t_1t_2...t_n$ for $t_iin 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):yin T}*l_T(g)=max{l_S(y):yin 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.
group-theory subgroup-growth
group-theory subgroup-growth
asked Jan 10 at 22:42
MikeMike
714415
asked Jan 10 at 22:42
MikeMike
714415
edited Jan 11 at 2:22
Mike
asked Jan 10 at 22:42
MikeMike
714415
asked Jan 10 at 22:42
MikeMike
714415
asked Jan 10 at 22:42
MikeMike
714415
714415
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 Cohen
Jan 11 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 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 Cohen
Jan 11 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 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 at 2:21
|
show 1 more comment
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 Cohen
Jan 11 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 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 Cohen
Jan 11 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 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 at 2:21
1
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 Cohen
Jan 11 at 1:03
$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 Cohen
Jan 11 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 at 1:05
$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 at 1:05
1
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 Cohen
Jan 11 at 1:34
$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 Cohen
Jan 11 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 at 2:13
$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 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 at 2:21
$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 at 2:21
|
show 1 more comment
1 Answer
1
active
oldest
votes
$begingroup$
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^dleq B_S(leftlfloor{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.
answered Jan 10 at 23:23
MindlackMindlack
3,68518
$endgroup$
$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 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 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 at 0:11
$begingroup$
No, that’s an unfortunate notation. I’ll edit it to make it clearer.
$endgroup$
– Mindlack
Jan 11 at 0:12
$begingroup$
I'm having a hard time getting your first inequality: $c_nk^dleq 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 at 1:22
|
show 1 more comment
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3069269%2fdoes-a-group-have-polynomial-growth-of-the-same-degree-under-all-generating-sets%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
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^dleq B_S(leftlfloor{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.
answered Jan 10 at 23:23
MindlackMindlack
3,68518
$endgroup$
$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 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 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 at 0:11
$begingroup$
No, that’s an unfortunate notation. I’ll edit it to make it clearer.
$endgroup$
– Mindlack
Jan 11 at 0:12
$begingroup$
I'm having a hard time getting your first inequality: $c_nk^dleq 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 at 1:22
|
show 1 more comment
$begingroup$
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^dleq B_S(leftlfloor{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.
answered Jan 10 at 23:23
MindlackMindlack
3,68518
$endgroup$
$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 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 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 at 0:11
$begingroup$
No, that’s an unfortunate notation. I’ll edit it to make it clearer.
$endgroup$
– Mindlack
Jan 11 at 0:12
$begingroup$
I'm having a hard time getting your first inequality: $c_nk^dleq 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 at 1:22
|
show 1 more comment
$begingroup$
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^dleq B_S(leftlfloor{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.
answered Jan 10 at 23:23
MindlackMindlack
3,68518
$endgroup$
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^dleq B_S(leftlfloor{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.
answered Jan 10 at 23:23
MindlackMindlack
3,68518
edited Jan 11 at 0:14
answered Jan 10 at 23:23
MindlackMindlack
3,68518
answered Jan 10 at 23:23
MindlackMindlack
3,68518
answered Jan 10 at 23:23
MindlackMindlack
3,68518
3,68518
$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 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 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 at 0:11
$begingroup$
No, that’s an unfortunate notation. I’ll edit it to make it clearer.
$endgroup$
– Mindlack
Jan 11 at 0:12
$begingroup$
I'm having a hard time getting your first inequality: $c_nk^dleq 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 at 1:22
|
show 1 more comment
$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 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 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 at 0:11
$begingroup$
No, that’s an unfortunate notation. I’ll edit it to make it clearer.
$endgroup$
– Mindlack
Jan 11 at 0:12
$begingroup$
I'm having a hard time getting your first inequality: $c_nk^dleq 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 at 1:22
$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 at 23:41
$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 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 at 23:59
$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 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 at 0:11
$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 at 0:11
$begingroup$
No, that’s an unfortunate notation. I’ll edit it to make it clearer.
$endgroup$
– Mindlack
Jan 11 at 0:12
$begingroup$
No, that’s an unfortunate notation. I’ll edit it to make it clearer.
$endgroup$
– Mindlack
Jan 11 at 0:12
$begingroup$
I'm having a hard time getting your first inequality: $c_nk^dleq 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 at 1:22
$begingroup$
I'm having a hard time getting your first inequality: $c_nk^dleq 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 at 1:22
|
show 1 more comment
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3069269%2fdoes-a-group-have-polynomial-growth-of-the-same-degree-under-all-generating-sets%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
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 Cohen
Jan 11 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 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 Cohen
Jan 11 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 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 at 2:21