Bernstein-Gelfand-Gelfand meets geometric complexity theory: resolving the 2×2 permanents of a 2×𝐧 matrix

Gesmundo, Fulvio; Huang, Hang; Schenck, Hal; Weyman, Jerzy

doi:10.1090/tran/9376

Bernstein-Gelfand-Gelfand meets geometric complexity theory: resolving the $\mathbf {2 \times 2}$ permanents of a $\mathbf {2 \times n}$ matrix
HTML articles powered by AMS MathViewer

by Fulvio Gesmundo, Hang (Amy) Huang, Hal Schenck and Jerzy Weyman;

Trans. Amer. Math. Soc. 378 (2025), 3573-3596

DOI: https://doi.org/10.1090/tran/9376

Published electronically: January 22, 2025

HTML | PDF | Request permission

Abstract:

We describe the minimal free resolution of the ideal of $2 \times 2$ subpermanents of a $2 \times n$ generic matrix $M$. In contrast to the case of $2 \times 2$ determinants, the $2 \times 2$ permanents define an ideal which is neither prime nor Cohen-Macaulay. We combine work of Laubenbacher-Swanson [J. Symbolic Comput. 30 (2000), pp. 195–205] on the Gröbner basis of an ideal of $2 \times 2$ permanents of a generic matrix with our previous work of Efremenko et al. [J. Algebra 503 (2018), pp. 8–20] connecting the initial ideal of $2 \times 2$ permanents to a simplicial complex. The main technical tool is a spectral sequence arising from the Bernstein-Gelfand-Gelfand correspondence.

References

N. Alon and M. Tarsi, Colorings and orientations of graphs, Combinatorica 12 (1992), no. 2, 125–134. \PrintDOI{10.1007/BF01204715}
Dave Bayer, Hara Charalambous, and Sorin Popescu, Extremal Betti numbers and applications to monomial ideals, J. Algebra 221 (1999), no. 2, 497–512. MR 1726711, DOI 10.1006/jabr.1999.7970
Jarosław Buczyński, Adam Ginensky, and J. M. Landsberg, Determinantal equations for secant varieties and the Eisenbud-Koh-Stillman conjecture, J. Lond. Math. Soc. (2) 88 (2013), no. 1, 1–24. MR 3092255, DOI 10.1112/jlms/jds073
Peter Bürgisser, Christian Ikenmeyer, and Greta Panova, No occurrence obstructions in geometric complexity theory, J. Amer. Math. Soc. 32 (2019), no. 1, 163–193. MR 3868002, DOI 10.1090/jams/908
P. Bürgisser, J. M. Landsberg, L. Manivel, and J. Weyman, An overview of mathematical issues arising in the Geometric Complexity Theory approach to $VP \neq VNP$, SIAM J. Comput. 40 (2011), no. 4, 1179–1209. \PrintDOI{10.1137/090765328}
Mats Boij and Zach Teitler, A bound for the Waring rank of the determinant via syzygies, Linear Algebra Appl. 587 (2020), 195–214. MR 4031710, DOI 10.1016/j.laa.2019.11.007
David Eisenbud and Joe Harris, The geometry of schemes, Graduate Texts in Mathematics, vol. 197, Springer-Verlag, New York, 2000. MR 1730819
D. Eisenbud, Linear sections of determinantal varieties, Amer. J. Math. 110 (1988), no. 3, 541–575. \PrintDOI{10.2307/2374622}
David Eisenbud, Commutative algebra, Graduate Texts in Mathematics, vol. 150, Springer-Verlag, New York, 1995. With a view toward algebraic geometry. MR 1322960, DOI 10.1007/978-1-4612-5350-1
David Eisenbud, The geometry of syzygies, Graduate Texts in Mathematics, vol. 229, Springer-Verlag, New York, 2005. A second course in commutative algebra and algebraic geometry. MR 2103875
Klim Efremenko, J. M. Landsberg, Hal Schenck, and Jerzy Weyman, On minimal free resolutions of sub-permanents and other ideals arising in complexity theory, J. Algebra 503 (2018), 8–20. MR 3779986, DOI 10.1016/j.jalgebra.2018.01.021
J. A. Eagon and D. G. Northcott, Ideals defined by matrices and a certain complex associated with them, Proc. Roy. Soc. London Ser. A 269 (1962), 188–204. MR 142592, DOI 10.1098/rspa.1962.0170
John A. Eagon and Victor Reiner, Resolutions of Stanley-Reisner rings and Alexander duality, J. Pure Appl. Algebra 130 (1998), no. 3, 265–275. MR 1633767, DOI 10.1016/S0022-4049(97)00097-2
William Fulton, Young tableaux, London Mathematical Society Student Texts, vol. 35, Cambridge University Press, Cambridge, 1997. With applications to representation theory and geometry. MR 1464693
Fulvio Gesmundo, Christian Ikenmeyer, and Greta Panova, Geometric complexity theory and matrix powering, Differential Geom. Appl. 55 (2017), 106–127. MR 3724215, DOI 10.1016/j.difgeo.2017.07.001
Ankit Gupta, Pritish Kamath, Neeraj Kayal, and Ramprasad Saptharishi, Arithmetic circuits: a chasm at depth three, 2013 IEEE 54th Annual Symposium on Foundations of Computer Science—FOCS 2013, IEEE Computer Soc., Los Alamitos, CA, 2013, pp. 578–587. MR 3246261, DOI 10.1109/FOCS.2013.68
Fulvio Gesmundo and Joseph M. Landsberg, Explicit polynomial sequences with maximal spaces of partial derivatives and a question of K. Mulmuley, Theory Comput. 15 (2019), Paper No. 3, 24. MR 4003839, DOI 10.4086/toc.2019.v015a003
M. Hochster, Rings of invariants of tori, Cohen-Macaulay rings generated by monomials,and polytopes, Ann. Math. 96 (1972), 318–337.
Christian Ikenmeyer and J. M. Landsberg, On the complexity of the permanent in various computational models, J. Pure Appl. Algebra 221 (2017), no. 12, 2911–2927. MR 3666732, DOI 10.1016/j.jpaa.2017.02.008
Christian Ikenmeyer and Greta Panova, Rectangular Kronecker coefficients and plethysms in geometric complexity theory, Adv. Math. 319 (2017), 40–66. MR 3695867, DOI 10.1016/j.aim.2017.08.024
George A. Kirkup, Minimal primes over permanental ideals, Trans. Amer. Math. Soc. 360 (2008), no. 7, 3751–3770. MR 2386244, DOI 10.1090/S0002-9947-08-04340-7
J. M. Landsberg, Geometry and complexity theory, Cambridge Studies in Advanced Mathematics, vol. 169, Cambridge University Press, Cambridge, 2017. MR 3729273, DOI 10.1017/9781108183192
Alain Lascoux, Syzygies des variétés déterminantales, Adv. in Math. 30 (1978), no. 3, 202–237 (French). MR 520233, DOI 10.1016/0001-8708(78)90037-3
Reinhard C. Laubenbacher and Irena Swanson, Permanental ideals, J. Symbolic Comput. 30 (2000), no. 2, 195–205. MR 1777172, DOI 10.1006/jsco.2000.0363
K. D. Mulmuley, H. Narayanan, and M. Sohoni, Geometric complexity theory III: on deciding nonvanishing of a Littlewood–Richardson coefficient, J. Alg. Combinatorics 36 (2012), no. 1, 103–110.
K. D. Mulmuley and M. Sohoni, Geometric Complexity Theory. I. An approach to the P vs. NP and related problems, SIAM J. Comput. 31 (2001), no. 2, 496–526 (electronic).
Ezra Miller and Bernd Sturmfels, Combinatorial commutative algebra, Graduate Texts in Mathematics, vol. 227, Springer-Verlag, New York, 2005. MR 2110098
K. D. Mulmuley and M. Sohoni, Geometric Complexity Theory. II. Towards explicit obstructions for embeddings among class varieties, SIAM J. Comput. 38 (2008), no. 3, 1175–1206. \PrintDOI{10.1137/080718115}
Gerald Allen Reisner, Cohen-Macaulay quotients of polynomial rings, Advances in Math. 21 (1976), no. 1, 30–49. MR 407036, DOI 10.1016/0001-8708(76)90114-6
Hal Schenck, Computational algebraic geometry, London Mathematical Society Student Texts, vol. 58, Cambridge University Press, Cambridge, 2003. MR 2011360, DOI 10.1017/CBO9780511756320
Hal Schenck, Algebraic foundations for applied topology and data analysis, Mathematics of Data, vol. 1, Springer, Cham, [2022] ©2022. MR 4559594, DOI 10.1007/978-3-031-06664-1
Jessica Sidman and Gregory G. Smith, Linear determinantal equations for all projective schemes, Algebra Number Theory 5 (2011), no. 8, 1041–1061. MR 2948471, DOI 10.2140/ant.2011.5.1041
L. G. Valiant, Completeness classes in algebra, In Proceedings of the 11th ACM Symposium on Theory of Computing, STOC ’79, ACM, New York, 1979, pp. 249–261.
Günter M. Ziegler, Lectures on polytopes, Graduate Texts in Mathematics, vol. 152, Springer-Verlag, New York, 1995. MR 1311028, DOI 10.1007/978-1-4613-8431-1

AMS Website Down

Transactions of the American Mathematical Society

Bernstein-Gelfand-Gelfand meets geometric complexity theory: resolving the $\mathbf {2 \times 2}$ permanents of a $\mathbf {2 \times n}$ matrix
HTML articles powered by AMS MathViewer

Abstract: