1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Prime-length cycles and their powers

  1. Jul 24, 2011 #1
    1. The problem statement, all variables and given/known data

    Suppose we have cyclic, prime-length [tex]\alpha = (a_{1}a_{2}...a_{s}).[/tex] Prove that every power of [tex]\alpha[/tex] is a cycle.

    2. Relevant equations

    None I can think of.

    3. The attempt at a solution

    I feel that I understand some of the intuition behind this problem. If any power of a cycle is not itself a cycle then it must either be the identity or the product of disjoint cycles. The only possibility here, then, would be a product of disjoint cycles. However, this seems to require that the original cycle not have a prime length, since one of the disjoint cycles must have an interval equivalent to a factor of the length of the original cycle.

    That was pretty garbled, so I'll use an example. Let [tex]\beta = (b_{1}b_{2}...b_{9}).[/tex] Here [tex]\beta^3[/tex] is a product of disjoint cycles [tex](b_{1}b_{4}b_{7})(b_{2}b_{5}b_{8})(b_{3}b_{6}b_{9}),[/tex] but note that this required an interval of 3, a factor of 9, in order for one disjoint cycle to "hit" the last element. Therefore any power of a prime-length cycle should be a cycle, since it can't be a product of disjoint cycles.

    But I'm kind of lost as to how to make this rigorous.
     
  2. jcsd
  3. Jul 25, 2011 #2
    64 reviews and no responses. Is my statement of the problem confusing? Perhaps my use of the term "cyclic" is wrong? I used it as a shorter way of saying "is a cycle".

    To elaborate on the difficulty I'm facing with making my proof rigorous: I'm unsure as to how to treat a general prime case. For example, if I assume that [tex]\alpha^k[/tex] is a power that isn't cyclic, then I might show that it cannot be a product of disjoint functions. However, I don't see how to write those disjoint functions and derive a contradiction due to uncertainty of what k is.
     
  4. Jul 25, 2011 #3

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    So lets say that [itex]\alpha[/itex] is a prime cycle. Let's say that [itex]\alpha^k[/itex] is the product of disjoint cycles? Then what is the order of [itex]\alpha^k[/itex]??
     
  5. Jul 25, 2011 #4
    Thanks for the response. My book doesn't include any definition for the order of a permutation that is the product of disjoint cycles. Length is just defined as the number of elements in a permutation. Looking around online, the order seems to be the least common multiple of the lengths of the disjoint cycles, which would make a prime order impossible. But this raises uncomfortable questions about the distinction between "length" and "order"?
     
  6. Jul 25, 2011 #5

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    The order is defined as the least number k such that [itex]\alpha^k=1[/itex]. Surely you must have seen this?
    And indeed, the order is the least common multiple of the lengths of a disjoint cycles.

    But what uncomfortable questions are there?
     
  7. Jul 25, 2011 #6
    I'm in Chapter 8 of Pinter's "Abstract Algebra". Order has been defined as the number of elements in a group, length has been defined as the number of elements in a cycle. But beyond that, I'm fairly sure there's nothing else so far. So bringing in these new definitions seems like "cheating".
     
  8. Jul 25, 2011 #7

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    OK, I see, order of elements is introduced in chapter 10.

    The only method I see that does not introduce order of elements is by brute force. That is, given a cycle of length p

    [tex]\alpha=(\alpha_1~\alpha_2~...~\alpha_p)[/tex]

    Compute directly now the powers of [itex]\alpha[/itex]. That is, try to find a formula and prove it by induction.

    So, try to form the first few powers, for example

    [tex]\alpha^2=(\alpha_1~\alpha_3~...~\alpha_{p-1}~\alpha_2~...~\alpha_p)[/tex]

    and see if you come up with something nice. (hint: thinking of the integers modulo p will be interesting here).
     
  9. Jul 26, 2011 #8
    My attempt at this is long, case-based and messy so I won't post it here, but I believe the crux of it is to use the fact that p is prime to go from a single (i.e. not disjoint and therefore a cycle) expression for case n to a likewise non-disjoint expression for case n+1 and therefore show that every power is a cycle?
     
  10. Jul 26, 2011 #9

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    Are you sure you didn't make it harder than it needed to be. The formula I was looking for is

    [tex]\alpha^k=(\alpha_k~\alpha_{2k}~\alpha_{3k}~... ~\alpha_{pk})[/tex]

    where the coefficient k, 2k, 3k, etc. are evaluated (mod p).
    I don't think this formula is hard to show by induction?

    The crux is that the cycle [itex]\alpha^k[/itex] is indeed of length p, and this uses the primality of p.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Prime-length cycles and their powers
  1. Odd length cycles (Replies: 4)

Loading...