lect03 rings and things

6.S897 Algebra and Computation February 15, 2012 Lecture 3 Lecturer: Madhu Sudan Scribe: Henry Yuen Of central importance to Algebra and Computation are structures such as groups, rings, and especially nite elds. Here, we review basic denitions and cover the construction of nite elds. It should be noted that these notes should not be used to learn about groups, etc. for the rst time. 1 Basic denitions: Groups, rings, elds, vector spaces Denition 1 (Monoid) For a setGand an operator
:GG!G, a pair (G;
)is a monoid i the following properties are satised: 1. (Identity) There exists e2Gsuch that for all a2G,a
e=a. 2. (Associativity) For all a;b;c2G,a
(b
c) = (a
b)
c. Denition 2 (Group) A monoid (G;
)is a group i for all a2G, there exists an element b2G such thata
b=e. We say a group (G;
)is commutative or Abelian i for all a;b2G,a
b=b
a. Denition 3 (Ring) For a setRand binary operators
and+overR, the triple (R;+;
)is a ring i the following properties are satised: 1. (Commutative addition) (R;+)is an Abelian group with identity element 0. 2. (Multiplication) (R;
)is a monoid with identity element 1. 3. (Distributivity) For all a;b;c2R,a
(b+c) =a
b+a
c. We say that a ring (R;+;
)is a commutative ring i for all a;b2R,a
b=b
a. A ring is an integral domain if it has no zero divisors. Denition 4 (Field) A tuple (F;+;
)is a eld i the following properties are satised: 1.(F;+;
)is an integral domain. 2.(Ff0g;
)is an Abelian group. Denition 5 (Vector space) A setV(whose elements are called vectors ), along with a vector addition operation + :VV!Vand a scalar multiplication operation
:FV!V, is a vector space over the eld Fi the following properties are satised: 1. (Closure under addition) (V;+)is an Abelian group. 2. (Scalar distributivity with respect to vector addition) For all 2F,u;v2V,
(u+v) = 
u+
v. 3. (Scalar distributivity with respect to eld addition) For all ;2F,u2V,(+)u=u+u. 4. (Field, vector space associativity): For all ;2F,u2V,(u) = ()u. 5. (Identity eld element): For all u2V,1
u=u, where 1is the multiplicative unit of F. Proposition 6 All nite vector spaces Vover a eld Fis isomorphic to Fnfor somen. 3-1 2 Finite Fields Much of the course will be concerned with computation over nite elds. Here, we'll cover the basics of nite elds: existence, uniqueness, and construction. 2.1 Notation All the elds discussed below will be nite. pandqwill almost always denote a prime and a prime power (ptfor some prime pand positive integer t), respectively. Symbols in the blackboard font will denote elds, e.g. F. A subscript to a eld symbol indicates the order of the eld, e.g. Fpis a nite eld of prime order. 2.2 Prime elds Denition 7 A eld Fis prime ifjFj=pfor some prime p. Theorem 8 For every prime p, a nite eld of size pexists, and moreover, it is unique up to isomorphism. Proof Consider the quotient ring Z=pZ. It is a eld, and a eld of size p. Let K;Lbe two elds of order p. For isomorphism, map 0 Kto 0 L, 1Kto 1 L; since KandL(the multiplicative groups of KandLrespectively) are cyclic groups, this mapping extends naturally and uniquely to an isomorphism between KandL. Denition 9 The characteristic of a nite eld char (F)is the smallest integer nsuch that the multiplicative identity 1added to itself ntimes is equal to the additive identity 0. 2.3 Constructing Fields from Fields Constructing non-prime elds is more interesting; we will actually construct them starting with prime elds. But before we get into that, let's look at how we can construct larger elds from smaller ones. Denition 10 (Field of fractions) LetRbe an integral domain. The eld of fractions F(R) = RR=whereis an equivalence relation such that a;b;c;d2R,(a;b)(c;d)if and only if ad=bc. Proposition 11 The eld of fractions F(R)for an integral domain Ris a eld. Here are two primary ways of constructing elds from elds. Let Fbe a eld, and let F[X] be the ring of polynomials with coecients in F. 1.F(F[X]), the eld of fractions, is called the eld of rational functions overF. 2. Letg2F[X] be an irreducible polynomial. Then F[X]=(g) is a eld. 2.4 Constructing Non-prime Fields Lemma 12 LetFbe a nite eld. Then it has prime characteristic. 3-2 Proof Suppose Fhad characteristic r=ab > 1, wherea;b6= 1. That means the sum 0 F= rz}|{ 1F+


+ 1Fcan be divided up into agroups of=bz}|{ 1F+


+ 1F. By assumption, 6= 0F. Then, 0F=1
0F=1(az}|{ +


+) =az}|{ 1F+


+ 1F, contradicting the minimality of r. Fact 13 Leta;b2Fwhere Fhas characteristic p. Then (a+b)pr=apr+bprfor any positive integerr. Lemma 14 LetFbe a nite eld, with characteristic p. Then Fis anFp-vector space. Proof This follows from the uniqueness of prime elds; we can think of Fqas being Z=pZ. Vector addition is the same as addition in F, and scalar-vector multiplication is repeated addition in the obvious manner. Corollary 15 LetFbe a nite eld. Then jFj=ptfor some prime pand some positive integer t. Proof This follows from the earlier fact that all nite vector spaces over Fare isomorphic to Fn for somen. Lemma 16 (Division Lemma) Letf;gpolynomials in F[X]for some nite eld F. Then there exists a unique pair (q;r)2F[X]such that deg(r)<deg(g)andf=q
g+r. Proof Existence of a pair ( q;r) follows from the standard polynomial division algorithm. We now argue uniqueness: suppose there were two such pairs ( q;r)6= (~q;~r). Then (q~q)
g+ (r~r) = 0, but this is impossible, because if q6= ~q, then (q~q)
gis a nonzero polynomial of degree greater thanr~r, and ifq= ~qbutr6= ~r, thenr~ris also a nonzero polynomial, a contradiction. Corollary 17 Letf2F[X]. For alla2F,f(x)f(a) mod (xa). Corollary 18 Letf2F[X]have degree r. Thenfhas at most rroots in F. Proof This follows from the Division Lemma and the previous corollary: repeated division of f by (xr) for a root r2Fwill eventually whittle fto either a constant or an irreducible polynomial. Lemma 19 (Multiplicative group of nite elds are cyclic) LetFbe a nite eld. Then F, the multiplicative group of F, is cyclic. Proof LetFhave order prfor some prime pand positive integer r. The multiplicative group F has orderpr1. Let ^pbe some prime that divides pr1, and letU^pbe the subgroup of elements ofFwhose orders are a power of ^ p. Clearly, by Lagrange's theorem, U^phas orderqsfor somes. SupposeU^pwere not cyclic. Then all elements of U^pmust be roots of the polynomial xqs11 (by Lagrange's theorem), which contradicts the corollary above. Thus all subgroups of Fof prime power order are cyclic. By the Fundamental Theorem of Abelian groups, we can write Fas the direct sum Zq1


 Zqk, where each qiare prime powers. The foregoing argument shows that any pairqiandqj(i6=j) must be coprime, and it is easy to see that the entire direct sum must be cyclic. 3-3 Corollary 20 LetFbe a eld of order q. Thenxqx=Q 2F(x). Proofxqxhas at most qroots in F. It now suces to show that for all 2F,xdivides xqx, or equivalently that is a root. If = 0, then it is clear. Otherwise, note that non-zero  is contained in F, which has order q1. By Lagrange's theorem q=, and we are done. We now are ready to construct our eld of order q=pr. To do so, we will construct a polynomial inFp[X] whose roots all lie in an extension eld ofFp, and the extension eld will have order q. Denition 21 (Extension eld) LetK;Lbe nite elds. Lis an extension eld of KiKL andLis anK-vector space. We denote the eld extension as L=K. Frequently, however, we will also say that L=Kis a eld extension even if Kisn't technically a subset of L, but rather, naturally embeds into L. For example, an important method of constructing extension elds for us will be to take a eld F, and consider the quotient eld L=F[X]=(f) for some polynomial f2F[X]. Since Fnaturally embeds into F[X] which naturally embeds into F[X]=(f), we also say that L=Fis a eld extension. Lemma 22 LetFbe a eld of order q. Letf2F[X]be an irreducible, monic polynomial of degree r. Then the quotient ring F[X]=(f)is a eld and has order qr. Proof We provide a proof sketch. F[X]=(f) must be a eld: there are both additive and multi- plicative inverses, and since fis irreducible, the underlying ring of F[X]=(f) is an integral domain. Furthermore, it is a vector space over F. Observe that 1 ;X;X2;:::;Xr1forms a basis for F[X]=(f), soF[X]=(f) must have dimension rand thus cardinality qr. Lemma 23 (Splitting Field Lemma) For allg2F[X], there exists a eld extension LofFsuch thatgsplits completely into linear factors in L[X]. Proof Suppose Fwere of order q. There are two cases: g2F[X] is irreducible, or not irreducible. Support it were irreducible. Consider the quotient eld L=F[X]=(g); it is of size qrwherer= deg(g). Then by the above corollary, gsplits completely into linear factors in L[X]. Ifgwere not irreducible, then we can write g=ab, whereais an irreducible polynomial and bis a nontrivial polynomial. Since asplits completely over F[X]=(a), we can then recurse on splitting bover an extension eld of F[X]=(a), until we nally obtain a nal extension eld where gcompletely splits. Denition 24 LetFLbe elds, and ga polynomial in F[X]. Then Lis called the splitting eld ofgoverFif and only if gfactors completely into linear polynomials in L[X]. We will use the Splitting Field Lemma to construct our eld of order qrfor anyr. Proposition 25 LetLbe a splitting eld of xqrxoverFq. ThenS=f2Ljqr=gforms a eld of order qr. Proof SinceLis the splitting eld of g(x) =xqrxoverFq, we know that all of g's completely factors into linear polynomials over L[X]. We now show that all the roots of ghave multiplicity 1, establishing that there are qrdistinct roots of ginL, and thusShas cardinality qr.Sis clearly a eld. Suppose 6= 02Lis a root of g, and that for contradiction ( x)2dividedg. Since 0 cannot be a double root of g(by inspection x2does not divide xqrx), (x)2must divide g0(x) =xqr11. However,g0(x)r(x) mod (x), wherer(x) =Pqr2 i=0q1ixi, butr() = (qr1)qr2, which is not 0. 3-4 Lemma 26 (Unique containment) LetF;Gbe subelds of K. IfjFj=jGj, then F=G. Proof LetKhave order prfor some prime p. All subelds of Kmust have order pkforkr. SupposejFj=jGj=pk. Consider the polynomial f(x) =xpkx2K[X]. All elements of FandG must be roots of f, but since fcan have at most pkroots in K,F=G. Lemma 27 (Uniqueness of nite elds) LetFprbe a nite eld of order pras constructed above. It is unique up to isomorphism. Proof LetK;Lbe nite elds of order pr. Then both are splitting elds of the polynomial xqx, where we let q=pr. The nite eld Fpembeds uniquely into both KandL. Letbe the isomorphism between the copy of FpinKand the copy in L. Treating KandLas vector spaces overFpwhere each element of the vector space is an ordered tuple of Fp, it is clear that extends to an isomorphism ~between KandL. We've shown a way to construct the unique eld of order qfor any prime power q. We now show a more direct method of creating Fq. 2.5 Constructing nite elds via minimal polynomials Denition 28 (Minimal polynomial) LetKbe a nite eld extension of F. Let2K. Then the minimal polynomial of overFis a monic, irreducible polynomial gof minimal degree in F[X] such thatg() = 0 . Denition 29 (Adjoining eld elements) LetL=Kbe a nite eld extension. For all 2L, K()denotes the minimal subeld of Lthat contains . We say that K()is the eld formed by adjoining toK. Fact 30 LetL=Kbe a nite eld extension, and 2L. Then every element a2K()can be expressed as the sum a0
1 +a1
+


+ak
kfor somek, whereai2K. Lemma 31 LetL=Kbe a nite eld extension. Let gbe the minimal polynomial for some 2L overK. Then K()=K[X]=(g). Proof Writeg=g0+g1X+g2X2+


+gdXd. Then K[X]=(g) is a degree deld extension ofK, thusjK[X]=(g)j=qdforq=jKj. We argue that jK(a)j=qdas well, and by the uniqueness of nite elds, this shows our lemma. K() is an extension eld over K, and hence is a K-vector space.f1;;2;:::;d1gis a basis for K(): observe that every element of K() can be written asa0
1 +a1
+


+ak
kfor somek, whereai2K. For anykd, the setf1;; 2;:::;kg is linearly dependent - the polynomial ggives the linear dependency. The set f1;; 2;:::;d1g is linearly independent, for otherwise gwould not be a minimal polynomial for . Thus K() is a K-vector space of dimension d, and the conclusion follows. Lemma 32 Letgis an irreducible polynomial of degree sinFq[X]. Thengdividesxqtx2Fq[X] if and only if sdividest. Lemma 33 Letqbe a prime power and rbe some positive integer. Then: xqrx=Y girreducible, monic 2Fq[X] deg(g)jrg(x) Corollary 34 For all prime power q, positive integer r, there exist an irreducible, monic polynomial g2Fq[X]of degreer. 3-5 3 Functions over nite elds There is a nice way of looking at functions over nite elds as polynomials. Consider some function f:Fq!Fq.fcan be, without loss of generality, be represented as some univariate polynomial of degree at most q1 (this follows from polynomial interpolation). Let us look at a particular class of functions fthat map FqrtoFq. We can still write f(x) =Pqr1 i=0cixi. Since we know the range offis contained in Fq, we have that X cixiq =X cixi: Sinceis a root of fqffor all2Fqr, it follows that xqrxdividesfqf, or equivalently fq=fmod (xqrx). We then note that f(x)q=X cixiq =X cq ixiq: We then can reduce xiqmoduloxQx, whereQ=qr. This is easy to do because the roots of xQxare precisely FQ, and thusxiq=xiqmod (Q1)modulo (xQx). Observe that the map i7!iq mod (Q1) is an invertible map for iQ1, and thus is a permutation. Setting coecients of the equationfq=fmod (xQx) equal, we get that fmapsFqrtoFqif and only if ciqmod (Q1)=cq i. We can look for the \simplest" such function by demanding that as many ci's be zero as possible, without being trivial. This can be accomplished by setting c1= 1, but that forces (by the equivalent condition above) cqk= 1 forkr1. This leads us to a particularly important function that maps FqrtoFq, called the trace : Denition 35 (Trace) The trace Tr :Fqr!Fqis dened as Tr (x) =x+xq+


+xqr1. Lemma 36 (Linearity of Trace) Tr is linear. Lemma 37 Tr is aqr1-to-1map. Proof Let2Fq. Then Tr( x)is a polynomial that maps FqrtoFqwith degree qr1, and thus it has at most qr1zeros. But that means every 2Fqhas a preimage under Tr of size qr1: otherwise there would be elements of Fqrthat would not map to anything under Tr, which is absurd. Perhaps a more interesting reason for why the trace function is important is because of its \universality" with respect to functions that map FqrtoFq, the following sense: Theorem 38 Letfbe a function that maps FqrtoFq. Then there exists a polynomial g2Fqr[X] such thatf=Tr(g). Proof For each2Fq, denet2Fqrto be such that Tr( t) =(there areqr1choices to pick from; choose arbitrarily). Then, interpolate a polynomial gof degreeqr1 such that for each 2Fqr,g() =tf(). It is clear that f= Tr(g). 3-6