Trigonometry and Nested Radicals

Early last month, I was chatting with one of my officemates about a curious problem I had studied in high school. I hadn't written any of the results down, so much of the discussion involved me rediscovering the results and proving them with much more powerful tools than I once possessed.

Before writing about the problem I had played around with, I want to give a brief motivation. For as long as humans have been doing mathematics, finding values of $\pi$ has been deemed worthwhile (or every generation has just found it worthwhile to waste time computing digits).

One such way the Greeks (particularly Archmides) computed $\pi$ was by approximating a circle by a regular polygon and letting the number of sides grow large enough so that the error between the area of the unit circle ($\pi \cdot 1^2$) and the area of the polygon would be smaller than some fixed threshold. Usually these thresholds were picked to ensure that the first $k$ digits were fully accurate (for some appropriate value of $k$).

In many introductory Calculus courses, this problem is introduced exactly when the limit is introduced and students are forced to think about the area problem in the regular polygon:

Given $N$ sides, the area is $N \cdot T_N$ where $T_N$ is the area of each individual triangle given by one side of the polygon and the circumcenter.

Call one such triangle $\Delta ABC$ and let $BC$ be the side that is also a side of the polygon while the other sides have $\left|AB\right| = \left|AC\right| = 1$ since the polygon is inscribed in a unit circle. The angle $\angle BAC = \frac{2\pi}{N}$ since each of the triangles has the same internal angle and there are $N$ of them. If we can find the perpendicular height $h$ from $AB$ to $C$, the area will be $\frac{1}{2} h \left|AB\right| = \frac{h}{2}$. But we also know that
$$\sin\left(\angle BAC\right) = \frac{h}{\left|AC\right|} \Rightarrow h = \sin\left(\frac{2\pi}{N}\right).$$ Combining all of these, we can approximate $\pi$ with the area:
$$\pi \approx \frac{N}{2} \sin\left(\frac{2\pi}{N}\right) = \pi \frac{\sin\left(\frac{2\pi}{N}\right)}{\frac{2 \pi}{N}}.$$ As I've shown my Math 1A students, we see that
$$\lim_{N \to \infty} \pi \frac{\sin\left(\frac{2\pi}{N}\right)}{\frac{2 \pi}{N}} = \pi \lim_{x \to 0} \frac{\sin(x)}{x} = \pi$$ so these are indeed good approximations.

Theory is Nice, But I Thought We Were Computing Something

Unfortunately for us (and Archimedes), computing $\sin\left(\frac{2\pi}{N}\right)$ is not quite as simple as dividing by $N$, so often special values of $N$ were chosen. In fact, starting from $N$ and then using $2N$, the areas could be computed via a special way of averaging the previous areas. Lucky for us, such a method is equivalent to the trusty half angle identities (courtesy of Abraham De Moivre). To keep track of these polygons with a power of two as the number of sides, we call $A_n = \frac{2^n}{2} \sin\left(\frac{2\pi}{2^n}\right)$.

Starting out with the simplest polygon, the square with $N = 2^2$ sides, we have
$$A_2 = 2 \sin\left(\frac{\pi}{2}\right) = 2.$$ Jumping to the octagon (no not that "The Octagon"), we have
$$A_3 = 4 \sin\left(\frac{\pi}{4}\right) = 4 \frac{\sqrt{2}}{2} = 2 \sqrt{2}.$$ So far, the toughest thing we've had to deal with is a $45^{\circ}$ angle and haven't yet had to lean on Abraham (him, not him) for help. The hexadecagon wants to change that:
$$A_4 = 8 \sin\left(\frac{\pi}{8}\right) = 8 \sqrt{\frac{1 - \cos\left(\frac{\pi}{4}\right)}{2}} = 8 \sqrt{\frac{2 - \sqrt{2}}{4}} = 4 \sqrt{2 - \sqrt{2}}.$$

To really drill home the point (and motivate my next post) we'll compute this for the $32$-gon (past the point where polygons have worthwhile names):

$$A_5 = 16 \sin\left(\frac{\pi}{16}\right) = 16 \sqrt{\frac{1 - \cos\left(\frac{\pi}{8}\right)}{2}}.$$ Before, we could rely on the fact that we know that a $45-45-90$ triangle looked like, but now, we come across $\cos\left(\frac{\pi}{8}\right)$, a value which we haven't seen before. Luckily, Abraham has help here as well:
$$\cos\left(\frac{\pi}{8}\right) = \sqrt{\frac{1 + \cos\left(\frac{\pi}{4}\right)}{2}} = \sqrt{\frac{2 + \sqrt{2}}{4}} = \frac{1}{2} \sqrt{2 + \sqrt{2}}$$ which lets us compute
$$A_5 = 16 \sqrt{\frac{1 - \frac{1}{2} \sqrt{2 + \sqrt{2}}}{2}} = 8 \sqrt{2 - \sqrt{2 + \sqrt{2}}}.$$

So why have I put you through all this? If we wave our hands like a magician, we can see this pattern continues and for the general $n$

$$A_n = 2^{n - 2} \sqrt{2 - \sqrt{2 + \sqrt{2 + \sqrt{\cdots + \sqrt{2}}}}}$$

where there are $n - 3$ nested radicals with the $\oplus$ sign and only one minus sign at the beginning.

This motivates us to study two questions, what is the limiting behavior of such a nested radical:

$$\sqrt{2 + s_1 \sqrt{2 + s_2 \sqrt{ \cdots }}}$$ as the signs $s_1, s_2, \ldots$ takes values in $\left\{-1, 1\right\}$. Recasting in terms of the discussion above, we want to know how close we are to $\pi$ as we increase the number of sides.

When I was in high school, I just loved to nerd out on any and all math problems, so I studied this just for fun. Having heard about the unfathomable brain of Ramanujan and the fun work he had done with infinitely nested radicals, I wanted to examine which sequences of signs $(s_1, s_2, \ldots)$ produced an infinite radical that converged and what the convergence behavior was.

I'm fairly certain my original questions came from an Illinois Council of Teachers of Mathematics (ICTM) contest problem along the lines of

$$\text{Find the value of the infinite nested radical } \sqrt{2 + \sqrt{2 + \cdots}}$$ or maybe the slightly more difficult $$\text{Find the value of the infinite nested radical } \sqrt{2 - \sqrt{2 + \sqrt{2 - \sqrt{2 + \cdots}}}}.$$ Armed with my TI-83, I set out to do some hardcore programming and figure it out. It took me around a month of off-and-on tinkering. This second time around as a mathematical grown-up, it took me the first half of a plane ride from SFO to Dallas.

In the next few weeks/months, I hope to write a few blog posts, including math, proofs and some real code on what answers I came up with and what other questions I have.

About Bossy Lobster

Calculating a Greatest Common Divisor with Dirichlet's Help

Having just left Google and started my PhD in Applied Mathematics at Berkeley, I thought it might be appropriate to write some (more) math-related blog posts. Many of these posts, I jotted down on napkins and various other places on the web and just haven't had time to post until now.

For today, I'm posting a result which was somewhat fun to figure out with/for one of my buddies from Michigan Math. I'd also like to point out that he is absolutely kicking ass at Brown.

While trying to determine if
$$J(B_n)_{\text{Tor}}\left(\mathbb{Q}\right) \stackrel{?}{=} \mathbb{Z}/2\mathbb{Z}$$ where $J(B_n)$ is the Jacobian of the curve $B_n$ given by $y^2 = (x + 2) \cdot f^n(x)$ where $f^n$ denotes $\underbrace{f \circ \cdots \circ f}_{n \text{ times}}$ and $f(x) = x^2 - 2$.

Now, his and my interests diverged some time ago, so I can't appreciate what steps took him from this to the problem I got to help with. However, he was able to show (trivially maybe?) that this was equivalent to showing that
$$\gcd\left(5^{2^n} + 1, 13^{2^n} + 1, \ldots, p^{2^n} + 1, \ldots \right) = 2 \qquad (1)$$ where the $n$ in the exponents is the same as that in $B_n$ and where the values we are using in our greatest common divisor (e.g. $5, 13$ and $p$ above) are all of the primes $p \equiv 5 \bmod{8}$.

My buddy, being sadistic and for some reason angry with me, passed me along the stronger statement:
$$\gcd\left(5^{2^n} + 1, 13^{2^n} + 1\right) = 2 \qquad (2)$$ which I of course struggled with and tried to beat down with tricks like $5^2 + 12^2 = 13^2$. After a few days of this struggle, he confessed that he was trying to ruin my life and told me about the weaker version $(1)$.

When he sent me the email informing me of this, I read it at 8am, drove down to Santa Clara for PyCon and by the time I arrived at 8:45am I had figured the weaker case $(1)$ out. This felt much better than the days of struggle and made me want to write about my victory (which I'm doing now). Though, before we actually demonstrate the weaker fact $(1)$  I will admit that I am not in fact tall. Instead I stood on the shoulders of Dirichlet and called myself tall. Everything else is bookkeeping.

Let's Start the Math

First, if $n = 0$, we see trivially that
$$\gcd\left(5^{2^0} + 1, 13^{2^0} + 1\right) = \gcd\left(6, 14\right) = 2$$ and all the remaining terms are divisible by $2$ hence the $\gcd$ over all the primes must be $2$.

Now, if $n > 0$, we will show that $2$ divides our $\gcd$, but $4$ does not and that no odd prime can divide this $\gcd$. First, for $2$, note that
$$p^{2^n} + 1 \equiv \left(\pm 1\right)^{2^n} + 1 \equiv 2 \bmod{4}$$ since our primes are odd. Thus they are all divisible by $2$ and none by $4$.

Now assume some odd prime $p^{\ast}$ divides all of the quantities in question. We'll show no such $p^{\ast}$ can exist by contradiction.

In much the same way we showed the $\gcd$ wasn't divisible by $4$, we seek to find a contradiction in some modulus. But since we are starting with $p^{2^n} + 1 \equiv 0 \bmod{p^{\ast}}$, if we can find some such $p$ with $p \equiv 1 \bmod{p^{\ast}}$, then we'd have our contradiction from
$$0 \equiv p^{2^n} + 1 \equiv 1^{2^n} + 1 \equiv 2 \bmod{p^{\ast}}$$ which can't occur since $p^{\ast}$ is an odd prime.

With this in mind, along with a subsequence of the arithmetic progression $\left\{5, 13, 21, 29, \ldots\right\}$, it seems that using Dirichlet's theorem on arithmetic progressions may be a good strategy. However, this sequence only tells us about the residue modulo $8$, but we also want to know about the residue modulo $p^{\ast}$. Naturally, we look for a subsequence in
$$\mathbb{Z}/\mathbb{8Z} \times \mathbb{Z}/\mathbb{p^{\ast}Z}$$ corresponding to the residue pair $(5 \bmod{8}, 1 \bmod{p^{\ast}})$. Due to the Chinese remainder theorem this corresponds to a unique residue modulo $8p^{\ast}$.

Since this residue $r$ has $r \equiv 1 \bmod{p^{\ast}}$, we must have
$$r \in \left\{1, 1 + p^{\ast}, 1 + 2p^{\ast}, \ldots, 1 + 7p^{\ast}\right\} .$$ But since $1 + kp^{\ast} \equiv r \equiv 5 \bmod{8}$, we have $kp^{\ast} \equiv 4 \bmod{8}$ and $k \equiv 4\left(p^{\ast}\right)^{-1} \bmod{8}$ since $p^{\ast}$ is odd and invertible mod $8$. But this also means its inverse is odd, hence $k \equiv 4\cdot(2k' + 1) \equiv 4 \bmod{8}$. Thus we have $1 + 4 p^{\ast} \in \mathbb{Z}/8p^{\ast}\mathbb{Z}$ corresponding to our residue pair. Thus every element in the arithmetic progression $S = \left\{(1 + 4p^{\ast}) + (8p^{\ast})k \right\}_{k=0}^{\infty}$ is congruent to $1 + 4 p^{\ast} \bmod{8p^{\ast}}$ and hence $5 \bmod{8}$ and $1 \bmod{p^{\ast}}$.

What's more, since $5 \in \left(\mathbb{Z}/8\mathbb{Z}\right)^{\times}$ and $1 \in \left(\mathbb{Z}/p^{\ast}\mathbb{Z}\right)^{\times}$, we have $1 + 4 p^{\ast} \in \left(\mathbb{Z}/8p^{\ast}\mathbb{Z}\right)^{\times}$ (again by the Chinese remainder theorem). Thus the arithmetic progression $S$ satisfies the hypothesis of Dirichlet's theorem. Hence there must at least one prime $p$ occurring in the progression (since there are infinitely many). But that also means $p$ occurs in $\left\{5, 13, 29, 37, \ldots\right\}$ hence we've reached our desired contradiction. RAA.

Now What?

We still don't know if the strong version $(2)$
$$\gcd\left(5^{2^n} + 1, 13^{2^n} + 1, \ldots, p^{2^n} + 1, \ldots \right) = 2$$ By similar arguments as above, if any odd prime $p^{\ast}$ divides this $\gcd$, then we have
$$5^{2^n} \equiv -1 \bmod{p^{\ast}}$$ hence there is an element of order $2^{n + 1}$. This means the order of the multiplicative group $\varphi\left(p^{\ast}\right) = p^{\ast} - 1$ is divisible by $2^{n + 1}$. Beyond that, who knows? We're still thinking about it (but only passively, more important things to do). About Bossy Lobster

Some Fibonacci Fun with Primes

I haven't written in way too long and just wanted to post this fun little proof.

Assertion: Let $F_n$ be the $n$th Fibonacci number defined by $F_n = F_{n-1} + F_{n-2}$, $F_0 = 0, F_1 = 1$. Show that for an odd prime $p\neq 5$, we have $p$ divides $F_{p^2−1}$.

Proof: We do this by working inside $\mathbb{F}_p$ instead of working in $\mathbb{R}$. The recurrence is given by

$$\left( \begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array} \right) \left( \begin{array}{c} F_{n-1} \\ F_{n-2} \end{array} \right) = \left( \begin{array}{c} F_{n-1} + F_{n-2} \\ F_{n-1} \end{array} \right) = \left( \begin{array}{c} F_n \\ F_{n-1} \end{array} \right)$$ and in general
$$\left( \begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array} \right)^{n} \left( \begin{array}{c} 1 \\ 0 \end{array} \right) = \left( \begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array} \right)^{n} \left( \begin{array}{c} F_1 \\ F_0 \end{array} \right) = \left( \begin{array}{c} F_{n + 1} \\ F_n \end{array} \right)$$ The matrix $A = \left(\begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array} \right)$ has characteristic polynomial
$$\chi_A(t) = (1 - t)(0 - t) - (1)(1) = t^2 - t - 1$$ If this polynomial has distinct roots, then $A$ is diagonalizable (this is sufficient, but not necessary). Assuming the converse we have $\chi_A(t) = (t - \alpha)^2$ for some $\alpha \in \mathbb{F}_p$; we can assume $\alpha \in \mathbb{F}_p$ since $-2\alpha = -1$ is the coefficient of $t$, which means $\alpha = 2^{-1}$ (we are fine with this since $p$ odd means that $2^{-1}$ exists). In order for this to be a root of $\chi_A$, we must have
$$0 \equiv 4 \cdot \chi_A\left(2^{-1}\right) \equiv 4 \cdot \left(2^{-2} - 2^{-1} - 1\right) \equiv 1 - 2 - 4 \equiv -5 \bmod{p}.$$ Since $p \neq 5$ is prime, this is not possible, hence we reached a contradiction and $\chi_A$ does not have a repeated root.

Thus we may write $\chi_A(t) = (t - \alpha)(t - \beta)$ for $\alpha, \beta \in \mathbb{F}_{p^2}$ (it's possible that $\chi_A$ is irreducible over $\mathbb{F}_p$, but due to degree considerations it must split completely over $\mathbb{F}_{p^2}$). Using this, we may write

$$A = P \left(\begin{array}{cc} \alpha & 0 \\ 0 & \beta \end{array} \right) P^{-1}$$ for some $P \in GL_{2} \left(\mathbb{F}_{p^2}\right)$ and so

$$A^{p^2 - 1} = P \left(\begin{array}{cc} \alpha & 0 \\ 0 & \beta \end{array} \right)^{p^2 - 1} P^{-1} = P \left(\begin{array}{cc} \alpha^{p^2 - 1}  & 0 \\ 0 & \beta^{p^2 - 1}  \end{array} \right)P^{-1}$$ Since $\chi_A(0) = 0 - 0 - 1 \neq 0$ we know $\alpha$ and $\beta$ are nonzero, hence $\alpha^{p^2 - 1} = \beta^{p^2 - 1} = 1 \in \mathbb{F}_{p^2}$. Thus $A^{p^2 - 1} = P I_2 P^{-1} = I_2$ and so

$$\left( \begin{array}{c} F_p \\ F_{p^2 - 1} \end{array} \right) = \left( \begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array} \right)^{p^2 - 1} \left( \begin{array}{c} 1 \\ 0 \end{array} \right) = I_2 \left( \begin{array}{c} 1 \\ 0 \end{array} \right) = \left( \begin{array}{c} 1 \\ 0 \end{array} \right)$$ so we have $F_{p^2 - 1} = 0$ in $\mathbb{F}_p$ as desired. About Bossy Lobster