Mixing
A kind of pumping lemma for finitely generated groups
Clash Royale CLAN TAG#URR8PPP
up vote
0
down vote
favorite
I was reading some notes on Geometric Group Theory from a seminar, and I came across a statement that reminded me of a pumping lemma. First of all I'll give some definitions and then I'll ask a couple of question on that statement and one of its implications.
Notation:
Let $G$ an infinite finitely generated group. For $gin G$ and a finite generating set $Xsubseteq G$, I denote $|g|_X$ the distance from $1_G$ to $g$ on the Cayley graph of $G$ with respect to $X$. By $w_g$ I denote the word of minimum lenght representing $g$ in $G$ and by $l(w)$ I denote the length of the word $w$.
Definition: A word $w=x_1cdots x_n$ is said to be $p$-periodic if $x_i=x_i+p$ for $1leq ileq n-p$.
Definition: The growth function of $G$ with respect to $X$ is defined by $beta_(G,X)(n)=#gin Gmid $.
The statement is the following
Given $minmathbbN$ and $gin G$ with $|g|_Xgeq 2m$, there exist words $u_g,v_g,s_g$ such that $l(u_g),l(v_g)leq m$, $s_g$ is $p$-periodic with $pleq m$ and $w_g=u_gs_gv_g$.
This statement appears in a proof of: the growth function of $G$ is of the order of a degree 1 polynomial implies that $G$ contains an infinite cyclic subgroup of finite index.
First of all, this statement reminds me of the pumping lemma for regular languages, so I would like to know whether this is a known result with a name and if it is indeed related with some pumping lemma.
Sencondly, there is the following explanation:
We observe that the above statement implies the existence of elements of strictly high order. We have $l(s_g)geq |g|_X-2m$ and $s_g=t_g^ks_g'$ with $t_gin G$ such that $|t_g|_X=pleq m$ and $t_g$ has order $>k$. Since there are finitely many choices of $t_g$, there must be one of infinite order.
I think it should be $l(w_t_g)=p$ and not necessarily $|t_g|=p$, since $t_g$ is represented by the word that is repeated in $s_g$. Furtheremore, I don't understand what is meant by "there are finitely many choices of $t_g$" since there is only one $t_g$ for each word $s_g$, and I don't see why this implies that there is some element of infinite order.
group-theory reference-request formal-languages geometric-group-theory
asked Jul 18 at 15:15
Javi
2,1631725
add a comment |Â
up vote
0
down vote
favorite
I was reading some notes on Geometric Group Theory from a seminar, and I came across a statement that reminded me of a pumping lemma. First of all I'll give some definitions and then I'll ask a couple of question on that statement and one of its implications.
Notation:
Let $G$ an infinite finitely generated group. For $gin G$ and a finite generating set $Xsubseteq G$, I denote $|g|_X$ the distance from $1_G$ to $g$ on the Cayley graph of $G$ with respect to $X$. By $w_g$ I denote the word of minimum lenght representing $g$ in $G$ and by $l(w)$ I denote the length of the word $w$.
Definition: A word $w=x_1cdots x_n$ is said to be $p$-periodic if $x_i=x_i+p$ for $1leq ileq n-p$.
Definition: The growth function of $G$ with respect to $X$ is defined by $beta_(G,X)(n)=#gin Gmid $.
The statement is the following
Given $minmathbbN$ and $gin G$ with $|g|_Xgeq 2m$, there exist words $u_g,v_g,s_g$ such that $l(u_g),l(v_g)leq m$, $s_g$ is $p$-periodic with $pleq m$ and $w_g=u_gs_gv_g$.
This statement appears in a proof of: the growth function of $G$ is of the order of a degree 1 polynomial implies that $G$ contains an infinite cyclic subgroup of finite index.
First of all, this statement reminds me of the pumping lemma for regular languages, so I would like to know whether this is a known result with a name and if it is indeed related with some pumping lemma.
Sencondly, there is the following explanation:
We observe that the above statement implies the existence of elements of strictly high order. We have $l(s_g)geq |g|_X-2m$ and $s_g=t_g^ks_g'$ with $t_gin G$ such that $|t_g|_X=pleq m$ and $t_g$ has order $>k$. Since there are finitely many choices of $t_g$, there must be one of infinite order.
I think it should be $l(w_t_g)=p$ and not necessarily $|t_g|=p$, since $t_g$ is represented by the word that is repeated in $s_g$. Furtheremore, I don't understand what is meant by "there are finitely many choices of $t_g$" since there is only one $t_g$ for each word $s_g$, and I don't see why this implies that there is some element of infinite order.
group-theory reference-request formal-languages geometric-group-theory
asked Jul 18 at 15:15
Javi
2,1631725
Yes, this appears inside a proof, so I'll add those hypothesis @LeeMosher
– Javi
Jul 18 at 15:51
It feels like there's an inequality or quantifier reversed somewhere in the first statement - as written we can just take $m=1$ and say that all words $w$ in $G$ other than the generators are of the form $x_ax_b^nx_c$ and that surely isn't correct.
– Steven Stadnicki
Jul 18 at 16:07
I copied it just like it was stated so I don't know what is wrong. Perhaps some quantifier on $m$ is needed. @StevenStadnicki
– Javi
Jul 18 at 16:11
1
To answer your question about whether this is a known result with a name, I know of no such result or name. Also, knowing that this lemma is appearing only in the middle of the proof you mention, I'm sure there is no need for a general name, because the class of groups that possess a cyclic subgroup of finite index is an extremely special class of groups.
– Lee Mosher
Jul 20 at 17:34
add a comment |Â
up vote
0
down vote
favorite
up vote
0
down vote
favorite
I was reading some notes on Geometric Group Theory from a seminar, and I came across a statement that reminded me of a pumping lemma. First of all I'll give some definitions and then I'll ask a couple of question on that statement and one of its implications.
Notation:
Let $G$ an infinite finitely generated group. For $gin G$ and a finite generating set $Xsubseteq G$, I denote $|g|_X$ the distance from $1_G$ to $g$ on the Cayley graph of $G$ with respect to $X$. By $w_g$ I denote the word of minimum lenght representing $g$ in $G$ and by $l(w)$ I denote the length of the word $w$.
Definition: A word $w=x_1cdots x_n$ is said to be $p$-periodic if $x_i=x_i+p$ for $1leq ileq n-p$.
Definition: The growth function of $G$ with respect to $X$ is defined by $beta_(G,X)(n)=#gin Gmid $.
The statement is the following
Given $minmathbbN$ and $gin G$ with $|g|_Xgeq 2m$, there exist words $u_g,v_g,s_g$ such that $l(u_g),l(v_g)leq m$, $s_g$ is $p$-periodic with $pleq m$ and $w_g=u_gs_gv_g$.
This statement appears in a proof of: the growth function of $G$ is of the order of a degree 1 polynomial implies that $G$ contains an infinite cyclic subgroup of finite index.
First of all, this statement reminds me of the pumping lemma for regular languages, so I would like to know whether this is a known result with a name and if it is indeed related with some pumping lemma.
Sencondly, there is the following explanation:
We observe that the above statement implies the existence of elements of strictly high order. We have $l(s_g)geq |g|_X-2m$ and $s_g=t_g^ks_g'$ with $t_gin G$ such that $|t_g|_X=pleq m$ and $t_g$ has order $>k$. Since there are finitely many choices of $t_g$, there must be one of infinite order.
I think it should be $l(w_t_g)=p$ and not necessarily $|t_g|=p$, since $t_g$ is represented by the word that is repeated in $s_g$. Furtheremore, I don't understand what is meant by "there are finitely many choices of $t_g$" since there is only one $t_g$ for each word $s_g$, and I don't see why this implies that there is some element of infinite order.
group-theory reference-request formal-languages geometric-group-theory
asked Jul 18 at 15:15
Javi
2,1631725
I was reading some notes on Geometric Group Theory from a seminar, and I came across a statement that reminded me of a pumping lemma. First of all I'll give some definitions and then I'll ask a couple of question on that statement and one of its implications.
Notation:
Let $G$ an infinite finitely generated group. For $gin G$ and a finite generating set $Xsubseteq G$, I denote $|g|_X$ the distance from $1_G$ to $g$ on the Cayley graph of $G$ with respect to $X$. By $w_g$ I denote the word of minimum lenght representing $g$ in $G$ and by $l(w)$ I denote the length of the word $w$.
Definition: A word $w=x_1cdots x_n$ is said to be $p$-periodic if $x_i=x_i+p$ for $1leq ileq n-p$.
Definition: The growth function of $G$ with respect to $X$ is defined by $beta_(G,X)(n)=#gin Gmid $.
The statement is the following
Given $minmathbbN$ and $gin G$ with $|g|_Xgeq 2m$, there exist words $u_g,v_g,s_g$ such that $l(u_g),l(v_g)leq m$, $s_g$ is $p$-periodic with $pleq m$ and $w_g=u_gs_gv_g$.
This statement appears in a proof of: the growth function of $G$ is of the order of a degree 1 polynomial implies that $G$ contains an infinite cyclic subgroup of finite index.
First of all, this statement reminds me of the pumping lemma for regular languages, so I would like to know whether this is a known result with a name and if it is indeed related with some pumping lemma.
Sencondly, there is the following explanation:
We observe that the above statement implies the existence of elements of strictly high order. We have $l(s_g)geq |g|_X-2m$ and $s_g=t_g^ks_g'$ with $t_gin G$ such that $|t_g|_X=pleq m$ and $t_g$ has order $>k$. Since there are finitely many choices of $t_g$, there must be one of infinite order.
I think it should be $l(w_t_g)=p$ and not necessarily $|t_g|=p$, since $t_g$ is represented by the word that is repeated in $s_g$. Furtheremore, I don't understand what is meant by "there are finitely many choices of $t_g$" since there is only one $t_g$ for each word $s_g$, and I don't see why this implies that there is some element of infinite order.
group-theory reference-request formal-languages geometric-group-theory
asked Jul 18 at 15:15
Javi
2,1631725
edited Jul 18 at 15:55
asked Jul 18 at 15:15
Javi
2,1631725
asked Jul 18 at 15:15
Javi
2,1631725
asked Jul 18 at 15:15
Javi
2,1631725
2,1631725
Yes, this appears inside a proof, so I'll add those hypothesis @LeeMosher
– Javi
Jul 18 at 15:51
It feels like there's an inequality or quantifier reversed somewhere in the first statement - as written we can just take $m=1$ and say that all words $w$ in $G$ other than the generators are of the form $x_ax_b^nx_c$ and that surely isn't correct.
– Steven Stadnicki
Jul 18 at 16:07
I copied it just like it was stated so I don't know what is wrong. Perhaps some quantifier on $m$ is needed. @StevenStadnicki
– Javi
Jul 18 at 16:11
1
To answer your question about whether this is a known result with a name, I know of no such result or name. Also, knowing that this lemma is appearing only in the middle of the proof you mention, I'm sure there is no need for a general name, because the class of groups that possess a cyclic subgroup of finite index is an extremely special class of groups.
– Lee Mosher
Jul 20 at 17:34
add a comment |Â
Yes, this appears inside a proof, so I'll add those hypothesis @LeeMosher
– Javi
Jul 18 at 15:51
It feels like there's an inequality or quantifier reversed somewhere in the first statement - as written we can just take $m=1$ and say that all words $w$ in $G$ other than the generators are of the form $x_ax_b^nx_c$ and that surely isn't correct.
– Steven Stadnicki
Jul 18 at 16:07
I copied it just like it was stated so I don't know what is wrong. Perhaps some quantifier on $m$ is needed. @StevenStadnicki
– Javi
Jul 18 at 16:11
1
To answer your question about whether this is a known result with a name, I know of no such result or name. Also, knowing that this lemma is appearing only in the middle of the proof you mention, I'm sure there is no need for a general name, because the class of groups that possess a cyclic subgroup of finite index is an extremely special class of groups.
– Lee Mosher
Jul 20 at 17:34
Yes, this appears inside a proof, so I'll add those hypothesis @LeeMosher
– Javi
Jul 18 at 15:51
Yes, this appears inside a proof, so I'll add those hypothesis @LeeMosher
– Javi
Jul 18 at 15:51
It feels like there's an inequality or quantifier reversed somewhere in the first statement - as written we can just take $m=1$ and say that all words $w$ in $G$ other than the generators are of the form $x_ax_b^nx_c$ and that surely isn't correct.
– Steven Stadnicki
Jul 18 at 16:07
It feels like there's an inequality or quantifier reversed somewhere in the first statement - as written we can just take $m=1$ and say that all words $w$ in $G$ other than the generators are of the form $x_ax_b^nx_c$ and that surely isn't correct.
– Steven Stadnicki
Jul 18 at 16:07
I copied it just like it was stated so I don't know what is wrong. Perhaps some quantifier on $m$ is needed. @StevenStadnicki
– Javi
Jul 18 at 16:11
I copied it just like it was stated so I don't know what is wrong. Perhaps some quantifier on $m$ is needed. @StevenStadnicki
– Javi
Jul 18 at 16:11
1
1
To answer your question about whether this is a known result with a name, I know of no such result or name. Also, knowing that this lemma is appearing only in the middle of the proof you mention, I'm sure there is no need for a general name, because the class of groups that possess a cyclic subgroup of finite index is an extremely special class of groups.
– Lee Mosher
Jul 20 at 17:34
To answer your question about whether this is a known result with a name, I know of no such result or name. Also, knowing that this lemma is appearing only in the middle of the proof you mention, I'm sure there is no need for a general name, because the class of groups that possess a cyclic subgroup of finite index is an extremely special class of groups.
– Lee Mosher
Jul 20 at 17:34
add a comment |Â
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
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
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2855666%2fa-kind-of-pumping-lemma-for-finitely-generated-groups%23new-answer', 'question_page');
);
Post as a guest
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
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
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
Yes, this appears inside a proof, so I'll add those hypothesis @LeeMosher
– Javi
Jul 18 at 15:51
It feels like there's an inequality or quantifier reversed somewhere in the first statement - as written we can just take $m=1$ and say that all words $w$ in $G$ other than the generators are of the form $x_ax_b^nx_c$ and that surely isn't correct.
– Steven Stadnicki
Jul 18 at 16:07
I copied it just like it was stated so I don't know what is wrong. Perhaps some quantifier on $m$ is needed. @StevenStadnicki
– Javi
Jul 18 at 16:11
1
To answer your question about whether this is a known result with a name, I know of no such result or name. Also, knowing that this lemma is appearing only in the middle of the proof you mention, I'm sure there is no need for a general name, because the class of groups that possess a cyclic subgroup of finite index is an extremely special class of groups.
– Lee Mosher
Jul 20 at 17:34