Remote Access Journal of the American Mathematical Society
Green Open Access

Journal of the American Mathematical Society

ISSN 1088-6834(online) ISSN 0894-0347(print)

Request Permissions   Purchase Content 
 

 

Geometric complexity theory V: Efficient algorithms for Noether normalization


Author: Ketan D. Mulmuley
Journal: J. Amer. Math. Soc. 30 (2017), 225-309
MSC (2010): Primary 14Q20; Secondary 68Q15
DOI: https://doi.org/10.1090/jams/864
Published electronically: June 21, 2016
MathSciNet review: 3556292
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Journal of the American Mathematical Society with MSC (2010): 14Q20, 68Q15

Retrieve articles in all journals with MSC (2010): 14Q20, 68Q15


Additional Information

Ketan D. Mulmuley
Affiliation: Department of Computer Science, The University of Chicago, Chicago, Illinois, 60637
Email: mulmuley@uchicago.edu

DOI: https://doi.org/10.1090/jams/864
Keywords: Geometric complexity theory, Noether normalization, explicit varieties
Received by editor(s): August 5, 2013
Received by editor(s) in revised form: March 3, 2014, January 12, 2015, November 6, 2015, March 27, 2016, and April 19, 2016
Published electronically: June 21, 2016
Additional Notes: This work was supported by NSF grant CCF-1017760. This article is the full version of its FOCS 2012 extended abstract [70].
Dedicated: Dedicated to Sri Ramakrishna
Article copyright: © Copyright 2016 American Mathematical Society