Feeds:
Posts

## The free cocompletion I

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.

## 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 $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.

## 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 $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}$.

## Short cycles in random permutations

Previously we showed that the distribution of fixed points of a random permutation of $n$ elements behaves asymptotically (in the limit as $n \to \infty$) like a Poisson random variable with parameter $\lambda = 1$. As it turns out, this generalizes to the following.

Theorem: As $n \to \infty$, the number of cycles of length $1, 2, ... k$ of a random permutation of $n$ elements are asymptotically independent Poisson with parameters $1, \frac{1}{2}, ... \frac{1}{k}$.

This is a fairly strong statement which essentially settles the asymptotic description of short cycles in random permutations.

## Fixed points of random permutations

The following two results are straightforward and reasonably well-known exercises in combinatorics:

1. The number of permutations on $n$ elements with no fixed points (derangements) is approximately $\frac{n!}{e}$.
2. The expected number of fixed points of a random permutation on $n$ elements is $1$.

As it turns out, it is possible to say substantially more about the distribution of fixed points of a random permutation. In fact, the following is true.

Theorem: As $n \to \infty$, the distribution of the number of fixed points of a random permutation on $n$ elements is asymptotically Poisson with rate $\lambda = 1$.

## Moments, Hankel determinants, orthogonal polynomials, Motzkin paths, and continued fractions

Previously we described all finite-dimensional random algebras with faithful states. In this post we will describe states on the infinite-dimensional $^{\dagger}$-algebra $\mathbb{C}[x]$. Along the way we will run into and connect some beautiful and classical mathematical objects.

A special case of part of the following discussion can be found in an old post on the Catalan numbers.

## Update, and the combinatorics of quintic equations

A brief update. I’ve been at Cambridge for the last week or so now, and lectures have finally started. I am, tentatively, taking the following Part II classes:

• Riemann Surfaces
• Topics in Analysis Probability and Measure
• Graph Theory
• Linear Analysis (Functional Analysis)
• Logic and Set Theory

I will also attempt to sit in on Part III Algebraic Number Theory, and I will also be self-studying Part II Number Theory and Galois Theory for the Tripos.

As far as this blog goes, my current plan is to blog about interesting topics which come up in my lectures and self-study, partly as a study tool and partly because there are a few big theorems I’d like to get around to understanding this year and some of the material in my lectures will be useful for those theorems.

Today I’d like to blog about something completely different. Here is a fun trick the first half of which I learned somewhere on MO. Recall that the Abel-Ruffini theorem states that the roots of a general quintic polynomial cannot in general be written down in terms of radicals. However, it is known that it is possible to solve general quintics if in addition to radicals one allows Bring radicals. To state this result in a form which will be particularly convenient for the following post, this is equivalent to being able to solve a quintic of the form

$\displaystyle y = 1 + xy^5$

for $y$ in terms of $x$. It just so happens that a particular branch of the above function has a particularly nice Taylor series; in fact, the branch analytic in a neighborhood of the origin is given by

$\displaystyle y = \sum_{n \ge 0} \frac{1}{4n+1} {5n \choose n} x^n$.

This should remind you of the well-known fact that the generating function $\displaystyle y = \sum_{n \ge 0} \frac{1}{n+1} {2n \choose n} x^n$ for the Catalan numbers satisfies $y = 1 + xy^2$. In fact, there is a really nice combinatorial proof of the following general fact: the generating function $\displaystyle y = \sum_{n \ge 0} \frac{1}{(k-1)n+1} {kn \choose n} x^n$ satisfies

$y = 1 + xy^k$.

## Test your intuition: consecutive tails

Something very unfortunate has happened: several things I have recently written that could have been blog entries are instead answers on math.SE! In the interest of exposition beyond the Q&A format I am going to “rescue” one of these answers. It is an answer to the following question, which I would like you to test your intuition about:

Flip $150$ coins. What is the probability that, at some point, you flipped at least $7$ consecutive tails?

Jot down a quick estimate; see if you can get within a factor of $2$ or so of the actual answer, which is below the fold.

## Walks on graphs and statistical mechanics

I finally learned the solution to a little puzzle that’s been bothering me for awhile.

The setup of the puzzle is as follows. Let $G$ be a weighted undirected graph, e.g. to each edge $i \leftrightarrow j$ is associated a non-negative real number $a_{ij}$, and let $A$ be the corresponding weighted adjacency matrix. If $A$ is stochastic, one can interpret the weights $a_{ij}$ as transition probabilities between the vertices which describe a Markov chain. (The undirected condition then means that the transition probability between two states doesn’t depend on the order in which the transition occurs.) So one can talk about random walks on such a graph, and between any two vertices the most likely walk is the one which maximizes the product of the weights of the corresponding edges.

Suppose you don’t want to maximize a product associated to the edges, but a sum. For example, if the vertices of $G$ are locations to which you want to travel, then maybe you want the most likely random walk to also be the shortest one. If $E_{ij}$ is the distance between vertex $i$ and vertex $j$, then a natural way to do this is to set

$a_{ij} = e^{- \beta E_{ij}}$

where $\beta$ is some positive constant. Then the weight of a path is a monotonically decreasing function of its total length, and (fudging the stochastic constraint a bit) the most likely path between two vertices, at least if $\beta$ is sufficiently large, is going to be the shortest one. In fact, the larger $\beta$ is, the more likely you are to always be on the shortest path, since the contribution from any longer paths becomes vanishingly small. As $\beta \to \infty$, the ring in which the entries of the adjacency matrix lives stops being $\mathbb{R}$ and becomes (a version of) the tropical semiring.

That’s pretty cool, but it’s not what’s been puzzling me. What’s been puzzling me is that matrix entries in powers of $A$ look an awful lot like partition functions in statistical mechanics, with $\beta$ playing the role of the inverse temperature and $E_{ij}$ playing the role of energies. So, for awhile now, I’ve been wondering whether they actually are partition functions of systems I can construct starting from the matrix $A$. It turns out that the answer is yes: the corresponding systems are called one-dimensional vertex models, and in the literature the connection to matrix entries is called the transfer matrix method. I learned this from an expository article by Vaughan Jones, “In and around the origin of quantum groups,” and today I’d like to briefly explain how it works.

## Hecke algebras and the Kazhdan-Lusztig polynomials

The Hecke algebra attached to a Coxeter system $(W, S)$ is a deformation of the group algebra of $W$ defined as follows. Take the free $\mathbb{Z}[q^{ \frac{1}{2} }, q^{ - \frac{1}{2} }]$-module $\mathcal{H}_W$ with basis $T_w, w \in W$, and impose the multiplicative relations

$T_w T_s = T_{ws}$

if $\ell(sw) > \ell(w)$, and

$T_w T_s = q T_{ws} + (q - 1) T_w$

otherwise. (For now, ignore the square root of $q$.) Humphreys proves that these relations describe a unique associative algebra structure on $\mathcal{H}_W$ with $T_e$ as the identity, but the proof is somewhat unenlightening, so I will skip it. (Actually, the only purpose of this post is to motivate the definition of the Kazhdan-Lusztig polynomials, so I’ll be referencing the proofs in Humphreys rather than giving them.)

The motivation behind this definition is a somewhat long story. When $W$ is the Weyl group of an algebraic group $G$ with Borel subgroup $B$, the above relations describe the algebra of functions on $G(\mathbb{F}_q)$ which are bi-invariant with respect to the left and right actions of $B(\mathbb{F}_q)$ under a convolution product. The representation theory of the Hecke algebra is an important tool in understanding the representation theory of the group $G$, and more general Hecke algebras play a similar role; see, for example MO question #4547 and this Secret Blogging Seminar post. For example, replacing $G$ and $B$ with $\text{SL}_2(\mathbb{Q})$ and $\text{SL}_2(\mathbb{Z})$ gives the Hecke operators in the theory of modular forms.