Triangle meander
Oct. 5th, 2011 11:01 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
sniffnoySo today I was sitting in the math common room working on my number theory problem set and one of my attempts at one of the problems (which probably would not have worked) yielded some polynomials that I didn't see any obvious pattern in but they were symmetric and began and ended with 1's so I wrote down their coefficients in a triangle. (OK, I could have easily written down a recurrence if I wanted to bother to, but I was hoping for maybe a bit more than that.)[0]
Well John Wiltshire-Gordon (a fellow grad student, first-year, also went to Chicago) wanders by and I pass him the triangle and just say something along the lines of, "Here, what do you make of this?" He's a bit puzzled; are those 11s there in row 3? Is that a 66? They are. Hm, well, the rows add up to factorials, that must be significant. Mel Hochster over at the next table overhears; "Oh, are you looking at Eulerian numbers?"
John: "I don't know, is 66 an Eulerian number?"
Mel: "Uh... I think so..."
So yes, these were Eulerian numbers. So, uh, what are Eulerian numbers? Something to do with the symmetric group, obviously. Number of permutations of a given length, is it? (Note here I'm considering Sn as being generated by the (i,i+1); with this generating set, length is just number of inversions.) That's gotta be what it is, right? Now of course this is ridiculous because lengths in Sn go up to n choose 2, but somehow neither of us notice this at the time. I work out the recurrence to see if I can prove this. I am being careful and slow and checking that the properties I expect actually work, but I keep getting my indexing wrong, so this takes me some time.
In any case John thinks this is cool because -- as he was going on about the other day -- if you have a Coxeter group and count the number of elements of a given length (note: the generating function of this is called a Poincare series), this tells you the cohomology of... something. He never really explained what. But apparently these numbers from cohomology in a more general context are also called Poincare series, and I'm guessing that usage probably came first. (Away at the blackboard, in a different context, Stembridge also mentions Poincare series. John turns his head.)
Anyway. After John takes some time pointing out my indexing errors (I was convinced there was something wrong with the recurrence I had written down -- there wasn't, I just kept screwing up the indexing trying to check it), finally I notice that number of elements of a given length is not at all possible as an interpretation of these. Spread them out, John suggests? No, you can't lack elements of intermediate length, I point out. Uh... John doesn't really remember... something about descent sets, he suggests? Time to look it up.
So Wikipedia tells us that it is in fact the number of permutations with a given number of "ascents" (an ascent being when an element is greater than the previous element); obviously ascents here could be replaced by descents, and indeed the number of descents in this sense is the size of the descent set in the sense of Coxeter groups, so that's what it is. (Hm: Are the sizes of the left and right descent sets equal in general? I suddenly realize I don't know this. Should figure this out.) Now John had been all excited because I had just been doing this and these cohomology dimensions had come up, and how it had been symmetric because of Poincare duality, and I point out, so this is not actually the cohomology of anything, then. Oh, but it is, he says! How's that? I ask. Well, he says, it's a triangle; and it begins and ends with 1s, and gets bigger in the middle; and it's symmetric. So it *must* be the cohomology of *something*!
Oh, is that so, I say. I decide to have a bit of fun with this and write down the first few rows of the Delannoy numbers (note, I didn't remember what they were called). "What's that the cohomology of, I ask?" He puzzles over it for a bit before finally asking what the recurrence is. I tell him and he declares that it's stupid. Where did you see these?! Oh, let's just throw that extra term in. These are completely unnatural. Not so, I say, I've seen them before! There's even a name for them! ("What, the stupid numbers?") There are a number of combinatorial interpretations! I just can't remember any of them[3]. He tries to interpret them as paths of a sort and I remember the obvious one, the one given on Wikipedia. OK, he decides, they're suitably natural after all and he does indeed set out actually trying to find something they're the cohomology of.
He hits a few snags, tries reduced cohomology instead, that isn't so helpful either. He wonders aloud what the Kunneth formula for reduced cohomology is. I, leaving, wander over to where Hunter is. Hunter points out that the Kunneth formula is entirely algebraic, so of course there's a Kunneth formula for reduced cohomology, you just have to account for the stuff in degree -1. I say, tell that to John, he's the one trying to do this. Oh, he says, he had figured we were doing topology homework. John comes over and notes that I was originally doing number theory homework; Hunter is confused. And so I gave a brief explanation of how we got here...
-Harry
[0]The actual way they came up was that I thought it would be helpful to look at the generating function of (k+1)n (k varying, n fixed); this is actually one of the first things Wikipedia mentions about them, I see...
[3]I did not mention where I originally encountered them, which was working with Arithmetree. Also later, a problem on the Putnam some years back.
Well John Wiltshire-Gordon (a fellow grad student, first-year, also went to Chicago) wanders by and I pass him the triangle and just say something along the lines of, "Here, what do you make of this?" He's a bit puzzled; are those 11s there in row 3? Is that a 66? They are. Hm, well, the rows add up to factorials, that must be significant. Mel Hochster over at the next table overhears; "Oh, are you looking at Eulerian numbers?"
John: "I don't know, is 66 an Eulerian number?"
Mel: "Uh... I think so..."
So yes, these were Eulerian numbers. So, uh, what are Eulerian numbers? Something to do with the symmetric group, obviously. Number of permutations of a given length, is it? (Note here I'm considering Sn as being generated by the (i,i+1); with this generating set, length is just number of inversions.) That's gotta be what it is, right? Now of course this is ridiculous because lengths in Sn go up to n choose 2, but somehow neither of us notice this at the time. I work out the recurrence to see if I can prove this. I am being careful and slow and checking that the properties I expect actually work, but I keep getting my indexing wrong, so this takes me some time.
In any case John thinks this is cool because -- as he was going on about the other day -- if you have a Coxeter group and count the number of elements of a given length (note: the generating function of this is called a Poincare series), this tells you the cohomology of... something. He never really explained what. But apparently these numbers from cohomology in a more general context are also called Poincare series, and I'm guessing that usage probably came first. (Away at the blackboard, in a different context, Stembridge also mentions Poincare series. John turns his head.)
Anyway. After John takes some time pointing out my indexing errors (I was convinced there was something wrong with the recurrence I had written down -- there wasn't, I just kept screwing up the indexing trying to check it), finally I notice that number of elements of a given length is not at all possible as an interpretation of these. Spread them out, John suggests? No, you can't lack elements of intermediate length, I point out. Uh... John doesn't really remember... something about descent sets, he suggests? Time to look it up.
So Wikipedia tells us that it is in fact the number of permutations with a given number of "ascents" (an ascent being when an element is greater than the previous element); obviously ascents here could be replaced by descents, and indeed the number of descents in this sense is the size of the descent set in the sense of Coxeter groups, so that's what it is. (Hm: Are the sizes of the left and right descent sets equal in general? I suddenly realize I don't know this. Should figure this out.) Now John had been all excited because I had just been doing this and these cohomology dimensions had come up, and how it had been symmetric because of Poincare duality, and I point out, so this is not actually the cohomology of anything, then. Oh, but it is, he says! How's that? I ask. Well, he says, it's a triangle; and it begins and ends with 1s, and gets bigger in the middle; and it's symmetric. So it *must* be the cohomology of *something*!
Oh, is that so, I say. I decide to have a bit of fun with this and write down the first few rows of the Delannoy numbers (note, I didn't remember what they were called). "What's that the cohomology of, I ask?" He puzzles over it for a bit before finally asking what the recurrence is. I tell him and he declares that it's stupid. Where did you see these?! Oh, let's just throw that extra term in. These are completely unnatural. Not so, I say, I've seen them before! There's even a name for them! ("What, the stupid numbers?") There are a number of combinatorial interpretations! I just can't remember any of them[3]. He tries to interpret them as paths of a sort and I remember the obvious one, the one given on Wikipedia. OK, he decides, they're suitably natural after all and he does indeed set out actually trying to find something they're the cohomology of.
He hits a few snags, tries reduced cohomology instead, that isn't so helpful either. He wonders aloud what the Kunneth formula for reduced cohomology is. I, leaving, wander over to where Hunter is. Hunter points out that the Kunneth formula is entirely algebraic, so of course there's a Kunneth formula for reduced cohomology, you just have to account for the stuff in degree -1. I say, tell that to John, he's the one trying to do this. Oh, he says, he had figured we were doing topology homework. John comes over and notes that I was originally doing number theory homework; Hunter is confused. And so I gave a brief explanation of how we got here...
-Harry
[0]The actual way they came up was that I thought it would be helpful to look at the generating function of (k+1)n (k varying, n fixed); this is actually one of the first things Wikipedia mentions about them, I see...
[3]I did not mention where I originally encountered them, which was working with Arithmetree. Also later, a problem on the Putnam some years back.
