On $\mathbb{F}_q$-Order of Polynomials and Properties of $r$-Primitive and $k$-Normal Elements over Finite Fields

Technical Summary: On Fq-Order of Polynomials and Properties of r-Primitive and k-Normal Elements over Finite Fields

Problem Statement
Finite fields, specifically the extension $\mathbb{F}_{q^n}$ over $\mathbb{F}_q$, possess two fundamental algebraic structures: an $n$-dimensional vector space structure and a cyclic multiplicative group structure. These give rise to distinguished classes of elements: primitive elements (generators of the multiplicative group) and normal elements (generators of the vector space via their conjugates). While the concepts of multiplicative order and $\mathbb{F}_q$-Order (the minimal polynomial annihilating an element under the Frobenius automorphism) are well-established for field elements, their application to polynomials has been less systematic. Specifically, the paper addresses the need to formally define the $\mathbb{F}_q$-Order of a polynomial and utilize this concept to investigate the structural properties and enumeration of $r$-primitive and $k$-normal elements and polynomials.

Methodology
The authors employ a combination of algebraic definitions, structural analysis, and combinatorial counting within the framework of finite field theory.

1. Definition Extension: The paper introduces a formal definition for the $\mathbb{F}_q$-Order of a polynomial $f \in \mathbb{F}_q[x]$, denoted $\text{Ord}(f)$, defined as the unique monic polynomial of least degree such that $f$ divides $g \circ x$ (where $\circ$ denotes composition).
2. Structural Analysis: The authors establish relationships between the $\mathbb{F}_q$-Order of a polynomial and the $\mathbb{F}_q$-Order of its roots, particularly for irreducible polynomials. They analyze how $\mathbb{F}_q$-Order behaves under polynomial operations such as composition, multiplication, and greatest common divisors.
3. Partitioning and Counting: The study utilizes the concepts of $m$-free and $g$-free elements to partition sets of field elements based on their orders and $\mathbb{F}_q$-Orders. The First Isomorphism Theorem is applied to homomorphisms defined by polynomial actions to derive cardinality formulas for specific subsets of $\mathbb{F}_{q^n}$.
4. Algebraic Properties: The paper investigates the behavior of $r$-primitive and $k$-normal elements under field operations (multiplication and addition), specifically examining conditions under which these properties are preserved or transformed.

Key Contributions and Results

• Formalization of Polynomial $\mathbb{F}_q$-Order:

  • The paper provides a precise definition of the $\mathbb{F}_q$-Order for polynomials, drawing an analogy to the $\mathbb{F}_q$-Order of field elements.
  • Proposition 4 establishes that for an irreducible polynomial $f$, $\text{Ord}(f)$ is equal to the $\mathbb{F}_q$-Order of its roots.
  • Proposition 9 demonstrates that the $\mathbb{F}_q$-Order of a product of pairwise relatively prime polynomials is the least common multiple (LCM) of their individual $\mathbb{F}_q$-Orders.
  • Proposition 10 characterizes normal polynomials: a polynomial $f$ of degree $m$ is normal if and only if it is monic and $\text{Ord}(f) = x^m - 1$.

• Enumeration of Polynomials:

  • Proposition 12 derives a formula for the number of irreducible polynomials of degree $n$ with a specific $\mathbb{F}_q$-Order $f$. The count is $\phi(f)/n$ if the order of $f$ (denoted $\text{ord}(f)$) equals $n$, and 0 otherwise.
  • Using these results, the authors provide an explicit summation formula for the number of $k$-normal polynomials of degree $n$ over $\mathbb{F}_q$.

• Properties of $r$-Primitive and $k$-Normal Elements:

  • Proposition 16 analyzes the product of $r_1$-primitive and $r_2$-primitive elements, showing that if their multiplicative orders are coprime, their product is $\gcd(r_1, r_2)$-primitive.
  • Proposition 24 and Corollary 25 investigate the inverse of normal elements, proving that if $\alpha$ is $(n-1)$-normal, then $\alpha^{-1}$ is also $(n-1)$-normal.
  • Proposition 26 and Corollary 27 examine the sum of elements. If $\alpha$ and $\beta$ have coprime $\mathbb{F}_q$-Orders $f$ and $g$, then $\text{Ord}(\alpha + \beta) = fg$. Consequently, if $\alpha$ is $k_1$-normal and $\beta$ is $k_2$-normal, their sum is $(k_1 + k_2 - n)$-normal.

• Partitioning and Identities:

  • The paper defines sets of elements based on divisibility of their orders and $\mathbb{F}_q$-Orders (e.g., Theorem 17 and Proposition 20).
  • Proposition 19 and Proposition 21 utilize homomorphisms to calculate the cardinality of sets of $r$-th powers and sets of elements with $\mathbb{F}_q$-Orders divisible by a specific polynomial.
  • These derivations provide alternative proofs for classical identities involving the Euler phi function, specifically $\sum_{d|n} \phi(d) = n$ and $\sum_{g|f} \phi(g) = q^{\deg(f)}$.

Significance
The paper claims to provide a unified and systematic framework for studying irreducible polynomials by relating the $\mathbb{F}_q$-Order of a polynomial directly to the properties of its roots. This approach allows for the derivation of explicit enumeration formulas for $k$-normal polynomials, a topic previously defined by Alizadeh et al. but not fully enumerated in this specific manner. Furthermore, the work extends the understanding of $r$-primitive and $k$-normal elements by analyzing their algebraic interactions under addition and multiplication, offering new combinatorial insights into the structure of finite field extensions. The authors position this work as a refinement of classical definitions (referencing Ore) within the modern context of finite fields, aiming to bridge the gap between element-based and polynomial-based algebraic structures.