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.


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.


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.


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.


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.


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 consist 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 »

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

\displaystyle Y : C \ni c \mapsto \text{Hom}(-, c) \in \widehat{C}

into its presheaf category \widehat{C} = [C^{op}, \text{Set}] (where we use [C, D] to denote the category of functors C \to D). The Yoneda lemma asserts in particular that Y is full and faithful, which justifies calling it an embedding.

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

Theorem: The Yoneda embedding Y : C \to \widehat{C} exhibits \widehat{C} as the free cocompletion of C in the sense that for any cocomplete category D, the restriction functor

\displaystyle Y^{\ast} : [\widehat{C}, D]_{\text{cocont}} \to [C, D]

from the category of cocontinuous functors \widehat{C} \to D to the category of functors C \to D is an equivalence. In particular, any functor C \to D extends (uniquely, up to natural isomorphism) to a cocontinuous functor \widehat{C} \to D, and all cocontinuous functors \widehat{C} \to D 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 \widehat{C} is the category obtained by “freely gluing together” the objects of C 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 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 G be a finite p-group acting on a finite set X. Let X^G denote the subset of X consisting of those elements fixed by G. Then |X^G| \equiv |X| \bmod p; in particular, if p \nmid |X| then G has a fixed point.

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


Read Full Post »

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 q be a prime power, let n be a positive integer, and consider the distribution of irreducible factors of degree 1, 2, ... k in a random monic polynomial of degree n over \mathbb{F}_q. Then, as q \to \infty, this distribution is asymptotically the distribution of cycles of length 1, 2, ... k in a random permutation of n elements.

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

Combined with our previous result, we conclude that as q, n \to \infty (with q tending to infinity sufficiently quickly relative to n), the distribution of irreducible factors of degree 1, 2, ... k is asymptotically independent Poisson with parameters 1, \frac{1}{2}, ... \frac{1}{k}.


Read Full Post »

Older Posts »