Connected objects and a reconstruction theorem

A common theme in mathematics is to replace the study of an object with the study of some category that can be built from that object. For example, we can

• replace the study of a group with the study of its category of linear representations,
• replace the study of a ring with the study of its category of -modules,
• replace the study of a topological space with the study of its category of sheaves,

and so forth. A general question to ask about this setup is whether or to what extent we can recover the original object from the category. For example, if is a finite group, then as a category, the only data that can be recovered from is the number of conjugacy classes of , which is not much information about . We get considerably more data if we also have the monoidal structure on , which gives us the character table of (but contains a little more data than that, e.g. in the associators), but this is still not a complete invariant of . It turns out that to recover we need the symmetric monoidal structure on ; this is a simple form of Tannaka reconstruction.

Today we will prove an even simpler reconstruction theorem.

Theorem: A group can be recovered from its category of -sets.

Read Full Post »

Four flavors of Schur-Weyl duality

If is a finite-dimensional complex vector space, then the symmetric group naturally acts on the tensor power by permuting the factors. This action of commutes with the action of , so all permutations are morphisms of -representations. This defines a morphism , and a natural question to ask is whether this map is surjective.

Part of Schur-Weyl duality asserts that the answer is yes. The double commutant theorem plays an important role in the proof and also highlights an important corollary, namely that admits a canonical decomposition

where runs over partitions, are some irreducible representations of , and are the Specht modules, which describe all irreducible representations of . This gives a fundamental relationship between the representation theories of the general linear and symmetric groups; in particular, the assignment can be upgraded to a functor called a Schur functor, generalizing the construction of the exterior and symmetric products.

The proof below is more or less from Etingof’s notes on representation theory (Section 4.18). We will prove four versions of Schur-Weyl duality involving , and (in the special case that is a complex inner product space) .

Read Full Post »

Epi-mono factorizations

In many familiar categories, a morphism admits a canonical factorization, which we will write

,

as the composite of some kind of epimorphism and some kind of monomorphism . Here we should think of as something like the image of . This is most familiar, for example, in the case of , and other algebraic categories, where is the set-theoretic image of in the usual sense.

Today we will discuss some general properties of factorizations of a morphism into an epimorphism followed by a monomorphism, or epi-mono factorizations. The failure of such factorizations to be unique turns out to be closely related to the failure of epimorphisms or monomorphisms to be regular.

Read Full Post »

The double commutant theorem

Let be an abelian group and be a collection of endomorphisms of . The commutant of is the set of all endomorphisms of commuting with every element of ; symbolically,

.

The commutant of is equal to the commutant of the subring of generated by the , so we may assume without loss of generality that is already such a subring. In that case, is just the ring of endomorphisms of as a left -module. The use of the term commutant instead can be thought of as emphasizing the role of and de-emphasizing the role of .

The assignment is a contravariant Galois connection on the lattice of subsets of , so the double commutant may be thought of as a closure operator. Today we will prove a basic but important theorem about this operator.

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 »

Short cycles in random permutations

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

Theorem: As , the number of cycles of length of a random permutation of elements are asymptotically independent Poisson with parameters .

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

Read Full Post »

Groupoid cardinality

Suitably nice groupoids have a numerical invariant attached to them called groupoid cardinality. Groupoid cardinality is closely related to Euler characteristic and can be thought of as providing a notion of integration on groupoids.

There are various situations in mathematics where computing the size of a set is difficult but where that set has a natural groupoid structure and computing its groupoid cardinality turns out to be easier and give a nicer answer. In such situations the groupoid cardinality is also known as “mass,” e.g. in the Smith-Minkowski-Siegel mass formula for lattices. There are related situations in mathematics where one needs to describe a reasonable probability distribution on some class of objects and groupoid cardinality turns out to give the correct such distribution, e.g. the Cohen-Lenstra heuristics for class groups. We will not discuss these situations, but they should be strong evidence that groupoid cardinality is a natural invariant to consider.

Read Full Post »

Fixed points of random permutations

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

1. The number of permutations on elements with no fixed points (derangements) is approximately .
2. The expected number of fixed points of a random permutation on elements is .

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 , the distribution of the number of fixed points of a random permutation on elements is asymptotically Poisson with rate .

Read Full Post »

String diagrams, duality, and trace

Previously we introduced string diagrams and saw that they were a convenient way to talk about tensor products, partial compositions of multilinear maps, and symmetries. But string diagrams really prove their use when augmented to talk about duality, which will be described topologically by bending input and output wires. In particular, we will be able to see topologically the sense in which the following four pieces of information are equivalent:

• A linear map ,
• A linear map ,
• A linear map ,
• A linear map .

Using string diagrams we will also give a diagrammatic definition of the trace of an endomorphism of a finite-dimensional vector space, as well as a diagrammatic proof of some of its basic properties.

Below all vector spaces are finite-dimensional and the composition convention from the previous post is still in effect.

Read Full Post »

Introduction to string diagrams

Today I would like to introduce a diagrammatic notation for dealing with tensor products and multilinear map. The basic idea for this notation appears to be due to Penrose. It has the advantage of both being widely applicable and easier and more intuitive to work with; roughly speaking, computations are performed by topological manipulations on diagrams, revealing the natural notation to use here is 2-dimensional (living in a plane) rather than 1-dimensional (living on a line).

For the sake of accessibility we will restrict our attention to vector spaces. There are category-theoretic things happening in this post but we will not point them out explicitly. We assume familiarity with the notion of tensor product of vector spaces but not much else.

Below the composition of a map with a map will be denoted (rather than the more typical ). This will make it easier to translate between diagrams and non-diagrams. All diagrams were drawn in Paper.

Read Full Post »