Product of all monic irreducibles with degree dividing $n$ in $\mathbb{F}_{q}$?

Solution 1:

Let $\mathbf{F}$ be the field of $q$ elements, and fix $n\geq 1$. The extension of degree $n$ over $\mathbf{F}$ is the field with $q^n$ elements. Call that $\mathbf{K}$.

If $a\in\mathbf{K}$, then $\mathbf{F}(a)$ is an intermediate field, so $[\mathbf{F}(a):\mathbf{F}]$ divides $n$; that is, the monic irreducible polynomial of $a$ is of degree dividing $n$ over $\mathbf{F}$. So every element corresponds to a monic irreducible.

Moreover, every monic irreducible of degree dividing $n$ corresponds to an element in $\mathbf{K}$: if $f(x)$ is such an irreducible, and $a$ is a root, then $\mathbf{F}(a)$ has degree $\deg(f)$, which divides $n$, and so is contained in the field extension of degree $n$ (remember that $\mathbf{F}_{q^r}\subseteq \mathbf{F}_{q^s}$ if and only if $r|s$).

That means that if you let $P(X)$ be the product of all monic irreducible polynomials over $\mathbf{F}$ that have degree dividing $n$, then its roots are precisely the elements of $\mathbf{K}$.

We also know that $\mathbf{K}$ is the splitting field of $X^{q^n}-X$: every element of $\mathbf{K}$ satisfies this polynomial (by Lagrange's Theorem, every nonzero element satisfies $a^{q^n-1}=1$, and then there's $0$), and no field strictly smaller than $\mathbf{K}$ can be the splitting field (not enough roots). So now we have two polynomials that are satisfied by every element of $\mathbf{K}$ and only by all the elements of $\mathbf{K}$: $X^{q^n}-X$ and our $P(X)$. So $X^{q^n}-X$ certainly must divide $P(X)$, and $P(X)$ must be a product of linear factors over $\mathbf{K}$.

So the only question that remains is: does $P(X)$ have any repeated roots?

Solution 2:

There are two steps here.

1. Prove that a prime $\pi(x)$ in $\mathbb F_q[x]$ divides $x^{q^n}-x$ if and only if $\deg(\pi(x))\mid n$.
2. Prove that there are no repeated prime factors of $x^{q^n}-x$.

First prove that for integers $d,n$, $x^{q^d}-x\mid x^{q^n}-x$ if and only if $d\mid n$.

I'll prove the first part of (1) for you. If $\deg(\pi(x))=d$, and $d\mid n$ then consider the field $F=\mathbb F_q[x]\big /{\left<\pi(x)\right>}$. It is of order $q^d$, so we know that for every element $y\in F$, $y^{q^d}=y$. In particular, $x$ is an element of $\mathbb F_q[x]$, so the image $\bar x$ of $x$ in $F$ has the property that ${\bar x}^{q^d}-\bar{x}=0$. But that means that the image of $x^{q^d}-x$ is in the kernel of the map from $\mathbb F_q[x]$ to $F$. So $x^{q^d}-x$ is divisible by $\pi(x)$. So, by our first step above, $x^{q^n}-x$ is divisible by $\pi(x)$ when $d\mid n$.

Solution 3:

Show that $\large X^{q^n}−X \in \mathbb{F}_q[X]$ (with $q = p^k$ for some prime $p \in \mathbb{N}^+$ and $k,n \in \mathbb{N}^+$) is the product of all monic irreducible polynomials $\pi \in \mathbb{F}_q[X]$ with $\deg(\pi) ~|~ n$:

Lemma 1:

$\forall q, n, d \in \mathbb{N}^+: \large q^n \bmod \left(q^d-1\right) = q^{n ~\bmod~ d}$ as $q^d = 1 \bmod \left(q^d-1\right)$

Lemma 2:

$\large \gcd\left(X^{q^n} - X, X^{q^d} - X\right) = X^{q^{\gcd(n, d)}} - X$
(in any polynomial ring over a field, especially in $\mathbb{F}_q[X]$)

For $n = d$ this is obvious, assume w.l.o.g. $n > d$. For all $1 \leq k \in \mathbb{N}$ with $q^n - k(q^d-1) > 0$ (required so all exponents are $\geq 0$):

$$\large X^{q^n} - X = \left(\sum\limits_{i=1}^k X^{q^n -i(q^d-1) - 1}\right)\cdot \left(X^{q^d}-X\right) + \left(X^{q^n -k(q^d-1)} - X\right)$$

As $q^n \bmod \left(q^d-1\right) = q^{n ~\bmod~ d} \neq 0$ ($\exists k: q^n \bmod \left(q^d-1\right) = q^n - k(q^d-1) > 0$):

$$ \large \Rightarrow \left(\large X^{q^n} - X\right) \bmod \left(X^{q^d}-X\right) = \left(X^{q^{n ~\bmod~ d}} - X\right)$$

$$ \large \Rightarrow \gcd\left(X^{q^n} - X, X^{q^d} - X\right) = \gcd\left(X^{q^d} - X, X^{q^{n ~\bmod~ d}} - X\right)$$

I.e. the $\gcd$ modulo reduction is done in the $q$ and $d$ exponents.

Step 1: (Similar to the answer by Thomas Andrews)

Let $\pi$ be a monic irreducible polynomial in $\mathbb{F}_q[X]$ with degree $d = \deg(\pi)$, and $F_{\pi} := \mathbb{F}_q[X]/\left<\pi\right>$ with $\varphi: \mathbb{F}_q[X] \to F_{\pi}$. Show $d ~|~ n \Rightarrow \pi ~|~ \left(X^{q^n}-X\right)$.

As the size of the multiplicative subgroup $\large \left|F_{\pi}^\ast\right| = q^d-1$, it follows that $\large\forall y \in F_{\pi}: y^{q^d-1} = 1, y^{q^d} - y = 0$. $\large y^{q^d} - y = 0$ is also true for $\large y = 0$, i.e. $\large\forall y \in F_{\pi}$.

Therefore $\large \varphi(X^{q^d}-X) = 0 \Rightarrow \exists k \in \mathbb{F}_q[X]: \left(X^{q^d}-X\right) = 0 + k \cdot \pi \Rightarrow \pi ~|~ \left(X^{q^d}-X\right)$

If $d ~|~ n \Rightarrow \large \gcd\left(X^{q^n} - X, X^{q^d} - X\right) = X^{q^d} - X \Rightarrow \pi ~|~ \left(X^{q^n} - X\right)$

Step 2:

$\large f = X^{q^n} - X \in \mathbb{F}_q[X]$ is square-free, as $\large f' = q^n \cdot X^{q^n-1} - 1 = -1$ ($q = 0$ in $\mathbb{F}_q$!), and $\gcd(f, f') = 1$.

If $\exists a, b \in \mathbb{F}_q[X]: f = (a \cdot a) \cdot b $
$\Rightarrow f' = (a\cdot a' + a' \cdot a) \cdot b + (a \cdot a) \cdot b' = a \cdot (a'\cdot b + a'\cdot b + a \cdot b')$
$\Rightarrow a ~|~ \gcd(f, f')$

As $\gcd(f, f') = 1$ there is no $a \in \mathbb{F}_q[X]$ with $\deg(a) \geq 1$ and $a ~|~ \gcd(f, f')$, and $f$ is square-free.

Step 3:

Induction over $n \geq 1$: show that $ \large p_n := X^{q^n} - X \in \mathbb{F}_q[X]$ is the product of all monic irreducible polynomials $\pi \in \mathbb{F}_q[X]$ with $\deg(\pi) ~|~ n$.

We already know that all such $\pi$ are factors of $p_n$ and $p_n$ is square free. Now show that all factors have the required form.

Let $\pi \in \mathbb{F}_q[X]$ be a irreducible polynomial with $d = \deg(\pi)$ and $\pi ~|~ p_n$. Then $\pi ~|~ \gcd(p_n, p_d) = p_{\gcd(n, d)}$.

If $\gcd(n, d) < d$ then (by induction) $\pi \nmid p_{\gcd(n, d)}$ as $d \nmid n$.

Otherwise $\gcd(n, d) = d \Rightarrow d ~|~ n$.