The Theorem

Via Keith Devlin: The Theorem. (To give more of a description would spoil the punchline; I'd recommend not reading Devlin's article until after you've seen the video.) This should be familiar to anybody who's seriously thought about mathematics, although my life doesn't come with background music like the video does.

Mandelbrot, Knuth, and open-ended citations

A citation reproduced verbatim from Benoit Mandelbrot's The Fractal Geometry of Nature (1983):

Knuth, D. 1968-. The art of computer programming. Reading, MA: Addison Wesley.

The "1968-" is not Knuth's birth date, of course, but the date at which he started writing the work in question, which was fifteen years in the making when Mandelbrot wrote. It's still not done.

Incidentally, Mandelbrot's book is a good one, full of pretty pictures (although of course not as intricate as one might see now, because the book is a quarter-century old); it's also fairly casually written. Mandelbrot describes it as an "essay", in what I take to be the original Francophone sense of the word that means roughly an "attempt" at something, and so it's rather discursive, personal, and nonrigorous; these idiosyncrasies are good for a book one wants to read casually, as I do right now, but someone who wanted a rigorous understanding of the concepts might look elsewhere. I'm tempted to say it's a good series of lectures crystallized into paper form, although as far as I know it was never intended as such.

I think I'd heard of the book before, but it was Nova's Hunting the Hidden Dimension (aired on Tuesday night) that got me to actually head to the library and find it. I suspect I'm not alone, because apparently it's selling quite well on Amazon.

(The usual disclaimer on books I'm reading that I borrowed from the library applies: ignore my recommendations if you're at Penn, because I have the library's copy.)

No more Knuth checks

Donald Knuth is no longer giving reward checks for those who find errors in his books. Apparently people have been stealing his banking information and he's had to close some checking accounts. He's maintaining a web page with the amount of rewards people would receive, which is basically as good, because nobody was cashing the checks anyway. And perhaps it's better, because now everybody in the world can see that you found a bug in one of Knuth's books! If you just had a framed check on your wall, only the people you invited in could see it.

Congratulations to the Phillies

Really, one World Series win in twenty-eight years is pretty close to average; over the last twenty-eight years there have been between twenty-six and thirty teams in Major League Baseball, so the average team should have won the World Series about once in that time span.

Still, this blog congratulates the Philadelphia Phillies on their winning the World Series in five and a third games. Not that any of them are reading it.

(If I cared about sports other than baseball, things would be different; Philadelphia has four major professional sports teams, and until last night none of them had won the championship of their sport since the 1983 Sixers; that's about 100 sports seasons without a championship, which is noteworthy. At that time I was a small ball of undifferentiated cells. As was Cole Hamels.)

People are not balls

The margin of error is only the beginning of political polling: "If one or more of the above statements [about certain red and blue balls] are true, then the formula for margin of error simplifies to Margin of Error = Who the hell knows?"

Electoral sensitivity

By combing through my logs I found The electoral college and second terms, which is related to my post on translating popular votes to electoral votes. (Roughly speaking, in a close election, the electoral-vote margin is about five times the popular-vote margin.)

Bert and Ernie teach probability

From Alan Schwarz in the New York Times:

You can hear it in the same broadcast booth. One announcer will say that Joe Hitter is in a slump, suggesting that he is somehow plagued and that his chances of success are lower than normal. Then, as if on cue, the color man (in jovial agreement) will say that, yes, Mr. Hitter is due to break out— implying that his chances of success are higher than usual.

These exchanges and more are collected on the recently released three-disc set, “Bert and Ernie Teach Probability.”

Things have been slow around here; between the World Series, obsessing over the election, and Real Work, the blog's kind of getting left behind. But I thought you might appreciate this. According to the model implied by What Announcers Say, the hitters who are most likely to do poorly in a given game are the ones who have been performing near their long-term average.

(Oh, and by the way, "Bert and Ernie Teach Probability" doesn't exist. I was up late last night -- the game didn't end until quarter of two in the morning -- so I'm not thinking quite straight. So I checked. It should exist. Dear Internet, get working on that.)

The curse of Al Polaneczky

The little-known curse of Al Polaneczky. Apparently the Phillies' 1964 collapse (they were six and a half games up with twelve to play, lost ten in a row, and ended up finishing in a tie for second place) can be blamed on Al Polaneczky, a statistician at the Franklin Institute, who used the institute's computers to determine the odds of the Phillies winning the pennant that year.

Of course, by that logic, all baseball teams are cursed now, because people are crunching numbers constantly. Maybe all the curses cancel out.

The Archimedean property of reality

The Archimedean property of reality: if you put one foot in front of the other for long enough, you can travel an arbitrarily long distance.

This is, of course, the Archimedean property of the real numbers -- that is, for any two positive real numbers x and y, there exists an integer n such that nx > y -- if we can make the assumption that step length is constant.

It's also what got me through some hard times in the first year of grad school, when I doubted my mathematical abilities; at least I could successfully walk to and from school each day. The proverb "a journey of a thousand miles begins with a single step" comes to mind, but my walk is about a mile and a half.

Jon Stewart's quiz: "Are you a real American?"

Jon Stewart inadvertently illustrates why you shouldn't use pictures as the names of your variables.

Two sorts of predictions

Lately, there are two things that a lot of people searching for this blog seem to want to know: predictions about the election, and predictions about the World Series.

Baseball Prospectus says the Phillies have a 51.7% chance of winning, and the Rays 48.3%. That seems a bit surprising, though; I would have thought (although I don't like to admit it) that the Rays would be a slight favorite. I suspect there's some difficulty in incorporating the fact that the American League (in which the Rays play) has a higher quality of play that the National League (in which the Phillies play).

And Fivethirtyeight.com says Barack Obama has a 93.8% chance of winning. (The election, not the World Series.) The prediction there is based on a Monte Carlo method which simulates the election results; there's a plot of the number of electoral votes received in the simulations, and it gets spikier and spikier as more and more states become settled one way or the other. (The site's model assumes that states may move between now and Election Day, and as "now" gets closer to Election Day, that effect diminishes.)

What do these two predictions have in common? Fivethirtyeight.com is Nate Silver's web site; he works for Baseball Prospectus.

By the way, various people have said that Fivethirtyeight.com doesn't take into account correlations between states. The most common misconception seems to be that the site assumes the results in each state are independent. This is not true; if you start from the state win probabilities displayed there and combine them under the assumption of independence, you get a distribution much different than the one currently displayed on the site.

Derivation is not destiny

Arnold Zwicky at Language Log points out that the "derivative" of "financial derivatives", a word we've been hearing lots in the news lately, is not derived from the "derivative" of calculus. (This is commenting on a misunderstanding in a recently published letter to the New York Times.)

It never made sense to me that while the verb for "find the integral" is "integrate", the verb for "find the derivative" is "differentiate" -- in one case the forms are parallel and in the other they aren't. Of course the derivative involves finding a difference, but the language seems a bit inconsistent. And I've had the occasional student refer to "derivating" a function.

It probably doesn't help that they both start with d, and that every d-like symbol (off the top of my head, at least d, D, δ, Δ, and ∂) gets used for some sort of derivative/difference-like thing in some context.)

Solvable PDEs have measure zero

PDEs are very hard to solve.

I heard it claimed that it's very lucky, if you're someone who does mathematical finance, that the Black-Scholes partial differential equation, when used to price a call option, has a closed-form solution. (Well, if you include the error function in "closed form".)

The payoff of the thing being priced gives the initial condition for the Black-Scholes PDE and for a simple perturbation of that, there is probably not such a simple solution. And options markets probably would have developed very differently if there hadn't been an exact solution, because solving such an equation numerically, while possible, is a lot slower.

A friend of mine who knows more about PDEs than I do said that, basically, the set of exactly solvable PDEs has measure zero. Of course this isn't a theorem, but the point is that people who study PDEs don't expect there to be exact solutions.

Another shot at the "theory vs. practice" question

Michael Alison Chandler, an education reporter for the Washington Post, is currently taking a high school "Algebra II" class. As she said in her first post, she's "not a math person" and yet math increasingly comes up in what she's reporting on, so she wanted to see what math education in the schools is like these days.

In today's post, she writes:

It's difficult to describe how or why math works. It's easier to just write the formula and say, "Do this." Several readers have commented on this blog that what's often missing from math education is more of a focus on why certain applications work. I agree. It's harder to remember what to do, if you don't have some sense of why it works.

This is something that many mathematicians should remember. But there's a balance to be struck; if you spend too much time on the theory ("why" it works) and never apply it that's silly too.

As you may have guesed, I primarily view mathematics as a tool for solving various interesting problems; I'm often not interested in the theory for its own sake, but I do like that knowing "theoretical" things makes lots of problems more tractable. Often such problems involve lots of calculation, and as many of you know it's easy to get lost in a calculation if you don't understand why you're doing it. But if you never calculate, and you only prove general results, I feel like you're ignoring why this subject exists in the first place. (Mathematicians of a more theoretical inclination may, of course, disagree.)

The launch of the Tricki

Tim Gowers on the forthcoming launch of the Tricki, essentially a wiki which will consist of mathematical problem-solving techniques or "tricks". I'm massively oversimplifying; read his post.

The Onion on math teaching

The Onion exposes poor math teaching in the schools.

An upper bound for the order of an element of the Rubik's cube group

The maximum order of an element of the Rubik's cube group R is 462 might be 462, or might be 1260, or might be something else.

Why? The Rubik's cube group is a subgroup of S₈ × S₁₂ × Z₃⁸ × Z₂¹²; the four factors here arise from possible permutations of the edge and corner pieces, and the orientations of the edges and the corners. (This is in fact twelve times as large as the actual group.) More concretely, it's the subgroup of this group consisting of quadruples (σ, τ, v, w), where σ ∈ S₈ and τ ∈ S₁₂ have the same parity, v is an element of Z₃⁸ whose coordinates sum up to zero, and w is a similar element of Z₂¹². The group operation in this group is given by working componentwise.

(If I have misunderstood what I've heard about Rubik's cubes, then please ignore the rest of this post.)

[edited, 8:48 pm: turns out I have, as the multiplication isn't exactly componentwise.]

So the order of (σ, τ, v, w) is the least common multiple of the orders of σ, τ, v, w in S₈, S₁₂, Z₃⁸, and Z₂¹² respectively. Call these o(σ), o(τ), o(v), o(w). If σ has one 7-cycle and one 1-cycle, τ has one 11-cycle and one 1-cycle, and v and w are nontrivial, then o(σ) = 7, o(τ) = 11, o(v) = 3, o(w) = 2, and so the order of (σ, τ, v, w) is lcm(7, 11, 3, 2) = 462. (This corresponds to a sequence of moves, whatever it may be, that permutes seven of the corners and eleven of the edges cyclically, and disrupts the orientations of both the corners and the edges.) Note that σ and τ are both even permutations.

Furthermore, we can't do better. I don't think there's a particularly elegant proof, but it's not hard to check by brute-force computation that no choice of the cycle types for σ and τ which gives both the same parity allows us to do better. If you let σ have one cycle of order 8, and τ have one cycle of order 7 and one of order 5, and let v, w both be nontrivial, then you'd think the order of (σ, τ, v, w) was lcm(8, 35, 3, 2) = 840, but σ is odd and τ is even. In fact, that's how I got the number 462 -- take lcm(s, t, 3, 2) where s ran over possible orders of elements of S₈ and t ran over possible orders of elements of S₁₂; the largest number you get this way is 840, but it can only come about in the way I described. 462 is the next-largest.

In case you're wondering how I came to this question -- it's easy to see if you play around with the cube that if you do the same sequence of moves over and over again, you eventually get back where you started. (Theoretically, this is a consequence of the fact that any element of a group has finite order.) So I just started to wonder how many times you might have to do the same sequence of moves on a solved cube to get it back to the solved state.

Schwitzgebel and Cushman's "moral sense test"

Eric Schwitzgebel (a philosopher at U.C. Riverside) and Fiery Cushman (a psychologist at Harvard) have designed a "Moral Sense Test" that asks respondents for their takes on various moral dilemmas. They're looking to compare the responses of philosophers and non-philosophers, so they've asked me to post a link to their test from this blog. They say that people who have taken other versions of this test have found it interesting to ponder the moral dilemmas they ask about. The test should take about 15-20 minutes and can be found here.

The test says "Please do not discuss the questions with anybody else, or consult any texts or outside material, while you are taking the test." I suspect that some of my readers will want to comment on the test, so if you intend to take the test, please don't read the comments to this post until after you've done so.

Tao on polling

Terry Tao on the mathematics of electoral polling.

Interesting fact of the day

The number of ways to write n as a sum of powers of 2, where each summand occurs at most three times, is (n/2) + 1 rounded down. See the 1983 Putnam exam, problem B2 (link goes to a solution, so don't go there if you want to think about the problem yourself!) I learned this from Bruce Reznick's paper "Some binary partition functions".

Of course, if we replace "three" by "one", the analogous problem is trivial -- it's just saying that the binary expansion of an integer is unique. If "three" is replaced by "two", we get an interesting sequence: let b(n) be the number of ways to write n as a sum of powers of two where each summansd occurs at most three times. So for example b(14) = 4, since we can write 14 as 8 + 4 + 2, 8 + 4 + 1 + 1, 8 + 2 + 2 + 1 + 1, or 4 + 4 + 2 + 2 + 1 + 1. I've alluded to this sequence before in comments. Starting with b(0), the sequence of b(n) is

1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4, 1, 5, 4, 7, ...

and we can make rational numbers out of these by taking b(n)/b(n+1):

1/1, 1/2, 2/1, 1/3, 3/2, 2/3, 3/1, 1/4, 4/3, 3/5, 5/2, 2/5, 5/3, 3/4, 4/1, 1/5, 5/4, 4/7, ...

and it turns out this sequence includes each rational number exactly once! Neil Calkin and Herb Wilf wrote about this in their paper Recounting the rationals, which you should read. I first learned about this paper from Brent Yorgey's series of posts.

Instability of the US News college rankings

Rating the Rankings, at Science News: by weighting the different factors in the US News and World Report college rankings differently, different schools can come out on top, and the rankings in general are pretty strongly perturbed, say Lior Pachter and Peter Huggins. The original paper is (I think) "Selecting universities: personal preference and rankings", arxiv:0805.1026. Basically, some schools do some things better and some schools do other things better.

It would be interesting to see this implemented as a sort of "make your own rankings" thing: a student could say how much they cared about various factors, and it wouldn't be hard to produce a ranking of schools according to which they would most like to go to.

However, to do this right, you'd have to allow nonlinear weights; most students would probably like to go to a school where they are near-average in the student population. Ranking schools according to their suitability for a given student is not the problem these rankings attempt to solve. And then the average 17-year-old doesn't really now what they want out of a college anyway... so maybe it isn't so easy. That's what guidance counselors are for, I suppose.

I've suspected that the ratings depended heavily on the weighting scheme for a while. I've even heard it somewhat cynically suggested that the weights on different factors are adjusted basically to make the rankings "look right", i. e. so that the schools that "everybody knows" are the best come out on top.

Conditional probability is subtle

From 60 Minutes on Sunday, video here: the banking crisis is the fault of the mathematicians and physicists, who went to work on Wall Street and invented some complicated models. The "financial expert" says that "you can't model human behavior with math". That may be true with our current mathematics, but I suspect the fault doesn't lie with the modelers so much as with the people who went ahead and thought the models were perfect.

Although there are rumors that a lot of the models basically worked on the principle that defaults on mortgages were independent, which is so obviously false that you'd fail a freshman who said it. (Basically, when the economy gets bad, more people can't pay their mortgages. The effect is larger because there are adjustable-rate mortgages, and everybody suffers roughly the same adjustments.) I would not be surprised to learn that the problem here is that Conditional Probability Is Subtle; the quants may very well have known their models were flawed, but the suits didn't want to hear it.

I just hope this meme dies out quickly and doesn't gain traction. Our PR already isn't so good.

The eyeballing game

Check out the eyeballing game. You're asked to "eyeball" various geometric constructions -- the perpendicular to a given segment, the center of a given circle, the bisector of a given angle, and so on.

I'm kind of curious which sort of mathematicians do best on this. I have very little reason to draw geometrically accurate pictures in my work. Although to be honest, even people who do geometry don't have to draw really accurate pictures; I suspect it's the engineers who would be best at this.

(via reddit.)

Freakonomics compiles math quotes

An interesting list of quotes about mathematics, as compiled by readers of the Freakonomics blog.

Here's one that's new to me and that resonates with me at the moment, having spent the afternoon creating a document which is essentially a list of facts, to which I'll add the proofs later. It's attributed to Poincare, although a bit of googling seems to indicate he said it about science, not mathematics.
"Math is built with facts as a house is built with bricks, but a collection of facts cannot be called mathematics anymore than a pile of bricks can be called a house."
What I have now is a pile of bricks. I have the mortar that holds them together, but it's not in the same place.

You'll also find the text of the poem which begins "I’m sure that I will always be a lonely number like root three", featured in Harold and Kumar Escape From Guantanamo Bay.

Who knew high school geometry was good for something?

Groundskeepers Display Artistry on the Diamond, September 30 (?) New York Times. David Mellor, the current head groundskeeper at Fenway Park, is the one who started the trend of mowing the grass in such a way as to create interesting-looking patterns; apparently he first did it in order to camouflage some damaged grass in Milwaukee in the early 90s. Roughly speaking, the mowing action bends the grass in one direction or another, creating contrasts of light and dark; you can see a similar effect when you vacuum your carpet. (I really mean "you" here. I can't; I have wood floors.)

And we're told that "High-school geometry classes visit [Mellor] at Fenway Park to study ways that an odd-shaped field can be divided and subdivided by straight lines and sharp angles."