Geometric complexity theory. V: Efficient algorithms for Noether normalization

DOI10.1090/JAMS/864MaRDI QIDQ2826783zbMATH OpenOpenAlexFDO

Publication date 18 October 2016

Published in Journal of the American Mathematical Society (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1209.5993

explicit varieties geometric complexity theory Noether normalization

Effectivity, complexity and computational aspects of algebraic geometry (14Q20) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

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 that: (1) The categorical quotient for any finite dimensional representation

V

of

S L_{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 i m e s m

matrices by the simultaneous conjugation action of

S L_{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, m / 2]

. (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.

Review text

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:NEWLINENEWLINE (1) The categorical quotient for any finite dimensional representation \(\mathbf V\) of \(\mathbf{SL}_m\), with constant \(m\), is explicit in characteristic zero.NEWLINENEWLINE (2) NNL for this categorical quotient can be solved deterministically in time quasi-polynomial in the dimension of \(\mathbf V\).NEWLINENEWLINE (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.NEWLINENEWLINE (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]\).NEWLINENEWLINE (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\).

Recommendations

Cites work

Cited in

(29)

This page was built for publication: Geometric complexity theory. V: Efficient algorithms for Noether normalization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2826783)