Double-exponential lower bound for the degree of any system of generators of a polynomial prime ideal
HTML articles powered by AMS MathViewer
- by
A. L. Chistov
Translated by: The author - St. Petersburg Math. J. 20 (2009), 983-1001
- DOI: https://doi.org/10.1090/S1061-0022-09-01081-4
- Published electronically: October 2, 2009
- PDF | Request permission
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 $\bar {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
- M. Baldassarri, Algebraic varieties, Ergebnisse der Mathematik und ihrer Grenzgebiete, (N.F.), Heft 12, Springer-Verlag, Berlin-Göttingen-Heidelberg, 1956. MR 0082172
- A. L. Chistov, An algorithm of polynomial complexity for factoring polynomials, and determination of the components of a variety in a subexponential time, Zap. Nauchn. Sem. Leningrad. Otdel. Mat. Inst. Steklov. (LOMI) 137 (1984), 124–188 (Russian, with English summary). Theory of the complexity of computations, II. MR 762101
- A. L. Chistov, Efficient construction of local parameters of irreducible components of an algebraic variety, Proceedings of the St. Petersburg Mathematical Society, Vol. 7 (Russian), Tr. St.-Peterbg. Mat. Obshch., vol. 7, Nauchn. Kniga, Novosibirsk, 1999, pp. 230–266 (Russian). MR 1784700
- —, A deterministic polynomial–time algorithm for the first Bertini theorem, Preprint S.-Peterburg. Mat. Obshch. no. 9, 2004, http://www.mathsoc.spb.ru/preprint/.
- Thomas W. Dubé, The structure of polynomial ideals and Gröbner bases, SIAM J. Comput. 19 (1990), no. 4, 750–775. MR 1053942, DOI 10.1137/0219053
- Grete Hermann, Die Frage der endlich vielen Schritte in der Theorie der Polynomideale, Math. Ann. 95 (1926), no. 1, 736–788 (German). MR 1512302, DOI 10.1007/BF01206635
- David Hilbert, Ueber die Theorie der algebraischen Formen, Math. Ann. 36 (1890), no. 4, 473–534 (German). MR 1510634, DOI 10.1007/BF01208503
- Daniel Lazard, Algèbre linéaire sur $K[X_{1},\cdots ,X_{n}]$, et élimination, Bull. Soc. Math. France 105 (1977), no. 2, 165–190 (French). MR 491702
- Ernst W. Mayr and Albert R. Meyer, The complexity of the word problems for commutative semigroups and polynomial ideals, Adv. in Math. 46 (1982), no. 3, 305–329. MR 683204, DOI 10.1016/0001-8708(82)90048-2
- A. Seidenberg, Constructions in algebra, Trans. Amer. Math. Soc. 197 (1974), 273–313. MR 349648, DOI 10.1090/S0002-9947-1974-0349648-2
- Chee-K. Yap, A new lower bound construction for commutative Thue systems with applications, J. Symbolic Comput. 12 (1991), no. 1, 1–27. MR 1124303, DOI 10.1016/S0747-7171(08)80138-1
- Oscar Zariski, Pencils on an algebraic variety and a new proof of a theorem of Bertini, Trans. Amer. Math. Soc. 50 (1941), 48–70. MR 4241, DOI 10.1090/S0002-9947-1941-0004241-4
Bibliographic Information
- A. L. Chistov
- Affiliation: St. Petersburg Branch, Steklov Mathematical Institute, Russian Academy of Sciences, Fontanka 27, 191023 St. Petersburg, Russia
- Email: alch@pdmi.ras.ru
- Received by editor(s): April 10, 2008
- Published electronically: October 2, 2009
- © Copyright 2009 American Mathematical Society
- Journal: St. Petersburg Math. J. 20 (2009), 983-1001
- MSC (2000): Primary 13P10, 14Q20
- DOI: https://doi.org/10.1090/S1061-0022-09-01081-4
- MathSciNet review: 2530898