31 March 2008

Kids are better at algebra than you think

Word problems take place in a graded ring, from (the recently relocated) Mathematics under the Microscope (Alexandre Borovik), via The Unapologetic Mathematician (John Armstrong).

In short, Borovik claims that elementary school word problems take place over $\mathbb{Q}[x_1, x_1^{-1}, x_2, x_2^{-1}, \ldots, x_n, x_n^{-1}]$, where the xi represent different things that could be added. In this formalism, it makes sense to add, say, apples and oranges, going against the usual rule that you're only allowed to add quantities with the same "dimension". (Indeed, Borovik illustrates the idea with an example of this nature.)

I'm reminded of "dimensional analysis" as taught in, say, introductory physics classes, where we only allow monomials to have meaning, namely that the monomial x ma kgb secc measures some physical quantity with dimensions LaMbTc where L, M, T stand for length, mass, and time. (For example, in the case of speed, a = 1, b = 0, c = -1.) I can't think of situations in physics where one deals with a quantity of the form, say, a kg + b m. Is this because they don't exist, or because I don't know as much physics as some people?

30 March 2008

Bringing Down The House

From the MIT News Office: Film loosely based on MIT blackjack team opens Friday. (That's Friday, March 28.) The film is based on the book Bringing Down The House. I haven't seen it, and I probably won't, because it hasn't gotten the best reviews. Also, I generally tend to dislike movies that take place in fictionalized versions of places I know; they look all wrong. (A Beautiful Mind and Good Will Hunting come to mind. Also, 10th and Wolf, which has nothing to do with math, but is set around the corner from where I was born in Philadelphia, and was filmed in Pittsburgh.)

Anyway, the press release says:
Most notably, the character played by Kevin Spacey, portrayed as an MIT professor, is entirely fictional. While his irresponsible acts may enliven the Hollywood script, they are entirely unrepresentative of the Institute.
I wonder if their legal department told them to say that. They also point out that real MIT students are good at math too! This is true.

It's almost baseball season again...

A Journey To Baseball's Alternate Universe, in today's New York Times, by Samuel Arbesman and Steven Strogatz.

Arbesman and Strogatz ask the question: how likely is it that some major league baseball player, at some point, would have had a 56-game hitting streak, as Joe DiMaggio did in 1941?

I've seen attempts to determine this before, but they're usually handwaving things that start out by saying "assume everybody bats .266 and gets 3.83 at-bats a game" (actual averages for the 2007 National League), and then let's compute the probability that such a player has a 56-game hitting streak in any given sequence of 56 games. In this case that's easy; the average player gets has a probability (1-.266)3.83 = 0.306 of not getting a hit in any given game, thus a probability 0.694 of getting a hit in any given game; raising this to the 56th power tells you that the average player has a probability of 1.31 in a billion of getting hits in, say, the 56 games starting tomorrow and ending sometime in early June.

So what's the expected number of 56-game hitting streaks this season, according to this model? There are 107 ways any given player could get a 56-game streak -- starting in game 1, 2, ..., 107. So the expected number of 56-game streaks for Joe Qankee (yes, I'm reviving the Qankees) is this probability times 107, or 1.41 × 10-7. Now, assume there are eight Qankees that play every day. (The Qankees are an extraordinarily healthy National League team. The fact that their name rhymes with that of the American League team that DiMaggio actually had his streak with is purely coincidence.) The expected number of 56-game hitting streaks by Qankees this season is thus 1.13 × 10-6. (Note that this is not the probability that one of them has such a streak. A 57-game streak would get counted twice here, a 58-game streak three times, and so on. However, it is an upper bound for the probability of a Qankee having a streak of at least 56 games.)

Now, there have been something less than three thousand "team seasons" in Major League Baseball (one team playing for one season). So the expected number of 56-games streaks is bounded above by (1.13 × 10-6) × 3000 = 0.0338, or about one in 300.

But we've had one. That seems like a lot.

What's the problem here? Well, the average player isn't the one that's going to have that streak. A .280 hitter will put together a streak in 7.40 56-game frames out of every billion. A .300 hitter, in 69 out of every billion. A .320 hitter, in 498 out of every billion. (And I'm still assuming such a player only gets 3.83 at-bats a game; that's probably not true, because the player who hits well will lead his team as a whole to have more at bats.) But an equally bad hitter doesn't drag down the expectation nearly as much. I've ignored batting order (which Arbesman and Strogatz did take into account, implicitly; their inputs for each player are the total number of hits, number of games played, and number of plate appearances, and number of plate appearances varies with position in the batting order).

Rather than making some assumptions on how batting averages are distributed (which would probably be wrong, and even if they were right in the peak of the distribution would still be wrong because what really matters is the tails), I'll defer to Arbesman and Strogatz. Their method is to simulate the entire history of baseball 10,000 times, which is enough to get a nice basically-smooth curve for the distribution of the length of the longest streak. The median length of the longest streak, in their simulations, is 53 games.

Simulation might not be entirely necessary, though. It's routine to calculate the distrbution of the length of the longest streaks in sequences of biased coin flips; aggregating that information together is a little harder. But I don't care enough to do it, so I'll stop here.

29 March 2008

Furstenberg's topological proof of the infinitude of primes

I just learned about Furstenberg's proof of the infinitude of primes (link goes to Wikipedia article); it was published in 1955 in the American Mathematical Monthly. (Link goes to JSTOR. Full citation: The American Mathematical Monthly, Vol. 62, No. 5. (May, 1955), p. 353. If you have to do any work to get the article from JSTOR -- for example, logging in through a proxy server because you're at home instead of on campus -- or you don't have JSTOR access -- don't worry, you're not missing much. The article's a third of a page, and the Wikipedia article is probably longer than Furstenberg's original.) Surprisingly, I hadn't seen this before.

Anyway, here's my version of the proof: topologize the integers by taking the (doubly infinite) arithmetic sequences as a basis. (The only thing that needs checking here, to show these form a basis, is that the nonempty intersection of two basis elements contains a basis element; this is true since the intersection of two arithmetic sequences is another arithmetic sequence.) Consider the set which consists of all the integers except -1 and 1; this is the union of the sequences pZ over all primes. Now, there are no nonempty finite open sets in this topology, so there are no cofinite closed sets except Z itself. Thus the union of the pZ isn't closed. So it can't be an union of finitely many closed sets, since finite unions of closed sets are closed. So there are infinitely many sets pZ, and thus infinitely many primes!

(Thanks to an anonymous commentator for pointing out some errors.)

28 March 2008

Open and closed?

At Language Log there's a post about how English-speakers use "open" and "closed", which are not grammatically the same sort of thing, in opposition to each other -- "open"/"close" or "opened"/"closed" would, on the surface, make more sense. (Compare French ouvert and fermé, which are both past participles.)

I won't try to summarize the linguistic content of the post; I'm not a linguist, although I did go through a phase where that seemed interesting.

But in mathematics-land, open and closed aren't even opposites, in the sense that open means not-closed and closed means not-open. Of course the complement of an open set is closed, and vice versa, but that's a more complicated relationship, because now we're talking about two sets, not one. This is one of about a zillion examples of how we take perfectly good natural-language words and give them specific meanings (group, ring, field, set, class, ...), which may or may not be preferable to making up entirely new words as some other fields (biology comes to mind) prefer.

The Mandelbrot monk

The Mandelbrot Monk, Udo of Aachen (1200-1270), began developing probability theory, computed an approximation of the Mandelbrot set, and like some other people got a suspiciously good approximation for π by stick-throwing.

27 March 2008

Stuff mathematicians like?

You probably by now know about the blog Stuff White People Like, which talks about stuff white people like.

By "white people", the blog doesn't mean all white people, but rather white urban twenty- and thirty-somethings with money to burn.

Stuff white people like (according to the blog) that I'd guess a lot of mathematicians also like include coffee (if you don't know why, you're probably not a mathematician), "Gifted" children (lots of mathematicians probably were), Apple products (mostly judging from what sort of computer colloquium and seminar speakers are running, although this could be skewed by the fact that Apple users, being in the minority, are probably more likely to bring their own machine), not arts degrees (arts degrees apparently make people more interesting to talk to at parties, a concept entirely foreign to us), graduate school (although it seems to be humanities PhD programs that they're referring to), and bad memories of high school.

There are also a lot of less-good imitations: Stuff Educated Black People Like, Stuff Lesbians Like, Stuff Gay Guys Like, Stuff College People Like, Stuff Asian People Like, Stuff White Trash People Like, Stuff Unimaginative Bloggers Like, and perhaps others.

But what about "Stuff Mathematicians Like"? I know that I wouldn't do a good job with it -- but someone should. I'll get you started -- the set of stuff mathematicians like includes coffee, Rubik's Cubes, saying things are trivial, being proud of the uselessness of one's work, and the prefix "co-". (So what is "ffee"? Okay, there's another thing mathematicians like -- bad jokes.) Feel free to name other elements of this set.

26 March 2008

Largest icosahedron ever?

Biggest icosahedron ever?

Some MIT students (I used to be one) built a 20-sided die in honor of Gary Gygax, the recently-dead inventor of Dungeons and Dragons.

Do you know of any physically larger icosahedron? (And, for that matter, how large is this one? I'm guessing maybe eight feet high, but I'm really just making that up. The building behind it is about four stories, but none of the other relevant distances are apparent.)

(Via Eric Berlin.)

25 March 2008

March Madness upsets

So it's that time of year when March Madness, the NCAA's 65-team college basketball tournament, happens. Lots of betting on this tournament takes place; this usually takes the form of filling out a bracket, and then entering a pool with one's friends where the person who has the "most correct" bracket is the winner. (I suspect most of my US readers are aware of this, but I have lots of non-US readers.) "Most correct" is usually judged by who named the winners of the most games correctly, with some sort of weighting that counts naming the correct winners of later games in the tournament more heavily.

The teams are divided into four groups of sixteen (there are 65 teams, because the two weakest teams in the field play a single game to get things started), and the teams in each group of sixteen are "seeded" 1, 2, ..., 16, with 1 being the perceived best team and 16 being the worst. In the first round of the tournament the #1 team plays the #16 team, the #2 team plays the #15 team, ..., the #8 team plays the #9 team in each group of 16.

One often hears that, say, teams seeded 10 or 11 routinely beat teams seeded 7 or 6, respectively. Fair enough. But therefore it's often claimed that in filling out a bracket one should pick one of those #10 or #11 seeds to win. Not so! Sure, in the average tournament one #10 seed (out of four) might win. But which one?

This is an example of the more general principle that given large enough samples, some rare event will happen... but which one? That's not at all obvious.

Also, Bill James (of baseball analysis fame) wrote an article on when the lead in a college basketball game is safe. Basically, a lead of N points is "safe" if the time in the game remaining is less than kN2 for some constant k; this is what one would expect if scoring can be modeled as a random walk, which seems reasonable.

And you've got to love this quote:
A heuristic could be loosely defined as a mathematical rule that works even though no licensed mathematician would be caught dead associating with it.


As you may have guessed from this post, and the somewhaht desultory nature of the sports content, I'm not really a big basketball fan. But the Red Sox and the A's played a regular-season game this morning in Tokyo. And I've got Phillies tickets for next week.

24 March 2008

Top 5 Reasons It Sucks to Be an Engineering Student

Top 5 Reasons It Sucks to Be an Engineering Student, from Wired, via Slashdot.

I think a lot of the same ideas -- poorly written textbooks, relatively non-inflated grades, etc. -- apply to mathematics education (at least in some places) as well. By the way, I'd argue not for grade inflation in math and science courses, but for grade deflation in the rest of the curriculum, because when it gets to the point where there are only, say, three grades that one can reasonably give (A, A-minus, or B-plus) that's just silly. (I even think it's silly for graduate classes; in some courses in my program everyone gets A's. Why even bother making the professor fill out the form with the grades on it? I'd support graduate classes not having grades, which from what I understand is the norm at some places.)

Thankfully, in five weeks I will be done taking classes (for credit) forever.

23 March 2008

Why is the 3x+1 problem hard?

Why is the 3X+1 problem hard, by Ethan Akin, via Anarchaia.

You might also be interested in my previous post on the 3x+1 problem.

And welcome slashdotters! Will there be more or less of you than people coming in from reddit for my post on "Why g = π2"?? (I don't know yet. I don't know enough about the shape of a "typical" slashdot traffic spurt to guess.)

22 March 2008

Names of mathematicians in the MSC

Dave Rusin has a list of names of mathematicians which appear in the MSC scheme. (That's the "Mathematics Subject Classification." I almost called it the "MSC classification" but managed to stop myself.) For reference, here's the 2000 MSC. (Rusin's file treats the 1991 version.) The idea is that these must be Important Mathematicians because some subfield of mathematics has been named after them, for the most part.

Rusin claims that Abel is the only person usually given the honor of having his name lowercased ("abelian", not "Abelian"). I have a sense that "euclidean" also occurs, though I may be thinking of the French usage.

The most amusing one, to me, is that "Monte Carlo" is named after a person -- Charles III of Monaco -- who was as far as I know not a mathematician at all. Amerigo Vespucci is also on the list; 01A12 is the history of mathematics and mathematicians of indigenous cultures of the Americas. If I had been compiling the list I'd probably have missed that.

Rusin also calls Fibonacci a "rabbit-farmer". I'd laugh, except I'm pretty sure at least one of my students also thinks this.

When are two algorithms the same?

When Are Two Algorithms The Same?, by Andreas Blass, Nachum Dershowitz, and Yuri Gurevich. Via Lambda the Ultimate and Anarchaia.

People usually regard algorithms as more abstract than the programs that implement them. The natural way to formalize this idea is that algorithms are equivalence classes of programs with respect to a suitable equivalence relation. We argue that no such equivalence relation exists.


My first thought here -- and this is unusual for me, since I'm basically a discrete mathematician -- is that maybe the space of programs is "effectively continuous", in the same sense, that, say, reality is "effectively continuous" but actually has a discrete nature if you look closely enough, thanks to quantum physics. So the right thing to do would be to topologize the set of programs, so you can say that algorithms X and X' are "close to" each other, or perhaps to put a metric on it. But I naturally imagine that, say, if two programs differ by some small number of small changes then they would have to be considered the "same program" if we were looking for an equivalence relation. Imagine a graph whose vertices are programs, and two programs are connected by an edge if they differ by some small number of small changes; then we're naturally led to think of "algorithms" (if they are equivalence classes of programs) as connected components of that graph. But how do we decide what number of changes to allow, or how large they can be? Basically, the relation on the set of programs "expresses the same algorithm" doesn't seem to be transitive, as the authors point out, so "equivalence relation" is the wrong idea.

By the way, I speculate that calling the space of programs a metric space (say, with the metric induced from the graph I alluded to before) is wrong as well, but in a different way -- how does one assign lengths to the edges? That seems a bit subjective and squishy. Topology's the way to go here, although it's not like anybody's holding their breath waiting for an answer to this question. And it sort of feels like a question about moduli spaces (link goes to a post by Jordan Ellenberg), although I know next to nothing about those.

This reminds me (and the authors) of the question asked in Tim Gowers' post when are two proofs essentially the same. (In fact, is this the same question?)

21 March 2008

Easter's early this year. Deal with it.

Family holidays ruined by earliest Easter in 90 years (from the Daily Mail).

About halfway down, a formula is given:

It may look daunting to non-mathematicians but the fiendishly complex formula used to work out when Easter actually falls is:

((19*t+u-w-(u-(u+8)\25)+1)\3)+15)mod30)+(32+2*x+2*y-(19*t+u-w- (u-(u+8)\25)+1)\3)+15)mod30)-z)mod7)-7*(t+11*(19*t+u-w(u- (u+8)\25)+1)\3)+15)mod30)+22*(32+2*x+2*y-(19*t+u-w-(u- (u+8)\25)+1)\3)+15)mod30)-g)mod7)+114)\31


Um, do you understand that formula? I think I know why some of the numbers are there -- the 31 at the end probably has something to do with the length of months, the 7 with the length of weeks, and the 19 with the Metonic cycle. Also, any sane mathematician wouldn't write the formula like that. First, there are repeated subexpressions like that ((u + 8) \ 25 + 1); I'd just call that by some other name and be done with it. Second, the formula just sits there in the middle of the article; this gives people the idea that mathematicians are freaks of nature who think in formula. What do the variables mean?

If you're curious, there is an algorithm at the Calendar FAQ. Easter is the first Sunday after the first (computed) full moon on or after the vernal equinox (calculated, and assumed to be March 21). The algorithm reflects this. First, assume that the Metonic cycle, which says that lunar phases repeat every 19 solar years, is exactly correct in the Julian calendar. (The algorithm was invented back when the Julian calendar was used.) Then make two corrections, one for the fact that the Julian calendar includes leap years that the Gregorian doesn't (years divisible by 100 but not 400) and one for the fact that the Metonic cycle's a bit off. (The expression "(u+8)\25" in the formula above comes from the second correction.) This gives the date of the full moon. Presumably if you've gotten this far you already know what the days of the week are.

Anyway, the cycle of Easter dates repeat themselves every 5,700,000 years. The cycle of epacts (which encode the date of the full moon) in the Julian calendar repeat every nineteen years. There are two corrections made to the epact, each of which depend only on the century; one repeats (modulo 30, which is what matters) every 120 centuries, the other every 375 centuries, so the air of them repeat every 300,000 years. The days of the week are on a 400-year cycle, which doesn't matter because that's a factor of 300,000. So the Easter cycle has length the least common multiple of 19 and 300,000, which is 5,700,000.

This whole computation is known as the computus (Latin for "computation"; I guess it was just that important at the time). Not surprisingly, Gauss had an algorithm which is much easier. Let Y be the current year. Then take:

a = Y mod 19

b = Y mod 4

c = Y mod 7

d = (19a + M) mod 30

e = (2b + 4c + 6d + N) mod 7

where M and N are constants depending on the century that don't look that hard to calculate, and which I assume are the corrections I alluded to above; the Wikipedia article gives them in a table. Then Easter falls on the d+e+22 of March or the d+e-9 of April, with certain exceptions which move it up a week when this algorithm gives a very late date for Easter. Basically, d finds the date of the full moon (so M is something like the epact) and e find the day of the week. In the case of this year you get a = 13, b = 0, c = 6; a table gives M = 24, N = 5 for this century, so d = 1, e = 0, and Easter is on the 23rd of March.

As for when Easter usually falls, well, go back to the original description: Easter is the date of the first Sunday after the first full moon on or after March 21. To me this seems like adding two random variables -- the number of days between March 21 and the first full moon, which is roughly uniformly distributed over [0, 29], and the number of days between that moon and the next Sunday, which is uniformly distributed over [1, 7]. There are 210 ordered pairs in ([0, 29] × [1, 7]). One of them sums to 1, giving an Easter date of March 22 in about one year out of 210. Two sum to 2, giving an Easter date of March 23 in two years out of 210. Three sum to 3 (March 24), ..., six sum to 6 (March 27). Seven sum to each of 7 through 30, giving Easter dates of each of March 28 through April 20 in seven years out of 210. Six sum to 31, giving April 21 in six years out of 210, ..., one sums to 36, giving April 26 in one year out of 210.

Indeed, this is basically what computations show, except that for some reason, when the methods given above call for Easter to be on April 26 it gets moved up to April 19. But basically the distribution of Easter dates is just a convolution of two uniform distributions! The Wikipedia article on the computus has a nice graph.

And I have no sympathy for the people quoted in that article. They've known this was coming since 1752, when the UK changed over to the Gregorian calendar. (It perhaps says something about me that I have more sympathy for the bakeries with lots of Irish patrons that are unhappy because Easter was only six days after St. Patrick's day this year.)

19 March 2008

Early retirement makes you live longer? Or kills you? Who knows?

"Staying on the job five extra years lowers your risk of dying by ten percent." -- on a local TV newscast.

The point here is that early retirement causes one to die earlier, even if you're healthy. That seems believable.

But we all have, of course, a one hundred percent risk of dying.

Presumably they meant that it lowers the risk of dying by ten percent per year. I don't want to try to get more data from that, though, because even that's a big assumption; the numbers in this context might be meaningless.

What I would want is a statement of the form "staying on the job five extra years raises your life expectancy by X years". (For what it's worth, a bit of poking around the internet doesn't give a value for X, but does give the impression that some people think X is negative.)

Who proved the rationals are countable?i

Who proved the rationals are countable? (No fair looking this up.) If you're not sure, guess.

I'm wondering if people know the answer to this one; via some informal surveying it seems less well known that I'd expect. Then again, I didn't know it.

On a related note, the usual proof that N × N is countable (where N = {1, 2, 3, 4, ...} is the natural numbers) goes by giving an explicit enumeration of the pairs of natural numbers, namely,

(1,1), (2,1), (1,2), (3,1), (2,2), (1,3), (4,1), (3,2), (2,3), (1,4), ...

where we list all pairs of integers summing to 2, then to 3, then to 4, then to 5, ... Thus we list pairs of integers in order of their "size". Alternatively, we're enumerating pairs of sets in order of their "size", where sets are only distinguished up to cardinality.

Combinatorialists are often concerned with classes of objects where there are a finite number of objects of size n for any integer n... of course this means that any such class is in fact countable. I don't think I'd heard this stated explicitly, probably because it's not particularly important for doing combinatorics.

For the answer to the question: see the comments.

18 March 2008

Are most groups solvable?

While trying to find a list of small groups (I needed to find a counterexample in a problem involving finite groups, and there would be some brute-force calculations involved, so I figured I wanted to work with the smallest groups possible) I came across The Groups of Order Sixteen Made Easy, by Marcel Wild, from the January 2005 American Mathematical Monthly. The paper gives a classification of the groups of order sixteen without appealing to the general theory of p-groups.

Anyway, towards the end of the paper things are put into the historical context of the theory of group extensions, and we learn that:
The groups that can be obtained from the trivial group by iteratively building cyclic extensions are called solvable. Statistically speaking “most” groups are solvable. For instance, all groups of order less than sixty are solvable.
Of course, groups of order less than sixty make up a negligible portion of all groups; it's certainly possible that all groups of order less than sixty are solvable, but most groups of order n are not solvable when n is large enough. There is the Feit-Thompson theorem, which states that every group of odd order is solvable, but numerical data for n up to 2015 shows that there seem to be more groups of even order than odd order. This isn't surprising; the number of groups of a given finite order depends strongly on the exponents of the primes in its factorization. Nor is this special to 2 -- in general numbers with lots of prime factors are the order of lots of groups.

It looks like the statement is true, though, in any reasonable sense; from Sloane's Encyclopedia, there are only 2240 integers n below 105 such that there exists a non-solvable group of order n. In fact, it looks like the sequence of such numbers has roughly constant density, of about 0.0224. That should be provable or disprovable from the note given in the Encyclopedia, which gives an easy way to find such numbers. The statement that most numbers are solvable (where a number is solvable if all groups of that order are solvable) is even stronger than the statement that most groups are solvable.

But talking about a ``randomly chosen group'' seems a bit silly, anyway; the groups of a given order don't strike me as the sort of set one picks things from at random. Choosing a random element of a group seems like a much more natural operation. (Feel free to correct me if I'm wrong!)

17 March 2008

Carl Sagan on Flatland

Carl Sagan on Flatland (from Blake Stacey at Science after Sunclipse).

I've got other things I want to talk about, but tomorrow morning's class won't prepare itself.

16 March 2008

Powerball "curse"? Come on...

From the Powerball FAQ:

HOW COME THE ONLY JACKPOT WINNERS ARE FROM THE [EAST - WEST - NORTH - SOUTH - CITIES - RURAL AREAS]?
HOW COME ONLY [WHITE, BLACK, TALL, SKINNY, YOUNG, OLD] PEOPLE WIN?

Powerball is a random game that knows nothing about who buys a ticket or where the ticket was purchased. [...]


They then go on to explain that there's such a thing as the Law of Large Numbers, and that the machine doesn't know anything about who bought the tickets. But this is buried pretty deep in the FAQ, so I wonder if people see it.

I can understand how someone might be suspicious that certain numbers come up more often than others -- maybe for whatever reason some balls come out of the machine more often than others. But how could the machine know what sort of people bought the tickets? (And even if it could, it would be incredibly difficult to load the balls appropriately, given the constraint that you can't get an arbitrary distribution on the many millions of combinations by just weighting down some of the 49 balls. There are nowhere near enough degrees of freedom -- if I want to weight the balls in such a way as to make 1-2-3-4-5 more/less likely, then other combinations involving some of those numbers will be made more/less likely as well.)

But people do ask this question, and some of them seem to believe that Philadelphia is cursed with regard to Powerball winnings.

The Unreasonable Effectiveness of Mathematics in the Natural Sciences

Eugene Wigner's famous essay The Unreasonable Effectiveness of Mathematics in the Natural Sciences is available online.

15 March 2008

Cosmology on bloggingheads.tv

I'm watching a fascinating video on bloggingheads.tv in which Sean Carroll of Cosmic Variance and John Horgan talk about modern comsology. An interesting point from my point of view is that the basic reason modern cosmology exists is because the idea of maximum likelihood doesn't seem to apply to the universe -- probabilistically the universe "shouldn't be" like it is. But it is! From an epistemological point of view that's why explaining the way the universe is is interesting -- you don't expect, for example, large-scale homogeneity and isotropy, but it's there!

(Also, bloggingheads has a feature by which you can speed up videos by a factor of 1.4, without the expected raise in pitch of the sound by a tritone. This is nice, because when listening to recorded speech I often find it to be too slow. That's fine -- I don't insist that people should speak faster -- but I can take in information faster than an extemporaneous speaker can produce it.)

Nothing particularly new if you know something about these things, but a good way to spend 47 (sped-up) or 66 (normal-speed) minutes on a Saturday afternoon.

14 March 2008

Daytime television

For $1,000, on Who Wants To Be A Millionaire:

If four out of five dentists say that they recommend a certain kind of gum, that is exactly what percentage of dentists?

A) 60%
B) 70%
C) 80%
D) 90%

(I'm not quoting the question perfectly, but the word "exactly" was in it. Those definitely were the choices. A specific kind of gum was named but of course that's irrelevant.)

Contestant nervously giggles and says "I'm not that good at math".
Audience laughs.
Contestant answers correctly.

No comment.

Okay, one comment: chances are "four out of five" in those surveys doesn't represent exactly eighty percent. Notice that you never hear, say, "nine out of eleven" or "seven out of nine" in these contexts.

13 March 2008

Course descriptions that describe

Moebius Stripper, whose blog is unfortunately defunct, wrote back in 2004 about course descriptions that describe. She points out that traditionally, course descriptions of mathematics classes are ridiculously uninformative and basically boil down to transforming the table of contents of a textbook into a run-on sentence. And then we wonder why students see math as a bunch of disjointed pieces of information with no overarching narrative to tie them together... don't we come into the classes with that attitude?

See, for example, my institution's mathematics course listing. Physicists do the same thing. Historians, for example, don't. People in the English department don't do it too much, although one does find the occasional list of books to be read in a course description. I am not sufficiently interested in this question to systematically study it, and even if I were there are other more interesting things to study first.

I'd heard this idea before; I'm not sure if I had it originally, if I got it from Moebius Stripper back in 2004, or elsewhere, but I know I think it every time I read course descriptions. Fortunately I will never be reading course descriptions from the point of view of a student taking courses again. (For those of you who don't know, this is my last semester taking courses. Today I was on campus and saw a pile of Fall 2008 course timetables. I almost took one. Then I realized that for the first time in many, many years, I will not be taking classes next semester.)

This may have something to do with the fact that it's expected at most universities that students shopping around for "elective" courses that they don't know much about are probably going to take more humanities-like classes; I don't have hard data on this, though. There's less of a point in trying to craft a good course description if you figure that nobody who's reading the course catalog looking for something to take will even look in your department. In fact, I don't even have anecdotal evidence for this claim, because I went to MIT for undergrad, and the normal rules don't apply there.

Streamlined math curriculum

Panel proposes streamlining math, from today's New York Times, in reference to math education from pre-kindergarten to eighth grade.

"Streamlining" in this context seems to mean covering fewer topics in each grade, but covering them more thoroughly; I'm not sure if it means covering less topics overall. The article also tells us that "The report tries to put to rest the long and heated debate over math teaching methods" -- somehow I don't think one report can do that, since people have been debating whether the teacher's role is to hand down facts from on high or help students discover things on their own from time immemorial. (And this isn't unique to mathematics.)

Larry Faulkner, who chaired the panel, says that the “talent-driven approach to math, that either you can do it or you can’t, like playing the violin” needs to be changed; this is something I agree with. You don't see people just saying "I can't read" and throwing up their hands in disgust -- okay, maybe you do, but not nearly as many as you do with math. I realize that this comparison isn't fair -- reading really is more fundamental than other kinds of learning, if only for the reason that most other learning involves reading -- but I'm making it anyway.

The panel also advocates shorter textbooks. As an instructor of calculus courses, I support this; the report isn't talking about college texts but one would hope that such a thing might filter upwards. Then I could actually bring the text home. I try not to with our current text, which is 1368 pages, because I commute on foot and so carrying around extra pounds is a Bad Thing. (By the way, reading the customer-written reviews of textbooks on Amazon is kind of funny in a depressing way; one gets the sense that students are often taking out their frustrations at their instructors on the textbook.)

12 March 2008

11 March 2008

Durrett's "Random Graph Dynamics"

From Rick Durrett's Random Graph Dynamics (link goes to the author's web site; you can read the first chapter online)
Mathematicians worry about justifying such approximations and spend a lot of effort coping with paranoid delusions, e.g., in section 4.2 that a sequence of numbers all of which lie between 1 and 2 might not converge.
Mathematicians cherish the rare moments where physicists’ leaps of faith get them into trouble.... While it is fun to point out physicists’ errors, it is much more satisfying when we discover something that they don’t know.... Despite remarks in the last few paragraph, our goal is not to lift ourselves up by putting other people down. As Mark Newman said in an email to me “I think there’s room in the world for people who have good ideas but don’t have the rigor to pursue them properly – makes more for mathematicians to do.

The first chapter is a nice overview of the theory of random graphs. The rest of the book has been rather interesting to flip through as well. Durrett doesn't shy away from using the sort of heuristics that physicists use in order to help give intuition, which I think is tremendously useful when thinking about probability. When one is doing "rigorous" probability it's too easy to get lost in a maze of calculations. (This is true for any sort of rigorous mathematics, but it's especially a shame in probability precisely because the correct intuitions are pretty close to the surface.)

10 March 2008

Simon's Rock asks interesting admissions questions

A friend of mine went to Simon's Rock College of Bard, which is a college that admits all its students "early", i. e. directly from tenth or eleventh grade, for the first two years of her undergraduate degree. Somehow I got to wondering, "what do you have to do to get into this college?"

From their application, the following question:

A young student has twenty-four 6” x 6” beautifully decorated, ceramic squares, which were given to her by her grandfather who made them when he himself was a young student. The young woman wishes to arrange the tiles on her floor in such a way as to cover as large a circular area as possible. How should she arrange the tiles to accomplish this? (Note that the tiles will not form a circle themselves, but must completely cover the circular area.) Write a two to four page essay explaining in detail the reasoning by which you arrived at your proposed arrangement and why it is a good one. You may include a description of some of your “first guesses,” as well as diagrams showing your arrangements and the equations used to justify your claims. (Diagrams and equations may be hand drawn.) We are interested in your reasoning and your ability to communicate that reasoning rather than a “correct” answer.

Applicants are asked to either answer this question or to critically analyze a passage from Aristotle which is given in the application. In addition, they are also asked the more "personal" question that basically boils down to "why do you want to come to our school?"

But I think this is an interesting concept, that they're asking people to answer a question like this on a college application. It says something about the sort of person they're looking for. I applied to some good, but conventional, colleges and I don't recall being asked anything like this.

Compare, for example, the application at my current institution, Penn, which asks (p. 12) for answers to the standard "why do you want to come here?" question and one of the following:
6a. You have just completed your 300-page autobiography. Please submit page 217.
6b. First experiences can be defining. Cite a first experience that you have had and explain its impact on you.
6c. Recall an occasion when you took a risk that you now know was the right thing to do.

(I wanted to put MIT's questions as well -- that's where I went for undergrad -- but their application can't be downloaded outside of admissions season.)

I explicitly ask you not to answer the Simon's Rock question -- this blog does well enough on Google that someone filling out the application could easily find the question,and if they found answers to it that would essentially defeat the purpose.

Death rates

How many people in the world do you think will die in the next day?

See here for a psuedo-hint, which is the somewhat easier related question which inspired this.

See here for the answer, from the U. S. Census Bureau.

09 March 2008

Approximating the length of an ellipse

Here's a question that occurred to me this morning -- what's the circumference (is this word appropriate here?) of an ellipse with semimajor axis 1+ε and semiminor axis 1? (ε is, of course, small. It could be negative, however.)

Of course, this is an elliptic integral. But I don't know much about elliptic integrals, and besides what good is that information? It doesn't give me a number. (I didn't actually need to know this for anything, but somehow the knowledge that the answer is, say, 2π+ε (it's not) is more satisfying than the fact that it can be written in terms of some special function that I don't know that well.

It turns out the answer is (2+ε)π.

Here's a sketch of a proof. This ellipse can be parametrized by x = (1+ε) cos t, y = sin t, with t varying from 0 to 2π. So the length is
\int_0^{2\pi} \sqrt{ (1+\epsilon)^2 \cos^2 t + \sin^2 t } \, dt
Expand, and let ε2 = 0, to get
\int_0^{2\pi} \sqrt{ (1+2\epsilon) \cos^2 t + \sin^2 t } \, dt
which simplifies to (recalling cos2 t + sin2 t = 1)
\int_0^{2\pi} \sqrt{ 1 + 2\epsilon \cos^2 t } \, dt
Now, since ε is "small", 2ε cos2 t is also "small". In general, for small h, (1+h)1/2 ~ 1 + (h/2); thus this is approximately
\int_0^{2\pi} 1 + \epsilon \cos^2 t \, dt
and now we recall that cos2 t has average value 1/2. So this is (2+ε)π, which is the answer.

More formally, if f(a) is the length of an ellipse with axis lengths 1 and a, this shows (modulo a couple leaps of faith) that f'(1) = π -- this can easily be checked with a computer algebra system, or if you actually know more about elliptic integrals than I do. This has the nice interpretation that if the lengths of the two axes of an ellipse are close to each other, the length of the ellipse is just π times the mean of the axis lengths -- which is true for a circle, where it just says that the circumference of a circle is π times its diameter. The Taylor series for the elliptic integral which gives the length is, according to Maple,
\pi \left( 2 + \epsilon + {1 \over 8} \epsilon^2 - {1 \over 16} \epsilon^3 + \cdots \right)

and from numerical data, for, say, ε = 0.1, this method predicts an ellipse length of 2.1π = 6.5973; the actual length is 6.6011. Even for ε = 0.5 the error's only about one percent (7.85 versus 7.93).

The real question that I started out with, though, still isn't answered -- is there some nice geometric way to see this?

Comments on "Lockhart's Lament"

A Mathematician's Lament, by Paul Lockhart, on the state of mathematics education. (Via Devlin's Angle.) Lockhart has a Ph.D. in mathematics and has been a research mathematician; he currently teaches at Saint Ann's School in Brooklyn.

Lockhart begins with a terrifying metaphor -- what if classes in music were taught as exercises in rote manipulation of musical notation, or art classes were classes in Paint-by-Numbers? Yet this is the state of affairs in school mathematics education. Sometimes it astounds me that our schools manage to produce anybody who's actually any good at mathematics. (The best thing a lot of my teachers did was to just get out of my way.)

Lockhart writes (p. 3):
The first thing to understand is that mathematics is an art. The difference between math and the other arts, such as music and painting, is that our culture does not recognize it as such.... Part of the problem is that nobody has the faintest idea what it is that mathematicians do.

I will not explain what it is that mathematicians do -- I'm preaching to the choir here, I suspect -- but I agree with this. One of the things I find myself doing, when people find out I'm a mathematician, is to try to briefly explain that mathematics is not about numbers and formulas but about abstract ideas and patterns, and that yes, it is possible to create new mathematics! (People seem to think that mathematics is complete.) I hope this missionary zeal doesn't go away -- but it very well might as I age. A lot of older mathematicians I know have said that they used to do this sort of thing but now don't bother any more.

Later (p. 6):
Many a graduate student has come to grief when they discover, after a decade of being told they were “good at math,” that in fact they have no real mathematical talent and are just very good at following directions. Math is not about following directions, it’s about making new directions.

This reminds me of something that I overheard a friend of mine saying a few days ago. He was talking to one of the young faculty in our department, trying to get some insight about how the process of creating mathematics works. And he said that he didn't know what real mathematics was -- just graduate school mathematics! And this is a man who will quite likely be receiving a PhD in mathematics in three short years. (Let it be said that I am not saying I was not in the same situation at that point in my own graduate career.)

On sources (p. 9):
What other subject is routinely taught without any mention of its history, philosophy, thematic development, aesthetic criteria, and current status? What other subject shuns its primary sources— beautiful works of art by some of the most creative minds in history— in favor of third-rate textbook bastardizations?

Indeed, friends of mine in the humanities are surprised to learn that we don't routinely learn from the writings of the masters. I've heard various explanations for this. First is the claim that one often doesn't want to see the original proof of some important theorem because it's a mess -- and yes, that might be true. So we write various explanations of it, and include those first in our research papers, sanding off a few rough edges here and there. Second is the fact that a lot of mathematicians just don't write that well, because the culture doesn't reward that.

Lockhart claims, in fact, that "there is no actual mathematics being done in our mathematics classes" -- I don't want to believe this, but he'd know better than I would. He's most annoyed at the fact that when school mathematics does teach the idea of "proof" -- which for traditional reasons is done in geometry classes -- the proofs that students produce are so different from real proofs as to be unrecognizable. For those of you who don't know, students in American schools are subjected to something called a "two-column proof" in which a sequence of statements is made in one column, and justifications for those statements is made in an adjacent column. I can imagine how this would be useful for very carefully checking if a proof is correct. But anybody who was actually reading such a proof in an attempt to learn something would probably attempt to translate it back to natural language first! I suspect that the real reason such "proofs" are so common in such courses is because they're much easier to grade than a proof actually written out in sentences and paragraphs. (This seems true of a lot of counterintuitive aspects of our educational system.) Lockhart advocates replacing the standard course with courses in which students actually struggle with trying to come up with their own mathematics. It sounds like it's working for him.

But Lockhart teaches at what appears to be a very good private school that has considerable latitude in choosing its students and gives considerable autonomy to its teachers. Would something like this work within the "mainstream" educational system? I don't know. I'd like to find out.

07 March 2008

Student faces expulsion for Facebook study group

Student faces expulsion for Facebook study group, from Slashdot. (The original article is from the Toronto Star.)

Basically, it's what it sounds like from the headline -- a student, Chris Avenir, started a group for discussing one of his classes on Facebook, and is now being charged with 147 counts of academic misconduct for doing so. The Slashdot comments are surprisingly insightful; basically we hear people point out that in the end you learn a lot more from talking to other people than from working in isolation anyway.

I'm not sure how I feel about the actual case in question. The "147 counts" sounds like trumped-up charges (and besides, how can they punish him 147 times?), but as some people have pointed out, certainly meaningful collaboration wasn't taking part in that large of a group. This is something I've felt when I've worked with groups on assignments, although in the end I rarely work with groups because either I feel that the other people in the group are bringing less to the table than me (and then I feel bitter that I'm doing their work for them) or are bringing more to the table than me (and then I feel guilty for sponging off of them). But I certainly am okay with the idea of people working in groups, both in classes that I'm taking and in classes that I'm teaching. Note that this is just my attitude towards collaboration in classes. My attitude towards collaboration in actual research is not well-formed yet.

05 March 2008

A factoring trick

I came across the polynomial f(x) = 2x2 + 3x - 5 during a calculation I was doing a few days ago. I wanted to factor it. Sure, I could have done it the usual way. But I have a better intuition for factoring numbers than I do for factoring polynomials. So I plug in x = 10; then f(10) = 225.225 factors into 9 times 25. Perhaps this reflects a factorization f(x) = g(x) h(x), where g(10) = 9, h(10) = 25.

Indeed, it does: 2x2 + 3x - 5 = (x-1)(2x+5). Of course, this gives a whole family of integer factorizations, plugging in different integers for x.

Of course, this doesn't work in general; consider for example 2x2 + 2x + 5, which doesn't factor at all. And when the trick is spelled out explicitly it seems to be irredeemably flawed -- how did I know to take (x-1)(2x+5), say, and not (x-1)(3x-5)? (More importantly, can this be explained without reference to the original polynomial?) One could perhaps point out that, say, 184 = (8)(23), which is just f(9) = g(9) h(9), and so on; from a family of such facts it might be possible to deduce the polynomial factorization, but at that point it's just not worth the trouble. These sorts of tricks, like jokes, rarely stand up to explanation.

04 March 2008

Bollobas and Riordan's "Percolation" -- cheap at Amazon

Amazon.com is selling Bollobás and Riordan's Percolation for $40.28 (marked down from $79).

Percolation isn't a subject that I'm interested enough in to buy the book (especially since our library has it), but I have talked about percolation here before and gotten some interesting responses, so I thought there might be someone out there who'd appreciate knowing.

03 March 2008

Breadth-first versus depth-first browsing

Firefox's tabbed browsing feature encourages breadth-first search. If I click on a link the tab containing the page linked to appears as the rightmost tab, and I generally work through tabs from left to right. Breadth-first search can be implemented in this way -- we maintain a list of pages to be looked at, and the first page to enter the queue is also the first page to leave it.

Depth-first browsing wouldn't be too much different on a cosmetic level -- it could be set up by having the new tab appear immediately after the current tab, giving a stack of pages to view instead of a queue. I suspect the subjective experience of Internet browsing would feel much different from such a point of view -- browsing often seems to lead to shallow knowledge. (If one had time to search the entire Internet breadth-first search and depth-first search would eventually visit the same set of pages -- but who has that kind of time?) The "optimal" algorithm for finding particular information isn't strictly breadth-first or depth-first, though; if you think about how you search when you look for a specific piece of information, you don't routinely follow the leftmost tab or the rightmost tab, but instead click on whatever tab subjectively seems like it would give the best information.

02 March 2008

The Harvard College Mathematics Review

There exists something called the Harvard College Mathematics Review, which "is a semiannual journal of expository mathematical articles written and edited by undergraduates." I learned about this from Vishal Lama's blog. (Conveniently, the how to link to a blog question is almost irrelevant here.)

The faculty feature article by Noam Elkies which was in their first issue, about the abc conjecture, is quite interesting. (I especially like the heuristics given therein for the number of rational points lying on certain curves and other solutions to diophantine equations -- concerning such questions as Mordell's conjecture and Fermat's last theorem -- which shouldn't surprise longtime readers.)

There have been two issues so far: the first issue and the second issue.

You know it's got to be good -- or at least it looks good from the table of contents and the few links I clicked on -- because I went to MIT for undergrad and I'm now a grad student at Penn and I'm still telling you about it. And you've got to love any publication which includes an article entitled Dunking Donuts: Culinary Calculations of the Euler Characteristic. I mean, who hasn't gotten hungry while doing topology? All those tori look like donuts.

And the editor-in-chief of the HCMR is Scott Kominers, who I've previously mentioned as one of the authors of a paper about whether or not you should wait for the bus.

01 March 2008

A leap year scheme based on binary expansions

Yesterday I wrote about leap day, and how a different scheme of determining which years are leap years could make calendrical calculation easier. In particular, the number of days in a year is very nearly 365+31/128; how can we pick 31 years out of every 128 to be leap years? (As was pointed out in the comments, 128 is a power of two, which is what makes this whole post work.)

The answer is obvious -- take every fourth year, except don't take years divisible by 128.

But then I asked -- what if we needed to take 33 years out of every 128? We clearly should take every fourth year... and then one more out of every 128. But which one?

I'm implicitly using the fact 31/128 = 1/4 - 1/128 and 33/128 = 1/4 + 1/128. But we can also write:

33/128 = 1/2 - 1/4 + 1/128.

Why would I do this? Because it gives a very good scheme for assigning 33 leap years out of every 128. Include in the set of leap years all years which are even, but not those that are divisble by 4, but do include those which are divisible by 128. So in every 128-year period we include the year 0, and the years 2, 6, 10, ..., 126.

But there's a nicer way to express that. Look at the binary expansion of such a year. Either it ends in exactly one 0 (it's 2 more than a multiple of 4) or it ends in at least seven 0s (it's a multiple of 128). It turns out that for any fraction of the form m/2n, where 0 ≤ m < 2n, we can write m/2n as an alternating sum of powers of 1/2. For example, consider

59/128 = 1/4 + 1/8 + 1/16 + 1/64 + 1/128.

where that's just the ordinary binary expansion. We can group the consecutive powers of 2 in the binary expansion together to get

59/128 = (1/4 + 1/8 + 1/16) + (1/64 + 1/128)

and then each sum of consecutive powers can be written as a difference, giving

59/128 = 1/2 - 1/16 + 1/32 - 1/128.

So let's say we want 59 leap years out of every 128. We include all the even years, but we don't include those that are divisible by 16, but we do include those that are divisible by 32, but then we don't include those that are divisible by 128.

It sounds complicated -- but there's a better way to say it. If you think about it, the rule I just gave says that the binary expansion of a leap year must end in 1, 2, 3, 5, or 6 zeroes. Write 59/128 = .01110112. Now, there are 1s in exactly the 2nd, 3rd, 4th, 6th, and 7th places after the decimal point. That's not a coincidence. The proportion 1/2n+1 of integers will have binary expansions ending in exactly n zeroes. In general, if we want m/2n of our years to be leap years, then we can determine if any given year k is a leap year via a scheme like this, as follows:
- let p be the number of zeroes terminating the binary expansion of k.
- if the (p+1)st bit of m/2n after the decimal point is 1, then k is a leap year, otherwise it's a common year.

The years for which we examine the jth bit are exactly 1/2j of all years, so this works.

For 31/128 = .0011111, this says that a year should be a leap year if its binary expansion ends in exactly 2, 3, 4, 5, or 6 zeroes -- exactly the rule I suggested in the first place. For 33/128 = .0100001, a year is a leap year if its binary expansion ends in exactly 1 or 6 zeroes. That's one flaw with this scheme -- the set of leap years changes radically as m/2n passes through some small power of (1/2). But that wasn't my aim here; my aim was to be able to read off if a year is a leap year directly from the binary expansion, just as one can almost do with the decimal expansion in the current scheme. The 8/33 scheme I talked about yesterday doesn't have this property in any small base, although I made the argument that since 33 = (100-1)/3 there are worse situations to be in.

(Exercise for the reader: can you come up with a scheme like this in decimal? Calling this an "exercise" isn't quite fair, because I don't know if it's possible.)

Zeros of some polynomials arising from sums

Here's a little thing I thought of a few days ago. Consider the following identities for the sums of powers:
\sum_{k=1}^n k^0 = n

(okay, that's kind of stupid, but you have to start somewhere...),
\sum_{k=1}^n k^1 = {n(n+1)\over 2};

\sum_{k=1}^n k^2 = {n(n+1)(n+1/2)\over 3}

(the right-hand side might be more familiar as n(n+1)(2n+1)/6), and
\sum_{k=1}^n k^3 = {n^2(n+1)^2\over 4}

(the right-hand side here is,coincidentally the square of (1+2+...+k). For each choice of exponent we get a different polynomial in the numerator. They all factor into linear terms... that doesn't keep up, though. For example,
\sum_{k=1}^n k^9 = {n^2(n^2+n-1)(n+1)^2 (n^4+2n^3 - n^2/2 - 3n/2 + 3) \over 10}

Still, one wonders -- what are the roots of these polynomials? (The first thought is that they're always in the interval [-1, 0], but that's pretty quickly disproven by considering the sum of 5th powers.)

Some computation shows that the patterns of zeroes in the complex plane are both symmetric around the real axis (no surprise there; zeroes come in complex conjugate pairs!) and around the line y = -1/2 (a bit more surprising). So you think to plot them, and you get something that looks like this plot for the polynomial you obtain when you sum 300th powers. (I didn't make that plot; it's from Richard Stanley's web page on interesting zeros of polynomials.)

It turns out that they're the Bernoulli polynomials; for very large n Veselov and Ward showed that the real zeroes are very near 0, ± 1/2, ± 1, ... if n is odd, and ± 1/4, ± 3/4, ± 5/4, ... if n is even; furthermore, in the limit, the nth Bernoulli polynomial has 2/(πe)n real zeros. (2/πe is about .235; thus in the 300th Bernoulli polynomial we expect about 70 real zeros, taking up an interval of length 35 or so centered at -1/2 on the real line; that's what you see in that plot.)

Goh and Boyer (who I've mentioned before for similar work on partition polynomials) have found the "zero attractor" of the Euler polynomials, and state in their paper that the methods there also give a similar result for the Bernoulli polynomials -- basically, what this means is that if we shrink down the plot of the zeros of the nth Bernoulli polynomial by a factor of n, then the zeroes fall very close to some limiting curves and are arranged with a certain density along those curves. (Along the portion of the real axis in question, the density is constant; along the other branches it doesn't seem to be.)

References:
William M. Y. Goh, Robert Boyer. On the Zero Attractor of the Euler Polynomials. arXiv: math.CO/0409062. (2004)
Alexander Veselov and Joseph Ward, On the real zeroes of the Hurwitz zeta-function and Bernoulli polynomials, arXiv: math.GM/0205183. (2002)