Largest Cyclic Subgroup of S_n

In summary, the conversation discusses the problem of finding a partition of a given number n into smaller numbers, such that the least common multiple of the smaller numbers is the maximum possible. This problem is equivalent to finding the largest order of an element in a specific permutation group. The conversation also mentions a paper and a program that attempt to solve this problem, but the program has some flaws and the problem becomes increasingly difficult for larger numbers.
  • #1
JoanBraidy
7
0
I became interested in this question a few weeks ago, I couldn't find much on it

basically I've realized it's equivalent to finding for each n a partition of n say

x_1,x_2,...,x_k such that x_1+x_2+...+x_k=n and lcm(x_1,...,x_k) is maximum

(because you can then take the subgroup <(123...x_1)(x_2...x_3)...(x_(k-1)...x_k)>

however computing this seems pretty much impossible

does anyone have any insights on this problem?
 
Physics news on Phys.org
  • #2
I don't think there is a closed form. Check out this paper: http://www.cs.ust.hk/mjg_lib/Library/Miller87.pdf
 
Last edited by a moderator:
  • #3
EDIT: Both the formula and programme in this post are incorrect (see sequel)

For the numbers [itex]P_n=\sum_{r=1}^{n}p_r[/itex] the largest order of an element in [itex]S_{P_n}[/itex] would be [itex]\Pi_{r=1}^{n}p_r[/itex]. It's also clear that the largest order for [itex]S_n[/itex] is monotonic non decreasing with [itex]n[/itex].

In the gaps between the [itex]P_n[/itex] the best places to distribute "remainder" between the existing cycles and how effective that can be will depend on both the remainder and the differences between [itex]p_{n+i}, i=1,2,\dots[/itex] and [itex]p_{n-i}, i=0,1,2,\dots[/itex]. Because of the awkwardness of the sequence of primes I would be surprised if a handy formula could be found for these.

I've put together a cheap and nasty javascript routine (below) to calculate the first few values, but this bows out after n=270 because the javascript integer accuracy is exceeded. Even if an unlimited accuracy routine for the arithmetic were included, I wouldn't hold out much hope of a BFI routine like this getting very far owing to the eventual size of the numbers if nothing else. (I haven' t attempted to quantify this either.)

Code: 
<script>
big=Math.pow(2,53)
toobig=false
function hcf(p,q){
  var u=Math.max(p,q)
  var v=Math.min(p,q)
  while(1){
    h=v
    v=u%v  
    if(!v)break
    u=h
  }
  return h  
}
function lcm(p,q){
  var wk=Math.min(p,q)/hcf(p,q)
  if(big/wk>=Math.max(p,q))return Math.max(p,q)*wk
  return 0
}
function cpy(u){
  if(!(u instanceof Array)){if(typeof(u)!='object')return u;wobbler()}
  var r=[]
  for(var i in u){
    r[i]=cpy(u[i])
  }
  return r
}
function part(n){
  if(!('done' in this))done=[]
  if(n in done)return cpy(done[n])
  var max=[n]
  max.v=n
  for(var i=n-1;i>=1;i--){
    var rest=n-i 
    rest=part(rest) 
    if(rest)rest.v=lcm(i,rest.v)             
    if(!(rest&&rest.v)){toobig=true;return null}
    if(rest.v>max.v){
      max.v=rest.v
      max.length=0
      var mx=0
      var idone=0
      for(var j=0;j<rest.length;j++){
        if(!idone&&i>=rest[j]){
          max[mx]=i
          mx++
          idone=1          
        }
        if(i!=rest[j]){
          max[mx]=rest[j]
          mx++
        }
      }
      if(!idone)max[mx]=i
    }    
  }
  done[n]=cpy(max) 
  return max
}
function doit(n,testlim,parm){
  if(!parm)parm=[100,10000]
  var pglim=parm[0]?parm[0]:100
  var gap=parm[1]?parm[1]:10000  
  if(!testlim)testlim=n
  var upper=n-(n%pglim)+pglim
  if(!('upto' in this))upto=document.getElementById('upto')
  if(!('blurb' in this))blurb=document.getElementById('blurb')
  var show=[]
  sp='&nbsp;';sp+=sp;sp+=sp;
  for(;n<Math.min(upper,testlim+1);n++){
    var maxpart=part(n)
    if(toobig){show[show.length]='<br>accuracy limit exceeded - terminating';break}
    show[show.length]=n+sp+maxpart.v+sp+'('+maxpart+')'
  }
  upto.innerHTML=n
  blurb.innerHTML=(n>pglim?'...<br>':'')+show.join('<br>')+(n<testlim?'<br>...':'')
  if(n<testlim&&!toobig)setTimeout('doit('+(n+1)+','+testlim+','+gap+')',gap)
}
</script>
<body onload="doit(1,1000000,[1000,1])">
<div>up to:</div>
<div id=upto></div>
<div>===========<br>n&nbsp;&nbsp;&nbsp;max_order&nbsp;&nbsp;&nbsp;max_cycle</div>
<div id=blurb></div>
 
Last edited:
  • #4
interesting

i don't get why it's obvious that s_sum(p_i) has productp_i as its largest order

couldnt there exist another partion of sum(p_i) whose lowest common multiple is bigger

say 2+3+5=10=7+3

but 2*3*5=30 and 7*3=21

so S_(7+3) would have largest order 21 according to you but

then it also has an element of order 30 just take (12)(345)(678910)

so anytime you can write n as a sum of primes 2 different ways this would probably

happen
 
  • #5
By [itex]p_i[/itex] I meant the [itex]i^{th}[/itex] prime, not just any old prime, so [itex]P_3=10[/itex] in that notation, and the max cycle order for [itex]10[/itex] would be given by [itex]{\Pi_{i=1}^{3}p_i=2.3.5=30}[/itex].

If [itex]n=14[/itex], [itex]P_3<n<P_4[/itex], so you have a "remainder" of [itex]4[/itex] to adjust the factors of [itex]2.3.5[/itex]. The best way is add [itex]2[/itex] to each of [itex]2,5[/itex] or, equivalently, [itex]1[/itex] to each of [itex]2,3[/itex] and [itex]2[/itex] to [itex]5[/itex]. In each case the new factors are relatively prime to the rest, but this rests partly on the fact that [itex]7-5=2[/itex], and similar relations between primes for higher numbers, so I wouldn't be optimistic about finding a simple formula for values of [itex]n[/itex] between the [itex]P_n[/itex].

But you're right that the formula is not obvious. In fact it breaks down for [itex]P_k[/itex] when [itex]k\geq 13[/itex], possibly before. In this case splitting [itex]2+41[/itex] as [itex]1+8+9+25[/itex] still gives factors that are relatively prime to anything except [itex]2,3,5[/itex], but [itex]1.8.9.25>2.41\times 3.5[/itex], hence [itex]{8.9.25\times 7.11.13\dots 37>2.3.5\dots 41}[/itex]. So all I can actually say is:
[itex]n\geq P_k\Rightarrow\text{max cycle length in }S_n\geq \Pi_{i=1}^{k}p_i[/itex]

and this bound will no doubt get progressively worse as n increases beyond [itex]{8+9+25+7+11+13+\dots +37=229}[/itex] (at most).

The programme posted is also flawed (I think for similar reasons).

Goes to show it would probably be a good idea if I thought before posting.
 
Last edited:
  • #6
I'm attaching a (hopefully) corrected version of the program previously posted. This version slows to a snails pace after about n=60 and would probably take all day to get up to the limit of javascript integer accuracy (I haven't tried it).

First difference from previous program is at n=29.

Challenge is to get it to run at reasonable speed or prove it never will.

Code: 
<script>
big=Math.pow(2,53)
toobig=false
done=[];done.maxix=1
show=[]
function hcf(p,q){
  var u=Math.max(p,q)
  var v=Math.min(p,q)
  while(h=v){    
    v=u%v  
    if(!v)break
    u=h
  }
  return h  
}
function lcm(p,q){
  var wk=Math.min(p,q)/hcf(p,q)
  if(big/wk>=Math.max(p,q))ret=Math.max(p,q)*wk
  else{
    toobig=true
    ret=0
  }
  return ret
}
function part(n){ 
  if(!done[n]){
    var cycs=[[n]]
    cycs[0].v=n
    cycs.max=0
    for(var i=n-1;i>=Math.floor((n+1)/2);i--){
      var icycs=part(i),jcycs=part(n-i)
      for(var ic in icycs)for(var jc in jcycs){
        if(ic!='max'&&jc!='max'){
          var icyc=icycs[ic],jcyc=jcycs[jc]
          var vtry=lcm(icyc.v,jcyc.v)            
          if(toobig)break;
          else{
            cycins=cycs.length
            for(var cx in cycs){
              if(cx!='max'){
                var cyc=cycs[cx]
                if(!(cyc.v%vtry)){cycins=undefined;break}              
                if(!(vtry%cyc.v)){cycins=cx;delete cycs[cx]}
              }
            }
            if(cycins!=undefined){ 
              if(cycins>done.maxix)done.maxix=cycins   
              if(!cycs[cycs.max]||cycs[cycs.max].v<vtry)cycs.max=cycins
              cyc=cycs[cycins]=[]
              cyc.v=vtry
              cyc.length=0
              var ix,jx; ix=jx=cx=0
              while(ix<icyc.length||jx<jcyc.length){
                if(ix<icyc.length&&(jx>=jcyc.length||icyc[ix]>=jcyc[jx]))cyc[cx++]=icyc[ix++]
                else cyc[cx++]=jcyc[jx++]
              }
            }
          }
        }    
      }
      if(toobig)break;
    }    
    done[n]=cycs    
  }
  return done[n]
}
function doit(n,lim,showix){
  var cyc=part(n)
  cyc=cyc[cyc.max]
  sp='&nbsp;';sp+=sp;sp+=sp;    
  if(toobig)show[show.length]='<br>accuracy limit exceeded - terminating'
  else show[show.length]=n+sp+cyc.v+sp+'('+cyc+')'    
  upto=document.getElementById('upto')
  upto.innerHTML=n+(showix?' max cycle index='+done.maxix:'')  
  blurb=document.getElementById('blurb')  
  blurb.innerHTML=show.join('<br>')
  n++
  if(!(toobig||(lim&&n>lim)))setTimeout('doit('+n+','+lim+','+showix+')',1)
}
</script>
<body onload="doit(1,1000)">
<div>up to:</div>
<div id=upto></div>
<div>===========<br>n&nbsp;&nbsp;&nbsp;max_order&nbsp;&nbsp;&nbsp;max_cycle</div>
<div id=blurb></div>
 

Related to Largest Cyclic Subgroup of S_n

What is the definition of the largest cyclic subgroup of S_n?

The largest cyclic subgroup of S_n is a subgroup of the symmetric group S_n that contains all the elements of S_n that are powers of a single element. It is also known as the maximum cyclic subgroup of S_n.

How is the largest cyclic subgroup of S_n represented?

The largest cyclic subgroup of S_n is typically represented as C_n, where n is the order of the subgroup. For example, the largest cyclic subgroup of S_4 would be denoted as C_4.

What is the order of the largest cyclic subgroup of S_n?

The order of the largest cyclic subgroup of S_n is equal to the order of the symmetric group S_n, which is n!. This means that the largest cyclic subgroup of S_n contains n! elements.

What are the generators of the largest cyclic subgroup of S_n?

The generators of the largest cyclic subgroup of S_n are the elements that can generate all the other elements in the subgroup through repeated multiplication. In the case of S_n, the generators are the n-cycles, which are elements that move n elements in the group and leave the rest fixed.

How does the largest cyclic subgroup of S_n relate to the symmetric group S_n?

The largest cyclic subgroup of S_n is a subgroup of the symmetric group S_n. It contains all the elements of S_n that are powers of a single element, and is therefore a subset of S_n. Additionally, the order of the largest cyclic subgroup of S_n is the same as the order of S_n, making it a significant subgroup in S_n.

Similar threads

B General explicit solution to polynomial interpolation
    • General Math
Replies
3
Views
836
I The Basic Area Problem (introduction to the topic of integrals)
    • Calculus
Replies
24
Views
2K
Showing that a subgroup of Sym(4) is isomorphic to D_8
    • Calculus and Beyond Homework Help
Replies
1
Views
953
I Some notes on stochastic physics
    • Classical Physics
Replies
0
Views
261
I Micromass' big October challenge
    • General Math
4
Replies
125
Views
17K
Challenge Intermediate Math Challenge - August 2018
    • Math Proof Training and Practice
Replies
20
Views
4K
Challenge Math Challenge - October 2021
    • Math Proof Training and Practice
2
Replies
61
Views
7K
Finding Riemann Sum for f(x)=3x^2+3
    • Calculus and Beyond Homework Help
Replies
1
Views
3K
Convergence rate (with unknown exact solution)
    • Calculus and Beyond Homework Help
Replies
6
Views
2K
Math Help for Finite Cyclic Group & Subgroups
    • Linear and Abstract Algebra
Replies
4
Views
2K

Hot Threads

Recent Insights

Back
Top