Exercise 11.2.9

Question

\def\imp{\Rightarrow}
\def\gcro{\mbox{[\hspace{-.15em}[}}% intervalles d'entiers 
\def\dcro{\mbox{]\hspace{-.15em}]}}

ewcommand{\be} {\begin{enumerate}}

ewcommand{\ee} {\end{enumerate}}

ewcommand{\deb}{\begin{eqnarray*}}

ewcommand{\fin}{\end{eqnarray*}}

ewcommand{\ssi} {si et seulement si }

ewcommand{\D}{\mathrm{d}}

ewcommand{\Q}{\mathbb{Q}}

ewcommand{\Z}{\mathbb{Z}}

ewcommand{\N}{\mathbb{N}}

ewcommand{\R}{\mathbb{R}}

ewcommand{\C}{\mathbb{C}}

ewcommand{\F}{\mathbb{F}}

ewcommand{\U}{\mathbb{U}}

ewcommand{e}{\,\mathrm{Re}\,}

ewcommand{\im}{\,\mathrm{Im}\,}

ewcommand{\ord}{\mathrm{ord}}

ewcommand{\Gal}{\mathrm{Gal}}

ewcommand{\legendre}[2]{\genfrac{(}{)}{}{}{#1}{#2}}

State and prove analogs of Theorem 11.2.2 and 11.2.4 that count monic irreducible polynomials of degree $n$ in $\F_q[x]$, where $q$ is now a power of the prime $p$.

Richard Ganaye · Accepted Answer

\def\imp{\Rightarrow}
\def\gcro{\mbox{[\hspace{-.15em}[}}% intervalles d'entiers 
\def\dcro{\mbox{]\hspace{-.15em}]}}

ewcommand{\be} {\begin{enumerate}}

ewcommand{\ee} {\end{enumerate}}

ewcommand{\deb}{\begin{eqnarray*}}

ewcommand{\fin}{\end{eqnarray*}}

ewcommand{\ssi} {si et seulement si }

ewcommand{\D}{\mathrm{d}}

ewcommand{\Q}{\mathbb{Q}}

ewcommand{\Z}{\mathbb{Z}}

ewcommand{\N}{\mathbb{N}}

ewcommand{\R}{\mathbb{R}}

ewcommand{\C}{\mathbb{C}}

ewcommand{\F}{\mathbb{F}}

ewcommand{\U}{\mathbb{U}}

ewcommand{e}{\,\mathrm{Re}\,}

ewcommand{\im}{\,\mathrm{Im}\,}

ewcommand{\ord}{\mathrm{ord}}

ewcommand{\Gal}{\mathrm{Gal}}

ewcommand{\legendre}[2]{\genfrac{(}{)}{}{}{#1}{#2}}

\bigskip

Let $q=p^{
u}$ a power of the prime $p$.

\bigskip

{\bf Proposition 11.2.1 bis.}
{\it
Let $f \in \F_q[x]$ be irreducible over $\F_q$, of degree $m$. Then:
\be
\item[(a)] $f$ divides $x^{q^m}-x$.
\item[(b)] $f$ is separable.
\item[(c)] Given an integer $n\geq 1$, $f$ divides $x^{q^n} -x$ $\iff$ $f$ has a root in $\F_{q^n}$ $\iff$ $m\mid n$.
\ee
}
\begin{proof}
\be
Note: we suppose that all the fields considered here are subfields of a field $\Omega$, which can be an algebraic closure of $\F_q$. In this case, there is a unique subfield of $\Omega$ with a given cardinality $q^d$, written $\F_{q^d}$, where
$$\F_{q^d} = \{\alpha \in \Omega \ | \ \alpha^{q^d} = \alpha\}.$$

We begin with part (c). Let $\alpha \in \Omega$ be a root of $f$. Since $f$ is irreducible over $\F_q$, the extension $\F_q \subset \F_q(\alpha)$ has degree $m = \deg(f)$. So $| \F_q(\alpha)| = q^m$, therefore $\F_q(\alpha) = \F_{q^m}$ (see the note). If $\alpha \in \F_{q^n}$, then $\F_q(\alpha) = \F_{q^m} \subset \F_{q^n}$, therefore $m\mid n$ (Corollary 11.1.8). Conversely, if $m\mid n$, then $\F_q(\alpha) = \F_{q^m} \subset \F_{q^n}$, so the root $\alpha$ of $f$ is in $\F_{q^n}$. This proves the second equivalence of part (c).

If $f$ has a root $\alpha \in \F_{q^n}$, then $\alpha^{q^n} = \alpha$, so $\alpha$ is a root of $x^{q^n}-x$. As $f$ is the minimal polynomial of $\alpha$ over $\F_q$, $f(x) \mid x^{q^n}-x$.

Conversely, suppose that $f(x) \mid x^{q^n}-x$. Take any root $\alpha$ of $f$ in $\Omega$. As $f(x) \mid x^{q^n}-x$, then $\alpha^{q^n} = \alpha$, and this implies $\alpha \in \F_{q^n}$, so (c) is proved.

We get part (a) by taking $n=m$ in part (c), and part (b) follows immediately, since $x^{q^n} -x = x^{p^{n 
u }} - x$ is separable by the proof of Theorem 11.1.4.

\ee
\end{proof}

{\bf Theorem 11.2.2 bis.} {\it Let}
$${\mathcal N}'_m =  \{f \in \F_q[x]\ |\  f 	ext{ is monic irreducible over } \F_q 	ext{ of degree } m\},$$
and $ N'_m = |{\mathcal N}'_m |$.

{\it Then, for any $n\geq 1$, we have
$$\sum_{m\mid n} m N'_m = q^n,$$
where the sum is over all positive divisors of $n$.}

\begin{proof}
Since $x^{q^n} - x$ is separable, we know that it factors as a product of distinct irreducible polynomials in $\F_p[x]$. Furthermore, since it is monic, we can assume that the polynomials in the factorization are also monic. Finally, part (c) of Proposition 11.2.1 bis shows that the polynomials in the factorization are {\it all} monic irreducible polynomials of $\F_p[x]$ whose degree $m$ divides $n$. Thus
$$x^{q^n} -x = \prod_{m\mid n} \prod_{f \in {\mathcal N}'_m} f.$$
Since every $f\in {\mathcal N}_m$ has degree $m$, taking the degree of each side give the desired formula.
\end{proof}
\bigskip

{\bf Theorem 11.2.4 bis.}
The number of monic irreducible polynomials of degree $n$ in $\F_q[x]$ is given by
$$N'_n = \frac{1}{n} \sum_{m\mid n} \mu(m) q^{\frac{n}{m}}.$$
\begin{proof}
Write $F(n) = nN'_n$ ,and $G(n) = \sum_{m\mid n}  F(m) = q^n$.

The M"obius inversion formula gives $F(n) = \sum_{m\mid n} \mu(m) G\left (\frac{n}{m} ight )$. So
$$n N'_n = \sum_{m\mid n} \mu(m) q^{\frac{n}{m}}.$$
\end{proof}

Exercise 11.2.9

Answers

Comments

Exercise 11.2.9

Answers

Comments

Add answer