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. David Speyer says:

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. Oops. I did forget to define Y_i. I’ve edited my original comment — now it says that the flags agree everywhere expect the i plane.

4. 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)

Joel-
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).

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

6. Alex says:

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.