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

Singer Cycles

  1. Aug 6, 2008 #1
    Assume GL(n,q) is the general linear group of nxn matrices with entries in the finite field with q elements. Define a Singer Cycle to be an element of GL(n,q) of order (q^n)-1. How can we show that such an element always exists? That is, for all n and q.

    Thanx in advance.
     
  2. jcsd
  3. Aug 6, 2008 #2

    morphism

    User Avatar
    Science Advisor
    Homework Helper

    Hint 1: The multiplicative group of a finite field is cyclic.

    Hint 2: GF(q^n)* can be embedded into GL(n,q).
     
  4. Aug 6, 2008 #3
    I am aware of the first hint. For the second, by an embedding you mean an injective homomorphism? I would think that if someone could find such a map, say f, then f(a) would be the element we are looking for, where a is a generator of GF(q^n)*. Of course it should be established that f is order preserving. Am I correct?
     
  5. Aug 6, 2008 #4

    morphism

    User Avatar
    Science Advisor
    Homework Helper

  6. Aug 6, 2008 #5
    Take T:GF(q^n)-->GF(q^n), with T=ax, GF(q^n)*=<a>. Then there exists a basis {e_1,...,e_n} of GF(q^n) over GF(q) such that Te_j=Σa_ije_i and T corresponds isomorphically to a matrix A=[a_ij] in GL(n,q) which must necessarily have order q^n-1. Does that sound correct?
     
  7. Aug 7, 2008 #6

    morphism

    User Avatar
    Science Advisor
    Homework Helper

    Yes -- good work! (Just make sure you notice that T is invertible.)
     
  8. Aug 7, 2008 #7
    Allright, I'd like to take it a step further:how about a singer cycle's minimal polynomial? It seems that its degree is always n, but I can't prove it. Any hints? Thank you for your help morphism.
     
  9. Aug 7, 2008 #8

    morphism

    User Avatar
    Science Advisor
    Homework Helper

    Do you have any reason to believe that is always the case? I don't immediately see how this can be proved. I actually think it may be false. If you can find a natural number n and a prime p such that the following inequality holds

    [tex]\sum_{d | n} \mu(d) p^{n/d} < \varphi(p^n - 1),[/tex]

    where [itex]\mu[/itex] is the Mobius function and [itex]\varphi[/itex] is the Euler totient function, then I can explain how this can be used to produce a counterexample. I haven't given this much thought, so it's very probable that this inequality may never hold.

    I'll try to think about this problem some more later.
     
  10. Aug 7, 2008 #9

    morphism

    User Avatar
    Science Advisor
    Homework Helper

    Ignore my previous post -- the term minimal polynomial slightly threw me off.

    What you want to do is show that every Single cycle A arises as above, i.e. as a generator of GF(q^n)*. Then, if m(t) is the minimal polynomial of A, we can see that GF(q)[t]/<m(t)> is GF(q^n). Hence deg(m(t)) = [GF(q^n) : GF(q)] = n.

    [Incidentally I think this will prove that [itex]\varphi(p^n - 1) \leq \sum_{d | n} \mu(d) p^{n/d}[/itex] for all n and p.]
     
  11. Aug 7, 2008 #10

    morphism

    User Avatar
    Science Advisor
    Homework Helper

    Some googling brought up this paper. You might find it useful.
     
  12. Aug 8, 2008 #11
    Yeah you are right! At some point I thought of that, but for some reason I rejected it.. I'll look more into this. Btw taking the rational canonical form, you get that every singer cycle is similar to a unique companion matrix, which implies that there are as many singer cycles as irreducible polynomials of degree n over GF(q). Right? Thanx for the paper.
     
  13. Aug 12, 2008 #12
    That's not quite right.. Any ideas about how many singer cycles there are?
     
  14. Sep 18, 2008 #13
    But, how do we know that every singer cycle in GL(n,q) corresponds to a linear transformation T=ax, where a is a primitive element?
     
  15. Sep 19, 2008 #14

    morphism

    User Avatar
    Science Advisor
    Homework Helper

    Just look at how GL(n,q) acts on GF(q^n)*.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Singer Cycles
  1. Counting cycles in S_5 (Replies: 1)

  2. Power of a cycle (Replies: 4)

  3. Disjoint Cycles (Replies: 5)

Loading...