Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)



Permanent versus determinant: Not via saturations

Authors: Peter Bürgisser, Christian Ikenmeyer and Jesko Hüttenhain
Journal: Proc. Amer. Math. Soc. 145 (2017), 1247-1258
MSC (2010): Primary 68Q17, 14L24
Published electronically: November 28, 2016
MathSciNet review: 3589323
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Let $ \mathit {Det}_n$ denote the closure of the $ \mathrm {Gl}_{n^2}(\mathbb{C})$-orbit of the determinant polynomial $ \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 $ \mathit {Det}_n$ form a finitely generated monoid $ S(\mathit {Det}_n)$. We prove that the saturation of $ S(\mathit {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(\mathit {Det}_n)$.

References [Enhancements On Off] (What's this?)

  • [1] N. Alon and M. Tarsi, Colorings and orientations of graphs, Combinatorica 12 (1992), no. 2, 125-134. MR 1179249,
  • [2] 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.
  • [3] M. F. Atiyah and I. G. Macdonald, Introduction to commutative algebra, Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont., 1969. MR 0242802
  • [4] 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,
  • [5] 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,
  • [6] Michel Brion, Stable properties of plethysm: on two conjectures of Foulkes, Manuscripta Math. 80 (1993), no. 4, 347-371. MR 1243152,
  • [7] Peter Bürgisser, Completeness and reduction in algebraic complexity theory, Algorithms and Computation in Mathematics, vol. 7, Springer-Verlag, Berlin, 2000. MR 1771845
  • [8] Peter Bürgisser, Matthias Christandl, and Christian Ikenmeyer, Even partitions in plethysms, J. Algebra 328 (2011), 322-329. MR 2745569,
  • [9] 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,
  • [10] Peter Bürgisser, J. M. Landsberg, Laurent Manivel, and Jerzy Weyman, An overview of mathematical issues arising in the geometric complexity theory approach to $ {\rm VP}\neq {\rm VNP}$, SIAM J. Comput. 40 (2011), no. 4, 1179-1209. MR 2861717,
  • [11] 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
  • [12] Igor Dolgachev, Lectures on invariant theory, London Mathematical Society Lecture Note Series, vol. 296, Cambridge University Press, Cambridge, 2003. MR 2004511
  • [13] Arthur A. Drisko, Proof of the Alon-Tarsi conjecture for $ n=2^rp$, Electron. J. Combin. 5 (1998), Research paper 28, 5 pp. (electronic). MR 1624999
  • [14] 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
  • [15] I. M. Gelfand, M. M. Kapranov, and A. V. Zelevinsky, Discriminants, resultants, and multidimensional determinants, Mathematics: Theory & Applications, Birkhäuser Boston, Inc., Boston, MA, 1994. MR 1264417
  • [16] 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,
  • [17] Bruno Grenet, An upper bound for the permanent versus determinant problem, Accepted for Theory of Computing, 2011.
  • [18] James E. Humphreys, Linear algebraic groups, Springer-Verlag, New York-Heidelberg, 1975. Graduate Texts in Mathematics, No. 21. MR 0396773
  • [19] Christian Ikenmeyer, Geometric Complexity Theory, Tensor Rank, and Littlewood-Richardson Coefficients, PhD thesis, Institute of Mathematics, University of Paderborn, 2012.
  • [20] Jesko Hüttenhain and Christian Ikenmeyer, Binary determinantal complexity, Linear Algebra Appl. 504 (2016), 559-573. MR 3502551,
  • [21] Harlan Kadish and J. M. Landsberg, Padded polynomials, their cousins, and geometric complexity theory, Comm. Algebra 42 (2014), no. 5, 2171-2180. MR 3169697,
  • [22] Hanspeter Kraft, Geometrische Methoden in der Invariantentheorie, Aspects of Mathematics, D1, Friedr. Vieweg & Sohn, Braunschweig, 1984 (German). MR 768181
  • [23] 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,
  • [24] 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,
  • [25] Guillaume Malod and Natacha Portier, Characterizing Valiant's algebraic complexity classes, J. Complexity 24 (2008), no. 1, 16-38. MR 2386928,
  • [26] Laurent Manivel and Mateusz Michałek, Secants of minuscule and cominuscule minimal orbits, Linear Algebra Appl. 481 (2015), 288-312. MR 3349658,
  • [27] Thierry Mignon and Nicolas Ressayre, A quadratic bound for the determinant and permanent problem, Int. Math. Res. Not. 79 (2004), 4241-4253. MR 2126826,
  • [28] Esra Miller and Bernd Sturmfels, Combinatorial Commutative Algebra, volume 227 of Graduate Texts in Mathematics, Springer, New York, 2004.
  • [29] 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,
  • [30] 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,
  • [31] 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.
  • [32] David Mumford, Algebraic geometry. I, Classics in Mathematics, Springer-Verlag, Berlin, 1995. Complex projective varieties; Reprint of the 1976 edition. MR 1344216
  • [33] 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,
  • [34] 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
  • [35] 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
  • [36] 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
  • [37] Akihiro Yabe, Bi-polynomial rank and determinantal complexity, arXiv:1504.00151v1

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2010): 68Q17, 14L24

Retrieve articles in all journals with MSC (2010): 68Q17, 14L24

Additional Information

Peter Bürgisser
Affiliation: Institute of Mathematics, Technische Universität, Berlin, Germany

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

Jesko Hüttenhain
Affiliation: Institute of Mathematics, Technische Universität, Berlin, Germany

Keywords: Geometric complexity theory, permanent versus determinant, representations, saturation of monoids
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
Article copyright: © Copyright 2016 American Mathematical Society

American Mathematical Society