← All problems

Moore and Russell's character bound for balanced Young diagrams

20 years old · traced to

Let C>0C>0. A Young diagram λ\lambda with nn boxes has at most CnC\sqrt{n} rows and columns, and let π∈Sn\pi\in S_n be a permutation. Moore and Russell's character bound. There exists a constant DD such that

∣χλ(π)∣<(Dn)∣π∣.|\chi^{\lambda}(\pi)| < \left(\frac{D}{\sqrt{n}}\right)^{|\pi|}.

This conjectured estimate would bound the multiplicities in Kronecker tensor products of balanced irreducible representations and would imply that the relevant quantum algorithm for graph isomorphism is no faster than the best known classical algorithms. Its resolution is not specified in the source.

References
  1. Amarpreet Rattan and Piotr Sniady, “Upper bound on the characters of the symmetric groups for balanced Young diagrams and a generalized Frobenius formula”, arXiv:math/0610540 (2007).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.