Set-multiset duality and supervector spaces

November 6, 2009

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

Read the rest of this entry »


I don’t trust uncountable sets

November 5, 2009

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 \mathbb{N} \to \mathbb{N}. 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 S_{\infty} 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 \mathbb{N} \to \mathbb{N} 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

November 4, 2009

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

\displaystyle \zeta_X(t) = \exp \sum_{n \ge 1} (\text{Fix } f^n) \frac{x^n}{n}.

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.

Read the rest of this entry »


The cyclotomic identity and Lyndon words

November 3, 2009

In number theory there is a certain philosophy that \mathbb{F}_q[x] is a good toy model for the integers \mathbb{Z}. 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 \mathbb{F}_q[x] are much easier than their corresponding questions over \mathbb{Z}. One way to see this is to look at their zeta functions.

The usual zeta function \zeta(s) = \sum_{n \ge 1} \frac{1}{n^s} reflects the structure of prime factorization through its Euler product

\displaystyle \zeta(s) = \prod_p \frac{1}{1 - p^{-s}}

where the product runs over all primes; this is essentially equivalent to unique factorization. Since we know that monic polynomials over \mathbb{F}_q[x] 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.

Read the rest of this entry »


Young’s lattice

November 2, 2009

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 S_0 \le S_1 < S_2 < S_3 of symmetric groups (where S_0 and S_1 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 n are the Young diagrams with n boxes.

It turns out that this “poset” is a genuine poset; in other words, in the restriction of an irreducible representation of S_n to an irreducible representation of S_{n-1}, the resulting representation contains each irreducible representation at most once. In fact, much more is true. In a poset we write \lambda \triangleright \mu if \lambda > \mu and there is no \lambda' with \lambda > \lambda' > \mu; this relation is called covering. So elements of rank n cover elements of rank n-1.

Theorem (Branching Rule): \lambda \triangleright \mu if and only if \mu is obtained from \lambda 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.

Read the rest of this entry »


The induced representation

November 1, 2009

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 \text{Res}_H^G :  \text{Rep}(G) \to \text{Rep}(H) 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 G-representation” associated to an H-representation. Given a representation \rho : H \to \text{Aut}(V) we therefore want to find a representation \rho' : G \to \text{Aut}(V') with the following universal property: any H-intertwining operator \phi : V \to W for \tau a G-representation on W naturally determines a unique G-intertwining operator \phi' : V' \to W. In other words, we want to construct a functor \text{Ind}_G^H : \text{Rep}(H) \to \text{Rep}(G) such that

\text{Hom}_{\text{Rep}(G)}(\text{Ind}_H^G \rho, \tau) \simeq \text{Hom}_{\text{Rep}(H)}(\rho, \text{Res}_H^G \tau).

Read the rest of this entry »


Some adjoint functors

October 27, 2009

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 H of a group G is as the image of a homomorphism into G. Given the inclusion map H \to G, the functor \text{Hom}(G, \text{End}(V)) in the category of groups acts contravariantly to give a map \text{Res}_H^G : \text{Rep}(G) \to \text{Rep}(H) called restriction. More concretely, the restricted representation \rho|_H of a representation \rho is defined simply by \rho|_H(h) = \rho(h). Hence there is a functorial way to pass from a representation of a group G to one of a subgroup H.

It is not obvious, however, whether there is a functorial way to pass from a representation of H back to one of G. 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.

Read the rest of this entry »


Math Overflow

October 14, 2009

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

October 7, 2009

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

Suppose you are given a bivariate generating function

\displaystyle F(x, y) = \sum_{m, n \ge 0} f(m, n) x^m y^n

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 \mathbb{Z}_{\ge 0}^2; then f(m,  n) might count the number of paths from (0, 0) to (m, n). If the path is only constrained by the fact that its steps must come from some set S \subset \mathbb{Z}_{\ge 0}^2 of steps containing only up or left steps, then we have the simple identity

\displaystyle F_S(x, y) = \frac{1}{1 - \sum_{(a, b) \in S} x^a y^b}.

Question: When can we determine the generating function \displaystyle D_F(x) = \sum_{n \ge 0} f(n, n) x^n 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.

Read the rest of this entry »


Something that’s been bugging me

October 6, 2009

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.