Classified problem November 4, 2009
Posted by Scott Carnahan in combinatorics.trackback
Today at tea, some grad students were discussing the following enumeration problem:
How many elements of
have zeroes in all diagonal entries?
I think they [Redacted]. The answer is apparently known but classified. It’s a sort of q-analog of derangements (i.e., permutations without fixed points), but if you take the derangement formula and add q-numbers in the naive way, the formula ![(q-1)^n \sum_{k=0}^n (-1)^k \frac{[n]!}{[k]!}](http://s0.wp.com/latex.php?latex=%28q-1%29%5En+%5Csum_%7Bk%3D0%7D%5En+%28-1%29%5Ek+%5Cfrac%7B%5Bn%5D%21%7D%7B%5Bk%5D%21%7D&bg=ffffff&fg=666666&s=0 "(q-1)^n \sum_{k=0}^n (-1)^k \frac{[n]!}{[k]!}")
Ricky Liu seems to have solved the problem:
but I have not tried to verify its correctness yet.
[Redacted - ed.].
This looks like a nice puzzle, but does it have any deeper
motivation? I’m fond of the linear groups over finite
fields, though far from being a combinatorist, so I tend to
look for conceptual links. (Is there really an analogy with
derangements? Linear operators represented by such
matrices could have lots of fixed points.)
Classified? Redacted? What’s the deal here? I know what was redacted, but why one earth would someone care to classify a solution to this problem? Wild, irresponsible speculation anyone?
To generalise Scott’s question above, how does anyone “classify” a mathematical result?
Sonia – I’d refer you to the National Security Agency database,but unfortunately their stuff is mostly classified.
(They seem to be the world’s biggest employer of Ph.D. mathematicians.)
To clarify my question a little bit, what is the point in classifying a result that someone else could independently discover? One doesn’t need access to the NSA’s labs to prove a theorem. I’d guess a lot of classified science does get discovered independently, though Clifford Cocks and RSA is the only example that comes to mind.
IMHO, the natural corollary is that suppressing knowledge is silly and a waste of everybody’s time.
PS: Prof. Humphreys, Your Lie algebras book is on my desk right now. Perhaps you could e-sign it for me?
@Humphreys: If we remove the
, then we can plug in q=1 and the resulting number is the derangements of size n. There’s a sort of conceptual way to think about it: look at the Bruhat decomposition of 
(say with respect to the Borel subgroup of lower triangular matrices) and count the number of matrices in each cell with zeroes on the diagonal. With a little bit of work, it can be shown that the cells indexed by derangements give a polynomial like 
where i is some number and f is some polynomial, while the cells indexed by other permutations give a polynomial like 
where f is some polynomial.
Steven – Thanks for giving me a better reason to
appreciate the problem. Though I haven’t yet figured
out what the final ! means in your earlier post. Is that
meant to be there?
Sonia – It’s done (but what exactly is required to e-sign
an actual printed book?) Anyway, you’d do well to consult
the revisions on my home page to the last revised
printing. (Publishers don’t revise any more, preferring
the cheaper print-on-demand technology.) GTM 9 was
a youthful excess, though it filled a gap at the time. It
was typed mostly by me on a small electric typewriter
and given no real copyreading by Springer, so the later
corrections were numerous. I recall walking the typescript
up Broadway to the old Springer-NY offices at the top of
the Flatiron Building. Not the current method, I guess.
Hope I get the LaTeX right in this comment ….
@Humphreys:
is q-analogue of n! counting the number of complete flags in an n-dimensional vector space over the field with q elements. (The other natural q-analogue of n! is the size of GL(n, q) and differs by a factor of q and a factor of (q – 1).)
Also, Ricky has been able to rewrite that expression as
, more obviously a q-analogue of derangements. Greta Panova also independently solved the problem (by a different method).
That redaction is completely pointless. My RSS feed reader picked up the first version of this post and the original information is stored in its database (since it caches the feeds). It’s probably lurking in several more plus search engine caches and the like. The effect of the redaction is probably to make it more likely that people will go looking to find out what exactly was removed!
It’s a lesson we Brits have been very slow to learn: the scandal and publicity of the cover-up is generally worse than the original crime. If you look at all the politicians who have resigned in the last few years, it’s never for the actual misdemeanour but always for the completely pointless cover-up.
I have to echo Scotts question. What does this all mean?
@Andrew: So, congratulations on cleverly having an RSS reader? The redacted material is not “scandalous” (or I wouldn’t have gone around talking about it in the common room), and your argument that (apparently) more people are going to read the word “redacted” and try to find out what used to be there than would have read what was there in the first place is … odd. (My apologies if the tone here is somewhat acid — it’s not intended to be nasty, but it’s always difficult to judge how such things get transmitted in text, hence this parenthetical.)
@Sonia: My (not very good) understanding is that a lot of pure mathematical research gets done at the NSA on subjects that in some cases (e.g., finite fields) might be important for cryptography. The result is that they end up classifying loads of stuff (like, say, this result) that is not obviously important for anything other than pure mathematical research, on the off chance that some of it really is useful to them. I personally find this silly, but I also understand the position of whatever bureaucrat at the NSA is in charge of it.
The fact that any such work is in principle duplicable outside the NSA is not the point (to them): if (say) the NSA can efficiently factor the product of two large prime numbers, this capability is extremely advantageous and important (to them) even if nothing stops someone else for discovering the same capability. That they wouldn’t make this information public is probably a disservice to humanity, but it’s also completely sensible given their official purpose.
My main reason for leaving the “redacted” notices was that I thought it would be funny. It seemed to fit well (in my mind) with the whole “classified secret stuff” theme. Given the response, I’ll have to rethink my dreams of becoming a text-mode comedian.
Incidentally, it took about 8-10 hours for the removed text to disappear from Google’s cache. That’s a pretty good memory hole.
Just chiming in that “redacted” did at least get a smirk out of me. Now you don’t have to claim that the lurkers support you in email.
Yeah, “funny.” More like preposterous.
Wow, harsh. Thank you for sharing, random internet person.
Upon further reflection, I think the problem was not the underlying idea, but the mediocre execution. It’s not clear that I should put much more effort into it, though.
Well, your blog description does say:
> Sort of like a seminar, but with (even) more rude commentary from the audience.
so what did you expect?
I still don’t understand the whole classified/redacted stuff but I’m beginning to think that I don’t really want to. When I first read this then it seemed as though you were being serious, which is why I made my comment about caches. Now it seems as though there’s a deep joke somewhere to do with, maybe, cryptography that I just don’t get. Ah, well. Humour never did cross the pond very well.
Is the problem easier if we only ask for vanishing trace?
Hi John! For vanishing trace, look at the Bruhat cell decomposition of GL(n, q) and it turns out that the intersection is exactly the 1/q of the cell you would expect, except that some adjustment is needed for the cell corresponding to the identity permutation. I don’t actually know how hard this is to prove (I’ve only seen it asserted, not proved).
@John: To follow up on Joel’s post, a formula for the number of traceless invertible matrices along with a proof is included in Stanley’s upcoming section edition of Enumerative Combinatorics vol. 1, which can be downloaded here:
http://math.mit.edu/~rstan/ec/ch1.pdf
(It’s Proposition 1.10.15)
FWIW, when I go to google’s cache, several days later, I see the original post with no redaction and no comments. I wouldn’t be shocked if google has geographically distributed
servers with different caches. But I’m surprised that Scott and I, both in New England, see different results.
John, JBL, Steven – In the trace 0 situation, but for SL
rather than GL, you are in effect looking for the number of
rational points in an affine variety: intersect the group with
its Lie algebra. Probably this doesn’t lead effectively to a
formula, but such a formulation (or an appeal to Bruhat
decomposition) is closer to the way I tend to think about
these problems. Anyway, I understand by now more of the
combinatorics in the original question, without totally
converting to that religion.
Ben, you are truly the bringer of bad news about the state of the internet. First you tell me EH’s Wikipedia article was repaired, and now this. Oh well, good to know. I recant my faith in the Google memory hole.
Steven Sam, thanks for the link. I had heard a lot of q-lore at Berkeley, but never managed to pick it up to the point of fluency.
I would look around memory caches to figure out what this whole “redacted/classified” business is about, but I get the sense from previous comments that it’s ultimately pointless. Oh well.
@Jim. I wonder if there is a “geometric” way of counting the intersections of tr(X) = 0 and the Bruhat classes. If we used
instead of 
this would a geometric question.
It would be cool to find a similar connection between flats and Schubert classes.
John – The short answer is that I don’t know, but the
question looks reasonable. The starting point could be
any algebraically closed field, such as one of prime
characteristic (then adapt to a smaller field of definition).
On the other hand, trace zero is probably special to the
GL or SL situation, within the natural matrix realization.
Bruhat decomposition occurs in other reductive or simple
groups, where for example it contributes to a uniform
computation of the finite group orders. There have been
other such counting arguments over finite fields, involving
intersections of double cosets, etc.
Don’t hesitate to use “\displaystyle” to make summation spiffier.