# 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:
• `x*(y*z)=(x*y)*z`;
• `i(x)*x = x*i(x) = e`;
• `x*e = e*x = x`.

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:

• `(Z, +, 0)`;
• `(Q\{0}, *, 1)`;
• `Sn` - the group of permutations of `n` elements; operation: composition; unit: identity map.

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:

• `(Z,+,*)`;
• Polynomials with real coefficients - `R[x]`;
• Residues modulo `n` - `Z/nZ`: `{0,1,...,n-1}` with operations ```x+y := x+y mod n```; `x*y := x*y mod n` etc.

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:

• `(Q,+,0,*,1)`;
• `(R,+,0,*,1)`;
• Rational functions with real coefficients - `R(x)`;
• Residues modulo prime number `p`: ```Z/pZ = Fp```.

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:
• - of a set = cardinality = number of elements = `#`.
• - of an element `x` of a group `G`: the smallest integer number `n` such that `xn=1`. It is also equal to the order of the subgroup generated by the element. The order of an element divides the order of the group (if both are finite), since the following is true for any subgroup `H`: `#G = #H * #(G/H)` (Prove it).

# 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`.

`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)`.

`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".