List of symmetric group elements from the usual presentation
$begingroup$
Let $S_n$ be the symmetric group of $n$ letters, generated by elements $s_i$ for $ 1 leq i leq n -1$ with relations $s_is_{i+1}s_i = s_{i+1}s_is_{i+1} $ and $s_i,s_j$ commute if $|i-j| > 1$.
I would like to have an algorithm to get a list $w_1, dots, w_{n!}$ which enumerates $S_n$ so that each $w_k$ can be expressed as a product in $s_1, dots, s_{n-1}$.
For example for $S_3$ such a list is given by $1, s_1, s_2, s_1s_2, s_2s_1, s_1s_2s_1$. A list for $S_4$ or $S_5$ would be already nice.
combinatorics group-theory symmetric-groups
asked Jan 16 at 23:48
studentstudent
1268
$endgroup$
add a comment |
$begingroup$
Let $S_n$ be the symmetric group of $n$ letters, generated by elements $s_i$ for $ 1 leq i leq n -1$ with relations $s_is_{i+1}s_i = s_{i+1}s_is_{i+1} $ and $s_i,s_j$ commute if $|i-j| > 1$.
I would like to have an algorithm to get a list $w_1, dots, w_{n!}$ which enumerates $S_n$ so that each $w_k$ can be expressed as a product in $s_1, dots, s_{n-1}$.
For example for $S_3$ such a list is given by $1, s_1, s_2, s_1s_2, s_2s_1, s_1s_2s_1$. A list for $S_4$ or $S_5$ would be already nice.
combinatorics group-theory symmetric-groups
asked Jan 16 at 23:48
studentstudent
1268
$endgroup$
add a comment |
$begingroup$
Let $S_n$ be the symmetric group of $n$ letters, generated by elements $s_i$ for $ 1 leq i leq n -1$ with relations $s_is_{i+1}s_i = s_{i+1}s_is_{i+1} $ and $s_i,s_j$ commute if $|i-j| > 1$.
I would like to have an algorithm to get a list $w_1, dots, w_{n!}$ which enumerates $S_n$ so that each $w_k$ can be expressed as a product in $s_1, dots, s_{n-1}$.
For example for $S_3$ such a list is given by $1, s_1, s_2, s_1s_2, s_2s_1, s_1s_2s_1$. A list for $S_4$ or $S_5$ would be already nice.
combinatorics group-theory symmetric-groups
asked Jan 16 at 23:48
studentstudent
1268
$endgroup$
Let $S_n$ be the symmetric group of $n$ letters, generated by elements $s_i$ for $ 1 leq i leq n -1$ with relations $s_is_{i+1}s_i = s_{i+1}s_is_{i+1} $ and $s_i,s_j$ commute if $|i-j| > 1$.
I would like to have an algorithm to get a list $w_1, dots, w_{n!}$ which enumerates $S_n$ so that each $w_k$ can be expressed as a product in $s_1, dots, s_{n-1}$.
For example for $S_3$ such a list is given by $1, s_1, s_2, s_1s_2, s_2s_1, s_1s_2s_1$. A list for $S_4$ or $S_5$ would be already nice.
combinatorics group-theory symmetric-groups
combinatorics group-theory symmetric-groups
asked Jan 16 at 23:48
studentstudent
1268
asked Jan 16 at 23:48
studentstudent
1268
asked Jan 16 at 23:48
studentstudent
1268
asked Jan 16 at 23:48
studentstudent
1268
asked Jan 16 at 23:48
studentstudent
1268
1268
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
For any $1le ile jle n$, let
$$
t^j_i=s_{j-1}s_{j-2}cdots s_i,
$$
with the convention that $t^i_i=1$. Any permutation in $S_n$ can be represented uniquely in the form
$$
t^1_{a(1)}t^2_{a(2)}dots t^n_{a(n)}
$$
where $a(1),a(2),dots,a(n)$ is a list of integers satisfying $1le a(i)le i$. Unpacking each $t^j_i$, you get an expression for each element of $S_n$ using the letters $s_i$.
The interpretation is that $t_{i}^j$ is a permutation which moves the item at slot $i$ to slot $j$, without disturbing any of the items above slot $j$.
answered Jan 17 at 1:11
Mike EarnestMike Earnest
22.6k12051
$endgroup$
add a comment |
$begingroup$
If you have the list of words (representing functions) for the $n$ group,
$$quad w_1, w_2, dots, w_{n!}$$
you can mechanically generate the words for the $n+1$ group using two facts:
$quad text{Every (new) permutation has the form } w circ tau text{ for a transposition } tau = (k ; ; n+1)$
$quad text{Every transposition can be written as a product of adjacent transpositions}$
We will use this theory to get the words for $S_4$.
To organize the work, we created a google sheet; here are the $24$ elements in $S_4$ ($s_0$ is the identity):
We did not work on representing these words with the shortest length. For example, the word in cell $text{C7}$ can obviously be reduced in length.
I am not aware of the theory that would give us an algorithm to do this.
answered Jan 17 at 14:20
CopyPasteItCopyPasteIt
4,1631628
$endgroup$
add a 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%2f3076439%2flist-of-symmetric-group-elements-from-the-usual-presentation%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
For any $1le ile jle n$, let
$$
t^j_i=s_{j-1}s_{j-2}cdots s_i,
$$
with the convention that $t^i_i=1$. Any permutation in $S_n$ can be represented uniquely in the form
$$
t^1_{a(1)}t^2_{a(2)}dots t^n_{a(n)}
$$
where $a(1),a(2),dots,a(n)$ is a list of integers satisfying $1le a(i)le i$. Unpacking each $t^j_i$, you get an expression for each element of $S_n$ using the letters $s_i$.
The interpretation is that $t_{i}^j$ is a permutation which moves the item at slot $i$ to slot $j$, without disturbing any of the items above slot $j$.
answered Jan 17 at 1:11
Mike EarnestMike Earnest
22.6k12051
$endgroup$
add a comment |
$begingroup$
For any $1le ile jle n$, let
$$
t^j_i=s_{j-1}s_{j-2}cdots s_i,
$$
with the convention that $t^i_i=1$. Any permutation in $S_n$ can be represented uniquely in the form
$$
t^1_{a(1)}t^2_{a(2)}dots t^n_{a(n)}
$$
where $a(1),a(2),dots,a(n)$ is a list of integers satisfying $1le a(i)le i$. Unpacking each $t^j_i$, you get an expression for each element of $S_n$ using the letters $s_i$.
The interpretation is that $t_{i}^j$ is a permutation which moves the item at slot $i$ to slot $j$, without disturbing any of the items above slot $j$.
answered Jan 17 at 1:11
Mike EarnestMike Earnest
22.6k12051
$endgroup$
add a comment |
$begingroup$
For any $1le ile jle n$, let
$$
t^j_i=s_{j-1}s_{j-2}cdots s_i,
$$
with the convention that $t^i_i=1$. Any permutation in $S_n$ can be represented uniquely in the form
$$
t^1_{a(1)}t^2_{a(2)}dots t^n_{a(n)}
$$
where $a(1),a(2),dots,a(n)$ is a list of integers satisfying $1le a(i)le i$. Unpacking each $t^j_i$, you get an expression for each element of $S_n$ using the letters $s_i$.
The interpretation is that $t_{i}^j$ is a permutation which moves the item at slot $i$ to slot $j$, without disturbing any of the items above slot $j$.
answered Jan 17 at 1:11
Mike EarnestMike Earnest
22.6k12051
$endgroup$
For any $1le ile jle n$, let
$$
t^j_i=s_{j-1}s_{j-2}cdots s_i,
$$
with the convention that $t^i_i=1$. Any permutation in $S_n$ can be represented uniquely in the form
$$
t^1_{a(1)}t^2_{a(2)}dots t^n_{a(n)}
$$
where $a(1),a(2),dots,a(n)$ is a list of integers satisfying $1le a(i)le i$. Unpacking each $t^j_i$, you get an expression for each element of $S_n$ using the letters $s_i$.
The interpretation is that $t_{i}^j$ is a permutation which moves the item at slot $i$ to slot $j$, without disturbing any of the items above slot $j$.
answered Jan 17 at 1:11
Mike EarnestMike Earnest
22.6k12051
answered Jan 17 at 1:11
Mike EarnestMike Earnest
22.6k12051
answered Jan 17 at 1:11
Mike EarnestMike Earnest
22.6k12051
answered Jan 17 at 1:11
Mike EarnestMike Earnest
22.6k12051
22.6k12051
add a comment |
add a comment |
$begingroup$
If you have the list of words (representing functions) for the $n$ group,
$$quad w_1, w_2, dots, w_{n!}$$
you can mechanically generate the words for the $n+1$ group using two facts:
$quad text{Every (new) permutation has the form } w circ tau text{ for a transposition } tau = (k ; ; n+1)$
$quad text{Every transposition can be written as a product of adjacent transpositions}$
We will use this theory to get the words for $S_4$.
To organize the work, we created a google sheet; here are the $24$ elements in $S_4$ ($s_0$ is the identity):
We did not work on representing these words with the shortest length. For example, the word in cell $text{C7}$ can obviously be reduced in length.
I am not aware of the theory that would give us an algorithm to do this.
answered Jan 17 at 14:20
CopyPasteItCopyPasteIt
4,1631628
$endgroup$
add a comment |
$begingroup$
If you have the list of words (representing functions) for the $n$ group,
$$quad w_1, w_2, dots, w_{n!}$$
you can mechanically generate the words for the $n+1$ group using two facts:
$quad text{Every (new) permutation has the form } w circ tau text{ for a transposition } tau = (k ; ; n+1)$
$quad text{Every transposition can be written as a product of adjacent transpositions}$
We will use this theory to get the words for $S_4$.
To organize the work, we created a google sheet; here are the $24$ elements in $S_4$ ($s_0$ is the identity):
We did not work on representing these words with the shortest length. For example, the word in cell $text{C7}$ can obviously be reduced in length.
I am not aware of the theory that would give us an algorithm to do this.
answered Jan 17 at 14:20
CopyPasteItCopyPasteIt
4,1631628
$endgroup$
add a comment |
$begingroup$
If you have the list of words (representing functions) for the $n$ group,
$$quad w_1, w_2, dots, w_{n!}$$
you can mechanically generate the words for the $n+1$ group using two facts:
$quad text{Every (new) permutation has the form } w circ tau text{ for a transposition } tau = (k ; ; n+1)$
$quad text{Every transposition can be written as a product of adjacent transpositions}$
We will use this theory to get the words for $S_4$.
To organize the work, we created a google sheet; here are the $24$ elements in $S_4$ ($s_0$ is the identity):
We did not work on representing these words with the shortest length. For example, the word in cell $text{C7}$ can obviously be reduced in length.
I am not aware of the theory that would give us an algorithm to do this.
answered Jan 17 at 14:20
CopyPasteItCopyPasteIt
4,1631628
$endgroup$
If you have the list of words (representing functions) for the $n$ group,
$$quad w_1, w_2, dots, w_{n!}$$
you can mechanically generate the words for the $n+1$ group using two facts:
$quad text{Every (new) permutation has the form } w circ tau text{ for a transposition } tau = (k ; ; n+1)$
$quad text{Every transposition can be written as a product of adjacent transpositions}$
We will use this theory to get the words for $S_4$.
To organize the work, we created a google sheet; here are the $24$ elements in $S_4$ ($s_0$ is the identity):
We did not work on representing these words with the shortest length. For example, the word in cell $text{C7}$ can obviously be reduced in length.
I am not aware of the theory that would give us an algorithm to do this.
answered Jan 17 at 14:20
CopyPasteItCopyPasteIt
4,1631628
answered Jan 17 at 14:20
CopyPasteItCopyPasteIt
4,1631628
answered Jan 17 at 14:20
CopyPasteItCopyPasteIt
4,1631628
answered Jan 17 at 14:20
CopyPasteItCopyPasteIt
4,1631628
4,1631628
add a comment |
add a 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%2f3076439%2flist-of-symmetric-group-elements-from-the-usual-presentation%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
