Meta
Categories
 algebra (47)
 arithmetic (86)
 books (35)
 calculus (7)
 challenges (58)
 combinatorics (29)
 complex numbers (6)
 computation (83)
 convergence (9)
 counting (38)
 famous numbers (48)
 fibonacci (18)
 fractals (13)
 games (34)
 geometry (72)
 golden ratio (8)
 group theory (28)
 humor (8)
 induction (8)
 infinity (19)
 iteration (24)
 links (76)
 logic (12)
 meta (43)
 modular arithmetic (30)
 number theory (108)
 open problems (11)
 paradox (1)
 pascal's triangle (8)
 pattern (106)
 people (23)
 pictures (74)
 posts without words (42)
 primes (57)
 probability (9)
 programming (20)
 proof (93)
 puzzles (18)
 recursion (16)
 review (25)
 sequences (28)
 solutions (31)
 teaching (16)
 trig (3)
 Uncategorized (6)
 video (19)
Archives
 June 2021 (1)
 May 2021 (1)
 March 2020 (4)
 February 2020 (1)
 January 2020 (7)
 December 2019 (4)
 November 2019 (2)
 October 2019 (5)
 September 2019 (7)
 August 2019 (3)
 July 2019 (5)
 May 2019 (4)
 April 2019 (2)
 March 2019 (3)
 February 2019 (3)
 January 2019 (4)
 November 2018 (3)
 October 2018 (4)
 September 2018 (4)
 August 2018 (6)
 July 2018 (2)
 June 2018 (5)
 May 2018 (3)
 April 2018 (5)
 March 2018 (4)
 February 2018 (3)
 January 2018 (4)
 December 2017 (3)
 November 2017 (3)
 October 2017 (1)
 September 2017 (1)
 July 2017 (4)
 June 2017 (4)
 May 2017 (9)
 April 2017 (7)
 March 2017 (5)
 February 2017 (4)
 January 2017 (3)
 December 2016 (4)
 November 2016 (6)
 October 2016 (6)
 September 2016 (2)
 August 2016 (5)
 July 2016 (2)
 June 2016 (4)
 May 2016 (4)
 April 2016 (2)
 March 2016 (3)
 February 2016 (9)
 January 2016 (8)
 December 2015 (5)
 November 2015 (29)
 August 2015 (3)
 June 2015 (2)
 April 2015 (1)
 May 2014 (1)
 December 2013 (1)
 October 2013 (1)
 July 2013 (1)
 June 2013 (1)
 May 2013 (1)
 April 2013 (3)
 March 2013 (3)
 February 2013 (2)
 January 2013 (5)
 December 2012 (3)
 November 2012 (4)
 October 2012 (5)
 September 2012 (1)
 August 2012 (4)
 July 2012 (1)
 June 2012 (6)
 May 2012 (2)
 April 2012 (3)
 March 2012 (1)
 February 2012 (4)
 January 2012 (5)
 December 2011 (1)
 November 2011 (7)
 October 2011 (4)
 September 2011 (6)
 July 2011 (2)
 June 2011 (4)
 May 2011 (5)
 April 2011 (2)
 March 2011 (4)
 February 2011 (1)
 January 2011 (1)
 December 2010 (1)
 November 2010 (4)
 October 2010 (2)
 September 2010 (1)
 August 2010 (1)
 July 2010 (1)
 June 2010 (2)
 May 2010 (3)
 April 2010 (1)
 February 2010 (6)
 January 2010 (3)
 December 2009 (8)
 November 2009 (7)
 October 2009 (3)
 September 2009 (3)
 August 2009 (1)
 June 2009 (4)
 May 2009 (5)
 April 2009 (4)
 March 2009 (2)
 February 2009 (1)
 January 2009 (7)
 December 2008 (1)
 October 2008 (2)
 September 2008 (7)
 August 2008 (1)
 July 2008 (1)
 June 2008 (1)
 April 2008 (5)
 February 2008 (4)
 January 2008 (4)
 December 2007 (3)
 November 2007 (12)
 October 2007 (2)
 September 2007 (4)
 August 2007 (3)
 July 2007 (1)
 June 2007 (3)
 May 2007 (1)
 April 2007 (4)
 March 2007 (3)
 February 2007 (7)
 January 2007 (1)
 December 2006 (2)
 October 2006 (2)
 September 2006 (6)
 July 2006 (4)
 June 2006 (2)
 May 2006 (6)
 April 2006 (3)
 March 2006 (6)
Post without words #30
Posted in posts without words
Tagged binary, bits, cube, diagram, Hasse, hypercube, lattice, subsets
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 19thcentury civil engineer and mathematician, best known nowadays for this incredible “colorcoded” 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 colorcoded 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 mid1800s. 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 8yearold 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…
do go no to
dodo
do go on
do no harm
do to others
go do likewise
gogo music
go no further
goto considered harmful
no can do
it’s a no go
a big nono
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.
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 2000Year Quest to Solve the Mathematical Problems of Antiquity
David S. Richeson
Princeton University Press, 2019
Let me get right to the point: this was handsdown 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 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 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 is constructible with straightedge and compass if and only if and 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 arbitrarysounding 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, multitape Turing machines, lambda calculus, Post canonical systems, RAM machines…) all yield the same set of computable functions, and so the arbitraryseeming 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 algebra, antiquity, circle, constructible, construction, cube, geometry, impossibility, polygon, problems, square, tales, trisect
4 Comments
A new counting system
0 = t__ough
1 = t_rough
2 = th_ough
3 = through
So, for example, trough through tough though though.
English is so strange.
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
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 PoShen 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 PoShen 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,
To make things simpler, we’ll assume that has a coefficient of . (If we have a quadratic equation with some other coefficient , we can always divide everything by first.)
Now imagine we knew how to factor the quadratic. Then we could rewrite the equation into the form
which would imply that and are the two solutions. If we multiply out the above factorization (using, you know, “FOIL”), we get
which means we’re looking for values and whose product is and whose sum is .
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 and 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 , let’s divide both sides by :
The lefthand side is the average of and , which lies halfway in between them on the number line. Let’s use to denote the distance from to . Since is halfway in between and , must also be the distance from to . So we can write and in the form
Now, we know their product has to be , and multiplying them is particularly easy because we get a difference of squares:
Now solving for is easy; just move to one side of the equation by itself and take the square root:
That means the solutions are
If you like, you can use the same method starting from to derive the usual quadratic formula including an arbitrary value of , 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 , so there’s no need to memorize a formula at all:
 Note that the two solutions must add up to , so their average is half of , and hence they can be written as .
 Write down the equation , and solve for .
 The solutions are and .
Of course if you need to solve something of the form , you can add an extra step to divide through by 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.
Post without words #29
(This variant was requested by Mark Dominus.)
Book review: Opt Art
[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.]
Opt Art: From Mathematical Optimization to Visual Design
Robert Bosch
Princeton University Press, 2019
I recently finished reading Robert Bosch’s new book, Opt Art. It was a quick read, both because it’s not actually that long, but also because it was fascinating and beautiful and I didn’t want to put it down!
The central theme of the book is using linear optimization (aka “linear programming”) to design and generate art. The resulting art can be simply beautiful for its own sake, or can also give us insight into underlying mathematics.
Linear optimization is something I knew about in a general sense, but after reading Bosch’s book I understand it much better—both the details of how the simplex algorithm works, and especially the various ways linear optimization can be applied. I think Bosch does a fantastic job explaining things in a way that gives real insight but doesn’t get bogged down in too much detail. (In a few places I personally wish there had been a few more details—but it’s quite possible that adding more detail would have made the book better for me but worse for a bunch of other people, i.e. it would not be a global optimum!)
Another thing the book explains really well is how the Travelling Salesman Problem (TSP) can be solved using linear optimization. I had no idea there was a connection between the two topics. I’m sure the connection is explained in great detail in the TSP book by William Cook, which I read 7 years ago, but for some reason when I read that I guess it didn’t really click. But from reading Bosch’s book I feel like I now know enough to put together the details and implement a basic TSP solver myself if I wanted to (maybe I will)!
I’m definitely inspired to use some of Bosch’s techniques to make my own artwork—if I do, I will obviously post about it here!
More on Human Randomness
In a post a few months ago I asked whether there is a way for a human to reliably generate truly random numbers. I got a lot of great responses and I think it’s worth summarizing them here!
Randomness in poker strategies
Robert Anderson noted that poker players sometimes use the second hand of a watch to introduce some randomness into their strategy. I assumed this would be something like getting a random bit based on whether the number of seconds is even or odd, but Pete McAllister chimed in to say that it is usually something more like dividing a minute into chunks, and making a decision based on which chunk the current second is in. For example, if you want to make one choice 20 percent of the time and another choice 80 percent of the time, you could just make the first choice if the second hand is between 0–12 seconds, and the other choice otherwise.
In game theory this is called a “mixed” strategy, and this kind of strategy can arise naturally as the Nash equilibrium of certain kinds of games, so it’s not surprising to me that it would show up in highlevel poker. I found conflicting advice about this online; some people were claiming that you should not use randomness when playing poker, but I did find a website that talked about implementing this kind of mixed strategy using the second hand of a watch, and it seemed to be a website with pretty highlevel poker advice.
In any case, if you have a phone or a watch with you, this does suggest some strategies for generating random numbers: for example, look at the last digit of the seconds to get a random number from 0–9, or whether it is even or odd to get a bit. Or you could just take the number of seconds directly as a random number between 0–59. Of course this only works once and then you have to wait a while before you can do it again. Also, it turns out that my phone doesn’t show seconds by default. Taking the ones digit of the minutes as a random number from 0–9 should work too, but the tens digit of the minutes seems like it’s “not random enough”, in the sense that it might be correlated with whatever it is that I’m doing.
Of course, a phone or watch counts as an “aid”, but most people tend to carry around something like this all the time, so it’s relatively practical. On the other hand, if you’re going to use a phone anyway, you should just use an app for generating random numbers.
Bodies and clothing

Naren Sundar commented that hair is pretty random, but admitted that it would be hard to measure.

Frederik suggested spitting, or throwing your shoe in the air and seeing which way the toe points when it lands. I like the shoe idea, but on the other hand it’s somewhat obtrusive to take your shoe off and throw it in the air every time you want a random bit! And what if you’re not wearing shoes? I’m also afraid I might throw my shoe in the same way every time; I’m not sure how random it would be in practice.
Minds and memorization
Kaligule suggested taking whatever song is currently running through your head, stopping it at a random point, and getting a random bit by seeing whether the number of consonants in the next word is even or odd.
This is a cool idea, and is the only proposal that really meets my criterion of generating randomness “without aids”. I think for some people it could work quite well. “Stopping at a random point” is somewhat problematic—you might be biased to stop at certain points more than others—but it’s pretty hard to know how many consonants are in a word before you count, so I’m not sure this would really bias the results that much.
Unfortunately, however, it won’t work for me because, although I do always have some kind of music running through my head, it often has no lyrics! Kaligule suggested using whether the melody goes up or down, but this is obvious (unlike number of consonants in a word) and too easy to “cheat”, i.e. pick a stopping point that gives me the bit I “want”.
This suggested another idea to me, however: just pregenerate some random data and put some upfront effort into memorizing it. Whenever you need some randomness, use the next part of the random sequence you memorized. When you use it up, generate another and memorize that instead. This leaves a number of questions:

How do you reliably keep track of where you are in the sequence? I don’t actually have a good answer to this. I think in practice I would get confused and forget whether I had already used a certain part or not. Though maybe this doesn’t really matter that much.

What format would be most effective, and how do you go about memorizing it? Some ideas:

My first idea is to generate a sequence of random bits, and then write a story where sequential words have even or odd numbers of letters corresponding to the bits in your sequence. Unfortunately, this seems like a relatively inefficient way to memorize data, but writing a story that corresponds to a given sequence of bits does sound like a fun exercise in constrained writing.

Alternatively, one could simply generate a random sequence of digits (or hexadecimal digits) and memorize them using whatever sort of memorization technique you like (e.g. a memory palace). This is less fun but probably more effective. Memorizing a story sounds like it would be easier, but I don’t think it is, especially since you would have to memorize it wordforword and you only get one bit per word memorized, as opposed to something like e.g. four bits per hexadecimal digit.

I have generated some random hexadecimal digits but haven’t gotten around to trying to memorize them yet. If I do I will definitely report on the experience. In the meantime, I’m also open to more ideas!