Zeta functions, statistical mechanics and Haar measure

An interesting result that demonstrates, among other things, the ubiquity of in mathematics is that the probability that two random positive integers are relatively prime is . A more revealing way to write this number is , where

is the Riemann zeta function. A few weeks ago this result came up on math.SE in the following form: if you are standing at the origin in and there is an infinitely thin tree placed at every integer lattice point, then is the proportion of the lattice points that you can see. In this post I’d like to explain why this “should” be true. This will give me a chance to blog about some material from another math.SE answer of mine which I’ve been meaning to get to, and along the way we’ll reach several other interesting destinations.

Read Full Post »

Hecke algebras and the Kazhdan-Lusztig polynomials

The Hecke algebra attached to a Coxeter system is a deformation of the group algebra of defined as follows. Take the free -module with basis , and impose the multiplicative relations

if , and

otherwise. (For now, ignore the square root of .) Humphreys proves that these relations describe a unique associative algebra structure on with as the identity, but the proof is somewhat unenlightening, so I will skip it. (Actually, the only purpose of this post is to motivate the definition of the Kazhdan-Lusztig polynomials, so I’ll be referencing the proofs in Humphreys rather than giving them.)

The motivation behind this definition is a somewhat long story. When is the Weyl group of an algebraic group with Borel subgroup , the above relations describe the algebra of functions on which are bi-invariant with respect to the left and right actions of under a convolution product. The representation theory of the Hecke algebra is an important tool in understanding the representation theory of the group , and more general Hecke algebras play a similar role; see, for example MO question #4547 and this Secret Blogging Seminar post. For example, replacing and with and gives the Hecke operators in the theory of modular forms.

Read Full Post »

Coxeter groups

At SPUR this summer I’ll be working on the Kazhdan-Lusztig polynomials, although my mentor and I haven’t quite pinned down what problem I’m working on. I thought I’d take the chance to share some interesting mathematics and also to write up some background for my own benefit. I’ll mostly be following the second half of Humphreys.

A Coxeter system is a group together with a generating set and presentation of the form

where , and . (When there is no relation between , we write this as .) The group is a Coxeter group, and is usually understood to come with a preferred presentation, so we will often abuse terminology and use “group” and “system” interchangeably. is also referred to as the set of simple reflections in , and the rank. (We will only consider finitely-generated Coxeter groups.)

Historically, Coxeter groups arose as symmetry groups of regular polytopes and as Weyl groups associated to root systems, which in turn are associated to Lie groups, Lie algebras, and/or algebraic groups; the former are very important in understanding the latter. John Armstrong over at the Unapologetic Mathematician has a series on root systems. In addition, for a non-technical overview of Coxeter groups and -analogues, I recommend John Baez’s week184 through week187. The slogan you should remember is that Weyl groups are “simple algebraic groups over .”

Read Full Post »

GILA IV: The unreasonable effectiveness of generating functions in the combinatorial sciences

We’ve got everything we need to prove the Polya enumeration theorem. To state the theorem, however, requires the language of generating functions, so I thought I’d take the time to establish some of the important ideas. It isn’t possible to do justice to the subject in one post, so I’ll start with some references.

Many people recommend Wilf’s generatingfunctionology, but the terminology is non-standard and somewhat problematic. Nevertheless, it has valuable insight and examples.

I cannot recommend Flajolet and Sedgewick’s Analytic Combinatorics highly enough. It is readable, includes a wide variety of examples as well as very general techniques, and places a great deal of emphasis on asymptotics, computation, and practical applications.

If you can do the usual computations but want to learn some theory, Bergeron, Labelle, and Laroux’s Combinatorial Species and Tree-like Structures is a fascinating introduction to the theory of species that requires fairly little background, although a fair amount of patience. It also contains my favorite proof of Cayley’s formula.

Doubilet, Rota, and Stanley’s On the idea of generating function is part of a fascinating program for understanding generating functions with posets as the fundamental concept. I may have more to say about this perspective once I learn more about it.

While it is by no means comprehensive, this post over at Topological Musings is a good introduction to the basic ideas of species theory.

And a shameless plug: the article I wrote for the Worldwide Online Olympiad Training program about generating functions is available here. I tried to include a wide variety of examples and exercises taken from the AMC exams while focusing on techniques appropriate for high-school problem solvers. There are at least a few minor errors, for which I apologize. You might also be interested in this previous post of mine.

In any case, this post will attempt to be a relatively self-contained discussion of the concepts necessary for understanding the PET.

Read Full Post »

Young diagrams, q-analogues, and one of my favorite proofs

I’ve decided to start blogging a little more about the algebraic combinatorics I’ve learned over the past year. In particular, I’d like to present one of my favorite proofs from Stanley’s Enumerative Combinatorics I.

The theory of Young tableaux is a great example of the richness of modern mathematics: although they can be defined in an elementary combinatorial fashion, interest in the theory is primarily driven (as I understand it) by their applications to representation theory and other fields of mathematics. The standard application is in describing the irreducible representations of the symmetric group in characteristic zero. I’ll be describing a more elementary aspect of the theory: the relationship between Young diagrams and -binomial coefficients.

Young diagrams can be defined as a visual representations of partitions. A partition of is a weakly decreasing sequence such that . Partitions uniquely describe cycle decompositions, hence conjugacy classes, of the symmetric group, which is a hint at the connection to representation theory. A Young diagram of the partition consists of rows of boxes where the row has boxes. Let denote the poset of Young diagrams that fit into an box, ordered by inclusion: equivalently, one can define the full Young lattice and define to be the elements less than or equal to the partition. (One can then define a standard Young tableau to be a chain in the Young lattice, but we will not need this notion.) One can easily check that the following is true.

Proposition: .

The rest of this post explains the -analogue of this result.

Read Full Post »