mathematics by story-telling part 1: Johnson scheme and irreps of S_n

A natural space on which the symmetric group S_n acts is the collection of all k subsets of {1,..,n}. The action is given by, for sigma in S_n, sigma({i_1,..,i_k}) = {sigma(i_1),..,sigma(i_k)}. One natural question to investigate is the number of S_n elements that do not fix any k set, i.e., the number of derangement of the action S_n on S_n / (S_k times S_{n-k}). This question turns out to be somewhat difficult even if we are only interested in the asymptotic number as n goes to infinity, divided by n!, i.e., the asymptotic probability that a randomly chosen S_n element doesn’t fix any k sets in {1,..n}. When k =1, the answer is simply 1/e, by inclusion exclusion principle. The idea is that we can count the number of sigma that fixes a particular element in {1,..,n}, and sum over all n elements to get n(n-1)! = n!, and then we have to subtract off the number of sigma that fixes two particular distinct elements in {1,..,n}, without regard to their ordering, summed over all unordered pairs, which gives n choose 2 times (n-2)! = n!/2, and then similarly three elements, 4 elements, etc, which gives n! (1-1+1/2-1/3! + 1/4! – ..) = n!/e.

The similar analysis for k >1 gets progressively more involved. For instance, the k=2 case can be analyzed as follows (courtesy of Lin Yuncheng), we first count how many sigma ‘s have no cycles of length less than or equal to 2. certainly those are not going to fix any 2-subsets. There are n!/ exp(1+1/2) such elements asymptotically as n goes to infinity, which can be obtained from generating function analysis on a recurrence equation given as follows: let a_n be the number we are interested in for k = 2. Consider the cycle in a particular sigma containing 1. If its length equals j, then there are a_{n-j} different choices of admissible permutations with each cycle of length greater than 2 after we remove the cycle containing 1, so the total number a_n must equal sum_{j=3}^{n-3} a_j. This is enough information to cook up a generating function a_n x^n and compute the asymptotic value of a_n based on the Taylor expansion of a formula in terms of x that the generating function satisfies. The detail can be safely left to the reader. The most challenging and creative part is to derive the recurrence equation based on the length of a fixed cycle.

The final answer for k=2 of how many derangements there are, is 2 n!/exp(1+1/2), where the 2 in front comes from the fact that besides the chunk with all cycles of length greater than 2, one can also add a single fixed point in the permutation. Thus by a simple calculation one sees that the number of such appendified permutations is equal to the number of unappendified permutations.

If one experiments with higher k, one soon notices that the answer will be always be a multiple of n!/exp(1+1/2), but the exact multiplier gets more and more complicated, usually in terms of a sum of exponentials of various exponents and coefficients. So at present, there doesn’t seem to be any efficient way of calculating this multiplier. One approach, however, has been suggested by me, which is to consider the character of the permutation representation of S_n acting on X_k = S_n/(S_k times S_{n-k}). It can be computed as follows: first we choose an orthonormal basis for the vector space L(X_k), {delta_x, x in X_k}, i.e., the dual basis of the vector space X_k CC. Then chi_k(sigma) = sum_{x in X_k} delta_{x, sigma x}, which equals 0 precisely when sigma does not fix any x in X_k! So the number of derangement a_{n,k} = #{sigma: chi_k (sigma)^2 = 0}. Here we take the square of the character since it’s convenient for decomposition in terms of sum of squares of the characters associated with the irreducible component representations of X_k. In fact, (and this is where the Harmonic analysis on finite Groups written by Tullio Ceccherini- Silberstein, Fabio Scarabotti, and Filippo Tolli comes into the scene), the representation M_{k,n-k} := L(X_k) for S_n can be decomposed into min{k,n-k}+1 pairwise nonequivalent irreducible representations. 

  In order to understand this decomposition into irreps, we need to introduce a pair of linear operators d: M_{k,n-k} -> M_{k-1,n-k+1} defined by df({i_1, ldots, i_{k-1}}) = sum_{{i_1, ldots, i_{k-1}} subset A; |A| = k} f(A), and d^* : M_{k-1,n-k+1} -> M_{k,n-k} defined as the adjoint of d. In fact d^* admits an explicit definition as well, which is completely dual to d, namely d^*f(A) = sum_{B subset A; |B| = |A| -1} f(B). Let’s check that this is indeed the case: suppose f in M_{k,n-k}, g in M_{k+1, n-k-1}, then
  <f, dg> = sum_{|A| = k} f(A) dg(A) = sum_{|A| = k, |B| = k+1, A subset B} f(A) g(B) = sum_{|B| = k+1} d^*f(B) g(B) = < d^* f, g>
where we have used the explicit definition of d^* in the third equality.

Now an important property of d and d^* is that they commute with the action of S_n on M_{k,n-k}, i.e., for any sigma in S_n, d(sigma . f) = sigma. (df). By linearity it clearly suffices to check on indicator functions of some A in X_{k,n}. For B in X_{k-1,n}
d sigma 1_A (B) = d 1_{sigma^{-1} A} (B) = sum_{B subset C; |C| = k} 1_{sigma^{-1} A} (C) = 1_{B subset sigma^{-1} A}.
sigma d 1_A (B) = sigma sum_{B subset C; |C| = k} 1_A (C) = sigma 1_{B subset A} = 1_{sigma B subset A} = 1_{B subset sigma^{-1} A}

So indeed they commute. Similarly d^* sigma = sigma d^*.
Next we define S^{m,n-m} = M_{m,n-m} cap ker(d: M_{m,n-m} to M_{m-1,n-m+1}), where ker denotes the kernel of the linear map, i.e., its zero set. By the intertwining property of d with the action on M_{m,n-m}, we have that S^{m,n-m} is invariant under the action of S_n. Similarly d^* S^{m,n-m} is invariant under the S_n action also. Furthermore we claim that
M_{k,n-k} is isomorphic as S_n modules to Oplus_{m=0}^{min{k, n-k}} (d^*)^{k-m} S^{m, n-m}.
  Let’s now also introduce an important operator Delta: M_{k,n-k} to M_{k,n-k} given by Delta f(A) = sum_{dist(B,A)=1, |B| = |A|} f(B), where the distance between A and B is simply |AB|= |BA| provided they have the same cardinality.
This should be compared with the Laplacian-Beltrami operator from differential geometry, since there is also an analogue of the Hodge Laplacian operator given by Delta’ = dd^* + d^* d.
We have the following relations which can be easily verified:
dd^* = Delta + (n-k)
d^* d = Delta + k 
So Delta’ = 2 Delta + n
It’s also easy to verify that the summands (d^*)^{k-m} S^{n-m,m} are eigenspaces of Delta. The completion of the proof that (d^*)^{k-m} S^{m,k-m} are irreducible representations will be postponed to next lecture.


About aquazorcarson

math PhD at Stanford, studying probability
This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s