Geodesic
Double-exponential lower bound for the degree of any system of generators of a~polynomial prime ideal
Algebra i analiz, Tome 20 (2008) no. 6, pp. 186-213.

Voir la notice de l'article provenant de la source Math-Net.Ru

Let $A$ be a polynomial ring in $n+1$ variables over an arbitrary infinite field $k$. It is proved that for all sufficiently large $n$ and $d$ there is a homogeneous prime ideal ${\mathfrak p}\subset A$ satisfying the following conditions. The ideal ${\mathfrak p}$ corresponds to a component, defined over $k$ and irreducible over $\overline{k}$, of a projective algebraic variety given by a system of homogeneous polynomial equations with polynomials in $A$ of degrees less than $d$. Any system of generators of ${\mathfrak p}$ contains a polynomial of degree at least $d^{2^{cn}}$ for an absolute constant $c>0$, which can be computed efficiently. This solves an important old problem in effective algebraic geometry. For the case of finite fields a slightly less strong result is obtained.
Keywords: Polynomial ideal, projective algebraic variety, Gröbner basis, effective algebraic geometry. 
@article{AA_2008_20_6_a5,
     author = {A. L. Chistov},
     title = {Double-exponential lower bound for the degree of any system of generators of a~polynomial prime ideal},
     journal = {Algebra i analiz},
     pages = {186--213},
     publisher = {mathdoc},
     volume = {20},
     number = {6},
     year = {2008},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/AA_2008_20_6_a5/}
}
TY  - JOUR
AU  - A. L. Chistov
TI  - Double-exponential lower bound for the degree of any system of generators of a~polynomial prime ideal
JO  - Algebra i analiz
PY  - 2008
SP  - 186
EP  - 213
VL  - 20
IS  - 6
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/AA_2008_20_6_a5/
LA  - ru
ID  - AA_2008_20_6_a5
ER  - 
%0 Journal Article
%A A. L. Chistov
%T Double-exponential lower bound for the degree of any system of generators of a~polynomial prime ideal
%J Algebra i analiz
%D 2008
%P 186-213
%V 20
%N 6
%I mathdoc
%U http://geodesic.mathdoc.fr/item/AA_2008_20_6_a5/
%G ru
%F AA_2008_20_6_a5
A. L. Chistov. Double-exponential lower bound for the degree of any system of generators of a~polynomial prime ideal. Algebra i analiz, Tome 20 (2008) no. 6, pp. 186-213. http://geodesic.mathdoc.fr/item/AA_2008_20_6_a5/

[1] Baldassarri M., Algebraicheskie mnogoobraziya, IL, M., 1961 | MR

[2] Chistov A. L., “Algoritm polinomialnoi slozhnosti dlya razlozheniya mnogochlenov i nakhozhdenie komponent mnogoobraziya v subeksponentsialnoe vremya”, Zap. nauch. semin. LOMI, 137, 1984, 124–188 | MR | Zbl

[3] Chistov A. L., “Effektivnaya konstruktsiya lokalnykh parametrov neprivodimykh komponent algebraicheskogo mnogoobraziya”, Tr. S.-Peterburg. mat. o-va, 7, 1999, 230–266 | MR

[4] Chistov A. L., A deterministic polynomial–time algorithm for the first Bertini theorem, Preprint S.-Peterburg. mat. o-va No9, , 2004 (na angl. yaz.) http://www.mathsoc.spb.ru/preprint/

[5] Dubé T. W., “The structure of polynomial ideals and Gröbner bases”, SIAM J. Comput., 19 (1990), 750–775 | DOI | MR

[6] Hermann G., “Die Frage der endlich vielen Schritte in der Theorie der Polynomideale”, Math. Ann., 95 (1926), 736–788 | DOI | MR | Zbl

[7] Hilbert D., “Über die Theorie der algebraischen Formen”, Math. Ann., 36 (1890), 473–534 | DOI | MR

[8] Lazard D., “Algèbre linéaire sur $k[x_1,\dots,x_n]$ et élimination”, Bull. Soc. Math. France, 105 (1977), 165–190 | MR | Zbl

[9] Mayr E. W., Meyer A. R., “The complexity of the word problems for commutative semigroups and polynomial ideals”, Adv. Math., 46 (1982), 305–329 | DOI | MR | Zbl

[10] Seidenberg A., “Constructions in algebra”, Trans. Amer. Math. Soc., 197 (1974), 273–313 | DOI | MR | Zbl

[11] Yap Chee K., “A new lower bound construction for commutative Thue systems, with applications”, J. Symbolic Comput., 12 (1991), 1–27 | DOI | MR | Zbl

[12] Zariski O., “Pencils on an algebraic variety and a new proof of a theorem of Bertini”, Trans. Amer. Math. Soc., 50 (1941), 48–70 | DOI | MR | Zbl