\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}