There is a long and terrific story to tell about Lie theory, and I wish I could do it justice, but there’s far too much to say in a single post. What I have today is merely one application of one Lie algebraic idea, which ends up being a useful theoretical and practical tool in enumerative combinatorics.

The long and short of it is that the representation theory of a spooky object called $\def\sl{\mathfrak{sl}}\sl(2)$ can be hijacked by combinatorialists to prove that certain sequences of positive integers are symmetric and unimodal. Typically symmetry is obvious but unimodality is quite hard to establish, so this $\sl(2)$ technology does make things somewhat neater. The other big tool I know about for proving things about unimodality or related properties like log-concavity is the theory of stable polynomials, which is also rather algebraic.

Lie algebras

Fix the field $\def\C{\mathbb C}\C$. Some of the following math can be done over other fields and even over general rings, but $\C$ is good enough for the combinatorialist and hence for this post. Formally, a Lie algebra is a vector space $\def\g{\mathfrak g}\g$ together with a special bilinear map $[{-},{-}] : \g \times \g \to \g$ called the Lie bracket. The Lie bracket must be antisymmetric, in that $[a,b] = -[b,a]$ for all $a,b \in \g$, and it must also satisfy the Jacobi identity,

$$[a,[b,c]] + [b,[c,a]] + [c,[a,b]] = 0,$$

for all $a,b,c \in \g$.

Lie algebras arise in a natural way from fantastic objects called Lie groups, which are essentially groups with smooth manifold structure. There is an enormous amount of theory on this topic, of which I will be needing rather little, and most of what I will talk about today can be done without invoking any of the deep Lie theory underlying everything, but I thought I would record at least a taste of what lies beneath.

Any associative $\C$-algebra $A$ gives rise to a Lie algebra on $A$, by taking the Lie bracket to be the commutator $[a,b] = ab - ba$. In particular, the matrix algebra $\mathrm{End}(V)$ of endomorphisms of a finite-dimensional vector space gives a Lie algebra denoted $\def\gl{\mathfrak{gl}}\gl(V)$. When the particular vector space is irrelevant we often abbeviate $\gl(n) = \gl(\C^n)$.

The Lie algebra $\sl(2)$ is a sub–Lie algebra of $\gl(2)$, consisting of those matrices with zero trace. The trace functional is not multiplicative, so $\sl(2)$ is not a subalgebra of $\mathrm{End}(\C^2)$, but it is true that $\def\tr{\operatorname{tr}}\tr(AB) = \tr(BA)$, so that $\tr([A,B]) = \tr(AB) - \tr(BA) = 0$ and then $\sl(2)$ is closed under the Lie bracket.

To better discuss $\sl(2)$, let

$$X = \begin{bmatrix} 0&1\\0&0 \end{bmatrix}, \quad Y = \begin{bmatrix} 0&0\\1&0 \end{bmatrix}, \quad H = \begin{bmatrix} 1 & 0 \\ 0 & -1 \end{bmatrix}.$$

$\{X,Y,H\}$ is a basis for $\sl(2)$, and we can compute that $[X,Y] = H$, $[H,X] = 2X$, and $[H,Y] = -2Y$. In fact, $\{X,Y\}$ together generate $\sl(2)$ as a Lie algebra, in that the only subset of $\sl(2)$ closed under finite linear combinations and brackets, and containing $X$ and $Y$, is all of $\sl(2)$.

Representation theory

A representation of a Lie algebra $\g$ is a linear map $\pi : \g \to \gl(V)$ for some vector space $V$, such that $\pi([x,y]_\g) = [\pi(x),\pi(y)]_{\gl(V)}$. One famous representation of any Lie algebra is the adjoint representation $\mathrm{ad} : \g \to \gl(\g)$ where $\mathrm{ad}(x) = [x,{-}]$. We’re going to investigate the representation theory of $\sl(2)$¹ and an arguably combinatorially useful property will fall out.

Let $\pi : \g \to \gl(V)$ be a representation. A subspace $W \subseteq V$ is $\pi$-invariant if it is $\pi(x)$-invariant for all $x \in \g$, that is, if $\pi(x)W \subseteq W$. $\pi$ is irreducible if the only nontrivial invariant subspace is $V$.

One would hope, as in the representation theory of finite groups, that every complex finite-dimensional representation of a Lie algebra $\g$ is a direct sum of irreducibles. This doesn’t work out unless $\g$ is semisimple. The definition is a bit involved and doesn’t motivate itself, but it’s not wrong to say that $\g$ is semisimple iff it is a direct sum of simple Lie algebras, which are those where the only nontrivial subspace $\mathfrak i$ such that $[\g,\mathfrak i] = \mathfrak i$ is $\g$ itself. Point is, $\sl(2)$ is semisimple.

One common abuse of notation is to make $\pi : \g \to \gl(V)$ implicit by declaring that $V$ is a representation of $\g$ and that $xv = \pi(x)v$ for $x \in \g$ and $v \in V$. Never having been one to rock the boat, I’ll do the same when discussing representations of $\sl(2)$.

Because $\{X,Y\}$ generate $\sl(2)$, representations of $\sl(2)$ are determined by the images of $X$ and $Y$. The coherence conditions they have to satisfy are $[H,X] = 2X$ and $[H,Y] = -2Y$, where of course $H = [X,Y]$. By the bilinearity and antisymmetry of the bracket, any pair of maps $(X,Y)$ satisfying these (two) equations forms a representation of $\sl(2)$.

If we take for granted that every representation of $\sl(2)$ decomposes a direct sum of irreducible representations, often abbreviated irreps, then it suffices to understand the irreps. Once we have that knowledge I can explain what it’s good for and how a combinatorialist might use it. (At this point you can skip to the next section if you believe me and don’t care why.)

So let $V$ be a finite-dimensional irrep of $\sl(2)$. By semisimplicity, we can use a principle called the preservation of Jordan decomposition². This tells us that $H$ acts diagonalizably on $V$, since it itself is diagonal in $\sl(2)$, and likewise $X$ and $Y$ act nilpotently. Because $H$ is diagonalizable, let’s decompose $V = \bigoplus_\lambda V_\lambda$ into $\lambda$-eigenspaces $V_\lambda$ for $H$. The eigenvalues $\lambda$ that have nontrivial $V_\lambda$ are called weights and the $V_\lambda$ are called weight spaces.

If $v \in V_\lambda$, then

$$HXv = (XH + [H,X])v = X(\lambda v) + (2X)v = (\lambda + 2)Xv$$

so $X(V_\lambda) \subseteq V_{\lambda+2}$, and likewise $Y(V_\lambda) \subseteq V_{\lambda-2}$. For this reason $X$ and $Y$ are often called raising and lowering operators, respectively.

If some $\alpha \in \C$ has a nontrivial $V_\alpha$, then $\bigoplus_{n \in \mathbb Z} V_{\alpha+2n}$ is an invariant subrepresentation of $V$, and hence equals $V$ by irreducibility. So by finite dimensionality, these eigenvalues show up in an unbroken line as in $\alpha, \alpha+2, \alpha+4, \dots, \alpha+2k$.

Let $v \in V_\alpha$ be a vector of lowest weight. Then consider the cyclic subspace $\{v, Xv, X^2v, ...\}$. Obviously, $Yv = 0$ by lowest weight. By induction we can show $YX^nv = n(\alpha+n-1)X^{n-1}v$, for

$$\begin{align*} YX^{n+1}v &= XYX^nv + HX^nv \\ &= X\bigl( n(\alpha+n-1) X^{n-1}v \bigr) + (\alpha+2n)X^nv \\ &= \bigl( n\alpha + n(n-1) + \alpha+2n \bigr)X^nv \\ &= \bigl( (n+1)\alpha + n(n+1) \bigr) X^nv \\ &= \bigl( (n+1)(\alpha + (n+1)-1) \bigr) X^nv. \end{align*}$$

It follows that this cyclic subspace is a subrepresentation, and by irreducibility, $V$ is equal to this subrepresentation. But now, because $V$ is finite-dimensional, we can do some numerological magic. $X^nv = 0$ for some least $n = \dim V$, and then $0 = YX^nv = n(\alpha+n-1)X^{n-1}v$.

Well, $X^{n-1}v$ is a nonzero vector, so the coefficient $n(\alpha+n-1)$ must be zero. If $V$ is nontrivial, then $\alpha + n-1 = 0$ and hence $\alpha$ is a strictly negative integer!

Finally, recall that $X(V_\lambda) \subseteq V_{\lambda+2}$, so that the weight spaces of $V$ have dimensions $1, 0, 1, 0, \dots$, starting at $\alpha$. Also, since $k = n-1 = -\alpha$ gives the last nonzero vector, the highest nontrivial weight space is $\alpha+2k = -\alpha = |\alpha|$.

Now we know all that we need to about irreps of $\sl(2)$.

Symmetry and unimodality

Taking stock of what just happened, we see that there is one irrep of any particular dimension, and its weight spaces have dimensions $1, 0, 1, 0, \dots, 0, 1$, symmetrically arranged around the 0-eigenspace. It follows that any finite-dimensional representation is isomorphic to a direct sum of these. That is to say, if $V = \bigoplus_i V_i$ is a representation of $\sl(2)$, graded by its weight spaces, and $d_i = \dim V_i$ is the dimension of the $i$-th weight space, then the following is true:

$$\cdots \le d_{-4} \le d_{-2} \le d_0 \ge d_2 \ge d_4 \ge \cdots$$ $$\cdots \le d_{-3} \le d_{-1} = d_1 \ge d_3 \ge \cdots$$

These two sequences, $(\dots, d_{-4}, d_{-2}, d_0, d_2, d_4, \dots)$ and $(\dots, d_{-3}, d_{-1}, d_1, d_3, \dots)$, have two properties that are referred to as symmetry—that they can be reflected about their center and remain equal—and unimodality—that they rise monotonically to some peak, and subsequently fall monotonically.

Because of this, if you would like to prove that some sequence of positive integers is symmetric and unimodal, it would suffice to find a representation of $\sl(2)$ with suitable weight spaces. The encoding for a sequence $(d_i)_{i=0}^n$ is usually to have $d_i$ be the dimension of the $(2i-n)$-th weight space.³ To show you some interesting examples, I’ll use a couple of bits of technology, but in principle I could give the coefficients explicitly and that would suffice.

Given any finite set $S$, there is a natural representation of $\sl(2)$, called the Boolean representation, on the free vector space $\C\mathcal P(S)$ whose basis is indexed by subsets of $S$. Denote the basis vector of $A \subseteq S$ by $\tilde A$. Then the representation of $\sl(2)$ is given by

$$X\tilde A = \sum_{a \notin A} (A \cup \{a\})^\sim \quad \text{and} \quad Y\tilde A = \sum_{a \in A} (A \smallsetminus \{a\})^\sim.$$

Let $V$ be a representation of $\sl(2)$ and suppose it has an action by some group $G \le \mathrm{GL}(V)$ as well. If the $\sl(2)$-rep is equivariant with respect to the $G$-action, in that $gx = xg$ for all $x \in \sl(2)$ and $g \in G$, then there exists a subrepresentation on the $G$-invariant vectors, i.e. on the vector space

$$V^G = \{ v \in V : g.v = v\ \text{for all}\ g \in G \}.$$

To wit, if $\{v_1, \dots, v_n\}$ is some orbit of $G$, then $\sum_i v_i \in V^G$, so in some sense $V^G$ is the space of orbits of $G$.

Now, we can see a couple of examples.

First, let $g_n(k)$ the number of isomorphism classes of $n$-vertex $k$-edge graphs. Clearly the sequence $g_n = ( g_n(k) : 0 \le k \le \binom{n}{2} )$ is symmetric, via complementation, but unimodality is far far harder to show combinatorially. Instead, we’ll use $\sl(2)$!

Let $E = \binom{[n]}2$ be the edge set of the complete graph $K_n$. The symmetric group $S_n$ has a natural action on $E$, by permuting the vertices of $K_n$ and bringing the edges along. This induces an action on $2^E$, which can be interpreted as the set of all graphs on the vertex set $[n] = \{1,\dots,n\}$. Notably, two graphs are in the same orbit iff they are isomorphic. It follows that the dimensions of the weight spaces of $\C\mathcal P(E)^{S_n}$ are precisely the $g_n(k)$’s above, so by the invariant subrepresentation of the Boolean representation of $\sl(2)$ on $E$, $g_n$ is symmetric and unimodal.

As a second example, let $p_{a,b}(k)$ be the number of integer partitions of $k$ with at most $a$ parts, each of which has size at most $b$. It’s a classical result of q-combinatorics that this is the coefficient of $q^k$ in the Gaussian polynomial

$$\def\qbinom{\genfrac{[}{]}{0pt}{}} \qbinom{a+b}{a}_q = \prod_{i=1}^a \frac{1-q^{b+i}}{1-q^i}.$$

Let $V$ be the Boolean representation of $[a] \times [b]$, and let $G = S_b \wr S_a$ be the wreath product of two symmetric groups. If you don’t know what this group is, then know that its action on $\mathcal P([a] \times [b])$ is exactly to permute the cells within each row, and then also to permute the rows afterwards. (If you’re reading the Wikipedia article, then this is an action induced by the imprimitive action.)

Given a proper definition, it is not hard to show each orbit of $G$ on $\mathcal P([a] \times [b])$ contains the Ferrers diagram of exactly one partition, and hence $G$ acts on $V$ such that $V^G$ is a vector space with basis indexed by these $a \times b$-bounded partitions. The partitions of $n$ all fall into the weight space with eigenvalue $2n - ab$, so the sequence $p_{a,b} = ( p_{a,b}(k) : 0 \le k \le ab )$ is symmetric and unimodal. This is but one of many proofs of the celebrated unimodality of the coefficients of $\qbinom{n}{k}_q$.

It is not very hard to give explicit coefficients for this particular representation, actually. Writing partitions as their multiplicity vectors $(m_0, \dots, m_b)$, it turns out that

$$\begin{align*} X\cdot(m_0, ..., m_b) &= \sum_{i=0}^b (b-i)m_i \cdot(\dots, m_i-1, m_{i+1}+1, \dots), \\ Y\cdot(m_0, ..., m_b) &= \sum_{j=0}^b jm_j \cdot(\dots, m_{j-1}+1, m_j-1, \dots). \end{align*}$$

At first glance it may appear that the above is not well-defined, but only valid partitions will show up in summands with nonzero coefficients, so all is well.

Let’s talk about posets now

Because posets and lattices are my favourite thing on this blog, I would be remiss if I were not to mention a very obvious connection to posets.

A poset $P$ is graded if it can be partitioned into disjoint ranks $P_i$, $i \in \{0, ..., r\}$, such that the only covering relations are between adjacent ranks $P_i$ and $P_{i+1}$. In such a situation, you could prove that $P$ is rank-symmetric and rank-unimodal by finding a representation of $\sl(2)$ on the free vector space $\tilde P$ whose weight spaces are the free subspaces $\tilde P_i$.

If you additionally require that the representation of $\sl(2)$ respect the poset structure—by saying that $X$ and $Y$ only raise or lower along covering relations, i.e. whenever $X\tilde a = \sum_i x_i \tilde b_i$ for nonzero $x_i$, then $a \le b_i$—then we say that $P$ carries that representation of $\sl(2)$. In this case, you prove not only that $P$ is rank-symmetric and unimodal, but has a third property: that any union of $k$ antichains is at most as large as the union of the $k$ largest ranks.

This is called the strong Sperner property, and those of you who have heard of Sperner theory are probably already groaning and closing your browser window, so I promise I won’t say much more about it. Essentially, this property is saying that there are no clever collections of large antichains, and if you want a bunch of them you might as well take from the ranks. In some sense it guarantees that your poset is not very lopsided.

A poset has the Peck property if it is rank-symmetric, rank-unimodal, and strongly Sperner. By a theorem of Proctor, a poset is Peck iff it carries a representation of $\sl(2)$.

The representations given as examples above are actually carried by posets. The first is carried by the poset of $n$-vertex isomorphism classes of graphs, ordered by the subgraph relation, and the second is carried by the lattice of bounded partitions, equivalently viewed as the lattice of order ideals in a product of two chains.