Well, I begin to write something while I’m reading. I hope it can be more productive than before. Anyway, let’s begin. I’m now reading Qianchu Yuan’s post “The Jacobi-Trudi identities” right now. I’m lazy enough to make absolutely no change to the title. The title is not quite informative though. I don’t understand what Schur function is, but this post is going to introduce one definition of it. Let $\lambda \vdash n$ be a patition. What’s patition by the way? $T$, $\lambda$, weight $x^T=x_1^{T_1}x_2^{T_2}\cdots$, $s_\lambda(x_1,x_2,\cdots)=\sum\limits_T x^T$ sum over all tableaux of shape $\lambda$. Verify $s_{(k)}=h_k$, $s_{(1^k)}=c_k$. What’s $h_k$ and $c_k$ by the way? I can’t follow this post anymore, perhaps I should check the previous post first. Ok, now I’m back to Qiaochu Yuan’s post , which at first sight, seem accessible by me. Young diagrams is a visual representation of partition, that reminds me of the definition. I think I have seen it before. A partition of $k$ is a sequence  $\lambda_1 \ge \lambda_2 \ge ... \ge \lambda_i$  such that $\lambda_1+\cdots+\lambda_i=k$. Young diagram consists of $i$ rows and $j^{th}$ row has $\lambda_j$ boxes.  Let $L(m,n)$ denote the poset of Young diagrams which fit into an $m\times n$ box, ordered by inclusion. Verify $|L(m,n)|=\binom{m+n}{m}$. Mmm, let me think, well, that’s an obvious combinotorial  exercise. I have done it hundreds of times during my middle school years. So let’s move on. Now what’s $q$-analogue. Let’s be a bit patient.We now consider the number of boxes, which we denote $rank(\lambda)$. Wait, what do we mean by the number of boxes, let me check. Let us first define $R_q(m,n)=\sum\limits_{\lambda\in L(m,n)}q^{rank(\lambda)}$ and we have the result $R_1(m,n)=\binom{m+n}{m}$. Let me play around it for a while. Mmm, that means $R_1(m,n)=|L(m,n)|$ and what does that mean? I can’t see it still. Let me look at some other places. Now after checking Wikipaedia, I think the number boxes in $m\times n$ is $m\times n$(The reason that I’m previous confused is Qiaochu said $m\times n$ box in several lines before which really obscures the meaning of box). Then it seems wrong that $R_1(m,n)=|L(m,n)|$. Anyway, let’s move on and check back later. Oh, I suddenly see. Every power of 1 is 1, that’s why $R_1(m,n)=|L(m,n)|$. By flipping the diagonal, we get $R_q(m,n)=R_q(n,m)$. We have the property $R_q(n,0)=1$ and $R_q(m,n)=R_q(m,n-1)+q^nR_q(m-1,n)$. The first one is obvious. The second one is straight forward too. COnsider the first row of a Young diagram in $L(m,n)$. If it’s not of length $n$, it’s an element of $L(m,n-1)$. Otherwise we delete it, then it’s in $L(m-1,n)$. The $q^n$ accounts for the deletion(since the first row has $n$ boxes in this case which further consolidates my belief in what “box” is). Define $(n)_q=R_q(n-1,1)$, since $R_1(n-1,1)=n$, this can be viewed as the $q$-analogue of the number $n$. Define $(n)!_q=(n)_q(n-1)_q\dots(1)_q$ and $\binom{m+n}{n}_q=\frac{(m+n)!_q}{(m)!_q(n)!_q}$. We wish to prove $R_q(m,n)=\binom{m+n}{n}_q$. But for now let’s forget all about the computation and focus on the conception. We have the proposition: If $q$ is a power of a prime, then $\binom{n}{k}_q$ is the number of $k$-dimensional subspaces of $\mathbb{F}^n_q$. Now consider $GL_n(F_q)$.  $|GL_n(F_q)|=q^{\binom{n}{2}}(n)!_q$. Wait, I think there’s something wrong here. Shouldn’t it be $|GL_n(F_q)|=q^{\binom{n}{2}}(n)!_q(q-1)^n$? Anyway, let’s temporarily jump this. $GL_n(F_q)$ acts transitively on $Gr(n,k)$ of $k$-dimensional subspaces of $\mathbb{F}^n_q$, this is Grassmannian by the way. I first encountered this in my Differential Topology class. It’s already a year ago. So from the orbit-stabilizer theorem(a theorem which quite fits my intuition, I like that), we get $|Gr(n,k)|=\frac{|GL_n(F_q)|}{|Stab(x)|}$ where $Stab(x)$ denotes the stabilizer subgroup of any particular $k$-dimensional subspace. So we compute the stabilizer subgroup of the space spanned by the first $k$ standard basis vector: any stabilizer is block upper-triangular with $k\times k$ block consists an element of $GL_k(F_q)$ and $n-k$ columns  chosen arbitrarily. So (lovely combinatorics) there’s $(q^k-1)\cdots(q^k-q^{k-1})(q^n-q^k)\cdots(q^n-q^{n-1})$. So $|Gr(n,k)|=\binom{n}{k}_q$. After all, $(q-1)^n$ will be canceled out and it doesn’t really matter. But what it has to do with Young diagrams? They are related by the so-called “cellular decomposition” of the Grassmannian. The rest omitted, but I have understood the correspondence at this point. Now let’s look at if there are other posts about Young diagram.

And we do find another post Standard Young tableaux and Robinson-Schensted-Knuth. A Young tableau is a chain in Young’s lattice which can be represented in a augumenting way. Given a Young diagram $\lambda$, let $f^{\lambda}$ denote the number of Young tableaux of shape $\lambda$(I already see why it’s not unique). Another notation, if $\lambda$ is the partition of $n$, we write $|\lambda|=n$ or $\lambda \vdash n$. Theorem $\sum\limits_{\lambda \vdash n}(f^{\lambda})^2)=n!$. Well, the proof ideas is to show a bijection between permutations and pairs of standard Young tableaux of the same shape. More details are not explicit in the post.

Now finally we are back to The Jacobi-Trudi identities  again. This time I did see semistandard Young tableau $T$ differs from standard ones in the way that integers are only weakly increasing along rows. Now I guess $s_{(k)}$ means a $1\times k$ Young diagram. Equivalent definitions: $s_{\lambda}=det(h_{\lambda_i+j-i})_{1\leq i,j\leq n}$, $s_{\lambda'}=det(e_{\lambda_i+j-i})_{1\leq i,j\leq n}$. So there exists one problem, I still don’t get what $h$ and $e$ is. Let me check it out. After checking wiki, $h$ is complete homogeneous symmetric polynomials and $e$ is elementary symmetric polynomials. Ah, now I understand it. Let me play around why $s_{(k)}=h_k$, $s_{(1^k)}=e_k$. Umm, that’s basically because the integers weakly increase along the row and strictly increase along the column, yeah, I see the reason. Let’s move on the proof of equivalence of definitions. While reading the proof, I suddenly found the $\latex det$ part is related to Qiaochu’s previous post .

So now we are on another post again. It’s quite frustrating to going backward and forth, I really hate that as you do. Let’s see what we’ve got. Ah, there’s a confliction again. $e_k$ perhaps means exterior algebra. Anyway, I’m tired, perhaps I’ll pick up this post at some future time. Have a good day.

It has been my long-standing curiosity about  the reference on the inequality related to Riemann Hypothesis. Today accidentally I found it. It’s in “Sharper Bounds for the Chebyshev Functions $\theta (x)$ and $\psi (x)$. II”, page 339, Corollary 1

The reduction is from Ising spin glasses. This post is an excerpt from Schuch’s paper with my comments.

First we should check Hartree-Fock is in NP, to do this we notice the ground state is $|\phi_0\rangle =(n!)^{-1/2}det|\phi_a(1)\phi_b(2)...\phi_z(n)|$. And since the determinant can be computed in polynomial time, we can efficiently evaluate whether a ground state is below a threshold. Another way of writing the ground state is $b_N^{\dagger}b_{N-1}^{\dagger}...b_1^{\dagger}|\Omega\rangle$ where $b_i=\Sigma u_{ij}a_j$ and $latex |\Omega\rangle$ is the vacuum. Note that $b_i$ is a fermion creater which is antisymmetric and satisfy $b_i^{\dagger}b_i^{\dagger}$ is 0. So it’s equivalent to the determinant expression.

Basically what we do is add $\lambda n_{2i}n_{2i+1}(\lambda=\theta(N^2))$ to penalize double occupancy and convert $J_{ij}S_iS_j$ to $J_{ij}\sum_{p,q=0,1}(-1)^{p+q}n_{2i+p}n_{2j+q}$. Only one of the four terms actually appear since we add the penalty for double occupancy previously. $(-1)^{p+q}$ represents the sign of the product $S_iS_j$. The ground state mapping is $S_i=1$ to $b_i=a_{2i}$ and $S_i=-1$ to $b_i=a_{2i+1}$