The Simpsons and continuous compounding

It appears the Simpsons have a mortgage that has 37% interest compounded every minute.

For the record, if the interest is compounded n times per year, then their interest wud be (1+0.37/n)ⁿ-1 compounded annually. If n = 12 (monthly), this is 43.97% per year; if n = 525,600 (every minute), this is 44.7734426% annually; compare 44.7734615% = exp(0.37)-1 for continuous compounding. In other words, compounding every minute might as well be continuous; the difference is one cent per $53,000 or so, per year.

The difference between every-minute and continuous compounding, at an interest rate of r, is the difference

exp(r) - 1 - (1+r/n)ⁿ

where n = 525,600; this is asymptotically r²/(2n). (This actually isn't a great approximation here; the next few terms of the series are reasonably large.)

Why do the Catalan numbers grow like they do?

So "everybody knows" that the nth Catalan number is given by , and furthermore that they have the asymptotic form

(Okay, I'll confess: I knew the first term, and I got Maple to calculate the others just now.)

So I found myself wondering -- why this n^-3/2? Let D_n = 4^-n C_n. Then

and so we get

; furthermore that sum is about -(3/2) log n, for large n, and so D_n is about n_-3/2. The replacement of 1-x with exp(-x) obviously would need to be justified (and such justification would explain the presence of the mysterious π) but I'm still amused that this simple computation got the exponent.

The asymptotics of "27 lines on a cubic"

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

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

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

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

where

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

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

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

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

and variance which is the sum of their variances,

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

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

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

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

and now note that

Therefore

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

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

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.

Gosper's modification of Stirling's approximation

From Math Forum: an improvement of Stirling's approximation, credited to Gosper:

The usual approximation is

which is just the beginning of an asymptotic series

and we can rewrite the square root to get

and combining the two square roots gives us

which is what we wanted. This is basically a combination of the first two terms of the usual Stirling approximation into one term. For example, when n = 8 this gives 40316, compared to 39902 for the first term of Stirling's series and 40318 for the first two. (8! = 40320.) In general the error of Gosper's approximation is about twice that in the first two terms of Stirling's, so this isn't incredibly useful but it's an interesting curiosity.

Should everyone know number theory?

From Anarchaia: Why everyone should know number theory, by Minhyong Kim.

I'm not convinced, even if "everyone" means "all mathematicians". Kim's argument seems to be that everything mathematicians ever write down is a finite collection of data and that that data can be written down as some very large number (say you enter it into a computer and consider the corresponding binary string of 0s and 1s as an integer). This reminds me of the idea of Godel numbers (which assign a number to each logical statement in a certain language), and writing down the rules that allow you to get from one Godel number which represents a true statement to another is impossibly ugly.

However, I'm really just getting this from the title, which Kim eventually admits is an exaggeration. Kim later says:

However, there is an even more essential reason why most practicing mathematicians can get by with a rather naive understanding of numbers and might be better off doing so. This is because of the extremely useful geometric picture of the real and complex numbers. Much of the time, it is perfectly reasonable to view the complex numbers as a geometric plane, and base all other constructions upon that picture, oblivious to the fine structure of our objects, pretty much as one can do plenty of classical physics without worrying about the fact that the macroscopic objects we are considering arise from the complicated interaction of elementary particles. Now, my claim is that the role of a number theorist in mathematics is exactly analogous to te role of a particle theorist in physics.

If that's true, why does everyone need to know number theory? Still, there are times when it's useful. To take a simple example, consider the central binomial coefficients,

,

or even more generally any binomial coefficient at all. The binomial coefficients have nice number-theoretic properties; for example, if you look at them modulo 2, and color the odd ones black and the even ones white, you get something that looks suspiciously like the Sierpinski triangle. But parity is fine structure; this particular result comes out of looking at how many factors of 2 are in the numerator and the denominator and subtracting them, and usually there are about the same number so one has to be careful about cancellations. A lot of the time what one really cares about is approximately how large this coefficient is. For this sort of question it's useful to use Stirling's approximation,

which allows us to determine lots of things about the sizes of things involving factorials -- for example, binomial coefficients -- without getting anywhere near close enough to them to determine their parity.

For example, it turns out that

which is the sort of information that might be useful in, say, probability; if I have some number of objects which are counted by the central binomial coefficients, and I want to know that, say, the proportion of them having some particular property is very small, this is much more valuable than knowing, say, the complete prime factorization of a binomial coefficient.

The essay does give some interesting examples, though -- the classical ones are things like doubling the cube and squaring the circle, and there are a bunch of modern examples of theorems which are in complex geometry but whose proofs require number theory. The paper builds up to a famous theorem of Matiyasevich, which says that "listable" sets of natural numbers (those for which we can write a computer program that will output all the numbers in the set, and no others) and Diophantine sets (those which are sets of solutions to polynomial equations with integer coefficients) are the same; so if you buy into the idea that all mathematics can be encoded in "things computers can do" then you essentially have to believe this number-theoretic hypothesis. And it's hard not to believe that about computers. I have sometimes told my students that if they are attempting to solve a problem, they only know a small number of things, so they could just try all of them. The mathematical community as a whole knows a large number of things, but stil a finite number, so if we wanted a computer to solve a mathematical problem we could conceivably enter it in some suitable form into a computer, along with all the facts we know, and tell the computer to "try everything". This isn't practical, though, which is why we still have mathematicians.

However, the polynomials corresponding to "simple" listable sets are not so nice; there's a polynomial of degree 25 in 26 variables all of whose positive values are primes. You can see it here. (Supposedly the degree can be reduced to 10; 26 is kind of cute, though, because it's the number of letters in our alphabet.)

Kim also gives brief outlines of how the four-color theorem could have been proven this way, and a possible proof of the Poincare conjecture via the same method (basically, it's enough to prove it for simplicial complexes, which we can enumerate, although there are some annoying problems, namely that we can't determine if a group is trivial by looking at its presentation. Maybe these reductions aren't so trivial after all.