1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ So the thing is that you have to do too much effort to compute them in the direct way, right? And that is the reason why people tried to computing them in an easier or less effortless way? $\endgroup$ – idriskameni Feb 10 at 18:27
  • $\begingroup$ Yes, that's what I am saying. $\endgroup$ – darij grinberg Feb 10 at 18:30
1
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ Does the final sentence want to say that proving such a lower bound would prove $P\neq NP$? (I don't know what a solution to $P=NP$ would be, unless you mean something like $N=1$, $P$ arbitrary.) $\endgroup$ – Marc van Leeuwen Feb 12 at 10:24
  • $\begingroup$ @Marc The computational complexity problem. It's the name of the problem. $\endgroup$ – Matt Samuel Feb 12 at 10:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.