Feeds:
Posts

## The man who knew partition asymptotics

(Part I of this post is here)

Let $p(n)$ denote the partition function, which describes the number of ways to write $n$ as a sum of positive integers, ignoring order. In 1918 Hardy and Ramanujan proved that $p(n)$ is given asymptotically by

$\displaystyle p(n) \approx \frac{1}{4n \sqrt{3}} \exp \left( \pi \sqrt{ \frac{2n}{3} } \right)$.

This is a major plot point in the new Ramanujan movie, where Ramanujan conjectures this result and MacMahon challenges him by agreeing to compute $p(200)$ and comparing it to what this approximation gives. In this post I’d like to describe how one might go about conjecturing this result up to a multiplicative constant; proving it is much harder.

## The man who knew elliptic integrals, prime number theorems, and black holes

I went to see The Man Who Knew Infinity yesterday. I have nothing much to say about the movie as a movie that wasn’t already said in Scott Aaronson‘s review, except that I learned a few fun facts during the Q&A session with writer/director Matthew Brown afterwards. Namely, it’s a little surprising the movie was able to get high-profile stars like Dev Patel and Jeremy Irons on board given that it was made on a relatively low budget. Apparently, Dev Patel signed on because he really wanted to popularize the story of Ramanujan, and Jeremy Irons signed on because he was hooked after being given a copy of Hardy’s A Mathematician’s Apology.

(Disclaimer: this blog does not endorse any of the opinions Hardy expresses in the Apology, e.g. the one about mathematics being a young man’s game, the one about pure math being better than applied math, or the one about exposition being an unfit activity for a real mathematician. The opinion of this blog is that the Apology should be read mostly for insight into Hardy’s psychology rather than for guidance about how to do mathematics.)

Anyway, since this is a movie about Ramanujan, let’s talk about some of the math that appears in the movie. It’s what he would have wanted, probably.

## Estimating roots

In lieu of a real blog post, which will have to wait for at least another two weeks, let me offer an estimation exercise: bound, as best you can, the unique positive real root of the polynomial

$\displaystyle x^{10000} + x^{100} - 1$.

The intermediate value theorem shows that $x \in (0, 1)$, which was the subject of a recent math.SE question that provided the inspiration for this question. I provide a stronger lower bound on $x$ using elementary inequalities and entirely by hand in an answer to the linked question, although I don’t try to improve the upper bound.

## Optimizing parameters

I came across a fun problem recently that gave me a good opportunity to exercise my approximation muscles.

Problem: Compute $\displaystyle \lim_{n \to \infty} \frac{n + \sqrt{n} + \sqrt[3]{n} + ... + \sqrt[n]{n}}{n}$, if it exists.

The basic approach to such sums is that the first few terms contribute to the sum because they are large and the rest of the terms contribute to the sum because there are a lot of them, so it makes sense to approximate the two parts of the sum separately. This is an important idea, for example, in certain estimates in functional analysis.

Since $\sqrt[k]{n} \ge 1, k \ge 2$ it follows that the limit, if it exists, is at least $\lim_{n \to \infty} \frac{2n-1}{n} = 2$. In fact, this is the precise value of the limit. We’ll show this by giving progressively sharper estimates of the quantity

$\displaystyle E_n = \frac{1}{n} \sum_{k=2}^{n} \left( \sqrt[k]{n} - 1 \right)$.

In the discussion that follows I’m going to ignore a lot of error terms to simplify the computations.