Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Largest Cyclic Subgroup of S_n

  1. May 26, 2010 #1
    I became interested in this question a few weeks ago, I couldnt 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?
     
  2. jcsd
  3. May 27, 2010 #2
    Last edited by a moderator: Apr 25, 2017
  4. May 27, 2010 #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 (Text):
    <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: May 28, 2010
  5. May 27, 2010 #4
    interesting

    i dont 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
     
  6. May 28, 2010 #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: May 28, 2010
  7. May 28, 2010 #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 (Text):
    <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>
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook