Contents

  1. Main Definitions
  2. Preliminaries
    1. Characteristic
    2. Finite field: number of elements
    3. Frobenius automorphism
  3. Polynomial Pq(x) = xq - x.
    1. Primitive element
    2. Irreducible factorization over Fp
  4. Miscellaneous

1. Main Definitions

Group:
Set G with a binary associative operation *: GxG --> G ("multiplication"); a neutral element ("unit") e and an inverse i(x)=x-1 for each element x in G. The rules are:

The group is called abelian if the operation is commutative:

x*y = y*x

Subgroup is a subset containing e and closed under * and i.

Examples:



Ring:

A ring is (R,+,0,*,1) such that (R,+,0) is an abelian group and (R\{0},1,*) is a commutative "semigroup", i.e., a "group without inverse". An additional condition is distributivity:

x*(y+z) = x*y + x*z.

Subring is a subset containing 1 and 0 and closed under +,-,*.

Examples:

Exercise: Prove that Z/nZ is a ring.



Field:

A field (K,+,0,*,1) is a ring such that (K\{0},*,1) is a group (called multiplicative group of a field and denoted K*); i.e., every nonzero element has a multiplicative inverse. Subfield is a subset containig 0 and 1 and closed under +,-,*,/.

Examples:

Exercise: Prove that Z/pZ is indeed a field. Why Z/nZ for a non-prime n is not a field?



Isomorfism:
Bijection preserving all operations.



Automorfism:
Isomorfism onto itself.

Problem:

  1. Prove that the only automorphism of the field of rational numbers Q is the idenity map.
  2. (hard): Prove that the only automorphism of the field of real numbers R is the idenity map.



Order:

2. Preliminaries: general facts.

2.1. Characteristic of a field. Simple fields.

Definition:
A simple field is a field that has no proper subfields. (i.e. the only subfield is the field itself).



Problem: Prove that...
  1. ... any field has a simple subfield;
  2. ... the only simple fields are Q (rationals) and Fp = Z/pZ (for prime p).



Definition:
The characteristic of a field is 0 if its simple subfield is Q and p if its simple subfield is Fp. Denoted: char.



Problem:

3. Prove that if char K = p then for any x - element of K - the sum ( x + ... + x ) (p items) is 0.



Hints:
  1. Consider the intersection of all the subfields.
  2. Any (sub)field must contain 0 and 1; thus it has to contain 1+1; 1+1+1; 1+1+1+1 etc. This sequence is either infinite (then char=0) or finite, i.e. for some p: 1+1+...+1=0 (p 1's). Prove that p is prime.
  3. Use distributivity.



Solutions:
  1. Every field has a simple subfield: it is just the intersection of all its subfields. It cannot have proper subfields since it is the intersection of all of those.
  2. Consider a field K. It contains 0 and 1. Consider the sequence an, s.t. a0=0; a1=1; a2=1+1; and, in general, an+1=an+1. (Sloppily we could write it as an=n*1; remember, the integer number n is not an element of K). Either all elements in this sequence are different, and then the subring {an; -an} is isomorphic to Z (then K contains a subfiels isomorphic to Q and its characteristic is 0), or there exists a smallest k such that ap=0. Then {al | l=1..p} is isomorphic to Z/pZ. If p=nm is not a prime, we have an*am=0 and K is not a field. Therefore any field contains a subfield isomorphic to Q or Fp, i.e., up to isomorphism, there are the only prime fields.
  3. x + ... + x = x*1 + ... + x*1 = x*( 1 + ... + 1) = x*0 = 0. The sum of p units is 0 - by the definition of the characteristic: 1 lies in the simple subfield Fp.



Note:
Although it is clear that a finite field has nonzero characteristic, it is not true that an infinite field has to have characteristic 0. E.g., the algebraic closure of Fp is infinite, but its characteristic is finite and equal to p.



Problem:
Prove that any automorphism of a field is the identity map on its simple subfield.



Hint:
0 --> 0; 1 --> 1; ==> 1+1 --> 1+1 ...



2.2. Finite field: number of elements.

Problem:
Suppose you have a finite field Fq; #Fq=q. Let char Fq=p. Prove that q=pk for some integer k.



Hint:
Consider Fq as a vector space over its subfield Fp (i.e. Fp is the field of scalars). Let its dimension be k. (Why is the dimension finite?) What is known about the structure of a finite dimensional vector space? (Coordinates, basis...)



Solution:
As a vector space over Fp (its simple subfield), Fq (a finite q-element field) is finite-dimensional (since it's finite), and thus isomorphic as a vector space to (Fp)k, with k=dim Fq. Thus q = #Fq = pk.

2.3. Frobenius automorphism.

Consider a finite field Fq; char Fq=p; q=pk; and let F: Fq --> Fq be the following transformation: F(x)=xp.

Problem:
Prove that F is a "field automorphism", i.e., F(x-y)=F(x)-F(y); F(x/y)=F(x)/F(y).



Hint:
Newton's binomial is useful here. Prove that for p - prime, k=1,...,p-1; p divides C(p,k) (the binomial coefficient).



Solution:

The statement F(x/y)=F(x)/F(y) follows from the usual properties of powers. Next,
(x-y)p=xp + (-y)p + Sum1p-1 C(p,k)xk yp-k.

p divides C(p,k) for k=1..p-1 and prime p, since we know that C(p,k)=p!/k!(p-k)!, and p divides the numerator but does not divide the denominator. Thus the "Sum" term is 0 and F(x-y)=xp + (-y)p. If p=2 then A+A=0 and A=-A thus F(x-y)=x2 + y2 = x2 - y2. If p is odd then (-y)p = -yp.



Definition:
This automorphism is called "Frobenius automorphism".



Note:
These two conditions imply that F(x+y)=F(x)+F(y); F(xy)=F(x)F(y); F(-x)=-F(x); F(x-1)=F(x)-1; F(1)=1; F(0)=0. Prove it! You might think about which set of conditions other than the one from the problem above will gurantee that the map is an automorophism.



Problem:
Prove that F(x)=x iff (if and only if) x lies in the simple subfield Fp.



Hint:
Consider polynomial Xp-X and its roots.



Solution:
If X in Fp, xp=x (see below). Since Xp-X cannot have more than p roots in Fq (and all p elements of Fp are its roots), no element of Fq\Fp can be a root.

3. Polynomial Pq(x) = xq - x.

3.1. Primitive element.

Problem:
  1. Prove that for any element x of field Fq we have xq=x; i.e., Pq(x)=0.
  2. (hard) Prove that there exists an element t in the field such that tq-1=1 and for any l<q-1; tl != 1. This means that the multiplicative group Fq* of the field Fq is isomorphic to Z/(q-1)Z (is "cyclic": each nonzero element of the field is some power of the element t, which is called "generator").



Hints:
  1. Consider the multiplicative group of the field, i.e. Fq* = Fq \ {0} with the operation of multiplication. Take an arbitrary element and multiply it by itself several times. You cannot always get a different element, can you? This treats the first part, since the order of an element must divide the order of the group q-1.
  2. In the second part, stick to the nonzero elements and let o(x) to be the order of x, i.e., the smallest number l such that xl=1. Let o = max {o(x) | x in Fq}. Prove that for any x we have that o(x) divides o, i.e., xo=1. (This is true since o(xy)<=lcm(o(x),o(y)); lcm = Least Common Multiple). Then if o<q-1, one must have a polynomial P(x)=xo-1 with more than o roots (namely, q-1). Is it possible in a field? Why?

3.2. Irreducible factorization over Fp.

Consider the polynomial P(x)=Pq(x)/Pp(x) (why is it a polynomial?)

Problem:
Describe its irreducible factorization over Fp.



Answer:
P(x) is the product of all irreducible polynomials of degree k over Fp. (recall that q=pk).



Hint:
Take z in Fq\Fp. Let z0=z; and zl+1=F(zl) (the Frobenius automorphism), i.e., zl=zpl; thus zk=z=z1. Therefore the polynomial Pz(x)= (x-z0)(x-z1)...(x-zk-1) is invariant under the Frobenius automorphism, thus its coefficients lie in Fp. These polynomials are irreducible over Fp. (Why? Apply the Frobenius automorphism to its alleged irreducible factor. It cannot change because of its coefficients - they lie in Fp and thus are invariant under the Frobenius automorphism - and it has to change because of its roots - they are not the whole set {z, F(z)=zp, F(F(z))=zp2, ..., F(F(...(F(z))...)) = zpk-1} and thus must change under the Frobenius automorphism). Any other irreducible polynomial of degree k has to be one of these. (It cannot have roots in Fp - then it's reducible - so it has roots in the algebraic closure of Fp, but with a root z it has to have F(z), F(F(z)), F(F(F(z))) etc. as roots, and it cannot have more than k roots, so zpk=zq=z - and thus z lies in Fq.)

4. Miscellaneous.

Problem:
Prove that for any function f: Fq --> Fq there exist the unique polynomial Pf of degree no more than q-1 such that for any x in Fq we have Pf(x)=f(x). How many such functions are there?



Define Aut(Fq):
to be the group of all possible automorphisms of Fq. The operation is the composition, the unit is the identity map, the inverse is the inverse map.



Problem:
Describe the group Aut(Fq).



Answer:
Aut(Fq) is isomorphic to Z/kZ, where q=pk; and the generator of Aut(Fq) is the Frobenius automorphism F.



Hint:
Prove that the order of F as an element of Aut(Fq) is k. Then prove that there are only k elements in this group.



Solution:

Suppose the order of F is l<k. Then Fl = id and for each element x of the field Fq we have xpl = x, i.e., any element of the field Fq is a root of the polynomial xpl-x of degree pl<pk=q which is impossible. Therefore for i=1,...,k-1 we have Fi != id and F0=Fk=id (since Fk(x)=xq=x). This also implies that the set {Fl | l=0,1,...,k-1} is a subgroup of Aut(Fq) isomorphic to Z/kZ.

Next, consider the generator t of the field Fq. Recall that for each nonzero element x of the field Fq there is a unique number 0<=l<=q-1 such that x=tl. Suppose we have an automorphism w of the field Fq and its value on the generator t is w(t)=ta for some 0<=a<=q-1. Then w(x) = w(tl) = w(t)l = {ta}l = tal = {tl}a = xa. Thus the automorphism w is determined by the image of the generator and furthemore, it can be represented in the form x --> xa. Now the only thing left to be proven is that a must be a power of p.

Here we again use the Newton's binomial. Since w is an automorphism, we have the following identity for all x from the field Fq: w(x+1) = w(x) + w(1) = w(x) + 1. Therefore we have (x + 1)a = xa + 1 or that the polynomial (x + 1)a - xa - 1 is identical to 0. Since its degree is less than q, the coefficients must be 0, and the coefficients are the binomial coefficients C(a,l) for l=1,...,a-1. They are 0 in the field Fq if and only if p divides each of them. Suppose that a=pm+b<pm+1. Careful consideration of C(a,b) shows that it is not divisible by p unless b=0. The reader is encouraged to actually perform the "careful consideration".



Sam Steingold
<sds@gnu.org>
 Valid XHTML Use CSS Valid CSS created: 1995-01-01