Irreducible Polynomials over Finite Fields

Click For Summary

Discussion Overview

The discussion revolves around the construction of irreducible polynomials over finite fields, specifically focusing on polynomials defined by the roots of two irreducible polynomials with coprime degrees. Participants explore the possibility of expressing a polynomial with roots formed by combinations of the roots of the given polynomials without directly referencing the roots in the formula.

Discussion Character

  • Exploratory
  • Technical explanation
  • Debate/contested

Main Points Raised

  • One participant inquires about the irreducible polynomial of degree nm with roots formed by the products of roots from two irreducible polynomials, seeking an explicit formula in terms of the original polynomials.
  • Another participant suggests that the polynomial can be expressed as a resultant and mentions various methods for computing resultants, including matrix determinants and Euclidean algorithm-like methods.
  • A participant expresses disappointment that the desired polynomial cannot be simply expressed as compositions of the original polynomials and references a paper discussing the topic, highlighting a theorem that may provide insight.
  • Further discussion touches on the complexity of resultant formulas and the potential for special classes of polynomials that might allow for faster computations than those presented in the referenced paper.

Areas of Agreement / Disagreement

Participants do not reach a consensus on the best approach to express the polynomial F(x) without roots appearing in the formula. Multiple methods and perspectives are presented, indicating ongoing exploration and uncertainty regarding the topic.

Contextual Notes

The discussion highlights limitations in the methods available for constructing the polynomial, including the complexity of resultant calculations and the potential for special cases that may simplify the process. Specific assumptions about the nature of the polynomials involved are not fully explored.

Who May Find This Useful

This discussion may be of interest to those studying algebraic structures over finite fields, particularly in the context of polynomial theory and computational methods in algebra.

burritoloco
Messages
81
Reaction score
0
Hi, yet another question regarding polynomials :). Just curious about this.

Let f(x), g(x) be irreducible polynomials over the finite field GF(q) with coprime degrees n, m resp. Let [itex]\alpha , \beta[/itex] be roots of f(x), g(x) resp. Then the roots of f(x), g(x), are [itex]\alpha^{q^i}, 0\leq i \leq n-1[/itex], and [itex]\beta^{q^j}, 0\leq j \leq m-1[/itex].

Question: What is the irreducible polynomial over GF(q) of degree nm with roots [itex]\alpha^{q^i}\beta^{q^j}[/itex] where [itex]0\leq i \leq n-1[/itex], and [itex]0\leq j \leq m-1[/itex]. Can you define such polynomial explicitly in terms of just f(x) and g(x) without the roots appearing in the formula?

Note: The last sentence/question is what really interests me as the following is the required polynomial (but defined in terms of the roots of f(x))

[tex]F(x) = \prod_{i=0}^{n-1}\alpha^{mq^i}g\left(\alpha^{-q^i}x\right)[/tex]

Thank you!
 
Last edited:
Physics news on Phys.org
It depends somewhat on just what you mean by "formula" and "appearing in".

I know that F can be expressed as a resultant. The formula you give is presumably comes from one of the methods of computing resultants. There exist other ways to compute resultants, such as as the determinant of a matrix, or a Euclidean algorithm-like method.

You could always find a way to write down the system of equations that literally expresses that [itex]\alpha \beta[/itex] is a root of F(x). Then F would be the solution!
 
Ah! The resultant formulas I was recalling are formulas 4.3 and 4.4. (Appearing just before theorem 4.3)
 
Thanks Hurkyl. I'll probably be coming up with more questions as my project goes along :). Feel free to answer whenever you can, haha. Great to have Physics Forums around.
 
Hmm, resultants and Thm 4.2 seem to be general methods on any two polynomials f(x), g(x) to obtain F(x). What if there are special classes of polynomials for which this computation could be done totally differently and much faster than the O(n^3 log^2(n)) in their paper? But what is this all good for anyways lol.
 

Similar threads

Undergrad How to show ##p(x)=g(x)x\pm 1\in\Bbb{Q}[x]## is irreducible in ##\Bbb{Q}_{\Bbb{Z}}[x]##?
  • · Replies 48 ·
2
Replies
48
Views
6K
Undergrad Finite fields, irreducible polynomial and minimal polynomial theorem
  • · Replies 6 ·
Replies
6
Views
3K
Undergrad Looking for a creative or quick method for finding roots in GF(p^n)
  • · Replies 3 ·
Replies
3
Views
2K
MHB The polynomial is irreducible over Q(i)
  • · Replies 16 ·
Replies
16
Views
4K
MHB Can a Unique Polynomial Satisfy Specific Integral Equations?
  • · Replies 4 ·
Replies
4
Views
2K
Undergrad Showing ##k[x_1,\ldots,x_n]/\mathfrak{a}## is finite dimensional
  • · Replies 40 ·
2
Replies
40
Views
5K
Undergrad Proving properties of polynomial in K[x]
  • · Replies 8 ·
Replies
8
Views
2K
Undergrad Splitting Fields: Anderson and Feil, Theorem 45.5 ....
  • · Replies 9 ·
Replies
9
Views
2K
Undergrad Matrix rank in terms of determinant polynomial
  • · Replies 14 ·
Replies
14
Views
4K
MHB Eisenstein polynomial and field extension
  • · Replies 24 ·
Replies
24
Views
5K