22
$\begingroup$

I like Kazhdan–Lusztig polynomials. I like them because I enjoy anything at the edge of where non-semisimple representation theory meets combinatorics. But if you asked me to motivate the Kazhdan–Lusztig polynomial definition, the only way I would be able to do that is via non-semisimple representation theory (characters of simples in Vermas etc).

It seems to me that much purer combinatorists than myself also agree that Kazhdan–Lusztig polynomials are interesting objects. I see a lot of papers which examine when the Kazhdan–Lusztig polynomials admit particularly beautiful combinatorial aspects to their construction. I'm also sort of aware that things like Kostka–Foulkes and LLT polynomials are special cases of Kazhdan–Lusztig polynomials and that these seem to be considered as a "better combinatorially understood/motivated" subfamily.

So my question is this: is it possible to convincingly motivate the definition and study of Kazhdan–Lusztig polynomials (even just in type $A$) from a solely combinatorial background? (With no representation theory or geometry?) If so, is there a nice reference for this? Even if it's just a nice example, rather than a whole body of theory, I'd still be interested. What I'm really looking for something that could serve to motivate a masters level student without them first having to do any non-semisimple representation theory.

Improve this question
$\endgroup$
4
  • 3
    $\begingroup$ This isn't exactly an answer to your question as stated, but if I were trying to motivate KL polynomials to a student without much algebra background I might do the following. Explain the recurrence for computing them. Do an example or two, maybe just in Type A, where you get something nontrivial, and note that even though there are signs in the recurrence you get something with only positive coefficients. Explain that this is a theorem, although not with any simple proof. Then state the "combinatorial invariance conjecture" and explain that this is still a conjecture in full generality. $\endgroup$
    – Sam Hopkins
    Commented Aug 22 at 12:55
  • 3
    $\begingroup$ A different answer: something very close to KL polynomials are the KL cells, and in Type A there is a beautiful description of KL cells in terms of "Knuth equivalence," which is closely related to the RSK algorithm. $\endgroup$
    – Sam Hopkins
    Commented Aug 22 at 13:05
  • 1
    $\begingroup$ The article "Relations between Young's natural and the Kazhdan-Lusztig representations of Sn" by Garsia and McLarnan, sciencedirect.com/science/article/pii/0001870888900606 might be a good way to motivate KL polynomials, or at least reduce the question to this other one: why do combinatorists care about representations of S_n? $\endgroup$
    – Abdelmalek Abdesselam
    Commented Aug 22 at 13:05
  • 3
    $\begingroup$ Honestly, Geordie Williamson's undergraduate thesis might be a really good guide here, I don't think it assumes much background at all in rep theory: people.mpim-bonn.mpg.de/geordie/Hecke.pdf $\endgroup$
    – Sam Hopkins
    Commented Aug 22 at 13:07

2 Answers 2

Reset to default
17
$\begingroup$

Here is an application that looks more combinatorial:

If you have a graded poset, it has a rank generating function. Many nice posets have palindromic rank generating functions, meaning that, for all $d$ the number of elements of rank $d$ is the same as the number of elements of rank $n-d$ (where $n$ is the maximum rank). (Even nicer is if a poset is self dual - there is an involution $I$ such that $v\leq w$ if and only if $I(v)\geq I(w)$; having palindromic rank generating function is a numerical weakening of being self dual.)

Consider the interval $[id,w]$ in Bruhat order. In general, its rank generating function is not palindromic, but if one counts an element $v$ by the KL polynomial $P_{v,w}(q)$ rather than naively, the rank generating function becomes palindromic. The KL polynomials are the correction factor for the failure of the rank generating function to be palindromic.

In particular, if the smallest nonconstant degree of $q$ appearing in $P_{id,w}(q)$ is $k$, then the number of elements in $[id,w]$ of rank $d$ and the number of elements of rank $n-d$ are equal for all $d<k$.

There is an analogue of KL polynomials for matroids, where this motivation is perhaps much more clear.

Of course, in the crystallographic case, this all comes from intersection cohomology for Schubert varieties (but note that Soergel bimodules are more or less algebraically defined analogues of the intersection cohomology).

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ I really like this, also because if you do end up wanting to talk about algebra and geometry, you can use this starting point to get to smoothness, Poincaré duality, etc. $\endgroup$
    – Sam Hopkins
    Commented Aug 22 at 17:27
  • $\begingroup$ This is a really nice motivation... is there a combinatorial proof? $\endgroup$
    – Chris Bowman
    Commented Aug 22 at 21:29
  • $\begingroup$ @ChrisBowman: I think you can extract a proof out of the Braden-Macpherson algorithm (if you accept that it computes KL polys) or out of the Elias-Williamson positivity proof - do you consider either of those combinatorial? At some point you need Poincare duality for intersection cohomology, either for real or for something constructed to mimic it. (You don't need the entire Hodge package.) $\endgroup$
    – Alexander Woo
    Commented Aug 23 at 0:11
5
$\begingroup$

This might provide one entry point: Kazhdan-Lusztig and R-polynomials from a combinatorial point of view, by F. Brenti (1998)

Kazhdan-Lusztig and R-polynomials have applications to algebra, topology, and representation theory. Although they were originally defined in terms of Hecke algebras, there are purely combinatorial rules to compute them. These rules not only make these objects more concrete, and accessible to a wider audience, but also make it easier to apply combinatorial reasoning and techniques to them.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Ah! But this only underscores my question! Kazhdan-Lusztig polynomials are defined entirely combinatorially. But the motivation you just cited is algebra, topology, and representation theory. These motivations require a lot of background to understand (namely, non-semisimple representation theory!) $\endgroup$
    – Chris Bowman
    Commented Aug 22 at 12:48
  • 3
    $\begingroup$ @ChrisBowman I'm a combinatorialist myself, but my personal answer is that there isn't really any good way to motivate KL polynomials from a purely combinatorial point of view. They're interesting to combinatoralists because they have beautiful and nontrivial combinatorial properties, but that's very different from saying that they can be motivated purely combinatorially. That said, one thing you could tell the master's student is that the KL polynomials enjoy some nonnegativity properties and it is an open problem to give those numbers a combinatorial interpretation. $\endgroup$
    – Timothy Chow
    Commented Aug 23 at 0:47
  • 2
    $\begingroup$ That open problem has been enough motivation for Brenti, a combinatorialist, to devote a large chunk of his career to it. This isn't motivation in the sense of "where does this come from" (to which I think the only honest answer is representation theory) but it is motivation in the sense of something that a combinatorialist can see is an interesting problem, without having to learn representation theory. $\endgroup$
    – Timothy Chow
    Commented Aug 23 at 0:48

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .