#+TITLE: Midterm One
#+AUTHOR: Lizzy Hunt
#+STARTUP: entitiespretty fold inlineimages
#+LATEX_HEADER: \notindent \notag \usepackage{ dsfont } \usepackage{amsmath} \usepackage[a4paper,margin=1in,portrait]{geometry}
#+LATEX: \setlength\parindent{0pt}
#+OPTIONS: toc:nil

* Question One
\begin{verbatim}
In [1]: sols = lambda n: set(filter(lambda x: (x**2 + x) % n == 0, range(n)))

In [2]: sols(5)
Out[2]: {0, 4}

In [3]: sols(6)
Out[3]: {0, 2, 3, 5}
\end{verbatim}

* Question Two
$p | a \Rightarrow np = a$

$p | a + bc \Rightarrow mp = a + bc \Rightarrow mp = np + bc \Rightarrow (m - n)p = bc$ which implies $p$ is a factor of $bc$ ($p | bc$), so by Theorem 1.5, $p | b$ or $p | c$.

* Question Three
From the multiplication table we can see that $e$ is the identity element $1_R$, the zero
element $0_R$ is $z$. From the addition table we find that every element is its own
additive inverse.

** a
The units in this ring are ${e, g}$, and the zero divisors are ${a, b, c, f}$.

** b
$3bd = 3(bd) = 3z = b$

$2ac = 2(ac) = 2b = b + b = z$

$g^{-1}f^3 = (g)(fff) (gf)(ff) = (d)(f) = d$

Thus, $3bd - 2ac + g^{-1}f^3 = b - z + d = b + d = f$.

* Question Four
To get a hunch,

#+BEGIN_SRC python
In [1]: import numpy as np

In [2]: def find_counter(matrix_generator, in_ring, search_space=range(-100, 100)):
...:     for a1 in search_space:
...:         n = matrix_generator(a1)
...:         for a2 in search_space:
...:             m = matrix_generator(a2)
...:             dot = np.dot(n, m)
...:             add = np.add(n, m)
...:
...:             if not in_ring(dot):
...:                 return (n, m, dot, '*')
...:             if not in_ring(add):
...:                 return (n, m, add, '+')
...:
...:     return None
...:

In [3]: find_counter(lambda a: [[0, a], [0, -a]], \
                     lambda m: m[0][1] == -m[1][1] and m[0][0] == 0 \
                     and m[1][0] == 0)

In [4]: find_counter(lambda a: [[0, a], [a, 0]], \
                     lambda m: m[0][1] == m[1][0] and m[1][1] == 0 \
                     and m[0][0] == 0)
Out[4]:
([[0, -100], [-100, 0]],
 [[0, -100], [-100, 0]],
 array([[10000,     0],
        [    0, 10000]]),
 '*')
#+END_SRC
** a
Using Theorem 3.2, this is a ring:

1. S_1 is closed under addition: $x, y \in S_1 \Rightarrow x + y =$ $\begin{smallmatrix} 0 & a \\ 0 & -a \end{smallmatrix}$ $+$ $\begin{smallmatrix} 0 & b \\ 0 & -b \end{smallmatrix}$ $\Rightarrow$ $x + y = \begin{smallmatrix} 0 & a + b \\ 0 & (-a) + (-b) \end{smallmatrix} = \begin{smallmatrix} 0 & a + b \\ 0 & -(a + b) \end{smallmatrix}$ which satisfies the rule
2. S_1 is closed under multiplication: $x, y \in S_1 \Rightarrow x \cdot y =$ $\begin{smallmatrix} 0 & a \\ 0 & -a \end{smallmatrix}$ $\cdot$ $\begin{smallmatrix} 0 & b \\ 0 & -b \end{smallmatrix}$ $\Rightarrow$ $x \cdot y =$ $\begin{smallmatrix} 0 + (a)(0) & 0(b) + a(-b) \\ 0 + (-a)(0) & 0b + (-a)(-b) \end{smallmatrix}$ $=$ $\begin{smallmatrix} 0 & -ab \\ 0 & ab \end{smallmatrix}$ which satisfies the rule
3. $0_R_{} = 0_{S_1} =$ $\begin{smallmatrix} 0 & 0 \\ 0 & 0 \end{smallmatrix}$
4. $a \in S_1 \Rightarrow a + x = 0_R \wedge x \in S_1$ since $\begin{smallmatrix} 0 & a \\ 0 & -a \end{smallmatrix}$ $+$ $x = 0_{S_1} =$ $\begin{smallmatrix} 0 & 0 \\ 0 & 0 \end{smallmatrix}$ $\Rightarrow x =$ $\begin{smallmatrix} 0 & -a \\ 0 & a \end{smallmatrix}$ $\in S_1$

** b
$\begin{smallmatrix} 0 & -100 \\ -100 & 0 \end{smallmatrix}$ $\cdot$ $\begin{smallmatrix} 0 & -100 \\ -100 & 0 \end{smallmatrix}$ = $\begin{smallmatrix} 10000 & 0 \\ 0 & 10000 \end{smallmatrix}$ is not in the ring.

* Question Five
No, it is not a homomorphism from the definition in 3.3.

Consider $n =$ $\begin{smallmatrix} 0 & 0 \\ 0 & 1 \end{smallmatrix}$ and $m =$ $\begin{smallmatrix} 1 & 0 \\ 0 & 0 \end{smallmatrix}$.

Then $nm =$ $\begin{smallmatrix} 0 & 0 \\ 0 & 0 \end{smallmatrix}$ and thus $Trace(n) \cdot Trace(m) = 1 \wedge Trace(nm) = 0 \Rightarrow f(n)f(m) \neq f(nm)$.

* Question Six
No, I don't believe $f$ to be an isomorphism.
** Lemma
We need to show that $x \in Q \wedge x \sqrt{2} = y \in Q \Rightarrow x = 0$.

If $x \neq 0$ then $y$ can be represented as $\frac{a}{b}$ with $a, b \neq 0 \wedge a,b \in \mathds{Z}$ and $(a, b) = 1$.

So, $x \sqrt{2} = \frac{a}{b} \Rightarrow x \sqrt{2} b = a \Rightarrow x^2(2b^2) = a^2$ and thus $2 | aa$, and by applying Corollary 1.6, $2 | a$.

By substituting $2c = a$ (a is divisible by 2), $x^2(2b^2) = 4c^2 \Rightarrow x^2 b^2 = 2c^2$ which implies $2 | (x^2 b^2) \Rightarrow 2 | x$ or $2 | b$ (again by Corollary 1.6).

But 2 cannot divide $b$ as well as $a$, since $(a, b) = 1$ and $b \neq 0$.

Thus $2 | x$. So $x = 2d \Rightarrow 4d^2(2b^2) = a^2 \Rightarrow 4 | a^2$, so $4e = a$, and by similar logic for $b$ above, $4 | x$.
Then, subsituting $x = 4f \Rightarrow 16f^2(2b^2) = a^2 \Rightarrow 16 | a^2$. Again, $16 | x$.

In fact, all range elements $R$ of the recursive function on the natural numbers $f \ni f(1) = 2, f(n) = f(n-1)^2 \text{\{} n > 1 \text{\}}$ must divide $x$.

Thus, x must be sup($R$), or 0 (everything divides zero). Obviously, though, $R$ is unbounded on the right, so it follows $x = 0$.

** Proof
$a, b \in Q(\sqrt{2}) \Rightarrow f(a) = n + m \sqrt{2} \wedge b = x + y \sqrt{2} \Rightarrow f(a) = n - m \sqrt{2} \vee f(b) = x - y \sqrt{2}$.

$f$ is not injective; if we assume $f(a) = f(b) \Rightarrow a = b$ then $f(a) - f(b) = 0 \Rightarrow n - m \sqrt{2} - x - y \sqrt{2} = 0 \Rightarrow 0 = (n-x) - (m + y)\sqrt{2} \Rightarrow n-x = (m+y)\sqrt{2}$ and, as $n-x \in Q$ since
Q is a ring and by definition, $(m + y)\sqrt{2} \in Q$ implies $(m + y) = 0$ by the lemma, thus $m = -y$. But $a = b \Rightarrow m = y$, a contradiction.