\documentclass[11pt]{article}
\usepackage{fullpage}
\usepackage{amsfonts}
\newcommand{\F}{\mathbb{F}}
\newcommand{\K}{\mathbb{K}}
\newcommand{\np}{\mathop{\rm NP}}
\newcommand{\binom}[2]{{#1 \choose #2}}
\newcommand{\Z}{{\mathbb Z}}
\newcommand{\vol}{\mathop{\rm Vol}}
\newcommand{\conp}{\mathop{\rm co-NP}}
\newcommand{\atisp}{\mathop{\rm ATISP}}
\renewcommand{\vec}[1]{{\mathbf #1}}
\newcommand{\emod}[1]{\, (\bmod\ #1)}
%\input{dansmacs}
\begin{document}
\noindent {\large Algebra and Computation (MIT 6.s897)
\hfill Lecturer: Madhu Sudan\\
Problem Set 1 \hfill
Due: Friday, March 6, 2015
\\
\section*{Instructions}
\begin{description}
\item[Goal:] The goal of this problem set is to induce some ``finite field''
thinking. So while it would be great if you can solve the problem without
consulting texts, if that makes things better feel free to do so.
\item[Collaboration:]
Collaboration is allowed, but try to think of the solutions you eventually
came up with (possibly collaboratively) in isolation and make sure you
understand it (and internalize it).
\item[Writeup:]
The due date is a recommendation rather than a deadline. It is best if you
think of the questions and answers sooner rather than later. The goal of
this pset is only to get you to think about potentially weak points in your
background. So submission of answers is optional - but I would like to get
an email acknowledging that you have thought about the questions and know
how to answer them. If you have any questions, email me. If you think you
would like to run your solutions by me to verify them or to check if there
are alternate solutions, do write them up and send to me by email.
\end{description}
\section*{Exercises}
\begin{enumerate}
\item
Prove $\F_q[x]/(g(x))$ is a field of cardinality $q^d$ if and only if
$g$ is an irreducible polynomial of degree $d$.
\begin{description}
\item[{\sf Solution:}]
Main thing to do here is to just verify that there are
no
zero divisors if $g(x)$ is irreducible; and then to count cardinality.
\end{description}
\item
Prove that the multiplicative group of the finite field $\F_q$, denoted
$\F_q^*$ is cyclic. Conclude that every field has a primitive element.
\begin{description}
\item[{\sf Solution:}]
The following shows how you can prove this with some finite field thinking,
and truly no counting!
Let $\mu_n(m)$ denote the number of elements of order $m$ in $\Z_n$
and let $\phi_n(m)$ denote the number of elements of order dividing $m$
in $\Z_n$. If $m$ divides $n$ we have
$$\phi_n(m) = m \mbox{ and } \phi_n(m) = \sum_{t | m}
\mu_n(t).$$
We also know that $\mu_n(m) \geq 1$ for every $m$ dividing $n$ (the element
$n/m$ has order $m$).
(Throughout the below, we will consider $m$ dividing $q-1$.)
Now let $\F = \F_q$ be the field of $q$ elements and let $\phi_\F(m)$ denote
the number of elements of order dividing $m$ in $\F^*_q$ (th multiplicative
subgroup) and let $\mu_\F(m)$ denote the number of elements of order exaclty
$m$. We show below that $\mu_\F(m) = \mu_{q-1}(m)$ for every $m$.
(This is sufficient since we then have $\mu_\F(q-1) \geq 1$.)
We do so by noticing that $\phi_\F$ and $\mu_\F$ satisfy many of the
conditions that $\phi_{q-1}$ and $\mu_{q-1}$ do.
For instance, we have $\phi_\F(m) = \sum_{t | m} \mu_\F(t)$.
Since every element of order dividing $m$ is a root of the polynomial
$x^m - 1$, we have that $\phi_\F(m) \leq m = \phi_{q-1}(m)$.
Note also that if $\mu_\F(m) \geq 1$ then there is an element $\alpha\in \F$
of order $m$,
and so there are at least $m$ elements of order dividing $m$ (all powers of $\alpha$), and since $\phi_\F(m) \leq m$ we have that there are exactly $m$ elements of order dividing $m$ and they form a cyclic subgroup of order $m$. We conclude that $\mu_\F(m) \geq 1$ implies $\mu_\F(m) = \mu_{q-1}(m)$, which in turn implies $\mu_{\F}(m) \leq
\mu_{q-1}(m)$.
But since every non-zero element is a
root of $x^{q-1} - 1$ we have $\phi_\F(q-1) = q-1$ and
so we have $\sum_{t | q-1} \mu_\F(t) =
\sum_{t | q-1} \mu_{q-1}(t)$. But term by term the left hand side is upper
bounded by the right, and so the only way to get equality is if each term on
the left equals the corresponding term on the right and so we have
$\mu_\F(t) = \mu_{q-1}(t)$.
\end{description}
\item If $\omega$ is a primitive element in $\F_{q^d}$ then prove that
$\omega$ is a generator of $\F_{q^d}$ over $\F_q$.
\begin{description}
\item[{\sf Solution:}]
Recall that $\F_{q^d}$ is a $d$-dimensional vector space over $\F_q$.
Let $\omega$ be primitive in $\F_{q^d}$ and consider the elements
$1,\omega,\omega^2,\ldots,\omega^d$. Since we have $d+1$ elements here
there must be an $\F_q$ relation over them (or else we have a vector space
of dimension $d+1$ or larger). But $1,\omega,\ldots,\omega^{d-1}$ must be linearly independent over $\F_q$ or else every power of $\omega$ can be
expressed in the $\F_q$ span of $1,\omega,\ldots,\omega^{d-2}$ which
violates the assumption that there are $q^d-1$ distinct powers of $\omega$.
\end{description}
\item Let $\alpha \in \F_{q^d}$ have $g \in \F_q[x]$ as it minimal polynomial.
Prove that $\K = \F_q[x]/(g)$ is a subfield of $\F_{q^d}$ and so the degree
of $g$ divides $d$.
\begin{description}
\item[{\sf Solution:}]
Since $g$ is the minimal polynomial it must be irreducible.
So we know from Problem 1 that $\K$ is a field of size $q^k$ where
$k$ is a degree of $g$. Since $\K$ is generated by
elements of $\F_{q^d}$ it is a subfield of $\F_{q^d}$.
Now using the fact that if
some field $\F$ extends some field $\K$ then $\F$ forms a vector space over
$\K$ and so $|\F| = |\K|^r$, we have that $q^d = |\K|^r$ for some integer
$r$. Using $|\K| = q^k$ we have $d = k\cdot r$ or in other words, $k$, the
degree of $g$, divides $d$.
\end{description}
\item
Prove the identity $x^q - x = \prod_{a \in \F_q} (x-a)$.
\begin{description}
\item[{\sf Solution:}]
From the fact that $\F_q[x]$ is a UFD, and the division algorithm, this is
equivalent to showing that $a^q = a$ for every $a \in \F_q$ which is
equivalent to showing $a^{q-1} = 1$ for every non-zero $a$, which in turn
follows from Lagrange's theorem in group theory.
\end{description}
\item
Prove $x^{q^d} - x = \prod_{g \in {\cal P}_{q,d}} g(x)$ where
$${\cal P}_{q,d} = \{g \in \F_q[x] | g \mbox{ irreducible, monic, with }
\deg(g) | d \}.$$
\begin{description}
\item[{\sf Solution:}]
Consider a irreducible polynomial $g$ of degree $k$ dividing $d$.
Consider the field $\K = \F_q[x]/(g(x))$. Note that for every
$\alpha \in \K$ we have $\alpha^{q^k} = \alpha$ and hence $\alpha^{q^d} = \alpha$
(since $k$ divides $d$).
We conclude that for every
polynomial $p(x) \in \F_q[x]$ we have $p(x)^{q^d} = p(x) \emod{g(x)}$.
In particular we have this for the polynomial $p(x) = x$ from which we get
$x^{q^d} = x \emod{g(x)}$
or equivalently $g(x)$ divides $x^{q^d} - x$. We conclude that the
polynomial on the right hand side divides the one on the left.
To prove the reverse direction, first consider any irreducible monic polynomial $h$ dividing $x^{q^d}-x$.
Since all roots of $x^{q^d} - x$ are in $\F_{q^d}$ (Problem 5),
$h$ has a root $\alpha \in \F_{q^d}$ and so $h$ is a minimal
polynomial of $\alpha$.
By Problem 4 we have that $h$ is of degree dividing
$d$. Thus all irreducible factors of $x^{q^d}-x$ appear in the polynomial on
the right. It only remains to note that $x^{q^d} - x$ has no repeated
factors and this is immediate since its derivative is the constant
polynomial $-1$ which has no common factors with $x^{q^d}-x$.
\end{description}
\item
Prove that if $g \in \F_q[x]$ is irreducible of degree $d$,
then it splits completely in $\F_{q^d}$.
(In class we claimed that $g$ has a root in $\F_q[x]/(g)$,
and if one combines this with the assertion that fields of cardinality
$q^d$ are
unique then it follows that $\F_{q^d}$ has a root of $g(x)$.
But the way to prove
the uniqueness is by proving that $g$ has a root in $\F_{q^d}$.)
\begin{description}
\item[{\sf Solution:}]
By Problem 6 we have that $g(x)$ divides
$x^{q^d} - x$, and by Problem 5, we have that $x^{q^d} - x$ splits into
linear factors over $\F_{q^d}$. It follows that $g(x)$ splits into linear
factors over $\F_{q^d}$.
\end{description}
\item
Prove that there is a unique field of any given cardinality: In particular
suppose $g \in \F_p[x]$ is irreducible of degree $a\cdot b$ and $h \in
\F_{p^a}[x]$ is irreducible of degree $b$. Then prove that
$\F_p[x]/(g(x)) \cong \F_{p^a}[x]/(h(x))$.
\begin{description}
\item[{\sf Solution:}]
Let $q = p^a$ and let
$\K$ be any field of cardinality $q^b$. Note that it suffices to show that
$\F_q[x]/(h(x)) \cong \K$. By Problem 7, $h$ has a root
in $\alpha \in \K$. It can be verified that the map $\phi$ that maps
$p(x)$ to $p(\alpha)$ is a bijection among polynomials of degree less
than $b$ and preserves addition and multiplication modulo $h$.
\end{description}
\item Write down the full details of the reduction alluded to in the beginning of Lecture 7 reducing
factorization of a polynomial $f \in \F_q[x]$ with all irreducible factors
having degree $d$, to root finding in $\F_{q^d}$.
\end{enumerate}
\begin{description}
\item[{\sf Solution:}]
TBD
\end{description}
\end{document}