Permanent versus determinant: Not via saturations
HTML articles powered by AMS MathViewer
- by Peter Bürgisser, Christian Ikenmeyer and Jesko Hüttenhain PDF
- Proc. Amer. Math. Soc. 145 (2017), 1247-1258 Request permission
Abstract:
Let $Det_n$ denote the closure of the $\mathrm {Gl}_{n^2}(\mathbb {C})$-orbit of the determinant polynomial $\mathrm {det}_n$ with respect to linear substitution. The highest weights (partitions) of irreducible $\mathrm {Gl}_{n^2}(\mathbb {C})$-representations occurring in the coordinate ring of $Det_n$ form a finitely generated monoid $S(Det_n)$. We prove that the saturation of $S(Det_n)$ contains all partitions $\lambda$ with length at most $n$ and size divisible by $n$. This implies that representation theoretic obstructions for the permanent versus determinant problem must be holes of the monoid $S(Det_n)$.References
- N. Alon and M. Tarsi, Colorings and orientations of graphs, Combinatorica 12 (1992), no. 2, 125–134. MR 1179249, DOI 10.1007/BF01204715
- Jarod Alper, Tristram Bogart, and Mauricio Velasco, A lower bound for the determinantal complexity of a hypersurface, To appear in Foundations of Computational Mathematics, 2015.
- M. F. Atiyah and I. G. Macdonald, Introduction to commutative algebra, Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont., 1969. MR 0242802
- 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
- Michel Brion, Sur l’image de l’application moment, Séminaire d’algèbre Paul Dubreil et Marie-Paule Malliavin (Paris, 1986) Lecture Notes in Math., vol. 1296, Springer, Berlin, 1987, pp. 177–192 (French). MR 932055, DOI 10.1007/BFb0078526
- Michel Brion, Stable properties of plethysm: on two conjectures of Foulkes, Manuscripta Math. 80 (1993), no. 4, 347–371. MR 1243152, DOI 10.1007/BF03026558
- Peter Bürgisser, Completeness and reduction in algebraic complexity theory, Algorithms and Computation in Mathematics, vol. 7, Springer-Verlag, Berlin, 2000. MR 1771845, DOI 10.1007/978-3-662-04179-6
- Peter Bürgisser, Matthias Christandl, and Christian Ikenmeyer, Even partitions in plethysms, J. Algebra 328 (2011), 322–329. MR 2745569, DOI 10.1016/j.jalgebra.2010.10.031
- Peter Bürgisser, Matthias Christandl, and Christian Ikenmeyer, Nonvanishing of Kronecker coefficients for rectangular shapes, Adv. Math. 227 (2011), no. 5, 2082–2091. MR 2803795, DOI 10.1016/j.aim.2011.04.012
- Peter Bürgisser, J. M. Landsberg, Laurent Manivel, and Jerzy Weyman, An overview of mathematical issues arising in the geometric complexity theory approach to $\textrm {VP}\neq \textrm {VNP}$, SIAM J. Comput. 40 (2011), no. 4, 1179–1209. MR 2861717, DOI 10.1137/090765328
- Harm Derksen and Gregor Kemper, Computational invariant theory, Invariant Theory and Algebraic Transformation Groups, I, Springer-Verlag, Berlin, 2002. Encyclopaedia of Mathematical Sciences, 130. MR 1918599, DOI 10.1007/978-3-662-04958-7
- Igor Dolgachev, Lectures on invariant theory, London Mathematical Society Lecture Note Series, vol. 296, Cambridge University Press, Cambridge, 2003. MR 2004511, DOI 10.1017/CBO9780511615436
- Arthur A. Drisko, Proof of the Alon-Tarsi conjecture for $n=2^rp$, Electron. J. Combin. 5 (1998), Research paper 28, 5. MR 1624999
- 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, DOI 10.1007/978-1-4612-0979-9
- I. M. Gel′fand, M. M. Kapranov, and A. V. Zelevinsky, Discriminants, resultants, and multidimensional determinants, Mathematics: Theory & Applications, Birkhäuser Boston, Inc., Boston, MA, 1994. MR 1264417, DOI 10.1007/978-0-8176-4771-1
- David G. Glynn, The conjectures of Alon-Tarsi and Rota in dimension prime minus one, SIAM J. Discrete Math. 24 (2010), no. 2, 394–399. MR 2646093, DOI 10.1137/090773751
- Bruno Grenet, An upper bound for the permanent versus determinant problem, Accepted for Theory of Computing, 2011.
- James E. Humphreys, Linear algebraic groups, Graduate Texts in Mathematics, No. 21, Springer-Verlag, New York-Heidelberg, 1975. MR 0396773, DOI 10.1007/978-1-4684-9443-3
- Christian Ikenmeyer, Geometric Complexity Theory, Tensor Rank, and Littlewood-Richardson Coefficients, PhD thesis, Institute of Mathematics, University of Paderborn, 2012.
- Jesko Hüttenhain and Christian Ikenmeyer, Binary determinantal complexity, Linear Algebra Appl. 504 (2016), 559–573. MR 3502551, DOI 10.1016/j.laa.2016.04.027
- Harlan Kadish and J. M. Landsberg, Padded polynomials, their cousins, and geometric complexity theory, Comm. Algebra 42 (2014), no. 5, 2171–2180. MR 3169697, DOI 10.1080/00927872.2012.758268
- Hanspeter Kraft, Geometrische Methoden in der Invariantentheorie, Aspects of Mathematics, D1, Friedr. Vieweg & Sohn, Braunschweig, 1984 (German). MR 768181, DOI 10.1007/978-3-322-83813-1
- Shrawan Kumar, A study of the representations supported by the orbit closure of the determinant, Compos. Math. 151 (2015), no. 2, 292–312. MR 3314828, DOI 10.1112/S0010437X14007660
- J. M. Landsberg, Geometric complexity theory: an introduction for geometers, Ann. Univ. Ferrara Sez. VII Sci. Mat. 61 (2015), no. 1, 65–117. MR 3343444, DOI 10.1007/s11565-014-0202-7
- Guillaume Malod and Natacha Portier, Characterizing Valiant’s algebraic complexity classes, J. Complexity 24 (2008), no. 1, 16–38. MR 2386928, DOI 10.1016/j.jco.2006.09.006
- Laurent Manivel and Mateusz Michałek, Secants of minuscule and cominuscule minimal orbits, Linear Algebra Appl. 481 (2015), 288–312. MR 3349658, DOI 10.1016/j.laa.2015.04.027
- Thierry Mignon and Nicolas Ressayre, A quadratic bound for the determinant and permanent problem, Int. Math. Res. Not. 79 (2004), 4241–4253. MR 2126826, DOI 10.1155/S1073792804142566
- Esra Miller and Bernd Sturmfels, Combinatorial Commutative Algebra, volume 227 of Graduate Texts in Mathematics, Springer, New York, 2004.
- 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
- Ketan D. Mulmuley, Geometric complexity theory VI: the flip via saturated and positive integer programming in representation theory and algebraic geometry, Technical Report TR-2007-04, Computer Science Department, The University of Chicago.
- David Mumford, Algebraic geometry. I, Classics in Mathematics, Springer-Verlag, Berlin, 1995. Complex projective varieties; Reprint of the 1976 edition. MR 1344216
- Igor Pak and Greta Panova, Strict unimodality of $q$-binomial coefficients, C. R. Math. Acad. Sci. Paris 351 (2013), no. 11-12, 415–418 (English, with English and French summaries). MR 3090120, DOI 10.1016/j.crma.2013.06.008
- Igor R. Shafarevich, Basic algebraic geometry. 1, 2nd ed., Springer-Verlag, Berlin, 1994. Varieties in projective space; Translated from the 1988 Russian edition and with notes by Miles Reid. MR 1328833
- L. G. Valiant, Completeness classes in algebra, Conference Record of the Eleventh Annual ACM Symposium on Theory of Computing (Atlanta, Ga., 1979) ACM, New York, 1979, pp. 249–261. MR 564634
- L. G. Valiant, Reducibility by algebraic projections, Logic and algorithmic (Zurich, 1980) Monograph. Enseign. Math., vol. 30, Univ. Genève, Geneva, 1982, pp. 365–380. MR 648313
- Akihiro Yabe, Bi-polynomial rank and determinantal complexity, arXiv:1504.00151v1
Additional Information
- Peter Bürgisser
- Affiliation: Institute of Mathematics, Technische Universität, Berlin, Germany
- MR Author ID: 316251
- Email: pbuerg@math.tu-berlin.de
- Christian Ikenmeyer
- Affiliation: Department of Mathematics, Texas A&M University, College Station, Texas 75429
- Address at time of publication: Max Planck Institute for Informatics, Saarland Informatics Campus, Germany
- MR Author ID: 911976
- Jesko Hüttenhain
- Affiliation: Institute of Mathematics, Technische Universität, Berlin, Germany
- Email: jesko@math.tu-berlin.de
- Received by editor(s): July 9, 2015
- Published electronically: November 28, 2016
- Additional Notes: The first and third author were partially supported by DFG grant BU 1371/3-2
This research was conducted while the second author was at Texas A&M University. - Communicated by: Harm Derksen
- © Copyright 2016 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 145 (2017), 1247-1258
- MSC (2010): Primary 68Q17, 14L24
- DOI: https://doi.org/10.1090/proc/13310
- MathSciNet review: 3589323