AMS eBook CollectionsOne of the world's most respected mathematical collections, available in digital format for your library or institution
Geometric Complexity Theory IV: nonstandard quantum group for the Kronecker problem
About this Title
Jonah Blasiak, Department of Mathematics, Drexel University, Philadelphia, PA 19104, Ketan D. Mulmuley, The University of Chicago and Milind Sohoni, I.I.T., Mumbai
Publication: Memoirs of the American Mathematical Society
Publication Year:
2015; Volume 235, Number 1109
ISBNs: 978-1-4704-1011-7 (print); 978-1-4704-2227-1 (online)
DOI: https://doi.org/10.1090/memo/1109
Published electronically: October 24, 2014
Keywords: Kronecker problem,
complexity theory,
canonical basis,
quantum group,
Hecke algebra,
graphical calculus
MSC: Primary 33D80, 20C30, 05E10.; Secondary 16S80, 11Y16
Table of Contents
Chapters
- 1. Introduction
- 2. Basic concepts and notation
- 3. Hecke algebras and canonical bases
- 4. The quantum group $GL_q(V)$
- 5. Bases for $GL_q(V)$ modules
- 6. Quantum Schur-Weyl duality and canonical bases
- 7. Notation for $GL_q(V) \times GL_q(W)$
- 8. The nonstandard coordinate algebra $\mathscr {O}(M_q(\check {X}))$
- 9. Nonstandard determinant and minors
- 10. The nonstandard quantum groups $GL_q(\check {X})$ and $\texttt {U}_q(\check {X})$
- 11. The nonstandard Hecke algebra $\check {\mathscr {H}}_r$
- 12. Nonstandard Schur-Weyl duality
- 13. Nonstandard representation theory in the two-row case
- 14. A canonical basis for $\check {Y}_\alpha$
- 15. A global crystal basis for two-row Kronecker coefficients
- 16. Straightened NST and semistandard tableaux
- 17. A Kronecker graphical calculus and applications
- 18. Explicit formulae for Kronecker coefficients
- 19. Future work
- A. Reduction system for ${\mathscr {O}}(M_q(\check {X}))$
- B. The Hopf algebra ${\mathscr {O}}_{q}^\tau$
Abstract
The Kronecker coefficient $g_{\lambda \mu \nu }$ is the multiplicity of the $GL(V)\times GL(W)$-irreducible $V_\lambda \otimes W_\mu$ in the restriction of the $GL(X)$-irreducible $X_\nu$ via the natural map $GL(V)\times GL(W) \to GL(V \otimes W)$, where $V, W$ are $\mathbb {C}$-vector spaces and $X = V \otimes W$. A fundamental open problem in algebraic combinatorics is to find a positive combinatorial formula for these coefficients.
We construct two quantum objects for this problem, which we call the nonstandard quantum group and nonstandard Hecke algebra. We show that the nonstandard quantum group has a compact real form and its representations are completely reducible, that the nonstandard Hecke algebra is semisimple, and that they satisfy an analog of quantum Schur-Weyl duality.
Using these nonstandard objects as a guide, we follow the approach of Adsul, Sohoni, and Subrahmanyam to construct, in the case $\dim (V) = \dim (W) = 2$, a representation $\check {X}_\nu$ of the nonstandard quantum group that specializes to $\operatorname {Res}_{GL(V) \times GL(W)} X_\nu$ at $q=1$. We then define a global crystal basis $+\mathrm {HNSTC}(\nu )$ of $\check {X}_\nu$ that solves the two-row Kronecker problem: the number of highest weight elements of $+\mathrm {HNSTC}(\nu )$ of weight $(\lambda ,\mu )$ is the Kronecker coefficient $g_{\lambda \mu \nu }$. We go on to develop the beginnings of a graphical calculus for this basis, along the lines of the $U_q(\mathfrak {sl}_2)$ graphical calculus and use this to organize the crystal components of $+\mathrm {HNSTC}(\nu )$ into eight families. This yields a fairly simple, positive formula for two-row Kronecker coefficients, generalizing a formula of Brown, Willigenburg, and Zabrocki. As a byproduct of the approach, we also obtain a rule for the decomposition of $\operatorname {Res}_{GL_2 \times GL_2 \rtimes {\mathcal {S}}_2} X_\nu$ into irreducibles.
- B. Adsul, M. Sohoni, and K. V. Subrahmanyam. Quantum deformations of the restriction of $GL_{mn}(\mathbb {C})$-modules to $GL_{m}(\mathbb {C})\times GL_{n}(\mathbb {C})$. ArXiv e-prints, October 2010. arXiv:0905.0094v2.
- Bharat Adsul and K. V. Subrahmanyam, A geometric approach to the Kronecker problem. I. The two row case, Proc. Indian Acad. Sci. Math. Sci. 118 (2008), no. 2, 213–226. MR 2423234, DOI 10.1007/s12044-008-0014-8
- Kaan Akin, David A. Buchsbaum, and Jerzy Weyman, Schur functors and Schur complexes, Adv. in Math. 44 (1982), no. 3, 207–278. MR 658729, DOI 10.1016/0001-8708(82)90039-1
- Michael Artin, William Schelter, and John Tate, Quantum deformations of $\textrm {GL}_n$, Comm. Pure Appl. Math. 44 (1991), no. 8-9, 879–895. MR 1127037, DOI 10.1002/cpa.3160440804
- Sami H. Assaf. Dual Equivalence Graphs I: A combinatorial proof of LLT and Macdonald positivity. ArXiv e-prints, May 2010. arXiv:1005.3759.
- C. M. Ballantine and R. C. Orellana, On the Kronecker product $s_{(n-p,p)}\ast s_\lambda$, Electron. J. Combin. 12 (2005), Research Paper 28, 26. MR 2156682
- Arkady Berenstein and Sebastian Zwicknagl, Braided symmetric and exterior algebras, Trans. Amer. Math. Soc. 360 (2008), no. 7, 3429–3472. MR 2386232, DOI 10.1090/S0002-9947-08-04373-0
- Jonah Blasiak. Nonstandard braid relations and Chebyshev polynomials. ArXiv e-prints, October 2010. arXiv:1010.0421.
- Jonah Blasiak, Quantum Schur-Weyl duality and projected canonical bases, J. Algebra 402 (2014), 499–532. MR 3160433, DOI 10.1016/j.jalgebra.2013.12.010
- Jonah Blasiak, $W$-graph versions of tensoring with the $\scr S_n$ defining representation, J. Algebraic Combin. 34 (2011), no. 4, 545–585. MR 2842910, DOI 10.1007/s10801-011-0281-9
- Jonah Blasiak. Representation theory of the nonstandard Hecke algebra. ArXiv e-prints, February 2012. arXiv:1201.2209v2.
- Sergey Bravyi, Requirements for compatibility between local and multipartite quantum states, Quantum Inf. Comput. 4 (2004), no. 1, 12–26. MR 2045769
- Emmanuel Briand, Rosa Orellana, and Mercedes Rosas, Quasipolynomial formulas for the Kronecker coefficients indexed by two two-row shapes (extended abstract), 21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009), Discrete Math. Theor. Comput. Sci. Proc., AK, Assoc. Discrete Math. Theor. Comput. Sci., Nancy, 2009, pp. 241–252. MR 2721516
- Emmanuel Briand, Rosa Orellana, and Mercedes Rosas, Reduced Kronecker coefficients and counter-examples to Mulmuley’s strong saturation conjecture SH, Comput. Complexity 18 (2009), no. 4, 577–600. With an appendix by Ketan Mulmuley. MR 2570451, DOI 10.1007/s00037-009-0279-z
- Andrew A. H. Brown, Stephanie van Willigenburg, and Mike Zabrocki, Expressions for Catalan Kronecker products, Pacific J. Math. 248 (2010), no. 1, 31–48. MR 2734163, DOI 10.2140/pjm.2010.248.31
- Jonathan Brundan, Dual canonical bases and Kazhdan-Lusztig polynomials, J. Algebra 306 (2006), no. 1, 17–46. MR 2271570, DOI 10.1016/j.jalgebra.2006.01.053
- Peter Buergisser and Christian Ikenmeyer. Geometric Complexity Theory and Tensor Rank. ArXiv e-prints, November 2010. arXiv:1011.1350.
- Charles W. Curtis and Irving Reiner, Methods of representation theory. Vol. I, John Wiley & Sons, Inc., New York, 1981. With applications to finite groups and orders; Pure and Applied Mathematics; A Wiley-Interscience Publication. MR 632548
- Igor B. Frenkel and Mikhail G. Khovanov, Canonical bases in tensor products and graphical calculus for $U_q({\mathfrak {s}}{\mathfrak {l}}_2)$, Duke Math. J. 87 (1997), no. 3, 409–480. MR 1446615, DOI 10.1215/S0012-7094-97-08715-9
- William Fulton and Joe Harris, Representation theory, Graduate Texts in Mathematics, vol. 129, Springer-Verlag, New York, 1991. A first course; Readings in Mathematics. MR 1153249
- J. J. Graham and G. I. Lehrer, Cellular algebras, Invent. Math. 123 (1996), no. 1, 1–34. MR 1376244, DOI 10.1007/BF01232365
- I. Grojnowski and G. Lusztig, On bases of irreducible representations of quantum $\textrm {GL}_n$, Kazhdan-Lusztig theory and related topics (Chicago, IL, 1989) Contemp. Math., vol. 139, Amer. Math. Soc., Providence, RI, 1992, pp. 167–174. MR 1197834, DOI 10.1090/conm/139/1197834
- Takahiro Hayashi, Nonexistence of homomorphisms between quantum groups, Tokyo J. Math. 15 (1992), no. 2, 431–435. MR 1197109, DOI 10.3836/tjm/1270129467
- Jin Hong and Seok-Jin Kang, Introduction to quantum groups and crystal bases, Graduate Studies in Mathematics, vol. 42, American Mathematical Society, Providence, RI, 2002. MR 1881971
- Michio Jimbo, A $q$-analogue of $U({\mathfrak {g}}{\mathfrak {l}}(N+1))$, Hecke algebra, and the Yang-Baxter equation, Lett. Math. Phys. 11 (1986), no. 3, 247–252. MR 841713, DOI 10.1007/BF00400222
- M. Kashiwara, On crystal bases of the $Q$-analogue of universal enveloping algebras, Duke Math. J. 63 (1991), no. 2, 465–516. MR 1115118, DOI 10.1215/S0012-7094-91-06321-0
- Masaki Kashiwara, Global crystal bases of quantum groups, Duke Math. J. 69 (1993), no. 2, 455–485. MR 1203234, DOI 10.1215/S0012-7094-93-06920-7
- David Kazhdan and George Lusztig, Representations of Coxeter groups and Hecke algebras, Invent. Math. 53 (1979), no. 2, 165–184. MR 560412, DOI 10.1007/BF01390031
- Apoorva Khare, Functoriality of the BGG category $\scr O$, Comm. Algebra 37 (2009), no. 12, 4431–4475. MR 2588860, DOI 10.1080/00927870902829098
- Anatoli Klimyk and Konrad Schmüdgen, Quantum groups and their representations, Texts and Monographs in Physics, Springer-Verlag, Berlin, 1997. MR 1492989
- J. M. Landsberg, Tensors: geometry and applications, Graduate Studies in Mathematics, vol. 128, American Mathematical Society, Providence, RI, 2012. MR 2865915
- Joseph M. Landsberg and Laurent Manivel. On the ideals of secant varieties of Segre varieties. Found. Comput. Math., 4(4):397–422, 2004.
- Michael J. Larsen and Eric C. Rowell, An algebra-level version of a link-polynomial identity of Lickorish, Math. Proc. Cambridge Philos. Soc. 144 (2008), no. 3, 623–638. MR 2418707, DOI 10.1017/S0305004107000424
- A. Lascoux, Produit de Kronecker des représentations du groupe symétrique, Séminaire d’Algèbre Paul Dubreil et Marie-Paule Malliavin, 32ème année (Paris, 1979) Lecture Notes in Math., vol. 795, Springer, Berlin, 1980, pp. 319–329 (French). MR 582085
- George Lusztig, Introduction to quantum groups, Progress in Mathematics, vol. 110, Birkhäuser Boston, Inc., Boston, MA, 1993. MR 1227098
- I. G. Macdonald, Symmetric functions and Hall polynomials, 2nd ed., Oxford Mathematical Monographs, The Clarendon Press, Oxford University Press, New York, 1995. With contributions by A. Zelevinsky; Oxford Science Publications. MR 1354144
- Yu. I. Manin, Quantum groups and noncommutative geometry, Université de Montréal, Centre de Recherches Mathématiques, Montreal, QC, 1988. MR 1016381
- Andrew Mathas, Iwahori-Hecke algebras and Schur algebras of the symmetric group, University Lecture Series, vol. 15, American Mathematical Society, Providence, RI, 1999. MR 1711316
- Susan Montgomery, Hopf algebras and their actions on rings, CBMS Regional Conference Series in Mathematics, vol. 82, Published for the Conference Board of the Mathematical Sciences, Washington, DC; by the American Mathematical Society, Providence, RI, 1993. MR 1243637
- K. Mulmuley. Geometric complexity theory VIII: On canonical bases for the nonstandard quantum groups. Technical Report TR 2007-15, Computer Science Department, The University of Chicago, 2007.
- Ketan Mulmuley. Geometric complexity theory VII: Nonstandard quantum group for the plethysm problem. CoRR, abs/0709.0749, 2007.
- Ketan Mulmuley. Explicit Proofs and The Flip. ArXiv e-prints, September 2010. arXiv:1009.0246.
- Ketan Mulmuley. Geometric complexity theory VI: The flip via positivity. Technical report, The Computer Science Department, The University of Chicago, January 2011.
- Ketan Mulmuley and Milind A. Sohoni. Geometric complexity III: on deciding positivity of Littlewood-Richardson coefficients. CoRR, abs/cs/0501076, 2005.
- Ketan Mulmuley and Milind A. Sohoni. Geometric complexity theory IV: Quantum group for the Kronecker problem. CoRR, abs/cs/0703110, 2007.
- Ketan D. Mulmuley, On P vs. NP and geometric complexity theory, J. ACM 58 (2011), no. 2, Art. 5, 26. MR 2786586, DOI 10.1145/1944345.1944346
- Ketan D. Mulmuley and Milind Sohoni, Geometric complexity theory. I. An approach to the P vs. NP and related problems, SIAM J. Comput. 31 (2001), no. 2, 496–526. MR 1861288, DOI 10.1137/S009753970038715X
- Ketan D. Mulmuley and Milind Sohoni, Geometric complexity theory. II. Towards explicit obstructions for embeddings among class varieties, SIAM J. Comput. 38 (2008), no. 3, 1175–1206. MR 2421083, DOI 10.1137/080718115
- Masatoshi Noumi, Hirofumi Yamada, and Katsuhisa Mimachi, Finite-dimensional representations of the quantum group $\textrm {GL}_q(n;\textbf {C})$ and the zonal spherical functions on $\textrm {U}_q(n-1)\backslash \textrm {U}_q(n)$, Japan. J. Math. (N.S.) 19 (1993), no. 1, 31–80. MR 1231510, DOI 10.4099/math1924.19.31
- Arun Ram, A Frobenius formula for the characters of the Hecke algebras, Invent. Math. 106 (1991), no. 3, 461–488. MR 1134480, DOI 10.1007/BF01243921
- Arun Ram, Seminormal representations of Weyl groups and Iwahori-Hecke algebras, Proc. London Math. Soc. (3) 75 (1997), no. 1, 99–133. MR 1444315, DOI 10.1112/S0024611597000282
- Jeffrey B. Remmel, A formula for the Kronecker products of Schur functions of hook shapes, J. Algebra 120 (1989), no. 1, 100–118. MR 977863, DOI 10.1016/0021-8693(89)90191-9
- Jeffrey B. Remmel and Tamsen Whitehead, On the Kronecker product of Schur functions of two row shapes, Bull. Belg. Math. Soc. Simon Stevin 1 (1994), no. 5, 649–683. MR 1315363
- N. Yu. Reshetikhin, L. A. Takhtadzhyan, and L. D. Faddeev, Quantization of Lie groups and Lie algebras, Algebra i Analiz 1 (1989), no. 1, 178–206 (Russian); English transl., Leningrad Math. J. 1 (1990), no. 1, 193–225. MR 1015339
- N. Reshetikhin, Multiparameter quantum groups and twisted quasitriangular Hopf algebras, Lett. Math. Phys. 20 (1990), no. 4, 331–335. MR 1077966, DOI 10.1007/BF00626530
- Mercedes H. Rosas, The Kronecker product of Schur functions indexed by two-row shapes or hook shapes, J. Algebraic Combin. 14 (2001), no. 2, 153–173. MR 1867232, DOI 10.1023/A:1011942029902
- Richard P. Stanley. Enumerative combinatorics. Vol. 2, volume 62 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 1999. With a foreword by Gian-Carlo Rota and appendix 1 by Sergey Fomin.
- Richard P. Stanley, Positivity problems and conjectures in algebraic combinatorics, Mathematics: frontiers and perspectives, Amer. Math. Soc., Providence, RI, 2000, pp. 295–319. MR 1754784
- A. Sudbery, Consistent multiparameter quantisation of $\textrm {GL}(n)$, J. Phys. A 23 (1990), no. 15, L697–L704. MR 1068228
- N. Ja. Vilenkin and A. U. Klimyk, Representation of Lie groups and special functions. Vol. 3, Mathematics and its Applications (Soviet Series), vol. 75, Kluwer Academic Publishers Group, Dordrecht, 1992. Classical and quantum groups and special functions; Translated from the Russian by V. A. Groza and A. A. Groza. MR 1206906
- Jerzy Weyman, Cohomology of vector bundles and syzygies, Cambridge Tracts in Mathematics, vol. 149, Cambridge University Press, Cambridge, 2003. MR 1988690
- S. L. Woronowicz, Compact matrix pseudogroups, Comm. Math. Phys. 111 (1987), no. 4, 613–665. MR 901157
- Sebastian Zwicknagl, Braided symmetric algebras of simple $U_q(sl_2)$-modules and their geometry, J. Algebra 358 (2012), 215–233. MR 2905027, DOI 10.1016/j.jalgebra.2012.02.020