\documentclass[10pt]{article}
\usepackage{amsfonts,fullpage}
%\usepackage{epsfig}
\begin{document}
\input{preamble.tex}
\renewcommand{\F}{{\mathbb F}}
\newcommand{\K}{{\mathbb K}}
\lecture{4}{Feb 17, 2015}{Madhu Sudan}{Akshay Degwekar}
In this lecture, we will review some of the basics of algebra for this course. Primarily we will cover three things - Factoring - When is it reasonable to think about Factorization? Then we will cover Finite fields and finally look at the Trace function.
This course assumes that you know concepts like Groups, Rings, Fields and Vector spaces over fields. We briefly review the definitions, but do not treat the topic in detail. We will mostly deal with enumerable objects and not fields like $\R$ - which require us to deal with imprecise calculation.
\section{Basic Definitions}
\begin{definition}[Group]
A set $G$ with an operator $\cdot : G \times G \to G$, is a \emph{Group} iff it satisfies the following properties:
\begin{enumerate}
\item (Closure) For all $a,b\in G$, $a\cdot b \in G$.\footnote{This is redundant but we still state it}
\item (Associativity) For all $a,b,c\in G$, $a\cdot (b\cdot c) = (a \cdot b) \cdot c$.
\item (Identity) There exists $e\in G$ such that for all $a\in G$, $e\cdot a = a \cdot e = a$.
\item (Inverse) For all $a\in G$ there exists $a^{-1}\in G$ such that $a\cdot a^{-1} = a^{-1}\cdot a = e$.
\end{enumerate}
\end{definition}
A group is \emph{Abelian} if $a\cdot b = b\cdot a$ for all $a,b\in G$. For the sake of brevity we now drop the $\cdot$.
\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) $(R,+)$ is an Abelian group with identity element $0$.
\item (Multiplication) $\cdot$ is closed and associative.\footnote{Also called a semi-group}
\item (Distributivity) For all $a,b,c\in R$, $a \cdot (b + c) = a\cdot b + a\cdot c$.
\end{enumerate}
A ring $(R,+,\cdot)$ is a \emph{commutative} iff for all $a,b\in R$, $a\cdot b = b\cdot a$. A ring is an \emph{integral domain} if it has no zero divisors.
\end{definition}
\begin{definition}[Field]
A tuple $(F,+,\cdot)$ is a field iff the following properties are satisfied:
\begin{enumerate}
\item $(F,+,\cdot)$ is an integral domain.
\item $(F - \{0\},\cdot)$ is an Abelian group.
\end{enumerate}
\end{definition}
\begin{definition}[Vector space]
A set $V$ (whose elements are called \emph{vectors}), along with a addition $+:V\times V \to V$ and a scalar multiplication $\cdot:\mathbb{F}\times V \to V$, is a vector space over the field $\mathbb{F}$ when the properties hold:
\begin{enumerate}
\item (Closure) $(V,+)$ is an Abelian group.
\item (Distributivity) For all $\alpha\in \mathbb{F}$, $u,v\in V$, $\alpha \cdot (u + v) = \alpha\cdot u + \alpha\cdot v$. and
For all $\alpha,\beta\in\mathbb{F}$, $u\in V$,$(\alpha + \beta)u = \alpha u + \beta u$.
\item (Associativity): For all $\alpha,\beta\in\mathbb{F}$, $u\in V$,$\alpha(\beta u) = (\alpha \beta) u$.
\item (Identity): For all $u\in V$, $1\cdot u = u$, where $1$ is the multiplicative unit of $\mathbb{F}$.
\end{enumerate}
\end{definition}
\section{Factoring and Unique Factorization Domains}
In this section we will only consider Unique Factorization Domains (UFDs) - they are subclasses of rings which admit unique factorizations. Here we assume that ring has an identity.
An element of a ring is a \emph{unit} if it has an inverse. Also an element $a$ is \emph{reducible} if there exist non-unit elements $b,c$ such that $a = bc$. An element is \emph{irreducible } if it is not reducible.
\begin{definition}[Unique Factorization Domain] A UFD is an integral domain $R$ in which every non zero element $x$ of $R$ can be written as a product of irreducible elements $x = p_1 p_2 \dots p_t$. This representation is unique upto permutation or multiplication by units.
\end{definition}
We now look at the first construction of a field from a ring. If $R$ is an integral domain, then we can construct the ring of fractions denoted by $\tilde{R}$ as follows -
\begin{definition}[Ring of Fractions]
The field $\tilde{R}$ is the set $R \times R/\set{0}$ where we represent elements as tuples $(a,b)$ where $a\in R$ and $b \in R /\set{0}$ with the operations defined as -
\begin{enumerate}
\item (Equality) $(a,b) = (c,d)$ if and only if $ad = bc$.
\item (Addition) $(a,b) + (c,d) \eqdef (ad + bc, bd)$
\item (Multiplication ) $(a,b) \cdot (c,d) \eqdef (ac,bd)$.
\end{enumerate}
\end{definition}
We can do this for every ring. It is an easy exercise to show that if $R$ is a UFD then $\tilde{R}$ is a Field.
\section{Getting bigger fields from fields}
We have seen one way of constructing Fields from rings, now we will see how to construct rings and fields via polynomials.
If we are given a field $\F$ we consider $\F[x]$ the ring of polynomials over $\F$. Also from the previous section, we know that the ring of fractions of $\F[x]$ that is the ring of rational functions over $\F$ will be a field if $\F[x]$ is a UFD. We claim that this is true.
\begin{theorem}
\label{th:ringF}
If $\F$ is a field, then $\F[x]$ the ring of polynomials is a UFD.
\end{theorem}
The proof proceeds from the ``Division Algorithm'' which says that for all $f,g\in \F[x]$ then $\exists ! q,r$ such that $\deg(r) < \deg(g)$ such that $f = qg+ r$
As an aside, this also gives us the notion of modular arithmetic in this ring and the idea of evaluation $f(\alpha)$ can be defined as the remainder when $f$ is divided by $(x-\alpha)$. Furthermore from here we can argue that every degree $d$ polynomial over a field has at most $d$ roots.
A more general version of Theorem \ref{th:ringF} stated below is due to Gauss.
\begin{theorem}
If $R$ is a UFD then $R[x]$ is a UFD
\end{theorem}
\begin{proof-sketch}
To prove the theorem, we first observe that $\tilde{R}[x]$ is a UFD. This follows from the fact that $\tilde{R}$ is a field and then we apply Thm \ref{th:ringF}.
The meat of the proof is the so called \emph{Gauss's Lemma} which we just state.
\begin{lemma}[Gauss's Lemma] For a polynomial $p \in R[x]$. If $p$ has a non trivial factorization in $\tilde{R}[x]$ then it has a non trivial factorization in $R[x]$.
\end{lemma}
Using Gauss's Lemma, we see that $R[x]$ has to be a UFD because
$\tilde{R}[x]$ is a UFD. Since $\tilde{R}[x]$ is a UFD, there cannot be multiple factorizations for a polynomial in $R[x]$ because these would imply non-unique factorizations in $\tilde{R}[x]$ and that the existence of a factorization is guaranteed by the Gauss's lemma.
\end{proof-sketch}
As an interesting fact, we note that this procedure not only gives us larger UFD's but also the Hensel's Lifting which we will encounter later in the course, allows a near black box translation of algorithms for factoring on $R$ to give algorithms for factoring on $R[x]$.
We have seen one way to construct bigger fields from fields - $\F(x)$ - the field of fractions. Now we see another way of constructing fields.
Consider a field $\F$ and an irreducible polynomial $g \in \F[x]$ and consider $\F[x]/g$ to be the polynomials modulo $g$. We claim that this is a field. This gives us a way to construct bigger Finite fields from smaller finite fields.
\section{Finite Fields}
For most of this course, we will deal with finite fields. We cover some of the basics here.
Let $p$ be a prime and $q = p^t$ be a prime power. We denote fields like $\F$.
\subsection{Prime fields}
Prime fields are fields of a prime size. We show that for every prime $p$, there is a field of size $p$ which is simply given by $\Z /p\Z$ that is the set of residues modulo $p$.
\begin{theorem}
For every prime $p$, a finite field of size $p$ exists, and moreover, it is unique up to isomorphism. We denote this field by $\F_p$.
\end{theorem}
\begin{definition}[Characteristic]
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}
Fields are said to be characteristic 0, if they do not have finite characteristic. All finite fields have a finite characteristic which is in fact a prime.
\subsection{Representing Finite Fields}
To perform computation efficiently, we want to succinctly represent the elements in a form amenable to algebraic manipulation. We will see three representations.
\paragraph{Vector Representation}
We can show that if $\K$ and $\F$ are finite fields such that $\F \subseteq \K$ then $\K$ is in fact a vector space over $\F$.
Also if we start with a finite field $\K$ such that $\abs{K} = p^t$ then $\F_p \subseteq \K$ and hence the finite field has to have a size $\abs{\F_p}^t$ for some $t$. We can now represent it as a vector over $\F_p$.
This representation is succinct and can be used to efficiently perform addition but is inadequate for multiplication.
\paragraph{Matrix Representation} Let $\alpha \in \F$. Now $\alpha$ defines a linear map from $\F to \F$ $\beta \rightarrow \alpha\beta$. So we can represent it as a matrix $M_\alpha$.
This representation is good for both addition and multiplication because for $\alpha, \gamma \in \F$, $M_{\alpha+\gamma} = M_\alpha + M_\gamma$ and $M_{\alpha\gamma} = M_\alpha M_\gamma$. The representation is fairly compact - it takes $\log(\abs{F})^2$ bits.
\subsection{Existence of Finite Fields}
Constructing non-prime fields is more interesting; we will actually construct them starting with prime fields.
We will now prove the theorem that a finite field of size $r$ exists if and only if $r = p^t$ for some prime $p$ and natural number $t$.
\paragraph{The first attempt} One way of showing this is to start with the observation that for a field $\F_p$ consider an irreducible polynomial of degree $d$ and construct the field $\F[x]/g$. The size of this field will be $p^d$.
This approach works, but we need to show the existence of an irreducible polynomial for every degree. There is a sophisticated non constructive argument that does this.
But instead we here take a different approach. This requires us to introduce some machinery.
\subsubsection{The right approach}
First we start off with an observation.
\begin{claim}\label{cl:one_more_root}
That if $g(y)$ is an irreducible polynomial in $\F[y]$ and $\K = \F[x]/g(x)$ be the field constructed. Then,
$$(y-x) | g(y)$$
\end{claim}
\begin{proof}
Substitute $y=x$ to get $g(x) \bmod g(x) = 0$ and hence it is a factor.
\end{proof}
Now we consider the notion of a splitting field
\begin{definition}[Splitting Field] The splitting field of $g(x) \in \F[x]$ is the smallest field $\K$ such that $F \subseteq \K$ such that $g$ splits into linear factors over $\K[x]$.
\end{definition}
Now we know from Claim \ref{cl:one_more_root} that splitting fields exist. Now for the construction. Suppose we want to construct a field of size $q = p^t$. Consider the polynomial $x^q-x$ over $\F[x]$. Let $\K$ be its splitting field. We consider the set of roots - $S = {\alpha\in \K \mid \alpha^q-\alpha = 0}$. We first see that $\abs{S} \leq q$ because a polynomial has at most degree many roots. Also, we can observe that $\abs{S} \geq q$ because it is the splitting field. And hence $\abs{S} = q$. It is left as an exercise to show that the set $S$ is a field and hence the exact field we want.
This completes the existence argument.
\subsection{Additional properties of Finite fields}
\begin{theorem}
The multiplicative group over any finite field $\F$ is cyclic.
\end{theorem}
\begin{theorem}
All finite fields have generators. Let $\F, \K$ be finite fields such that $\abs{\K} = \abs{\F}^t$. Then $\exists \alpha \in \K$ such that the $\F$-span of $\set{1, \alpha, \alpha^2, \dots \alpha^{t-1}}$\footnote{$\F$-span is the linear span with scalars from $\F$} spans $\K$.
\end{theorem}
\begin{theorem}
For field $\K$ of characteristic $p$, the unique embedding of $\F_p$ is given by the set $\set{\alpha\in \K \mid \alpha^p = \alpha}$
\end{theorem}
\section{Trace}
Trace is an important function that maps a large field to its corresponding base field.
\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}
A priori it is not clear why the trace should be in $\F_q$, to show that it is well defined, we consider $\mbox{Tr}(\beta)^q = (\beta + \beta^q + \dots \beta^{q^{r-1}})^q = \beta^q + \beta^{q^{2}}+\dots \beta^{q^{r-1}}+\beta^{q^{r}} = \mbox{Tr}(\beta)$.\footnote{We make use of the fact that $(a+b)^{p^t} = a^{p^t}+b^{p^t}$ in fields of characteristic $p$} Hence $\mbox{Tr}(\beta)\in \F_q$.
\begin{lemma}$\mbox{Tr}$ is linear. That is $\mbox{Tr}(x+y) = \mbox{Tr}(x)+\mbox{Tr}(y)$ and $\mbox{Tr}(\alpha x) = \alpha \mbox{Tr}(x)$
\end{lemma}
\begin{lemma}
$\mbox{Tr}$ is a $q^{r-1}$-to-$1$ map.
\end{lemma}
\begin{proof}
Let $\alpha\in\mathbb{F}_q$. Then $\mbox{Tr}(x) - \alpha$ is a polynomial that maps $\mathbb{F}_{q^r}$ to $\mathbb{F}_q$ with degree $q^{r-1}$, and thus it has at most $q^{r-1}$ zeros. But that means every $\alpha\in\mathbb{F}_q$ has a preimage under $\mbox{Tr}$ of size $q^{r-1}$: otherwise there would be elements of $\mathbb{F}_{q^r}$ that would not map to anything under $\mbox{Tr}$, which is absurd.
\end{proof}
Trace also has a very nice composition property. If we denote the trace from field $\K$ to $\F$ by $\mbox{Tr}_{\K \rightarrow \F}$ where $\F \subseteq \K$ then if
$\mathbb{L}$ further extends $\K$ then we have
$$\mbox{Tr}_{\mathbb{L}\rightarrow \F} = \mbox{Tr}_{\K \rightarrow \F}\circ \mbox{Tr}_{\mathbb{L} \rightarrow \K}.$$
So, trace has these nice properties and also trace is a very sparse polynomial and this has interesting consequences that we will see in the course.
Finally, trace allows us to represent a elements of a $\K$ in terms of $\F$ in the following way. If $\gamma_1, \gamma_2, \dots \gamma_r$ in $\K$ are $\F$-linearly independent, then the function $\alpha \rightarrow (\mbox{Tr}(\alpha \gamma_1), \mbox{Tr}(\alpha \gamma_2), \dots \mbox{Tr}(\alpha \gamma_r))$
is a bijection. This bijection again is very nice with respect to addition and not so much for multiplication.
\paragraph{Acknowledgments} Quite a few things in this scribe have been recycled from the scribed notes of the previous iteration of the course.
\end{document}