12
$\begingroup$

In the finite field of $q^n$ elements, the product of all monic irreducible polynomials with degree dividing $n$ is known to simply be $X^{q^n}-X$. Why is this?

I understand that $q^n=\sum_{d\mid n}dm_d(q)$, where $m_d(q)$ is the number of irreducible monic polynomials with degree $d$, and that each element of the field satisfies $X^{q^n}-X$.

How does the conclusion follow from this? I tried substituting the exponent to $X^{\sum_{d\mid n}dm_d(q)}-X$ but this doesn't seem to do much good.

$\endgroup$
  • 3
    $\begingroup$ Your first $q^n$ should be $q$. The product of all monic irreducible polynomials of degree dividing $n$ over the field of $q^n$ elements is $X^{(q^n)^n}-X$: there are at least $q^n$ of degree $1$, and you also have irreducibles of degree $n$, among others. $\endgroup$ – Arturo Magidin Feb 7 '12 at 17:07
11
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ The existence of $\mathbf{K}$ depends on the existence of a monic irreducible polynom with degree $n$; the latter one can be shown by using the formula in the question. Unless you can find another way to show the existence you can't actually use it in the proof. So this answer feels like cheating to me :) $\endgroup$ – Stefan Nov 5 at 15:25
  • $\begingroup$ @Stefan: No, you do not need to prove the existence of a monic irreducible of degree $n$ to prove the existence of $\mathbf{K}$, because $\mathbf{K}$ can be obtained by successive extensions or in other ways if need be. But in any case, it is trivial to show that $\mathbf{K}$ exists: it is the splitting field of $x^{q^n}-x$ over $\mathbb{F}_p$. There is no "cheating" involved; just because you can't see a way around an issue you (think you) find doesn't mean people are just skipping it. Some of us may be taking an alternate route. $\endgroup$ – Arturo Magidin Nov 5 at 15:52
  • $\begingroup$ Hm. I think it would be useful to mention why $X^{q^n}-X$ has unique roots; but even then $\mathbf{K}$ is only (isomorphic to) the splitting field if $\mathbf{K}$ exists in the first place; I don't see how your argument shows the existince of the splitting field leading the the existence of $\mathbf{K}$. $\endgroup$ – Stefan Nov 5 at 20:46
  • 1
    $\begingroup$ @Stefan. Sigh. The polynomial is separable because its derivative is $-1$. As to the existence of $\mathbf{K}$, did you even bother to notice that the problem in question actually assumes the existence of $\mathbf{K}$? But even if you did not, just what exactly are you talking about? So far as I can tell, nothing: The field of $q^n$ elements contains the field of $q$ elements, and has degree $n$ over it, hence yes, there is an extension of degree $n$ of the field of $q$ elements. Their existence follows from the existence of arbitrary splitting fields. $\endgroup$ – Arturo Magidin Nov 5 at 21:08
  • $\begingroup$ @Stefan: In short: the existence and uniqueness of fields of order $p^k$ for any prime $p$ and any $k\geq 1$ follows from the existence and uniqueness of splitting fields: the field of $p$ elements exists, and the splitting field of $x^{p^n}-x$ has $p^n$ elements by separability; and any field of $p^n$ elements is a splitting field of that polynomial over $\mathbb{F}_p$. Thus, for any prime power $q$, and any $n\gt 0$, there is a (unique) field of order $q$ and a (unique) extension of degree $n$ over it, which has $q^n$ elements. $\endgroup$ – Arturo Magidin Nov 5 at 21:12
10
$\begingroup$

As noted by Arturo, the problem should be stated about $\mathbb F_q$, not $\mathbb F_{q^n}$.

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|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|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_p[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|n$.

$\endgroup$
  • 1
    $\begingroup$ It could be that $\pi ~|~ x^{x^n}-x$ but not $x^{q^d}-x ~|~ x^{q^n}-x$, so it doesn't follow that $d ~|~ n$ as far as I can see. $\endgroup$ – Stefan Oct 29 '13 at 15:34
  • $\begingroup$ @Stefan I said the first part of (1). Note the sentence, "If $\deg =d$ and $d\mid n$. I did not try to prove the other part of the "if and only if." $\endgroup$ – Thomas Andrews Oct 29 '13 at 17:08
  • $\begingroup$ Ah yes, that explains it. I got a little bit confused why you asked to prove "$d,n$, $x^{q^d}-x|x^{q^n}-x$ if and only if $d|n$" first, as you only need the $\Leftarrow$ part for the first part of (1). Thanks! $\endgroup$ – Stefan Oct 29 '13 at 19:13
  • $\begingroup$ I probably should hav said "half of" rather than "the first part of..." :) @Stefan $\endgroup$ – Thomas Andrews Oct 29 '13 at 19:21
  • $\begingroup$ I can't prove the second half of (1) $\endgroup$ – MaudPieTheRocktorate Apr 20 '17 at 20:56
7
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.