Singer Cycles

1. Aug 6, 2008

the_fox

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.

2. Aug 6, 2008

morphism

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

Hint 2: GF(q^n)* can be embedded into GL(n,q).

3. Aug 6, 2008

the_fox

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?

4. Aug 6, 2008

Yup.

5. Aug 6, 2008

the_fox

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?

6. Aug 7, 2008

morphism

Yes -- good work! (Just make sure you notice that T is invertible.)

7. Aug 7, 2008

the_fox

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.

8. Aug 7, 2008

morphism

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

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

where $\mu$ is the Mobius function and $\varphi$ 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.

9. Aug 7, 2008

morphism

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 $\varphi(p^n - 1) \leq \sum_{d | n} \mu(d) p^{n/d}$ for all n and p.]

10. Aug 7, 2008

morphism

Some googling brought up this paper. You might find it useful.

11. Aug 8, 2008

the_fox

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.

12. Aug 12, 2008

the_fox

That's not quite right.. Any ideas about how many singer cycles there are?

13. Sep 18, 2008

the_fox

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?

14. Sep 19, 2008

morphism

Just look at how GL(n,q) acts on GF(q^n)*.