Categorification, step 1

Today at the St Petersburg meeting, Igor Frenkel talked about categorification. He explained that there are five levels (maybe more!) and one has to take certain steps between them; he illustrated with an example, where level 0 was Jacobi’s Triple Product Identity and level 5 was four-dimensional quantum Yang–Mills.

He did say,

Forget about categorification if you don’t want to hear this word,

and it is certainly not an attractive word.

But I, like a stubborn mule, found myself unable to cross the Pons Asinorum from Level 0 to Level 1, since the landscape along the way was too attractive. I have some questions about this, which I will describe briefly here. I may try to write this out at greater length sometime.

Numbers and vector spaces

Step 1, in essence, consists in replacing numbers (non-negative integers) with vector spaces over a field, which is usually taken to be the field of complex numbers (but undoubtedly different things will happen over other fields). The number n is replaced by an n-dimensional vector space over C.

Addition and multiplication of numbers is replaced by direct sum and tensor product of vector space; the dimensions do indeed behave correctly.

An equation like ab+c = 0 is replaced by a short exact sequence

{0} → A → B → C → {0};

this means that the image of each map is equal to the kernel of the next. Again the dimensions behave correctly. But we see already that the process is not purely mechanical, since the reverse of the short exact sequence (which could be realised by maps of the dual spaces) may not be the thing that naturally occurs.

For example, Euler’s polyhedral formula (written in the form 1−V+EF+1 = 0) can be realised in this way: first orient the edges and faces of the polyhedron; now replace V,E,F by vector spaces of functions from vertices, edges and faces to C; and then use “coboundary maps” to make the sequence. (For example, from V to E, we replace a function f on vertices by a function df on edges, where df(v,w) = f(w)−f(v).) Now the proof of Euler’s formula becomes the proof of exactness of this sequence.

Formal power series

A formal power series ∑anxn has to be treated a bit differently. We cannot substitute a natural number for x, since all but the tamest such sequences have radius of convergence smaller than 1. But, as in combinatorial enumeration, we regard the powers of x as markers.

Thus, the interpretation of the series is a graded vector space ⊕An, where An is a vector space of dimension an.

Now direct sum or tensor product of graded vector spaces (with the usual conventions about grading, that is, the product of elements of degrees k and l has degree k+l), correspond to the sum or product of the formal power series.

Problem What if the graded vector space is actually a graded algebra?

In particular, the formal power series 1 and x corresponds to 1-dimensional vector spaces with degree 0 and 1 respectively.


Let G be a finite permutation group on the set {1,…,n}. Then G has a natural action on a vector space V of dimension n, by permuting the vectors of a basis. An invariant of G is simply a vector fixed by G; such a vector must have coordinates which are constant on each G-orbit, and so the space of invariants of G (written VG) has dimension equal to the number of orbits of G. So we have taken the first step towards categorifying orbit-counting.

More generally, let W be a graded vector space. Then there is a natural action of G on the direct sum V = Wn of n copies of G. How do we “count” invariants here?

The answer lies in Pólya theory. Associated with G is a multivariate polynomial called the cycle index of G. This is the polynomial in indeterminates s1,…sn constructed as follows: for each element g of the group, having ci cycles of length i for each i, we form a monomial by raising si to the power ci, multiplying all these together; then sum these monomials over all group elements, and divide by the order of the group. This is denoted by Z(G).

Suppose that we have a collection of “figures”, each with a non-negative integer “weight”, so that there are only finitely many (say ai) figures of weight i for each i. The figures can be represented by a figure-counting series A(x) = ∑aixi. Now a “function” is a map from the set {1,…n} to the set of figures (essentially it puts a figure at every point of this set). G permutes the functions by moving their arguments. We are interested in counting the orbits of G on functions of given total weight (the sum of the weights of their values). If bi is the number of orbits, then the function-counting series is B(x) = ∑bixi.

Now Pólya’s Theorem asserts that B(x) is obtained from Z(G) by substituting A(xi) for si, for each i.

Now (I think), if we replace the figure-counting series by a graded vector space W, and let G act on the direct sum V of n copies of V, then the function-counting series corresponds to the space of invariants of G in V.

Of course, permutation actions are a special case of linear actions.

Problem. What happens for linear actions? Do we replace Pólya’s theorem by Molien’s?

Oligomorphic groups

A permutation group G on an infinite set is called oligomorphic if it has only finitely many (say an) orbits on the set of all n-element subsets of the permutation domain.

The definition of cycle index breaks down completely for oligomorphic permutation groups. However, one can define a modified cycle index for an oligomorphic group; this is obtained by taking orbit representatives for the orbits of G on the finite subsets of its domain, for each orbit representative take the cycle index of the finite group induced on this set by its setwise stabiliser in G, and then summing. It is easy to see that we obtain a formal power series in the infinitely many indeterminates s1,s2,….

A finite permutation group is a special case of an oligomorphic group; according to the Shift Theorem, its modified cycle index can be obtained from its ordinary cycle index by replacing si by si+1, for each i.

Many substitution results hold. For example, the power series ∑anxn is obtained from the modified cycle index by substituting xi for si, for each i. There are also rules for direct and wreath products.

There is at least the possibility of turning all this into graded vector spaces. Let Vi be the vector space of all functions from the set of G-orbits on i-sets to C, and V the graded vector space having these spaces as their homogeneous components. Then the vector space V “represents” the orbit-counting power series.

The vector space V has a natural algebra structure, which I won’t describe here. In fact, though results about the rate of growth of the numbers an tend to be proved by combinatorial methods (chiefly by Dugald Macpherson), I have had a small amount of success in proving smoothness results using algebraic methods, based on the fact that the multiplication in the algebra gives a map from VmVn to Vm+n.

Problem What are the vector space operations corresponding to direct and wreath product of oligomorphic groups?

Problem Is there a linear group analogue of oligomorphic permutation groups, for which a similar theory can be developed?

I think that is enough problems to be going on with!

About Peter Cameron

I count all the things that need to be counted.
This entry was posted in exposition, open problems and tagged , , , , , . Bookmark the permalink.

2 Responses to Categorification, step 1

  1. Jon Awbrey says:

    Some asses are golden, as Apuleius has told us.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.