pset-9.tex

\documentclass[letterpaper]{article}

\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{hyperref}
\usepackage{geometry}
\usepackage{nth}

% Comment the following lines to use the default Computer Modern font
% instead of the Palatino font provided by the mathpazo package.
% Remove the 'osf' bit if you don't like the old style figures.
\usepackage[T1]{fontenc}
\usepackage[sc,osf]{mathpazo}

\newcommand*{\QED}{\hfill\ensuremath{\square}}%

\makeatletter
\renewcommand{\@seccntformat}[1]{%
  \ifcsname prefix@#1\endcsname
    \csname prefix@#1\endcsname
  \else
    \csname the#1\endcsname\quad
  \fi}
% define \prefix@section
\newcommand\prefix@section{Question \thesection}
\makeatother

\DeclareMathOperator{\rank}{rank}
\DeclareMathOperator{\lcm}{lcm}
\DeclareMathOperator{\tr}{Tr}

% Set your name here
\def\name{Problem Set 9}


\geometry{
  body={6.5in, 8.5in},
  left=1.0in,
  top=1.25in
}

% Customize page headers
\pagestyle{myheadings}
\markright{\name}
\thispagestyle{empty}

% Custom section fonts
\usepackage{sectsty}
\sectionfont{\rmfamily\mdseries\Large}
\subsectionfont{\rmfamily\mdseries\itshape\large}

% Other possible font commands include:
% \ttfamily for teletype,
% \sffamily for sans serif,
% \bfseries for bold,
% \scshape for small caps,
% \normalsize, \large, \Large, \LARGE sizes.

% Don't indent paragraphs.
\setlength\parindent{0em}

\begin{document}

{\huge \name}

% Alternatively, print name centered and bold:
%\centerline{\huge \bf \name}

\vspace{0.25in}

Dev Dabke \\
MATH 501: Introduction to Algebraic Structures I \\
November 15, 2016 \\
Prof.\ Calderbank \\

\section{}
\label{sec:Question1}

By definition, we know that the trace of $ \gamma $ is:
\[
\tr{(\gamma)} = \gamma^{2^0} + \cdots + \gamma^{2^9}
\]
However, we see that $ \gamma^{31} - 1 = 0 $ by assumption.
Therefore, $ \gamma^{31} \gamma - \gamma = 0 $, which implies that $ \gamma^{32} = \gamma \iff \gamma^{2^{5}} = \gamma $.
Applying this to our trace formula, we find that:
\[
\tr{(\gamma)} = 2 \gamma^{2^0} + \cdots + 2 \gamma^{2^5} = 0
\]
Therefore, all solutions $ \gamma \in \mathbb{F}_{1024} $ to the equation $ x^{31} - 1 = 0 $ satisfy $ \tr{(\gamma)} = 0 $.
There are $ 31 $ of these.
\QED{}

\section{}
\label{sec:Question2}

\subsection{Part i}
\label{subs:2Parti}

Note that the minimal polynomial in $ \mathbb{F}_2 $ of the root $ \alpha : \alpha^4 + \alpha + 1 = 0 $ is very conveniently: $ g_1(x) = x^4 + x + 1 $.
The minimal polynomial of $ \alpha^3 $ is $ g_2(x) = x^4 + x^3 + x^2 + x + 1 $.
Thus, by definition, the generator polynomial is $ g(x) = g_1(x)g_2(x) $ and multiply through we yield:
\[
g(x) = x^8 + x^7 + x^6 + x^4 + 1
\]
By definition, the check polynomial $ h(x) = (x^{15} + 1) / g(x) $.
Since $ h(x) $ must include the factors of $ x^{15} + 1 $ that $ g(x) $ does not, we can see that $ h(x) = (x^4 + x^3 + 1)(x^2 + x + 1)(x + 1) $.
Multiplying through, we find that
\[
h(x) = x^7 + x^6 + x^4 + 1
\]
\QED{}

\subsection{Part ii}
\label{subs:2Partii}

Note that the degree of $ g(x) $ is $ 8 $.
By definition, we know that $ \deg{(g(x))} = N - k $, where $ C $ is a $ k $-dimensional code (cf.\ Lecture 18, Slide 5).
Since the codewords are polynomials with degree at most $ N - 1 $, we can easily see that by assumption $ N - 1 = 14 \implies N = 15 $.
Thus, $ 8 = 15 - k \iff k = 7 $.
Thus, $ C $ is a $ 7 $-dimensional code.
\QED{}

\subsection{Part iii}
\label{subs:2Partiii}

From what we saw before, we know that three rows will correspond to roots of $ p_1(x) = (x^4 + x^3 + 1) $, $ p_2(x) = (x^2 + x + 1) $, $ p_3(x) = (x + 1) $, i.e.\ the three minimal polynomial factors of $ h(x) $.
The first polynomial has factor $ \alpha^{-1} = \alpha^7 $; thus $ i = 7 $.
The second polynomial has factor $ \alpha^{5} $; thus $ i = 5 $.
The third polynomial $ p_3 $ has root $ \alpha_3 = 1 $ and corresponds to $ i = 0 $.
This will let us construct generator matrix:
\[
H = \begin{bmatrix}
\alpha^{0 \times 7} & \alpha^{1 \times 7} & \cdots & \alpha^{14 \times 7} \\
\alpha^{0 \times 5} & \alpha^{1 \times 5} & \cdots & \alpha^{14 \times 5} \\
\alpha^{0 \times 0} & \alpha^{1 \times 0} & \cdots & \alpha^{14 \times 0} \\
\end{bmatrix}
\]
As we demonstrated before, $ g(x) $ has two of the five minimal polynomial factors: $ (x^4 + x + 1)(x^4 + x^3 + x^2 + x + 1) $, while $ h(x) $ has three of the five minimal polynomial factors: $ (x^4 + x^3 + 1)(x^2 + x + 1)(x + 1) $.
Since all field elements have to be divisible by these five minimal polynomials, and $ h(x) $ and $ g(x) $ share no common factors, we know that the only element that is a multiple of both $ h(x) $ and $ g(x) $ is $ (x^{15} + 1) $.
By our chosen residue class, we know that $ (x^{15} + 1) = 0 $.
Therefore, the codes $ C_1 $ and $ C $, generated by $ h(x) $ and $ g(x) $ respectively, have trivial intersection, i.e.\ $ \langle 0 \rangle $.
\QED{}

\section{}
\label{sec:Question3}

We look at Lecture 18, Slide 7 and see that we have a few tests that tell us the number of errors in the transmitted signal.
By convention, we write $ Hv^t = \begin{pmatrix} s_1 \\ s_3 \end{pmatrix} = \begin{pmatrix} \alpha \\ \alpha^4 \end{pmatrix} $.
Let us perform the checks systematically and see what we find.
\\ \\
First, when $ s_1 = s_3 = 0 $, we have no errors.
But, note that $ \alpha \neq \alpha^4 \neq 0 $.
This means that $ s_1 \neq s_3 \neq 0 $, and thus there is at least one error.
\\ \\
Next, we test if $ s_3 = s_1^3 $.
If this is true, then we have one error.
By substitution, $ s_3 = s_1^3 \iff \alpha^4 = \alpha^3 $.
Since we have inverses in the field, we compute: $ \alpha^{-3}\alpha^4 = \alpha^{-3}\alpha^3 $ which reduces to $ \alpha = 1 $.
Thus, $ s_3 = s_1^3 \iff \alpha = 1 $.
However, note that $ \alpha $ must be a root of $ x^5 + x^3 + 1 $.
Plugging in $ 1 $, we yield $ 1^5 + 1^3 + 1 = 1 $ and so $ 1 $ is not a root.
Thus $ \alpha \neq 1 $.
By the contrapositive identity, we know that $ \alpha \neq 1 \implies s_3 \neq s_1^3 $.
Thus, by Slide 7, we know that we have at least $ 2 $ errors.
\\ \\
Finally, we must test if $ \tr{\left[ (s_1^3 + s_3) / s_1^3 \right]} = 0 $.
This tells us if we have two errors.
Since the trace is linear, we know that:
\[
\tr{\left[ \frac{(s_1^3 + s_3)}{s_1^3} \right]} = \tr{\left(\frac{s_1^3}{s_1^3} + \frac{s_3}{s_1^3}\right) = \tr{\left( 1 + \frac{\alpha^4}{\alpha^3} \right)}} = \tr{(1)} + \tr{(\alpha)}
\]
Note that $ \tr{(1)} = 1^{2^0} + 1^{2^1} + 1^{2^2} + 1^{2^3} + 1^{2^4} = 1 $.
Next, we solve for the trace of $ \alpha $.
Note that $ \alpha^5 + \alpha^3 + 1 = 0 \implies \alpha^6 + \alpha^4 + \alpha = 0 $.
However, $ \alpha^6 = \alpha $.
Thus, $ \alpha^6 + \alpha^4 + \alpha = 0 \implies \alpha^4 + 2\alpha = 0 $.
We take the trace and use its linearity to see that $ \tr{(\alpha^4)} + 2\tr{(\alpha)} = 0 \implies \tr{(\alpha^4)} = 0 $.
We also know that (by the properties of the trace) $ \tr{(\alpha^4)} = \tr{(\alpha^2)} = \tr{(\alpha)} $.
Thus, $ \tr{(\alpha)} = 0 $.
Going back, we see that $ \tr{(1)} = 1 $ and $ \tr{(\alpha)} = 0 $, so $ \tr{(1)} + \tr{(\alpha)} = 1 $.
Thus, we know that $ \tr{\left[ (s_1^3 + s_3) / s_1^3 \right]} = 1 \neq 0 $.
This means that we have strictly greater than two errors.
\\ \\
To conclude formally, we see that we have proven that we do not have zero, one, or two errors.
Thus, we must have \textit{at least} three errors.
\QED{}

\section{}
\label{sec:Question4}

Let us compute $ g(x) = f(x - 1) $.
We see that:
\[
g(x) = x^4 - 4x^3 + 6
\]
Let $ p = 2 $.
Now check the Eisenstein Criterion (Lecture 19, Slide 11).
We see that $ p $ does not divide $ 1 $, but it divides $ -4 $, $ 0 $, and $ 6 $.
In addition, $ p^2 = 4 $ and $ 4 $ does \textbf{not} divide $ 6 $.
Thus, the Eisenstein Criterion is satisfied, and we know that $ g(x) $ is irreducible in $ \mathbb{Q}[x] $.
However, since $ x $ is and arbitrary field element and $ 1 $ is also a field element, we know that $ x + 1 $ is also an arbitrary field element.
Thus, if $ g(x) $ is irreducible, we know that $ g(x + 1) $ is irreducible.
Since by construction, $ g(x + 1) = f(x - 1 + 1) = f(x) $, we can formally conclude that $ f(x) $ is irreducible in $ \mathbb{Q}[x] $.
\QED{}

\section{}
\label{sec:Question5}
No.
\\ \\
Let us walk through the proof:
\\ \\
The difference between an integral domain and a field is the existence of multiplicative inverses.
However, let us consider the finite integral domain $ D $ of size $ 10 $ that we have in front of us.
Since $ D $ is finite, we know that multiplying arbitrary strings of elements will eventually find a way to get ``back'' to $ 1 $, which means that we will have an inverse.
Let us consider this more rigorously.
Take arbitrary element $ x \in D $.
If there exists some power $ i : x^i = 1 $, then we are done.
$ x^{i - 1} $ is the inverse of $ x $.
\\ \\
Now, suppose that there does not exist some $ x^{i} = 1 $.
Since we are in a finite integral domain, we know that by taking powers $ j $ and $ k $ with $ j \neq k $ of $ x $, we will come to the point where $ x^j = x^k $ (because we will simply run out of options for these powers to equal, since there are literally only $ 10 $ elements in $ D $).
This would imply an inverse, again.
Formally, this means that all arbitrary elements of $ D $ have a well-defined multiplicative inverse.
Intuitively, we can see this result by noting that powers of arbitrary elements of $ D $ have to eventually cycle back to $ 1 $ because we only have $ 10 $ elements.
\\ \\
At any rate, a finite integral domain with well-defined inverses is in fact a finite field by definition.
Since finite fields must have prime power order and $ 10 $ is not of prime power order, we can formally conclude that there is no integral domain containing exactly $ 10 $ elements.
\QED{}

\section{}
\label{sec:Question6}

\subsection{Part i}
\label{subs:6Parti}

We will sadly proceed by quasi-brute force; however, we will use a neat trick: for this polynomial to have factors of order $ 4 $, it must have linear factors. For it to have factors of order $ 3 $, it must have factors of order $ 1 $.
\\ \\
This polynomial clearly has no linear factors.
Thus, it also has no factors of order $ 4 $.
\\ \\
$ x $ and $ x + 1 $ do not divide this polynomial.
Thus, it has no factors of order $ 1 $, and, thankfully, it has no factors of order $ 3 $.
\\ \\
$ x^2 $, $ x^2 + x $, $ x^2 + 1 $, and $ x^2 + x + 1 $ do not divide this polynomial, and so it does have not have factors of order $ 2 $.
\\ \\
This polynomial has degree $ 4 $ and has no factors of order $ 4 $, $ 3 $, $ 2 $, $ 1 $ or linear factors, it must be irreducible.
\QED{}

\subsection{Part ii}
\label{subs:6Partii}

Since we live in $ \mathbb{F}_{7} $, we know that $ 1 \equiv -6 \mod{7} $, and so we can equivalently write $ x^2 + 1 $ as $ x^2 - 6 $.
For reasons that will become clear, we will prove that $ x^2 - 6 $ is irreducible.
We will proceed by contradiction.
\\ \\
Assume that $ x^2 - 6 $ is not irreducible.
Note that $ x^2 - 6 $ must have linear factors if it is not irreducible.
Thus, $ a^2 = 6 $ for some $ a \in \mathbb{F}_{7} $.
Consider $ \mathbb{F}^{*}_{7} $, which is the cyclic multiplicative group of order $ 6 $ of the field.
Clearly $ a \neq 0 $, and so $ a \in \mathbb{F}^{*}_{7} $.
If we inspect the form of the squares $ y^2 $ in $ \mathbb{F}^{*}_{7} $, we can see that $ y^{2^{3}} = y^{6} = 1 $.
Thus the squares $ y^2 $ have order $ 3 $.
Since $ 6 = a^2 $, i.e.\ it is a square, we know that $ 6^{3} \equiv 1 \mod{7} $ for there to be such $ a $.
\\ \\
We use the techniques in our very problem set to compute that $ 6^{3} \equiv 6 \mod{7} $.
Thus, we see that $ 6 $ is not a square in $ \mathbb{F}^{*}_{7} $, and so there exists no $ a : a^2 = 6 $.
Rolling this back up, we see that $ x^2 - 6 $ thus cannot have any linear factors, but this is a contradiction.
Thus, $ x^2 - 6 $ is not, not irreducible, which means it is irreducible.
To formally conclude, we noted that $ x^2 - 6 $ is equivalent to $ x^2 + 1 $, and so $ x^2 + 1 $ is irreducible.
\QED{}

\subsection{Part iii}
\label{subs:6Partiii}

We will proceed by contradiction.
Assume that $ x^3 - 9 $ is not irreducible.
Note that $ x^3 - 9 $ must have linear factors if it is not irreducible.
Thus, $ a^3 = 9 $ for some $ a \in \mathbb{F}_{31} $.
Consider $ \mathbb{F}^{*}_{31} $, which is the cyclic multiplicative group of order $ 30 $ of the field.
Clearly $ a \neq 0 $, and so $ a \in \mathbb{F}^{*}_{31} $.
If we inspect the form of the cubes $ y^3 $ in $ \mathbb{F}^{*}_{31} $, we can see that $ y^{3^{10}} = y^{30} = 1 $.
Thus the cubes $ y^3 $ have order $ 10 $.
Since $ 9 = a^3 $, i.e.\ it is a cube, we know that $ 9^{10} \equiv 1 \mod{31} $ for there to be such $ a $.
\\ \\
We use the techniques in our very problem set to compute that $ 9^{10} \equiv 5 \mod{31} $.
Thus, we see that $ 9 $ is not a cube in $ \mathbb{F}^{*}_{31} $, and so there exists no $ a : a^3 = 9 $.
Rolling this back up, we see that $ x^3 - 9 $ thus cannot have any linear factors, but this is a contradiction.
Thus, $ x^3 - 9 $ is not, not irreducible, which means it is irreducible.
\QED{}

\end{document}