Fdtxjr

How to make money from a browser who sees 5 seconds into the future of any web page?

Why is so much work done on numerical verification of the Riemann Hypothesis?

Taxes on Dividends in a Roth IRA

C++ check if statement can be evaluated constexpr

Strong empirical falsification of quantum mechanics based on vacuum energy density?

Make a Bowl of Alphabet Soup

Is there a RAID 0 Equivalent for RAM?

What is Cash Advance APR?

What kind of floor tile is this?

Why do ¬, ∀ and ∃ have the same precedence?

What does Apple's new App Store requirement mean

Change the color of a single dot in `ddot` symbol

The Digit Triangles

A variation to the phrase "hanging over my shoulders"

Why can't the Brexit deadlock in the UK parliament be solved with a plurality vote?

What to do when eye contact makes your coworker uncomfortable?

How do I tell my boss that I'm quitting soon, especially given that a colleague just left this week

awk assign to multiple variables at once

Why should universal income be universal?

Why Shazam when there is already Superman?

I found an audio circuit and I built it just fine, but I find it a bit too quiet. How do I amplify the output so that it is a bit louder?

A Trivial Diagnosis

Does the reader need to like the PoV character?

Is there a nicer/politer/more positive alternative for "negates"?

Maximal order of an element in a symmetric group

The Maximum possible order for an element $S_n$Order of cyclic subgroups in symmetric groupsWhat is maximal possible order of an element in $S_10$ ? Why?Upper bound on the order of elements in the symmetric groupWhat is the largest possible order of a permutation in $S_n$?What's the smallest exponent to give the identity in $S_n$?maximum order of an element in symmetric groupHow do I find the permutation with the highest order in a symmetric group?Finding the inverse of an element of $S_n$ and it's orderIf P is an nxn permutation matrix, is there an upper bound on k such that $P^k = I$?Permutation group and element of order equal $15$Some properties of $sigma,$ a $10-cycle.$How to show the Symmetric Group $S_4$ has no elements of order $6$.Finding the smallest positive integer $n$ such that $S_n$ contains an element of order 60.Checking if an element of a certain order is present in $S_n$How do I find the permutation with the highest order in a symmetric group?Proving that a permutation $sigma in S_n$ of order two is a product of disjoint 2-cyclesElement of Largest Order in $S_n$Show that $S_n$ has elements of order $p^t Longleftrightarrow n geq p ^t$, being $n, t$ positive integers and $p$ a prime number.Smallest positive integer $n$ such that $S_n$ has an element of order $2n$

17

11

$begingroup$

If we let $S_n$ denote the symmetric group on $n$ letters, then any element in $S_n$ can be written as the product of disjoint cycles, and for $k$ disjoint cycles, $sigma_1,sigma_2,ldots,sigma_k$, we have that $|sigma_1sigma_2ldotssigma_k|=operatornamelcm(sigma_1,sigma_2,ldots,sigma_k)$.

So to find the maximum order of an element in $S_n$, we need to maximize $operatornamelcm(sigma_1,sigma_2,ldots,sigma_k)$ given that $sum_i=1^k=n$. So my question:

How can we determine $|sigma_1|,|sigma_2|,ldots,|sigma_k|$ such that $sum_i=1^k=n$ and $operatornamelcm(sigma_1,sigma_2,ldots,sigma_k)$ is at a maximum?

Example

For $S_10$ we have that the maximal order of an element consists of 3 cycles of length 2,3, and 5 (or so I think) resulting in an element order of $operatornamelcm(2,3,5)=30$.

I'm certain that the all of the magnitudes will have to be relatively prime to achieve the greatest lcm, but other than this, I don't know how to proceed. Any thoughts or references? Thanks so much.

abstract-algebra group-theory optimization finite-groups symmetric-groups

share|cite|improve this question

edited Mar 14 at 17:38

Shaun

9,690113684

asked Oct 26 '12 at 0:00

JemmyJemmy

928923

$endgroup$

• 
  
  
  

  
  5
  

  
  
  
  
  
  

  
  $begingroup$
  I've wanted to know this for quite a while, ever since I noticed that $Z_6$ is a subgroup of $S_5$, so thanks for asking.
  $endgroup$
  – MJD
  Oct 26 '12 at 0:34
  
  

  
  
  
  

add a comment | 

17

11

$begingroup$

If we let $S_n$ denote the symmetric group on $n$ letters, then any element in $S_n$ can be written as the product of disjoint cycles, and for $k$ disjoint cycles, $sigma_1,sigma_2,ldots,sigma_k$, we have that $|sigma_1sigma_2ldotssigma_k|=operatornamelcm(sigma_1,sigma_2,ldots,sigma_k)$.

So to find the maximum order of an element in $S_n$, we need to maximize $operatornamelcm(sigma_1,sigma_2,ldots,sigma_k)$ given that $sum_i=1^k=n$. So my question:

How can we determine $|sigma_1|,|sigma_2|,ldots,|sigma_k|$ such that $sum_i=1^k=n$ and $operatornamelcm(sigma_1,sigma_2,ldots,sigma_k)$ is at a maximum?

Example

For $S_10$ we have that the maximal order of an element consists of 3 cycles of length 2,3, and 5 (or so I think) resulting in an element order of $operatornamelcm(2,3,5)=30$.

I'm certain that the all of the magnitudes will have to be relatively prime to achieve the greatest lcm, but other than this, I don't know how to proceed. Any thoughts or references? Thanks so much.

abstract-algebra group-theory optimization finite-groups symmetric-groups

share|cite|improve this question

edited Mar 14 at 17:38

Shaun

9,690113684

asked Oct 26 '12 at 0:00

JemmyJemmy

928923

$endgroup$

• 
  
  
  

  
  5
  

  
  
  
  
  
  

  
  $begingroup$
  I've wanted to know this for quite a while, ever since I noticed that $Z_6$ is a subgroup of $S_5$, so thanks for asking.
  $endgroup$
  – MJD
  Oct 26 '12 at 0:34
  
  

  
  
  
  

add a comment | 

$begingroup$

If we let $S_n$ denote the symmetric group on $n$ letters, then any element in $S_n$ can be written as the product of disjoint cycles, and for $k$ disjoint cycles, $sigma_1,sigma_2,ldots,sigma_k$, we have that $|sigma_1sigma_2ldotssigma_k|=operatornamelcm(sigma_1,sigma_2,ldots,sigma_k)$.

So to find the maximum order of an element in $S_n$, we need to maximize $operatornamelcm(sigma_1,sigma_2,ldots,sigma_k)$ given that $sum_i=1^k=n$. So my question:

How can we determine $|sigma_1|,|sigma_2|,ldots,|sigma_k|$ such that $sum_i=1^k=n$ and $operatornamelcm(sigma_1,sigma_2,ldots,sigma_k)$ is at a maximum?

Example

For $S_10$ we have that the maximal order of an element consists of 3 cycles of length 2,3, and 5 (or so I think) resulting in an element order of $operatornamelcm(2,3,5)=30$.

I'm certain that the all of the magnitudes will have to be relatively prime to achieve the greatest lcm, but other than this, I don't know how to proceed. Any thoughts or references? Thanks so much.

abstract-algebra group-theory optimization finite-groups symmetric-groups

share|cite|improve this question

edited Mar 14 at 17:38

Shaun

9,690113684

asked Oct 26 '12 at 0:00

JemmyJemmy

928923

$endgroup$

share|cite|improve this question

edited Mar 14 at 17:38

Shaun

9,690113684

asked Oct 26 '12 at 0:00

JemmyJemmy

928923

share|cite|improve this question

edited Mar 14 at 17:38

Shaun

9,690113684

asked Oct 26 '12 at 0:00

JemmyJemmy

928923

edited Mar 14 at 17:38

Shaun

9,690113684

edited Mar 14 at 17:38

Shaun

9,690113684

asked Oct 26 '12 at 0:00

JemmyJemmy

928923

asked Oct 26 '12 at 0:00

JemmyJemmy

928923

3 Answers
3

active

oldest

votes

16

$begingroup$

This is Landau's Function.

Asymptotic estimates are known.

share|cite|improve this answer

answered Oct 26 '12 at 0:16

André NicolasAndré Nicolas

454k36432819

$endgroup$

add a comment | 

6

$begingroup$

André has already provided the name and the link; here's a derivation of the bound $g(n)ltmathrm e^n/mathrm e$ in the article. If we could choose all the $l_i:=|sigma_i|$ freely, only constrained by their sum $n$, we'd want to find the stationary points of the objective function

$$
prod_il_i-lambdasum_il_i;.
$$

Differentiating with respect to $sigma_j$ yields

$$
prod_il_i=lambda l_j;,
$$

so not surprisingly the only stationary point is where all the $l_i$ are equal. Then we can optimize their number $k$ by writing $l_i=n/k$, and we want to maximize

$$
left(frac nkright)^k;,
$$

or equivalently

$$
logleft(frac nkright)^k=kleft(log n-log kright);.
$$

Taking the derivative with respect to $k$ yields $log n-log k=1$ and thus $k=n/mathrm e$, so ideally we'd want all the $l_i$ to be $mathrm e$. In that case the product would be $mathrm e^n/mathrm e$, and the constraints that the $l_i$ have to be coprime integers can only lower that value (quite considerably, as the asymptotic result in the article shows).

This calculation also shows that $mathrm e$ would be the optimal radix for a Fast Fourier Transform.

share|cite|improve this answer

answered Oct 26 '12 at 0:36

jorikijoriki

171k10189350

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Thank you for this derivation. It is very helpful.
  $endgroup$
  – Jemmy
  Oct 26 '12 at 10:06
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @Jeremy: You're welcome!
  $endgroup$
  – joriki
  Oct 26 '12 at 10:11
  

  
  
  
  

add a comment | 

2

$begingroup$

For more detail you can see this paper.

The maximum order of an element of finite symmetric group by William Miller, American Mathematical Monthly, page 497-506.

share|cite|improve this answer

edited Dec 30 '13 at 20:36

user26857

answered Dec 30 '13 at 18:12

Babak MiraftabBabak Miraftab

5,39912249

$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
);



);

draft saved

draft discarded

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

Name

Email

Required, but never shown

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f221211%2fmaximal-order-of-an-element-in-a-symmetric-group%23new-answer', 'question_page');

);

Post as a guest

Name

Email

Required, but never shown

16

$begingroup$

This is Landau's Function.

Asymptotic estimates are known.

share|cite|improve this answer

answered Oct 26 '12 at 0:16

André NicolasAndré Nicolas

454k36432819

$endgroup$

add a comment | 

16

$begingroup$

This is Landau's Function.

Asymptotic estimates are known.

share|cite|improve this answer

answered Oct 26 '12 at 0:16

André NicolasAndré Nicolas

454k36432819

$endgroup$

add a comment | 

$begingroup$

This is Landau's Function.

Asymptotic estimates are known.

share|cite|improve this answer

answered Oct 26 '12 at 0:16

André NicolasAndré Nicolas

454k36432819

$endgroup$

share|cite|improve this answer

answered Oct 26 '12 at 0:16

André NicolasAndré Nicolas

454k36432819

answered Oct 26 '12 at 0:16

André NicolasAndré Nicolas

454k36432819

answered Oct 26 '12 at 0:16

André NicolasAndré Nicolas

454k36432819

6

$begingroup$

André has already provided the name and the link; here's a derivation of the bound $g(n)ltmathrm e^n/mathrm e$ in the article. If we could choose all the $l_i:=|sigma_i|$ freely, only constrained by their sum $n$, we'd want to find the stationary points of the objective function

$$
prod_il_i-lambdasum_il_i;.
$$

Differentiating with respect to $sigma_j$ yields

$$
prod_il_i=lambda l_j;,
$$

so not surprisingly the only stationary point is where all the $l_i$ are equal. Then we can optimize their number $k$ by writing $l_i=n/k$, and we want to maximize

$$
left(frac nkright)^k;,
$$

or equivalently

$$
logleft(frac nkright)^k=kleft(log n-log kright);.
$$

Taking the derivative with respect to $k$ yields $log n-log k=1$ and thus $k=n/mathrm e$, so ideally we'd want all the $l_i$ to be $mathrm e$. In that case the product would be $mathrm e^n/mathrm e$, and the constraints that the $l_i$ have to be coprime integers can only lower that value (quite considerably, as the asymptotic result in the article shows).

This calculation also shows that $mathrm e$ would be the optimal radix for a Fast Fourier Transform.

share|cite|improve this answer

answered Oct 26 '12 at 0:36

jorikijoriki

171k10189350

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Thank you for this derivation. It is very helpful.
  $endgroup$
  – Jemmy
  Oct 26 '12 at 10:06
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @Jeremy: You're welcome!
  $endgroup$
  – joriki
  Oct 26 '12 at 10:11
  

  
  
  
  

add a comment | 

6

$begingroup$

André has already provided the name and the link; here's a derivation of the bound $g(n)ltmathrm e^n/mathrm e$ in the article. If we could choose all the $l_i:=|sigma_i|$ freely, only constrained by their sum $n$, we'd want to find the stationary points of the objective function

$$
prod_il_i-lambdasum_il_i;.
$$

Differentiating with respect to $sigma_j$ yields

$$
prod_il_i=lambda l_j;,
$$

so not surprisingly the only stationary point is where all the $l_i$ are equal. Then we can optimize their number $k$ by writing $l_i=n/k$, and we want to maximize

$$
left(frac nkright)^k;,
$$

or equivalently

$$
logleft(frac nkright)^k=kleft(log n-log kright);.
$$

Taking the derivative with respect to $k$ yields $log n-log k=1$ and thus $k=n/mathrm e$, so ideally we'd want all the $l_i$ to be $mathrm e$. In that case the product would be $mathrm e^n/mathrm e$, and the constraints that the $l_i$ have to be coprime integers can only lower that value (quite considerably, as the asymptotic result in the article shows).

This calculation also shows that $mathrm e$ would be the optimal radix for a Fast Fourier Transform.

share|cite|improve this answer

answered Oct 26 '12 at 0:36

jorikijoriki

171k10189350

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Thank you for this derivation. It is very helpful.
  $endgroup$
  – Jemmy
  Oct 26 '12 at 10:06
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @Jeremy: You're welcome!
  $endgroup$
  – joriki
  Oct 26 '12 at 10:11
  

  
  
  
  

add a comment | 

$begingroup$

André has already provided the name and the link; here's a derivation of the bound $g(n)ltmathrm e^n/mathrm e$ in the article. If we could choose all the $l_i:=|sigma_i|$ freely, only constrained by their sum $n$, we'd want to find the stationary points of the objective function

$$
prod_il_i-lambdasum_il_i;.
$$

Differentiating with respect to $sigma_j$ yields

$$
prod_il_i=lambda l_j;,
$$

so not surprisingly the only stationary point is where all the $l_i$ are equal. Then we can optimize their number $k$ by writing $l_i=n/k$, and we want to maximize

$$
left(frac nkright)^k;,
$$

or equivalently

$$
logleft(frac nkright)^k=kleft(log n-log kright);.
$$

Taking the derivative with respect to $k$ yields $log n-log k=1$ and thus $k=n/mathrm e$, so ideally we'd want all the $l_i$ to be $mathrm e$. In that case the product would be $mathrm e^n/mathrm e$, and the constraints that the $l_i$ have to be coprime integers can only lower that value (quite considerably, as the asymptotic result in the article shows).

This calculation also shows that $mathrm e$ would be the optimal radix for a Fast Fourier Transform.

share|cite|improve this answer

answered Oct 26 '12 at 0:36

jorikijoriki

171k10189350

$endgroup$

share|cite|improve this answer

answered Oct 26 '12 at 0:36

jorikijoriki

171k10189350

answered Oct 26 '12 at 0:36

jorikijoriki

171k10189350

answered Oct 26 '12 at 0:36

jorikijoriki

171k10189350

2

$begingroup$

For more detail you can see this paper.

The maximum order of an element of finite symmetric group by William Miller, American Mathematical Monthly, page 497-506.

share|cite|improve this answer

edited Dec 30 '13 at 20:36

user26857

answered Dec 30 '13 at 18:12

Babak MiraftabBabak Miraftab

5,39912249

$endgroup$

add a comment | 

2

$begingroup$

For more detail you can see this paper.

The maximum order of an element of finite symmetric group by William Miller, American Mathematical Monthly, page 497-506.

share|cite|improve this answer

edited Dec 30 '13 at 20:36

user26857

answered Dec 30 '13 at 18:12

Babak MiraftabBabak Miraftab

5,39912249

$endgroup$

add a comment | 

$begingroup$

For more detail you can see this paper.

The maximum order of an element of finite symmetric group by William Miller, American Mathematical Monthly, page 497-506.

share|cite|improve this answer

edited Dec 30 '13 at 20:36

user26857

answered Dec 30 '13 at 18:12

Babak MiraftabBabak Miraftab

5,39912249

$endgroup$

share|cite|improve this answer

edited Dec 30 '13 at 20:36

user26857

answered Dec 30 '13 at 18:12

Babak MiraftabBabak Miraftab

5,39912249

answered Dec 30 '13 at 18:12

Babak MiraftabBabak Miraftab

5,39912249

answered Dec 30 '13 at 18:12

Babak MiraftabBabak Miraftab

5,39912249