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.
     
  22. Aug 20, 2008 #21

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    I think so.... The main point I see is that if A is a singer cycle, then GF(q)[A] is a finite field with qn elements. If something commutes with A, how does it act on this realization of GF(qn)?

    Note also that we have a GF(q)-vector space isomorphism GF(q)n ~= GF(qn). Maybe we need both realizations to prove something? Ideally they should be compatable in some way.
     
    Last edited: Aug 20, 2008
  23. Aug 20, 2008 #22
    I'm not even sure I understand what you ask. Can you be a little bit more analytic, or perhaps illustrate this with an example?
     
  24. Aug 20, 2008 #23

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Let A be the GF(2)-matrix
    [tex]
    \left(
    \begin{array}{cc}
    0 & 1 \\
    1 & 1
    \end{array}
    \right)[/tex]

    Then A^2 + A + I = 0, and the ring GF(2)[A] -- the subring of the ring of matrices that is generated by A -- is a finite field with the 4 elements 0, I, A, A^2 (= I + A).

    Furthermore, GF(2)[A] is a vector space over GF(2). Construct an isomorphism of GF(2)[A] with GF(2)^2 by selecting the basis (I, A). Note that the "multiplication by A" is a GF(2)-linear transformation of GF(2)[A], and so it has a coordinate representation as a 2x2 matrix. In this example, it miraculously turns out that that matrix is A. (Actually, I selected A specifically so that would happen in this basis)


    Is that the part you wanted elaborated? Or is it something else?
     
    Last edited: Aug 20, 2008
  25. Aug 20, 2008 #24
    A nice example indeed. The part I didn't really get though, was about the action. If an element commutes with A in this example, then what? I assume your selection was motivated by taking the companion matrix of the 2-degree primitive polynomial over GF(2).
     
  26. Aug 20, 2008 #25

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    The whole reason I'm trying to insert GF(q^n) into the picture is so that we can invoke what we know about linear algebra over that field. In my example, "multiplication by A" is not merely a GF(2)-linear transformation, but also a GF(4)-linear transformation! I think, in general, we can arrange things so that GF(q^n)-linear algebra becomes applicable here.

    Yes, I chose the matrix in the way you suggested. Not for any deep reason; just because it's the only way I could quickly produce an example, and it's arithmetically convenient too. Actually, I didn't think of it as the companion matrix -- I was constructing the example in the reverse direction that I gave the exposition: I first chose the realization of GF(4) as a 2-dimensional vector space over GF(2) (with generator satisfying x^2 + x + 1 = 0), and then constructed A as the "multiply by generator" transformation. But it works out the same either way, I suppose.
     
    Last edited: Aug 20, 2008
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook