Set-multiset duality and supervector spaces

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

A particularly interesting choice of endomorphism occurs when we set . This endomorphism sends the generating function for the elementary symmetric polynomials to the generating function , and this is an involution – in other words, it follows that and 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

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

I don’t trust uncountable sets

I have a mathematical confession: I don’t trust uncountable sets.

Some time ago on MathOverflow somebody asked what a reasonable definition of “infinite permutation” would be. The first answer that comes to mind is a bijection . The set of all such bijections does form a group, but not only is it uncountably generated, it contains, as Darsh observes, a copy of every countably generated group (acting on itself by left multiplication). In particular it contains a copy of the free group on countably many generators. It also doesn’t seem to carry any natural kind of topology.

On the other hand, a much nicer candidate is the set of “compactly supported” permutations, i.e. those which fix all but finitely many elements. This countable group is generated by transpositions and therefore has a neat presentation given by the usual relations. I believe it’s also the largest locally finite subgroup of the full group of bijections.

I find this group much more philosophically appealing than the full group of bijections, and the reason is simple: each element of the group is computable. On the other hand, only countably many elements of the full group of bijections are computable: the rest can’t be written down by a Turing machine. And I don’t trust anything that can’t be written down by a Turing machine.

Corollary: I don’t trust the real numbers.

Instead of explaining what I mean by this, which I don’t think I have time for today, I’ll just throw a question out to the audience: how do you feel about all this?

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

In a previous post I gave essentially the following definition: given a discrete dynamical system, i.e. a space and a function , and under the assumption that has a finite number of fixed points for all , we define the dynamical zeta function to be the formal power series

.

What I didn’t do was motivate this definition, mostly because I hadn’t really worked out the motivation myself. Now that we have an important special case worked out, we can discuss the general case, which will give a purely combinatorial proof of the second half of the Newton-Girard identities.

The cyclotomic identity and Lyndon words

In number theory there is a certain philosophy that is a good toy model for the integers . The two rings share an important property: they are basically the canonical examples of Euclidean domains, hence PIDs, hence UFDs. However, many number-theoretic questions involving prime factorization over are much easier than their corresponding questions over . One way to see this is to look at their zeta functions.

The usual zeta function reflects the structure of prime factorization through its Euler product

where the product runs over all primes; this is essentially equivalent to unique factorization. Since we know that monic polynomials over also enjoy unique factorization, it’s natural to ask whether there’s a sum over monic polynomials that would give a similar Euler product.

In fact, there is such a product, and investigating it leads naturally to a seemingly unrelated subject: the combinatorics of words.

Young’s lattice

As we saw last time, a sequence of nested groups gives rise to a graded “poset” in which objects can be related by more than one arrow. The poset we want to construct now is given by the sequence of symmetric groups (where and are both the trivial group). Since irreducible representations of the symmetric groups are parameterized by Young diagrams, this gives the set of Young diagrams a graded structure where the elements of rank are the Young diagrams with boxes.

It turns out that this “poset” is a genuine poset; in other words, in the restriction of an irreducible representation of to an irreducible representation of , the resulting representation contains each irreducible representation at most once. In fact, much more is true. In a poset we write if and there is no with ; this relation is called covering. So elements of rank cover elements of rank .

Theorem (Branching Rule): if and only if is obtained from by removing a box.

This is the remarkable theorem that really justifies the choice of Young diagrams as a natural description of the irreducible representations of the symmetric group. Today we’ll explore some of the consequences of this theorem.

The induced representation

Charles Siegel over at Rigorous Trivialities suggested a NaNoWriMo for math bloggers: instead of writing a 50,000-word novel, just write a blog post every day. I have to admit I rather like the idea, so we’ll see if I can keep it up.

Continuing the previous post, what we want to do now is to think of restriction as a forgetful functor, since restricting a representation just corresponds to forgetting some of the data that defines it. Its left adjoint, if it exists, should be a construction of the “free -representation” associated to an -representation. Given a representation we therefore want to find a representation with the following universal property: any -intertwining operator for a -representation on naturally determines a unique -intertwining operator . In other words, we want to construct a functor such that

.

Some adjoint functors

Note: as usual, I will be playing free and loose with category theory in this post. Apologies to those who know better.

One way to define a subgroup of a group is as the image of a homomorphism into . Given the inclusion map , the functor in the category of groups acts contravariantly to give a map called restriction. More concretely, the restricted representation of a representation is defined simply by . Hence there is a functorial way to pass from a representation of a group to one of a subgroup .

It is not obvious, however, whether there is a functorial way to pass from a representation of back to one of . There is such a construction, which goes by the name of induction, and we will need it later. Today we’ll discuss the general category-theoretic context in which induction is understood, where it is called an adjoint functor. For more about adjoints, see (in no particular order) posts at Concrete Nonsense, the Unapologetic Mathematician, and Topological Musings.

Math Overflow

The news has already been spreading around the blathosphere, but recently a website called Math Overflow modeled on Stack Overflow has opened up where anyone can post their mathematical questions. I would explain more, but the website is mostly self-explanatory.

MO couldn’t have come into existence at a better time for me. I’ve been carrying around a lot of questions I know someone should have an answer to, but I’ve never found a good way to ask them. For example, the conjecture I made at the end of my last post turned out to be a straightforward exercise in automaton theory. More generally I’m excited about the possibilities here in terms of improving the efficiency of mathematical research.

In other math-and-the-internet news, I have a Google Wave account, but (to my knowledge) nobody I do math with does! Hopefully this will be resolved eventually.

Extracting the diagonal

Needless to say, I have been very, very busy. But enough about me.

Suppose you are given a bivariate generating function

in “closed form,” where I’ll be vague about what that means. Such a generating function may arise, for example, from counting lattice paths in ; then might count the number of paths from to . If the path is only constrained by the fact that its steps must come from some set of steps containing only up or left steps, then we have the simple identity

.

Question: When can we determine the generating function in closed form?

I’d like to discuss an analytic approach to this question that gives concrete answers in at least a few important special cases, including the generating function for the central binomial coefficients, which is our motivating example.

Something that’s been bugging me

When you find a new math blog, do you go back and read its archives?

This was a feasible strategy for me when I only found new math blogs every once in a blue moon, but now that Google Reader is recommending feeds to me I don’t think it’s sustainable. But now I’m wondering if other people attempt this at all.