Geometric complexity theory V: Efficient algorithms for Noether normalization

Mulmuley, Ketan¹

¹ Department of Computer Science, The University of Chicago, Chicago, Illinois, 60637

Journal of the American Mathematical Society, Tome 30 (2017) no. 1, pp. 225-309

Résumé

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.

Détail

DOI : 10.1090/jams/864

Bibliographie

[1] Agrawal, Manindra Proving lower bounds via pseudo-random generators 2005 92 105

[2] Agrawal, Manindra, Saha, Chandan, Saxena, Nitin Quasi-polynomial hitting-set for set-depth-Δ formulas 2013 321 330

[3] Arora, Sanjeev, Barak, Boaz Computational complexity 2009

[4] Arvind, V., Joglekar, Pushkar S., Srinivasan, Srikanth Arithmetic circuits and the Hadamard product of polynomials 2009 25 36

[5] Basu, Saugata New results on quantifier elimination over real closed fields and applications to constraint databases J. ACM 1999 537 555

[6] Blasiak, Jonah, Mulmuley, Ketan D., Sohoni, Milind Geometric complexity theory IV: nonstandard quantum group for the Kronecker problem Mem. Amer. Math. Soc. 2015

[7] Boutot, Jean-Franã§Ois Singularités rationnelles et quotients par les groupes réductifs Invent. Math. 1987 65 68

[8] Brion, Michel Representations of quivers 2012 103 144

[9] Bruns, Winfried, Herzog, Jã¼Rgen Cohen-Macaulay rings 1993

[10] Le Bruyn, Lieven, Procesi, Claudio Semisimple representations of quivers Trans. Amer. Math. Soc. 1990 585 598

[11] Bã¼Rgisser, Peter Completeness and reduction in algebraic complexity theory 2000

[12] Bã¼Rgisser, Peter The complexity of factors of multivariate polynomials Found. Comput. Math. 2004 369 396

[13] Bã¼Rgisser, Peter, Landsberg, J. M., Manivel, Laurent, Weyman, Jerzy An overview of mathematical issues arising in the geometric complexity theory approach to 𝑉𝑃≠𝑉𝑁𝑃 SIAM J. Comput. 2011 1179 1209

[14] Cook, Stephen A. A taxonomy of problems with fast parallel algorithms Inform. and Control 1985 2 22

[15] Derksen, Harm Polynomial bounds for rings of invariants Proc. Amer. Math. Soc. 2001 955 963

[16] Derksen, Harm, Kemper, Gregor Computational invariant theory 2015

[17] Derksen, Harm, Weyman, Jerzy Semi-invariants of quivers and saturation for Littlewood-Richardson coefficients J. Amer. Math. Soc. 2000 467 479

[18] Dieudonnã©, J. The historical development of algebraic geometry Amer. Math. Monthly 1972 827 866

[19] Domokos, M. Finite generating system of matrix invariants Math. Pannon. 2002 175 181

[20] Domokos, M., Zubkov, A. N. Semi-invariants of quivers as determinants Transform. Groups 2001 9 24

[21] Donkin, Stephen Invariants of several matrices Invent. Math. 1992 389 401

[22] Doubilet, Peter, Rota, Gian-Carlo, Stein, Joel On the foundations of combinatorial theory. IX. Combinatorial methods in invariant theory Studies in Appl. Math. 1974 185 216

[23] Eisenbud, David Commutative algebra 1995

[24] Flenner, Hubert Rationale quasihomogene Singularitäten Arch. Math. (Basel) 1981 35 44

[25] Forbes, Michael A., Shpilka, Amir Quasipolynomial-time identity testing of non-commutative and read-once oblivious algebraic branching programs 2013 243 252

[26] Forbes, Michael A., Shpilka, Amir Explicit Noether normalization for simultaneous conjugation via polynomial identity testing 2013 527 542

[27] Formanek, Edward Generating the ring of matrix invariants 1986 73 82

[28] Fulton, William, Harris, Joe Representation theory 1991

[29] Gã¶Bel, Manfred Computing bases for rings of permutation-invariant polynomials J. Symbolic Comput. 1995 285 291

[30] Gordan, Paul 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. 1868 323 354

[31] Grenet, Bruno, Koiran, Pascal, Portier, Natacha The multivariate resultant is NP-hard in any characteristic 2010 477 488

[32] Grochow, Joshua A. Unifying known lower bounds via geometric complexity theory Comput. Complexity 2015 393 475

[33] Gupta, Ankit, Kamath, Pritish, Kayal, Neeraj, Saptharishi, Ramprasad Arithmetic circuits: a chasm at depth three 2013 578 587

[34] Hartshorne, Robin Algebraic geometry 1977

[35] Hilbert, David Ueber die Theorie der algebraischen Formen Math. Ann. 1890 473 534

[36] Hilbert, David Ueber die vollen Invariantensysteme Math. Ann. 1893 313 373

[37] Humphreys, James E. Linear algebraic groups 1975

[38] Ibarra, Oscar H., Moran, Shlomo Probabilistic algorithms for deciding equivalence of straight-line programs J. Assoc. Comput. Mach. 1983 217 228

[39] Impagliazzo, Russell, Wigderson, Avi 𝑃 1999 220 229

[40] Kabanets, Valentine, Impagliazzo, Russell Derandomizing polynomial identity tests means proving circuit lower bounds Comput. Complexity 2004 1 46

[41] 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. 1990 301 320

[42] Kayal, Neeraj, Saptharishi, Ramprasad A selection of lower bounds for arithmetic circuits 2014 77 115

[43] King, A. D. Moduli of representations of finite-dimensional algebras Quart. J. Math. Oxford Ser. (2) 1994 515 530

[44] Koiran, Pascal Hilbert’s Nullstellensatz is in the polynomial hierarchy J. Complexity 1996 273 286

[45] Kollã¡R, Jã¡Nos Sharp effective Nullstellensatz J. Amer. Math. Soc. 1988 963 975

[46] Lakshmibai, Venkatramani, Raghavan, Komaranapuram N. Standard monomial theory 2008

[47] Landsberg, J. M. Tensors: geometry and applications 2012

[48] Malod, Guillaume, Portier, Natacha Characterizing Valiant’s algebraic complexity classes J. Complexity 2008 16 38

[49] Mayr, Ernst W., Ritscher, Stephan Space-efficient Gröbner basis computation without degree bounds 2011 257 264

[50] Mourrain, Bernard, Pan, Victor Y. Multivariate polynomials, duality, and structured matrices J. Complexity 2000 110 180

[51] Mulmuley, Ketan Lower bounds in a parallel model without bit operations SIAM J. Comput. 1999 1460 1509

[52] Mulmuley, Ketan D. On P vs. NP and geometric complexity theory J. ACM 2011

[53] Mulmuley, Ketan D. Geometric complexity theory V: equivalence between blackbox derandomization of polynomial identity testing and derandomization of Noether’s normalization lemma 2012 629 638

[54] Mulmuley, Ketan D., Narayanan, Hariharan, Sohoni, Milind Geometric complexity theory III: on deciding nonvanishing of a Littlewood-Richardson coefficient J. Algebraic Combin. 2012 103 110

[55] Mulmuley, Ketan D., Sohoni, Milind Geometric complexity theory. I. An approach to the P vs. NP and related problems SIAM J. Comput. 2001 496 526

[56] Mulmuley, Ketan, Sohoni, Milind Geometric complexity theory, P vs. NP and explicit obstructions 2003 239 261

[57] Mulmuley, Ketan D., Sohoni, Milind Geometric complexity theory. II. Towards explicit obstructions for embeddings among class varieties SIAM J. Comput. 2008 1175 1206

[58] Mumford, David Algebraic geometry. I 1976

[59] Mumford, D., Fogarty, J., Kirwan, F. Geometric invariant theory 1994

[60] Nisan, Noam, Wigderson, Avi Hardness vs. randomness J. Comput. System Sci. 1994 149 167

[61] Pappacena, Christopher J. An upper bound for the length of a finite-dimensional algebra J. Algebra 1997 535 545

[62] Popov, V. L. The constructive theory of invariants Izv. Akad. Nauk SSSR Ser. Mat. 1981

[63] Vinberg, È. B., Popov, V. L. Invariant theory 1989

[64] Procesi, C. The invariant theory of 𝑛×𝑛 matrices Advances in Math. 1976 306 381

[65] Raz, Ran, Shpilka, Amir Deterministic polynomial identity testing in non-commutative models Comput. Complexity 2005 1 19

[66] Saxena, Nitin Diagonal circuit identity testing and lower bounds 2008 60 71

[67] Schwartz, J. T. Fast probabilistic algorithms for verification of polynomial identities J. Assoc. Comput. Mach. 1980 701 717

[68] Shafarevich, I. R. Basic algebraic geometry 1977

[69] Shpilka, Amir, Volkovich, Ilya Improved polynomial identity testing for read-once formulas 2009 700 713

[70] Shpilka, Amir, Yehudayoff, Amir Arithmetic circuits: a survey of recent results and open questions Found. Trends Theor. Comput. Sci. 2009

[71] Strassen, Volker Die Berechnungskomplexität von elementarsymmetrischen Funktionen und von Interpolationskoeffizienten Numer. Math. 1972/73 238 251

[72] Sturmfels, Bernd Algorithms in invariant theory 1993

[73] Valiant, L. G. Completeness classes in algebra 1979 249 261

[74] Valiant, L. G. The complexity of computing the permanent Theoret. Comput. Sci. 1979 189 201

[75] Valiant, L. G., Skyum, S., Berkowitz, S., Rackoff, C. Fast parallel computation of polynomials using few processors SIAM J. Comput. 1983 641 644

[76] Weyl, Hermann The classical groups 1997