\begin{document}
\documentclass[11pt]{article}

\usepackage{latexsym}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{hyperref}
\usepackage{algorithmic}
\usepackage{algorithm}
\usepackage{complexity}
\usepackage{graphicx}

\usepackage{palatino} %what a beautiful font!


\newcommand{\handout}[5]{
  \noindent
  \begin{center}
    \framebox[\textwidth]{
      \vbox{
        \hbox to \textwidth { {\bf #2}\hfill {\bf Computational Number Theory }
       }
        \vspace{4mm}
        \hbox to \textwidth { {\Large \hfill #5  \hfill} }
        \vspace{2mm}
        \hbox to \textwidth { {\em #3 \hfill #4} }
      }
    }
  \end{center}
  \vspace*{4mm}
}

\newcommand{\lecture}[4]{\handout{#1}{#2}{Instructor: #3}{Scribe:
    #4}{Lecture #1}}

\newtheorem{theorem}{Theorem}
\newtheorem{theorem*}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{definition}[]{Definition}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{fact}[]{Fact}
\newtheorem{subclaim}[theorem]{Subclaim}

% my custom commands
\newcommand{\inparen}[1]{\left(#1\right)}             %\inparen{x+y}  is (x+y)
\newcommand{\inbrace}[1]{\left\{#1\right\}}           %\inbrace{x+y}  is {x+y}
\newcommand{\insquar}[1]{\left[#1\right]}             %\insquar{x+y}  is [x+y]
\newcommand{\inangle}[1]{\left\langle#1\right\rangle} %\inangle{A}    is <A>
\newcommand{\abs}[1]{\left|#1\right|}                 %\abs{x}        is |x|
\newcommand{\norm}[1]{\left\Vert#1\right\Vert}        %\norm{x}       is ||x||
\newcommand{\union}{\cup}
\newcommand{\Union}{\bigcup}
\newcommand{\intersection}{\cap}
\newcommand{\Intersection}{\bigcap}
\newcommand{\super}[2]{#1^{\inparen{#2}}}             %\super{G}{i-1} is G^{(i-1)}
\newcommand{\setdef}[2]{\inbrace{{#1}\ : \ {#2}}}
\newcommand{\inv}[1]{#1^{-1}}
\newcommand{\inrpdt}[2]{\left\langle{#1},{#2}\right\rangle}%\inrpdt{x}{y} is <x,y>.
\newcommand{\pderiv}[2]{\frac{\partial #1}{\partial #2}}
\newcommand{\iso}{\cong}
\newcommand{\bea}[1]{\begin{eqnarray*} #1 \end{eqnarray*}}
\newcommand{\legendre}[2]{\inparen{\frac{#1}{#2}}}

% Commands specific to this file
% TODO: Find the right way to typeset group index
\DeclareMathOperator{\Sym}{Sym}
\newcommand{\gpidx}[2]{\insquar{#1 : #2}}             %\gpidx{H}{K}   is [H : K]
\newcommand{\gpigs}[2]{\gpidx{\super{G}{#1}}{\super{G}{#2}}} %Group index of g super ...
\newcommand{\llhd}{\!\!\lhd\!\!\lhd}
\newcommand{\roundoff}[1]{\left\lfloor #1 \right\rceil}


% \newcommand{\ceil}[1]{\lceil #1 \rceil}
\newcommand{\floor}[1]{\lfloor #1 \rfloor}
\newcommand{\F}{\mathbb{F}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\Z}{\mathbb{Z}}
\renewcommand{\R}{\mathbb{R}}
\renewcommand{\C}{\mathbb{C}}

%for algorithms
\renewcommand{\algorithmicrequire}{\textbf{Input:}}

% Problems we look at
\newcommand{\GIso}{\lang{Graph\text{-}Iso}} %Without \text, ugly minus instead of hyphen.
\newcommand{\GAut}{\lang{Graph\text{-}Aut}}
\newcommand{\SStab}{\lang{Set\text{-}Stab}}

%for Quantum computing
\newcommand{\q}[1]{\left|#1\right\rangle}


\lecture{8: More on Finite Fields}{CS681}{Piyush P Kurur}{Ramprasad Saptharishi}

We will be spending some time on understanding the structure of fields
of finitely many elements. In this class we shall some necessary
properties that finite fields (or any field in general) should hold. 

\section{Characteristic of Finite Fields}

Looking at the examples of fields that we know of, we clearly see that
$\Q$ and $\Z/p\Z$ are different. Apart from just the cardinality
properties, $\Z/p\Z$ has this property of $k$ and $p-k$ cancelling
off. Using this as a motivation, let us define what a characteristic
of a field is. First we shall state it formally and then look at a
better interpretation of it. 

\begin{definition}
For any ring $R$, there exists the identity element $1.$ Consider the
homomorphism 
\bea{
\phi: \Z & \longrightarrow & K\\
n & \mapsto & n\cdot 1
}
where $n\cdot 1$ simple means adding $1$, in $R$, $n$ times. And $\Z$
being a PID, the kernel of this map will be of the form $m\Z.$ This
number $m$ is called the characteristic of the field. 
\end{definition}

In other words, the characteristic is the smallest number $m$ such
that $m$ times the identity element is zero. 

However, it is possible that $m\cdot 1$ will never be zero. For
example, take the rings like $\Q,\R,\C,\Q[x]$ etc. The corresponding
map will hence have a trivial kernel and that is the ideal $0\Z.$
Hence the characteristics of these rings is $0$ and not
infinity. This is just the language. Infact, we shall refer
characteristic $0$ rings as rings of infinite characteristic. 


Here is a trivial lemma.
\begin{lemma}
Let $R$ be a ring (with identity) of characteristic $m$ and $S$ be a
ring that contains $R.$ Then characteristic of $S$ is also $m.$
\end{lemma}
\begin{proof}
$R$ has characteristic $m$ implies that $\phi: \Z \longrightarrow R$
  has the kernel as $m\Z.$ The homomorphism works just on the identity
  element of $R$ and hence would be exactly the same on $S$ (since $S$
  has to share its identity element with $R$). Thus, since the
  homomorphism is the same, the kernel has to be the same.
\end{proof}

\subsection{Characteristic of Fields}

Now, suppose $m$ is the characteristic of any ring $R$. Then by
definition the kernel of the map $\phi$ is $m\Z.$ And by the isomorphism
theorem, we know that the following map is injective:
$$
\hat{\phi}: \Z/m\Z \longrightarrow R
$$
And therefore, in a way, a copy of $\Z/m\Z$ is sitting inside $R.$
Thus, $\Z/m\Z$ is a subring of $R.$\\

Now let us look at the characteristic of fields instead of rings. Let
us take the identity element and just keep adding it. Either, for some
$m$ we have $m\cdot 1 = 0$ or it just keeps going on. If it becomes
$0$, we know that the field has characteristic $m.$ The other case is
the characteristic $0$ case. 

Now, can it be possible that $m$ is composite? Suppose $m = pq$ where
both $p,q<m.$ Since we know that $m\cdot 1 = 0$, this means that
$(p\cdot 1)(q\cdot 1) = pq\cdot 1 = 0.$ And by our assumption, we know
that neither $p\cdot 1$ nor $q\cdot 1$ is zero; we just showed the
existence of zero divisors in a field! That is not possible. Hence
summarizing as a theorem: 

\begin{theorem}
Any field $F$ must either have $0$ characteristic or a characteristic
that is a prime. 
\end{theorem}

Let us pick any field $F$ whose characteristic is a prime $p.$ We know
that if we let $1$ 'generate' a subfield of its own by just adding
itself, it would get to $\Z/p\Z.$ Thus for any field of prime
characteristic, it should contain $\Z/p\Z.$ We shall refer to $\Z/p\Z$
by $\F_p.$

For a field of infinite characteristic (characteristic $0$, just
language), $1$ would keep being added on without ever giving a $0.$
Thus it would generate the entire set of positive integers. And since
additive inverses should exist, the negative integers should also
belong to the field. And further, because of the multiplicative
inverses, all rational numbers should exist. Hence, every field either
contains $\F_p$ or $\Q.$\\

Please keep in mind that finite characteristic does not mean finite
cardinality. As a counter example, look at the following set:
$$
\F_p(X) = \setdef{\frac{f(X)}{g(X)}}{f,g \in \F_p[X],g\neq 0}
$$
that the set of rational functions over one variable. This field has
infinite cardinality and since it contains $\F_p$ has characteristic
$p.$\\

\section{Order of Finite Fields}

Now let us take any finite field $K$. Then this field must have
characteristic that is not zero. Why? Since if it did have
characteristic zero, it would contain $\Q$ and hence be infinite. 

Since the characteristic of this field is finite, say $p$, it contains
$\F_p.$ Recall that if  $K$ is a field that contains another field $F$
(in our case $\F_p$), then $K$ is an extension of $F.$

Thus, this tells us that any field of characteristic $p$ is a
vector space over $\F_p.$ Since we now have a vector space, we can
talk of the dimension of this vector space. The dimension cannot be
infinite. Why? For it it was, then the basis, which belongs to $K$,
would be an infinite set. And this is an obvious contradiction since
we assumed that $K$ was finite. 

Thus, the dimension of $K$ over $\F_p$ is finite, say $s.$
And since every element of $K$ can be written as a $s$-tuple of
elements of $\F_p,$ this means that the number of elements of $K$ is
$p^s.$

And, from our earlier theorem, we know that the characteristic of a
finite field has to be a prime. Hence the order of any finite field
has to be a power of a prime. 

\begin{theorem}
Any finite field has $p^s$ elements where $p$ is a prime and $s$ a
positive integer. 
\end{theorem}

The moment we make such a statement, we have two questions in mind. 
\begin{itemize}
\item Existence: For every prime $p$ and positive integer $s$, do we have a field
  of $p^s$ elements?
\item Uniqueness: Can we have two different fields with $p^s$ elements?
\end{itemize}

We shall soon see that the answer to the first question is yes and the
second is no. There is exactly one field of size $p^s.$ 

\subsection{Creating Extensions of $\F_p$}

The general question is how to obtain extension fields of a given
field. As a motivation, let us look at $\R.$ How do we get an
extension field of $\R$? In a sense, we need to increase our
domain. Therefore, we need to find elements that don't belong to $\R.$
The way to do that is to look at roots of polynomials. There is no
root of the polynomial $X^2 + 1$ in $\R.$ Hence, just add the
root. This is formally done by quotienting. 

But there is a small catch before we do that. We now know that we have
the complex number $i$ is a root of $X^2 + 1$ but it is of course the
root of $(X^2+1)(X^{213} - 3X^{127} +897)$ as well. This is where the
concept of minimal polynomial comes in. 

\begin{definition}
Let $L$ be an extension of $K$. For any $\alpha \in L$, the mimimum
polynomial of $\alpha$ over $K$ is the monic polynomial of smallest
degree over $K$ that has $\alpha$ as a root.
\end{definition}

Again, the questions of existence and uniqueness comes in. Does every
$\alpha$ have a minimum polynomial? The answer is no, and the example
is $\pi$ over $\Q.$ It doesn't make sense to talk of a minimum
polynomial when the number is transcendental. 

But suppose the number is not transcendental, that it is a root of
some polynomial. Then do we have a unique minimum polynomial?
Yes. Since if $f$ and $g$ are two polynomials of smallest degree that
has $\alpha$ as a root, then so does $gcd(f,g)$ and the gcd clearly
has smaller degree. This then contradicts that $f$ and $g$ had least
degree. Thus the minimum polynomial is unique. 

And by the same reason, the minimum polynomial must be
irreducible. For if $f$ was the minimum polynomial of $\alpha$ and if
$f(X) = g(X)h(X)$ then $\alpha$ must be a root of either $g$ or $h$
and their degree is strictly less than $f.$ Thus the minimum
polynomial if indeed irreducible. \\

Another way is the following. We have some $\alpha \in L$ and we want
the minimum polynomial of $\alpha$. Consider the following
homomorphism. 

\bea{
\text{eval}_\alpha: K[X] & \longrightarrow & L\\
f(X) & \mapsto & f(\alpha)
}

The map is called the evaluation map since it just evaluates every
polynomial at $\alpha$. The kernel of this map will be an ideal of
$K[X]$, a principle ideal. The generator of this ideal is the minimum
polynomial. \\


Here is a way to create extensions. Look at $\F_p[X]$ and take some
irreducible polynomial $f$ of it. Then we know that $\F_p[X]/(f)$ is a
field since the ideal $(f)$ is maximal as $f$ is irreducible. If the
degree of $f$ is $d$, then this would give is a field of size $p^d.$\\

We shall see this in more detail next time. 

\end{document}