# Monthly Archives: June 2015

## A tricky limit from the Math 32A final

The following limit appeared on yesterday’s Math 32A final:
$\lim_{(x, y) \to (0, 0)} \frac{\sin x^2 + \tan^2 y}{x^2 + \tan y^2}.$
The limit seemed to cause a lot of trouble. In fact, no one in the lecture of 200 students had a perfect solution! I thought I would write up a solution here to give some closure on the problem. I will use only tools that appear in a standard calculus course: the squeeze theorem and the fact that $$\lim_{x \to 0} \sin(x) / x = 1$$.

The first thing to note is that evaluating the limit along the $$x$$-axis (taking $$y = 0$$) gives a limit of $$1$$:
$\lim_{x \to 0} \frac{\sin x^2}{x^2} = \lim_{u \to 0} \frac{\sin u}{u} = 1.$
This tells us that if the original limit exists, it must be $$1$$. However, this argument does not allow us to conclude that the limit does indeed exist. Choosing any other path through $$(0, 0)$$ will also give a limit of $$1$$, so one should anticipate that the limit exists and is equal to $$1$$. We remark that, in general, $$\lim_{(x, y) \to (a, b)} f(x, y) = L$$ if and only if $$\lim_{(x, y) \to (a, b)} |f(x, y) – L| = 0$$. This reformulation is convenient because $$0 \leq |f(x, y) – L|$$, so applying the squeeze theorem is less fussy: we only need to bound $$|f(x, y) – L| \leq g(x, y)$$ where $$\lim_{(x, y) \to (a, b)} g(x, y) = 0$$. Thus, we wish to show that
$\lim_{(x, y) \to (0, 0)} \left| \frac{\sin x^2 + \tan^2 y}{x^2 + \tan y^2} – 1\right| = 0.$
To this end, we compute the following bound
\begin{align*} \left| \frac{\sin x^2 + \tan^2 y}{x^2 + \tan y^2} – 1\right| &= \left| \frac{\sin x^2 + \tan^2 y}{x^2 + \tan y^2} – \frac{x^2 + \tan y^2}{x^2 + \tan y^2}\right|\\ &= \left| \frac{\sin x^2 – x^2 + \tan^2 y – \tan y^2}{x^2 + \tan y^2}\right|\\ &\leq \left| \frac{\sin x^2 – x^2}{x^2 + \tan y^2}\right| + \left| \frac{\tan^2 y – \tan y^2}{x^2 + \tan y^2}\right|\\ &\leq \left| \frac{\sin x^2 – x^2}{x^2}\right| + \left| \frac{\tan^2 y – \tan y^2}{\tan y^2}\right|. \end{align*}
The first inequality holds by the triangle inequality ($$|a + b| \leq |a| + |b|$$), while the second inequality holds because $$\tan y^2 \geq 0$$ (when $$y$$ is close to $$0$$) and $$x^2 \geq 0$$. Since we have
$0 \leq \left| \frac{\sin x^2 + \tan^2 y}{x^2 + \tan y^2} – 1\right| \leq \left| \frac{\sin x^2 – x^2}{x^2}\right| + \left| \frac{\tan^2 y – \tan y^2}{\tan y^2}\right|,$
it suffices to show that the limit of the expression on the right is $$0$$ as $$(x, y) \to (0, 0)$$. The expression on the right is much easier to deal with than the original limit because it is the sum of two terms, each of which only involves a single variable. Thus, one can use familiar methods from single variable calculus to compute the limits. One can show that in fact we have
$\lim_{x \to 0} \left| \frac{\sin x^2 – x^2}{x^2}\right| = 0 \quad\text{and}\quad \lim_{y \to 0} \left| \frac{\tan^2 y – \tan y^2}{\tan y^2}\right| = 0.$
The first limit follows easily from the fact that $$\lim_{x \to 0} \sin(x) / x = 1$$, while the second limit requires a little more ingenuity. We compute
\begin{align*} \lim_{y \to 0} \left| \frac{\tan^2 y – \tan y^2}{\tan y^2}\right| &= \left| \lim_{y \to 0} \frac{\tan^2 y}{\tan y^2} – \lim_{y \to 0} \frac{\tan y^2}{\tan y^2} \right|\\ &= \left| \lim_{y \to 0} \frac{\tan^2 y}{\tan y^2} – 1 \right|\\ &= \left| \lim_{y \to 0} \frac{\tan^2 y}{y^2} \frac{y^2}{\tan y^2} – 1 \right|\\ &= \left| \lim_{y \to 0} \left(\frac{\tan y}{y}\right)^2 \frac{y^2}{\tan y^2} – 1 \right|\\ &= | (1)^2 (1) – 1 |\\ &= 0. \end{align*}
The penultimate equality follows from the fact that $$\lim_{y \to 0} \tan(y) / y = 1$$, which can be deduced by writing $$\tan y = (\sin y) / (\cos y)$$ and using the familiar $$\sin(y) / y$$ limit identity (or an application of L’Hopital’s rule). At any rate, we may now deduce from the squeeze theorem that
$\lim_{(x, y) \to (0, 0)} \frac{\sin x^2 + \tan^2 y}{x^2 + \tan y^2} = 1.$
Whew.

## Math 32A Final Review Problems

I have just finished putting together some problems for the final review for Math 32A, which are available here. I have included answers to the problems. I haven’t gotten a chance to double check my work on the solutions, so let me know in the comments below if you disagree with any of the answers. I will go over the solutions this evening again and update the answers if I find any problems.

## John Nash, Cryptography, and Computational Complexity

Recently, the brilliant mathematician John Nash and his wife were killed in a car crash. While Nash was probably most famous for his pioneering work on game theory and his portrayal in Ron Howard‘s popular film A Beautiful Mind, he also worked in the field of cryptography. Several years ago, the NSA declassified several letters from 1955 between Nash and the NSA wherein Nash describes some ideas for an encryption/decryption scheme. While the NSA was not interested in the particular scheme devised by Nash, it seems that Nash foresaw the importance of computational complexity in the field of cryptography. In the letters, Nash states:

Consider the enciphering process with a finite “key,” operating on binary messages. Specifically, we can assume the process [is] described by a function
$y_i = F(\alpha_1, \alpha_2, \ldots, \alpha_r; x_i, x_{i-1}, \ldots, x_{i-n})$
where the $$\alpha$$’s, $$x$$’s and $$y$$’s are mod 2 and if $$x_i$$ is changed with the other $$x$$’s and $$\alpha$$’s left fixed then $$y_i$$ is changed. The $$\alpha$$’s denote the “key” containing $$r$$ bits of information. $$n$$ is the maximum span of the “memory” of the process…

…We see immediately that in principle the enemy needs very little information to break down the process. Essentially, as soon as $$r$$ bits of enciphered message have been transmitted the key is about determined. This is no security, for a practical key should not be too long. But this does not consider how easy or difficult it is for the enemy to make the computation determining the key. If this computation, although always possible in principle, were sufficiently long at best the process could still be secure in a practical sense.

Nash goes on to say that

…a logical way to classify the enciphering process is the way in which the computation length for the computation on the key increases with increasing length of the key… Now my general conjecture is as follows: For almost all sufficiently complex types of enciphering…the mean key computation length increases exponentially with the length of the key.

The significance of this general conjecture, assuming its truth, is easy to see. It means that it is quite feasible to design ciphers that are effectively unbreakable.

To my knowledge, Nash’s letter letter is the earliest reference to using computational complexity to achieve practical cryptography. The idea is that while it is theoretically possible to decrypt an encrypted message without the key, doing so requires a prohibitive amount of computational resources. Interestingly, Nash’s letter predates an (in)famous 1956 letter from Kurt Godel to John von Neumann which is widely credited as being the first reference to the “P vs NP problem.” However the essential idea of the P vs NP problem is nascent in Nash’s conjecture: there are problems whose solution can efficiently be verified, but finding such a solution is computationally intractable. Specifically, a message can easily be decrypted if one knows the key, but finding the key to decrypt the message is hopelessly difficult.

The P vs NP problem was only formalized 16 years after Nash’s letters by Stephen Cook in his seminal paper, The complexity of theorem-proving procedures. In fact, Nash’s conjecture is strictly stronger than the P vs NP problem–its formulation is more akin to the exponential time hypothesis, which was only formulated in 1999!

Concerning Nash’s conjecture, he was certainly aware of the difficulty of its proof:

The nature of this conjecture is such that I cannot prove it, even for a special type of cipher. Nor do I expect it to be proven. But this does not destroy its significance. The probability of the truth of the conjecture can be guessed at on the basis of experience with enciphering and deciphering.

Indeed, the P vs NP problem remains among the most notorious open problems in mathematics and theoretical computer science.

PDF of Nash’s Letters to the NSA.

teaching

## Two Tricky Linear Algebra Problems

There are a couple questions from the homework that seem to have given people (myself included) a fair amount of trouble. Since I wasn’t able to give satisfactory answers to these questions in office hours, I thought I’d write up clean solutions to the problems, available here. The questions both involve projections $$E : V \to V$$ where $$V$$ is an inner product space. The problems ask you to prove:

1. If $$E$$ is idempotent ($$E^2 = E$$) and normal ($$E^* E = E E^*$$), then $$E$$ is self-adjoint ($$E = E^*$$).
2. If $$E$$ satisfies $$\|E v\| \leq \|v\|$$ for all $$v \in V$$, then $$E$$ is an orthogonal projection onto its image.