God Plays Dice

"Roommates" is a euphemism?

2009-07-16T18:58:00.003-04:00

I'm at the Cornell Probability Summer School. (This announcement is too late for anybody who wants to find me here, as it's almost over! But I have been tracked down by at least one fan.)

In a lecture here this morning, Ander Holroyd spoke about the stable marriage problem and variations of it involving point processes (see this paper of Holroyd, Pemantle, Peres, and Schramm, which I've mentioned before, for details). The goal of the problem is to pair up n men and n women in such a way that no two people who aren't married to each other prefer each other to their current partners; this is called a "stable matching" and one always exists.

The original paper on the stable marriage problem is that of Gale and Shapley, in 1962. This paper also talks about the "stable roommates" problem, which is the analogous problem where everybody is of the same gender. Rather surprisingly, I never realized that "roommates" might be a euphemism here, which is something that Holroyd pointed out this morning to quite a bit of laughter.

Batting under .200

2009-07-15T22:51:00.001-04:00

Stat of the day (from baseball-reference.com) has a list of players who went an entire season, had enough at bats to qualify for the batting title (I forget the statistics for this, but this basically means they have to play regularly), and are batting under .200.

Most of them are from a long time ago. Why? Because .200 is well below average and always has been (which is why the list was worth compiling) and the variance in batting averages has gone down as the standard of play has improved. Stephen Jay Gould wrote about this in Full House: The Spread of Excellence from Plato to Darwin; the argument is roughly that as baseball scouting and training has gotten better, there are not as many bad pitchers in the major leagues as there were in the past, so players can't inflate their batting average that way. (I'm in Ithaca and my copy of the book is in Philadelphia, so I can't check if I'm stating this correctly.)

A puzzle

2009-07-11T19:38:00.003-04:00

2²⁹, expressed in base 10, is a nine-digit number. All nine of its digits are different. Find the digit that is missing without explicitly calculating 2²⁹. (Thanks to Kate for this one; a solution is there, so don't look until you've thought about it.)

Problems that are hard for intermediate values of some parameter

2009-07-05T16:37:00.000-04:00

In Clifford Henry Taubes' review of Monopoles and three-manifolds, by Peter Kronheimer and Tomasz Mrowka (citation information; article), near the end of the first paragraph the authors mention the problem of classifying compact manifolds with the homotopy type of the n-sphere. In any dimension there is exactly one. The history of this problem is roughly as follows:

n ≥ 5: Smale, 1960 (and Stallings at around the same time)

n = 4: Freedman, 1980

n = 3: Perelman, early 2000s (this is the Poincare conjecture)

n = 2: "follows from the Riemann mapping theorem"

n = 1: "a nice exercise for an undergraduate"

So in low dimensions the problem is easy, or at least doesn't require "modern" apparatus; in high dimensions it's harder (Smale and Freedman both got Fields Medals); in "middle" dimensions (like 3) it's the hardest, or at least took the longest. It's my understanding that it's pretty typical in geometry/topology for the three- or four-dimensional cases of a problem to be the most difficult?

Can you think of other problems (from any area of mathematics) that have a similar property -- that they're hardest for some medium-sized value of whatever a natural parameter for the problem is? (Yes, it's a vague question.)

Brownies and space-filling curves

2009-06-25T08:29:00.002-04:00

The Baker's Edge brownie pans, which are pans constructed in such a way that everybody gets an edge piece and nobody gets a piece from the middle, remind me of space-filling curves.

The isoperimetric inequality suggests that the only way to do the reverse -- to have pans where nearly everybody gets the middle and nearly nobody gets the edge -- is to have really big pans.

The Iranian election

2009-06-23T13:57:00.002-04:00

The Devil Is in the Digits, an op-ed by Bernd Beber and Alexandra Scacco in Saturday's Washington Post.

This piece claims that the distribution of insignificant digits in vote totals in the recent Iranian election look funny, and that there's a good chance this is because the numbers were made up.

I haven't looked at the numbers myself, but this seems like an avenue worth pursuing.

Money with mathematicians on it

2009-06-18T12:42:00.005-04:00

Banknotes featuring scientists and mathematicians. Including the two in-print US bills that we're all least likely to see: the $100 (Franklin) and the $2 (Jefferson). For the non-US readers: the $100 is the largest bill in general circulation. For some reason the $2 bill has fallen out of favor, and although it's legal it's very rare, to the point that some people don't know about them and urban legends circulate about the $2 being suspected as counterfeit)

There seem to be more "scientists" than "mathematicians" on the list, but this may just reflect the fact that there are more scientists than mathematicians in general. In fact, "scientist" is a broad enough category that I don't think too many people would describe themselves as "scientists" when asked "what do you do?", rather responding with something like "physicist" or "biologist"; but I think a lot of mathematicians would answer "I'm a mathematician" to this question. (This seems to correspond roughly with the way departments are organized in most universities; there's usually a "department of mathematics" but very rarely a "department of science".)

(via a comment at Gil Kalai's blog)

Edit, 6:20 pm: the linguists seem to be compiling their own list of linguists-on-money, over at Language Log.

The Math Factory?

2009-06-16T11:16:00.003-04:00

On Sunday, June 14, in New York City, there was a Math Midway as part of the World Science Festival's street fair. The web page refers to it as a "traveling exhibit" so maybe it's coming to somewhere near you?

This is the first exhibit mounted by the Math Factory, which will be a full-scale museum of mathematics, incorporating the collection of the now closed Goudreau Museum, which was housed in a couple classrooms at a former school. This is the brainchild of Glen Whitney, who got a PhD in math, worked for a hedge fund for some time, and now is devoting himself to this museum, according to this article from the New York Daily News. Here is a list of exhibits they're planning and an interview about the museum that Whitney did in April in the oddly named online magazine gelf.

I found out about the midway from Quomodocumque and the Daily News article from My Biased Coin.

Incidentally, I'm not sure I like the name "Math Factory" for this museum. Factories are generally not pleasant places, and in addition they won't actually be manufacturing mathematics there.

When do you learn that the rationals are countable, and the reals aren't?

2009-06-09T12:59:00.005-04:00

I'm currently teaching a course "Ideas in Mathematics" in our summer session. This is a course generally taken by students not in technical fields; quickly speaking, my syllabus is some basic number theory, different notions of infinity, some bits of geometry (polyhedra, letting them know that there is such a thing as non-Euclidean geometry, etc.), fractals and chaos, and a smattering of probability. This is a course that's not a prerequisite for anything and the students aren't going into fields where they'll need math, so I, like a lot of other people teaching this class, take the approach of showing them that "math is beautiful" rather than that "math is useful".

So today I'm showing my students that the rationals are countable, first by the standard proof and then by the superior Calkin-Wilf proof. I find the Calkin-Wilf proof aesthetically superior because the "standard" proof, in my opinion, is "really" a proof that the set of pairs of natural numbers is countable; we then just cross off the pairs which aren't in lowest terms as a sort of afterthought. As a result, it's difficult to answer questions like "what's the 1000th rational number in the `standard' enumeration?". Then I will show them that the reals are uncountable, using Cantor's diagonalization argument.

While preparing today's class, I realized that I don't know when I learned that the rationals are countable and the reals are uncountable. Is this even part of the "standard" curriculum for math majors? These feel like facts that I have always known; presumably I picked them up from some popular mathematics book at an early age. Do any of you remember when you learned this?

Odd periods in continued fractions

2009-06-04T15:03:00.000-04:00

Here's a question. Why is the period of the quotients in the continued fraction of N^1/2 "usually" even? For example, if N runs over the ninety non-squares less than 100, then only 20 times does the continued fraction expansion of N^1/2 have an odd period. Of the 992 non-squares less than 1024, 157 have an odd period. Of the 9900 squares less than 10⁴, 1322 have an odd period. This is a sign that something is going on under the hood -- naively you'd expect half the periods to be odd.

Arnold has observed this, but only empirically; I first observed it from this problem from Project Euler.

The period of the continued fraction of N^1/2 is odd if and only if x² - Ny² = -1 has solutions in integers. All such integers, it turns out, have no prime factors congruent to 3 mod 4, which is pretty rare for large numbers. (The number of positive integers less than N with no prime factors congruent to 3 mod 4 is about N(log N)^-1/2.) For integers having no prime factors congruent to 3 mod 4, though, a paper of Etienne Fouvry and Jurgen Kluners shows that asymptotically at least 52% of such numbers have odd period, and at most two-thirds do.

Random Walk: The visualization of randomness

2009-06-03T14:19:00.002-04:00

Random Walk: The visualization of randomness, Daniel Becker's diploma thesis, shows fascinating pictures that illustrate various stochastic phenomena: dart-throwing and the Poisson distribution, Benford's law, Monte Carlo methods, some hidden high-order correlations in pseudo-random number generators, and so on.

Square roots and sunscreen

2009-05-14T09:12:00.005-04:00

Also, here's an interesting tidbit, from this New York Times piece on SPF. SPF, or "sun protection factor", is the number on the sunscreen bottle; if a properly applied sunscreen lets through a fraction p of the UV rays it's meant to protect against, then that sunscreen has SPF 1/p. (The numbers in the article talk about the proportion of the UV rays which are blocked; in this case, if a fraction q of the UV rays are blocked, the sunscreen has SPF 1/(1-q).)

Anyway, you're supposed to apply some ridiculous amount of sunscreen to your body, about an ounce. This seems like a lot to most people, because that stuff is expensive! So a lot of people underapply sunscreen. (I'll include myself here.) The article quotes Darrell Rigel, NYU dermatologist, as saying that if you apply half the sunscreen you're "supposed" to, you have to take the square root of the SPF.

That sounds obvious once you think about it -- but I'll admit I'd never thought about it. Say I have a sunscreen that allows through one-sixteenth of the light which hits it when applied properly. Now imagine splitting it up into two coats, each of which allows through the same proportion of the light that hits it. One-fourth of the light makes it through the outer coat; one-fourth of that light makes it through to the skin.

Of course there are issues with this analysis, but according to this paper in the British Journal of Dermatology it appears to hold up. And applying twice the usual amount of sunscreen apparently squares the SPF. (The effect is actually a bit less than this, because sunscreens don't block all wavelengths equally, nor does the sun's spectrum contain all wavelengths equally.)

This all implies that if you want to compare prices of sunscreens, you should divide the cost of the sunscreen by the product of the bottle's volume and the logarithm of the SPF. Do sunscreen prices actually work this way?

Twitter Ratio - why?

2009-05-14T09:04:00.002-04:00

Twitter Ratio calculates the ratio of the number of followers you have on Twitter to the number of people who follow you.

Yes, there's a web site to do division. (And Twitter reports the two numbers involved in the quotient, so it's not even like this web site is doing the counting.)

Apparently it also saves historical numbers, so it's not entirely worthless, but it still seems like an odd thing to base a site around.

The third derivative of the employment rate is positive

2009-05-08T13:21:00.003-04:00

The third derivative of the number of people employed in the United States is positive. (From 538.)

Nate Silver puts it as "the second derivative has improved", but let's face it, this is really a statement about the third derivative. Compare Nixon's 1972 statement that the rate of increase of inflation was decreasing, which Hugo Rossi pointed out in the Notices was a statement about the third derivative. (I seem to recall John Allen Paulos pointing this out in one of his books, but I don't recall which book and therefore can't date it relative to Rossi's letter in the Notices.)

The physics of singing in the shower

2009-05-08T12:09:00.000-04:00

I was singing in the shower, as I do.

I noticed that certain notes seemed to resonate with the shower more than others.

These were, in ascending order, Eb2, G2, C3, and G3, where C4 is middle C. (These may not be exactly right; I don't have perfect pitch. The intervals are right, though.)

Exercise for the reader: how large is my shower?

The Calkin-Wilf tree on Wikipedia

2009-05-07T23:33:00.005-04:00

The Calkin-Wilf tree now has a Wikipedia page. This is an infinite binary tree with rational numbers at the nodes, such that it contains each rational number exactly once. In the sequence of rational numbers that one gets from breadth-first traversal of the tree,

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

the denominator of each number is the numerator of the next; furthermore the sequence of denominators (or of numerators) actually counts something. Plus, there are some interesting pictures that come from plotting these sequences, and some interesting probabilistic properties (see arXiv:0801.0054 for some of the probabilistic stuff, although I actually just found it and haven't read it thoroughly) I've given a talk about this; one day I'll write down some version of it. This is one of my favorite mathematical objects.

It looks like we've got David Eppstein to thank for this. It was introduced in this article by Calkin and Wilf.

Bears, pigs, and the like

2009-05-04T14:07:00.004-04:00

The blog's been slow. I've been off writing real mathematics, thinking for and preparing for the class I'm teaching this summer, and so on. But I'm still here!

And while I'm here, you should read Chad Orzel on the faulty thermodynamics of children's stories. In the story of Goldilocks and the three bears, one would expect that the papa bear is the largest, then the mama bear, and then the baby bear. Furthermore, you'd think that the larger the bear, the larger the bowl of porridge, and the slower it should cool off. But it doesn't seem to work that way! Read the comments come up with some interesting explanations.

Exercise for the scientifically-inclined reader: comment on the physical implications of the Three Little Pigs.

Exercise for the not-so-scientifically-inclined reader: what's with all the animals coming in threes?

Calculus made awesome

2009-04-23T08:17:00.001-04:00

Calculus Made Awesome, by Silvanus P. Thompson, is available online. (Okay, so it's actually called Calculus Made Easy, but I like my alternate title better.)

Furthermore, unlike the modern calculus texts, it is nowhere near large enough to use as a weapon, even if you buy the print version, a 1998 edition fixed up by Martin Gardner Next time I teach calculus I must make sure to tell my students this book exists. And it's in the public-domain and free online, so it's not like I'd be recommending another expensive book. How much has calculus really changed in a century, anyway?

Thanks to Sam Shahfor reminding me of it. See also Ivars Peterson's review of the 1998 reissue. John Baez likes it but doesn't like that the new edition is longer than the old one.

Constrained tourism

2009-04-22T22:44:00.004-04:00

Does there exist a Hamiltonian tour of the graph whose vertices are the 48 contiguous United States and whose edges connect states which border each other? More geographically, can you drive through all of the lower 48 states passing through each exactly once? (From 360.)

Here's one possible solution, although I ignored the constraint implicit in the story that provoked the question, which required a start in Michigan. Note that you have to start or end the tour in Maine since it only borders one other state.

The Art of the Probable: Literature and Probability

2009-04-17T10:45:00.003-04:00

From MIT's Open Course Ware: The Art of the Probable: Literature and Probability. The course readings include both some of the classical mathematical writings about probability (Pascal, Fermat, Leibnitz, Bernoulli, Bayes, Quetelet, etc.) as well as various more "literary" pieces.

Only at MIT...

(Seriously, though, I would have liked to take this class. And one of the readings from the last week is "the Bohr-Einstein dialogue", which you may know refers to whether God does or does not play dice.)

Global octahedron

2009-04-06T21:21:00.002-04:00

The Onion, in its fictional world, is owned by Global Tetrahedron. Their logo is a dodecahedron.

(The title of this post splits the difference.)

James Stewart's house

2009-04-06T18:48:00.005-04:00

James Stewart, author of calculus texts, has a $24 million house. It has lots of curved walls. Problem: find their areas or volumes, by integrating.

Simmons Hall, an MIT dorm opened in 2002, has a lot of oddly shaped rooms. (I found this silly, because the curved walls meant wasted space -- but I didn't live there, I just had friends who did, so it didn't bother me too much.) The story goes that the Cambridge fire department had trouble giving them a certificate of occupancy because they couldn't determine the volume of certain rooms and therefore couldn't determine whether they were adequately ventilated.

(Article from the Wall Street Journal; link from Casting Out Nines.)

God and some humans play dice

2009-04-06T15:53:00.002-04:00

From Tierney Lab at the New York Times:A puzzle in which God, Einstein, and Oppenheimer play dice, and its solution.

Which two states are closest together?

2009-04-04T11:55:00.004-04:00

Fix two sets X and Y in the plane, each the interior of a curve, such that their closures don't intersect. How would one go about finding points x in X and y in Y such that the distance between X and Y is minimal?

Furthermore, say we have a bunch of sets X₁, ..., X_n, each the interior of a curve, with nonintersecting closures. Let d(i,j) be the minimal distance between X_i and X_j. How can we find the minimal nonzero d(i,j), that is, the minimal distance between any two sets with nonintersecting closures? (In particular, there should be a faster algorithm than computing all the d(i,j). I suspect O(n log n) of the d(i,j) need to be computed although I have no idea why I'm saying this.)

The problem that inspired this is the following geographic one. What two states in the US that don't border each other are closest together? I think I know the answer; I'll post about that later.

17 Gauss Way

2009-03-31T17:32:00.002-04:00

MSRI (the Mathematical Sciences Research Institute) is located at 17 Gauss Way, Berkeley, California. Here's a picture.

Of course, Gauss constructed the 17-gon with ruler and compass and was very proud of this. This article says it's not a coincidence, and so does this official MSRI document.

And rather surprisingly, that's not the only thing on Gauss Way. The Space Sciences Laboratory is at 7 Gauss Way. I'm not sure what significance 7 has, if any.