\documentclass[fullpage]{article}

\newtheorem{define}{Definition}
\input{preamble.tex}

\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}

\begin{document}
\lecture{3}{February 15, 2012}{Madhu Sudan}{Henry Yuen}

Of central importance to Algebra and Computation are structures such as groups, rings, and especially finite fields. Here, we review basic definitions and cover the construction of finite fields.

\section{Basic definitions: Groups, rings, fields, vector spaces}
	
\begin{definition}[Group]
For a set $G$ and an operator $\cdot : G \times G \to G$, a pair $(G,\cdot)$ is a group iff the following properties are satisfied:

	\begin{enumerate}
		\item (Identity) There exists $e\in G$ such that for all $a\in G$, $a \cdot e = a$. 
		\item (Associativity) For all $a,b,c\in G$, $a\cdot (b\cdot c) = (a \cdot b) \cdot c$. 
		\item (Inverses) For all $a\in G$, there exists an element $b\in G$ such that $a \cdot b = e$.
	\end{enumerate}
	
\noindent We say a group $(G,\cdot)$ is commutative or Abelian iff for all $a,b\in G$, $a \cdot b = b \cdot a$. If $(G,\cdot)$ has an identity and satisfies associativity but not all elements have inverses is called a monoid.
\end{definition}

\begin{definition}[Ring]
For a set $R$ and binary operators $\cdot$ and $+$ over $R$, the triple $(R,+,\cdot)$ is a ring iff the following properties are satisfied:

	\begin{enumerate}
			\item (Commutative addition with additive identity) $(R,+)$ is an Abelian group with identity element $0$.
			\item (Multiplication with multiplicative identity) $(R,\cdot)$ is a monoid with identity element $1$.
			\item (Distributivity) For all $a,b,c\in R$, $a \cdot (b + c) = a\cdot b + a\cdot c$.
	\end{enumerate}

\noindent We say that a ring $(R,+,\cdot)$ is a commutative ring iff for all $a,b\in R$, $a\cdot b = b\cdot a$.
\end{definition}

\begin{definition}[Field]
A tuple $(F,+,\cdot)$ is a field iff the following properties are satisfied:
	\begin{enumerate}
		\item $(F,+,\cdot)$ is a ring.
		\item $(F - \{0\},\cdot)$ is an Abelian group.
	\end{enumerate}
\end{definition}

\begin{definition}[Vector space]
$V$ is a vector space over the field $\mathbb{F}$ if there is an addition operation $+:V\times V \to V$ and an scalar multiplication operation $\cdot:\mathbb{F}\times V \to V$ such that:
 
	\begin{enumerate}
		\item (Closure under addition) $(V,+)$ is an Abelian group.
		\item (Scalar distributivity) For all $a\in \mathbb{F}$, $u,v\in V$, $\alpha \cdot (u + v) = \alpha\cdot u + \alpha\cdot v$.
	\end{enumerate}

\end{definition}

\begin{proposition}
All finite vector spaces $V$ over a field $\mathbb{F}$ is isomorphic to $\mathbb{F}^n$ for some $n$.
\end{proposition}

\section{Finite Fields}

Much of the course will be concerned with computation over finite fields. Here, we'll cover the basics of finite fields: existence, uniqueness, and construction. 

\subsection{Notation}

All the fields discussed below will be finite. $p$ and $q$ will almost always denote a prime and a prime power ($p^t$ for some prime $p$ and positive integer $t$), respectively.

\subsection{Prime fields}

\begin{definition}
A field $\mathbb{F}$ is prime if $|\mathbb{F}| = p$ for some prime $p$.
\end{definition}

\begin{theorem}
For every prime $p$, a finite field of size $p$ exists, and moreover, it is unique up to isomorphism.
\end{theorem}

\begin{proof}
	Consider the quotient ring $\mathbb{Z}/p\mathbb{Z}$. It is a field, and a field of size $p$. Let $\mathbb{K},\mathbb{L}$ be two fields of order $p$. For isomorphism, map $0_\mathbb{K}$ to $0_\mathbb{L}$, $1_\mathbb{K}$ to $1_\mathbb{L}$; it is clear that this mapping extends naturally and uniquely to an isomorphism.
\end{proof}

\begin{definition}
	The characteristic of a finite field $\mbox{char}(\mathbb{F})$ is the smallest integer $n$ such that the multiplicative identity $1$ added to itself $n$ times is equal to the additive identity $0$.
\end{definition}

\subsection{Constructing Fields from Fields}

Constructing non-prime fields is more interesting; we will actually construct them starting with prime fields. But before we get into that, let's look at how we can construct larger fields from smaller ones.

\begin{definition}[Field of fractions]
	Let $R$ be an integral domain. The field of fractions $F(R) = R\times R/\sim$ where $\sim$ is an equivalence relation such that $a,b,c,d\in R$, $(a,b) \sim (c,d)$ if and only if $ad = bc$. 
\end{definition}

\begin{proposition}
The field of fractions $F(R)$ for an integral domain $R$ is a field.
\end{proposition}

Here are two primary ways of constructing fields from fields. Let $\mathbb{F}$ be a field, and let $\mathbb{F}[X]$ be the ring of polynomials with coefficients in $\mathbb{F}$.

\begin{enumerate}
	\item $F(\mathbb{F}[X])$, the field of fractions, is called the field of \emph{rational functions} over $\mathbb{F}$.
	
	\item Let $g\in \mathbb{F}[X]$ be an irreducible polynomial. Then $\mathbb{F}[X]/(g)$ is a field.
\end{enumerate}

\subsection{Constructing Non-prime Fields}

\begin{lemma}
	Let $\mathbb{F}$ be a finite field. Then it has prime characteristic.
\end{lemma}

\begin{fact}
	Let $a,b\in \mathbb{F}$ where $\mathbb{F}$ has characteristic $p$. Then $(a + b)^{p^r} = a^{p^r} + b^{p^r}$ for any positive integer $r$.
\end{fact}

\begin{lemma}
	Let $\mathbb{F}$ be a finite field, with characteristic $p$. Then $\mathbb{F}$ is an $\mathbb{F}_p$-vector space. 
\end{lemma}

\begin{corollary}
	Let $\mathbb{F}$ be a finite field. Then $|\mathbb{F}| = p^t$ for some prime $p$ and some positive integer $t$.
\end{corollary}

\begin{lemma}[Division Lemma]
	Let $f,g$ polynomials in $\mathbb{F}[X]$ for some finite field $\mathbb{F}$. Then there exists a unique pair $(q,r)\in\mathbb{F}[X]$ such that $\deg(r) < \deg(g)$ and $f = q\cdot g + r$.
\end{lemma}

\begin{corollary}
Let $f\in\mathbb{F}[X]$ have degree $r$. Then $f$ has at most $r$ roots in $\mathbb{F}$.
\end{corollary}


\begin{corollary}
	Suppose $\mathbb{F}$ were some field of order $q$. Then $x^{q} - x = \prod_{\alpha \in \mathbb{F}}{(x-\alpha)}$.
\end{corollary}
\begin{proof}
	By the division lemma, $x^q - x$ has at most $q$ roots in $\mathbb{F}$. It now suffices to show that for all $\alpha \in \mathbb{F}$, $x - \alpha$ divides $x^q - x$, or equivalently that $\alpha$ is a root. If $\alpha = 0$, then it is clear. Otherwise, note that non-zero $\alpha$ is contained in $\mathbb{F}^*$, the cyclic multiplicative group of $\mathbb{F}$, and by Lagrange's theorem $\alpha^q = \alpha$, and we are done.
\end{proof}

\begin{lemma}[Splitting Field Lemma]
	For all $g\in \mathbb{F}[X]$, there exists a field extension $\mathbb{K}$ of $\mathbb{F}$ such that $g$ splits completely into linear factors in $\mathbb{K}[X]$.
\end{lemma}
\begin{proof}
	Suppose $\mathbb{F}$ were of order $q$. There are two cases: $g\in\mathbb{F}[X]$ is irreducible, or not irreducible. Support it were irreducible. Consider the quotient field $\mathbb{K} = \mathbb{F}[X]/(g)$; it is of size $q^r$ where $r = \deg(g)$. Then by the above corollary, $g$ splits completely into linear factors in $\mathbb{K}[X]$. If $g$ were not irreducible, then we can write $g = ab$, where $a$ is an irreducible polynomial and $b$ is a nontrivial polynomial. Since $a$ splits completely over $\mathbb{F}[X]/(a)$, we can then recurse on splitting $b$ over an extension field of $\mathbb{F}[X]/(a)$, until we finally obtain a final extension field where $g$ completely splits.
\end{proof}


\begin{definition}
	Let $\mathbb{F}\subseteq\mathbb{K}$ be fields, and $g$ a polynomial in $\mathbb{F}[X]$. Then $\mathbb{K}$ is called the splitting field of $g$ over $\mathbb{F}$ if and only if $g$ factors completely into linear polynomials in $\mathbb{K}[X]$.
\end{definition}

\noindent We will use the Splitting Field Lemma to construct our field of order $q^r$ for any $r$.

\begin{proposition}
	Let $\mathbb{K}$ be a splitting field of $x^{q^r} - x$ over $\mathbb{F}_q$. Then $S = \{\alpha \in \mathbb{K} \mid \alpha^{q^r} = \alpha \}$ forms a field of order $q^r$.
\end{proposition}


\begin{lemma}[Unique containment]
	Let $\mathbb{F},\mathbb{G}$ be subfields of $\mathbb{K}$. If $|\mathbb{F}| = |\mathbb{G}|$, then $\mathbb{F} = \mathbb{G}$.
\end{lemma}

\begin{lemma}[Uniqueness of finite fields]
Let $\mathbb{F}_{p^r}$ be a finite field of order $p^r$ as constructed above. It is unique up to isomorphism.
\end{lemma}
\begin{proof}
	Let $\mathbb{K},\mathbb{L}$ be finite fields of order $p^r$. Then both are splitting fields of the polynomial $x^q - x$, where we let $q = p^r$. The finite field $\mathbb{F}_p$ embeds uniquely into both $\mathbb{K}$ and $\mathbb{L}$. Let $\phi$ be the isomorphism between the copy of $\mathbb{F}_p$ in $\mathbb{K}$ and the copy in $\mathbb{L}$. Treating $\mathbb{K}$ and $\mathbb{L}$ as vector spaces of $\mathbb{F}_p$ where each element of the vector space is an ordered tuple of $\mathbb{F}_q$, it is clear that $\phi$ extends to an isomorphism $\tilde{\phi}$ between $\mathbb{K}$ and $\mathbb{L}$.  
\end{proof}

\noindent We've shown that if we are given an irreducible polynomial $g(x)\in\mathbb{F}_q[X]$ of degree $r$, then we can construct the unique field of size $q^r$. Now we show that such an irreducible polynomial of degree $r$ always exists, and hence fields of all prime powers exist.

\begin{lemma}
If $g$ is an irreducible polynomial of degree $r$ in $\mathbb{F}_q[X]$, then $g$ divides $x^{q^r} - x\in\mathbb{F}_q[X]$. 
\end{lemma}
\begin{proof}
	Consider $\mathbb{K} = \mathbb{F}_q[X]/(g)$, which is a field of order $q^r$. The multiplicative group $\mathbb{K}^*$ is cyclic and has order $q^r - 1$, and by Lagrange's theorem $x^{q^r} \equiv x \mod g(x)$, and thus $g$ divides $x^{q^r} - x$. 
\end{proof}

\begin{lemma}
Let $q$ be a prime power and $r$ be some positive integer. Then:
\[ x^{q^r} - x = \prod_{\substack{g \text{ irreducible, monic } \in \mathbb{F}_q[X]\\ \deg(g) | r}}g(x) \]
\end{lemma}

\begin{corollary}
For all prime power $q$, positive integer $r$, there exist an irreducible, monic polynomial $g\in \mathbb{F}_q[X]$ of degree $r$.
\end{corollary}
\begin{proof}
By the above lemma we have that $x^{q^r} - x$ is the product of monic, irreducible polynomials in $\mathbb{F}_q[X]$ with degree that divide $r$. Via a clever counting argument (which will be filled in the more polished version of these scribe notes later), there must exist a monic, irreducible $g$ with degree exactly equal to $r$.
\end{proof}

\noindent We have now shown that constructing $\mathbb{F}_q[X]/(g)$ for some irreducible, degree $r$ polynomial $g$ will give the unique finite field of order $q^r$, up to isomorphism.

\begin{definition}[Minimal polynomial]
Let $\mathbb{K}$ be a finite field extension of $\mathbb{F}$. Let $\alpha \in \mathbb{K}$. Then the minimal polynomial of $\alpha$ over $\mathbb{F}$ is a monic, irreducible polynomial $g$ of minimal degree in $\mathbb{F}[X]$ such that $g(\alpha) = 0$.
\end{definition}

\section{Functions over finite fields}

There is a nice way of looking at functions over finite fields as polynomials. Consider some function $f:\mathbb{F}_q \to \mathbb{F}_q$. $f$ can be, without loss of generality, be represented as some univariate polynomial of degree at most $q-1$ (this follows from polynomial interpolation). 

A function $f:\mathbb{F}_{q^r} \to \mathbb{F}_q$ can be understood in a very nice way by first viewing $f$ as some function $\tilde{f}:\mathbb{F}_{q^r} \to \mathbb{F}_{q^r}$ which just happens to map only into the smaller subfield $\mathbb{F}_q$. Then, as before, we can represent $\tilde{f}$ as a polynomial $\tilde{f}(x) = \sum{c_ix^i}$. However, since we know the range of $\tilde{f}$ is contained in $\mathbb{F}_q$, we have that

\[\left(\sum{c_i x^i}\right)^q = \left(\sum{c_i x^i}\right)\]

\noindent in $\mathbb{F}_{q^r}$. 

\begin{definition}[Trace]
	The trace $\mbox{Tr}:\mathbb{F}_{q^r} \to \mathbb{F}_{q}$ is defined as $\mbox{Tr}(x) = x + x^q + \cdots + x^{q^r - 1}$.
\end{definition}

\begin{lemma}[Linearity of Trace]
	$\mbox{Tr}$ is linear.
\end{lemma}

\end{document}





