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

Primitive polynomials

  1. Aug 17, 2008 #1
    Can anyone tell me how to find the exact number of primitive polynomials of degree n over a finite field F_q? I believe the answer is φ(q^n-1)/n, but I cannot find a proof of this.

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

    morphism

    User Avatar
    Science Advisor
    Homework Helper

    What's your definition of a primitive polynomial of degree n?
     
  4. Aug 17, 2008 #3
    It's an irreducible polynomial whose roots generate F_q^n. So for example f(x)=x^4 + x^3 + x^2 +x + 1 in F_16[x] is not primitive (a root c of f(x) has order 5), while g(x)=x^4 + x + 1 is (a root c of g(x) has necessarily order 15).
     
  5. Aug 17, 2008 #4

    morphism

    User Avatar
    Science Advisor
    Homework Helper

    OK. And do you know how to many generators F_q^n has?
     
  6. Aug 17, 2008 #5
    Yeah, φ(q^n-1).
     
  7. Aug 17, 2008 #6

    morphism

    User Avatar
    Science Advisor
    Homework Helper

    Now put 2 and 2 together. (Some field theory will be helpful.)
     
  8. Aug 17, 2008 #7
    Every primitive polynomial produces n distinct roots in the extension field that are primitive elements. Hence #(primitive polynomials)*n=φ(q^n-1). But is this a formal argument? I don't feel so much at ease with field theory..

    P.S. 2+2=4
     
  9. Aug 17, 2008 #8

    morphism

    User Avatar
    Science Advisor
    Homework Helper

    Yes, that's a formal argument, provided you also note that every generator of F_q^n corresponds to a primitive polynomial of degree n in F_q[x] (namely its minimal polynomial).
     
  10. Aug 18, 2008 #9
    Allright. So we can say that elements of order q^n-1 in GL(n,q) can be divided in φ(q^n-1) conjugacy classes, to combine results with the Singer cycles thread. What I want to do is find the order of each conjugacy class. Any ideas?
     
  11. Aug 18, 2008 #10

    morphism

    User Avatar
    Science Advisor
    Homework Helper

    What's the reasoning behind that?
     
  12. Aug 18, 2008 #11
    I'm sorry; I meant φ(q^n-1)/n classes. the companion matrices that correspond to primitive polynomials of degree n have order q^n-1 and Singer cycles that have the same minimal polynomial necessarily lie in the same conjugacy class.
     
  13. Aug 18, 2008 #12

    morphism

    User Avatar
    Science Advisor
    Homework Helper

    Is that obvious? I mean, there are two notions of 'conjugacy' here: conjugacy in the sense of field theory in F_q^n, and conjugacy in the sense of group theory in GL(n,q). Do they coincide?
     
  14. Aug 18, 2008 #13
    I think it becomes obvious if you notice that a Singer cycle cannot have an irreducible polynomial that is not primitive as a minimal polynomial. For example, can f(x)=x^4 + x^3 + x^2 +x + 1 in F_16[x] be the minimal polynomial of a singer cycle in GL(4,2)?
     
  15. Aug 19, 2008 #14
    By the way, I think it's true that no element in GL(n,q) has order that exceeds q^n-1. An thoughts on this?
     
  16. Aug 19, 2008 #15

    morphism

    User Avatar
    Science Advisor
    Homework Helper

    I think this is proved in the paper I posted in the Singer cycle thread.

    True, but how does this relate to conjugacy?
     
  17. Aug 19, 2008 #16
    What I mean is, that Singer cycles with the same minimal polynomial belong to the same conjugacy class defined by C(m(x)), the companion matrix of m(x). Assume conjugacy is restricted to the group theoretic sense. For example, all Singer cycles in GL(3,2) belong to either one of the two distinct conjugacy classes defined by companion matrices of the irreducible (and also primitive) polynomials x^3+x^2+1 and x^3+x+1.
     
  18. Aug 20, 2008 #17
    I just realized that S. cycles are also self centralizing, but I can't prove it. If I manage to though, I will have a formula for how many there are.
     
  19. Aug 20, 2008 #18

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Let A be an element of GL(n, q).
    Let f(x) be the minimal polynomial of A.
    Let [itex]f_d(x)[/itex] be the product of all irreducible degree-d factors of f(x).
    Note that the [itex]f_d(x)[/itex] are pairwise relatively prime.
    Note that [itex]f_d(x)[/itex] divides [itex]x^{q^d - 1} - 1[/itex].
    Therefore, f(x) divides the least common multiple of the relevant [itex]x^{q^d - 1} - 1[/itex].
    [tex]
    \mathop{lcm}\left\{ x^{q^{d_i} - 1} - 1 \right\} = x^{ \mathop{lcm}\{ q^{d_i} - 1 \} }- 1 [/tex]
    Since [itex]\sum_i d_i \leq n[/itex], we have that [itex]A^m = I[/itex] for some [itex]0 < m < q^n[/itex].
     
    Last edited: Aug 20, 2008
  20. Aug 20, 2008 #19
    I've also noticed that s.c. commute only with their powers, i.e., are self centralising. Can we prove that?
     
  21. Aug 20, 2008 #20
    Oops.. sorry for the double post.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Primitive polynomials
  1. Primitive root ! (Replies: 2)

  2. Primitive polynomial? (Replies: 1)

  3. Primitive matrix (Replies: 1)

  4. Primitive elements (Replies: 1)

Loading...