Remote Access St. Petersburg Mathematical Journal

St. Petersburg Mathematical Journal

ISSN 1547-7371(online) ISSN 1061-0022(print)



Double-exponential lower bound for the degree of any system of generators of a polynomial prime ideal

Author: A. L. Chistov
Translated by: The author
Original publication: Algebra i Analiz, tom 20 (2008), nomer 6.
Journal: St. Petersburg Math. J. 20 (2009), 983-1001
MSC (2000): Primary 13P10, 14Q20
Published electronically: October 2, 2009
MathSciNet review: 2530898
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: 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 $ \widebar{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.

References [Enhancements On Off] (What's this?)

  • 1. M. Baldassarri, Algebraic varieties, Ergeb. Math. Grenzgeb., Heft 12, Springer-Verlag, Berlin, 1956. MR 0082172 (18:508f)
  • 2. A. L. Chistov, An algorithm of polynomial complexity for factoring polynomials, and finding the components of varieties in subexponential time, Zap. Nauchn. Sem. Leningrad. Otdel. Mat. Inst. Steklov. (LOMI) 137 (1984), 124-188; English transl., J. Soviet Math. 34 (1986), no. 4, 1838-1882. MR 0762101 (86g:11077b)
  • 3. -, Efficient construction of local parameters of irreducible components of an algebraic variety, Trudy S.-Peterburg. Mat. Obshch., vol. 7, Nauchn. Kniga, Novosibirsk, 1999, pp. 230-266; English transl. in Amer. Math. Soc. Transl. Ser. 2, vol. 203, Amer. Math. Soc., Providence, RI, 2001. MR 1784700 (2002b:14081)
  • 4. -, A deterministic polynomial-time algorithm for the first Bertini theorem, Preprint S.-Peterburg. Mat. Obshch. no. 9, 2004,
  • 5. T. W. Dubé, The structure of polynomial ideals and Gröbner bases, SIAM J. Comput. 19 (1990), 750-775. MR 1053942 (91h:13021)
  • 6. G. Hermann, Die Frage der endlich vielen Schritte in der Theorie der Polynomideale, Math. Ann. 95 (1926), 736-788. MR 1512302
  • 7. D. Hilbert, Über die Theorie der algebraischen Formen, Math. Ann. 36 (1890), 473-534. MR 1510634
  • 8. D. Lazard, Algèbre linéaire sur $ k[x_1, \ldots, x_n]$ et élimination, Bull. Soc. Math. France 105 (1977), 165-190. MR 0491702 (58:10905)
  • 9. E. W. Mayr and A. R. Meyer, The complexity of the word problems for commutative semigroups and polynomial ideals, Adv. Math. 46 (1982), 305-329. MR 0683204 (84g:20099)
  • 10. A. Seidenberg, Constructions in algebra, Trans. Amer. Math. Soc. 197 (1974), 273-313. MR 0349648 (50:2141)
  • 11. Chee K.  Yap, A new lower bound construction for commutative Thue systems, with applications, J. Symbolic Comput. 12 (1991), 1-27. MR 1124303 (92i:03046)
  • 12. O. Zariski, Pencils on an algebraic variety and a new proof of a theorem of Bertini, Trans. Amer. Math. Soc. 50 (1941), 48-70. MR 0004241 (2:345a)

Similar Articles

Retrieve articles in St. Petersburg Mathematical Journal with MSC (2000): 13P10, 14Q20

Retrieve articles in all journals with MSC (2000): 13P10, 14Q20

Additional Information

A. L. Chistov
Affiliation: St. Petersburg Branch, Steklov Mathematical Institute, Russian Academy of Sciences, Fontanka 27, 191023 St. Petersburg, Russia

Keywords: Polynomial ideal, projective algebraic variety, Gr\"obner basis, effective algebraic geometry.
Received by editor(s): April 10, 2008
Published electronically: October 2, 2009
Article copyright: © Copyright 2009 American Mathematical Society

American Mathematical Society