skew Schur functions $C^{\lambda}_{\mu, \nu}$

Question

When working with skew Schur functions, they can be defined as follows.

Let $C^{\lambda}_{\mu, \nu}$ be the integers such that

$$s_{\mu}s_{\nu}=\sum_{\lambda} C^{\lambda}_{\mu, \nu} s_{\lambda}$$

Then, we can define skew Schur functions as

$$s_{\lambda/\mu}= \sum_{\nu} C^{\lambda}_{\mu, \nu} s_{\nu}$$

My question is, if we can calculate each of this $s_{\mu}$, $s_{\nu}$, and $s_{\lambda}$, why can't we find $C^{\lambda}_{\mu, \nu}$ sometimes?

My teacher told me that something very different is to have a formula and to have an explicit product. He told me that these coefficients are not always easy to compute. And I have seen in some papers that it is equal to the number of tableaux such that has shape $\lambda$ and whatever. I mean, they use another methods to compute such coefficients.

Why does this happens if we know how to compute all but one object in this formula?

Answer 1

Of course, you can compute the Littlewood-Richardson coefficients by multiplying out $s_\mu s_\nu$ and expanding it in the Schur basis. But this isn't very efficient -- you cannot compute directly in the Schur basis (unless you already know the Littlewood-Richardson coefficients), so you would have to convert $s_\mu$ and $s_\nu$ into another basis (e.g., monomial or complete homogeneous) first, then multiply out, then convert the result back.

Answer 2

We do know how to compute the $C_{\mu, \nu}^\lambda$, for instance by counting tableaux as you said. There are also faster ways than that using recurrence relations. Finding a formula for the coefficients is not particularly difficult, the main issue was finding a formula that expressed it as the cardinality of a set. Such a formula, the Littlewood-Richardson rule, was conjectured in the 1930s and no one was able to prove it until 1970.

There's something rather deep going on here. It turns out that computing the coefficients is a #P-complete problem, so you can reduce any problem that counts the number of accepting states of a Turing machine that runs in nondeterministic polynomial time to computing these coefficients. While we don't have any concrete results on this, the fastest known algorithms run in exponential time, and it's speculated that that is the best one can do.

A lower bound on the time to compute it that is larger than polynomial would be effectively a solution to $P=NP$.