A few words about PWW #30

A few things about the images in my previous post that you may or may not have noticed:

  • As several commenters figured out, the nth diagram (starting with n = 1) is showing every possible subset a set of n items. Two subsets are connected by an edge when they differ by exactly one element.
  • All subsets with the same number of elements are aligned horizontally.
  • Each diagram is made of two copies of the previous diagram—one verbatim, and one with a new extra element added to every subset, with edges connecting corresponding subsets in the two copies. Do you see why this makes sense? (Hint: if we want to list all subsets of a set, we can pick a particular element and break them into two groups, one consisting of subsets which contain that element and one consisting of subsets which don’t.)
  • As commenter Denis pointed out, each diagram is a hypercube: the first one is a line (a 1-dimensional “cube”), the second is a square, the third is a cube, then a 4D hypercube, and so on. (On my own computer I rendered them up to n=8 but it gets very hard to see what’s going on after 5.)
  • Each subset can also be seen as corresponding to a bitstring specifying which elements are in the set. A dot corresponds to a 1, and an empty slot to a 0. So another way to think of this is the graph of all bitstrings of length n, where two bitstrings are connected by an edge if they differ in exactly one bit.
  • Thinking of it as bitstrings makes it clearer why we get hypercubes: each bit corresponds to a dimension. So for example for the 3D case you could think of the three bits as corresponding to back/front, left/right, and down/up.
  • I drew something similar to this many years ago, in Post without words #2. The big difference is that it recently occurred to me how to lay out the nodes recursively to highlight the hypercube structure, so they don’t all just smoosh together on each line.
  • There was actually some interesting math involved in figuring out the horizontal offsets to use for the subset nodes; perhaps I’ll write about that in another post!
Posted in posts without words | Tagged , , , , , , , | 4 Comments

Post without words #30

Image | Posted on by | Tagged , , , , , , , | 5 Comments

The First Six Books of the Elements of Euclid, by Oliver Byrne (Taschen)

Recently for my birthday I received a copy of Oliver Byrne’s 1847 edition of Euclid’s Elements (pictured at right), republished by Taschen Books in 2010. I’ve only just started reading it, but it’s beautiful and fascinating. Oliver Byrne was a 19th-century civil engineer and mathematician, best known nowadays for this incredible “color-coded” edition of Euclid. Euclid’s Elements, of course, is the most successful and influential mathematics textbook of all time, widely used as a geometry textbook even up into early 1900’s. Nowadays hardly anyone reads the Elements itself, but its content and style is still widely emulated. In 1847, Oliver Byrne decided to make an English edition of the Elements that not only used colored illustrations, but actually used color-coded pictures of lines, angles, and so on, inline in the text itself to refer to the picture instead of using the traditional points labelled by letters (see the example below). I can’t imagine how much work went into designing and printing this in the mid-1800s. I guess there would have to be four engraved plates for every single page? In any case, it’s beautiful, creative, and surprisingly effective. I spent a while last night going through some of the propositions and their proofs with my 8-year-old son—I highly doubt he would have been interested or able to follow a traditional edition that used letters to refer to labelled points in a diagram.

It’s also surprisingly inexpensive—only $20! You can get a copy through Taschen’s website here.

In a similar vein, the publisher Kronecker Wallis decided to finish what Byrne started, creating a beautifully designed, artistic version of all 13 books of Euclid. (Byrne only did the first six books; I am actually not sure whether because that’s all he intended to do, or because that’s all he got around to.) Someday I would love to own a copy, but it costs 200€ (!) so I think I’m going to wait a bit…

Posted in books, geometry, pictures | Tagged , , , , , , | 3 Comments

do go no to

do go on
do no harm
do to others
go do likewise
go-go music
go no further
goto considered harmful
no can do
it’s a no go
a big no-no
say no to drugs
what to do
here or to go
to no avail
I don’t think we’re in Kansas anymore, Toto

English is strange.

Posted in counting, humor | Tagged , ,

Book review: Tales of Impossibility

[Disclosure of Material Connection: Princeton Press kindly provided me with a free review copy of this book. I was not required to write a positive review. The opinions expressed are my own.]

Tales of Impossibility: The 2000-Year Quest to Solve the Mathematical Problems of Antiquity
David S. Richeson
Princeton University Press, 2019

Let me get right to the point: this was hands-down my favorite math book that I read this year. If you don’t already have a copy, you should stop reading this post right now and go buy one! Go on, you’ll thank me. Need more convincing? Read on.

The book is focused around the four “problems of antiquity”: squaring the circle (i.e. constructing a square with the same area as a given circle), angle trisection, doubling the cube (constructing the side length of a cube double the volume of a given cube), and constructing regular n-gons. The “problem” of each is to carry out the required construction using only a compass and straightedge (a set of tools that is probably familiar to most readers from some point in their mathematical education). As Richeson so ably relates, these problems inspired all sorts of advances in mathematics over thousands of years—even though (because?) all were eventually proved impossible in general: Wantzel (angle trisection, doubling the cube, regular n-gons) and Lindemann (squaring the circle) gave the final, definitive proofs, but both built on top of a great deal of mathematics that came before them. Each new player in the story added layer upon layer of understanding over thousands of years.

First and foremost, I am amazed at the incredible amount of historical and mathematical background research that Richeson obviously did for this book, and the way he intertwines mathematics and history into a compelling story. Stereotypically, a book of mathematical history runs a double risk of being dry: too much unmotivated historical or mathematical detail can put anyone to sleep. Richeson deftly avoids this trap, and his book exudes human warmth. But it doesn’t skimp on details either; I learned a great deal of both history and mathematics. In many cases (such as with many of the purely geometric arguments) proofs are included in full detail. In other cases (such as in the discussion of irreducible polynomials), some mathematical details are omitted. Richeson has a good nose for sniffing out the most elegant way to present a proof, and also for knowing when to omit things that would bog down the story too much.

Alternating with the “regular” chapters, Richeson includes a number of “tangents”, each one a short, fascinating glimpse into some topic which is related to the previous chapter but isn’t strictly necessary for driving the story forward (e.g. toothpick constructions, Crockett Johnson, origami, the Indiana pi bill, computing digits of pi, the tau vs pi debate, etc.). Even though none of them are strictly necessary, taken as a whole these “tangent” chapters do a lot to round out the story and give a fuller sense of the many explorations inspired by the problems of antiquity.

In addition to the many mathematical and historical details I learned from the book, I also took away a more fundamental insight. I had always thought of “compass and straightedge” constructions as being rather arbitrary: these are the tools the Greeks happened to choose, and so now we are stuck in a rut of thinking about geometrical constructions using these tools—or so I thought. However, it turns out that they are not quite so arbitrary after all: there are many different sets of tools that lead to exactly the same set of constructible things (there is even some interesting history here, as mathematicians figured out what it should even mean to say that you can “construct the same things” with different tools, leading to definitions of constructible points and constructible numbers). For example, toothpicks, a straightedge and “rusty” compass, a straightedge and a single circle, a compass by itself, or a “thick” straightedge by itself (with two given starting points), all can perform exactly the same set of constructions as a traditional straightedge and compass. And as we learned in later centuries, the constructible numbers have a nice algebraic characterization as well: a point (x,y) is constructible with straightedge and compass if and only if x and y can be described using the four arithmetic operations and square roots. In other words, the set of constructible points seems to be a robust set that can be described in many equivalent ways; it is a more fundamental notion than the arbitrary-sounding description in terms of compass and straightedge would seem to imply. I don’t think I would have been able to understand this without someone like Richeson to do a lot of research and then put all the details together into a coherent story.

[It reminds me of a similar phenomenon with computation: for example, the description of a Turing machine seems rather arbitrary, and in some ways it is, but it turns out that many different models of computation (Turing machines, multi-tape Turing machines, lambda calculus, Post canonical systems, RAM machines…) all yield the same set of computable functions, and so the arbitrary-seeming choice is actually describing something more fundamental.]

In the same way, I thought the problems of antiquity themselves were somewhat arbitrary; but they were famous because they are hard, and it turns out they were hard precisely because they were really getting at the heart of some fundamentally deep ideas. So the fact that they inspired so much rich mathematics is no mere accident of history. One gets the sense that if we ever encounter intelligent life elsewhere in the universe, we may find that they struggled with the same mathematical problems—in very different forms, to be sure, but recognizably the same on a fundamental level.

Anyway, I’ve written more than enough at this point, and I think you get the idea: I thoroughly enjoyed this book, learned a lot from it, and highly recommend it!

Posted in books, review | Tagged , , , , , , , , , , , , | 4 Comments

A new counting system

0 = t__ough
1 = t_rough
2 = th_ough
3 = through

So, for example, 458 = trough through tough though though.

English is so strange.

Posted in arithmetic, counting | Tagged , , , | 1 Comment

A simple proof of the quadratic formula

If you’re reading this blog you have probably memorized (or used to have memorized) the quadratic formula, which can be used to solve quadratic equations of the form

ax^2 + bx + c = 0.

But do you know how to derive the formula? Usually the derivation is presented via completing the square and it involves some somewhat messy algebra (not to mention the idea of “completing the square” itself).

My colleague Gabe Ferrer recently brought to my attention a remarkable new paper by Po-Shen Loh, A Simple Proof of the Quadratic Formula. This paper is remarkable for several reasons: first of all, it’s remarkable that anyone could discover anything new about the quadratic formula; it’s also remarkable for a research mathematician to publish something about elementary mathematics. (But Po-Shen Loh is not your average research mathematician either; he does lots of really cool work making mathematics more accessible for all kinds of learners.) I’m going to explain the basic idea but I highly recommend actually reading the paper, which not only explains the ideas but also does a great job putting everything in proper historical context. Loh has also made a whole web page dedicated to explaining the ideas, with a video, worked examples, etc.; it’s definitely worth taking a look!

The Setup

Suppose we have a quadratic equation we want to solve,

x^2 + bx + c = 0.

To make things simpler, we’ll assume that x^2 has a coefficient of 1. (If we have a quadratic equation with some other coefficient ax^2, we can always divide everything by a first.)

Now imagine we knew how to factor the quadratic. Then we could rewrite the equation into the form

(x - r)(x - s) = 0

which would imply that x = r and x = s are the two solutions. If we multiply out the above factorization (using, you know, “FOIL”), we get

x^2 - (r+s)x + rs = 0

which means we’re looking for values r and s whose product is c and whose sum is -b.

So far, so good; everyone learns this much in high school algebra. The way one usually goes about factoring quadratic polynomials is to make informed guesses for values of r and s and check whether their sum and product give the right coefficients.

The Insight

The key insight at this point, however, is that we don’t actually have to guess! Starting from r + s = -b, let’s divide both sides by 2:

\displaystyle \frac{r+s}{2} = -\frac{b}{2}

The left-hand side is the average of r and s, which lies halfway in between them on the number line. Let’s use z to denote the distance from r to -b/2. Since -b/2 is halfway in between r and s, z must also be the distance from -b/2 to s. So we can write r and s in the form

r,s = -b/2 \pm z

Now, we know their product has to be c, and multiplying them is particularly easy because we get a difference of squares:

\displaystyle c = rs = \left(-\frac{b}{2} + z \right) \left(-\frac{b}{2} - z \right) = \left(-\frac{b}{2} \right)^2 - z^2

Now solving for z is easy; just move z^2 to one side of the equation by itself and take the square root:

\displaystyle z = \pm \sqrt{\frac{b^2}{4} - c}

That means the solutions are

\displaystyle r,s = -\frac{b}{2} \pm z = -\frac{b}{2} \pm \sqrt{\frac{b^2}{4} - c}.

If you like, you can use the same method starting from ax^2 + bx + c = 0 to derive the usual quadratic formula including an arbitrary value of a, although the required algebra gets a bit messier.

Using it in practice

One particularly nice thing about this derivation is that it corresponds to a simple algorithm for solving an arbitrary quadratic equation x^2 + bx + c = 0, so there’s no need to memorize a formula at all:

  1. Note that the two solutions must add up to -b, so their average is half of -b, and hence they can be written as -b/2 \pm z.
  2. Write down the equation (-b/2 + z)(-b/2 - z) = b^2/4 - z^2 = c, and solve for z.
  3. The solutions are -b/2 + z and -b/2 - z.

Of course if you need to solve something of the form ax^2 + bx + c = 0, you can add an extra step to divide through by a first.

And that’s it! I really hope this new method will make its way into classrooms around the world; Loh makes the argument (and I agree) that it really is much easier for early algebra learners to grasp. And again, I really encourage you to go look at Loh’s web page to read more, especially about the historical context: at what point in human history could someone have come up with this idea? And why didn’t they? (Or if they did, why did we forget?) All this and more are in the original paper, which is a really fascinating and accessible read.

Posted in algebra, proof | Tagged , , , , | 3 Comments