\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{9: Uniqueness of $\F_{p^m}$}{CS681}{Piyush P Kurur}{Ramprasad Saptharishi} Last lecture we closed with two questions of existence and uniqueness of fields of order $p^m.$ This lecture, we shall the question of uniqueness and also understand some other properties of extensions. \section{Some More Properties of Field Extensions} Firsly, we need to understand what quotienting means. Suppose we have a field $K$ and we look at the polynomial ring over this field - $K[X].$ Let us take some irreducible polynomial $f$ and look at $K[X]/(f(X)).$ What does this mean? Quotienting means that you consider all occurences of the ideal $(f(X))$ as zero. So in particular, if you look at $f(X)$ in this ring, it would be zero. Hence the variable $X$ can now be thought of as a root of $f.$ Infact, this is exactly what we do to adjoin roots. Suppose we have a field $K$ and we need to adjoin some element $\alpha.$ We take the minimum polynomial $f$ of $\alpha$ and we look at $K[X]/(f(X)).$ Here, essentially, $X$ is $\alpha.$ This is how we built $\C.$ We looked at $\R[X]$ and quotiented it with the ideal generated by $X^2 + 1.$ And now note that there is no real distinction between $-i$ or $i.$ Algebraically, $\R(i) \iso \R(-i) = \C.$ So the general point to note is that if $\alpha$ and $\beta$ are both roots of the same irreducible polynomial $f$, then $K(\alpha) \iso K(\beta) \iso K[X]/(f(X)).$ \subsection{Splitting Fields} Until we knew that an object called $\C$ existed, we had no idea if there was an element $i$ such that $i^2 = -1.$ So as such, it doesn't make sense to adjoin some element until you know where it is from. When you look at $K[X]/(f(X))$, we said that $X$ can be identified with a root of $f$, but what root? Where is this root? I know it's not in $K$ (for if it were, $X-\alpha$ is a factor of $f$ and hence can't be irreducible), but where else is it? This is where splitting fields come in. \begin{definition} A splitting field of a polynomial $f$ over $K$ is the smallest field extension $E/K$ that contains all the roots of $f.$ Or equivalently, it's the smallest field $E$ where the polynomial $f$ factorizes into linear factors. \end{definition} The first thing to note is that this is not equivalent to adjoining a root. To illustrate the difference, take the field $\Q$ and let us look at the polynomial $X^3 - 2.$ This polynomial is irreducible and hence we can talk of the field $\Q[X]/(X^3 - 2)$ and identify the element $X$ with a root of the polynomial say $\sqrt[3]{2}.$ But note that this is {\em not} the splitting field. The polynomial has other roots, namely $\sqrt[3]{2}\omega,\sqrt[3]{2}\omega^2$ where $\omega$ is a primitive cube root of unity. And it is clear that $\Q(\sqrt[3]{2})$ is a subfield of the reals and obviously cannot contain the complex number $\sqrt[3]{2}\omega$ and hence cannot be the splitting field of the polynomial. The splitting field of this polynomial is $\Q(\sqrt[3]{2},\omega)$ and is a degree $6$ extension over $\Q$ whereas the extension by adjoining roots are degree $3$ extensions over $\Q.$\\ An important theorem is the following: \begin{theorem} If $E$ and $E'$ are two splitting fields of a polynomial $f(X)$ over $K$, then $E\iso E'.$ \end{theorem} We omit the proof, but nevertheless the theorem is important and will be used. Interested readers can refer any abstract algebra books for the proof of this fact. \subsection{The Frobenius Map} The binomial theorem takes a very simple form over $\F_p.$ We know that $$ (X+Y)^p = \sum_{i=0}^p \binom{p}{i} x^i y^{p-i} $$ \begin{lemma} For $i\neq 0,p$, the coefficient $\binom{p}{i}$ is divisible by $p.$ \end{lemma} \begin{proof} The proof is quite obvious. The coeffient is $$ \binom{p}{i} = \frac{p\cdot(p-1)\cdots (p-i+1)}{1\cdot 2\cdots i} $$ and the numerator has a factor of $p$ and the denominator does not. And since this si an integer, the factor of $p$ will remain uncancelled and hence will be divisible by $p.$ \end{proof} This then tells us that in the field $\F_p$, $$ (X+Y)^p = X^p + Y^p $$ If you look at it as a automorphism (an isomorphism of $\F_p$ into itself), this shows the map $x\mapsto x^p$ is an automorphism of $\F_p.$ This map $\phi(x) = x^p$ is called the Frobenius map. It is a very important automorphism of finite fields and appears almost everywhere. \subsection{The Multiplicative Group of a Finite Field is Cyclic} Let $K$ be a finite field of $p^m$ elements. We shall show now that the multiplicative group $K\setminus\inbrace{0}$ is a cyclic group. Infact, we shall show a much stronger theorem. \begin{theorem} Let $K$ be any field (not necessarily finite) and let $A$ be any finite subgroup of $K^\star = K \setminus\inbrace{0}.$ Then the subgroup $A$ is cyclic. (That is, there exists an element $a\in A$ such that every other element in $A$ is a power of $a$) \end{theorem} \begin{proof} Let $|A| = M.$ We need to show that there exists an element in $A$ of order $M.$ Suppose not, let $a$ be the element of highest order in $A.$ Let the order of $a$ be $m < M.$ Now pick any $x\in A$. We claim that the order of $x$ must divide $M.$ To prove this, let the order of $x$ be $n.$ Let the gcd of $m$ and $n$ be $d.$ By Euclid's lemma, there exists integers $p,q$ such that $pn + qm = d.$ Thus, let us look at the element $g = x^pa^q.$ Then $g^m = x^{pm}a^{qm} = a^{qm} = d$ since $qm = d \bmod{n}.$ And similarly $g^n = x^d.$ Thus, the order of $g$ is infact equal to $\frac{mn}{d} = lcm(m,n).$ And since we assumed that $a$ was an element of maximum order, the lcm of $m$ and $n$ has to be $m$ and therefore $n$ has to divide $m.$\\ Having established this, we see that the order of every element must divide $m$ and therefore $x^m = 1$ for every $x\in A.$ And therefore, the polynomial $X^m - 1$ has every element of $A$ as a root. But if we were to assume that $m<M$, then a polynomial of degree $m$ would have $M>m$ roots! And this clearly cannot happen in a field. And therefore, $m = M$ and hence the group $A$ is cyclic. \end{proof} \section{Uniqueness of $\F_{p^m}$} Now we come to the proof that every field of $p^m$ elements are isomorphic. So essentially, there is only $1$ field of size $p^m$ and hence would make sense to refer to {\em the} field of size $p^m$ as $\F_{p^m}.$To avoid cluttering of subscripts and superscripts, let $q = p^m.$ We need to show that any two fields of size $q$ are isomorphic. Now let $F$ be any field of order $q.$ Then every element $a\in F$ satisfies the property that $a^q = a.$ Hence in particular, every element of the field $F$ is a root of $X^q - X.$ And therefore, considering this polynomial over $\F_p$, $F$ is a splitting field of $X^q - X$ over $\F_p.$ And by a theorem stated earlier, all splitting fields of a polynomial are isomorphic. And therefore, any two fields of order $q$ are isomorphic. \section{More about $X^q - X$} Here is a very important property of this polynomial $X^q - X.$ \begin{theorem} Let $Irr(K,d)$ be the set of all irreducible polynomials of degree $d$ over $K.$ Then, the following equation holds in $\F_p[X]:$ $$ X^{p^m} - X = \prod_{\substack{f\in \text{Irr}(\F_p,d)\\d\mid m}} f(X) $$ \end{theorem} \begin{proof} We shall show that the LHS is equal to the RHS by comparing the roots on both sides. For the roots to first exist, we shall go to some large field. Firstly, note the polynomial $X^{q} - X$ is satisfied by every element of $\F_q.$ And by the same degree argument, the roots of the polynomial is precisely all the elements of $\F_q.$ We shall first show that every element $\alpha \in \F_q$ is also a root of the RHS. Since $\alpha \in \F_q$, pick up the minimum polynomial $f(X)$ of $\alpha$ over $\F_p.$ We have seen earlier that this polynomial must be irreducible. Hence $\F_p[X]/(f(X))$ corresponds to the field $\F_p(\alpha).$ Let the degree of $f$ be $d.$ We know that \bea{ \insquar{\F_q:\F_p} & = & \insquar{\F_{q}:\F_p(\alpha)}\insquar{\F_p(\alpha):\F_p}\\ \implies m & = & \insquar{\F_q:\F_p(\alpha)}\cdot d\\ \implies d\mid m & & } And hence, since the degree of this irreducible polynomial divides $m$, it appears in the product of the RHS as well. \\ The other way is easy too. Pick up any factor $f(X)$ on the RHS. Let its degree be $d.$ Let $\alpha$ be one of the roots. Then we know that $\F_p(\alpha)$ must be the field $\F_{p^d}.$ But since $d$ divides $m$, this is a subfield of $\F_q.$ And therefore every element of $\F_{p^d}$, in particular $\alpha$, must be in $\F_q$ as well. \end{proof} \subsection{Extracting Factors} The formula outlined in the previous section is extremely useful in factoring. It helps us pull out factors of the same degree. We shall see a quick sketch here and discuss this in detail next class. Let us say we have some polynomial $f$ over $\F_p.$ How do we extract all linear factors over $\F_p$? The idea is pretty simple. We know that $X^p - X$ splits as linear factors over $\F_p.$ And more over, the formal derivative of it is $pX^{p-1} - 1 = -1 \neq 0$ and therefore it has no repeated roots as well. Then, we have $$ g(X) = gcd(f,X^p - X) $$ Then if $\alpha \in \F_p$ was any root of $f$, then clearly since $\alpha$ also satisfies $X^p - X$, $\alpha$ will be a root of $g$ as well. And more importantly, since $X^p - X$ is has no repeated roots, $g$ will retain the same property as well. Hence every root of $f$ over $\F_p$ appears exactly once in $g.$ Having removed all degree $1$ factors, we can all extract degree $2$ factors by taking the gcd with $X^{p^2} - X.$\\ We shall discuss this idea of factoring in detail soon. \end{document}