Irreducible polynomials over finite fields

Click For Summary

Discussion Overview

The discussion revolves around the properties of irreducible polynomials over finite fields, specifically addressing the polynomial x^q^n - x and its relationship to irreducible polynomials whose degrees divide n. Participants explore proofs, lemmas, and related concepts in the context of field theory and linear algebra.

Discussion Character

  • Technical explanation
  • Debate/contested
  • Mathematical reasoning

Main Points Raised

  • Some participants seek clarification on the statement regarding the polynomial x^q^n - x and its factorization into irreducible polynomials, questioning whether q is prime and if the field is GF(q^n) or Z_q.
  • One participant proposes a lemma stating that an irreducible polynomial f of degree m divides x^q^n - x if and only if m divides n, and provides a proof outline for this lemma.
  • Another participant requests a detailed proof for the first lemma, emphasizing the need for clarity on the conditions under which it holds.
  • Discussion includes the implications of roots of the polynomial forming a field extension and the conditions under which a polynomial has multiple roots.
  • A participant raises a question about the minimal polynomial of an element in GL(n,q) and its degree, seeking to understand the irreducibility of the characteristic polynomial without direct evaluation.
  • Several participants engage in a back-and-forth regarding definitions and implications of irreducibility, minimal polynomials, and the structure of field extensions.
  • One participant suggests that if the characteristic polynomial is reducible, it implies the element lies in a proper subfield, while another proposes a formal proof involving the degrees of subfields and contradictions arising from assumptions about orders of elements.
  • Another participant notes that an element of order p^n - 1 in GF(p^n) generates the cyclic multiplicative group, leading to the conclusion that its irreducible polynomial is of degree n.

Areas of Agreement / Disagreement

Participants express differing views on the initial statement regarding the polynomial x^q^n - x, with some clarifying terms and others questioning the assumptions. The discussion on minimal polynomials and their degrees also reveals a lack of consensus on the best approach to prove irreducibility.

Contextual Notes

Limitations include missing details in proofs, assumptions about the nature of the field, and the specific conditions under which certain statements hold. The discussion also reflects varying levels of familiarity with the underlying mathematical concepts.

gonzo
Messages
277
Reaction score
0
Can someone explain to me why the following is true (ie, show me the proof, or at least give me a link to one):

Over the field Zq the following polynomial:

x^q^n-x

is the product of all irreducible polynomials whose degree divides n


Thanks.
 
Physics news on Phys.org
Somethings not quite right in the statement i think. First of all, i guess the q is prime. Secondly, do you mean over the field GF(q^n) and not Z_q ?

[edit]Now that i think about it, you did mean Z_q. Let me call it F_q rather.
The proof of this is carried out over some steps.

1. Lemma : If f belongs F_q[x] is an irreducible polynomial over F_q of degree m (say), then f(x) would divide x^q^n - x iff m divides n
This would imply that all monic irreducible polynomials over F_q that we see in the factorization of x^q^n-x (belonging to F_q[x]) are exactly those whose degree divides n

2. Lemma : An f belonging to F_q[x] has a multiple root iff (f,f') != 1
Now Consider g(x) = x^q^n-x. So g'(x) = -1. So from the above lemma, we get that all monic irreducible polynomials whose degree divides n, occur exactly once in factorization of g in F_q[x]

Hence proved.
I have avoided proofs of the above lemmas. I guess they should be simple enough to be proved.[/edit]

-- AI
 
Last edited:
Thanks, but could you please show me the proof for lemma 1? And yes, q has to be prime, sorry for not stating that, I thought it was implied since I said Zq was a field.
 
well the roots of that polynomial form a field extension of Fq, of degree n, hence their minimal polynomials are all factros of that polyno9mial. isn't that about it?
 
oh and just because Fq is a field, it does not of course follow that q is prime, unless you think that Fq means Z/qZ.

usually Fq denotes the unique field of order q where q is a power of a prime p.
 
Lemma 1 : If f belongs F_q[x] is an irreducible polynomial over F_q of degree m (say), then f(x) would divide x^q^n - x iff m divides n

Proof :
First half -->
Let k be a root of f(x)
F_q(k) is a subfield of F_q^n (why??)
[F_q(k):F_q] = m
but [F_q^n : F_q] = n
Therefore, m divides n (why??)

Converse,
given m|n
F_q^m is a subfield of F_q^n (why??)

If k is a root of f,
then F_q(k) = F_q^m (why??)

Therefore, k is a root of x^q^n - x (why??)
Hence, f divides x^q^n - x

I have left a lot of details in the proof, try to fill them in.

-- AI
 
Hi everyone. I have a question: How can we show that an element s of order q^n -1 belonging to GL(n,q) has a minimal polynomial of degree n? Or equivalently that it's characteristic polynomial is irreducible?
 
Resurrecting dead threads isn't usually a good idea.

But to answer your question...

What are the definitions of all the things involved? Let's write them out.

1) What is the definition of min poly?

2) Suppose that f is reducible: f(x)=g(x)h(x) and that a is a root of f, i.e. f(a)=0.

3) Does that imply anything about g(a) or h(a)?

4) Remember this is a field
 
Sorry about that. I realized it was a dead thread after I posted. To answer 2) it would imply that a would either be a root of g(x) or h(x). But I still don't see how that would give us the irreducibility of the characteristic polynomial.
 
  • #10
So, if it's a root of a poly of smaller degree, wouldn't that negate some part of the definition of _minimal_ (I think I mistakenly used characteristic in the last post) polynomial?
 
  • #11
If you use the minimal polynomial, then what we need to show is that it's degree is n. I simply said that this is equivalent to showing that the characteristic polynomial is irreducible (that's because the minimal polynomial is irreducible and divides the characteristic polynomial). I will make the question more specific: Take GL(5,2)
and the element [01110]
[00011]
[00111]
[11000]
[01000]
which is of order 31. It's minimal polynomial is x^5 + x^4 + x^3 + x^2 + 1. How can we assure that it's degree is 5 without evaluating it. It could as easily be 2 or 3 or whatever.
 
  • #12
Ah, got you. Not having a good time with my return to this kind of mathematics.
 
  • #13
Well, the obvious observation is that if [itex]a[/itex]'s char poly is reducible, then it implies that [itex]a[/itex] lies in a proper subfield of F_{q^n}, i.e. the splitting field of the char poly is not F_{q^n}. But I'm not seeing a way to write that in a way that doesn't just say 'nah, because it is'.
 
  • #14
I suppose the more formal proof goes along the lines of:

the roots of a poly of degree k form a subfield of degree q^k, and hence any element has order at most q^k-1, if k is not n, then this is a contradiction.
 
  • #15
If z is an element of order p^n-1 in GF(p^n), it is the generator of the cyclic multiplicative group, and by the Primitive element theorem, GF(p^n) = Zp[z]. Therefore it's irr. polynomial is of degree n.
 
  • #16
I mean Zp(z), the field, of course.

Steve
 

Similar threads

Replies
48
Views
7K
  • · Replies 6 ·
Replies
6
Views
3K
  • · Replies 16 ·
Replies
16
Views
5K
  • · Replies 3 ·
Replies
3
Views
2K
  • · Replies 1 ·
Replies
1
Views
3K
  • · Replies 9 ·
Replies
9
Views
2K
  • · Replies 3 ·
Replies
3
Views
4K
  • · Replies 8 ·
Replies
8
Views
4K
Replies
12
Views
5K
  • · Replies 1 ·
Replies
1
Views
3K