Review of "Gödel, Escher, Bach"

"It seems to me that you may begin approaching Zen through any path you know—even if it completely antithetical to Zen. As you approach it, you gradually learn to stray from that path. The more you stray from the path, the closer you get to Zen."

-- Achilles to the Tortoise 

* * *

Where to begin? This is a monstrous book, unlike anything I've read before—the right and proper Compendious Book, I think. I am convinced there is exactly one man in the world who could have written it, because the idea of a 700-page unraveling of the principles behind Gödel's Incompleteness Theorem, that approaches its destination, by turns, from the twisted fancies of Escher's illusionism, from the folds and turns of Baroque music, from the ripples of Zen Buddhist thought, from the manic episodes of an everlasting comic strip in prose, and from the inhospitable acres of formal logic, and all in a book intended for general audiences, is an idea that should not have occurred to any person on this good earth.

And yet there is Douglas Hofstadter.

Half the difficulty of explaining the book comes from even describing the format. Essentially, what we have are alternating chapters of fiction and non-fiction. Two of Hofstadter's characters—the Tortoise and Achilles, from Zeno's paradoxical footrace—go on merry adventures and share witty repartee that in some way will frame all the mathematical ideas Hofstadter wishes to introduce in the upcoming chapter.

To make this all clearer, I'll explain one such pairing in unusual detail. For me, one of the highlights of the book was a chapter called "Little Harmonic Labyrinth," where the Tortoise and Achilles traverse multiple levels of story within a story. The chapter begins ominously as the duo are trapped in the kitchen of the hungry giant Goodfortune (level 1). To pass the time, they begin reading a story, deciding to roleplay as the characters therein (level 2). But this story itself has an internal story, and so on. Keeping track of the "true" level of meaning becomes increasingly difficult as the narration "pushes" and "pops" from level to level, until at the end we are hopelessly disoriented. The chapter ends happily with an amicable parting of the heroes... but at what level? The observant reader (or perhaps the one who has been drawing a diagram?) will realize, to his dismay, that only level 2 of the story was concluded happily, which leaves the real Achilles and Tortoise still trapped in the giant's lair. The discord between the "happy ending" and this anxious realization is more unnerving than I can describe.

All this is a precursor to Hofstadter's formal introduction of the idea of recursivity. And yet even then he does not immediately proceed to the mathematical idea, but first draws parallels from classical music (by some marvel of the mind, we listeners manage to keep organized multiple levels of meaning at once, distinguishing ordinary chord progressions from a key change) and language (we dive in and out of prepositional phrases, appositions, and subclauses, sometimes all nested within one another). All this is preparation for the mathematical concept, and by the time the reader hits A_n = A_n-1 + etc., he is more than ready for it; he understands intuitively the positive need for such an idea. Never will a subject that's been given the Hofstadter treatment seem an airy abstraction or a sterile formula; to say Hofstadter gives mathematical concepts connotations is not enough, because he gives them personalities!

Recursion may have been the particular province of the two chapters I just described, but in many ways, it is the fundamental theme of the book. What unites all the far-flung influences that Hofstadter manages to invite into his book is the idea of "strange loops." Escher's recursive hands, Bach's self-canny fugues... There is an absolutely thrilling discussion of that crown jewel of recursivity, Russell's Paradox, and the searing unnaturalness of any attempt to solve it by prohibiting self-reference (Russell's theory of types). Late in the book, there is an extended discussion of the prospects of artificial intelligence. Hofstadter's threshold, if I had to define it for him, is that a brain (or machine) gets marked apart as "intelligent" once it becomes self-aware. I think this also explains why Hofstadter brings in Zen as an intellectual counterpoint, because enlightenment is often described as a sublimation into non-self-awareness. The Zen monk's eureka moment could be described, "I think not, therefore I am not."

This is not a book for everyone. No one would call it light reading; a paragraph of text usually demands about a paragraph of thought. Often enough this book calls for having a pen and paper next to you, and that's without any note-taking requirement! However, I found the effort well worth it, as this is intellectual stimulation of the first rate, so I would certainly recommend it to anyone who's looking for such a thing and has time on his or her hands.

Review of "Radical Equations"

I choose this book because of my interest in the Civil Rights movement, and it did not disappoint. Robert "Bob" Moses can truly claim to have walked the walk, as he played a crucial role in organizing the suffrage movement in Mississippi. Considering the beatings, arrests, and threats he received along the way, it's remarkable enough that the man is around to tell his story. What's more amazing still is that in his own lifetime, he's seen his "extreme" position of equal rights become the only respectable one, and seen himself become an elder statesman of the movement. (Truly, the still-continuing march from slavery towards equality must be the most inspiring story American history has to offer; maybe even world history.)

Now, however, Dr. Moses has shifted his campaign for equality to a different venue indeed. Just as a vote is the gateway to democratic citizenship and equality with one's political peers, Moses views mathematical literacy as the gateway to "economic citizenship" for today's black Americans. Mastery of algebra is an essential gateway to college, increasingly seen as the only path to a middle-class lifestyle.

Throughout, Dr. Moses draws parallels with the travails of the Civil Rights movement. What Moses is trying to effect in the schools where he mentors is nothing less than a culture change. He invites the reader to ask, "How can we change a community's way of thinking about things; make it reconsider what is collectively possible; and how do we motivate people to go ahead and take action?" It sometimes seems that every struggle Bob Moses ever fought, from Mississippi to middle schools, is about shifting the Overton window of possible outcomes. It's striking how much energy it took to mobilize blacks themselves to take ownership of their birthright as American citizens to cast a ballot. Too many lived in a state of resignation to their station. Moses wants the middle school students to rise up and demand what is theirs as well—in a sense. He unabashedly uses the language of the '60s with the students: competency in school, and especially math, is a right. When he first introduces the Algebra Project to a new school, Moses tries to juice enthusiasm by talking about the program as a privilege.

To win converts to this view, Moses first sees the need to rototill over the students' already packed-down impressions of math. As the first lesson of every Algebra Project classroom, he organizes an extravaganza: a field trip outside into the city (on public transportation if possible), which at first seems to have implausibly little to do with math. This trip (which many school administrators met with skepticism—more on that later) serves two functions. First, it marks a violent break with whatever prior experience students have had with the subject. When riding the T is math class, you know math is not going to be the same as before. Second, Moses uses the idea of motion towards or from a physical goal as the most natural and relevant jumping-off point for middle schoolers to understand the basic concepts of algebra. As a teacher, Moses is able to mine weeks worth of curricula from that single experience: from operations with negative numbers, to distance over time, to rates of change (and therefore the all-important idea of slope).

It's actually something of a pity that Moses doesn't venture more into the nuts and bolts of how he teaches. His overall method is pretty clear, and there are a few representative stories about students learning, but I would have loved just a single chapter that narrated on a minute-by-minute basis how he runs his class. Oh well, I suppose pre-service teachers can't have been expected to be the target audience.

What Moses does spend quite a bit of time on is the organizational side; how to win over dubious teachers, how to mobilize parents, how to build consensus. One gets the sense that for all the love of what he does in the classroom, Dr. Moses is still a community organizer at heart. Since his algebra agenda is a totalizing project and essentially mutually exclusive with the traditional curriculum, there was no doubt it would have its doubters. In a way, you might say the amount of resistance he faces is surprisingly low.  The biggest stumbling blocks have been teachers (often the minority on a team whose majority voted to adopt the Project) who feel uncomfortable with Moses's self-discovery model of education, and administrators who fear the program could hinder the schools' test scores, or raise difficulties when paperwork time comes and state standards must be met.

Parents, on the other hand, seem to have been Dr. Moses's eagerest allies. It seems that for all those parents who do not understand or even fear algebra, they decidedly want their own children to learn it if given a choice. Above all, Moses sells parents on the idea that mathematical literacy is the pathway from poverty to independence. Moses relates the story of one New York City school where he rallied dozens of students and teachers to demand a more advanced math be offered, only to realize that he had been so successful that the school could not offer nearly enough sections of the class to meet demand.

Such popularizing is well within Moses's broader goals. He refers to mathematics as it was once practiced as a "high priesthood" that could select with care only those with unusual talent and interest. Today, he feels, mathematics must be democratized. Why, he asks, do parents feel they can volunteer with reasonable confidence to look over their child's essay, but confess inability—sometimes proud inability—when it comes to junior's math homework?

In all, this was an easy read on an important topic by a man whose words command respect. I would enthusiastically recommend Dr. Moses's book.

Deriving the Cubic Formula Part II: Solving a Depressed Cubic [communicating in math]

Although we're continuing from our work last time, we'll start afresh (i.e., variables aren't going to retain their meanings from last time) with a generic depressed cubic of the form

y = x³ + cx + d

The overarching goal here is to wind up with a quadratic equation so that we can revert to the familiar Quadratic Formula.

In this step, we're all but forced to use an early substitution. Much as I would love to accomplish the "respelling" by just factoring our starting variables (and it can be done), it's just too complicated to be bothered with (at one point, you have to complete, not the square, not the cube, but a binomial taken to the sixth power). If you're at all interested in how the algebra works, though, you can click through to this Desmos graph

https://www.desmos.com/calculator/dxik7vhi7v

where equations 17 through 9 (reading upwards) are the same function respelled over and over.

But that's really not worth it, so we'll just use a substitution. Here we're actually departing from what Cardano did in favor of a much simpler method by Vieta. We let

plug things in, and expand and simplify as below:

This last line doesn't look like a quadratic equation, but it is. Remember, we're only interested in the roots of our depressed cubic formula, which means we can set y = 0 and multiply both sides by z:

Indisputably a quadratic, so we apply the Quadratic Formula:

At this point, you might think we could plug z back into x and be done, which would make our Depressed Cubic Formula look like this:

That's mostly correct, but there is a major complication. A cubic ought to have three roots; here the plus/minus sign would seem to give us two of those, but the third one is unavailing...

Well, this isn't actually a well known fact (I didn't realize it myself until I started studying the Cubic Formula), but a square root isn't the only single-input expression with more than one output. It turns out that a cube root has three solutions, a fourth root has four solutions, and so on. Let's take 1^(1/3). Obviously, 1 is a root, but so too are –1/2 + (3^(1/2)/2)i

and its complex conjugate, –1/2 – (3^(1/2)/2)i

In fact, the three roots are perfectly spaced on an equilateral triangle inscribed in the unit circle on the complex plane.

(As it turns out, any nth roots have this remarkable property of sitting at the points of an n-gon on the complex plane.) This is fortunate, because it means that if we have only one root of z^(1/3), we can use trigonometry to find the other two.

So this, and not the plus/minus sign from the Quadratic Formula (which ends up cancelling itself out in the course of things), is what gives us three roots to each cubic.

Let's try an example. Find the zeros of

y = x³ – 15x + 4

First we'll find z as defined in the substitution above:

Then with a lot of tedious trig (not included because it's not really the point of this exercise), the three cube roots of z:

Finally, plug each in to find the three solutions for x. I'll write out the first listed just to show how the plus/minus sign ends up not mattering in the end:

I promise the other two work too, but I'm not writing out all those radicals! Those roots turn out to be 2 + 3^(1/2) and 2 – 3^(1/2).

That was an amazing amount of work to find the exact values of those roots, and remember, that's when we start with a depressed cubic. The actual cubic formula combines the steps in these two blog posts, which means just substituting one substitution into the other. It's nothing special once you've seen all the work along the way.

I'm glad to say I understand the derivation of this formula. I still think I'll stick to Newton's Method next time though.

Deriving the Cubic Formula Part I: Depressing the Cubic [communicating in math]

I spent some time trying to come to grips with the derivation of the cubic formula. I was surprised to discover that all the algebra involved is elementary — at the most, a student who succeeded in Alegbra II should be able to understand the steps involved (leaving aside the imaginary numbers when it comes to actually finding the roots — but oh well, Cardano himself didn't understand them), but most of the procedures are unintuitive; it would be unclear to an observer just why we take this step or that substitution.

I'll try to hit on all the major concepts, and lay out the derivation in such a way that (hopefully) it can be followed by someone who doesn't understand the process yet.

The first thing to know is that solving a cubic is practically two separate problems. First (and this is the easier of the two steps), we use some clever factoring to "respell" our cubic so it has no x² term. When we do this we are said to be depressing the cubic. The reason this is a desirable thing to do will become clear in the next blog post; for now, just assume that our end goal is some equation of the form

y = x³ + cx + d

We'll begin, however, with a cubic equation of the form,

y = x³ + bx² + cx + d

If the x³ term has a coefficient other than 1, say, a, it's much simpler to divide the entire polynomial by a and then take that result as your cubic to be solved.

Now, the strategy for eliminating that bx² term relies on "completing the cube." One thing to which we'll recur multiple times is the Binomial Theorem, especially the expansion of a cubed binomial. Just to put it out there in eyesight,

(x + b)³ = x³ + 3bx² + 3b²x +b³

Better still for our purposes,

(x + b/3)³ = x³ + bx² + b²x/3 +b³/27

In other words, we can dispose of that bx² term by folding it into a cubed binomial. To complete the cube, we add and subtract b²x/3 +b³/27 from the cubic and follow through as below. The substitution with z at the end is just to better showcase the underlying nature of the depressed cubic with which we're left.

Note that there is also a way to depress the cubic by beginning with a substitution. We can let x = (z – b/3) and simplify, which makes the algebra easier, but, in my opinion, seems to come out of nowhere and obscures the underlying logic of what is going on. Here it is though:

Either way, we have our depressed cubic and are ready to proceed to Part II.

Geodesics in taxicab geometry

I was interested in the taxicab geometry from class, so I decided to examine one particular problem. Suppose you are on one corner of a city whose streets form a perfect grid, and you wish to reach the opposite corner in the shortest possible distance. How many possible paths can you take? More abstractly, how many geodesics are there in a taxicab geometry grid of a given size?

It turns out that there is a very elegant formula to find the answer; as I discovered, in a city with c × n blocks, there are exactly

geodesics between opposite corners.

My goal here will be to document my personal "discovery process" for this remarkable little formula, rather than arrive at it in the most logical or efficient way.

So, my first step was to realize that any size grid can be broken into smaller grids. When the traveler begins in the corner of a c × n grid, he can take only one of two paths.

Either way, after one step, he finds himself on a "new" grid of size (c – 1) × n or c × (n – 1). The number of possible geodesics in the old grid, which I notate A_c,n, is equal to the sum of the number of possibilities in each of the two smaller grids. In other words,

A_c,n = A_c-1,n + A_c,n–1

The other thing to know is that any grid with a dimension 0 automatically has only one geodesic—a single path from end to end.

So, we can begin constructing some grids and seeing what patterns emerge. With a 1 × 1 grid, it should be fairly obvious by intuition that there are two paths:

but let's use the formula nonetheless:

A_1,1 = A_0,1 + A_1,o = 1 + 1 = 2.

For a 1 × 2 grid, we would imagine there are three geodesics:

A_1,2 = A_0,2 + A_1,1 = 1 + 2 = 3.

In fact, it very quickly becomes clear that for any 1 × n grid, there are

A_1,n = (n + 1)

geodesics. So far, so good. Now let's calculate the geodesics in some 2 × n grids:

A_2,2 = A_1,2 + A_2,1 = 3 + 3 = 6

A_2,3 = A_1,3 + A_2,2 = 4 + 6 = 10

A_2,4 = A_1,4 + A_2,3 = 5 + 10 = 15

A_2,5 = A_1,5 + A_2,4 = 6 + 15 = 21

A_2,6 = A_1,6 + A_2,5 = 7 + 21 = 28

This is a familiar pattern; in a grid size 2 × n, we are summing the integers from 1 to (n + 1). We know the formula for this behavior:

A_2,n = (n + 1)(n + 2)/2

It's probably too early to generalize from these two formulae so far, so let's keep gathering results.

Number of geodesics in a grid with the given dimensions (dimensions are commutative)

It's quite easy once we recognize that each number is the sum of the squares to above and to the left.

Since the differences between the values in a given row are determined by the row above, the direct formula for each row should be a higher-degree polynomial than the row above. I.e., row 1 is linear, row 2 quadratic, row 3 cubic, row 4 quartic, etc. I plugged the values for row 3 into my calculator for a cubic regression and found the roots:

Well, that's surely curious. Each time we've increased c by 1, we've multiplied that row's direct formula by (n + c)/c. That seems to suggest that any general formula would be of the form

A_c,n = (1/c!) ⋅ ((n + 1)(n + 2)(n + 3) ⋅ … ⋅ (n + c))

= (1/c!) ⋅ ((n + c)!/n!)

= (c + n)!/(c!n!)

which makes intuitive sense, since it's clear from this formula that n and c are indeed interchangeable, making the dimensions of a grid commutative.

Let's try one example: a 5 × 7 grid. From the formula,

A_5,7 = (5 + 7)!/(5!7!)

         = 12!/(5!7!)

         = 792

I'll decline to draw 792 paths on a grid, but you can glance up the page to see that this is indeed the number of paths we have in the table, which was constructed by sound methods.

Apart from being extremely simple and easy to use, this formula is a nice reminder that even the explosive factorial function is just repeated addition. Everything in the chart, up to the daunting 184756 paths in a 10 × 10 grid, comes from adding single digit numbers. 

More Desmos: Secants in polar

I figured I'd try to graph some n-gons in polar. I remembered that I had once discovered that the secant function in polar is vertical line, so that seemed like the best place to start.

Furthermore, with a modulo function we can break the graph into several discrete parts. In the equation below, the graph will have a "arms" for any integer a > 2.

(The coefficient 6 is only there in front to enlarge the graph.) Here is an example where a = 6:

Combine the modulo function with the secant function to "straighten" out the graph, and we get a disjoint line segments:

Finally, by shifting θ back by π/a units, we make the graph continuous. We use a = 6 once again to get a hexagon.

Here is link to the file if you'd like to experiment with other values of a. 
https://www.desmos.com/calculator/fwkuzx2fhn

Incidentally, some non-integer values of a yield coherent shapes too. For example, when a is a fraction with an odd numerator and denominator 2, the graph is a star with as many points as the value of the numerator. E.g., we get the standard 5-pointed star with a = 5/2:

* * *

Finally (and this one was absurdly challenging), I decided to graph a Swiss cross in polar. I should note that at this time I noticed that Desmos would accept τ as equivalent to 2π. How subversive! So from here on, I'm using τ in my equations.

So for the cross's 16 sides, we need 16 line segments... and they have to slope upwards not just individually, but in groups of four. Here's what I'm talking about, graphed on a standard Cartesian plane so it's clearer to understand what's going on:

Here's the secant of the above, back in polar.

The absolute value isn't strictly necessary (you get the same graph without it), but it forces our function to finish drawing in each quadrant before moving on to the next. Or, to say it another way, only with the absolute value will we be able to draw the finished cross without picking up our pencil from the paper.

The obvious problem is that from here we need to expand the north/south/east/west edges, i.e. everything in domain 3τ/16 < θ < τ/16 (mod τ/4), if you'll pardon the odd notation. Meanwhile, we have to contract four interior corners, i.e. domain τ/16 < θ < 3τ/16 (mod τ/4). So we'll multiply by the following

which looks like this:

The product of the two functions is a perfect Swiss cross.

If you're curious, here's what it looks like as function of x and y instead:

One more thing... in the course of making the cross, I accidentally figured out how to make a nice Bolnisi cross. I won't walk through the procedure for that one, but here's the equation and a graph.

Here's the link to this set of graphs: https://www.desmos.com/calculator/hufxpvk43q

One feature I added is a slider for b, a phantom variable that just lets you see the graph draw itself as θ goes from 0 to τ (like on a graphing calculator).