The Jacobi-Trudi identities

Today I’d like to introduce a totally explicit combinatorial definition of the Schur functions. Let be a partition. A semistandard Young tableau of shape is a filling of the Young diagram of with positive integers that are weakly increasing along rows and strictly increasing along columns. The weight of a tableau is defined as where is the total number of times appears in the tableau.

Definition 4:

where the sum is taken over all semistandard Young tableaux of shape .

As before we can readily verify that . This definition will allow us to deduce the Jacobi-Trudi identities for the Schur functions, which describe among other things the action of the fundamental involution . Since I’m trying to emphasize how many different ways there are to define the Schur functions, I’ll call these definitions instead of propositions.

Definition 5: .

Definition 6: .

The Lindstrom-Gessel-Viennot lemma

One of my favorite results in algebraic combinatorics is a surprisingly useful lemma which allows a combinatorial interpretation of the determinant of certain integer matrices. One of its more popular uses is to prove an equivalence between three other definitions of the Schur functions (none of which I have given yet), but I find its other applications equally endearing.

Let be a locally finite directed acyclic graph, i.e. it has a not necessarily finite vertex set with finitely many edges between each pair of vertices such that no collection of edges forms a cycle. For example, could be with edges and , which we’ll denote the acyclic plane. Assign a weight to each edge and assign to a path the product of the weights of its edges. Given two vertices let denote the sum of the weights of the paths from to . Hence even if there are infinitely many such paths this sum is well-defined formally, and if there are only finitely many paths between two vertices then setting each weight to gives a well-defined non-negative integer.

Let and be a collection of vertices called sources and vertices called sinks. We are interested in -tuples of paths, hereafter to be referred to as -paths, sending each source to a distinct sink. Let be the matrix such that . Then the permanent of counts the number of -paths, but this is not interesting as permanents are hard to compute.

A -path is called non-intersecting if none of the paths that make it up share a vertex; in particular, each is sent to distinct . A non-intersecting path determines a permutation of the vertices; let the sign of a non-intersecting -path be the sign of this permutation.

Lemma (Lindstrom, Gessel-Viennot): is the signed sum of the weights of all non-intersecting -paths.

Corollary: If the only possible permutation is (i.e. is non-permutable), then is the sum of the weights of all non-intersecting -paths.

Groups vs. abelian groups

A few weeks ago on MathOverflow Greg Muller asked, “why do groups and abelian groups feel so different?” The answers were very interesting and came from several different perspectives, but I still don’t feel as if the question was resolved. So I’ll try to synthesize and summarize some of the answers and hopefully something will be clearer in the end.

The many faces of Schur functions

The last time we talked about symmetric functions, I asked whether the vector space could be turned into an algebra, i.e. equipped with a nice product. It turns out that the induced representation allows us to construct such a product as follows:

Given representations of , their tensor product is a representation of the direct product in a natural way. Now, injects naturally into , which gives a new representation

.

The character of this representation is called the induction product of the characters of , and with this product becomes a graded commutative algebra. (Commutativity and associativity are fairly straightforward to verify.) It now remains to answer the first question: does there exist an algebra homomorphism ? And can we describe the inner product on coming from the inner product on ?

To answer this question we’ll introduce perhaps the most important class of symmetric functions, the Schur functions .

N.B. I’ll be skipping even more proofs than usual today, partly because they require the development of a lot of machinery I haven’t described and partly because I don’t understand them all that well. Again, good references are Sagan or EC2.

Whoops!

I seem to have broken my MaBloWriMo streak. I hope you’ll believe me when I say it was impossible for me to get a post up yesterday. Unfortunately, the rest of this week looks just as hairy (for completely different reasons), so I’m going to have to take a break. Here’s where we’re headed once I have time again:

I’m going to skip a lot of background at some point and just introduce several equivalent definitions of the Schur functions. My hope is that stating some of the important results of the theory, even without proof, will be enough to get other people interested in symmetric function theory. I also get a lot of material to go back to and flesh out in subsequent posts, since I haven’t gone through most of the proofs of the basic results very thoroughly.

After that, I want to meander slowly through parts of basic algebraic number theory and algebraic geometry. My goal here is to thoroughly understand the classical analogy between rings of integers in number fields and nonsingular affine algebraic curves. Since several bloggers have covered much of this material in some form already, I’ll try to link to other posts I’m aware of, but I’ll have to repeat some things because I want to motivate every definition I need.

Since I don’t have anything else to say at the moment, let’s make this post an open thread and we’ll see if the Scott Aaronson style of blogging works for me. General comments, questions, suggestions, requests, etc. welcome!

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.