I Will Derive

"I Will Derive", a parody of "I Will Survive".



(via reddit.)

Now, the original song is clearly about female empowerment, and there is somebody who could be described as a "jerk" in the song. (Here are the lyrics, in case you've been living in a cave, or you're not from the US -- I'm not sure how well-known this song is in other countries.) I think this parody would be improved if it mentioned jerk, the third derivative of position.

Phillies radio silliness

There's a commercial which airs on Phillies radio broadcasts. Since I dislike Comcast, but am addicted to the Internet, I'm willing to pay them for high-speed Internet access but not for cable TV. This means I listen to Phillies games on the radio.

Anyway, there's a commercial for Citizens Bank (who own the naming rights to Citizens Bank Park, where the Phillies play) that regularly airs during these broadcasts. It goes something like this (I'm paraphrasing, but the "math" is correct):

Did you ever notice how important the number seven is to the Phillies? They've won seven National League East division titles. There are seven letters in Ashburn, Schmidt, and Carlton. Thirty-two Hall of Famers played for the Phillies. Divide by the number of runs scored in a grand slam and, yes, you get eight. Subtract the number on Whitey's back and what do you get. Seven!

The voice then proceeds to tell us how Citizens Bank is open seven days a week. Which I suppose would be nice to know if I didn't do basically all my banking at ATMs anyway.

But I think the commercial is intended to make fun of people who jump through hoops like this to make the numbers work out. And seven is a small number and therefore easy to manufacture by the manipulation of other small numbers, or so I noted on July 7, 2007.

Large Rubik's cubes and asymptotic thoughts

A video of the solution of a Rubik's cube of side 100, from YouTube.

I don't know the details of the algorithm, but it has the interesting property that at first it looks like nothing's happening, and then larger and larger blocks of each color seem to form -- I'm not sure if this is because of the low resolution or if this really is some sort of "phase transition" in the algorithm. This is the sort of thing one just doesn't see in the normal-sized cube.

I came to this from a solution of the size-20 cube, which works in a much different way; each of the faces of the cube gets "filled in" in turn. So in the second case the algorithm appears to be making steady progress; in the first case it doesn't. There are essentially two different families of algorithm.

It would be interesting to know how the solution time (measured in number of moves) of these families of algorithms -- and I'm calling them "families" because I suspect that the actual side length of the cube isn't all that important -- scales with time. Also, how do these algorithms compare with the asymptotically fastest one? One could compute a lower bound on the number of moves needed to solve a Rubik's cube of arbitrary size by just computing the number of possible positions (analogously to the calculation of that number for the normal cube I outlined here) and comparing that to the number of possible moves one can make from a given position. An absolutely useless question -- is that lower bound (I worked it out once, but I forget what it is, and it was the sort of the back-of-the-envelope work that might have been wrong anyway) asymptotically tight? That is, does there exist a solution procedure for the Rubik's cube for which the number of moves needed to solve the size-n cube is within a constant factor of this obvious lower bound?

As for what that lower bound is, I may write that up as another post; I'd either need to find the notes I made on it a few months ago or (more likely) rederive them.

It's a tax on stupidity -- but nobody's that stupid.

You win $1,500 by feeding slot only $3.75 million -- Paul Carpenter, from the (Allentown, Pennsylvania) Morning Call, via fark.com.

From that headline, it sounds like slot machines essentially never pay out, right?

Carpenter becomes suspicious that the machines are rigged because Flo Fabrizio, a "key backer" of legalized gambling in Pennsylvania, won $1500 on his first play of the machine. Now, I can understand this suspicion -- sure, it could happen randomly. But then Carpenter goes on to do some "math" which proves he really doesn't understand what he's talking about. The article basically debunks itself.

It states that slot machines in Pennsylvania have to pay back at least 85 percent of what they take in. So then Carpenter says:

If it takes a regular player 50 million three-second plays to get a big jackpot, it would take more than 11 years, playing 10 hours a day, every day. More important, if each play averages 50 cents, the player would have to put $25 million into the slot. The 85 percent payback would be $21,250,000. So, odds are, the cost of playing long enough to get a $1,500 jackpot would be $3,750,000.

That's true. (The "50 million" comes from the regulations that say that casinos can set up their slots so that the jackpot only pays one time out of every 50 million.) But somehow I doubt a $1500 jackpot would be that rare. And more importantly, while the player is making those fifty million plays, they'll make a lot of small bets back. This is like saying that poker's a losing game because you only get a royal flush once every several hundred thousand hands. Or saying that you must not be broke because you didn't buy a million-dollar house you couldn't afford, but ignoring all the little expenses that add up. (Try telling your credit card company that!) You can't cherry-pick the tail of the distribution like that!

Could there be corruption in the gambling industry? Sure. But this doesn't prove anything. Not to mention that these calculations seem to imply that slot machines basically never pay out. Casinos aren't stupid -- they know that if slots essentially never paid out then nobody would play! The whole trick is that if you have enough small gains, you won't realize that on average you're losing.

On the other hand, they say that gambling is a tax on stupidity. At least this man's stupidity will keep him out of the casinos.

Optimal choice of partners

Optimizing your wife. From MathPages, via reddit. (This is apparently also known as the secretary problem or the sultan's dowry problem.)

The following is a semi-standard bit of mathematical folklore. Say you expect to meet N possible suitors in your life. You want to maximize your chances of picking the best one, given that you expect to meet these people in a random order, and once you say no to one of them you can never see them again, and that you can say for any two of them either "X is better than Y" or "Y is better than X". (There are no ties, and everybody's comparable.)

My readers who are not mathematicians are probably thinking that these are ridiculous assumptions. This is true. In particular, the first one seems silly to me -- we don't meet people at random, but through other people we know, so I suspect that the longer one spends living the more one tends to find people one likes. This certainly is true in my experience when seeking out friends -- people who I like spending time with tend to know other people I'd like spending time with. The inability to go back to previous suitors seems to be not a horrible approximation. The fact that everyone is rankable seems at first like a bad assumption -- but we manage to do it for economic goods all the time. For example, houses have prices which are scalars, despite the fact that there are multiple dimensions along which houses can be compared. The fourth assumption, that you know how many potential suitors there are, seems the most wrong to me. But combined with the assumption that you meet suitors at a constant rate, this converts strategies which talk about numbers of suitors to strategies which talk about time.

My readers who are mathematicians probably didn't read the previous paragraph.

Anyway, the optimal strategy is to reject the first N/e of the people you meet, and then pick the first person you meet who's better than everyone you'd met previously. The probability of this strategy succeeding -- in that you pick the very best person -- is close to 1/e when N is large.

I'm pretty sure I first heard this around fifteen years ago, and have probably heard it at least once a year since then -- but I didn't know a proof until now. (Strictly speaking, there's some hand-waving in the argument given there, as there always is whenever someone says "X is approximately equal to Y" without giving any sort of bound on X-Y or X/Y -- but I don't plan to use this to prove anything else, so I'm convinced.)

Malthus is overrated

Malthus, the false prophet, from The Economist, and Costs of Living, a review of Common Wealth: Economics for a Crowded Planet by Jeffrey Sachs.


Sachs' book is about how to avert global economic catastrophe, which is obviously something worth worrying about. Basically, he seems to be saying that global cooperation is necessary, because "we're all in this together". He also argues, it seems, that population growth is bad; I found the article from Greg Mankiw's blog. Mankiw quotes the end of the review:

In an age when we don’t need to have lots of children to work the fields, or to compensate for high infant mortality, Sachs argues that it’s both economically rational — and crucial for a future of sustainable growth — for people to reproduce at a rate close to 2.1 children per family. In his acknowledgments, Sachs thanks his three children.

But Mankiw pointed out in 1998 that it's not necessarily true that population growth is bad. It seems like a lot of people like to quote Thomas Malthus on this, who said that population grows exponentially with time (true) but that food production ability only grows linearly. As far as I know Malthus had no reasonable argument for this; people talk about the Malthusian catastrophe. But if you actually look at the relevant section in An Essay on the Principle of Population, in chapter 1 Malthus just postulates these growth rates. In Chapter 2 he offers as justification for this basically that there's not enough room in England for the farms to feed an exponentially growing population. But there's not room for an exponentially growing population itself either!

It would be one thing if, say, farms fell from the sky at a constant rate. But farms are made by people; thus if people grow exponentially so will farms.

Now, I'm not saying that we aren't running out of room. It's obvious that some land is better for farming than other land, and people will tend to farm the better land first; as time goes on we will be obliged to farm more and more of the inferior land, therefore decreasing the amount of food grown per person.

But Malthus was writing in 1798. He assumes that the population is producing just enough food for itself in his time, and then goes on to say:

In two centuries and a quarter, the population would be to the means of subsistence as 512 to 10.

Two centuries and a quarter is 2023; roughly speaking, now. We clearly have much more than two percent of the food we need.

Of course, it's possible -- as is pointed out in every introductory computer science class -- that polynomial growth can outstrip exponential growth over some short time, and we're not in the limiting regime yet. But I don't think anybody is seriously saying this. And anyway, Malthus made the stronger claim that food production is growing linearly.

(Does Malthus get more sophisticated than this? I'm just cherry-picking, but skimming his work it seems to continue in roughly the same vein.)

Now, this is an obvious criticism -- but somehow it rarely gets pointed out. Mankiw pointed it out, though -- sure, people use resources. But they also create resources. People will eat food. But they will also figure out how to grow more food. That is, if we don't just disintegrate into a society of virtual reality addicts first.

edited, 11:08 am: Also from the NYT, Deaths are outpacing births in the Pittsburgh metropolitan area. I'm not sure how meaningful this is on a national level, because people move around.

A little number theory problem

Here's an interesting little problem, taken from Chapter Zero which I recently discovered.

It was once asked on the Math GRE -- what's the greatest common divisor of p⁴-1 over all primes p > 5? It's an odd way to formulate the question, but it's simple enough.

First, remember the possibly familiar fact that for primes p > 3, p²-1 is a multiple of 24. This is simple enough -- we can write p²-1 = (p-1)(p+1). Since p is odd, both of these factors are divisible by 2, and one of them is divisible by 4. So p² - 1 is a multiple of 8. (This is true for all odd numbers, not just primes.) Furthermore, since p isn't a multiple of 3, either p-1 or p+1 is. So p² - 1 is divisible by 8 and by 3, therefore by 24.

This suggests an approach to the analogous problem for fourth powers, which is basically taken from the original post. A bit of numerical experimentation gives 7⁴-1 = 2400, 11⁴ - 14640, 13⁴ - 1 = 28560, ... -- all of these are divisible by 240. So you start to suspect that 240 might be the answer. And it turns out that it is; we can write

p⁴ - 1 = (p-1)(p+1)(p²+1).

Now, what power of 2 appears in the prime factorization of p⁴-1? Each of the three factors on the right-hand side is even; furthermore one of p-1 or p+1 must be divisible by 4, so there are at least four occurrences of 2.

Similarly, either p-1 or p+1 is divisible by 3.

And p⁴ - 1 is divisible by 5 by Fermat's little theorem. (A brute-force analysis is also possible -- if p is congruent to 1 mod 5 then p-1 is divisible by 5, if p is congruent to 4 mod 5 then p+1 is divisible by 5, and is p is congruent to ± 2 mod 5 then p² + 1 is divisible by 5.)

So p⁴ - 1 is divisible by 2⁴ 3¹ 5¹, which is 240, for all primes p > 5. We can easily see that, say, gcd(11⁴-1, 13⁴ - 1) = 240. So 240 is the answer.

The original post which I found this from asked two questions:

• can this be done in a less ad hoc manner?


• are there generalizations?

The method generalizes pretty easily to other powers; by a similar analysis, the gcd of p⁶ - 1 over primes p > 7 is 504. For eighth powers, 480. For tenth powers, 264. (In all cases, when taking nth powers we require p > n+1.)

There's no pattern obvious in these numbers, though. But they turn out to be related to the Bernoulli numbers. If you know more about this sort of thing that I do you might try to prove (or disprove) that:

Conjecture. gcd(p^a - 1), taken over primes p > a+1, is the denominator of B_a/(2a), where B_a are the Bernoulli numbers.

(I have not made any attempt at all to determine if this is known. Feel free to point out if it is!)