Geometric complexity theory V: Efficient algorithms for Noether normalization

Mulmuley, Ketan

doi:10.1090/jams/864

Geometric complexity theory V: Efficient algorithms for Noether normalization
HTML articles powered by AMS MathViewer

by Ketan D. Mulmuley;

J. Amer. Math. Soc. 30 (2017), 225-309

DOI: https://doi.org/10.1090/jams/864

Published electronically: June 21, 2016

PDF | Request permission

Abstract:

We study a basic algorithmic problem in algebraic geometry, which we call NNL, of constructing a normalizing map as per Noether’s Normalization Lemma. For general explicit varieties, as formally defined in this paper, we give a randomized polynomial-time Monte Carlo algorithm for this problem. For some interesting cases of explicit varieties, we give deterministic quasi-polynomial time algorithms. These may be contrasted with the standard EXPSPACE-algorithms for these problems in computational algebraic geometry.

In particular, we show the following:

(1) The categorical quotient for any finite dimensional representation $V$ of $SL_m$, with constant $m$, is explicit in characteristic zero.

(2) NNL for this categorical quotient can be solved deterministically in time quasi-polynomial in the dimension of $V$.

(3) The categorical quotient of the space of $r$-tuples of $m \times m$ matrices by the simultaneous conjugation action of $SL_m$ is explicit in any characteristic.

(4) NNL for this categorical quotient can be solved deterministically in time quasi-polynomial in $m$ and $r$ in any characteristic $p \not \in [2,\lfloor m/2 \rfloor ]$.

(5) NNL for every explicit variety in zero or large enough characteristic can be solved deterministically in quasi-polynomial time, assuming the hardness hypothesis for the permanent in geometric complexity theory.

The last result leads to a geometric complexity theory approach to put NNL for every explicit variety in P.

References

Manindra Agrawal, Proving lower bounds via pseudo-random generators, FSTTCS 2005: Foundations of software technology and theoretical computer science, Lecture Notes in Comput. Sci., vol. 3821, Springer, Berlin, 2005, pp. 92–105. MR 2212985, DOI 10.1007/11590156_{6}
Manindra Agrawal, Chandan Saha, and Nitin Saxena, Quasi-polynomial hitting-set for set-depth-$\Delta$ formulas, STOC’13—Proceedings of the 2013 ACM Symposium on Theory of Computing, ACM, New York, 2013, pp. 321–330. MR 3210793, DOI 10.1145/2488608.2488649
Sanjeev Arora and Boaz Barak, Computational complexity, Cambridge University Press, Cambridge, 2009. A modern approach. MR 2500087, DOI 10.1017/CBO9780511804090
V. Arvind, Pushkar S. Joglekar, and Srikanth Srinivasan, Arithmetic circuits and the Hadamard product of polynomials, Foundations of software technology and theoretical computer science—FSTTCS 2009, LIPIcs. Leibniz Int. Proc. Inform., vol. 4, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2009, pp. 25–36. MR 2870698
Saugata Basu, New results on quantifier elimination over real closed fields and applications to constraint databases, J. ACM 46 (1999), no. 4, 537–555. MR 1812131, DOI 10.1145/320211.320240
Jonah Blasiak, Ketan D. Mulmuley, and Milind Sohoni, Geometric complexity theory IV: nonstandard quantum group for the Kronecker problem, Mem. Amer. Math. Soc. 235 (2015), no. 1109, x+160. MR 3338303, DOI 10.1090/memo/1109
Jean-François Boutot, Singularités rationnelles et quotients par les groupes réductifs, Invent. Math. 88 (1987), no. 1, 65–68 (French). MR 877006, DOI 10.1007/BF01405091
R. Brauer and C. Nesbitt, On the modular representations of groups of finite order I, In Richard Brauer: Collected papers (Vol. I) (1980), 336–354.
Michel Brion, Representations of quivers, Geometric methods in representation theory. I, Sémin. Congr., vol. 24, Soc. Math. France, Paris, 2012, pp. 103–144 (English, with English and French summaries). MR 3202702
Winfried Bruns and Jürgen Herzog, Cohen-Macaulay rings, Cambridge Studies in Advanced Mathematics, vol. 39, Cambridge University Press, Cambridge, 1993. MR 1251956
Lieven Le Bruyn and Claudio Procesi, Semisimple representations of quivers, Trans. Amer. Math. Soc. 317 (1990), no. 2, 585–598. MR 958897, DOI 10.1090/S0002-9947-1990-0958897-0
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, The complexity of factors of multivariate polynomials, Found. Comput. Math. 4 (2004), no. 4, 369–396. MR 2097213, DOI 10.1007/s10208-002-0059-5
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
Stephen A. Cook, A taxonomy of problems with fast parallel algorithms, Inform. and Control 64 (1985), no. 1-3, 2–22. MR 837088, DOI 10.1016/S0019-9958(85)80041-3
Harm Derksen, Polynomial bounds for rings of invariants, Proc. Amer. Math. Soc. 129 (2001), no. 4, 955–963. MR 1814136, DOI 10.1090/S0002-9939-00-05698-7
Harm Derksen and Gregor Kemper, Computational invariant theory, Second enlarged edition, Encyclopaedia of Mathematical Sciences, vol. 130, Springer, Heidelberg, 2015. With two appendices by Vladimir L. Popov, and an addendum by Norbert A’Campo and Popov; Invariant Theory and Algebraic Transformation Groups, VIII. MR 3445218, DOI 10.1007/978-3-662-48422-7
H. Derksen and V. Makam, Polynomial degree bounds for matrix semi-invariants, ArXiv:1512.03393 (2015).
Harm Derksen and Jerzy Weyman, Semi-invariants of quivers and saturation for Littlewood-Richardson coefficients, J. Amer. Math. Soc. 13 (2000), no. 3, 467–479. MR 1758750, DOI 10.1090/S0894-0347-00-00331-3
J. Dieudonné, The historical development of algebraic geometry, Amer. Math. Monthly 79 (1972), 827–866. MR 308117, DOI 10.2307/2317664
M. Domokos, Finite generating system of matrix invariants, Math. Pannon. 13 (2002), no. 2, 175–181. MR 1932423
M. Domokos and A. N. Zubkov, Semi-invariants of quivers as determinants, Transform. Groups 6 (2001), no. 1, 9–24. MR 1825166, DOI 10.1007/BF01236060
Stephen Donkin, Invariants of several matrices, Invent. Math. 110 (1992), no. 2, 389–401. MR 1185589, DOI 10.1007/BF01231338
Peter Doubilet, Gian-Carlo Rota, and Joel Stein, On the foundations of combinatorial theory. IX. Combinatorial methods in invariant theory, Studies in Appl. Math. 53 (1974), 185–216. MR 498650, DOI 10.1002/sapm1974533185
J. Drozd, Tame and wild matrix problems, Amer. Math. Soc. Transl. 128 (1986), no. 2, 31–55.
R. Eggermont, Generalizations of a theorem of Brauer and Nesbitt, Master Thesis, Mathematisch Instituut, Universiteit Leiden (2011).
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
Hubert Flenner, Rationale quasihomogene Singularitäten, Arch. Math. (Basel) 36 (1981), no. 1, 35–44 (German). MR 612234, DOI 10.1007/BF01223666
M. Forbes, R. Saptharishi, and A. Shpilka, Hitting sets for multilinear read-once algebraic branching programs, in any order, Proc. STOC, 2014, pp. 867–875.
Michael A. Forbes and Amir Shpilka, Quasi-polynomial-time identity testing of non-commutative and read-once oblivious algebraic branching programs, Electronic Colloquium on Computational Complexity (ECCC), 19:115, Version 1, 2012.
Michael A. Forbes and Amir Shpilka, Quasipolynomial-time identity testing of non-commutative and read-once oblivious algebraic branching programs, 2013 IEEE 54th Annual Symposium on Foundations of Computer Science—FOCS 2013, IEEE Computer Soc., Los Alamitos, CA, 2013, pp. 243–252. MR 3246226, DOI 10.1109/FOCS.2013.34
Michael A. Forbes and Amir Shpilka, Explicit Noether normalization for simultaneous conjugation via polynomial identity testing, Approximation, randomization, and combinatorial optimization, Lecture Notes in Comput. Sci., vol. 8096, Springer, Heidelberg, 2013, pp. 527–542. MR 3126552, DOI 10.1007/978-3-642-40328-6_{3}7
Edward Formanek, Generating the ring of matrix invariants, Ring theory (Antwerp, 1985) Lecture Notes in Math., vol. 1197, Springer, Berlin, 1986, pp. 73–82. MR 859385, DOI 10.1007/BFb0076314
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
Manfred Göbel, Computing bases for rings of permutation-invariant polynomials, J. Symbolic Comput. 19 (1995), no. 4, 285–291. MR 1339909, DOI 10.1006/jsco.1995.1017
Paul Gordan, Beweis, dass jede Covariante und Invariante einer binären Form eine ganze Function mit numerischen Coefficienten einer endlichen Anzahl solcher Formen ist, J. Reine Angew. Math. 69 (1868), 323–354 (German). MR 1579424, DOI 10.1515/crll.1868.69.323
Bruno Grenet, Pascal Koiran, and Natacha Portier, The multivariate resultant is NP-hard in any characteristic, Mathematical foundations of computer science 2010, Lecture Notes in Comput. Sci., vol. 6281, Springer, Berlin, 2010, pp. 477–488. MR 2727251, DOI 10.1007/978-3-642-15155-2_{4}2
Joshua A. Grochow, Unifying known lower bounds via geometric complexity theory, Comput. Complexity 24 (2015), no. 2, 393–475. MR 3349809, DOI 10.1007/s00037-015-0103-x
J. Grochow, Y. Qiao, and K. Mulmuley, Boundaries of VP and VNP, To appear in the proceedings of ICALP, 2016.
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
Robin Hartshorne, Algebraic geometry, Graduate Texts in Mathematics, No. 52, Springer-Verlag, New York-Heidelberg, 1977. MR 463157, DOI 10.1007/978-1-4757-3849-0
J. Heintz and C. Schnorr, Testing polynomials that are easy to compute, Proc. STOC, 1980, pp. 262–272.
David Hilbert, Ueber die Theorie der algebraischen Formen, Math. Ann. 36 (1890), no. 4, 473–534 (German). MR 1510634, DOI 10.1007/BF01208503
David Hilbert, Ueber die vollen Invariantensysteme, Math. Ann. 42 (1893), no. 3, 313–373 (German). MR 1510781, DOI 10.1007/BF01444162
James E. Humphreys, Linear algebraic groups, Graduate Texts in Mathematics, No. 21, Springer-Verlag, New York-Heidelberg, 1975. MR 396773, DOI 10.1007/978-1-4684-9443-3
Oscar H. Ibarra and Shlomo Moran, Probabilistic algorithms for deciding equivalence of straight-line programs, J. Assoc. Comput. Mach. 30 (1983), no. 1, 217–228. MR 694489, DOI 10.1145/322358.322373
C. Ikenmeyer and G. Panova, Rectangular Kronecker coefficients and plethysms in geometric complexity theory, ArXiv:1512.03798 (2015).
Russell Impagliazzo and Avi Wigderson, $\textrm {P}=\textrm {BPP}$ if $\textrm {E}$ requires exponential circuits: derandomizing the XOR lemma, STOC ’97 (El Paso, TX), ACM, New York, 1999, pp. 220–229. MR 1715634
G. Ivanyos, Y. Qiao, and K. Subrahmanyam, Constructive noncommutative rank computation in deterministic polynomial time over fields of arbitrary characteristic, ArXiv:1512.03531 (2016).
Valentine Kabanets and Russell Impagliazzo, Derandomizing polynomial identity tests means proving circuit lower bounds, Comput. Complexity 13 (2004), no. 1-2, 1–46. MR 2105971, DOI 10.1007/s00037-004-0182-6
E. Kaltofen, Factorization of polynomials given by straight-line programs, Randomness and Computation 5 (1989), 375–412.
E. Kaltofen and G. Lecerf, Factorization of multivariate polynomials, Chapter 11.5, in Handbook of Finite Fields, Discrete Mathematics and Its Applications, CRC Press (2013).
Erich Kaltofen and Barry M. Trager, Computing with polynomials given by black boxes for their evaluations: greatest common divisors, factorization, separation of numerators and denominators, J. Symbolic Comput. 9 (1990), no. 3, 301–320. MR 1056629, DOI 10.1016/S0747-7171(08)80015-6
Neeraj Kayal and Ramprasad Saptharishi, A selection of lower bounds for arithmetic circuits, Perspectives in computational complexity, Progr. Comput. Sci. Appl. Logic, vol. 26, Birkhäuser/Springer, Cham, 2014, pp. 77–115. MR 3330014
A. D. King, Moduli of representations of finite-dimensional algebras, Quart. J. Math. Oxford Ser. (2) 45 (1994), no. 180, 515–530. MR 1315461, DOI 10.1093/qmath/45.4.515
Pascal Koiran, Hilbert’s Nullstellensatz is in the polynomial hierarchy, J. Complexity 12 (1996), no. 4, 273–286. Special issue for the Foundations of Computational Mathematics Conference (Rio de Janeiro, 1997). MR 1422712, DOI 10.1006/jcom.1996.0019
János Kollár, Sharp effective Nullstellensatz, J. Amer. Math. Soc. 1 (1988), no. 4, 963–975. MR 944576, DOI 10.1090/S0894-0347-1988-0944576-7
Venkatramani Lakshmibai and Komaranapuram N. Raghavan, Standard monomial theory, Encyclopaedia of Mathematical Sciences, vol. 137, Springer-Verlag, Berlin, 2008. Invariant theoretic approach; Invariant Theory and Algebraic Transformation Groups, 8. MR 2388163
J. M. Landsberg, Tensors: geometry and applications, Graduate Studies in Mathematics, vol. 128, American Mathematical Society, Providence, RI, 2012. MR 2865915, DOI 10.1090/gsm/128
J. Landsberg and N. Ressayre, Hypersurfaces with degenerate duals and the geometric complexity theory program, ArXiv:1004.4802 (2010).
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
Ernst W. Mayr and Stephan Ritscher, Space-efficient Gröbner basis computation without degree bounds, ISSAC 2011—Proceedings of the 36th International Symposium on Symbolic and Algebraic Computation, ACM, New York, 2011, pp. 257–264. MR 2895220, DOI 10.1145/1993886.1993926
J. Milne, Reductive groups, http://www.jmilne.org/math/CourseNotes/RG.pdf (2012).
Bernard Mourrain and Victor Y. Pan, Multivariate polynomials, duality, and structured matrices, J. Complexity 16 (2000), no. 1, 110–180. Real computation and complexity (Schloss Dagstuhl, 1998). MR 1762401, DOI 10.1006/jcom.1999.0530
K. Mulmuley, Geometric complexity theory VI, Revised version under preparation, The current version of this article at ArXiv:0704.0229 is outdated; cf. the third paragraph in Section \ref{sgctapproach}.
Ketan Mulmuley, Lower bounds in a parallel model without bit operations, SIAM J. Comput. 28 (1999), no. 4, 1460–1509. MR 1681069, DOI 10.1137/S0097539794282930
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, The GCT program toward the $P$ vs. $NP$ problem, Commun. ACM 55 (2012), no. 6, 98–107.
Ketan D. Mulmuley, The GCT chasm I, Tutorial in the workshop on Geometric Complexity Theory, Simons Institute, Berkeley, http://simons.berkeley.edu/workshops/schedule/430 (2014).
Ketan D. Mulmuley, Geometric complexity theory V: equivalence between blackbox derandomization of polynomial identity testing and derandomization of Noether’s normalization lemma, 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science—FOCS 2012, IEEE Computer Soc., Los Alamitos, CA, 2012, pp. 629–638. MR 3186651
Ketan D. Mulmuley, Hariharan Narayanan, and Milind Sohoni, Geometric complexity theory III: on deciding nonvanishing of a Littlewood-Richardson coefficient, J. Algebraic Combin. 36 (2012), no. 1, 103–110. MR 2927658, DOI 10.1007/s10801-011-0325-1
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 Mulmuley and Milind Sohoni, Geometric complexity theory, P vs. NP and explicit obstructions, Advances in algebra and geometry (Hyderabad, 2001) Hindustan Book Agency, New Delhi, 2003, pp. 239–261. MR 1988959
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
David Mumford, Algebraic geometry. I, Grundlehren der Mathematischen Wissenschaften, No. 221, Springer-Verlag, Berlin-New York, 1976. Complex projective varieties. MR 453732
D. Mumford, J. Fogarty, and F. Kirwan, Geometric invariant theory, 3rd ed., Ergebnisse der Mathematik und ihrer Grenzgebiete (2) [Results in Mathematics and Related Areas (2)], vol. 34, Springer-Verlag, Berlin, 1994. MR 1304906, DOI 10.1007/978-3-642-57916-5
Noam Nisan and Avi Wigderson, Hardness vs. randomness, J. Comput. System Sci. 49 (1994), no. 2, 149–167. MR 1293639, DOI 10.1016/S0022-0000(05)80043-1
Christopher J. Pappacena, An upper bound for the length of a finite-dimensional algebra, J. Algebra 197 (1997), no. 2, 535–545. MR 1483779, DOI 10.1006/jabr.1997.7140
V. L. Popov, The constructive theory of invariants, Izv. Akad. Nauk SSSR Ser. Mat. 45 (1981), no. 5, 1100–1120, 1199 (Russian). MR 637618
È. B. Vinberg and V. L. Popov, Invariant theory, Algebraic geometry, 4 (Russian), Itogi Nauki i Tekhniki, Akad. Nauk SSSR, Vsesoyuz. Inst. Nauchn. i Tekhn. Inform., Moscow, 1989, pp. 137–314, 315 (Russian). MR 1100485
C. Procesi, The invariant theory of $n\times n$ matrices, Advances in Math. 19 (1976), no. 3, 306–381. MR 419491, DOI 10.1016/0001-8708(76)90027-X
Ran Raz and Amir Shpilka, Deterministic polynomial identity testing in non-commutative models, Comput. Complexity 14 (2005), no. 1, 1–19. MR 2134043, DOI 10.1007/s00037-005-0188-8
Y. Razmyslov, Trace identities of full matrix algebras over a field of characteristic zero, Math. USSR Izv. 8 (1974), 727–760.
Nitin Saxena, Diagonal circuit identity testing and lower bounds, Automata, languages and programming. Part I, Lecture Notes in Comput. Sci., vol. 5125, Springer, Berlin, 2008, pp. 60–71. MR 2500261, DOI 10.1007/978-3-540-70575-8_{6}
J. T. Schwartz, Fast probabilistic algorithms for verification of polynomial identities, J. Assoc. Comput. Mach. 27 (1980), no. 4, 701–717. MR 594695, DOI 10.1145/322217.322225
I. R. Shafarevich, Basic algebraic geometry, Springer Study Edition, Springer-Verlag, Berlin-New York, 1977. Translated from the Russian by K. A. Hirsch; Revised printing of Grundlehren der mathematischen Wissenschaften, Vol. 213, 1974. MR 447223
Amir Shpilka and Ilya Volkovich, Improved polynomial identity testing for read-once formulas, Approximation, randomization, and combinatorial optimization, Lecture Notes in Comput. Sci., vol. 5687, Springer, Berlin, 2009, pp. 700–713. MR 2551039, DOI 10.1007/978-3-642-03685-9_{5}2
Amir Shpilka and Amir Yehudayoff, Arithmetic circuits: a survey of recent results and open questions, Found. Trends Theor. Comput. Sci. 5 (2009), no. 3-4, 207–388 (2010). MR 2756166, DOI 10.1561/0400000039
Volker Strassen, Die Berechnungskomplexität von elementarsymmetrischen Funktionen und von Interpolationskoeffizienten, Numer. Math. 20 (1972/73), 238–251 (German, with English summary). MR 324947, DOI 10.1007/BF01436566
Bernd Sturmfels, Algorithms in invariant theory, Texts and Monographs in Symbolic Computation, Springer-Verlag, Vienna, 1993. MR 1255980, DOI 10.1007/978-3-7091-4368-1
B. Totaro, private communication.
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, The complexity of computing the permanent, Theoret. Comput. Sci. 8 (1979), no. 2, 189–201. MR 526203, DOI 10.1016/0304-3975(79)90044-6
L. G. Valiant, S. Skyum, S. Berkowitz, and C. Rackoff, Fast parallel computation of polynomials using few processors, SIAM J. Comput. 12 (1983), no. 4, 641–644. MR 721003, DOI 10.1137/0212043
Hermann Weyl, The classical groups, Princeton Landmarks in Mathematics, Princeton University Press, Princeton, NJ, 1997. Their invariants and representations; Fifteenth printing; Princeton Paperbacks. MR 1488158