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.

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

## Lower bounds on off-diagonal Ramsey numbers

The goal of this post is to prove the following elementary lower bound for off-diagonal Ramsey numbers $R(s, t)$ (where $s \ge 3$ is fixed and we are interested in the asymptotic behavior as $t$ gets large):

$\displaystyle R(s, t) = \Omega \left( \left( \frac{t}{\log t} \right)^{ \frac{s}{2} } \right).$

The proof does not make use of the Lovász local lemma, which improves the bound by a factor of $\left( \frac{t}{\log t} \right)^{ \frac{1}{2} }$; nevertheless, I think it’s a nice exercise in asymptotics and the probabilistic method. (Also, it’s never explicitly given in Alon and Spencer.)

## The Schrödinger equation on a finite graph

One of the most important discoveries in the history of science is the structure of the periodic table. This structure is a consequence of how electrons cluster around atomic nuclei and is essentially quantum-mechanical in nature. Most of it (the part not having to do with spin) can be deduced by solving the Schrödinger equation by hand, but it is conceptually cleaner to use the symmetries of the situation and representation theory. Deducing these results using representation theory has the added benefit that it identifies which parts of the situation depend only on symmetry and which parts depend on the particular form of the Hamiltonian. This is nicely explained in Singer’s Linearity, symmetry, and prediction in the hydrogen atom.

For awhile now I’ve been interested in finding a toy model to study the basic structure of the arguments involved, as well as more generally to get a hang for quantum mechanics, while avoiding some of the mathematical difficulties. Today I’d like to describe one such model involving finite graphs, which replaces the infinite-dimensional Hilbert spaces and Lie groups occurring in the analysis of the hydrogen atom with finite-dimensional Hilbert spaces and finite groups. This model will, among other things, allow us to think of representations of finite groups as particles moving around on graphs.

## Ramsey theory and Fermat’s Last Theorem

In the first few lectures of Graph Theory, the lecturer (Paul Russell) presented a cute application of Ramsey theory to Fermat’s Last Theorem. It makes a great introduction to the general process of casting a problem in one branch of mathematics as a problem in another and is the perfect size for a blog post, so I thought I’d talk about it.

The setup is as follows. One naive way to go about proving the nonexistence of nontrivial integer solutions to $x^n + y^n = z^n, n > 2$ (that is, solutions such that $x, y, z$ are not equal to zero) is using modular arithmetic; that is, one might hope that for every $n > 2$ it might be possible to find a modulus $m$ such that the equation has no nontrivial solution $\bmod m$. To simplify matters, we’ll assume that $x, y, z$ are relatively prime to $m$, or else there is some subtlety in the definition of “nontrivial” (e.g. we might have $x, y, z$ not divisible by $m$ but $x^n \equiv 0 \bmod m$.) Note that it might be the case that $m$ is not relatively prime to a particular nontrivial solution in the integers, but if we can prove non-existence of nontrivial solutions for infinitely many $m$ (in particular, such that any integer is relatively prime to at least one such $m$) then we can conclude that no nontrivial integer solutions exist.

By the Chinese Remainder Theorem, this is possible if and only if it is possible with $m$ a prime power, say $m = p^k$. If $p$ is relatively prime to $n$, this is possible if and only if it is possible with $m = p$. This is because given a nontrivial solution $\bmod p$ we can use Hensel’s lemma to lift it to a nontrivial solution $\bmod p^k$ for any $k$ (and even to $\mathbb{Z}_p$), and the converse is obvious. (Again to simplify matters, we’ll ignore the finitely many primes that divide $n$.) So we are led to the following question.

For a fixed positive integer $n > 2$ do there exist infinitely many primes $p$ relatively prime to $n$ such that $x^n + y^n \equiv z^n \bmod p$ has no nontrivial solutions?

As it turns out, the answer is no. In 1916 Schur found a clever way to prove this by proving the following theorem.

Theorem: For every positive integer $k$ there exists a positive integer $m$ such that if $\{ 1, 2, ... m \}$ is partitioned into $k$ disjoint subsets $A_1, ... A_k$, then there exists $i$ such that there exist $a, b, c \in A_i$ with $a + b = c$. In other words, the Schur number $S(k) = m$ exists. (Note that I am using a convention which is off by $1$.)

If we let $p$ be a prime greater than $S(n)$ and let the $A_i$ be the cosets of the subgroup of $n^{th}$ powers in $(\mathbb{Z}/p\mathbb{Z})^{*}$, which has index at most $n$, we obtain the following as a corollary.

Corollary: Fix a positive integer $n > 2$. For any sufficiently large prime $p$, there exists a nontrivial solution to $x^n + y^n \equiv z^n \bmod p$.

## The McKay correspondence I

Today we’re going to relate the representation graphs introduced in this blog post to something I blogged about in the very first and second posts in this blog! The result will be a beautiful connection between the finite subgroups of $\text{SU}(2)$, the Platonic solids, and the ADE Dynkin diagrams. This connection has been written about in several other places on the internet, for example here, but I don’t know that any of those places have actually gone through the proof of the big theorem below, which I’d like to (as much for myself as for anyone else who is reading this).

Let $G$ be a finite subgroup of $\text{SL}_2(\mathbb{C})$. Since any inner product on $\mathbb{C}^2$ can be averaged to a $G$-invariant inner product, every finite subgroup of $\text{SL}_2(\mathbb{C})$ is conjugate to a finite subgroup of $\text{SU}(2)$, so we’ll suppose this without loss of generality. The two-dimensional representation $V$ of $G$ coming from this description is therefore faithful and self-dual. Consider the representation graph $\Gamma(V)$, whose vertices are the irreducible representations of $G$ and where the number of edges between $V_i$ and $V_j$ is the multiplicity of $V_j$ in $V_i \otimes V$. We will see that $\Gamma(V)$ is a connected undirected loopless graph whose spectral radius $\lambda(\Gamma(V))$ is $2$. Today our goal is to prove the following.

Theorem: The connected undirected loopless graphs of spectral radius $2$ are precisely the affine Dynkin diagrams $\tilde{A}_n, \tilde{D}_n, \tilde{E}_6, \tilde{E}_7, \tilde{E}_8$.

We’ll describe these graphs later; for now, just keep in mind that they are graphs with a number of vertices which is one greater than their subscript. In a later post we’ll see how these give us a classification of the Platonic solids, and we’ll also discuss other connections.

## Walks on graphs and tensor products

Recently I asked a question on MO about some computations I’d done with Catalan numbers awhile ago on this blog, and Scott Morrison gave a beautiful answer explaining them in terms of quantum groups. Now, I don’t exactly know how quantum groups work, but along the way he described a useful connection between walks on graphs and tensor products of representations which at least partially explains one of the results I’d been wondering about and also unites several other related computations that have been on my mind recently.

Let $G$ be a compact group and let $\text{Rep}(G)$ denote the category of finite-dimensional unitary representations of $G$. As in the finite case, due to the existence of Haar measure, $\text{Rep}(G)$ is semisimple (i.e. every unitary representation decomposes uniquely into a sum of irreducible representations), and via the diagonal action it comes equipped with a tensor product with the property that the character of the tensor product is the product of the characters of the factors.

Question: Fix a representation $V \in \text{Rep}(G)$. What is the multiplicity of the trivial representation in $V^{\otimes n}$?

## Newton’s sums, necklace congruences, and zeta functions

The goal of this post is to give a purely combinatorial proof of Newton’s sums which would have interrupted the flow of the previous post. Recall that, in the notation of the previous post, Newton’s sums (also known as the first Newton-Girard identity) state that

$\displaystyle p_k - e_1 p_{k-1} \pm ... = (-1)^{k+1} ke_k$.

One way to motivate a combinatorial proof is to recast the generating function interpretation appropriately. Given a polynomial $C(t)$ with non-negative integer coefficients and $C(0) = 0$, let $r_1, ... r_n$ be the reciprocals of the roots of $C(t) - 1 = 0$. Then

$\displaystyle \frac{t C'(t)}{1 - C(t)} = \sum_{k \ge 1} p_k(r_1, ... r_n) t^k$.

The left hand side of this identity suggests a particular interpretation in terms of the combinatorial species described by $C(t)$. Today we’ll describe this species when $C(t)$ is a polynomial with non-negative integer coefficients and then describe it in the general case, which will handle the extension to the symmetric function case as well.

The method of proof used here is closely related to a post I made previously about the properties of the Frobenius map, and at the end of the post I’ll try to discuss what I think might be going on.

## The magic of the Frobenius map II

Once upon a time I discussed some interesting uses of the Frobenius map to solve some Putnam-style problems. Unfortunately, I wrote that post before becoming really interested in combinatorics, so I neglected to develop that particular side of the story, which I’d like to do now.

The beginning of this story is the folklore combinatorial proof of Fermat’s little theorem: for any positive integer $a$ and prime $p$, we have

$a^p \equiv a \bmod p$.

The proof is simple but powerful. Consider the set of possible ways to color $p$ beads with $a$ colors. The cyclic group $\mathbb{Z}/p\mathbb{Z}$ acts on this set in the obvious way. (One says that the beads are “on a necklace.”) The great thing about actions of a prime cyclic group is that elements arrange themselves into two kinds of orbits: fixed points and orbits of size $p$. (This is just a special case of the orbit-stabilizer theorem.) The total number of colorings is $a^p$, but if we only want to work $\bmod p$ it suffices to count the number of fixed points under the action of $\mathbb{Z}/p\mathbb{Z}$. These are precisely the colorings using only one color, of which there are $a$, and the result follows.

The standard generalization of this result to finite fields is as follows: $\text{Gal}(\mathbb{F}_{p^n}/\mathbb{F}_p) \simeq \mathbb{Z}/n\mathbb{Z}$ and is generated by the Frobenius map $x \mapsto x^p$. Does this result also have a combinatorial proof?

## The Catalan numbers, regular languages, and orthogonal polynomials

I’ve been inspired by The Unapologetic Mathematician (and his pages and pages of archives!) to post more often, at least for the remainder of the summer. So here is a circle of ideas I’ve been playing with for some time.

Let $C(x) = \sum_{n \ge 0} C_n x^n$ be the ordinary generating function for the ordered rooted trees on $n+1$ vertices (essentially we ignore the root as a vertex). This is one of the familiar definitions of the Catalan numbers. From a species perspective, ordered rooted trees are defined by the functional equation

$\displaystyle C(x) = \frac{1}{1 - xC(x)}$.

The generating function $\frac{1}{1 - x} = 1 + x^2 + ...$ describes the species $\textsc{Seq}$ of sequences. So what this definition means is that, after tossing out the root, an ordered rooted tree is equivalent to a sequence of ordered rooted trees (counting their roots) in the obvious way; the roots of these trees are precisely the neighbors of the original root. Multiplying out gets us a quadratic equation we can use to find the usual closed form of $C(x)$, but we can instead recursively apply the above to obtain the beautiful continued fraction

$\displaystyle C(x) = \frac{1}{1 - \frac{x}{1 - \frac{x}{1 - ...}}}$.

Today’s discussion will center around this identity and some of its consequences.