[go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

On the complexity of computing Kronecker coefficients

  • Published:
computational complexity Aims and scope Submit manuscript

Abstract

We study the complexity of computing Kronecker coefficients \({g(\lambda,\mu,\nu)}\). We give explicit bounds in terms of the number of parts \({\ell}\) in the partitions, their largest part size N and the smallest second part M of the three partitions. When M =  O(1), i.e., one of the partitions is hook-like, the bounds are linear in log N, but depend exponentially on \({\ell}\). Moreover, similar bounds hold even when \({M=e^{O(\ell)}}\). By a separate argument, we show that the positivity of Kronecker coefficients can be decided in O(log N) time for a bounded number \({\ell}\) of parts and without restriction on M. Related problems of computing Kronecker coefficients when one partition is a hook and computing characters of S n are also considered.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Cristina M. Ballantine & Rosa C. Orellana (2005/07). A combinatorial interpretation for the coefficients in the Kronecker product \({s_{(n-p,p)} \ast s_\lambda}\). Sém. Lothar. Combin. 54A, Art. B54Af, 29 pp. (electronic). ISSN 1286-4889.

  • Alexander Barvinok (2008). Integer points in polyhedra. Zurich Lectures in Advanced Mathematics. European Mathematical Society (EMS), Zürich. ISBN 978-3-03719-052-4, viii+191. URL http://dx.doi.org/10.4171/052.

  • Alexander Barvinok & James E. Pommersheim (1999). An algorithmic theory of lattice points in polyhedra. In New perspectives in algebraic combinatorics (Berkeley, CA, 1996–97), volume 38 of Math. Sci. Res. Inst. Publ., 91–147. Cambridge Univ. Press, Cambridge.

  • Georgia Benkart, Frank Sottile & Jeffrey Stroomer (1996). Tableau switching: algorithms and applications. J. Combin. Theory Ser. A 76(1), 11–43. ISSN 0097-3165. URL http://dx.doi.org/10.1006/jcta.1996.0086.

  • J. Blasiak (2012). Kronecker coefficients for one hook shape. arXiv:1209.2018.

  • Emmanuel Briand, Rosa Orellana & Mercedes Rosas (2009). Reduced Kronecker coefficients and counter-examples to Mulmuley’s strong saturation conjecture SH. Comput. Complexity 18(4), 577–600. ISSN 1016-3328. URL http://dx.doi.org/10.1007/s00037-009-0279-z. With an appendix by Ketan Mulmuley.

  • Emmanuel Briand, Rosa Orellana & Mercedes Rosas (2011). The stability of the Kronecker product of Schur functions. J. Algebra 331, 11–27. ISSN 0021-8693. URL http://dx.doi.org/10.1016/j.jalgebra.2010.12.026.

  • Michel Brion (1993). Stable properties of plethysm: on two conjectures of Foulkes. Manuscripta Math. 80(4), 347–371. ISSN 0025-2611. URL http://dx.doi.org/10.1007/BF03026558.

  • P. Bürgisser (2009). Review of “Geometric Complexity theory II” (K. D. Mulmuley and M. Sohoni), MR2421083 (2009j:68067) .

  • Peter Bürgisser, Michael Clausen & M. Amin Shokrollahi (1997). Algebraic complexity theory, volume 315 of Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]. Springer-Verlag, Berlin. ISBN 3-540-60582-7, xxiv+618. URL http://dx.doi.org/10.1007/978-3-662-03338-8. With the collaboration of Thomas Lickteig.

  • Peter Bürgisser & Christian Ikenmeyer (2008). The complexity of computing Kronecker coefficients. In 20th Annual International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2008), Discrete Math. Theor. Comput. Sci. Proc., AJ, 357–368. Assoc. Discrete Math. Theor. Comput. Sci., Nancy.

  • Peter Bürgisser & Christian Ikenmeyer (2013). Deciding positivity of Littlewood-Richardson coefficients. SIAM J. Discrete Math. 27(4), 1639–1681. ISSN 0895-4801. URL http://dx.doi.org/10.1137/120892532.

  • M. De Visscher C. Bowman & R. Orellana (2015). The partition algebra and the Kronecker coefficients. Trans. Am. Math. Soc. 367, 3647–3667.

  • Matthias Christandl, Brent Doran & Michael Walter (2012). Computing multiplicities of Lie group representations. In 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science—FOCS 2012, 639–648. IEEE Computer Soc., Los Alamitos, CA.

  • Matthias Christandl, Aram W. Harrow & Graeme Mitchison (2007). Nonzero Kronecker coefficients and what they tell us about spectra. Comm. Math. Phys. 270(3), 575–585. ISSN 0010-3616. URL http://dx.doi.org/10.1007/s00220-006-0157-3.

  • Jesus De Loera & Shmuel Onn (2004). The complexity of three-way statistical tables. SIAM J. Comput. 33(4), 819–836 (electronic). ISSN 0097-5397. URL http://dx.doi.org/10.1137/S0097539702403803.

  • Jesús A. De Loera, Raymond Hemmecke, Jeremiah Tauzer & Ruriko Yoshida (2004). Effective lattice point counting in rational convex polytopes. J. Symbolic Comput. 38(4), 1273–1302. ISSN 0747-7171. URL http://dx.doi.org/10.1016/j.jsc.2003.04.003.

  • Jesús A. De Loera & Tyrrell B. McAllister (2006). On the computation of Clebsch-Gordan coefficients and the dilation effect. Experiment. Math. 15(1), 7–19. ISSN 1058-6458. URL http://projecteuclid.org/euclid.em/1150476899.

  • Persi Diaconis & Anil Gangolli (1995). Rectangular arrays with fixed margins. In Discrete probability and algorithms (Minneapolis, MN, 1993), volume 72 of IMA Vol. Math. Appl., 15–41. Springer, New York. URL http://dx.doi.org/10.1007/978-1-4612-0801-3_3.

  • Yoav Dvir (1993). On the Kronecker product of S n characters. J. Algebra 154(1), 125–140. ISSN 0021-8693. URL http://dx.doi.org/10.1006/jabr.1993.1008.

  • Martin Dyer & Ravi Kannan (1997). On Barvinok’s algorithm for counting lattice points in fixed dimension. Math. Oper. Res. 22(3), 545–549. ISSN 0364-765X. URL http://dx.doi.org/10.1287/moor.22.3.545.

  • Friedrich Eisenbrand (2003). Fast integer programming in fixed dimension. In Algorithms—ESA 2003, volume 2832 of Lecture Notes in Comput. Sci., 196–207. Springer, Berlin. URL http://dx.doi.org/10.1007/978-3-540-39658-1_20.

  • Fortnow L. (2009) The Status of the P Versus NP Problem. Comm. ACM 52(9): 78–86

    Article  Google Scholar 

  • Michael R. Garey & David S. Johnson (1979). Computers and intractability. W. H. Freeman and Co., San Francisco, Calif. ISBN 0-7167-1045-5, x+338. A guide to the theory of NP-completeness, A Series of Books in the Mathematical Sciences.

  • C. T. Hepler (1994). On The Complexity of Computing Characters of Finite Groups. Master’s thesis, University of Calgary. Available at URL https://dspace.ucalgary.ca/handle/1880/45530.

  • C. Ikenmeyer (2012). Geometric Complexity Theory, Tensor Rank, and Littlewood-Richardson Coefficients. Ph.D. thesis, University of Paderborn. Available at URL http://bit.ly/SVIr0M.

  • Gordon James & Adalbert Kerber (1981). The representation theory of the symmetric group, volume 16 of Encyclopedia of Mathematics and its Applications. Addison-Wesley Publishing Co., Reading, Mass. ISBN 0-201-13515-9, xxviii+510. With a foreword by P. M. Cohn, With an introduction by Gilbert de B. Robinson.

  • Anatol N. Kirillov (2004). An invitation to the generalized saturation conjecture. Publ. Res. Inst. Math. Sci. 40(4), 1147–1239. ISSN 0034-5318. URL http://projecteuclid.org/euclid.prims/1145475445.

  • Michael Klemm (1977). Tensorprodukte von Charakteren der symmetrischen Gruppe. Arch. Math. (Basel) 28(5), 455–459. ISSN 0003-889X.

  • Allen Knutson & Terence Tao (1999). The honeycomb model of GL n (C) tensor products. I. Proof of the saturation conjecture. J. Amer. Math. Soc. 12(4), 1055–1090. ISSN 0894-0347. URL http://dx.doi.org/10.1090/S0894-0347-99-00299-4.

  • A. Lascoux (1980). Produit de Kronecker des représentations du groupe symétrique. In Séminaire d’Algèbre Paul Dubreil et Marie-Paule Malliavin, 32ème année (Paris, 1979), volume 795 of Lecture Notes in Math., 319–329. Springer, Berlin.

  • D. E. Littlewood (1956). The Kronecker product of symmetric group representations. J. London Math. Soc. 31, 89–93. ISSN 0024-6107.

  • D. E. Littlewood (1958). Products and plethysms of characters with orthogonal, symplectic and symmetric groups. Canad. J. Math. 10, 17–32. ISSN 0008-414X.

  • I. G. Macdonald (1995). Symmetric functions and Hall polynomials. Oxford Mathematical Monographs. The Clarendon Press, Oxford University Press, New York, 2nd edition. ISBN 0-19-853489-2, x+475. With contributions by A. Zelevinsky, Oxford Science Publications.

  • Laurent Manivel (2011). On rectangular Kronecker coefficients. J. Algebraic Combin. 33(1), 153–162. ISSN 0925-9899. URL http://dx.doi.org/10.1007/s10801-010-0240-x.

  • K. D. Mulmuley (2007). Geometric complexity theory VI: The flip via positivity. arXiv:0704.0229v4.

  • K. D. Mulmuley (2012). The GCT program toward the P vs. NP problem. Comm. ACM 55(6), 98–107.

  • Ketan D. Mulmuley, Hariharan Narayanan & Milind Sohoni (2012). Geometric complexity theory III: on deciding nonvanishing of a Littlewood-Richardson coefficient. J. Algebraic Combin. 36(1), 103–110. ISSN 0925-9899. URL http://dx.doi.org/10.1007/s10801-011-0325-1.

  • Ketan D. Mulmuley & Milind Sohoni (2008). Geometric complexity theory. II. Towards explicit obstructions for embeddings among class varieties. SIAM J. Comput. 38(3), 1175–1206. ISSN 0097-5397. URL http://dx.doi.org/10.1137/080718115.

  • F. D. Murnaghan (1938). The Analysis of the Direct Product of Irreducible Representations of the Symmetric Groups. Amer. J. Math. 60(1), 44–65. ISSN 0002-9327. URL http://dx.doi.org/10.2307/2371542.

  • Francis D. Murnaghan (1955). On the analysis of the Kronecker product of irreducible representations of S n . Proc. Nat. Acad. Sci. U.S.A. 41, 515–518. ISSN 0027-8424.

  • Francis D. Murnaghan (1956). On the Kronecker product of irreducible representations of the symmetric group. Proc. Nat. Acad. Sci. U.S.A. 42, 95–98. ISSN 0027-8424.

  • Hariharan Narayanan (2006). On the complexity of computing Kostka numbers and Littlewood-Richardson coefficients. J. Algebraic Combin. 24(3), 347–354. ISSN 0925-9899. URL http://dx.doi.org/10.1007/s10801-006-0008-5.

  • I. Pak & G. Panova (2015+). Combinatorics and complexity of Kronecker coefficients. in preparation.

  • I. Pak, G. Panova & E. Vallejo (2013). Kronecker products, characters, partitions, and the tensor square conjectures. Adv. Math. to appear. arXiv:1304.0738.

  • Igor Pak & Greta Panova (2014). Unimodality via Kronecker products. J. Algebraic Combin. 40(4), 1103–1120. ISSN 0925-9899. URL http://dx.doi.org/10.1007/s10801-014-0520-y.

  • Igor Pak & Ernesto Vallejo (2005). Combinatorics and geometry of Littlewood-Richardson cones. European J. Combin. 26(6), 995–1008. ISSN 0195-6698. URL http://dx.doi.org/10.1016/j.ejc.2004.06.008.

  • Igor Pak & Ernesto Vallejo (2010). Reductions of Young tableau bijections. SIAM J. Discrete Math. 24(1), 113–145. ISSN 0895-4801. URL http://dx.doi.org/10.1137/070689784.

  • Christos H. Papadimitriou (1994). Computational complexity. Addison-Wesley Publishing Company, Reading, MA. ISBN 0-201-53082-1, xvi+523.

  • Amitai Regev (2014). Kronecker multiplicities in the \({(k,\ell)}\) hook are polynomially bounded. Israel J. Math. 200(1), 39–48. ISSN 0021-2172. URL http://dx.doi.org/10.1007/s11856-014-0005-7.

  • Jeffrey B. Remmel (1989). A formula for the Kronecker products of Schur functions of hook shapes. J. Algebra 120(1), 100–118. ISSN 0021-8693. URL http://dx.doi.org/10.1016/0021-8693(89)90191-9.

  • Mercedes H. Rosas (2001). The Kronecker product of Schur functions indexed by two-row shapes or hook shapes. J. Algebraic Combin. 14(2), 153–173. ISSN 0925-9899. URL http://dx.doi.org/10.1023/A:1011942029902.

  • Bruce E. Sagan (2001). The symmetric group, volume 203 of Graduate Texts in Mathematics. Springer-Verlag, New York, 2nd edition. ISBN 0-387-95067-2, xvi+238. URL http://dx.doi.org/10.1007/978-1-4757-6804-6. Representations, combinatorial algorithms, and symmetric functions.

  • Alexander Schrijver (1986). Theory of linear and integer programming. Wiley-Interscience Series in Discrete Mathematics. John Wiley & Sons, Ltd., Chichester. ISBN 0-471-90854-1, xii+471. A Wiley-Interscience Publication.

  • Richard P. Stanley (1999). Enumerative combinatorics. Vol. 2, volume 62 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge. ISBN 0-521-56069-1; 0-521-78987-7, xii+581. URL http://dx.doi.org/10.1017/CBO9780511609589. With a foreword by Gian-Carlo Rota and appendix 1 by Sergey Fomin.

  • Ernesto Vallejo (1999). Stability of Kronecker products of irreducible characters of the symmetric group. Electron. J. Combin. 6, Research Paper 39, 7 pp. (electronic). ISSN 1077-8926. URL http://www.combinatorics.org/Volume_6/Abstracts/v6i1r39.html.

  • Vijay V. Vazirani (2001). Approximation algorithms. Springer-Verlag, Berlin. ISBN 3-540-65367-8, xx+378.

  • Andrei Zelevinsky (1999). Littlewood-Richardson semigroups. In New perspectives in algebraic combinatorics (Berkeley, CA, 1996–97), volume 38 of Math. Sci. Res. Inst. Publ., 337–345. Cambridge Univ. Press, Cambridge.

Download references

Author information

Authors and Affiliations

  1. Mathematics Department, UCLA, Los Angeles, CA, 90095, USA

    Igor Pak

  2. Mathematics Department, University of Pennsylvania, Philadelphia, PA, 19104, USA

    Greta Panova

Authors
  1. Igor Pak
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Greta Panova
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Greta Panova.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Pak, I., Panova, G. On the complexity of computing Kronecker coefficients. comput. complex. 26, 1–36 (2017). https://doi.org/10.1007/s00037-015-0109-4

Download citation

  • Received:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00037-015-0109-4

Keywords

Subject Classification

Search

Navigation