Permanent versus determinant: Not via saturations

Bürgisser, Peter; Ikenmeyer, Christian; Hüttenhain, Jesko

doi:10.1090/proc/13310

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