Feeds:
Posts
Comments

Archive for the ‘math.CO’ Category

In the previous post we described a fairly straightforward argument, using generating functions and the saddle-point bound, for giving an upper bound

\displaystyle p(n) \le \exp \left( \pi \sqrt{ \frac{2n}{3} } \right)

on the partition function p(n). In this post I’d like to record an elementary argument, making no use of generating functions, giving a lower bound of the form \exp C \sqrt{n} for some C > 0, which might help explain intuitively why this exponential-of-a-square-root rate of growth makes sense.

The starting point is to think of a partition of n as a Young diagram of size n, or equivalently (in French coordinates) as a lattice path from somewhere on the y-axis to somewhere on the x-axis, which only steps down or to the right, such that the area under the path is n. Heuristically, if the path takes a total of L steps then there are about 2^L such paths, and if the area under the path is n then the length of the path should be about O(\sqrt{n}), so this already goes a long way towards explaining the exponential-of-a-square-root behavior.

(more…)

Read Full Post »

(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.

(more…)

Read Full Post »

Two weeks ago we proved the following formula. Let G be a finitely generated group and let a_n be the number of subgroups of G of index n. Then

\displaystyle \sum_{n \ge 0} \frac{|\text{Hom}(G, S_n)|}{n!} z^n = \exp \left( \sum_{n \ge 1} \frac{a_n}{n} z^n \right).

This identity reflects, in a way we made precise in the previous post, the decomposition of a finite G-set (the terms on the LHS) into a disjoint union of transitive G-sets (the terms on the RHS).

Noam Zeilberger commented on the previous post that he had seen results like this for more specific groups in the literature; in particular, Samuel Vidal describes a version of this analysis for G = \Gamma = PSL_2(\mathbb{Z}), the modular group. In this post we’ll use the above formula to compute the number of subgroups of index n in \Gamma using a computer algebra system that can manipulate power series. We’ll also say something about how to visualize these subgroups.

(more…)

Read Full Post »

Yesterday I described the answer to the puzzle of what the generating function

\displaystyle \log \sum_{n \ge 0} n! z^n = z + \frac{3}{2} z^2 + \frac{13}{3} z^3 + \frac{71}{4} z^4 + \dots

counts by sketching a proof of the following more general identity: if G is a finitely generated group and a_n is the number of subgroups of G of index n, then

\displaystyle \sum_{n \ge 0} \frac{|\text{Hom}(G, S_n)|}{n!} z^n = \exp \left( \sum_{n \ge 1} \frac{a_n}{n} z^n \right).

The main ingredient is the exponential formula, but the discussion of the proof involved some careful juggling to make sure we weren’t inappropriately quotienting out by various symmetries, and one might find this conceptually unsatisfying. The goal of today’s post is to state a categorical result which describes exactly how to juggle these symmetries and gives a conceptually clean proof of the above identity.

The key is to describe in exactly what sense a finite G-set (corresponding to the LHS) has a canonical “connected components” decomposition as a disjoint union of transitive G-sets (corresponding to the RHS), which is the following.

Claim: The symmetric monoidal groupoid of finite G-sets, with symmetric monoidal structure given by disjoint union, is the free symmetric monoidal groupoid on the groupoid of transitive finite G-sets.

From here, we’ll use a version of the exponential formula that comes from relating (weighted) groupoid cardinalities of a groupoid and of the free symmetric monoidal groupoid on it.

(more…)

Read Full Post »

The answer to the puzzle

Two days ago, as a puzzle, I asked what the generating function

\displaystyle \log \sum_{n \ge 0} n! z^n = z + \frac{3}{2} z^2 + \frac{13}{3} z^3 + \frac{71}{4} z^4 + \dots

counts. Yesterday, I suggested as a hint that it might be useful to interpret that n! as \frac{n!^2}{n!}, and to use the exponential formula.

The answer to the puzzle can be described in several ways. Below I’ll use a description that suggests a generalization I particularly like.

(more…)

Read Full Post »

MaBloWriMo continues with a hint

Yesterday, as a puzzle, I asked what the generating function

\displaystyle \log \sum_{n \ge 0} n! z^n = z + \frac{3}{2} z^2 + \frac{13}{3} z^3 + \frac{71}{4} z^4 + \dots

counts. Today I’ll give some hints; unfortunately I did not have enough time to write up a satisfying solution. As commenter Zahlen points out, it’s better to think of \sum_{n \ge 0} n! z^n, not as an ordinary generating function, but as an exponential generating function. That makes it the exponential generating function of the sequence (n!)^2 of squared factorials.

The reason we’d like to do this, although Zahlen didn’t make this explicit, is that this maneuver opens up the possibility of appealing to the exponential formula. Loosely speaking, the exponential formula can be interpreted as saying that if some exponential generating function f(z) counts objects that have a decomposition into “connected components,” then \log f(z) counts connected objects. For example, when f(z) = \frac{1}{1 - z} (the exponential generating function of the factorials), the logarithm is

\displaystyle \log f(z) = \log \frac{1}{1 - z} = \sum_{n \ge 1} \frac{z^n}{n}

and this can be interpreted as reflecting the cycle decomposition of a permutation.

So: what is the relevant “connected components” decomposition here?

Read Full Post »

MaBloWriMo begins with a puzzle

It’s time to try writing a blog post every day of November again. This time I’ll really try to make the posts shorter.

This one will consistent entirely of a puzzle. Consider the formal power series

\displaystyle f(z) = \sum_{n \ge 0} n! z^n = 1 + z + 2z^2 + 6z^3 + 24 z^4 + \dots

giving the ordinary generating function of the factorials. This power series has zero radius of convergence, but it still makes sense formally. Its logarithm

\displaystyle \log f(z) = \sum_{n \ge 1} \frac{(1 - f(z))^n}{n} = z + \frac{3z^2}{2} + \frac{13 z^3}{3} + \frac{71 z^4}{4} + \dots

is another formal power series of the form \displaystyle \sum_{n \ge 1} \frac{a_n z^n}{n}, where the a_n turn out to be positive integers.

Puzzle: What do the a_n count?

No cheating using the OEIS! That’s no fun anyway.

Read Full Post »

Older Posts »