More on partition asymptotics

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

on the partition function . In this post I’d like to record an elementary argument, making no use of generating functions, giving a lower bound of the form for some , 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 as a Young diagram of size , 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 . Heuristically, if the path takes a total of steps then there are about such paths, and if the area under the path is then the length of the path should be about , so this already goes a long way towards explaining the exponential-of-a-square-root behavior.

Read Full Post »

The man who knew partition asymptotics

(Part I of this post is here)

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

.

This is a major plot point in the new Ramanujan movie, where Ramanujan conjectures this result and MacMahon challenges him by agreeing to compute 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.

Read Full Post »

Finite index subgroups of the modular group

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

.

This identity reflects, in a way we made precise in the previous post, the decomposition of a finite -set (the terms on the LHS) into a disjoint union of transitive -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 , the modular group. In this post we’ll use the above formula to compute the number of subgroups of index in using a computer algebra system that can manipulate power series. We’ll also say something about how to visualize these subgroups.

Read Full Post »

The categorical exponential formula

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

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

.

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 -set (corresponding to the LHS) has a canonical “connected components” decomposition as a disjoint union of transitive -sets (corresponding to the RHS), which is the following.

Claim: The symmetric monoidal groupoid of finite -sets, with symmetric monoidal structure given by disjoint union, is the free symmetric monoidal groupoid on the groupoid of transitive finite -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.

Read Full Post »

The answer to the puzzle

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

counts. Yesterday, I suggested as a hint that it might be useful to interpret that as , 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.

Read Full Post »

MaBloWriMo continues with a hint

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

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 , not as an ordinary generating function, but as an exponential generating function. That makes it the exponential generating function of the sequence 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 counts objects that have a decomposition into “connected components,” then counts connected objects. For example, when (the exponential generating function of the factorials), the logarithm is

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 consist entirely of a puzzle. Consider the formal power series

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

is another formal power series of the form , where the turn out to be positive integers.

Puzzle: What do the count?

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

Read Full Post »

The free cocompletion I

Let be a (locally small) category. Recall that any such category naturally admits a Yoneda embedding

into its presheaf category (where we use to denote the category of functors ). The Yoneda lemma asserts in particular that is full and faithful, which justifies calling it an embedding.

When is in addition assumed to be small, the Yoneda embedding has the following elegant universal property.

Theorem: The Yoneda embedding exhibits as the free cocompletion of in the sense that for any cocomplete category , the restriction functor

from the category of cocontinuous functors to the category of functors is an equivalence. In particular, any functor extends (uniquely, up to natural isomorphism) to a cocontinuous functor , and all cocontinuous functors arise this way (up to natural isomorphism).

Colimits should be thought of as a general notion of gluing, so the above should be understood as the claim that is the category obtained by “freely gluing together” the objects of in a way dictated by the morphisms. This intuition is important when trying to understand the definition of, among other things, a simplicial set. A simplicial set is by definition a presheaf on a certain category, the simplex category, and the universal property above says that this means simplicial sets are obtained by “freely gluing together” simplices.

In this post we’ll content ourselves with meandering towards a proof of the above result. In a subsequent post we’ll give a sampling of applications.

Read Full Post »

The p-group fixed point theorem

The goal of this post is to collect a list of applications of the following theorem, which is perhaps the simplest example of a fixed point theorem.

Theorem: Let be a finite -group acting on a finite set . Let denote the subset of consisting of those elements fixed by . Then ; in particular, if then has a fixed point.

Although this theorem is an elementary exercise, it has a surprising number of fundamental corollaries.

Read Full Post »

Small factors in random polynomials over a finite field

Previously I mentioned very briefly Granville’s The Anatomy of Integers and Permutations, which explores an analogy between prime factorizations of integers and cycle decompositions of permutations. Today’s post is a record of the observation that this analogy factors through an analogy to prime factorizations of polynomials over finite fields in the following sense.

Theorem: Let be a prime power, let be a positive integer, and consider the distribution of irreducible factors of degree in a random monic polynomial of degree over . Then, as , this distribution is asymptotically the distribution of cycles of length in a random permutation of elements.

One can even name what this random permutation ought to be: namely, it is the Frobenius map acting on the roots of a random polynomial , whose cycles of length are precisely the factors of degree of .

Combined with our previous result, we conclude that as (with tending to infinity sufficiently quickly relative to ), the distribution of irreducible factors of degree is asymptotically independent Poisson with parameters .

Read Full Post »