Presentations that make the Todd-Coxeter algorithm blow up
Consider the presentation defined, for an integer $n > 1$, by
$$G_{n} = langle x, y mid xy^n = y^{n+1}x, yx^{n+1} = x^{n}yrangle .$$
The group defined by this presentation is trivial. Is it true that the minimum number of cosets that must be defined by the Todd-Coxeter process before any coincidences occur, when run on this presentation over the trivial subgroup, is bounded below by some (at least linear, probably worse) function of $n$, and is such a lower bound known? (In practice, this seems to behave quite badly.)
(A special case of this appears in a recent question, which is what prompted this one.)
group-theory reference-request group-presentation combinatorial-group-theory
edited Dec 3 '18 at 0:52
Shaun
8,810113680
asked Jun 14 '14 at 8:44
James
7,01721426
add a comment |
Consider the presentation defined, for an integer $n > 1$, by
$$G_{n} = langle x, y mid xy^n = y^{n+1}x, yx^{n+1} = x^{n}yrangle .$$
The group defined by this presentation is trivial. Is it true that the minimum number of cosets that must be defined by the Todd-Coxeter process before any coincidences occur, when run on this presentation over the trivial subgroup, is bounded below by some (at least linear, probably worse) function of $n$, and is such a lower bound known? (In practice, this seems to behave quite badly.)
(A special case of this appears in a recent question, which is what prompted this one.)
group-theory reference-request group-presentation combinatorial-group-theory
edited Dec 3 '18 at 0:52
Shaun
8,810113680
asked Jun 14 '14 at 8:44
James
7,01721426
I have never heard of a theorem proving such a lower bound. You get much faster completion with Todd-Coxeter coset enumeration if you enumerate cosets of the subgroup $langle x rangle$ rather than the trivial subgroup. It completes very quickly even with $n=100$.
– Derek Holt
Jun 14 '14 at 19:50
@DerekHolt, yes you're right. It does still seem to blow up, though, just much more slowly. But I was mainly curious whether this was one of those examples that was known, or could be shown, to have necessarily bad behaviour. I have an example in my notes of the form $langle x,ymid x^ny^{n+1}, x^{n+1}y^{n+2}rangle$ where it is supposed to require at least $n$ cosets to be defined before any coincidence can occur in Todd-Coxeter. I thought this might be another such. Alas, I did not write down the reference. I thought it might have been your "Handbook", but I could not find it there now.
– James
Jun 17 '14 at 3:08
@DerekHolt. I guess it was obvious what I meant, but I notice that I failed to note that I was referring to an enumeration of the cosets of the trivial subgroup. I've fixed it.
– James
Jun 17 '14 at 3:10
add a comment |
Consider the presentation defined, for an integer $n > 1$, by
$$G_{n} = langle x, y mid xy^n = y^{n+1}x, yx^{n+1} = x^{n}yrangle .$$
The group defined by this presentation is trivial. Is it true that the minimum number of cosets that must be defined by the Todd-Coxeter process before any coincidences occur, when run on this presentation over the trivial subgroup, is bounded below by some (at least linear, probably worse) function of $n$, and is such a lower bound known? (In practice, this seems to behave quite badly.)
(A special case of this appears in a recent question, which is what prompted this one.)
group-theory reference-request group-presentation combinatorial-group-theory
edited Dec 3 '18 at 0:52
Shaun
8,810113680
asked Jun 14 '14 at 8:44
James
7,01721426
Consider the presentation defined, for an integer $n > 1$, by
$$G_{n} = langle x, y mid xy^n = y^{n+1}x, yx^{n+1} = x^{n}yrangle .$$
The group defined by this presentation is trivial. Is it true that the minimum number of cosets that must be defined by the Todd-Coxeter process before any coincidences occur, when run on this presentation over the trivial subgroup, is bounded below by some (at least linear, probably worse) function of $n$, and is such a lower bound known? (In practice, this seems to behave quite badly.)
(A special case of this appears in a recent question, which is what prompted this one.)
group-theory reference-request group-presentation combinatorial-group-theory
group-theory reference-request group-presentation combinatorial-group-theory
edited Dec 3 '18 at 0:52
Shaun
8,810113680
asked Jun 14 '14 at 8:44
James
7,01721426
edited Dec 3 '18 at 0:52
Shaun
8,810113680
asked Jun 14 '14 at 8:44
James
7,01721426
edited Dec 3 '18 at 0:52
Shaun
8,810113680
edited Dec 3 '18 at 0:52
Shaun
8,810113680
edited Dec 3 '18 at 0:52
Shaun
8,810113680
8,810113680
asked Jun 14 '14 at 8:44
James
7,01721426
asked Jun 14 '14 at 8:44
James
7,01721426
asked Jun 14 '14 at 8:44
James
7,01721426
7,01721426
I have never heard of a theorem proving such a lower bound. You get much faster completion with Todd-Coxeter coset enumeration if you enumerate cosets of the subgroup $langle x rangle$ rather than the trivial subgroup. It completes very quickly even with $n=100$.
– Derek Holt
Jun 14 '14 at 19:50
@DerekHolt, yes you're right. It does still seem to blow up, though, just much more slowly. But I was mainly curious whether this was one of those examples that was known, or could be shown, to have necessarily bad behaviour. I have an example in my notes of the form $langle x,ymid x^ny^{n+1}, x^{n+1}y^{n+2}rangle$ where it is supposed to require at least $n$ cosets to be defined before any coincidence can occur in Todd-Coxeter. I thought this might be another such. Alas, I did not write down the reference. I thought it might have been your "Handbook", but I could not find it there now.
– James
Jun 17 '14 at 3:08
@DerekHolt. I guess it was obvious what I meant, but I notice that I failed to note that I was referring to an enumeration of the cosets of the trivial subgroup. I've fixed it.
– James
Jun 17 '14 at 3:10
add a comment |
I have never heard of a theorem proving such a lower bound. You get much faster completion with Todd-Coxeter coset enumeration if you enumerate cosets of the subgroup $langle x rangle$ rather than the trivial subgroup. It completes very quickly even with $n=100$.
– Derek Holt
Jun 14 '14 at 19:50
@DerekHolt, yes you're right. It does still seem to blow up, though, just much more slowly. But I was mainly curious whether this was one of those examples that was known, or could be shown, to have necessarily bad behaviour. I have an example in my notes of the form $langle x,ymid x^ny^{n+1}, x^{n+1}y^{n+2}rangle$ where it is supposed to require at least $n$ cosets to be defined before any coincidence can occur in Todd-Coxeter. I thought this might be another such. Alas, I did not write down the reference. I thought it might have been your "Handbook", but I could not find it there now.
– James
Jun 17 '14 at 3:08
@DerekHolt. I guess it was obvious what I meant, but I notice that I failed to note that I was referring to an enumeration of the cosets of the trivial subgroup. I've fixed it.
– James
Jun 17 '14 at 3:10
I have never heard of a theorem proving such a lower bound. You get much faster completion with Todd-Coxeter coset enumeration if you enumerate cosets of the subgroup $langle x rangle$ rather than the trivial subgroup. It completes very quickly even with $n=100$.
– Derek Holt
Jun 14 '14 at 19:50
I have never heard of a theorem proving such a lower bound. You get much faster completion with Todd-Coxeter coset enumeration if you enumerate cosets of the subgroup $langle x rangle$ rather than the trivial subgroup. It completes very quickly even with $n=100$.
– Derek Holt
Jun 14 '14 at 19:50
@DerekHolt, yes you're right. It does still seem to blow up, though, just much more slowly. But I was mainly curious whether this was one of those examples that was known, or could be shown, to have necessarily bad behaviour. I have an example in my notes of the form $langle x,ymid x^ny^{n+1}, x^{n+1}y^{n+2}rangle$ where it is supposed to require at least $n$ cosets to be defined before any coincidence can occur in Todd-Coxeter. I thought this might be another such. Alas, I did not write down the reference. I thought it might have been your "Handbook", but I could not find it there now.
– James
Jun 17 '14 at 3:08
@DerekHolt, yes you're right. It does still seem to blow up, though, just much more slowly. But I was mainly curious whether this was one of those examples that was known, or could be shown, to have necessarily bad behaviour. I have an example in my notes of the form $langle x,ymid x^ny^{n+1}, x^{n+1}y^{n+2}rangle$ where it is supposed to require at least $n$ cosets to be defined before any coincidence can occur in Todd-Coxeter. I thought this might be another such. Alas, I did not write down the reference. I thought it might have been your "Handbook", but I could not find it there now.
– James
Jun 17 '14 at 3:08
@DerekHolt. I guess it was obvious what I meant, but I notice that I failed to note that I was referring to an enumeration of the cosets of the trivial subgroup. I've fixed it.
– James
Jun 17 '14 at 3:10
@DerekHolt. I guess it was obvious what I meant, but I notice that I failed to note that I was referring to an enumeration of the cosets of the trivial subgroup. I've fixed it.
– James
Jun 17 '14 at 3:10
add a comment |
0
active
oldest
votes
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%2f833694%2fpresentations-that-make-the-todd-coxeter-algorithm-blow-up%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
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.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- 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.
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%2f833694%2fpresentations-that-make-the-todd-coxeter-algorithm-blow-up%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
I have never heard of a theorem proving such a lower bound. You get much faster completion with Todd-Coxeter coset enumeration if you enumerate cosets of the subgroup $langle x rangle$ rather than the trivial subgroup. It completes very quickly even with $n=100$.
– Derek Holt
Jun 14 '14 at 19:50
@DerekHolt, yes you're right. It does still seem to blow up, though, just much more slowly. But I was mainly curious whether this was one of those examples that was known, or could be shown, to have necessarily bad behaviour. I have an example in my notes of the form $langle x,ymid x^ny^{n+1}, x^{n+1}y^{n+2}rangle$ where it is supposed to require at least $n$ cosets to be defined before any coincidence can occur in Todd-Coxeter. I thought this might be another such. Alas, I did not write down the reference. I thought it might have been your "Handbook", but I could not find it there now.
– James
Jun 17 '14 at 3:08
@DerekHolt. I guess it was obvious what I meant, but I notice that I failed to note that I was referring to an enumeration of the cosets of the trivial subgroup. I've fixed it.
– James
Jun 17 '14 at 3:10