Fall 2015

  • Lemma: \(f\) is injective \(\iff f\) has a left inverse \(f^{-1}\) satisfying \(f^{-1}f(a) = a\).

    Suppose \(f,g: A \to A\) are injective and \(x,y \in A\), we want to show that \((f\circ g)(x) = (f\circ g)(y) \implies x = y\). So suppose \(f(g(x)) = f(g(y))\). Since \(f\) is injective, \(f\) has a left inverse, so \(g(x) = g(y)\), and since \(g\) is injective \(x = y\). \(\hfill\blacksquare\)

  • Claim: take \(\delta < \min(1, \sqrt{\frac{\varepsilon}{5}})\). Then \({\left\lvert {x-2} \right\rvert} < \delta \implies 1 < x < 2 \implies 1 > \frac 1 x > \frac 1 2\), so in particular \(\frac 1 x < 1\) and \begin{align*}\begin{align*} {\left\lvert {x + \frac 1 x - \frac 5 2} \right\rvert} &= {\left\lvert {\frac{2x^2 - 5x + 2}{2x}} \right\rvert}\\ &< \frac 1 2 {\left\lvert {(2x^2-4x + 2) - x} \right\rvert}\\ &= \frac 1 2 {\left\lvert {2(x-2)^2 + 3(x-2)} \right\rvert} \\ &< {\left\lvert {2(x-2)^2 + 3(x-2)} \right\rvert} \\ &\leq 2{\left\lvert {x-2} \right\rvert}^2 + 3{\left\lvert {x-2} \right\rvert} \\ &< 2\delta^2 + 3\delta \\ &< 5\delta^2 \hspace{10em} \text{since } \delta < 1 \implies \delta^2 < \delta \\ &< 5 \left(\sqrt{\frac{\varepsilon}{5}}\right)^2 \\ &= \varepsilon. \end{align*}\end{align*} \(\hfill\blacksquare\)

  • Denoting \(D^n f \coloneqq{\frac{\partial ^n f}{\partial x^n}\,}\) and noting that \(D^1 D^n f = D^{n+1}f\), we have \begin{align*}\begin{align*} D^0f &= xe^{2x} \\ D^1f &= e^{2x} + 2D^0f \\ D^2f &= 2e^{2x} + 2D^1f \\ D^3f &= 4e^{2x} + 2D^2f \\ \end{align*}\end{align*}

    and (claim) so we find that \begin{align*}D^n f = 2^{n-1}e^{2x} + 2D^{n-1}f.\end{align*}

    This is trivially the case for \(n=1\), where we’ve computed \(D^1 f = e^2x + 2xe^{2x} = 2^0e^{2x} + 2D^0 f\), and the inductive step holds exactly because \begin{align*} D^{n+1}f = DD^{n}f \\ = D(2^{n-1}e^{2x} + 2D^{n-1}f) \\ =2^n e^{2x} + 2D^n f. \end{align*} \(\hfill\blacksquare\)

  • It will exactly be the row space of \begin{align*} A = \left(\begin{array}{rrrr} 1 & 1 & 1 & 1 \\ 3 & 4 & 6 & 7 \\ 5 & 6 & 8 & 9 \end{array}\right), \end{align*} where we could note that \(R_3 = 2R_1 + R_2\) but \(R_1 \neq \lambda R_2\) and so the first two rows span the correct subspace. We can also easily compute the RREF, which has the same rowspace, \begin{align*}\tilde A = \left(\begin{array}{rrrr} 1 & 0 & -2 & -3 \\ 0 & 1 & 3 & 4 \\ 0 & 0 & 0 & 0 \end{array}\right)\end{align*} from which we find that \(\mathbf{v}_1 = {\left[ {1,0,-2,-3} \right]}\) and \(\mathbf{v}_2 = {\left[ {0,1,3,4} \right]}\) also do the job. \(\hfill\blacksquare\)

  • We have \(p_A(x) = (x+1)(x-1)(x) = x^3 - x\) and so by Cayley-Hamilton, \(A^3 - A = 0 \implies A^3 = A\). \(\hfill\blacksquare\)

  • We first need the derivatives of \(\arctan\), since \begin{align*} T(p, x) = \sum_{n=0}^\infty \frac{f^{(n)}(p)}{n!}(x-p)^n \implies T(0, x) = \sum_{n=0}^\infty \frac{f^{(n)}(0)}{n!}x^n \end{align*}

    Starting with \(y=\arctan x\), we can write \(\tan y - x = 0 \implies \sec^2y~dy - 1~dx = 0\) by implicit differentiation and the chain rule, and so \({\frac{\partial y}{\partial x}\,} = y' = \sec^{-2}y = \cos^2(\arctan x))\). Embed this in a triangle with angle \(y\) to find that \begin{align*}y' = (1+x^2)^{-1}.\end{align*}

    Computing higher derivatives of \(\arctan\) directly is tedious, so instead we’ll take a power series of \(y'\) and differentiate that instead:

    \begin{align*}\begin{align*} f'(x) = (1+x^2)^{-1} & =1 - x^2 + x^4 - x^6 + x^8 - x^{10} + \cdots = \sum_{i=0} (-1)^{i}x^{2i} \\ \implies f''(x) = {\frac{\partial }{\partial x}\,} (1+x^2)^{-1} &= -2x + 4x^3 - 6x^5 + \cdots = \sum_{i=1}^\infty (2i)(-1)^{i}x^{2i-1} \\ \implies f^{(3)}(x) = {\frac{\partial ^2}{\partial x^2}\,} (1+x^2)^{-1} &= -2 + 12x^2 - 30x^4 + \cdots = \sum_{i=1}^\infty (2i )(2i-1)(-1)^{i}x^{2i-2} \\ \implies f^{(4)}(x) = {\frac{\partial ^3}{\partial x^3}\,} (1+x^2)^{-1} &= 24x - 120x^3 + \cdots = \sum_{i=2}^\infty (2i)(2i-1)(2i-2)(-1)^{i}x^{2i-3} \\ \implies f^{(5)}(x) = {\frac{\partial ^4}{\partial x^4}\,} (1+x^2)^{-1} &= 24 - 360x^2 + \cdots = \sum_{i=2}^\infty (2i)(2i-1)(2i-2)(2i-3)(-1)^{i}x^{2i-4} \\ \end{align*}\end{align*}

    so recalling that we’ll be evaluating at \(x=0\), we can notice that whenever \(n+1\) is even (and thus \(n\) is odd), there is no constant term. So for \(n+1\) odd, we can extract the general pattern: \begin{align*}\begin{align*} f^{(n)}(0) &= {\left.{{ {\frac{\partial ^{n}}{\partial x^{n}}\,} (1+x^2)^{-1}}} \right|_{{x = 0}} } &= \begin{cases} (n-1)! & n-1 \equiv 0 \operatorname{mod}4 \\ -(n-1)! & n -1 \equiv 2 \operatorname{mod}4 \end{cases} \end{align*}\end{align*}

    Thus the desired Taylor expansion will be \begin{align*} T(0, x) = \sum_{n=0}^\infty \frac{f^{(n)}(0)}{n!}x^n \\ = \arctan(0) + \sum_{n>0\text{ odd}} \sigma_n \frac{(n-1)!}{n!} x^n \\ =\sum_{n>0\text{ odd}} \frac{\sigma_nx^n}{n} \end{align*}

    where \(\sigma_n = -1 \iff n \equiv 3 \operatorname{mod}4\).

    We can then start writing this out: \begin{align*} T(0, x) = x - \frac 1 3 x^3 + + \frac{1}{5}x^5 - \frac 1 7 x^7 \end{align*}

    We then want an \(n\) such that \begin{align*}\frac{(\frac{n-1}{2})!}{(n-1)!} (\frac 1 {10^2})^n \leq \frac 1 {10^5}.\end{align*}

    Checking manually, \(i=1\) does not work, but \(i=2\) does, so we take the approximation \begin{align*}\widehat f(x) = x - \frac 1 3 x^3.\end{align*} \(\hfill\blacksquare\)

  • Suppose \(f_n \rightrightarrows g\) with each \(f_n\) bounded; we want to show that all of the \(f_n\) are uniformly bounded by some \(M\), i.e. \begin{align*} \exists M {~\mathrel{\Big\vert}~}\forall x\in {\mathbf{R}}, \forall n\in {\mathbb{N}}, \quad {\left\lvert {f_n(x)} \right\rvert} \leq M. \end{align*}

  • Since each \(f_n\) is bounded, we can produce some \(M_n\) such that \({\left\lvert {f_n(x)} \right\rvert} \leq M < \infty\).
  • Since \(f_n \rightrightarrows g\), we can give ourselves an epsilon of room and get an \(N\) such that \(n\geq N \implies {\left\lvert {f_n(x) - g(x)} \right\rvert} < \varepsilon\). We then write \begin{align*} f_n(x) = f_n(x) - g(x) + g(x) - f_N(x) + f_N(x) \\ \implies {\left\lvert {f_n(x)} \right\rvert} \leq {\left\lvert {f_n(x) - g(x)} \right\rvert} + {\left\lvert {g(x) - f_N(x)} \right\rvert} + {\left\lvert {f_N(x)} \right\rvert} \\ \leq \varepsilon + \varepsilon + M_N \end{align*}

by the above two statements. But \(N<\infty\), so we can choose \(M = \max\left\{{M_1, M_2, \cdots M_{N-1}, 2\varepsilon + M_N}\right\}\) as a uniform bound. Then just take \(\varepsilon \to 0\). (Maybe not necessary?)

  • Write \(f\) as \(f(x,y)\), we are then given that \(f_x, f_y \in C_0(\left\{{0}\right\})\). It has the type \begin{align*} f: {\mathbf{R}}^2 \to {\mathbf{R}}\\ (x,y) \mapsto f(x,y) \end{align*}

    Definition: \begin{align*} \mathbf{u} = {\left[ {a, b} \right]} \implies D _ { \mathbf{u} } f = \lim _ { h \rightarrow 0 } \frac { f ( x + a h , y + b h ) - f ( x , y ) } { h } \end{align*} Definition: \begin{align*} {\frac{\partial }{\partial x}\,}f(x,y) = f_x(x,y) = \lim_{h\to 0} \frac{f(x+h, y) - f(x,y)}{h} \end{align*}

    We need to show that \(D_{\mathbf{u}}f\) exists for arbitrary \(\mathbf{u}\). Wlog, assume \({\left\lVert {\mathbf{u}} \right\rVert} = 1\), and let \(D_{\mathbf{u}}f\) denote the directional derivative of \(f\) in the direction \(\mathbf{u}\). Fix some \(\mathbf{p} \in {\mathbf{R}}^2\) and define the curve \begin{align*} \gamma(t): {\mathbf{R}}\to {\mathbf{R}}^2 \\t \mapsto \mathbf{p} + t \mathbf{u} \end{align*}

    Then define \begin{align*} g: {\mathbf{R}}\to {\mathbf{R}}\\ t \mapsto f(\gamma(t)) = f(\mathbf{p} + t\mathbf{u}). \end{align*}

    Note that \(g(0) = f(\mathbf{p})\).

    Since the partial derivatives of \(f\) exist and are continuous, \(f\) is differentiable with derivative \begin{align*} Df = \sum_{i=1}^2 {\frac{\partial f}{\partial x_i}\,} \mathbf{e}_i \coloneqq\nabla f. \end{align*}

    Thus by the multivariate chain rule, \(g\) is differentiable as well and can be computed as \begin{align*} g'(t) = Df(\gamma(t)) ~ D\gamma(t) = {\left\langle {\nabla f(\gamma(t))},~{\gamma'(t)} \right\rangle}. \end{align*}

    Note that \(\gamma(0) = \mathbf{p}\), and \(\gamma\) is a linear function of \(t\) that is differentiable, with derivative/tangent vector \(\gamma'(t) = \mathbf{u}\).

    From this, we can compute \begin{align*} g'(0) = {\left\langle {\nabla f(\mathbf{p})},~{\mathbf{u}} \right\rangle} \end{align*} in the above expression.

    Since \(g\) is differentiable, we can write \begin{align*}\begin{align*} g'(0) &= {\left.{{g'(t)}} \right|_{{t=0}} } \\ &= {\left.{{\lim_{h\to 0} \frac{g(t+h) - g(t)}{h}}} \right|_{{t=0}} } \\ &= \lim_{h\to 0} \frac{g(h) - g(0)}{h} \\ &\coloneqq\lim_{h\to 0} \frac{f(\mathbf{p} + h\mathbf{u}) - f(\mathbf{p})}{h} \end{align*}\end{align*}

    In particular, since \(g'(0)\) exists, the limit in the last term does as well, and by definition is \(D_{\mathbf{u}}(\mathbf{p})\). Now letting \(\mathbf{p} = \mathbf{x}\) be variable, we combine these to obtain \begin{align*} D_{\mathbf{u}}(\mathbf{p}) = {\left\langle {\nabla f(\mathbf{p})},~{\mathbf{u}} \right\rangle} \end{align*} Since \(\mathbf{u}\) was arbitrary, this shows that the directional derivative exists in any direction and is given by the above expression. \(\hfill\blacksquare\)

  • Note that \(8=2^3\) is a prime power \(p^n\), so we can get this as a quotient of a polynomial algebra. In particular, since \(p=2\), we’ll want to look at \({ \mathbf{F} }_2[t]\), and we’ll want to quotient it by a polynomial of degree \(n=3\) that is irreducible in the base field \({ \mathbf{F} }_2\).

    We could use Rabin’s test: \(f\) is irreducible over \(F\) iff \begin{align*} x^{p^n} - x \equiv 0 \operatorname{mod}f \quad\text{ and }\quad \left( f , x ^ { p ^ { n / q } } - x \right) = 1 ~~\forall \text{ prime $q$ dividing $n$} \end{align*}

    But I’m bad at polynomial division. With some work, we can brute force by listing out all of the \(2^4 = 16\) polynomials over \({ \mathbf{F} }_2\) of degree at most 3. Then start multiplying together low-degree terms to cross off higher degree terms; using degree arguments you can show that the irreducible polynomials are: \begin{align*} x \\ x+1 \\ x^2 + 1 \\ x^2 + x + 1 \\ x^3 + x + 1 \\ x^3 + x^2 + 1. \end{align*}

    So we can pick one of the degree 3 ones to obtain our desired field: \begin{align*} GF(8) = \frac{{ \mathbf{F} }_2[t]}{\left\langle{t^3+t+1}\right\rangle}. \hfill\blacksquare \end{align*} General Principle Trinomials of the form \(x^n + ax^{<n} + b\) with \(a,b \in { \mathbf{F} }_p\) are usually irreducible.