Finding the Number of Primitive Polynomials in Finite Fields

[the_fox]

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.

 

[morphism]

What's your definition of a primitive polynomial of degree n?

 

[the_fox]

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).

 

[morphism]

OK. And do you know how to many generators F_q^n has?

 

[the_fox]

Yeah, φ(q^n-1).

 

[morphism]

Now put 2 and 2 together. (Some field theory will be helpful.)

 

[the_fox]

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

 

[morphism]

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).

 

[the_fox]

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?

 

[morphism]

So we can say that elements of order q^n-1 in GL(n,q) can be divided in φ(q^n-1) conjugacy classes

What's the reasoning behind that?

 

[the_fox]

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.

 

[morphism]

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?

 

[the_fox]

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)?

 

[the_fox]

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?

 

[morphism]

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?

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

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.

True, but how does this relate to conjugacy?

 

[the_fox]

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.

 

[the_fox]

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.

 

[Hurkyl]

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?

Let A be an element of GL(n, q).
Let f(x) be the minimal polynomial of A.
Let $f_d(x)$ be the product of all irreducible degree-d factors of f(x).
Note that the $f_d(x)$ are pairwise relatively prime.
Note that $f_d(x)$ divides $x^{q^d - 1} - 1$.
Therefore, f(x) divides the least common multiple of the relevant $x^{q^d - 1} - 1$.
$$\mathop{lcm}\left\{ x^{q^{d_i} - 1} - 1 \right\} = x^{ \mathop{lcm}\{ q^{d_i} - 1 \} }- 1$$
Since $\sum_i d_i \leq n$, we have that $A^m = I$ for some $0 < m < q^n$.

 

[the_fox]

I've also noticed that s.c. commute only with their powers, i.e., are self centralising. Can we prove that?

 

[the_fox]

Oops.. sorry for the double post.

 

[Hurkyl]

I've also noticed that s.c. commute only with their powers, i.e., are self centralising. Can we prove that?

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 qⁿ elements. If something commutes with A, how does it act on this realization of GF(qⁿ)?

Note also that we have a GF(q)-vector space isomorphism GF(q)ⁿ ~= GF(qⁿ). Maybe we need both realizations to prove something? Ideally they should be compatable in some way.

 

[the_fox]

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?

 

[Hurkyl]

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

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?

 

[the_fox]

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).

 

[Hurkyl]

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.

 

[the_fox]

So how can we get commutativeness into the picture?