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

Life of π: Continued Fractions and Infinite Series

This is from a talk I gave to the UC Santa Cruz Math Club back in February. I have had the slides cluttering my desk since I gave the talk as a reminder of putting them up on the web, and today I finally cleaned them off!

An interested tidbit about these slides: I gave the same talk one other time as an undergraduate. As an undergraduate I gave the talk the day after a root canal. This February (at UCSC), one day after the talk I also had a root canal. What's the moral of the story? Don't give this talk.

No seriously, don't give this talk. Though the fact is cool and the math is not too bad to grasp, the stuff from slides 106 to 113 goes way over an audience's collective head just because they have stopped paying attention at that point. Too many variables!

Life of π: Continued Fractions and Infinite Series

View more presentations from bossylobster.

About Bossy Lobster

Finding (Fibonacci) Golden Nuggets Part 2

This is the mostly code second half of a two part post that delivers on a promise of meaningful uses of some theory I overviewed in my last set of posts. If you see words like topograph, river, and base and you aren't sure what I mean, you may want to read that last set of posts.

In the first half of this post, I outlined a solution to Project Euler problem 137 and will continue with the solution here. Stop reading now if you don't want to be spoiled. There was no code in the first post, so this post will be mostly code, providing a pretty useful abstraction for dealing with binary quadratic forms.

In the very specific solution, I was able to use one picture to completely classify all integer solutions to the equation \(5 x^2 - y^2 = 4\) due to some dumb luck. In the solution, we were able to use "Since every edge protruding from the river on the positive side has a value of 4 on a side...by the climbing lemma, we know all values above those on the river have value greater than 4," but this is no help when trying to find solutions to \(5 x^2 - y^2 = 9\), for example.

To answer the question \(5 x^2 - y^2 = 9\), we'll use the same pretty picture, but emphasize different parts of it. As you can see below, to classify all the values, we only need to travel from the initial base

along the river until we arrive at an identical base as the blue circles indicate below:

As noted above, for problem 137, we luckily were concerned about finding values \(4\) or \(1\), and the climbing lemma saved us from leaving the river. However, as I've noted above with #1, #2, #3, and #4, there are four tributaries coming from the river where we can consider larger values. Using the Arithmetic Progression Rule, we find values \(19\), \(11\), \(11\), and \(19\) as the first set of values above the river. From this point, we can stop checking for solutions to \(f(x, y) = 9\) since the climbing lemma says all further values above the tributaries will be \(11\) or greater. Thus, the only solutions come via scaling solutions of \(f(x, y) = 1\) by a factor of \(3\) (using homogeneity of a quadratic form).

Now for the (Python) code.

First, the data structure will be representative of a base along the river, but will also include the previous and next faces (on the shared superbases) and so we'll call it a juncture (my term, not Conway's). Each face in a juncture needs to be represented by both the pair \((x, y)\) and the value that \(f\) takes on this face. For our sanity, we organize a juncture as a tuple \((B, P, N, F)\), (in that order)

where \(P\) and \(N\) form a base straddling the river, with \(P\)  taking the positive value and \(N\) negative, as well as \(B\) the face "back" according to our orientation and \(F\)  the face "forward". Note, depending on the value of the form at \(F\), the river may "turn left" or "turn right" at the superbase formed by \(P\), \(N\) and \(F\).

To move "along the river until we arrive at an identical base", we need a way to move "forward" (according to our imposed orientation) to the next juncture on the river. Moving along the river, we'll often come to superbases \((B, N, P)\) and need to calculate the forward face \(F\). To calculate \(F\), assume we have already written a plus function that determines the vector at \(F\) by adding the vectors from \(P\) and \(N\) and determines the value at \(F\) by using the arithmetic progression rule with the values at all three faces in the superbase. Using this helper function, we can define a way to get the next juncture by turning left or right:

def next_juncture_on_river(juncture):
    B, P, N, F = juncture
    forward_val = F[1]
    if forward_val < 0:
        # turn left
        NEXT = plus(P, F, N[1])
        return (N, P, F, NEXT)
    elif forward_val > 0:
        # turn right
        NEXT = plus(N, F, P[1])
        return (P, F, N, NEXT)
    else:
        raise Exception("No infinite river here.")

Next, to know when to stop crawling on the river, we need to know when we have returned to an identical juncture, so we define:

def juncture_ident(juncture1, juncture2):
    B1, P1, N1, F1 = juncture1
    B2, P2, N2, F2 = juncture2
    return ((B1[1] == B2[1]) and (P1[1] == P2[1]) and
            (N1[1] == N2[1]) and (F1[1] == F2[1]))

Using these functions, we can first find the recurrence that will take us from a base of solutions to all solutions and second, keep track of the positive faces on the river to generalize the solution of \(f(x, y) = z\). For both of these problems, we impose a simplification for the sake of illustration. We will only be considering quadratic forms \[f(x, y) = a x^2 + b y^2\] where \(a > 0\), \(b < 0\) and \(\sqrt{\left|\frac{a}{b}\right|}\) is not rational. This guarantees the existence of a river. We will pass such forms as an argument form=(a, b) to our functions. We start our river at the juncture defined by the trivial base \((1, 0), (0, 1)\)

and crawl the river using the functions defined above. (Note: \(f(1, -1) = a(1)^2 + b(-1)^2 = a + b\), etc.)

To find the recurrence, we need just walk along the river until we get an identical juncture where the trivial base is replaced by the base \((p, q), (r, s)\). Using the same terminology as in part one, let the base vectors define a sequence \(\left\{(u_k, v_k)\right\}_{k \geq 0}\) with \(u_0 = (1, 0)\) and \(v_0 = (0, 1)\), then we have a recurrence \begin{align*}u_{k + 1} &= p u_k + q v_k \\ v_{k + 1} &= r u_k + s v_k. \end{align*} Using this -- \(u_{k + 2} - p u_{k + 1} - s(u_{k + 1} - p u_k) = q v_{k + 1} - s (q v_k) = q(r u_k)\) -- hence \(u\) satisfies the recurrence \(u_{k + 2} = (r q - p s)u_k + (p + s)u_{k + 1}\). (You can check that \(v\) satisfies this as well.) Hence our function to spit out the recurrence coefficients is:

def get_recurrence(form):
    a, b = form
    B = ((1, -1), a + b)
    P = ((1, 0), a)
    N = ((0, 1), b)
    F = ((1, 1), a + b)
    J_init = (B, P, N, F)
    J_curr = next_juncture_on_river(J_init)
    while not juncture_ident(J_init, J_curr):
        J_curr = next_juncture_on_river(J_curr)

    final_B, final_P, final_N, final_F = J_curr
    p, q = final_P[0]
    r, s = final_N[0]
    return (r*q - p*s, p + s)

For solving \(f(x, y) = z\), (\(z\) positive) we need to consider all the positive tributaries coming out of the river and let them grow and grow until the climbing lemma tells us we no longer need to consider values larger than \(z\). In order to consider tributaries, we describe a new kind of juncture. Instead of having a positive/negative base in the center of the juncture, we have two consecutive faces from the positive side

and have the negative from across the river as the "back" face. With this definition, we first write a function to return all tributaries:

def all_positive_tributaries(form):
    # ...Initialization logic...

    new_positives = []
    J_curr = next_juncture_on_river(J_init)
    while not juncture_ident(J_init, J_curr):
        # we add a new positive if the forward
        # value is positive
        forward = J_curr[-1]
        if forward[1] > 0:
            new_positives.append(J_curr)
        J_curr = next_juncture_on_river(J_curr)

    # For each (B, P, N, F) in new_positives, we want to
    # transform to a juncture with positive values, which will
    # be (N, P_1, P_2, P_F)
    result = []
    for new_positive in new_positives:
        B, P, N, F = new_positive
        new_face = plus(P, F, N[1])
        tributary = (N, P, F, new_face)
        result.append(tributary)
    return result

For each tributary, we can climb up away from the river until our values are too large. So we write a helper function to take a given tributary and a max value and recursively "climb" the topograph until we exceed the value. This function will naively return all possible faces (value and vector) without checking the actual values.

def seek_up_to_val(juncture, max_value):
    N, P_1, P_2, P_F = juncture
    if P_F[1] > max_value:
        return []
    result = [P_F]

    turn_left = plus(P_1, P_F, P_2[1])
    J_left = (P_2, P_F, P_1, turn_left)
    result.extend(seek_up_to_val(J_left, max_value))

    turn_right = plus(P_2, P_F, P_1[1])
    J_right = (P_1, P_F, P_2, turn_right)
    result.extend(seek_up_to_val(J_right, max_value))
    return result

Finally, we can combine these two helper functions into a function which will find all solutions to \(f(x, y) = z\) above the river. We may have a pair (or pairs) \((x, y)\) on the topograph where \(f(x, y) = \frac{z}{k^2}\) for some integer \(k\); if so, this gives rise to a solution \((kx, ky)\) which we'll be sure to account for in our function.

def all_values_on_form(form, value):
    # Use a helper (factors) to get all positive integer factors of value
    factor_list = factors(value)
    # Use another helper (is_square) to determine which factors can be
    # written as value/k^2 for some integer k
    valid_factors = [factor for factor in factor_list
                     if is_square(value/factor)]

    tributaries = all_positive_tributaries(form)
    found = set()
    for tributary in tributaries:
        candidates = seek_up_to_val(tributary, value)
        found.update([candidate for candidate in candidates
                      if candidate[1] in valid_factors])
        # Since each tributary is of the form (N, P_1, P_2, P_F) for
        # P_1, P_2 on the river, we need only consider P_1 and P_2 since
        # those faces above are in candidates. But P_2 will always be in
        # next tributary, so we need not count it. You may assume this ignores
        # the very final tributary, but here P_2 actually lies in the 
        # second period of the river
        N, P_1, P_2, F = tributary
        if P_1[1] in valid_factors:
            found.add(P_1)

    # Finally we must scale up factors to account for
    # the reduction by a square multiple
    result = []
    for face in found:
        (x, y), val = face
        if val < value:
            ratio = int(sqrt(value/val))
            x *= ratio
            y *= ratio
        result.append((x, y))

    return result

Combining all_values_on_form with get_recurrence, we can parameterize every existing solution!

As far as Project Euler is concerned, in addition to Problem 137, I was able to write lightning fast solutions to Problem 66, Problem 94, Problem 100, Problem 138 and Problem 140 using tools based on the above -- a general purpose library for solving binary quadratic forms over integers!

About Bossy Lobster

Finding (Fibonacci) Golden Nuggets Part 1

As I mentioned in my last set of posts, the content would go somewhere and this post will be the first to deliver on that. In fact this is the all math, no code first half of a two part post that will deliver. If you see words like topograph, river, and base and you aren't sure what I mean, you may want to read that last set of posts.

In this post, I outline a solution to Project Euler problem 137, so stop reading now if you don't want to be spoiled. There is no code here, but the second half of this post has a pretty useful abstraction.

The problems asks us to consider \[A_F(z) = z F_1 + z^2 F_2 + z^3 F_3 + \ldots,\] the generating polynomial for the Fibonacci sequence*. The problem defines (without stating so), a sequence \(\left\{z_n\right\}_{n > 0}\) where \(A_F(z_n) = n\) and asks us to find the values \(n\) for which \(z_n\) is rational. Such a value \(n\) is called a golden nugget. As noted in the problem statement, \(A_F(\frac{1}{2}) = 2\), hence \(z_2 = \frac{1}{2}\) is rational and \(2\) is the first golden nugget.

As a first step, we determine a criterion for \(n\) to be a golden nugget by analyzing the equation \(A_F(z) = n\). With the recurrence relation given by the Fibonacci sequence as inspiration, we consider \begin{align*}(z + z^2)A_F(z) = z^2 F_1 &+  z^3 F_2 + z^4 F_3 + \ldots \\ &+ z^3 F_1 + z^4 F_2 + z^5 F_3 + \ldots. \end{align*}Due to the fact that \(F_2 = F_1 = 1\) and the nature of the recurrence relation, we have \[(z +z^2)A_F(z) = z^2 F_2 + z^3 F_3 + z^4 F_4 + \ldots = A_F(z) -z\] which implies \[A_F(z) = \frac{z}{1 - z - z^2}.\] Now solving \(A_F(z) = n\), we have \[z = n - n z - n z^2 \Rightarrow n z^2 + (n + 1)z - n = 0.\] In order for \(n\) to be a golden nugget, we must have the solutions \(z\) rational. This only occurs if the discriminant \[(n + 1)^2 - 4(n)(-n) = 5 n^2 + 2 n + 1\] in the quadratic is the square of a rational.

So we now positive seek values \(n\) such that \(5 n^2 + 2 n + 1 = m^2\) for some integer \(m\) (the value \(m\) must be an integer since a rational square root of an integer can only be an integer.) This equation is equivalent to \[25n^2 + 10n + 5 = 5m^2\] which is equivalent to \[5m^2 - (5 n + 1)^2 = 4.\] This is where Conway's topograph comes in. We'll use the topograph with the quadratic form \(f(x, y) = 5 x^2 - y^2\) to find our solutions. First note, a solution is only valuable if \(y \equiv 1 \bmod{5}\) since \(y = 5 n + 1\) must hold. Also, since \(\sqrt{5}\) is irrational, \(f\) can never take the value \(0\), but \(f(1, 0) = 5\) and \(f(0, 1) = -1\), hence there is a river on the topograph and the values of \(f\) occur in a periodic fashion. Finally, since we take pairs \((x, y)\) that occur on the topograph, we know \(x\) and \(y\) share no factors. Hence solutions \(f(x, y) = 4\) can come either come from pairs on the topograph or by taking a pair which satisfies \(f(x, y) = 1\) and scaling up by a factor of \(2\) (we will have \(f(2x, 2y) = 2^2 \cdot 1 = 4\) due to the homogeneity of \(f\)).

Starting from the trivial base \(u = (1, 0)\) and \(v = (0, 1)\), the full period of the river has length \(8\) as seen below:

(Note: in the above, the values denoted as combinations of \(u\) and \(v\) are the vectors for each face on the topograph while the numbers are the values of \(f\) on these vectors.) Since every edge protruding from the river on the positive side has a value of \(4\) on a side (the value pairs are \((5, 4)\), \((4, 1)\), \((1, 4)\), and \((4, 5)\)), by the climbing lemma, we know all values above those on the river have value greater than \(4\). Thus, the only solutions we are concerned with -- \(f(x, y) = 1\) or \(4\) -- must appear on the river. Notice on the river, the trivial base \((u, v)\) is replaced by the base \((9 u + 20 v, 4 u + 9 v)\). This actually gives us a concrete recurrence for the river and with it we can get a complete understanding of our solution set.

When we start from the trivial base, we only need consider moving to the right (orientation provided by the above picture) along the river since we only care about the absolute value of the coordinates (\(n\) comes from \(y\), so it must be positive). As such, we have a sequence of bases \(\left\{(u_k, v_k)\right\}_{k \geq 0}\) with \(u_0 = (1, 0)\), \(v_0 = (0, 1)\) and recurrence \begin{align*}u_{k + 1} &= 9 u_k + 20 v_k \\ v_{k + 1} &= 4 u_k + 9 v_k. \end{align*} This implies that both \(\left\{u_k\right\}\) and \(\left\{v_k\right\}\) satisfy the same relation \begin{align*}u_{k + 2} - 9 u_{k + 1} - 9(u_{k + 1} - 9 u_k) &= 20 v_{k + 1} - 9(20 v_k) = 20(4 u_k) \\ v_{k + 2} - 9 v_{k + 1} - 9(v_{k + 1} - 9 v_k) &= 4 u_{k + 1} - 9(4 u_k) = 4(20 v_k). \end{align*} With these recurrences, you can take the three base solutions on the river and quickly find each successive golden nugget. Since each value is a coordinate in a vector, it satisfies the same linear recurrence as the vector. Also, since each of the solution vectors occur as linear combinations of \(u_k\) and \(v_k\), they must satisfy the same recurrence as well.

Since the recurrence is degree two, we need the first two values to determine the entire sequence. For the first solution we start with \(u_0 + v_0 = (1, 1)\) and \(u_1 + v_1 = (13, 29)\); for the second solution we start with \(u_0 + 2 v_0) = (2, 4)\) and \(u_1 + 2 v_1 = (17, 38)\); and for the third solution we start with \(5 u_0 + 11 v_0 = (5, 11)\) and \(5 u_1 + 11 v_1 = (89, 199)\). For the second solution, since \(f(1, 2) = 1\), we use homogeneity to scale up to \((2, 4)\) and \((34, 76)\) to start us off. With these values, we take the second coordinate along the recurrence and get the following values:

n	First	Second	Third
0	1	4	11
1	29	76	199
2	521	1364	3571
3	9349	24476	64079
4	167761	439204	1149851
5	3010349	7881196	20633239
6	54018521	141422324	370248451
7	969323029	2537720636	6643838879
8	17393796001	45537549124	119218851371
9	312119004989	817138163596	2139295485799
10	5600748293801	14662949395604	38388099893011

We don't get our fifteenth golden nugget candidate (value must be one more than a multiple of \(5\)) until \(5600748293801\), which yields \(\boxed{n = 1120149658760}\). By no means did I do this by hand in real life; I didn't make a pretty representation of the river either. I just wanted to make the idea clear without any code. To get to the code (and the way you should approach this stuff), move on to the second half of this post.

*The Fibonacci sequence is given by \(F_0 = 0\), \(F_1 = 1\), and \(F_{n} = F_{n - 1} + F_{n - 2}\).

About Bossy Lobster

Conway's Topograph Part 3

This is the third (continued from Part 2) in a series of three blog posts. In the following we'll investigate a few properties of an object called Conway’s topograph. John Conway conjured up a way to understand a binary quadratic form – a very important algebraic object – in a geometric context. This is by no means original work, just my interpretation of some key points from his The Sensual (Quadratic) Form that I'll need for some other posts.

---

Definition: For the form \(f(x, y) = a x^2 + h x y + b y^2\), we define the discriminant as the value \(ab - \left(\frac{1}{2}h\right)^2\).  \(\Box\)

The base \((1, 0)\) and \((0, 1)\) take values \(a\) and \(b\) on the form in the Definition above and are part of a sequence with common difference \(h\). In fact, if we know the values \(a'\), \(b'\) and the difference \(h'\) at any base (edge in the topograph), the value \(a'b' - \left(\frac{1}{2}h'\right)^2\) is independent of the base and the direction (left or right) which determines the sign of \(h'\) and hence equal to the discriminant. To see this, first note the sign of \(h'\) is immaterial since it is squared. Also, consider the two other bases (edges) in the superbase. As in the proof of the climbing lemma, one base takes values \(a' = a\) and \(b' = a + b + h\) with common difference \(h' = 2a + h\) which gives
\begin{align*}
a'b' - \left(\frac{1}{2}h'\right)^2 &= a(a + b + h) - \frac{1}{4}\left(2a + h\right)^2 \\
&= a^2 + a b + a h - \left(a^2 + a h + \frac{1}{4} h^2\right) \\
&= ab - \left(\frac{1}{2}h\right)^2.
\end{align*}
Similarly the other base in the given superbase gives
\begin{align*}
a'b' - \left(\frac{1}{2}h'\right)^2 &= (a + b + h)b - \frac{1}{4}\left(2b + h\right)^2 \\
&= b^2 + a b + b h - \left(b^2 + b h + \frac{1}{4} h^2\right) \\
&= ab - \left(\frac{1}{2}h\right)^2.
\end{align*}
Having showed that there are no cycles when starting from a given superbase, our work in understanding the topograph is not complete. We haven't actually showed that we can get from one superbase to any other superbases within the topograph. To show this, we'll use the discriminant and the following.

Definition: A superbase \(W\) is called a well if all the edges at \(W\) point away from \(W\).

\(\Box\)

Notice a well is dependent on the values, hence depends on the form \(f\). In a positive--valued topograph, we may find a well by traveling along the topograph in the opposite direction of the edges. Eventually, we must encounter a superbase where all arrows point out (as above), leaving us nowhere to travel and thus becoming our well. This is because, assuming the topograph is positive--valued, we can only decrease in value for so long (eventually the values must approach the minimum).

Lemma: (The Well Lemma) For a positive--valued form \(f\) and a well (with respect to \(f\)) \(W\), the three values \(f\) takes on the faces in \(W\) are the smallest values that \(f\) takes on the topograph.

Proof: Using the labels from the well in the definition above, the Arithmetic Progression Rule for our differences gives
\[2\alpha = b + c - a, \quad 2\beta = c + a - b, \quad 2\gamma = a + b - c\]
and solving,
\[a = \beta + \gamma, \quad b = \alpha + \gamma, \quad c = \beta + \alpha.\]
Let the superbase \(W = \left\{e_1, e_2, e_3\right\}\). Since \(W\) is a superbase, we may write any vector as
\[v = m_1 e_1 + m_2 e_2 + m_3 e_3\]
for \(m_1\), \(m_2\), \(m_3 \in \mathbf{Z}\). Also due to the fact that \(W\) is a superbase, \(e_1 + e_2 + e_3 = (0, 0)\) and so we may also write
\[v = (m_1 - k) e_1 + (m_2 - k) e_2 + (m_3 - k) e_3\]
for \(k \in \mathbf{Z}\). From this it is clear only the differences of the \(m_i\) matter. With this as our inspiration we write
\[f(v) = \alpha(m_2 - m_3)^2 + \beta(m_1 - m_3)^2 + \gamma(m_1 - m_2)^2,\]
a formula discovered by Selling.

To verify this, notice both sides of the equation are quadratic forms in \(v\) and
\begin{align*}
f(e_1) = a &= \beta + \gamma = \alpha \cdot 0^2 + \beta \cdot 1^2 + \gamma \cdot 1^2 \\
f(e_2) = b &= \alpha + \gamma = \alpha \cdot 1^2 + \beta \cdot 0^2 + \gamma \cdot (-1)^2 \\
f(e_3) = c &= \beta + \alpha = \alpha \cdot (-1)^2 + \beta \cdot (-1)^2 + \gamma \cdot 0^2.
\end{align*}
hence they must be equal since both sides are quadratics that agree on more than two points.

If two of the \(m_i\) are equal, then \(v\) must be an integral multiple of the third vector, hence the value \(f(v)\) will be at least as large as the value of \(f\) on the third vector. If not, all the differences must be non--zero (hence greater than or equal to \(1\) in absolute value, since integers), thus
\[f(v) \geq \alpha \cdot 1^2 + \beta \cdot 1^2 + \gamma \cdot 1^2\]
which is greater than or equal to each of \(a = \beta + \gamma\), \(b = \alpha + \gamma\), and \(c = \beta + \alpha\) since all of \(\alpha\), \(\beta\), and \(\gamma\) are non--negative. \(\Box\)

Corollary: The topograph is connected; one may travel along the topograph from any given superbase to any other.

Proof: Using the same quadratic form \(f\) as we did to show the topograph had no cycles, we can show it is connected. Any arbitrary superbase is on the topograph, hence must be in some connected component of the topograph, but there may be more than one component. Since \(f\) is positive--valued, we must have some well in this component. But, by the above, the values at a well must be the absolute lowest values \(f\) takes on the topograph. This implies the well must take the values \(1\), \(1\), \(1\) and shows all superbases must be in the same component. \(\Box\)

From this point, we will concentrate on a special type of form relevant to our discussion. For a form \(f\) which takes both positive and negative values, but never \(0\), the topograph has a special path that separates the which separates the faces where takes a positive value and those where \(f\) takes a negative value.

Claim: If a form \(f\) takes both positive and negative values, but not zero, then there is a unique path of connected edges separating the positive and negative values. What's more, the values that occur on this river do so periodically.

Proof: Since the topograph is connected, there must be some edge where positive and negative values meet. As we proceed along adjacent edges, we can choose to follow a path of edges which will separate positive and negative (each subsequent value must be positive or negative, allowing us to "turn" left or right).

On first sight, there is no reason that this path should be unique. However, with the climbing lemma in mind, starting on the positive side of the path and moving away from the negative values, we must have only positive values. Using the logic of the climbing lemma instead with negative values, we similarly see that starting on the negative side and more away from the positive values will yield all negative numbers below the path. Hence nowhere above the path can positive and negative values meet and similarly below. Thus the path must be unique.

To show this path is periodic, we must utilize the discriminant. For each edge along the path, we have some positive value \(a\) and a negative \(b\) (by definition of the path) and the common difference \(h\). Thus the determinant \(D\) must be negative since the product \(ab\) is, hence
\[\left|D\right| = \left|ab\right| + \left(\frac{1}{2}h\right)^2.\]
Thus, both \(\left(\frac{1}{2}h\right)^2\) and \(\left|ab\right|\) are bounded by \(\left|D\right|\). So \(a\), \(b\) and \(h\) are bounded (by \(\left|D\right|\). Thus we have finitely many possible triples \((a, b, h)\), hence some value must be repeated in the path. This forces the path to be periodic since the triple starting from one triple \((a, b, h)\) determines next triple along the path and hence the entire path.

This path is so crucial that we give it it's own name.

Definition: If a form \(f\) takes both positive and negative values, but not zero, we call the path separating the positive and negative values the river. \(\Box\)

Thanks for reading, I'll make use of all this in a few days!

Update: This material is intentionally aimed at an intermediate (think college freshman/high school senior) audience. One can go deeper with it, and I'd love to get more technical off the post.

Update: All images were created with the tikz LaTeX library and can be compiled with native LaTeX if pgf is installed.
About Bossy Lobster

Conway's Topograph Part 2

This is the second (continued from Part 1) in a series of three blog posts. In the following we'll investigate a few properties of an object called Conway’s topograph. John Conway conjured up a way to understand a binary quadratic form – a very important algebraic object – in a geometric context. This is by no means original work, just my interpretation of some key points from his The Sensual (Quadratic) Form that I'll need for some other posts.

---

In the following, as mentioned in Part 1, "when referring to a base/superbase, we are referring to the lax equivalent of these notions."

To begin to form the topograph, note each superbase \(\left\{e_1, e_2, e_3\right\}\) contains only three bases
\[\left\{e_1, e_2\right\}, \left\{e_2, e_3\right\}, \left\{e_3, e_1\right\}\]
as subsets. Going the other direction, a base \(\left\{e_1, e_2\right\}\) can only possibly be contained as a subset of two superbases:
\[\langle e_1, e_2, (e_1 + e_2)\rangle, \langle e_1, e_2, (e_1 - e_2)\rangle.\]
With these two facts in hand, we can begin to form the geometric structure of the topograph. The interactions between bases and superbases (as well as the individual vectors themselves) give us the form. In the graph, we join each superbase (\(\bigcirc\)) to the three bases (\(\square\)) in it.

Each edge connecting two superbases (\(\bigcirc\)) represents a base and we mark each of these edges with a (\(\square\)) in the middle. Since each base can only be in two superbases, we have well--defined endpoints for each base (edge). Similarly, since each superbase contains three bases as subsets, each superbase (endpoint) has three bases (edges) coming out of it.

As we traverse each edge (base) surrounding a given vector (\(e_1\) above), we move from superbase (vertex) to superbase (vertex), and form a face. Starting from a base \(e_1, e_2\), traveling along each of the new faces encountered we begin to form the full (labeled) topograph below:

Notice the values of \(f\) on the combinations of \(e_1\) and \(e_2\) is immaterial to the above discussion, hence the shape of the topograph doesn't depend on \(f\).

If we know the values of \(f\) at some superbase, it is actually possibly to find the values of \(f\) at vectors (faces) we encounter on the topograph without actually knowing \(f\).

Claim: For vectors \(v_1, v_2\),
\[f(v_1 + v_2) + f(v_1 - v_2) = 2\left(f(v_1) + f(v_2)\right)\]
Proof: Exercise. (If you really can't get it, let me know in the comments.) \(\Box\)

This implies that if
\[a = f(v_1), \quad b = f(v_2), \quad c = f(v_1 + v_2), \quad d = f(v_1 - v_2)\]
then \(d\), \(a + b\), \(c\) form an arithmetic progression with common difference \(h\). This so--called Arithmetic Progression Rule allows us to mark each edge with a direction based on the value of \(h\). Hence if \(d < a + b < c\), we have \(h > 0\) and the following directed edge:

Obviously starting from a base \(e_1, e_2\), one wonders if it is possible to move to any pair \((x, y)\) with \(x\) and \(y\) coprime along the topograph. It turns out that we can; the topograph forms a structure called a tree, and all nodes are connected.

Lemma: (Climbing Lemma) Given a superbase \(Q\) with the surrounding faces taking values \(a\), \(b\), and \(c\) as below, if the \(a\), \(b\) and the common difference \(h\) are all positive, then \(c\) is positive and the other two edges at \(Q\) point away from \(Q\).

Proof: First \(c\) is positive because \(h = c - (a + b)\), hence \(c = a + b + h > 0\). The two other edges at \(Q\) have common differences \((a + c) - b\) and \((b + c) - a\). Since \(c = a + b + h\) is greater than both \(a\) and \(b\), these differences are positive. \(\Box\)

Notice also that this establishes two new triples \((a, a + b + h, 2 a + h)\) and \((b, a + b + h, 2 b + h)\) that continue to point away from each successive superbase and hence climb the topograph. We can use this lemma (along with a specific form) to show that there are no cycles in the topograph, i.e. the topograph doesn't loop back on itself.

Consider the form which takes the following values at a given superbase:

Due to the symmetry, we may consider traveling along an edge in any direction from this superbase identically. Picking an arbitrary direction, we reach the following superbase:

Since the values must increase indefinitely as laid out by the climbing lemma, the form can't loop back on itself; if it were to, it would need to loop back to a smaller value. Since this holds in all directions from the original well, there are no cycles.

Follow along to Part 3.

Update: This material is intentionally aimed at an intermediate (think college freshman/high school senior) audience. One can go deeper with it, and I'd love to get more technical off the post.

Update: All images were created with the tikz LaTeX library and can be compiled with native LaTeX if pgf is installed.
About Bossy Lobster

Conway's Topograph Part 1

This is the first in a series of three blog posts. In the following we'll investigate a few properties of an object called Conway’s topograph. John Conway conjured up a way to understand a binary quadratic form – a very important algebraic object – in a geometric context. This is by no means original work, just my interpretation of some key points from his The Sensual (Quadratic) Form that I'll need for some other posts.

---

Definition: A binary quadratic form \(f\) is an equation of the form:

\[f(x, y) = A x^2 + H x y + B y^2.\]

That is, a function of two variables which is homogeneous of degree two. The coefficients \(A\), \(H\), and \(B\) and variables \(x\) and \(y\) are often real numbers, rational numbers or integers. \(\Box\)

When we require the coefficients \(A\), \(H\), and \(B\) as well as the variables \(x, y\) to be integers, we get an integer--valued form. In his Disquisitiones Arithmeticae, Gauss asked (and largely answered) the fundamental question: what integer values can each form take? For example, you may have seen the form

\[f(x, y) = x^2 + y^2,\]

where it was determined that the only primes (Gaussian primes) occuring were \(2\) and those odd primes congruent to 1 modulo 4.

As each form \(f\) is homogenous degree two, \(f(\lambda x, \lambda y) = \lambda^2 f(x, y)\). As a result, if we can understand the values of \(f\) for pairs \((x, y)\) which don't share any factors, we can understand the entire set of values that \(f\) takes. Also, letting \(\lambda = -1\), there is no change in the value of \(f\) since \(\lambda^2 = 1\), hence it suffices to think of \(v = (x, y)\) as \(\pm v\), i.e. \(\left\{(x, y), (-x, -y)\right\}\).

For integers \(x\) and \(y\), any point \((x, y)\) can be expressed as an integral linear combination of the vectors \(e_1 = (1, 0)\) and \(e_2 = (0, 1)\). So if we like, we can express all relevant inputs for \(f\) in terms of two vectors. However, instead considering \(e_2 = (1, 1)\), we have

\[(x - y) \cdot e_1 + y \cdot e_2 = (x, y)\]

and realize a different pair \(e_1, e_2\) which again yield all possible integer valued vectors as integral linear combinations.

Definition: A strict base is an ordered pair \((e_1, e_2)\) whose integral linear combinations are exactly all vectors with integer coordinates. A lax base is a set \(\left\{\pm e_1, \pm e_2\right\}\) obtained from a strict base. \(\Box\)

Definition: A strict superbase is an ordered triple \((e_1, e_2, e_3)\), for which \(e_1 + e_2 + e_3 = (0, 0)\) and \((e_1, e_2)\) is a strict base (i.e., with strict vectors), and a lax superbase is a set \(\langle\pm e_1, \pm e_2, \pm e_3\rangle\) where \((e_1, e_2, e_3)\) is a strict superbase. \(\Box\)

For our (and Conway's) purposes, it is useful to consider the lax notions and leave the strict notions as an afterthought since a binary quadratic form is unchanged given a sign change. From here forward, for a vector \(v\), we use the notation \(v\) interchangeably with \(\pm v\) and when referring to a base/superbase, we are referring to the lax equivalent of these notions.

Follow along to Part 2.

Update: This material is intentionally aimed at an intermediate (think college freshman/high school senior) audience. One can go deeper with it, and I'd love to get more technical off the post.

About Bossy Lobster

Continued fraction expansions of irrational square roots

I had no idea (until this Thursday, July 16) that I had never seen a proof of the fact that the continued fraction expansion of \(\sqrt{D}\) is periodic whenever \(D\) is not a perfect square. But have no fear, I found out about something called a reduced quadratic irrational and now have a proof. Here we go.

Definition: An irrational root \(\alpha\) of a quadratic equation with integer coefficients is called reduced if \(\alpha > 1\) and its conjugate \(\tilde{\alpha}\) satisfies \(-1 < \tilde{\alpha} < 0\). \(\Box\)

Solutions (since assumed real) of such quadratics can be written as $$\alpha = \frac{\sqrt{D} + P}{Q}$$ where \(D, P, Q \in \mathbf{Z}\) and \(D, Q > 0\). It is also possible (though not required) to ensure that \(Q\) divides \(D - P^2\). This is actually a necessary assumption for some of the stuff I do, is mentioned here and generally frustrated the heck out of me, so that. As an example for some enlightenment, notice $$\alpha = \frac{2 + \sqrt{7}}{4}$$ is reduced but \(4\) does not divide \(7 - 2^2\). However, if we write this as \(\frac{8 + \sqrt{112}}{16}\), we have our desired condition.

Definition: We say a reduced quadratic irrational \(\alpha\) is associated to \(D\) if we can write $$\alpha = \frac{P + \sqrt{D}}{Q}$$ and \(Q\) divides \(D - P^2\). \(\Box\)


Lemma 1: Transforming a reduced irrational root \(\alpha\) associated to \(D\) into its integer part and fractional part via $$\alpha = \lfloor \alpha \rfloor + \frac{1}{\alpha'},$$ the resulting quadratic irrational \(\alpha'\) is reduced and associated to \(D\) as well. (This is what one does during continued fraction expansion, and as I did with \(\sqrt{2}\) during my last post.)

Proof: Letting $$\alpha = \frac{\sqrt{D} + P}{Q}$$ and \(X = \lfloor \alpha \rfloor\), we have $$\frac{1}{\alpha'} = \frac{\sqrt{D} - (QX - P)}{Q}.$$

• Since \(\sqrt{D}\) is irrational, we must have \(\frac{1}{\alpha'} > 0\) and since \(\frac{1}{\alpha'}\) is the fractional part we know $$0 < \frac{1}{\alpha'} < 1 \Rightarrow \alpha' > 1.$$ 
• Transforming $$\alpha' = \frac{Q}{\sqrt{D} - (QX - P)} \cdot \frac{\sqrt{D} + (QX - P)}{\sqrt{D} + (QX - P)} = \frac{\sqrt{D} + (QX - P)}{\frac{1}{Q}\left(D - (QX - P)^2\right)},$$ we have \(P' = QX - P\) and \(Q' = \frac{1}{Q}\left(D - (QX - P)^2\right)\) and need to show \(Q' \in \mathbf{Z}\). But \(D - (QX - P)^2 \equiv D - P^2 \bmod{Q}\) and since \(\alpha\) is associated to \(D\), \(Q\) must divide this quantity, hence \(Q'\) is an integer.
• Since \(X = \lfloor\frac{\sqrt{D} + P}{Q}\rfloor\) is an integer and \(\alpha\) is irrational, we know \(X < \frac{\sqrt{D} + P}{Q}\) hence \(P' = QX - P < \sqrt{D}\) forcing \(\tilde{\alpha}' < 0\).
• Since \(\alpha > 1\) we know \(X \geq 1 \Leftrightarrow 0 \leq X - 1\). Thus \begin{align*}\tilde{\alpha} = \frac{P - \sqrt{D}}{Q} &< 0 \leq X - 1 \\ \Rightarrow Q &< \sqrt{D} + (QX - P) \\ \Rightarrow Q(\sqrt{D} - (QX - P)) &< D - (QX - P)^2 \\ \Rightarrow -\tilde{\alpha}' = \frac{\sqrt{D} - (QX - P)}{\frac{1}{Q}\left(D - (QX - P)^2\right)} &< 1 \end{align*} hence \(\tilde{\alpha}' > -1\) and \(\alpha'\) is reduced.
• Since \(Q' = \frac{1}{Q}\left(D - (P')^2\right)\), we know $$D - (P')^2 \equiv Q Q' \equiv 0 \bmod{Q'}$$ hence \(\alpha'\) is associated to \(D\).

Thus \(\alpha'\) is both reduced and associated to \(D\). \(\Box\)


Lemma 2: There are finitely many reduced quadratic irrationals associated to a fixed \(D\).

Proof: As above write an arbitrary reduced irrational as \(\alpha = \frac{\sqrt{D} + P}{Q}\).  Since \(\alpha > 1\) and \(\tilde{\alpha} > -1\), we know \(\alpha + \tilde{\alpha} = \frac{2P}{Q} > 0\) hence with the assumption \(Q > 0\) we have \(P > 0\). Since \(\tilde{\alpha} < 0\) we also have \(P < \sqrt{D}\). Also, since \(\alpha > 1\) by assumption we have \(Q < P + \sqrt{D} < 2\sqrt{D}\) thus there are finitely many choices for both \(P\) and \(Q\), forcing finitely many reduced quadratic irrationals associated to a fixed \(D\) (this amount is strictly bounded above by \(2D\)). \(\Box\)

Claim: The continued fraction expansion of \(\sqrt{D}\) is periodic whenever \(D\) is not a perfect square.

Proof: We'll use Lemma 1 to establish a series of reduced quadratic irrationals associated to \(D\) and then use Lemma 2 to assert this series must repeat (hence be periodic) due to the finite number of such irrationals.

Write \(a_0 = \lfloor \sqrt{D} \rfloor\) and \(\sqrt{D} = a_0 + \frac{1}{\alpha_0}\). From here, we will prove

• \(\alpha_0\) is a reduced quadratic irrational associated to \(D\).
• By defining \(a_{i+1} = \lfloor \alpha_i \rfloor\) and \(\alpha_i = a_{i + 1} + \frac{1}{\alpha_{i + 1}}\), \(\alpha_{i + 1}\) is also a reduced quadratic irrational associated to \(D\) (assuming all \(\alpha\) up until \(i\) are as well).

Since \(\frac{1}{\alpha_0}\) is the fractional part of the irrational \(\sqrt{D}\), we have $$0 < \frac{1}{\alpha_0} < 1 \Rightarrow \alpha_0 > 1.$$ By simple algebra, we have $$\alpha_0 = \frac{a_0 + \sqrt{D}}{D - a_0^2}, \qquad \tilde{\alpha_0} = \frac{a_0 - \sqrt{D}}{D - a_0^2}.$$ Since \(a_0\) is the floor, we know \(a_0 - \sqrt{D} < 0 \Rightarrow \tilde{\alpha_0} < 0\). Since \(D \in \mathbf{Z} \Rightarrow \sqrt{D} > 1\) and \(\sqrt{D} > a_0\), we have $$1 < \sqrt{D} + a_0 \Rightarrow \sqrt{D} - a_0 < D - a_0^2 \Rightarrow a_0 - \sqrt{D} > -(D - a_0^2) \Rightarrow \tilde{\alpha_0} > -1.$$ Thus \(\alpha_0\) is a reduced quadratic irrational. Since \(P_0 = a_0\) and \(Q_0 = D - a_0^2 = D - P_0^2\), \(Q_0\) clearly divides \(D - P_0^2\) so \(\alpha_0\) is associated to \(D\) as well.

Following the recurrence defined, since each \(\alpha_i\) is a reduced quadratic irrational, each \(a_i \geq 1\). Also, by Lemma 1, each \(\alpha_{i + 1}\) is reduced and associated to \(D\) since \(\alpha_0\) is. By Lemma 2, we only have finitely many choices for these, hence there must be some smallest \(k\) for which \(\alpha_k = \alpha_0\). Since \(\alpha_{i + 1}\) is determined completely by \(\alpha_i\) we will then have \(\alpha_{k + j} = \alpha_j\) for all \(j > 0\), hence the \(\alpha_i\) are periodic. Similarly, as the \(a_i\) for \(i > 0\) are determined completely by \(\alpha_{i - 1}\), the \(a_i\) must be periodic as well, forcing the continued fraction expansion $$\sqrt{D} = a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \ddots}}$$ to be periodic.\(\Box\)

Update: I posted this on
About Bossy Lobster

Continued Fractions for the Greater Good part 1

OK, maybe not for the greater good, but still fun. This first post will be relatively short and sweet, intended to give an introduction for the posts that will follow.

Before the introduction, some motivation courtesy of Wikipedia:

“...decimal representation has some problems. One problem is that many rational numbers lack finite representations in this system. For example, the number \(\frac{1}{3}\) is represented by the infinite sequence \((0, 3, 3, 3, 3, \ldots )\). Another problem is that the constant \(10\) is an essentially arbitrary choice, and one which biases the resulting representation toward numbers that have some relation to the integer \(10\). For example, \(\frac{137}{1600}\) has a finite decimal representation, while \(\frac{1}{3}\) does not, not because \(\frac{137}{1600}\) is simpler than \(\frac{1}{3}\), but because \(1600\) happens to divide a power of \(10\) (\(10^6 = 1600 \times 625\)). Continued fraction notation is a representation of the real numbers that avoids both these problems. Let us consider how we might describe a number like \(\frac{415}{93}\), which is around \(4.4624\). This is approximately \(4\). Actually it is a little bit more than \(4\), about \(4 + \frac{1}{2}\). But the \(2\) in the denominator is not correct; the correct denominator is a little bit more than \(2\)  about \(2 + \frac{1}{6}\), so \(\frac{415}{93}\) is approximately $$4 + \cfrac{1}{2+\cfrac{1}{6}}.$$ But the \(6\) in the denominator is not correct; the correct denominator is a little bit more than \(6\), actually \(6+\frac{1}{7}\). So \(\frac{415}{93}\) is actually $$4 + \cfrac{1}{2+\cfrac{1}{6 + \cfrac{1}{7}}}.$$ This is exact...”

With this in mind, one can define an infinite continued fraction to be $$a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \ddots}}.$$ With the denominators \(a_0, a_1, a_2, \ldots\), we can define a recurrence for the finite approximations (convergents) of this value. For example, the zeroth is \(a_0\) and the first is \(a_0 + \frac{1}{a_1} = \frac{a_0 a_1 + 1}{a_1}\).

The other motivation (the one I actually learned first in real life) for continued fractions comes from \(\sqrt{2}\) being represented by an infinite continued fraction. (Instead of saying a probability of \(0.01876\), people would rather say a \(1\) in \(53\) chance.) So we try to write \(\sqrt{2} = 1.41421356\ldots\) as \(1 + \frac{1}{2.414}\). But, instead, notice that $$\sqrt{2} = 1 + (\sqrt{2} - 1) = 1 + \frac{1}{\sqrt{2} + 1}.$$ Plugging this into itself, we have $$\sqrt{2} = 1 + \cfrac{1}{1 + 1 + \cfrac{1}{\sqrt{2} + 1}} = 1 + \cfrac{1}{1 + 1 + \cfrac{1}{1 + 1 + \cfrac{1}{\sqrt{2} + 1}}}$$ and notice it can be represented by \((1; 2, 2, 2, \ldots)\).

Define the \(n\)th convergent to be \(\frac{h_n}{k_n}\), so above we have \(h_0 = a_0, k_0 = 1\) and \(h_1 = a_0 a_1 + 1, k_0 = a_1\).

Claim: \(h_n\) and \(k_n\) satisfy \begin{align*}h_n &= a_n h_{n - 1} + h_{n - 2} \\ k_n &= a_n k_{n - 1} + k_{n - 2} \end{align*} along with \(h_{-1} = 1, h_{-2} = 0\) and \(k_{-1} = 0, k_{-2} = 1\).

Proof: The fraction \(\frac{h_n}{k_n}\) is converted into \(\frac{h_{n + 1}}{k_{n + 1}}\) simply by changing \(a_n\) to \(a_n + \frac{1}{a_{n + 1}}\) in the final denominator. Since $$\frac{h_n}{k_n} = \frac{a_n h_{n - 1} + h_{n - 2}}{a_n k_{n - 1} + k_{n - 2}}$$ we similarly have \begin{align*} \frac{h_{n + 1}}{k_{n + 1}} &= \frac{\left(a_n + \frac{1}{a_{n + 1}}\right) h_{n - 1} + h_{n - 2}}{\left(a_n + \frac{1}{a_{n + 1}}\right) k_{n - 1} + k_{n - 2}} \\ &= \frac{a_{n + 1}(a_n h_{n - 1} + h_{n - 2}) + h_{n - 1}}{a_{n + 1}(a_n k_{n - 1} + k_{n - 2}) + k_{n - 1}} \\ &= \frac{a_{n + 1} h_n + h_{n - 1}}{a_{n + 1} k_n + k_{n - 1}}\end{align*}
Thus \(h_{n + 1}\) and \(k_{n + 1}\) satisfy the same recurrence.

It remains to check the initial conditions work, but note \begin{align*}h_0 &= a_0 h_{-1} + h_{-2} = a_0 \cdot 1 + 0 = a_0 \\ k_0 &= a_0 k_{-1} + k_{-2} = a_0 \cdot 0 + 1 = 1\end{align*} and \begin{align*}h_1 &= a_1 h_{0} + h_{-1} = a_0 a_1 + 1 \\ k_1 &= a_1 k_{0} + k_{-1} = a_1 \cdot 1 + 0 = a_1\end{align*} as we checked above.  \(\Box\)

Check out my next post, where I actually accomplish something with fractions (or at least prepare to accomplish something).

About Bossy Lobster