305 -Fields (3)

At the end of last lecture we arrived at the question of whether every finite field is a {mathbb Z}_p for some prime p.

In this lecture we show that this is not the case, by exhibiting a field of 4 elements. We also find some general properties of finite fields. Finite fields have many interesting applications (in cryptography, for example), but we will not deal much with them as our focus through the course is on number fields, that we will begin discussing next lecture.

We begin by proving the following result:

Lemma 13. Suppose that {mathbb F} is a finite field. Then there is some natural number n>0 such that the sum of n ones vanishes, 1+dots+1=0. The least such n is a prime that divides the size of the field

Proof. Suppose |{mathbb F}|=m. Consider the following elements of {mathbb F}: 0,1,1+1,dots,underbrace{1+dots+1}_{m}. There are m+1 elements in this list and only m elements in {mathbb F}, so necessarily two of these expressions must coincide, i.e., for some two distinct numbers k,t, with 0le k<tle m, we must have underbrace{1+dots+1}_k =underbrace{1+dots+1}_t, so underbrace{1+dots+1}_{t-k}=0, where the last equation is obtained by adding the additive inverse -(underbrace{1+dots+1}_k) to both sides of the previous equation. 

Let A={hin{mathbb Z}^+ : underbrace{1+dots+1}_h=0}. All we did in the paragraph above was to show that Aneemptyset. By the well-ordering principle, A has a least element n. Now we argue that n is a prime: First of all, n>1 since one of the field axioms tells us that 1ne0. Suppose towards a contradiction that n is not a prime, so we can write n=n_1n_2 where 1<n_1<n and 1<n_2<n. Then underbrace{1+dots+1}_n = (underbrace{1+dots+1}_{n_1})(underbrace{1+dots+1}_{n_2}), as can be easily checked from the field axioms. We now have a product ab=0 in a field {mathbb F}. As shown last lecture, immediately after Lemma 12, it must be the case that either a=0 or b=0, i.e., either n_1in A or n_2in A. But this contradicts the minimality of n, and we are forced to conclude that n is a prime.

We are left to argue that n|m (recall that |{mathbb F}|=m). This is a particular case of an argument we will encounter again later on, Lagrange’s theorem. Let C={0,1,dots,underbrace{1+dots+1}_{n-1}}. Then:

  • |C|=n, since otherwise we must have two elements of C that are equal, which (reasoning as in the first paragraph of the proof) gives us a number strictly smaller than n in A.
  • C is closed under addition and under additive inverses, i.e., if a,bin C then also a+bin C and -ain C. This is because, essentially, C with addition behaves like {mathbb Z}_n with addition mod n.

For ain{mathbb F} write a+C for the set {a+b : bin C}. Then:

  • For any ain{mathbb F}, |a+C|=n.
  • For any a,bin{mathbb F}, either a+C=b+C or else (a+C)cap(b+C)=emptyset.

Both these properties are easily checked using the two properties of C we pointed out right before.

It follows that we have partitioned {mathbb F} into disjoint sets, all of them of the same size n. It must therefore be the case that n|m=|{mathbb F}|, as we wanted to show. {sf QED}

Definition 14. If {mathbb F} is a finite field, the prime number n from Lemma 13 is called the characteristic of {mathbb F}, {rm char}({mathbb F}).

 Let us now return to Example 7. Can we have a field of 4 elements? Say {mathbb F}={0,1,a,b}. Then {rm char}({mathbb F})=2, because {rm char}({mathbb F}) is a prime that divides 4. This means that 1+1=0, which implies that a+a=0=b+b as well, since for example a+a=acdot1+acdot1=a(1+1)=acdot0=0. Clearly, a+1 cannot be any of 0,1,a, since 1=-1 and a,1ne0. Thus a+1=b. Similar reasoning shows us that there is only one way to complete the addition table of {mathbb F}: 

  • 0+x=x+0=x and x+x=0 for any x. 
  • 1+a=a+1=b and 1+b=b+1=a.
  • a+b=b+a=1.

It is easy to check that + is commutative and associative, that there is an additive identity and every element has an additive inverse.

Now we need to see if there is a way of constructing the multiplication table of {mathbb F}. Notice that acdot ane0,1,a: It cannot be 0 since {mathbb F} cannot have zero divisors. It cannot be 1, since a^2=1 implies (a-1)(a+1)=0 which in turn implies that a=1 or a=-1=1. It cannot be a, since a^2=a implies that a(a-1)=0 so a=0 or a=1. Thus acdot a=b.  Similar reasoning shows us that there is only one way to complete the multiplication table of {mathbb F}:   

  • xcdot0=0cdot x=0 for all x. 
  • xcdot 1=1cdot x=x for all x.
  • acdot a=b, acdot b=bcdot a=1.
  • bcdot b=a.

It is easy to check that times is commutative and associative, that there is a multiplicative identity and that every nonzero element has a multiplicative inverse. It is also easy to check that times distributes over +. It follows that ({mathbb F},+times,0,1) is indeed a field.

This is an interesting object: It is a field of 4 elements, so it is not a {mathbb Z}_n. Notice that (up to renaming of its elements) there is only one such field, we did not have any freedom in the construction of the tables for addition or multiplication. Notice also that (x+a)(x+b)=x^2+(a+b)x+ab=x^2+x+1 for any x, so x^4-x=x(x-1)(x-a)(x-b). This is an interesting phenomenon that always holds in finite fields. 

I list without proof the following general results:

  • If {mathbb F} is a finite field, then |{mathbb F}|=p^n for p={rm char}({mathbb F}) and some n>0.
  • For any prime p and any positive integer n there is a field of size p^n, this field is unique up to renaming of the elements. (The technical term for “renaming” is isomorphism, a notion we will soon study in detail.)
  • In the field {mathbb F} of size p^n, the equation x^{p^n}-x=0 is true for all x.

Next time we will see several examples of infinite fields.

Advertisements

2 Responses to 305 -Fields (3)

  1. […] 1. Show directly that there is no field of elements. (“Directly” means, among other things, that we cannot use the facts mentioned without proof at the end of lecture 4.3.) […]

  2. […] This polynomial has no roots in since Recall that in lecture 4.3 we constructed a field of 4 elements. Using the same notation we used there, where (this easily […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: