The orthogonality relations for representations of finite groups

In order to continue our discussion of symmetric functions it will be useful to have some group representation theory prerequisites, although I will use many of the results in the representation theory of the symmetric groups as black boxes. I had planned on using this post to discuss Frobenius reciprocity, but got so carried away with motivating it that this post now stands alone.

Today I’d like to discuss the representation theory of finite groups over . As these are strong assumptions, the resulting theory is quite elegant, but I always found the proofs a little unmotivated, so I’m going to try to use the categorical perspective to fix that. Admittedly, I don’t have much experience with this kind of thing, so this post is for my own benefit as much as anyone else’s. The main focus of this post is motivating the orthogonality relations.

Read Full Post »

Newton’s sums, necklace congruences, and zeta functions

The goal of this post is to give a purely combinatorial proof of Newton’s sums which would have interrupted the flow of the previous post. Recall that, in the notation of the previous post, Newton’s sums (also known as the first Newton-Girard identity) state that

.

One way to motivate a combinatorial proof is to recast the generating function interpretation appropriately. Given a polynomial with non-negative integer coefficients and , let be the reciprocals of the roots of . Then

.

The left hand side of this identity suggests a particular interpretation in terms of the combinatorial species described by . Today we’ll describe this species when is a polynomial with non-negative integer coefficients and then describe it in the general case, which will handle the extension to the symmetric function case as well.

The method of proof used here is closely related to a post I made previously about the properties of the Frobenius map, and at the end of the post I’ll try to discuss what I think might be going on.

Read Full Post »

Introduction to symmetric functions

The theory of symmetric functions, which generalizes some ideas that came up in the previous discussion of Polya theory, can be motivated by thinking about polynomial functions of the roots of a monic polynomial . Problems on high school competitions often ask for the sum of the squares or the cubes of the roots of a given polynomial, and those not familiar with symmetric functions will often be surprised that these quantities end up being integers even though the roots themselves aren’t integers. The key is that the sums being asked for are always symmetric in the roots, i.e. invariant under an arbitrary permutation. The coefficients of a monic polynomial are the elementary symmetric polynomials of its roots, which we are given are integers. It follows that any symmetric polynomial that can be written using integer coefficients in terms of the elementary symmetric polynomials must in fact be an integer, and as we will see, every symmetric polynomial with integer coefficients has this property.

These ideas lead naturally to the use of symmetric polynomials in Galois theory, but combinatorialists are interested in symmetric functions for a very different reason involving the representation theory of . This post is a brief overview of the basic results of symmetric function theory relevant to combinatorialists. I’m mostly following Sagan, who recommends Macdonald as a more comprehensive reference.

Read Full Post »

Kraft’s inequality for prefix codes

Kraft’s inequality: Let be a prefix code on an alphabet of size , and let denote the number of codewords of length . Then .

In lieu of reposting my old blog posts I thought I’d revisit some of their topics instead. In an old post of mine I set this inequality as a practice problem. I had an easy but uninspired proof in mind, but recently I learned that this problem is an exercise in the first chapter of The probabilistic method by Alon and Spencer. The probabilistic proof is quite elegant, so I thought it was worth presenting.

Read Full Post »

The “correct” definition of a homomorphism

(Warning: I’m trying to talk about things I don’t really understand in this post, so feel free to correct me if you see a statement that’s obviously wrong.)

Why are continuous functions the “correct” notion of homomorphism between topological spaces?

The “obvious” way to define homomorphisms for a large class of objects involves thinking of them as “sets with extra structure,” and then homomorphisms are functions that preserve that extra structure. In category theory this is formalized by the notion of a concrete category, i.e. a category with a good notion of forgetful functor. For topological spaces this is the functor which gives the set of points.

However, a naive interpretation of “preserving additional structure” suggests that homomorphisms between topological spaces should be open maps, and this isn’t the case. So what gives?

I’m not sure. But rather than take the concrete perspective I’d like to talk about another general principle for defining a good notion of homomorphism.

Little insight: If you can realize a structure as a small category, homomorphisms should be functors.

Read Full Post »

Halmos on writing and education

John Ewing wrote up a nice collection of quotes from Paul Halmos for the Notices of the AMS; let’s meditate on his words.

For example:

The best notation is no notation; whenever possible to avoid the use of a complicated alphabetic apparatus, avoid it. A good attitude to the preparation of written mathematical exposition is to pretend that it is spoken. Pretend that you are explaining the subject to a friend on a long walk in the woods, with no paper available; fall back on symbolism only when it is really necessary.

I’d have to agree. I see this as one of the strongest aspects of, for example, Terence Tao’s expository style. His latest post on relativization is a perfect example; Tao is a master at recognizing when technical details would obscure his exposition and when they are necessary. A related point:

Read Full Post »