exercises-finite.ipynb

Kernel:

%%html
<link href="http://mathbook.pugetsound.edu/beta/mathbook-content.css" rel="stylesheet" type="text/css" />
<link href="https://aimath.org/mathbook/mathbook-add-on.css" rel="stylesheet" type="text/css" />
<style>.subtitle {font-size:medium; display:block}</style>
<link href="https://fonts.googleapis.com/css?family=Open+Sans:400,400italic,600,600italic" rel="stylesheet" type="text/css" />
<link href="https://fonts.googleapis.com/css?family=Inconsolata:400,700&subset=latin,latin-ext" rel="stylesheet" type="text/css" /><!-- Hide this cell. -->
<script>
var cell = $(".container .cell").eq(0), ia = cell.find(".input_area")
if (cell.find(".toggle-button").length == 0) {
ia.after(
    $('<button class="toggle-button">Toggle hidden code</button>').click(
        function (){ ia.toggle() }
        )
    )
ia.hide()
}
</script>

Important: to view this notebook properly you will need to execute the cell above, which assumes you have an Internet connection. It should already be selected, or place your cursor anywhere above to select. Then press the "Run" button in the menu bar above (the right-pointing arrowhead), or press Shift-Enter on your keyboard.

ParseError: KaTeX parse error: \newcommand{\lt} attempting to redefine \lt; use \renewcommand

Section22.3Exercises

¶

1

Calculate each of the following.

1. $[\gf(3^6) : \gf(3^3)]$

2. $[\gf(128): \gf(16)]$

3. $[\gf(625) : \gf(25) ]$

4. $[\gf(p^{12}): \gf(p^2)]$

Hint

Make sure that you have a field extension.

2

Calculate $[\gf(p^m): \gf(p^n)]\text{,}$ where $n \mid m\text{.}$

3

What is the lattice of subfields for $\gf(p^{30})\text{?}$

4

Let $\alpha$ be a zero of $x^3 + x^2 + 1$ over ${\mathbb Z}_2\text{.}$ Construct a finite field of order 8. Show that $x^3 + x^2 + 1$ splits in ${\mathbb Z}_2(\alpha)\text{.}$

Hint

There are eight elements in ${\mathbb Z}_2(\alpha)\text{.}$ Exhibit two more zeros of $x^3 + x^2 + 1$ other than $\alpha$ in these eight elements.

5

Construct a finite field of order 27.

Hint

Find an irreducible polynomial $p(x)$ in ${\mathbb Z}_3[x]$ of degree 3 and show that ${\mathbb Z}_3[x]/ \langle p(x) \rangle$ has 27 elements.

6

Prove or disprove: ${\mathbb Q}^\ast$ is cyclic.

7

Factor each of the following polynomials in ${\mathbb Z}_2[x]\text{.}$

1. $x^5- 1$

2. $x^6 + x^5 + x^4 + x^3 + x^2 + x + 1$

3. $x^9 - 1$

4. $x^4 +x^3 + x^2 + x + 1$

Hint

(a) $x^5 -1 = (x+1)(x^4+x^3 + x^2 + x+ 1)\text{;}$ (c) $x^9 -1 = (x+1)( x^2 + x+ 1)(x^6+x^3+1)\text{.}$

8

Prove or disprove: ${\mathbb Z}_2[x] / \langle x^3 + x + 1 \rangle \cong {\mathbb Z}_2[x] / \langle x^3 + x^2 + 1 \rangle\text{.}$

Hint

True.

9

Determine the number of cyclic codes of length $n$ for $n = 6\text{,}$ 7, 8, 10.

10

Prove that the ideal $\langle t + 1 \rangle$ in $R_n$ is the code in ${\mathbb Z}_2^n$ consisting of all words of even parity.

11

Construct all BCH codes of

1. length 7.

2. length 15.

Hint

(a) Use the fact that $x^7 -1 = (x+1)( x^3 + x+ 1)(x^3+x^2+1)\text{.}$

12

Prove or disprove: There exists a finite field that is algebraically closed.

Hint

False.

13

Let $p$ be prime. Prove that the field of rational functions ${\mathbb Z}_p(x)$ is an infinite field of characteristic $p\text{.}$

14

Let $D$ be an integral domain of characteristic $p\text{.}$ Prove that $(a - b)^{p^n} = a^{p^n} - b^{p^n}$ for all $a, b \in D\text{.}$

15

Show that every element in a finite field can be written as the sum of two squares.

16

Let $E$ and $F$ be subfields of a finite field $K\text{.}$ If $E$ is isomorphic to $F\text{,}$ show that $E=F\text{.}$

17

Let $F \subset E \subset K$ be fields. If $K$ is a separable extension of $F\text{,}$ show that $K$ is also separable extension of $E\text{.}$

Hint

If $p(x) \in F[x]\text{,}$ then $p(x) \in E[x]\text{.}$

18

Let $E$ be an extension of a finite field $F\text{,}$ where $F$ has $q$ elements. Let $\alpha \in E$ be algebraic over $F$ of degree $n\text{.}$ Prove that $F( \alpha )$ has $q^n$ elements.

Hint

Since $\alpha$ is algebraic over $F$ of degree $n\text{,}$ we can write any element $\beta \in F(\alpha)$ uniquely as $\beta = a_0 + a_1 \alpha + \cdots + a_{n-1} \alpha^{n-1}$ with $a_i \in F\text{.}$ There are $q^n$ possible $n$-tuples $(a_0, a_1, \ldots, a_{n-1})\text{.}$

19

Show that every finite extension of a finite field $F$ is simple; that is, if $E$ is a finite extension of a finite field $F\text{,}$ prove that there exists an $\alpha \in E$ such that $E = F( \alpha )\text{.}$

20

Show that for every $n$ there exists an irreducible polynomial of degree $n$ in ${\mathbb Z}_p[x]\text{.}$

21

Prove that the Frobenius map $\Phi : \gf(p^n) \rightarrow \gf(p^n)$ given by $\Phi : \alpha \mapsto \alpha^p$ is an automorphism of order $n\text{.}$

22

Show that every element in $\gf(p^n)$ can be written in the form $a^p$ for some unique $a \in \gf(p^n)\text{.}$

23

Let $E$ and $F$ be subfields of $\gf(p^n)\text{.}$ If $|E| = p^r$ and $|F| = p^s\text{,}$ what is the order of $E \cap F\text{?}$

24Wilson's Theorem

Let $p$ be prime. Prove that $(p-1)! \equiv -1 \pmod{p}\text{.}$

Hint

Factor $x^{p-1} - 1$ over ${\mathbb Z}_p\text{.}$

25

If $g(t)$ is the minimal generator polynomial for a cyclic code $C$ in $R_n\text{,}$ prove that the constant term of $g(x)$ is $1\text{.}$

26

Often it is conceivable that a burst of errors might occur during transmission, as in the case of a power surge. Such a momentary burst of interference might alter several consecutive bits in a codeword. Cyclic codes permit the detection of such error bursts. Let $C$ be an $(n,k)$-cyclic code. Prove that any error burst up to $n-k$ digits can be detected.

27

Prove that the rings $R_n$ and ${\mathbb Z}_2^n$ are isomorphic as vector spaces.

28

Let $C$ be a code in $R_n$ that is generated by $g(t)\text{.}$ If $\langle f(t) \rangle$ is another code in $R_n\text{,}$ show that $\langle g(t) \rangle \subset \langle f(t) \rangle$ if and only if $f(x)$ divides $g(x)$ in ${\mathbb Z}_2[x]\text{.}$

29

Let $C = \langle g(t) \rangle$ be a cyclic code in $R_n$ and suppose that $x^n - 1 = g(x) h(x)\text{,}$ where $g(x) = g_0 + g_1 x + \cdots + g_{n - k} x^{n - k}$ and $h(x) = h_0 + h_1 x + \cdots + h_k x^k\text{.}$ Define $G$ to be the $n \times k$ matrix

$$\begin{equation*} G = \begin{pmatrix} g_0 & 0 & \cdots & 0 \\ g_1 & g_0 & \cdots & 0 \\ \vdots & \vdots &\ddots & \vdots \\ g_{n-k} & g_{n-k-1} & \cdots & g_0 \\ 0 & g_{n-k} & \cdots & g_{1} \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & g_{n-k} \end{pmatrix} \end{equation*}$$

and $H$ to be the $(n-k) \times n$ matrix

$$\begin{equation*} H = \begin{pmatrix} 0 & \cdots & 0 & 0 & h_k & \cdots & h_0 \\ 0 & \cdots & 0 & h_k & \cdots & h_0 & 0 \\ \cdots & \cdots & \cdots & \cdots & \cdots & \cdots & \cdots \\ h_k & \cdots & h_0 & 0 & 0 & \cdots & 0 \end{pmatrix}. \end{equation*}$$

1. Prove that $G$ is a generator matrix for $C\text{.}$

2. Prove that $H$ is a parity-check matrix for $C\text{.}$

3. Show that $HG = 0\text{.}$