A Russian teacher in America

A Russian teacher in America, by Andrei Toom.

It's what it sounds like. Toom repeats the familiar litany that in America, students learn for grades, and only incidentally for learning; it's an interesting read, mostly because of the perspective that he's able to bring to it as somebody who didn't grow up within the American system.

I'm thankful for the Borel-Cantelli lemma

Cosmic Variance is thankful for the spin-statistics theorem, because it enables the division between matter and force, which is kind of important.

In this spirit, I am thankful for the second Borel-Cantelli lemma, which states that if countably many events E₁, E₂, E₃, ... are independent and the sum of the probabilities of the E_n diverges to infinity, then the probability that infinitely many of them occur is 1. Let these events be "something interesting happens at time n", for a suitable quantization of time; then given infinite time, infinitely many interesting things will happen. (Of course I'm making an independence assumption here.) I like interesting things.

I am also thankful for whoever it was that took a picture of a monkey at a typewriter.

Neal Stephenson's Anathem

I haven't really digested it yet (in fact, I'm only a third of the way through it), but Anathem by Neal Stephenson is making a strong run at the title of My Favorite Book. Mostly because there's math hidden everywhere inside it. And how could I resist this, which almost feels like something out of The Glass Bead Game:

Three fraas and two suurs sang a five-part motet while twelve others milled around in front of them. Actually they weren't milling; it just looked that way from where we sat. Each one of them represented an upper or lower index in a theorical equation inolving certain tensors and a metric. As they moved to and fro, crossing over one another's paths and exchanging places wile traversing in front of the high table, they were acting out a calculation on the curvature of a four-dimensional manifold, involving various steps of symmetrization, antisymmetrization, and raising and lowering of indices. Seen from above by someone who didn't know any theorics, it would have looked like a country dance. The music was lovely even if it was interrupted every few seconds by the warbling of jeejahs.

Please, Internet, deliver me video of this mathematical dancing. Somewhat more seriously, though, moving pictures often float in my mind (and I suppose the minds of others) as I attempt to understand various mathematical structures.

Stephenson gave an interesting
talk/Q-and-A at Google about the book, if you've got an hour to kill. I think if you liked Cryptonomicon
you'll like this one; on the other hand I was disappointed by the Baroque Cycle, which lots of people seem to have liked. I suspect this has to do with the times in which they're set; the Baroque Cycle takes place a few centuries ago, Cryptonomicon during World War Two, and Anathem on another planet entirely, but one in which the secular world is roughly comparable to present-day Earth. (Perhaps a bit too comparable; Earth intellectual history and the intellectual history inside Anathem are essentially the same thing with different names.) Except in Anathem, the mathematicians live in what are essentially monasteries cut off from the outside world. I don't think I could handle that. I suppose some would argue that universities aren't the Real World, though...

The asymptotics of "27 lines on a cubic"

Charlie Siegel, whose office is just down the hall from mine, had for a while the following statement on the blackboard in his office (paraphrased and renotated a bit): Let g(n) be the number of lines on the generic hypersurface of degree 2n-1 in complex projective (n+1)-space. Then

where the notation means "the coefficient of zⁿ in f(z)". For example, g(2) is the coefficient of z² in (1-z)(3)(2+z)(1+2z)(3z), which turns out to be 27; this means that the number of lines on the generic hypersurface of degree 3 in complex projective 3-space is 27. Informally, "there are 27 lines on the cubic". Want to know why? For the cubic case, see this post by Charlie or go to his talk last week.

The first few values of g(n) are 1, 27, 2875, 698005, 305093061, 210480374951, 210776836330775, 289139638632755625... -- so this sequence grows pretty quickly. How quickly? I couldn't tell at first, but it kept nagging at me every time I was in Charlie's office. The sequence is A027363 in the Encyclopedia of Integer Sequences. It turns out that it's in an appendix of the paper that the Encyclopedia links to (arXiv:math/0610286, specifically its appendix by Zagier) but the derivation there is long and involved and it was more fun with the formula myself. There are a few gaps, but here it is.

We can deal easily with the 1-z factor out front, and we want

where

We can already see it's going to be kind of tricky; the coefficients of f_n(z) are probably going to be pretty big and not that far apart.

Now, we can pull out a 2n-1 from each factor in the expression for f_n(z), and we get

Call the product p_n(z). Now this is where, out of nowhere, I start having Fun With Probability. (It's kind of amusing because there is nothing probabilistic about the original question.) The term corresponding to j in that product is the probability generating function of a random variable which is 1 with probability (j/(2n-1)) and 0 otherwise. The product is thus the p.g.f. of the sum of such random variables for j = 0, 1, ..., 2n-1.

Now, this sum has mean which is the sum of the means of those random variables, that is,

and variance which is the sum of their variances,

which is approximately n²/3. Furthermore, since the sum is a sum of a bunch of small contributions, it's approximately normal. So p_n(z) is the probability generating function of a random variable which is roughly normal with mean n and variance n²/3, but integer-valued, and its kth coefficient is the probability that such a random variable is equal to k.

Therefore [z^k] p_n(z) is approximately

which is the density of such a normal random variable. We want to know [zⁿ] p_n(z) - [zⁿ] p_n-1}(z), and this is approximately q_n(n) - q_n(n-1). You'd think this would be q_n'(n), but q_n(n) is actually zero -- the fact that the coefficients were "close to each other" is even more troublesome than you'd expect. Still, we can make a Taylor series for q_n at n, and the linear term is zero, so we get

And g(n) = [zⁿ] f_n(z) - [zⁿ] f_n-1(z) = (2n-1)²ⁿ ([zⁿ] p_n(z) - [zⁿ] p_n-1(z)); using the approximation we get

and now note that

Therefore

which matches (with a bit of computation) the result given by Zagier in the arXiv, and the terms reported in the OEIS. I wouldn't have trusted it otherwise; that "take the second derivative" step is particularly sketchy, although it can probably be justified as there are results on the rate of convergence of the central limit theorem. But asymptotic analysis is nice in this way; if it's easy to compute the terms of some sequence, then we can often be confident in results like this even without

Besides, I'd never seen the trick of using the second derivative to approximate a difference before. At least not that I can remember.

Eulerian beer

At mathlog: Jever Bierdeckel-Mathematik und die Brücken von Kaliningrad. That is, "Jever coaster mathematics and the bridges of Konigsberg." (Why this funny translation? Because you haven't heard of the bridges of Kaliningrad, even though that's what the city is called now.)

It includes a solution to the general problem of identifying graphs with Eulerian tours. In English, in the form of a poem.

And what do coasters have to do with this? Jever is a beer, and the problem of finding an Eulerian tour is on a coaster they distribute (in German).

Edit, 1:28 pm: In the comments, Wing says that he thought the post would be about Euler beer. Apparently there is a beer named Euler. Someone's auctioning off a coaster on ebay.

On foods of genus one

It seems that some people describe the torus as the shape of a bagel, and others as the shape of a doughnut.

I wonder if this is somehow correlated with geography; bagels are more common in some places, doughnuts in others.

Heuristic derivation of the Prime Number Theorem

One way of stating the Prime Number Theorem is that the "probability" that a large number near x is prime is 1/log(x). (Here, as always, all logs are natural.)

A heuristic derivation of the prime number theorem, Frank Morgan, via Andrew Gelman, with some embellishment by me: let P(x) be the "probability" that a large integer x is prime. Then how do P(x+1) and P(x) compare? Say x is prime, which it is with "probability" P(x); it "divides" x+1 (and all larger numbers) with probability 1/x. (Of course, this doesn't actually make sense; the idea is that we're modeling the numbers divisible by x as a random set with density 1/x, which should have the same large-scale properties.) Other than this, x and x+1 are equally "likely" to be prime. So the function P satisfies

(*) P(x+1) = P(x) [P(x) (1 - 1/x)] + (1 - P(x)) P(x)

since x+1 is "prime" with probability P(x) (1-1/x) if x is "prime", and P(x) otherwise. Divide through by P(x) to get

P(x+1)/P(x) = P(x) (1-1/x) + (1-P(x))
P(x+1)/P(x) = 1 - P(x)/x.

Now, P(x+1) can be approximated by P(x) + P'(x), so we have

1 + P'(x)/P(x) = 1 - P(x)/x
P'(x)/P(x) = -P(x)/x

which has the general solution P(x) = 1/(C + log x).

This is a bit of a lie. For one thing, the difference equation (*) actually seems to have solutions that differ from those of the differential equation by a constant factor, which seems to depend on the initial conditions. (This amounts to changing the base.) For another thing, the assumption that x+1 might be divisible by x is, um, stupid if we're actually talking about prime numbers. (It's probably possible to rephrase this heuristic derivation as a rigorous result about random sets, though.) Still, it gets the prime number theorem to within a constant factor, which isn't bad for such a simple argument.

The Know-It-All

I'm reading The Know-It-All: One Man's Humble Quest to Become the Smartest Person in the World, by A. J. Jacobs -- I remembered hearing good reviews, and they're for the most part right. It's an amusing book to read, because it's part trivia and part A. J. Jacobs, who's an editor at Esquire, read the entire Encyclopedia Britannica in a year or so, which is long enough that while he was reading it amusing stories unfolded in his life -- most of which have some trivia worked in. Is it great literature? No. But it's fun. And there's the inevitable moment when you know something that Jacobs doesn't mention he knows; that makes you feel a little smarter when you're reading any book, but especially one with this book's subtitle.

It's amusing and interesting to be reading this during my less ambitious attempt to read the The Princeton Companion to Mathematics
. But I'm mostly making this post because I couldn't resist sharing this, from when Jacobs joins Mensa:

Of course, I'm terrified that I'll be rejected. In fact, I'm pretty sure that they'll send me a letter thanking me for my interest, then have a nice hearty laugh and go back to their algebraic topology and Heidegger texts and Battlestar Galactica reruns.

From britannica.com, it looks like the EB does not have an article titled "algebraic topology". But there are articles titled "topology" and "mathematics" with sections named "algebraic topology", and they do seem to have serious treatments of mathematics in there. Jacobs admits (p. 338) that "the math sections... are my bête noire.

Kiyoshi Ito dead

Kiyoshi Ito (of Ito calculus fame) is dead.

(When? I'm not sure. The New York Times says Monday, the 17th, but the Japan Times published an obituary on Saturday the 15th which said he died "Monday" -- so I'm guessing the 10th.)

See the obituaries, the MacTutor biography and Wikipedia article, or this Notices article upon his receipt of the Gauss Prize for an idea of his contributions.

A couple amusements from the Princeton Companion

From The Princeton Companion to Mathematics, specifically the article "Algebraic Geometry", by János Kollár:

Finally, if we marry a scheme to an orbifold, the outcome is a stack. The study of stacks is strongly recommended to people who would have been flagellants in earlier times.

I feel this way about most of algebraic geometry, but that's only because Penn has a high enough concentration of algebraic geometers that I get tired of hearing people walking around and talking about it all the time.

Also, I find myself screaming at the book quite often. But I do it in a good way; it's often some crucial insight that makes me think "why didn't anybody tell me that before?" (Of course, it's possible they did and I wasn't listening.) And sometimes it's "oh, damn, I thought I came up with that myself". For example, I just read the article on computational number theory, by Carl Pomerance, in which he explains a heuristic reason why Fermat's last theorem is true. I won't give it in full here, but it's basically the following. First, Euler showed it for n = 3. Second, consider all the positive integers which are nth powers for some n ≥ 4. The "probability" that a number m is in this set is about m^-3/4. So replace the set of fourth-or-higher powers with a random set S, which contains m with probability m^-3/4. Then the probability that a givennumber n can be written as a sum of two such elements of this set S is proportional to n^-1/2; independently, it has probability n^-3/4 of being in S. So the probability that n can be written as a sum of two elements of S and is also in S itself is proportional to n^-5/4, and so we expect finitely many examples. This isn't quite true, because the set of fourth-or-higher powers has some nontrivial structure. But it also took a couple hundred words, instead of a couple hundred pages like the real proof.

But I figured out something like this when I was in college, and I was so proud of myself! So it saddens me to learn I'm not the only one who thought of it. (It also makes me happy, though, because the idea is due to Erdos and Ulam, and there are worse people to be imitating.)

Etymology of "theorem"

Is there some connection between the etymology of "theorem" and words like "theology" or "theist"?

For "theorem" the OED says: theorem, from the late Latin theorema, from the Greek θεωρημα, spectacle, speculation, theory, (in Euclid) a proposition to be proved, from θεωρειν to be a spectator (θεωροσ), to look at, inspect. (This isn't an exact quote; I've expanded some of the abbreviations, and suppressed some of the accent marks. But if you're the sort of person who could actually answer my question you probably already knew that.)

But for the words where "the-" or "theo-" is god-related, of which there are a lot, it just says things like "from Greek θεοσ, God" and doesn't go any further. And maybe you could imagine that people "look at" or "inspect" God. Of course I recognize that the OED is not the best possible source for these things -- but I'm suspecting that someone in my audience has also noticed this apparent coincidence of words and knows the answer.

(I just want to reiterate that the title "God Plays Dice" is not a religious thing; it's alluding to the quote of Einstein, as I've written before.)

NYT on the Netflix Prize

In this week's New York Times Magazine, Clive Thompson writes about people trying to win the Netflix Prize.

Early in 2007, Netflix, the video-rental-by-mail service, made (anonymized) data on its users preferences available, and is offering $1,000,000 to the first person or team that creates an algorithm for recommending movies that makes a certain substantial improvement upon the existing algorithms. More precisely, Netflix attempts to predict the star rating, on a one-to-five scale, that users will give to a movie; the root mean square error in their old algorithm was about 0.95 stars, and they'll pay the $1,000,000 for improvement of this by 10%. (They also pay $50,000 for improvements of 1%.)

Why are they doing this? Well, Netflix recommends movies to lots of people, and they want their recommendations to be good. And it sounds like they're getting a lot more than a million dollars worth of time from the various competitors working on this; if they actually had these people on their payroll it would cost more.

It's interesting that there are certain movies that are very difficult to predict; Napoleon Dynamite is one of the examples the article gives, which won't surprise anybody who's seen it; poking around the forums on the Netflixprize.com site I found a list of movies like that, although it's a year and a half old so there's been progress since then. (Hmm, I'm not sure if I like Napoleon Dynamite -- sometimes I do and sometimes I don't.)

Apparently one of the major mathematical tools that has emerged as being useful here is singular value decomposition. I'm not surprised that some Big Fancy Linear Algebra tool was necessary, as a lot of the algorithms essentially seem to work by identifying various dimensions along which movies can vary. (Look, it's a hidden metric space!) Hmm, I wonder if the space of movies has some nontrivial topology... no, I will not get sucked into thinking about this!

Classification is hard, and libraries are not perfect

When I go to the library, even if it's just to get a specific book, I tend to browse a bit. I've found some interesting books this way.

So I was just there, and Anatomy of Integers, the proceedings of this conference, was shelved near the calculus textbooks. In particular, it was near various books that collect integrals. "Anatomy of integers" is a name that seems to be used for a certain branch of number theory that looks at the distribution of prime factors; for a nice introduction to the concept, see Andrew Granville's anatomy of integers and permutations. (This paper, still in development, talks about the analogy between the prime factorizations of integers and cycle structure of permutations. For example, the distribution of the number of cycles of a random permutation of {1, 2, ..., n} is approximately normal with mean and variance near log n; the Erdos-Kac theorem says that the distribution of the number of prime factors of a random integer less than or equal to eⁿ is asymptotically normal with mean and variance near log n. Lots of results about prime factorizations or about permutations seem to have counterparts in the other realm. Anyway, this isn't calculus! But it was with the calculus books.

Similarly, I found a book entitled Mathematical Essays: In Honor of Su Buchin, which was a volume of mathematical research articles in honor of the Chinese differential geometer Su Buchin, shelved with various books that consist of reflections by mathematicians on mathematics -- the sort of nontechnical writing that "essay" usually means.

Is there something wrong with Penn's library? Not at all. They were in the right place according to the Library of Congress Classification, but whoever does that classification seems to make the occasional error. Of course the reasons for these particular errors were obvious from the titles, which is why I spotted them. I am not sure if the classification is done by people who aren't familiar with mathematics; that would explain the integer/integral mistake, at least.

Tao's blog is soon to be a book

In the issue of the Notices of the American Mathematical Society, which arrived in the mail today, I learned that Structure and Randomness: Pages from Year One of a Mathematical Blog will be coming out soon.
I saw a draft copy of it when Tao posted it on his blog back in April; he announced the book was going to exist here and posted the draft here. The book is a collection of Tao's posts on various open problems, expository posts, summaries of lectures, and so on, and is in large part intended to be, so far as I can tell, what one might think of as an "archival" version of the blog. A lot of Tao's blog posts tend to be longer than typical blog posts, so his blog seems particularly suited for the book medium.

The title of the draft version is "What’s new - 2007: Open questions, expository articles, and lecture series from a mathematical blog", which describes the content well -- but I like "Structure and Randomness" better. Here's a long post I made back in July of 2007 on "psuedorandomness" in the primes, in large part inspired by watching a talk Tao gave entitled "Structure and Randomness in the Prime Numbers".

Worst math joke I've heard today

A joke that I've seen in several places today (first from my friend Karen): "An infinite number of mathematicians walk into a bar. The first one orders a beer. The second orders half a beer. The third, a quarter of a beer. The bartender says "You're all idiots", and pours two beers."

I can "improve" this joke. An infinite number of mathematicians walk into a bar. The first one orders a beer. The second orders two beers. The third orders three beers, and so on. The bartender takes a twelfth of a beer from the first one and they all walk away happy.

(Why, you ask? Because ζ(-1)=-1/12.)

People on Slashdot don't know probability

This is a few days old, but I didn't mention it when I first saw it: Microsoft Exploit Predictions Right 40% of Time, from Slashdot. (The link is to Slashdot; here's the original article.)

Apparently Microsoft has a mechanism for predicting which parts of its code are most likely to be exploited by malevolent hackers; they made nine predictions in October, and four actually got exploited. Of course, the Slashdot commentary is filled with reflexive Microsoft-bashing, and people pointing out that that's worse than flipping a coin. But the correct comparison isn't to flipping a coin. The correct comparison is to the number of hits that would have been obtained if Microsoft had picked nine pieces of their code at random, which presumably is much less than four. There are a few people in the comments trying to put numbers on this, but nothing that really sounds informed.

Folklore for divergent series

From Emanuel Kowalski, quoting what is apparently folklore: "The only 'truly' divergent series is the harmonic series."

The idea is that one can assign a value somehow to basically any other divergent series; see the link for a more thorough explanation.

(But don't tell the calculus students! They already can't remember the harmonic series is divergent.)

And I usually think of the harmonic series as being "equal" to log n, although of course log n isn't a number. So I amend the folklore, somewhat facetiously: "there are no divergent series."

Navigability of complex networks

Here's an interesting idea, which falls in the very large set of "things I thought about but have no idea how to implement": M. Boguna, D. Krioukov, kc claffy. Navigability of Complex Networks, arXiv:0709.0303v2. (Published in the November 16, 2008 issue of Nature Physics; I learned about it from physorg.com.) The basic idea is that it is possible to navigate in complex networks by navigating in some underlying hidden metric space. Nodes are close together in the hidden metric space if they are similar to each other in some abstract sense, and they are more likely to be connected to each other in the network if they are closer together.

To take an example where the metric space isn't hidden, one navigates between airports by thinking about distances on the surface of the Earth; if you route greedily, by at each airport taking the flight which gets you closest to where you want to go, you usually will end up at your destination. Of course, this isn't a priori true -- you could get stuck in an infinite loop -- but the point is that real networks seem to obey this.

This is something that I think a lot of people have an intuitive sense of. For example, there are people I've met that when I meet them, I want to ask "why haven't we met before?" -- some combination of shared geography and shared interests makes it seem like we should know each other. (In my own life, there is at least one case of somebody who I never met when I was an undergrad, though there were plenty of amusing stories about mutual friends of ours that we'd both heard; we met shortly after I moved back to Philadelphia for grad school.)

A couple of questions on the mechanics of writing mathematical papers

I'm writing a paper, and of course this requires the use of LaTeX. As many of you know, the way one creates cross-references inside a LaTeX document is a two-step process. First, you insert the command \label{big-important-theorem} where your Big Important Theorem is in the paper. Then when you want to refer to your theorem, you write something like "And as a consequence of Theorem \ref{big-important-theorem} we can prove Corollary \ref{million-dollar-problem}, and so I claim to be the winner of a million dollar prize."

No, I have not written that sentence. Nor do I plan to. In fact, I would add "claims to be the winner of one of the Clay prizes in the body of the paper" to John Baez's crackpot index. Baez couldn't have put that in his list, because it was written in 1998. He does mention the Nobel, though, which carries a similar monetary value.

But this leads to a question -- how do you label your theorems, equations, etc. in your own LaTeX code? I try to come up with names that reflect what the labeled object is about, but this isn't so easy, because sometimes there are lots of objects that are "about" the same sort of thing. I'm tempted to just find some source of extra-mathematical names. So I could name my theorems \label{market}, \label{chestnut}, \label{walnut}, \label{locust}, ... (Philadelphia streets), say. Of course, this sequence has the disadvantage that the streets come in order; a set of names with no natural order is probably better, because then I won't feel like I'm moving things out of order when I move them around.

On a related note, often one sees bibliographical references of the form
[Be74] Edward A. Bender. Asymptotic methods in enumeration. SIAM Review,
Vol. 16, No. 4, October 1974.
I prefer this form to the form where [Be74] is replaced by a number, because if something is cited more than once in the same paper, I only need to look at the reference once; the second time I see [Be74] in the paper I know it's the paper by somebody whose name starts with Be, written in 1974. (And if it's a paper I've heard of already, sometimes I don't have to look at the citation at all.)

But what's the convention for picking the letters to be used? First two letters of the name seems common for a single-authored paper, but by no means universal; I've definitely seen one-letter citations, the problem being that if you have a reasonably extensive bibliography you'll want to cite two different authors with the same initial. I'm currently using just the first letter of each name for multiple-author works -- [FS08] for Flajolet and Sedgewick's Analytic Combinatorics (coming out sometime in December, preorderable now! and readable online!), for example. I've tried to reverse-engineer whatever convention there is from other people's reference lists and I can't. Is there actually no convention?

Of course, there is no need for a convention, as long as each work cited has a unique identifier.

Monopoly: electronic banking edition

There is, I just learned from a television commercial, a Monopoly Electronic Banking Edition.

The children of the future, it appears, will perhaps not be able to claim that Monopoly is educational because it requires them to do math. (Although I'll admit that I always found Monopoly frustrating because other people's mental math is slower than mine.)

Somewhat more seriously, are the children of the future (or, perhaps, the present) going to feel that they have less reason to learn mathematics because they don't deal with cash? That seems like it would be something that would motivate at least some students to learn basic arithmetic.

How does the orbit of the moon look?

The orbit of the moon around the sun doesn't look like what you'd expect.

(Although now that I've told you this, you might think a little harder about what the orbit looks like.)

The geometry of a game

From 360: Shinju, a geometrical game. You're given an arrangement of shells in some of the squares of a square grid. One of the shells hides a pearl. Your goal is to find it, opening at most four shells. When you open a shell, it either contains the pearl, or a number. That number is the distance to the pearl, in the (T)chebyshev distance.

There's a nice little result hiding here:
Problem 1: Given any arrangement of shells, prove that it is possible to find the shell in four clicks.
Since you always get four clicks (at least as long as I played), the game becomes trivial if you can find a constructive proof of that fact. (If you're the sort of person that likes to rack up points in video games, though, I think you get more points if you don't use all your clicks -- so how do you set things up so that you're likely to solve the puzzle in less than four clicks?)

Problem 2: Generalize (to higher dimensions, different metrics, etc.)

In which I buy the Princeton Companion to Mathematics

I cashed in 5.793 kilograms of assorted coins today at the bank. That's $115.19, for a density of $19.88 per kilogram; I know the weight because the bank's coin counting machine gave a receipt that had the numbers of each type of coin I received. I then immediately proceeded to the bookstore and purchased the The Princeton Companion to Mathematics (That was $106 with sales tax; perhaps I should have bought it from Amazon.com, where it's cheaper. Oh well, it's too late now. But at ten cents a page it's still a good deal.) I told myself I wouldn't buy it, but I'm doing some private tutoring on the side, and so there's a bit of extra money floating around, and I couldn't help myself...

I want to compliment the design of it; the side of the book which faces out on the shelf has "The Princeton Companion to" in small letters and then "Mathematics" in large letters, perhaps giving the impression that the book contains all of mathematics. This is not true, but from the portions of it I've seen online and the part I've read so far, it seems to admirably solve the optimization problem of squishing down mathematics to an object that only weighs five pounds. That's less than the coins I hauled to the bank to get the cash I paid for it! For links to various reviews, see this entry from Tim Gowers' blog. Gowers is the editor, and also wrote substantial parts of the book, although it has many other contributors; you can play the party game "how many of these names do I recognize?" I was interested to see that I recognize many more than I would have when I started grad school.

Yes, I'm actually trying to read it cover-to-cover. Like many mathematicians, there are a bunch of things that people seem to assume I'm familiar with, but I only heard about very briefly in some course in my first year of grad school in which I was holding on by the skin of my teeth. Indeed, this is one of the uses that's recommended in the introduction! I will resist the urge to turn this blog into a Companion to the Princeton Companion to Mathematics.

Etch-a-Sketch graphing

Mr. K points out that the Etch-a-Sketch toy helps students understand graphing. You turn one knob and the x-coordinate changes; you turn the other knob and the y-coordinate changes.

That's a good point -- but I was surprised to learn that eighth graders (that's who Mr. K teaches) are familiar with the Etch-a-Sketch.

Combinatorics of universal remotes

From the wrapping a univeral remote I recently bought: "Controls VCR/DVD combos, TV/VCR combos, and TV/DVD combos!"

This is because it controls two devices, and those are the three types of device that people have. But I guess "controls two devices" doesn't work from a marketing standpoint, so they have to list all 3-choose-2 subsets. (And I also find elsewhere on the packaging "manage up to 8 separate devices with one remote control". Something doesn't add up here.)

They can take our labs, but they can't take our brains!

Chemistry hobbyists face a labyrinth of local and state regulations -- an article about how increasing regulation makes amateur chemistry more and more difficult. Via slashdot.

Fortunately mathematics is not so easily regulated. Although if mathematics comes to rely increasingly on computers to do the "dirty work", then one can imagine a future where amateur mathematics is concentrated in certain fields -- the fields which don't require computation -- if high-powered computers become regulated. But in the end mathematics is pure thought, and they can't regulate what goes on inside our brains.

(I studied chemistry as well as mathematics in college. I would never have laboratory equipment in my home. But this is because whenever I touched laboratory equipment it broke, which is why I got out of chemistry. In the hands of a competent chemist, there's nothing to fear.)

A quirk of electoral apportionment

I was curious: how will the electoral vote apportionment change between now and 2012? (Reapportionment is done after each census, and censuses take place in years divisible by 10; the apportionment takes effect the year after the census. Thus the 2004 and 2008 presidential elections were done under one apportionment, and the 2012, 2016, and 2020 elections will be done under another one.)

I don't know (my first attempt at programming the apportionment gave some really strange-looking results) but I wanted to share an amusing fact.

Each of the 50 states receives a number of electoral votes equal to its number of Representatives, plus two. So the question is really one of determining the number of Representatives that each state gets. The way this works is as follows. First, each state receives one seat. Then, let the populations of the states be P₁, P₂, ..., P₅₀; let

Q_i,j = P_i / (j(j-1))^1/2

for 1 ≤ i ≤ 50 and all positive integers j. Sort these numbers, and take the 385 largest of these numbers. Now state i (the state with population P_i) gets r = r_i representatives, where r is the unique integer such that Q_i,r is one of the 385 largest Q's, and Q_i,r+1 is not. (385 is 435-50; 435 is the number of seats in the House of Representatives, and 50 seats were already assigned in the previous step, one for each state.) Essentially, this assigns the seats in the House "in sequence", so we can speak of the 51st seat, 52nd seat, ..., 435th seat.

So what if there's a tie for 385th place in that ordering? This can occur, of course, if two states have the same population, and I bet some tiebreaker is written into the law. But what if two states have different populations, but after dividing by the square root factor, two of the Q_i,j are the same? Surprisingly, this can happen. Let P₁ = 6P₂. Then it's not hard to see Q_1,9 = Q_2,2; that is, state 1 gets its ninth seat "simultaneously with" state 2 getting its second seat. More generally, if

P₁ / (m(m-1))^1/2 = P₂ / (n(n-1))^1/2

then state 1 gets its mth seat simultaneously with state 2 getting its nth seat. Note that P₁/P₂ is rational. So a tie can only occur when (m(m-1)/n(n-1))^1/2 is rational; when does this happen?

When n = 2, this amounts to asking when (m(m-1)/2) is a square; this happens for m = 2, 9, 50, ... (the indices of the square-triangular numbers in the sequence of triangular numbers) So one state can receive its second seat at the same time another one gets its 9th seat, its 50th seat, ... if the larger state has 6, 35, ... times the population of the smaller one.

Somehow I doubt the law covering apportionment has a provision for this. I suspect the provision taken would be similar to what happens if there's a tie in an election; I know there are some jurisdictions that just flip a coin in that case.

Edit, 10:53 pm: Boris points out in the comments that somebody's done the projection. Texas gains 4, Florida and Arizona each gain 2; the Carolinas, Georgia, Utah, Nevada, and Oregon each gain 1. New York and Ohio each lose 2; Massachusetts, New Jersey, Pennsylvania, Michigan, Illinois, Minnesota, Iowa, Missouri, Louisiana, and California each lose 1. At first glance this shift seems like it would favor the Republicans in the presidential race; nine of the seats created are in states that voted for McCain in '08, and only two of the seats destroyed are. But I'm not sure about this analysis; states are made of people, so as a state's population grows or shrinks its political makeup changes as well. Maybe Nate Silver will have something to say about this?

The notion of "typical" doesn't behave nicely

Matt Yglesias makes an interesting point. The "typical" American is white, in that more than half of all Americans are white. The "typical" American is Christian, in that more than half of all Americans are Christian. But does this mean that the "typical" American is a white Christian, in that more than half of all Americans are white Christians? Not necessarily; I don't have the numbers.

Moreover, the "typical" white Christian votes Republican. Thus typical people vote Republican, so the Republicans should have won last night. But they didn't.

The point is that most people are "typical" in some ways, but few people are "typical" in all ways. And a party that is based around just people who are "typical" in all ways (note that I'm not saying this describes the Republican party) is doomed to fail, because most people are unusual along some dimension. I don't think this deserves the name of "paradox", but it's just something worth keeping in mind about How Statistics Work.

We win!

I heard that the featured articles at Wikipedia were the articles on McCain and Obama, and for the first time ever they had two featured articles at once.

So I went over to check.

But Wikipedia runs on GMT... and so it's Wednesday there. The featured article is Group (mathematics).

The "We" in the subject line is "mathematicians", of course.

Vote!

Scott Aaronson points out that the probability of your vote changing the results of the election scales like N^-1/2, where N is the number of people. But the amount of change your vote creates, if it tips the election, scales like N. So the expected amount of change you will cause, by voting, scales like N^1/2. That's a big number, so you should vote. If you live in a big country, you should vote more, although that's irrelevant; if any other country is voting today, the US media has ensured that I don't know that.

Of course, N^1/2 seems a bit high, and it comes from modeling people as flips of a fair coin; Aaronson points out that under a more realistic prior (due to Andrew Gelman), the expected probability that your vote flips the election is N^-1, so the expected amount of change your vote causes doesn't depend on the size of the country.

I won't "officially endorse" anybody. But one of the candidates in the present election trained as a lawyer, taught in a law school for a while, and likes to compare himself to a certain Senator from Illinois. That senator, in order to equip himself to understand the law better, studied Euclid. Being a mathematician, I think this is pretty cool. Who I'm voting for is left as an exercise for the reader.

AMS: Math in the Media

The AMS puts together a roundup of math in the (mainstream) media.

I think I may be the last person to know this, but in case I'm not, here it is.

JSTOR question

I just googled JSTOR in order to find it. (Of course, it's at jstor.org.)

Anyway, the Google result I get reads (with links omitted):

JSTOR: Home
Scans of print journals, with 10 major math journals (requires subscription).
www.jstor.org/ - Similar pages - Note this

Does Google know I'm interested in math, or does it say this to everybody?

As it turns out, I was in fact looking for an article from the Bulletin of the American Mathematical Society, so telling me there were math journals in there worked out well for them.

A thought on expectation

Political campaigns should not campaign in such a way as to maximize their expected number of votes. Rather, they should campaign in such a way as to maximize their probability of winning.

Early in a campaign, these are pretty much the same thing, because one doesn't know how things are going to play out; late in a campaign they diverge. The candidate that's behind in the polls should, perhaps, start doing things that are, in expectation, Bad Ideas. If there were something that McCain could do that had a 1% chance of swinging 10% of the vote to him in the next 24 hours, and a 99% chance of scaring all the voters away, he should do it. (For example, let's say McCain turns out to secretly be an extraterrestrial; we probably don't want to be ruled by extraterrestrials, but who knows, we might change our mind? Of course, I'm being deliberately silly here.)

This is somewhat analogous to what happens in sports; strategies change late in a game. In the early innings of a baseball game you play, basically, in such a way as to maximize the difference between the expectation of your number of runs and your opponents' number of runs. In the late innings, when you have a better idea of how many runs you need, you change your strategies. See, for example, the bottom of the ninth inning of Game 3 of the World Series; tie game, bases loaded, nobody out. The Rays bring in one of their outfielders to create a fifth infielder; the idea is essentially that they want to maximize the probability of the Phillies scoring zero runs, and if the ball gets into the outfield a run is scoring anyway. (As it turns out, the Phillies won that game -- on a hit in the infield.) Of course, nobody saw that because it happened at two in the morning. Things are different when you're playing for one run.

Basically, what's happening as I write this is that Obama is running out the clock. (Yes, baseball doesn't have a clock. But Obama's a basketball player, so I think he'd like this metaphor.)

What politics and sports have in common, of course, is that there's a huge difference between second place and first place. If you're a company of some sort, does it matter if you sell 1% more or 1% less than your competitor? Not really, although it might have meaning for your pride. But if you're a politician, 1% of the vote makes a big difference.

Conditional probability is subtle, part 2

Nate Silver returns to the idea of conditional probability: he's saying Pennsylvania is "in play" in this election, not because the polling in Pennsylvania is close, but because conditioned on the election being close, Pennsylvania is close. In general, I've heard quite a few people argue that the candidates should focus on the states that would be close if the election were roughly tied, not the ones that actually are close, because the details of which state a candidate deliberately tries to sway things in only matter in a close election anyway.

Unfortunately, subtleties like this seem to be lost on some of Silver's commenters.

In case you're wondering, my last post titled "Conditional probability is subtle" had nothing to do with politics.