26
$\begingroup$

What are the fields with 4 elements?

$\endgroup$
6
  • 4
    $\begingroup$ There is a unique field of 4 elements, which is a field extension of $\mathbb{F}_2$. Do you know how to construct field extensions? $\endgroup$
    – Zhen Lin
    Commented May 30, 2011 at 15:51
  • $\begingroup$ Sorry, I have yet to cover field extensions $\endgroup$
    – Freeman
    Commented May 30, 2011 at 15:59
  • 3
    $\begingroup$ perhaps you should tell us what you have covered. $\endgroup$
    – lhf
    Commented May 30, 2011 at 16:13
  • $\begingroup$ @lhf I have done a first course in groups, a list of what I have covered is here under 'Synopsis' maths.ox.ac.uk/courses/course/12493/synopsis $\endgroup$
    – Freeman
    Commented May 30, 2011 at 16:20
  • 1
    $\begingroup$ That course covers quotient rings, which means my answer should be accessible (perhaps with a bit more detail). Do you in fact know about quotient rings? $\endgroup$ Commented May 30, 2011 at 21:38

4 Answers 4

41
$\begingroup$

Here is a nice general method to build examples of finite fields of any desired size (a power of a prime):

Given a prime $p$ (in your case, $p=2$), pick a monic polynomial $q(x)\in {\mathbb F}_p[x]$ of degree $n$ and irreducible (in this case, $n=2$ and $q(x)=x^2+x+1$. By a counting argument, one can show that there is always at least one such polynomial $q$).

We use $q$ to build a field of size $p^n$.

Let $A$ be the companion matrix of $q$. This means that if $q(x)=a_0+a_1x+\dots+a_{n-1}x^{n-1}+x^n$, then $$A=\left(\begin{array}{ccccc}0&0&\dots&0&-a_0\\ 1&0&\dots&0&-a_1\\ 0&1&\dots&0&-a_2\\ \vdots&\vdots&\vdots&\vdots&\vdots\\ 0&0&\dots&1&-a_{n-1}\end{array}\right).$$ In our case, $$A=\left(\begin{array}{cc}0&1\\ 1&1\end{array}\right).$$

Now let $F=\{ r(A)\mid r \in{\mathbb F}_p[x]\}$.

The point is that $q(A)=a_0I+a_1A+\dots+a_{n-1}A^{n-1}+A^n=0$ and in fact, if $t(x)\in{\mathbb F}_p[x]$ and $t(A)=0$, then $q$ is a factor of $t$. Using this, one easily checks that $F$ is closed under addition and multiplication and has size $p^n$. Also, $t(A)s(A)=s(A)t(A)$ for all polynomials $t,s$. Finally, if $t$ is not a multiple of $p$ (i.e., $t(A)\in F$ is non-zero), then $\{t(A)r(A)\mid r(A)\in F\}=F$, so there is an $r(A)\in F$ such that $t(A)r(A)=1$, i.e., all elements of $F$ have inverses in $F$. So $F$ is a field.

To see that the key point is true requires a little argument. Call ${\mathbf e}_1,\dots,{\mathbf e_n}$ the standard basis in the vector space ${\mathbb F}_p^n$. Then $A{\mathbf e}_i={\mathbf e}_{i+1}$ for $i<n$ and from this it follows easily that for no non-zero polynomial $t$ of degree less than $n$ we can have $t(A)=0$, and also that $q(A)=0$.

[In more detail: We have $A{\mathbf e}_1={\mathbf e}_2$, $A^2{\mathbf e_1}=A{\mathbf e}_2={\mathbf e}_3$, etc, so for any polynomial $t(x)=b_0+\dots+b_{n-1}x^{n-1}$ of degree at most $n-1$ we have $t(A){\mathbf e}_1=b_0{\mathbf e}_1+b_1{\mathbf e}_2+\dots+b_{n-1}{\mathbf e}_n$, which is non-zero unless $b_0=\dots=b_{n-1}=0$ to begin with. Also, $q(A){\mathbf e}_1=0$ since $A^n{\mathbf e}_1=A{\mathbf e}_n=-a_0{\mathbf e}_1-a_1{\mathbf e}_2-\dots-a_{n-1}{\mathbf e}_n$. Since each ${\mathbf e}_i$ is $A^k{\mathbf e}_1$ for some $k$, it follows that $q(A){\mathbf e}_i=0$ for all $i$ (since $q(A)A^k=A^kq(A)$). Since the ${\mathbf e}_i$ form a basis, $q(A){\mathbf v}=0$ for all ${\mathbf v}$, so $q(A)=0$.

Also, since $q(A)=0$, note that $A^n$ is equal to a polynomial of degree at most $n-1$ applied to $A$ (namely, $-a_0I-\dots-a_{n-1}A^{n-1}$). It follows that any polynomial of degree $n$ applied to $A$ equals a polynomial in $A$ of degree at most $n-1$. But then $A^{n+1}=A^nA$ equals a polynomial in $A$ of degree at most $n$, and therefore one of degree at most $n-1$, and the same holds for any polynomial of degree $n+1$. Then $A^{n+2}=A^{n+1}A$ equals a polynomial in $A$ of degree at most $n$, etc.]

In our case, the field of 4 elements we obtained is $$\left\{0=\left(\begin{array}{cc}0&0\\ 0&0\end{array}\right),I=\left(\begin{array}{cc}1&0\\ 0&1\end{array}\right),A=\left(\begin{array}{cc}0&1\\ 1&1\end{array}\right),A+I=A^2=\left(\begin{array}{cc}1&1\\ 1&0\end{array}\right)\right\}.$$

The nice thing about this example is that the product and addition are just familiar operations (product and addition of matrices). Of course, from the general theory of finite fields, any two examples of the same size are isomorphic. However, I think this is a very concrete example that is useful to keep in mind as one advances through the theory, to see how general results apply in this setting.

$\endgroup$
31
$\begingroup$

Let $K$ be your field.

The additive group of $K$ is an abelian group with four elements. The order of $1$ in this group divides $4$, so it is either $2$ or $4$. Were it $4$, we would have $1+1\neq0$ and $(1+1)\cdot(1+1)=0$, which is absurd in a field. It follows that $1+1=0$ in $K$. But then for all $x\in K$ we have $x+x=x\cdot(1+1)=0$, and we see that all elements have order $2$. In particular, $-1=1$.

Let $a$ be an element in $K$ which is neither $0$ nor $1$. Then $a+1$ is neither $a$ nor $1$ and if we had $a+1=0$, then $a=-1=1$ which again is a not true. We conclude that the four elements of $K$ are $0$, $1$, $a$ and $a+1$.

You should check that this knowledge complete determines the addition in $K$.

We have to determine the multiplication now. Since $0$ and $1$ are what they are, we need only see what $a\cdot a$, $a\cdot(a+1)$ and $(a+1)\cdot(a+1)$ are:

  • We can't have $a^2=a$, for then $a(a-1)=0$ and we are supposing that $a\not\in\{0,1\}$; similarly, $a^2\neq0$. If $a^2=1$, then $(a-1)^2=a^2-1=0$ , which is also impossible. We must have thus $a^2=1+a$.

  • Next, using this, $a\cdot(a+1)=a^2+a=1+a+a=1$.

  • Finally, using that $1+1=0$, $(a+1)\cdot(a+1)=a^2+1=a$.

Multiplication is completely determined.

Now we have to check that with this operations we do have a field... You should have no trouble with that :)

$\endgroup$
2
  • $\begingroup$ @MarianoSuárez-Alvarez Please tell me you didn't know that at the top of your head. That clarifies so much. Although I am really confused by the line The additive group of K is an abelian group with four elements. The order of 1 in this group divides 4, so it is either 2 or 4 $\endgroup$ Commented Jul 7, 2012 at 23:52
  • $\begingroup$ @ladiesMan217: Let me answer your question 11 years late, for the benefit of future readers. Lagrange's theorem tells us that for a group $G$ and element $g\in G$, the order of $g$ divides $|G|$. Therefore, in our case, the order of $1$ must be $1$, $2$, or $4$. But the only element of order $1$ in a group is the identity element of group, here by denoted by $0$. Thus, if the order of $1$ is $1$, then $1=0$. This contradicts the field axioms, one of which explicitly states that $1\neq 0$. Thus, the only possibilities are that the order of $1$ is $2$ or $4$. $\endgroup$
    – Joe
    Commented Jun 14, 2023 at 12:23
20
$\begingroup$

Hint: Two of the elements have to be $0$ and $1$, and call the others $a$ and $b$. We know the mulitplicative group is cyclic of order $3$ (there is only one group to choose from), so $a*a=b, b*b=a, a*b=1$. Now you just have to fill in the addition table: how many choices are there for $1+a$? Then see what satisfies distributivity and you are there.

Added: it is probably easier to think about the choices for $1+1$

$\endgroup$
5
$\begingroup$

HINT $\ $ Such a field would be a quadratic extension of its prime field $\rm\:\mathbb F_2\:.\:$ So it suffices to consider $\rm\:\mathbb F_2[x]/(f(x))\:$ where $\rm\:f(x)\:$ is an irreducible quadratic polynomial over $\rm\:\mathbb F_2\:.\:$ Testing irreducibility is trivial via the Parity Root Test.

$\endgroup$
4
  • $\begingroup$ Dubque sorry that covered in my course, but thank you for your time $\endgroup$
    – Freeman
    Commented May 30, 2011 at 16:06
  • $\begingroup$ @LHS Such an exercise can occur before or after you study quotient rings and or beginning field theory, i.e. before the study of finite fields. You may wish to revisit this answer after you've studied such. It's always a good idea to say something about your background when you post questions. This will help you to receive answers at the appropriate level. $\endgroup$ Commented May 30, 2011 at 16:16
  • 5
    $\begingroup$ Checking whether a given polynomial has a root in $\mathbb F_2$ is done by plugging in the two candidates. You don't need a fancy name like Parity Root Test. So this is an imitation of the construction of the complex numbers from the reals. The only hard part is choosing a quadratic with no solution (since the conventional choice $x^2+1$ has solutions). $\endgroup$
    – GEdgar
    Commented May 30, 2011 at 20:25
  • $\begingroup$ @GEdgar The point of naming the Parity Root Test is that it works in any ring that admits parity - of which their are many, e.g. the Gaussian integers - see the linked post. Here it is trivial, but in other rings it may be quite nontrivial. This is but a simple manifestation of ideas that play fundamental roles in number theory. As such it deserves pedagogical emphasis. $\endgroup$ Commented May 30, 2011 at 23:33

Not the answer you're looking for? Browse other questions tagged .