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

Homework Help: 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
    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
    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
    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
    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.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook