Feeds:
Posts

## Set-multiset duality and supervector spaces

Recall that the elementary symmetric functions $e_{\lambda}$ generate the ring of symmetric functions $\Lambda$ as a module over any commutative ring $R$. A corollary of this result, although I didn’t state it explicitly, is that the elementary symmetric functions $e_1, e_2, ...$ are algebraically independent, hence any ring homomorphism from the symmetric functions is determined freely by the images of $e_1, e_2, ...$.

A particularly interesting choice of endomorphism $\omega : \Lambda \to \Lambda$ occurs when we set $\omega(e_n) = h_n$. This endomorphism sends the generating function $E(t)$ for the elementary symmetric polynomials to the generating function $H(t) = \frac{1}{E(-t)}$, and this is an involution – in other words, it follows that $\omega(h_n) = e_n$ and $\omega$ itself must also be an involution on the ring of symmetric functions. Thus the elementary symmetric functions and complete homogeneous symmetric functions are dual in a very strong sense. This is closely related to the identity

$\displaystyle \left( {n \choose d} \right) = (-1)^d {-n \choose d}$

and today I’d like to try to explain one interpretation of what’s going on that I learned from Todd Trimble, which is that “the exterior algebra is the symmetric algebra of a purely odd supervector space.”

Naive definitions

The multisets of a set with $n$ elements form a monoid under union, so we can take their monoid algebra, which is a generalization of the notion of group algebra. The homogeneous elements of degree $d$ are given by the set of linear combinations of multisets of size $d$, and this gives the familiar construction of the symmetric algebra

$\displaystyle S(V) = \bigoplus_{d=0}^{\infty} S^d(V)$

where $V$ is the free vector space on a set with $n$ elements (and $S(V)$ is the free commutative algebra on $V$). The Hilbert series of this algebra is $\displaystyle \frac{1}{(1 - t)^n}$; in particular, the number of elements of degree $d$ is $\displaystyle \left( {n \choose d} \right) = \frac{n(n+1)...(n+d-1)}{d!}$. So the symmetric algebra is a good linearization of the notion of multiset. One can think of it as the ring of polynomials $\mathbb{C}[x_1, ... x_n]$, which is a familiar object.

On the other hand, if we try to linearize subsets in the same way we run into the problem of how to describe the product structure. The solution is to take a leaf out of the book of physics, namely the Pauli exclusion principle, to obtain a physically significant possibility: the product of two subsets with an element in common should be empty. In other words, the product should satisfy

$\mathbf{v} \vee \mathbf{v} = 0$

for all $\mathbf{v}$. But it’s not hard to see that this implies that

$(\mathbf{v} + \mathbf{w}) \vee (\mathbf{v} + \mathbf{w}) = \mathbf{v} \vee \mathbf{w} + \mathbf{w} \vee \mathbf{v}$.

In other words, the multiplication must be antisymmetric. This multiplication defines the exterior algebra on $V$,

$\displaystyle E(V) = \bigoplus_{d=0}^{\infty} E^d(V)$.

The Hilbert series of this algebra is $(1 + t)^n$; in particular, the number of elements of rank $d$ is $\displaystyle {n \choose d} = \frac{n(n-1)...(n-d+1)}{d!}$. One way, therefore, to interpret the identity

$\displaystyle \left( {n \choose d} \right) = (-1)^d {-n \choose d}$

is that the symmetric algebra on a vector space of dimension $n$ should behave something like the exterior algebra on a vector space of dimension $-n$, whatever that means. So what could that possibly mean?

Negative dimension

What we’re going to do is just start with a normal vector space $V_0$ which is “positive” and throw in a second vector space $V_1$ which is “negative.” This might be a sensible thing to do if, for example, you were interested in talking about a collection of positively and negatively charged particles. The supervector space we are looking at then is just the direct sum $V_0 \oplus V_1$ regarded as a $\mathbb{Z}/2\mathbb{Z}$-graded vector space; we’ll refer to the first component interchangeably as the even or positive part and the second component as the odd or negative part, and we’ll say it has dimension $(m, n)$ if $\dim V_0 = m, \dim V_1 = n$, although what we’re really interested in is $m - n$, which we’ll call the Euler characteristic and denote by $\chi(V)$.

Example. Let $V_0 \to V_1 \to ... \to V_k$ be a sequence of vector spaces and linear maps, and define the supervector space whose even part is all the even-numbered spaces and whose odd part is all the odd-numbered spaces. If the sequence is exact (with the zero vector spaces at the beginning and the end) then the Euler characteristic vanishes. This is the simplest manifestation of a deep relationship with homology theory; see the enlightening answers to another one of my MathOverflow questions here.

One way to think of how the category $\text{S-Vect}$ of supervector spaces should behave is to start with the category $\text{Rep}(\mathbb{Z}/2\mathbb{Z})$, since every representation decomposes into copies of the trivial representation (the even part) and the sign representation (the odd part). The intertwining operators here are the grade-preserving ones, i.e. the ones that send positive elements to positive elements and negative elements to negative elements; these are the morphisms in $\text{S-Vect}$. (The Euler characteristic is then the trace of the non-identity element of $\mathbb{Z}/2\mathbb{Z}$.)

Next we should introduce a tensor product structure. Going off of how we want the $\mathbb{Z}/2\mathbb{Z}$-action to behave on each component of the tensor product, the even part of the tensor product $(A_0 \oplus A_1) \otimes (B_0 \oplus B_1)$ should be

$A_1 \otimes B_0 \oplus A_1 \otimes B_1$

and the odd part should be

$A_1 \otimes B_0 \oplus A_0 \otimes B_1$.

With this definition, Euler characteristics are multiplicative, so we have categorified the identity $(a - b)(c - d) = (ac + bd) - (bc + ad)$. Note that this is the same tensor product identity as the one we used to discuss the orthogonality relations. The unit of this tensor product is the base field $K^{1|0}$ regarded as a purely even space, so that $K \otimes A \simeq A \otimes K \simeq A$, and one can check that all the obvious laws hold.

Supercommutativity

The next structure we’d like is a way to identify the tensor products $A \otimes B$ and $B \otimes A$, i.e. a braiding. Unlike in the case for $\text{Vect}$, where the only sensible identification sends $a \otimes b$ to $b \otimes a$ on pure tensors, there are two braidings. Let’s suppose for now that any sensible braiding will still have the form

$a \otimes b \mapsto \omega(a, b) b \otimes a$

for some scalar $\omega(a, b)$ on pure homogeneous tensors. By bilinearity it really suffices to define how to switch two even elements, an even and an odd element, and two odd elements, since nice braidings satisfy $\omega(a, b) \omega(b, a) = 1$. Now, compatibility with units (which are even) implies that

$b \simeq 1 \otimes b \mapsto \omega(1, b) b \otimes 1 \simeq \omega(1, b) b$

so it follows that $\omega(1, b) = \omega(a, 1) = 1$; in other words, even elements don’t introduce any sign changes. By the above considerations it follows that $\omega(a, b) = \omega(b, a)$, hence for odd elements we have $\omega(a, b)^2 = 1$. The only way to avoid the boring braiding is to require that $\omega(a, b) = -1$ for odd elements, which is often written

$a \otimes b \mapsto (-1)^{|a| |b|} b \otimes a$

where $|a|, |b|$ are the parities of $a, b$ (as elements of $\{ 0, 1 \}$). One can check that all the associativity axioms hold, so this braiding turns $\text{S-Vect}$ into a symmetric monoidal category, and now we can define the supersymmetric powers $S^n(V)$ of a supervector space $V = V_0 \oplus V_1$ as the quotient of the tensor power by the above relation. Even better, we can now define the supercommutative algebra

$\displaystyle S(V_0 \oplus V_1) = \bigoplus_{n=0}^{\infty} S^n(V_0 \oplus V_1)$.

Supercommutativity appears naturally in several settings: in the exterior algebra (which we already knew about), in the cup product in a cohomology ring, and in Clifford algebras, so there is plenty of evidence that this isn’t an ad hoc definition; see also the great answers when I asked why this definition was meaningful at MathOverflow.

Edit, 11/8/09: For a more concise and general way to describe $\text{S-Vect}$, see also the answers to the MathOverflow question here.

And now something remarkable happens.

Proposition: $\displaystyle \chi(S^d(V)) = \left( { \chi(V) \choose d} \right)$.

If $V = V_0$ is purely even of dimension $n$, then supercommutativity is commutativity and $S^d(V)$ is a purely even copy of the usual symmetric power. If $V = V_1$ is purely odd of dimension $n$, then supercommutativity is anticommutativity and $S^d(V)$ is a purely $(-1)^d$-signed copy of the usual exterior power. This is the categorification of the set-multiset identity I wrote earlier, which we now know should really be written $\left( {-n \choose d} \right) = (-1)^d {n \choose d}$. So not only do we know how to interpret this result, but it has a great generalization, which we just have to prove.

Proof. In the general case $V = V_0 \oplus V_1$ where $\dim V_0 = m, \dim V_1 = n$, any product of pure tensors can be rewritten, using supercommutativity, as the product of elements of $V_0$ followed by elements of $V_1$, which gives a direct sum decomposition

$\displaystyle S^d(V) = \bigoplus_{i=0}^{d} S^i(V_0) \otimes E^{d-i}(V_1)$

where $S^i(V_0) \otimes E^{d-i}(V_1)$ has Euler characteristic $(-1)^{d-i} \left( {m \choose i} \right) {n \choose d-i}$ since the odd parts anticommute and the even parts commute. It remains to show that

$\displaystyle \left( {m-n \choose d} \right) = \sum_{i=0}^{d} (-1)^{d-i} \left( {m \choose i} \right) {n \choose d-i}$.

The combinatorial proof for $m \ge n$ is as follows: we have a set of $m$ elements, of which $n$ are “bad” and the others are “good.” We want to compute the number of multisets with $d$ elements, all of which are good, and we proceed by inclusion-exclusion. We start with the multisets of $d$ arbitrary elements, then remove the multisets with at least one bad element, then add back the multisets with at least two distinct bad elements, and so forth. The proof for $m < n$ is identical except that we count subsets.

This proof should have a linearization in which we define morphisms making

$S^d(V_0) \to S^{d-1}(V_0) \otimes E^1(V_1) \to ... \to E^d(V_1)$

an exact sequence (except at the ends), but I can’t figure out what the morphisms should be.

Characters

The upshot of all of this is that we can think of the symmetric and exterior algebras on an equal footing. There is a natural way to switch between the two since in $\text{S-Vect}$ the functor $\textbf{Hom}(K^{0|1}, -)$, where $K^{0|1}$ is the base field regarded as a purely odd vector space, interchanges the even and odd parts. In physics this is the relationship between the Fock spaces of fermions and bosons. As usual John Baez has lots to say on this subject, except that I can’t find the TWF I’m thinking of.

This is the same relationship as the one between the elementary symmetric functions and complete homogeneous symmetric functions. To see this, note that the symmetric and antisymmetric algebra constructions are functorial, so they send automorphisms $V \to V$ to automorphisms $S^d(V) \to S^d(V)$ and $E^d(V) \to E^d(V)$. It turns out that these are actually irreducible representations of $GL(V)$ and the traces of an element $G \in GL(V)$ on these representations are the complete homogeneous symmetric functions and the elementary symmetric functions of the eigenvalues of $G$, respectively.

Here’s a riddle for next time: the symmetric group $S_d$ acts on $S^d(V)$ and $E^d(V)$ by swapping factors, the first by the trivial representation and the second by the sign representation. These representations have characters the trivial and sign characters, and we showed way before that

$\displaystyle h_n = \frac{1}{n!} \sum_{\pi \in S_n} p_{\pi}$

and

$\displaystyle e_n = \frac{1}{n!} \sum_{\pi \in S_n} \text{sgn}(\pi) p_{\pi}$.

In other words, the trace of the symmetric algebra has something to do with the trivial representation, and the trace of the exterior algebra has something to do with the sign representation. What does this mean?

### 4 Responses

1. on November 8, 2009 at 5:56 pm | Reply Gonçalo Marques

Great series of posts! I’m still absorbing most of it. I do have a question. You say
“if we try to linearize subsets in the same way we run into the problem of how to describe the product”
Why is that? Subsets also form a monoid under union, so we could also take the monoid ring. Or am I missing something?

• Sure, but the problem with this product structure is that the corresponding monoid ring isn’t graded by the number of elements in the subset, since subsets can have nontrivial intersection. We want the gradation so that the Hilbert series is what it “should be.” (The underlying idea, which I didn’t state explicitly, is that certain sufficiently nice generating functions should be Hilbert series of various algebras.)

2. “This proof should have a linearization in which we define morphisms making

$S^d(V_0) \to S^{d-1}(V_0) \otimes E^1(V_1) \to \cdots \to E^d(V_1)$

an exact sequence (except at the ends), but I can’t figure out what the morphisms should be. ”

This is a special case of what’s called a “Schur complex.” There’s one for every partition. The data needed to create a Schur complex is a matrix $A \colon V_1 \to V_0$. If the matrix is sufficiently generic and the partition is rectangular, then the complex will be exact. In this case, this is the Schur complex associated to a horizontal strip (or vertical strip depending on your conventions). I learned about these in Jerzy Weyman’s book Cohomology of Vector Bundles and Syzygies (Section 2.4). That section of the book only requires knowledge of super linear algebra. If you have trouble finding the book, let me know. Otherwise, another reference is the paper Schur functors and Schur complexes by Akin, Buchsbaum, and Weyman. I’ve never looked at this paper though.

3. on November 6, 2009 at 8:44 pm | Reply phorgyphynance

By the way, I was having fun with multisets recently. There is another obvious way they form a rig. I wrote some notes on the nLab:

http://nlab.mathforge.org/nlab/show/multiset

An old fashioned set $X$ in the free rig of multisets is idempotent.