Interpreting the Hecke Algebra

Let F_q denote the finite field with q elements. Let Flag_n(q) denote the set of complete flags (V_0, V_1, \ldots, V_n) in F_q^n. Such a flag is a chain of subspaces of F_g^n, with V_{i} subset V_{i+1} and dim V_i=i. For example, if n=3, an element of Flag_n(q) is a quadruple ( { 0 }, L, H, F_q^3), where H is a plane through the origin and L is a line through the origin, with L contained in H. Of course, including V_0 and V_n is redundant, as V_0 is always zero and V_n is always F_q^n, but we will see that it is convenient to have them around. Now consider the following operation: forget V_i and replace it by one of the other possible i-planes lying between V_{i-1} and V_{i+1}. There are q such choices, and we pick uniformly at random. Note that we are forbidden to just put V_i back where it was. We will denote this operation by P_i.

Let’s do an example: starting with a given flag, in the case n=3, what is the effect of P_1 P_2 P_1? Note that we draw our pictures projectively, so we visualize (V_1, V_2) as a pair (point, line through the point) in the projective plane. Let’s call this pair (p,\ell). The first step moves the point p along the line \ell to a new point p' . The second step pivots the line \ell about the point p' to a new line \ell'. And the final step slides the point p' along the pivoted line \ell' to its final resting place at p''.


(Click the image for a larger version.) Now, if we are given (p, \ell) and (p'', \ell'), what is the probability that P_1 P_2 P_1 takes us from (p, \ell) to (p'', \ell')?

Exercise: This probability is zero if \ell=\ell', or if any two of the points p, \ell \cap \ell' and p'' coincide. If none of these unfortunate events occur, then the probability is 1/q^3. (Hint: note that we must take p'=\ell \cap \ell' to have any chance of success.

Now, here is the interesting thing. Run through the same analysis for P_2 P_1 P_2. The intermediate stages of the process will look completely different, but the end effect is precisely the same: probability zero in the degenerate cases mentioned above, and probability 1/q^3 the rest of the time.


So we can write the equation P_1 P_2 P_1=P_2 P_1 P_2 and, more generally, P_{i} P_{i+1} P_{i}=P_{i+1} P_i P_{i+1}. If you are uncomfortable talking about an equality of “processes”, you may interpret P_i as a linear operator on the space of probability distributions on Flag_n(q). There are also two other relations between the P_i. The first, which is completely obvious, is that P_i P_j=P_j P_i when |i-j| geq 2. The second, which takes only a moment’s more thought, says that P_i^2=1/q+(1-1/q) P_i. In other words, if we do P_i twice, there is a 1/q chance that we will get back the i-plane we stared with and a 1-1/q chance that we won’t. Noah Snyder and John Baez can talk for hours about how this shows up in the tensor category of representations of a quantum group, so I won’t. Instead, I’ll explain some of the consequences of this for combinatorialists. At the end, I’ll bring up a very natural question that Jim Propp asked me, to which I don’t have a good answer yet. If no one writes in with a good solution, then I’ll pull together a sequel explaining my failed attempts.

All right, first of all, I have the word Hecke Algebra in the title and I haven’t defined it yet. Let’s fix that right now: The Hecke algebra is the algebra of operators on probability distributions on Flag_n(q) generated by T_i := q P_i. That factor of q is just there to get rid of the denominators. (Actually, T_i is also more natural than P_i from the general Hecke perspective that John Baez and Jim Dolan are presenting over at the n-Category cafe. But P_i is both a little easier to think about, and a lot more natural for Jim’s question.) We can also describe the Hecke algebra as the algebra with generators T_1, T_2, …, T_{n-1} and the relations: T_{i} T_{i+1} T_i = T_{i+1} T_i T_{i+1}, T_i T_j=T_j T_i when |i-j| geq 2 and T_i^2=(q-1) T_i+q.

A priori, the Hecke algebra could be huge! One could imagine that it has dimension |Flag_n(q)|^2 approx q^{n(n-1)}. In fact, it only has dimension n!. (Also huge, but not as huge.) To see why this might be the case, let’s imagine plugging in q=1. This doesn’t make sense in if we use the definition in terms of operators on Flag_n(q), but the definition in terms of generators and relations works just fine. Our relations now read T_{i} T_{i+1} T_i = T_{i+1} T_i T_{i+1}, T_i T_j=T_j T_i when |i-j| \geq 2 and T_i^2=1. Let s_i be the element of the permutation group S_n which swaps i and i+1, leaving 1, 2, …, i-1, i+2, …, n where they are. Then the s_i satisfy the same relations. It is a fundamental result in Coxeter theory that the group generated by r_1, r_2, …, r_{n-1} subject to these relations is S_n. So, when q=1, the Hecke algebra is isomorphic to the group algebra of S_n. In other words, if the relation s_{i_1} s_{i_2} \cdots s_{i_a}=s_{j_1} s_{j_2} \cdots s_{j_b} holds in S_n, then the corresponding relation T_{i_1} T_{i_2} \cdots T_{i_a}=T_{j_1} T_{j_2} \cdots T_{j_b} holds in the Hecke algebra (at q=1.)

When q is not 1, life is trickier. However, we have the following amazing result: Suppose that the words s_{i_1} s_{i_2} \cdots s_{i_a} and s_{j_1} s_{j_2} \cdots s_{j_b} are both reduced. This means that a=b and there is no shorter way to write s_{i_1} s_{i_2} \cdots s_{i_a} as a product of s_i‘s. Then the relation T_{i_1} T_{i_2} \cdots T_{i_a}=T_{j_1} T_{j_2} \cdots T_{j_b} is still true, for arbitrary q. This gives us a way, for any element w of S_n, to define a corresponding element T_w in the Hecke algebra: simply take the product T_{i_1} T_{i_2} \cdots T_{i_a} where s_{i_1} s_{i_2} \cdots s_{i_a} is a reduced word for w. Furthermore, it turns out that the T_w are a basis for the Hecke algebra.

Expressing nonreduced products of the T_i‘s in the basis of T_w‘s is an area of active combinatorial research. In the probabilistic model at the start of this section, we can describe the problem this way: Suppose we do a Markov walk on Flag_n(q), performing one P_i after another. Can we give an explicit description of how this walk mixes? (Of course there are many variants of this problem, because I haven’t told you how to select the sequence of P_i which we use.)

This brings us to Jim’s question. In the Markov description above, there is no interpretation of sending q to 1. Jim asked whether there was an alternate Markov process we could come up with, which modeled the Hecke algebra, but in which q was a continuous parameter. (Or, rather, this was my interpretation of a somewhat less specific question.) Presumably, as q went to 1, this process would become the Cayley graph of S_n. I can do this in a stupid way, by defining a certain orientation on said Cayley graph and defining a walk which is random except that, when the walk would take an edge which is directed against it, it stays put instead with probability 1-1/q. But what I think would be interesting would be to define a Markov process on Flag_n(\mathbb{C}) which, as q goes to 1, becomes the Cayley walk on the n! permutation flags.

Any ideas?

9 thoughts on “Interpreting the Hecke Algebra

  1. Hi David,

    Your question is related to something that Greg Kuperberg asked me once.

    I don’t know a solution but here is an idea which I’m sure that you have already thought of. Also,I don’t really know what Markov process means but I bet what I will describe is close.

    Fix n, and let F = Flag_n(C^n).

    Consider the space D of constructible functions on F.

    Consider the locus Y_i \subset F \times F which consists of pairs of flags which agree at every spot other than the ith spot and disagree there. So Y_i has two pushforwards p_1, p_2 to F.

    Then define an operator P_i : D \rightarrow D by {p_2}_* p_1^*().

    Here {p_2}_* is “integration of constructible functions” which just means that you look at the Euler characteristics of fibres times the values of the function upstairs (ie first you break the domain into regions where the function is constant, then look at Euler char of these regions intersected with the fibres).

    I think that these P_i will satisfy the braid relations. Of course, we don’t have a “q” in the picture so it is hard to say whether they satisfy the relation involving q. In a sense the q would/could come from looking at Poincare polynomial rather than Euler characteristic. In good cases, Poincare polynomial specialize to number of points over the finite field when you plug in q. However, some of the fibre might be bad, so this won’t work.

    Is it possible that some kind of motivic picture could get around these difficulties?

  2. Hey Joel.

    First a quick note — you never define Y_i. I’m going to assume that it is the constructible set where we insist that the i-plane changes. That matches my conventions above, and gives the prettiest formulas.

    These P_i will indeed will indeed satisfy the braid relations. They also satisfy P_i^2=1.
    That’s because, when we do P_i twice, the space of ways to get back where we started is \mathbb{C}, with Euler characteristic one, while the space of ways to get to a given other point is $\mathbb{C}^*$, with Euler characteristic zero. My understadning is that the theory of motives exactly fixes this; that the motivic integral of $\mathbb{C}$ is not 1 but a formal parmeter $\Lambda$.

    I don’t really like this solution, though, because I don’t get to think of actual points smearing around in the flag manifold. (I tried to present something like this to Jim, but I did a really bad job of it, talking about pushing forward sheaves instead of just saying ” integrate with respect to Euler characteristic integral”.) What I’ve been hoping to do is take some actual measure on F \times F, concentrated on Y_i, and replace Euler characteristic integration with ordinary integrals. Then, as q went to one, we could let our measure approach a delta function on Allen’s non-complex Weyl group action.

  3. David-
    What’s so bad about random walks on Coxeter groups? One can think of a longer permutation as having “lower energy” and the condition on edges that lower in the Bruhat order as measuring how big the energy gap is. That is one could say something like: let the energy of a permutation w be -\ell(w). Then P_i tries to switch w(i) and w(i+1) by applying an amount of energy between [0,q/(q-1)] (and then stopping it once it reach an equilibrium point). If w(i) < w(i+1), then this pushes in an unstable direction, and the numbers will switch no matter how much energy you apply. If w(i+1) < w(i), then the amount of energy needs to be at least 1, or you roll back to your starting point.

    Perhaps this isn’t physically realistic, but it could still be explained to combinatorialists without making them tear their hair out (as opposed to bringing up mixed Hodge structures)

    Of course, the categorified version of this picture works great. Instead of functions, consider the derived category of perverse sheaves. Then this pull push is going to give you the action of the shuffling (or twisting, depending on which side of Koszul duality you like) functors on derived category O (the braid group action of interest to those who want to construct HOMFLY homology). However, here the q is coming from mixed Hodge structures. I don’t think those behave very well with respect to decategorification (which is why everything works better in characteristic p).

  4. I wrote things in terms of constructible functions in order to make it sound more like probability. Your start with a constructible function which you can think of as a kind of probability distribution (or at least a weighted count of points on the flag variety). Then you hit it with P_i and get another “probability distribution”.

    Yes, I agree with Ben that mixed is the key word for getting the “q” out of the complex geometry.

  5. Hi Dave:

    You’re probably aware of the (unique) paper of Diaconis-Ram. If what they are studying specializes to what you’re doing, I vaguely recall that things should conjecturally mix in n^2 steps.

Comments are closed.