×

Geometric complexity theory. V: Efficient algorithms for Noether normalization. (English) Zbl 1402.14078

The authors study a basic algorithmic problem in algebraic geometry, which is called NNL, of constructing a normalizing map as per Noether’s Normalization Lemma. For general explicit varieties, as formally defined in this paper, authors give a randomized polynomial-time Monte Carlo algorithm for this problem. For some interesting cases of explicit varieties, it is provided deterministic quasi-polynomial time algorithms. These may be contrasted with the standard EXPSPACE-algorithms for these problems in computational algebraic geometry. In particular, it is shown the following:
(1) The categorical quotient for any finite dimensional representation \(\mathbf V\) of \(\mathbf{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 \(\mathbf V\).
(3) The categorical quotient of the space of \(r\)-tuples of \(m \times m\) matrices by the simultaneous conjugation action of \(\mathbf{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\).

MSC:

14Q20 Effectivity, complexity and computational aspects of algebraic geometry
68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Agrawal, Manindra, Proving lower bounds via pseudo-random generators. FSTTCS 2005: Foundations of software technology and theoretical computer science, Lecture Notes in Comput. Sci. 3821, 92\textendash 105 pp. (2005), Springer, Berlin · Zbl 1172.68479
[2] Agrawal, Manindra; Saha, Chandan; Saxena, Nitin, Quasi-polynomial hitting-set for set-depth-\( \Delta\) formulas. STOC’13\textemdash Proceedings of the 2013 ACM Symposium on Theory of Computing, 321\textendash 330 pp. (2013), ACM, New York · Zbl 1293.94140
[3] Arora, Sanjeev; Barak, Boaz, Computational complexity, xxiv+579 pp. (2009), Cambridge University Press, Cambridge · Zbl 1193.68112
[4] Arvind, V.; Joglekar, Pushkar S.; Srinivasan, Srikanth, Arithmetic circuits and the Hadamard product of polynomials. Foundations of software technology and theoretical computer science\textemdash FSTTCS 2009, LIPIcs. Leibniz Int. Proc. Inform. 4, 25\textendash 36 pp. (2009), Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern · Zbl 1248.68209
[5] Basu, Saugata, New results on quantifier elimination over real closed fields and applications to constraint databases, J. ACM, 46, 4, 537\textendash 555 pp. (1999) · Zbl 1065.03507
[6] Blasiak, Jonah; Mulmuley, Ketan D.; Sohoni, Milind, Geometric complexity theory IV: nonstandard quantum group for the Kronecker problem, Mem. Amer. Math. Soc., 235, 1109, x+160 pp. (2015) · Zbl 1364.20004
[7] Boutot, Jean-Fran{\c{c}}ois, Singularit\'es rationnelles et quotients par les groupes r\'eductifs, Invent. Math., 88, 1, 65\textendash 68 pp. (1987) · Zbl 0619.14029
[8] brauer R. Brauer and C. Nesbitt, On the modular representations of groups of finite order I, In Richard Brauer: Collected papers (Vol. I) (1980), 336\textendash 354. · Zbl 0018.29504
[9] Brion, Michel, Representations of quivers. Geometric methods in representation theory. I, S\'emin. Congr. 24, 103\textendash 144 pp. (2012), Soc. Math. France, Paris · Zbl 1295.16007
[10] Bruns, Winfried; Herzog, J{\"u}rgen, Cohen-Macaulay rings, Cambridge Studies in Advanced Mathematics 39, xii+403 pp. (1993), Cambridge University Press, Cambridge · Zbl 0788.13005
[11] Le Bruyn, Lieven; Procesi, Claudio, Semisimple representations of quivers, Trans. Amer. Math. Soc., 317, 2, 585\textendash 598 pp. (1990) · Zbl 0693.16018
[12] B{\"u}rgisser, Peter, Completeness and reduction in algebraic complexity theory, Algorithms and Computation in Mathematics 7, xii+168 pp. (2000), Springer-Verlag, Berlin · Zbl 0948.68082
[13] B{\"u}rgisser, Peter, The complexity of factors of multivariate polynomials, Found. Comput. Math., 4, 4, 369\textendash 396 pp. (2004) · Zbl 1061.68064
[14] B{\"u}rgisser, Peter; Landsberg, J. M.; Manivel, Laurent; Weyman, Jerzy, An overview of mathematical issues arising in the geometric complexity theory approach to \({\rm VP}\neq{\rm VNP} \), SIAM J. Comput., 40, 4, 1179\textendash 1209 pp. (2011) · Zbl 1252.68134
[15] Cook, Stephen A., A taxonomy of problems with fast parallel algorithms, Inform. and Control, 64, 1-3, 2\textendash 22 pp. (1985) · Zbl 0575.68045
[16] Derksen, Harm, Polynomial bounds for rings of invariants, Proc. Amer. Math. Soc., 129, 4, 955\textendash 963 (electronic) pp. (2001) · Zbl 0969.13003
[17] Derksen, Harm; Kemper, Gregor, Computational invariant theory, Encyclopaedia of Mathematical Sciences 130, xxii+366 pp. (2015), Springer, Heidelberg · Zbl 1332.13001
[18] makam H. Derksen and V. Makam, Polynomial degree bounds for matrix semi-invariants, ArXiv:1512.03393 (2015). · Zbl 1361.15033
[19] Derksen, Harm; Weyman, Jerzy, Semi-invariants of quivers and saturation for Littlewood-Richardson coefficients, J. Amer. Math. Soc., 13, 3, 467\textendash 479 (electronic) pp. (2000) · Zbl 0993.16011
[20] Dieudonn{\'e}, J., The historical development of algebraic geometry, Amer. Math. Monthly, 79, 827\textendash 866 pp. (1972) · Zbl 0255.14003
[21] Domokos, M., Finite generating system of matrix invariants, Math. Pannon., 13, 2, 175\textendash 181 pp. (2002) · Zbl 1007.16017
[22] Domokos, M.; Zubkov, A. N., Semi-invariants of quivers as determinants, Transform. Groups, 6, 1, 9\textendash 24 pp. (2001) · Zbl 0984.16023
[23] Donkin, Stephen, Invariants of several matrices, Invent. Math., 110, 2, 389\textendash 401 pp. (1992) · Zbl 0826.20036
[24] Doubilet, Peter; Rota, Gian-Carlo; Stein, Joel, On the foundations of combinatorial theory. IX. Combinatorial methods in invariant theory, Studies Appl. Math., 53, 185\textendash 216 pp. (1974) · Zbl 0426.05009
[25] drozd J. Drozd, Tame and wild matrix problems, Amer. Math. Soc. Transl. 128 (1986), no. 2, 31\textendash 55. · Zbl 0583.16022
[26] eggermont R. Eggermont, Generalizations of a theorem of Brauer and Nesbitt, Master Thesis, Mathematisch Instituut, Universiteit Leiden (2011).
[27] Eisenbud, David, Commutative algebra, Graduate Texts in Mathematics 150, xvi+785 pp. (1995), Springer-Verlag, New York · Zbl 0819.13001
[28] Flenner, Hubert, Rationale quasihomogene Singularit\"aten, Arch. Math. (Basel), 36, 1, 35\textendash 44 pp. (1981) · Zbl 0454.14001
[29] fs1 M. Forbes, R. Saptharishi, and A. Shpilka, Hitting sets for multilinear read-once algebraic branching programs, in any order, Proc. STOC, 2014, pp. 867\textendash 875. · Zbl 1315.68127
[30] fs21 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.
[31] Forbes, Michael A.; Shpilka, Amir, Quasipolynomial-time identity testing of non-commutative and read-once oblivious algebraic branching programs. 2013 IEEE 54th Annual Symposium on Foundations of Computer Science\textemdash FOCS 2013, 243\textendash 252 pp. (2013), IEEE Computer Soc., Los Alamitos, CA
[32] Forbes, Michael A.; Shpilka, Amir, Explicit Noether normalization for simultaneous conjugation via polynomial identity testing. Approximation, randomization, and combinatorial optimization, Lecture Notes in Comput. Sci. 8096, 527\textendash 542 pp. (2013), Springer, Heidelberg · Zbl 1407.68535
[33] Formanek, Edward, Generating the ring of matrix invariants. Ring theory, Antwerp, 1985, Lecture Notes in Math. 1197, 73\textendash 82 pp. (1986), Springer, Berlin
[34] Fulton, William; Harris, Joe, Representation theory, Graduate Texts in Mathematics 129, xvi+551 pp. (1991), Springer-Verlag, New York · Zbl 0744.22001
[35] G{\"o}bel, Manfred, Computing bases for rings of permutation-invariant polynomials, J. Symbolic Comput., 19, 4, 285\textendash 291 pp. (1995) · Zbl 0832.13006
[36] Gordan, Paul, Beweis, dass jede Covariante und Invariante einer bin\"aren Form eine ganze Function mit numerischen Coefficienten einer endlichen Anzahl solcher Formen ist, J. Reine Angew. Math., 69, 323\textendash 354 pp. (1868) · JFM 01.0060.01
[37] Grenet, Bruno; Koiran, Pascal; Portier, Natacha, The multivariate resultant is NP-hard in any characteristic. Mathematical foundations of computer science 2010, Lecture Notes in Comput. Sci. 6281, 477\textendash 488 pp. (2010), Springer, Berlin · Zbl 1287.68056
[38] Grochow, Joshua A., Unifying known lower bounds via geometric complexity theory, Comput. Complexity, 24, 2, 393\textendash 475 pp. (2015) · Zbl 1329.68123
[39] GMQ J. Grochow, Y. Qiao, and K. Mulmuley, Boundaries of VP and VNP, To appear in the proceedings of ICALP, 2016. · Zbl 1388.68076
[40] Gupta, Ankit; Kamath, Pritish; Kayal, Neeraj; Saptharishi, Ramprasad, Arithmetic circuits: a chasm at depth three. 2013 IEEE 54th Annual Symposium on Foundations of Computer Science\textemdash FOCS 2013, 578\textendash 587 pp. (2013), IEEE Computer Soc., Los Alamitos, CA
[41] Hartshorne, Robin, Algebraic geometry, xvi+496 pp. (1977), Springer-Verlag, New York-Heidelberg · Zbl 0367.14001
[42] schnorr J. Heintz and C. Schnorr, Testing polynomials that are easy to compute, Proc.  STOC, 1980, pp. 262\textendash 272.
[43] Hilbert, David, Ueber die Theorie der algebraischen Formen, Math. Ann., 36, 4, 473\textendash 534 pp. (1890) · JFM 22.0133.01
[44] Hilbert, David, Ueber die vollen Invariantensysteme, Math. Ann., 42, 3, 313\textendash 373 pp. (1893) · JFM 25.0173.01
[45] Humphreys, James E., Linear algebraic groups, xiv+247 pp. (1975), Springer-Verlag, New York-Heidelberg · Zbl 0325.20039
[46] Ibarra, Oscar H.; Moran, Shlomo, Probabilistic algorithms for deciding equivalence of straight-line programs, J. Assoc. Comput. Mach., 30, 1, 217\textendash 228 pp. (1983) · Zbl 0497.68013
[47] ikenmeyer C. Ikenmeyer and G. Panova, Rectangular Kronecker coefficients and plethysms in geometric complexity theory, ArXiv:1512.03798 (2015). · Zbl 1388.68088
[48] Impagliazzo, Russell; Wigderson, Avi, \({\rm P}={\rm BPP}\) if \({\rm E}\) requires exponential circuits: derandomizing the XOR lemma. STOC ’97 (El Paso, TX), 220\textendash 229 (electronic) pp. (1999), ACM, New York · Zbl 0962.68058
[49] IQS G. Ivanyos, Y. Qiao, and K. Subrahmanyam, Constructive noncommutative rank computation in deterministic polynomial time over fields of arbitrary characteristic, ArXiv:1512.03531 (2016).
[50] Kabanets, Valentine; Impagliazzo, Russell, Derandomizing polynomial identity tests means proving circuit lower bounds, Comput. Complexity, 13, 1-2, 1\textendash 46 pp. (2004) · Zbl 1089.68042
[51] kaltofen E. Kaltofen, Factorization of polynomials given by straight-line programs, Randomness and Computation 5 (1989), 375\textendash 412.
[52] kaltofenlec 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).
[53] Kaltofen, Erich; Trager, Barry M., Computing with polynomials given by black boxes for their evaluations: greatest common divisors, factorization, separation of numerators and denominators, J. Symbolic Comput., 9, 3, 301\textendash 320 pp. (1990) · Zbl 0712.12001
[54] Kayal, Neeraj; Saptharishi, Ramprasad, A selection of lower bounds for arithmetic circuits. Perspectives in computational complexity, Progr. Comput. Sci. Appl. Logic 26, 77\textendash 115 pp. (2014), Birkh\"auser/Springer, Cham · Zbl 1345.68162
[55] King, A. D., Moduli of representations of finite-dimensional algebras, Quart. J. Math. Oxford Ser. (2), 45, 180, 515\textendash 530 pp. (1994) · Zbl 0837.16005
[56] Koiran, Pascal, Hilbert’s Nullstellensatz is in the polynomial hierarchy, J. Complexity, 12, 4, 273\textendash 286 pp. (1996) · Zbl 0862.68053
[57] Koll{\'a}r, J{\'a}nos, Sharp effective Nullstellensatz, J. Amer. Math. Soc., 1, 4, 963\textendash 975 pp. (1988) · Zbl 0682.14001
[58] Lakshmibai, Venkatramani; Raghavan, Komaranapuram N., Standard monomial theory, Encyclopaedia of Mathematical Sciences 137, xiv+265 pp. (2008), Springer-Verlag, Berlin · Zbl 1137.14036
[59] Landsberg, J. M., Tensors: geometry and applications, Graduate Studies in Mathematics 128, xx+439 pp. (2012), American Mathematical Society, Providence, RI · Zbl 1238.15013
[60] ressayre2 J. Landsberg and N. Ressayre, Hypersurfaces with degenerate duals and the geometric complexity theory program, ArXiv:1004.4802 (2010). · Zbl 1292.14033
[61] Malod, Guillaume; Portier, Natacha, Characterizing Valiant’s algebraic complexity classes, J. Complexity, 24, 1, 16\textendash 38 pp. (2008) · Zbl 1135.68017
[62] Mayr, Ernst W.; Ritscher, Stephan, Space-efficient Gr\"obner basis computation without degree bounds. ISSAC 2011\textemdash Proceedings of the 36th International Symposium on Symbolic and Algebraic Computation, 257\textendash 264 pp. (2011), ACM, New York · Zbl 1323.68616
[63] milne J. Milne, Reductive groups, http://www.jmilne.org/math/CourseNotes/RG.pdf (2012).
[64] Mourrain, Bernard; Pan, Victor Y., Multivariate polynomials, duality, and structured matrices, J. Complexity, 16, 1, 110\textendash 180 pp. (2000) · Zbl 0963.68232
[65] GCT6 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 sgctapproach.
[66] Mulmuley, Ketan, Lower bounds in a parallel model without bit operations, SIAM J. Comput., 28, 4, 1460\textendash 1509 (electronic) pp. (1999) · Zbl 0940.68052
[67] Mulmuley, Ketan D., On P vs. NP and geometric complexity theory, J. ACM, 58, 2, Art. 5, 26 pp. (2011) · Zbl 1327.68111
[68] GCTcacm Ketan D. Mulmuley, The GCT program toward the \(P\) vs. \(NP\) problem, Commun. ACM 55 (2012), no. 6, 98\textendash 107.
[69] GCTtutorial 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).
[70] Mulmuley, Ketan D., Geometric complexity theory V: equivalence between black-box derandomization of polynomial identity testing and derandomization of Noether’s normalization lemma. 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science\textemdash FOCS 2012, 629\textendash 638 pp. (2012), IEEE Computer Soc., Los Alamitos, CA
[71] Mulmuley, Ketan D.; Narayanan, Hariharan; Sohoni, Milind, Geometric complexity theory III: on deciding nonvanishing of a Littlewood-Richardson coefficient, J. Algebraic Combin., 36, 1, 103\textendash 110 pp. (2012) · Zbl 1271.03055
[72] Mulmuley, Ketan D.; Sohoni, Milind, Geometric complexity theory. I. An approach to the P vs.NP and related problems, SIAM J. Comput., 31, 2, 496\textendash 526 pp. (2001) · Zbl 0992.03048
[73] Mulmuley, Ketan; Sohoni, Milind, Geometric complexity theory, P vs.NP and explicit obstructions. Advances in algebra and geometry, Hyderabad, 2001, 239\textendash 261 pp. (2003), Hindustan Book Agency, New Delhi · Zbl 1046.68057
[74] Mulmuley, Ketan D.; Sohoni, Milind, Geometric complexity theory. II. Towards explicit obstructions for embeddings among class varieties, SIAM J. Comput., 38, 3, 1175\textendash 1206 pp. (2008) · Zbl 1168.03030
[75] Mumford, David, Algebraic geometry. I, x+186 pp. (1976), Springer-Verlag, Berlin-New York · Zbl 0821.14001
[76] Mumford, D.; Fogarty, J.; Kirwan, F., Geometric invariant theory, Ergebnisse der Mathematik und ihrer Grenzgebiete (2) [Results in Mathematics and Related Areas (2)] 34, xiv+292 pp. (1994), Springer-Verlag, Berlin · Zbl 0797.14004
[77] Nisan, Noam; Wigderson, Avi, Hardness vs.randomness, J. Comput. System Sci., 49, 2, 149\textendash 167 pp. (1994) · Zbl 0821.68057
[78] Pappacena, Christopher J., An upper bound for the length of a finite-dimensional algebra, J. Algebra, 197, 2, 535\textendash 545 pp. (1997) · Zbl 0888.16008
[79] Popov, V. L., The constructive theory of invariants, Izv. Akad. Nauk SSSR Ser. Mat., 45, 5, 1100\textendash 1120, 1199 pp. (1981)
[80] Vinberg, {\`E}. B.; Popov, V. L., Invariant theory. Algebraic geometry, 4 (Russian), Itogi Nauki i Tekhniki, 137\textendash 314, 315 pp. (1989), Akad. Nauk SSSR, Vsesoyuz. Inst. Nauchn. i Tekhn. Inform., Moscow
[81] Procesi, C., The invariant theory of \(n\times n\) matrices, Adv. Math., 19, 3, 306\textendash 381 pp. (1976) · Zbl 0331.15021
[82] Raz, Ran; Shpilka, Amir, Deterministic polynomial identity testing in non-commutative models, Comput. Complexity, 14, 1, 1\textendash 19 pp. (2005) · Zbl 1096.68070
[83] razmyslov Y. Razmyslov, Trace identities of full matrix algebras over a field of characteristic zero, Math. USSR Izv. 8 (1974), 727\textendash 760. · Zbl 0311.16016
[84] Saxena, Nitin, Diagonal circuit identity testing and lower bounds. Automata, languages and programming. Part I, Lecture Notes in Comput. Sci. 5125, 60\textendash 71 pp. (2008), Springer, Berlin · Zbl 1152.68703
[85] Schwartz, J. T., Fast probabilistic algorithms for verification of polynomial identities, J. ACM, 27, 4, 701\textendash 717 pp. (1980) · Zbl 0452.68050
[86] Shafarevich, I. R., Basic algebraic geometry, xv+439 pp. (1977), Springer-Verlag, Berlin-New York
[87] Shpilka, Amir; Volkovich, Ilya, Improved polynomial identity testing for read-once formulas. Approximation, randomization, and combinatorial optimization, Lecture Notes in Comput. Sci. 5687, 700\textendash 713 pp. (2009), Springer, Berlin · Zbl 1255.68297
[88] Shpilka, Amir; Yehudayoff, Amir, Arithmetic circuits: a survey of recent results and open questions, Found. Trends Theor. Comput. Sci., 5, 3-4, 207\textendash 388 (2010) pp. (2009) · Zbl 1205.68175
[89] Strassen, Volker, Die Berechnungskomplexit\"at von elementarsymmetrischen Funktionen und von Interpolationskoeffizienten, Numer. Math., 20, 238\textendash 251 pp. (1972/73) · Zbl 0251.65036
[90] Sturmfels, Bernd, Algorithms in invariant theory, Texts and Monographs in Symbolic Computation, vi+197 pp. (1993), Springer-Verlag, Vienna · Zbl 0802.13002
[91] totaro B. Totaro, private communication.
[92] Valiant, L. G., Completeness classes in algebra. Conference Record of the Eleventh Annual ACM Symposium on Theory of Computing, Atlanta, Ga., 1979, 249\textendash 261 pp. (1979), ACM, New York
[93] Valiant, L. G., The complexity of computing the permanent, Theoret. Comput. Sci., 8, 2, 189\textendash 201 pp. (1979) · Zbl 0415.68008
[94] Valiant, L. G.; Skyum, S.; Berkowitz, S.; Rackoff, C., Fast parallel computation of polynomials using few processors, SIAM J. Comput., 12, 4, 641\textendash 644 pp. (1983) · Zbl 0524.68028
[95] Weyl, Hermann, The classical groups, Princeton Landmarks in Mathematics, xiv+320 pp. (1997), Princeton University Press, Princeton, NJ · Zbl 1024.20501
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.