Skip to content

Protected: Search-to-Decision Sample Complexity

This content is password protected. To view it please enter your password below:

Protected: Attacks on Ideal Lattices

This content is password protected. To view it please enter your password below:

Protected: Structured lattice reduction for rings

This content is password protected. To view it please enter your password below:

Protected: Search-to-Decision for NTRU

This content is password protected. To view it please enter your password below:

Aside

Jacobi-Trudi identities

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.

Riemann Hypothesis

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

NP-completeness of Hartree-Fock

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}

Follow

Get every new post delivered to your Inbox.