Abstract Nonsense

Crushing one theorem at a time

The Fundamental Result for Tableaux Combinatorics


Point of Post: In this post we prove that sum of f\left(\mathcal{F}\right)^2 where \mathcal{F} is taken over all n-frames is n!

\text{ }

Motivation

The ultimate goal of this brief journey into combinatorics land is that we will eventually show that there is a map \left\{n\text{-frames}\right\}\to\widehat{S_n}. But, the fact that there exists a correspondence is obvious since we know that \#\left(\widehat{S_n}\right)=p(n)=\left\{n\text{-frames}\right\}. What is interesting is that we are able to correspond an element \mathcal{F}\in\left\{n\text{-frames}\right\} an element of \widehat{S_n} in a meaningful way. What precisely I mean by ‘interesting’ I will wait to say, but probably the most useful part of it is that if \rho^{(\mathcal{F})} is the irrep corresponding to \mathcal{F}\in\left\{n\text{-frames}\right\} then \deg\rho^{(\mathcal{F})}=f_{\text{st}}\left(\mathcal{F}\right)–the number of standard Young tableaux on \mathcal{F}. In this post we prove a result which is not only integral in proving this fact but is consistent with this hypothesis, namely that the sum over all n-frames \mathcal{F} with f_{\text{st}}\left(\mathcal{F}\right)^2 is n!.

\text{ }

The Result

\text{ }

The idea of the proof is simple. We’ll induct on n (the n in the ‘sum over n-frames) and evaluate a certain double sum two ways: one way will tell us that the double actual reduces to the single sum in question and the other way will make the double sum amenable to applying the dimension hypothesis. We’ll heavily use our two facts about the sum over subordinate and superordinate frames and the standard tableaux on them. So, let’s get to it:

\text{ }

Remark: For notational convenience let \text{Frame}_n=\left\{n\text{-frames}\right\}

\text{ }

Theorem: For any n\in\mathbb{N} it is true that

\text{ }

\displaystyle \sum_{\mathcal{F}\in\text{Frame}_n}f_{\text{st}}\left(\mathcal{F}\right)^2=n!

\text{ }

Proof: We proceed by induction on n. Indeed, the result is true for n=1 since the only 1-frame is \begin{array}{|c|}\cline{1-1}\hphantom{\times}\\ \cline{1-1}\end{array} and so

\text{ }

\displaystyle \sum_{\mathcal{F}\in\text{Frame}_1}f_{\text{st}}\left(\mathcal{F}\right)^2=f_{\text{st}}\left(\begin{array}{|c|}\cline{1-1}\hphantom{\times}\\ \cline{1-1}\end{array}\right)^2=1^2=1=1!

\text{ }

So, assume the result is true for n and consider the sum

\text{ }

\displaystyle \sum_{\mathcal{F}\in\text{Frame}_{n+1}}\sum_{\mathcal{G}\triangleleft\mathcal{F}}f_{\text{st}}\left(\mathcal{F}\right)f_{\text{st}}\left(\mathcal{G}\right)

\text{ }

Writing it firstly as

\text{ }

\displaystyle \sum_{\mathcal{F}\in\text{Frame}_{n+1}}\left(f_{\text{st}}\left(\mathcal{F}\right)\left(\sum_{\mathcal{G}\triangleleft\mathcal{F}}f_{\text{st}}\left(\mathcal{G}\right)\right)\right)

\text{ }

and using our previous result about summing over subordinate frames we find that

\text{ }

\displaystyle \sum_{\mathcal{F}\in\text{Frame}_{n+1}}\sum_{\mathcal{G}\triangleleft\mathcal{F}}f_{\text{st}}\left(\mathcal{F}\right)f_{\text{st}}\left(\mathcal{G}\right)=\sum_{\mathcal{F}\in\text{Frame}_{n+1}}f_{\text{st}}\left(\mathcal{F}\right)^2

\text{ }

That said, a little thought shows that we may reverse this sum and write it as

\text{ }

\displaystyle \sum_{\mathcal{F}\in\text{Frame}_{n+1}}\sum_{\mathcal{G}\triangleleft\mathcal{F}}f_{\text{st}}\left(\mathcal{F}\right)f_{\text{st}}\left(\mathcal{G}\right)=\sum_{\mathcal{K}\in\text{Frame}_n}\sum_{\mathcal{H}\triangleright\mathcal{K}}f_{\text{st}}\left(\mathcal{H}\right)f_{\text{st}}\left(\mathcal{K}\right)

\text{ }

But, by our previous result on summing over superordinates we may rewrite the right side of the above as

\text{ }

\displaystyle (n+1)\sum_{\mathcal{K}\in\text{Frame}_n}f_{\text{st}}\left(\mathcal{K}\right)^2

\text{ }

and applying our induction hypothesis we see that this is equal to (n+1)!. Thus,

\text{ }

\displaystyle \begin{aligned}\sum_{\mathcal{F}\in\text{Frame}_{n+1}}f_{\text{st}}\left(\mathcal{F}\right)^2 &=\sum_{\mathcal{F}\in\text{Frame}_{n+1}}\sum_{\mathcal{G}\triangleleft\mathcal{F}}f_{\text{st}}\left(\mathcal{F}\right)f_{\text{st}}\left(\mathcal{G}\right)\\ &=\sum_{\mathcal{K}\in\text{Frame}_n}\sum_{\mathcal{H}\triangleright\mathcal{K}}f_{\text{st}}\left(\mathcal{K}\right)f_{\text{st}}\left(\mathcal{H}\right)\\ &=(n+1)!\end{aligned}

\text{ }

and so the induction is complete. \blacksquare

\text{ }

\text{ }

References:

1. Simon, Barry. Representations of Finite and Compact Groups. Providence, RI: American Mathematical Society, 1996. Print.

Advertisements

May 12, 2011 - Posted by | Algebra, Algebraic Combinatorics, Representation Theory | , , , , , , , , ,

3 Comments »

  1. […] our last post we let slip the deal with looking at the combinatorial objects we have been looking at. In […]

    Pingback by Hook-length in a Ferrer’s Diagram « Abstract Nonsense | May 12, 2011 | Reply

  2. […] of a frame, the number of standard Young tableaux with that frame. Consequently, as was previously mentioned this will also give us the degree of the irrep for . The idea of the proof is simple, we induct […]

    Pingback by The Hook-length Formula « Abstract Nonsense | May 14, 2011 | Reply

  3. […] enough being cryptic. I promised that we will create a bijection in such a way that –it’s about time I explained […]

    Pingback by A Weird Condition on Tableaux « Abstract Nonsense | May 22, 2011 | Reply


Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

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

Connecting to %s

%d bloggers like this: