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)



Ideal membership in polynomial rings over the integers

Author: Matthias Aschenbrenner
Translated by:
Journal: J. Amer. Math. Soc. 17 (2004), 407-441
MSC (2000): Primary 13P10; Secondary 11C08
Published electronically: January 15, 2004
MathSciNet review: 2051617
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We present a new approach to the ideal membership problem for polynomial rings over the integers: given polynomials $f_0,f_1,\dots,f_n\in\mathbb Z[X]$, where $X=(X_1,\dots,X_N)$ is an $N$-tuple of indeterminates, are there $g_1,\dots,g_n\in\mathbb Z[X]$ such that $f_0=g_1f_1+\cdots+g_nf_n$? We show that the degree of the polynomials $g_1,\dots,g_n$ can be bounded by $(2d)^{2^{O(N\log(N+1))}}(h+1)$ where $d$ is the maximum total degree and $h$ the maximum height of the coefficients of $f_0,\dots,f_n$. Some related questions, primarily concerning linear equations in $R[X]$, where $R$is the ring of integers of a number field, are also treated.

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

  • 1. M. Aschenbrenner, Bounds and definability in polynomial rings, submitted.
  • 2. -, Kronecker's problem, in preparation.
  • 3. -, Ideal Membership in Polynomial Rings over the Integers, Ph.D. thesis, University of Illinois at Urbana-Champaign, 2001.
  • 4. C. Ayoub, On constructing bases for ideals in polynomial rings over the integers, J. Number Theory 17 (1983), no. 2, 204-225. MR 85m:13017
  • 5. W. Baur, Rekursive Algebren mit Kettenbedingungen, Z. Math. Logik Grundlagen Math. 20 (1974), 37-46.MR 50:4269
  • 6. T. Becker and V. Weispfenning, Gröbner Bases, Graduate Texts in Mathematics, vol. 141, Springer-Verlag, New York, 1993.MR 95e:13018
  • 7. C. Berenstein and A. Yger, Bounds for the degrees in the division problem, Michigan Math. J. 37 (1990), 25-43.MR 91c:32004
  • 8. S. Bosch, U. Güntzer, and R. Remmert, Non-Archimedean Analysis. A Systematic Approach to Rigid Analytic Geometry, Grundlehren der Mathematischen Wissenschaften, vol. 261, Springer-Verlag, Berlin, 1984. MR 86b:32031
  • 9. H. Cohen, A Course in Computational Algebraic Number Theory, Graduate Texts in Mathematics, vol. 138, Springer-Verlag, Berlin, 1993. MR 94i:11105
  • 10. A. Dickenstein, N. Fitchas, M. Giusti, and C. Sessa, The membership problem for unmixed polynomial ideals is solvable in single exponential time, Discrete Appl. Math. 33 (1991), 73-94. MR 92m:13025
  • 11. H. M. Edwards, Kronecker's views on the foundations of mathematics, The History of Modern Mathematics, Vol. I (Poughkeepsie, NY, 1989), Academic Press, Boston, MA, 1989, pp. 67-77. MR 91b:01041
  • 12. T. Evans, Some connections between residual finiteness, finite embeddability and the word problem, J. London Math. Soc. (2) 1 (1969), 399-403. MR 40:2589
  • 13. G. Gallo and B. Mishra, A solution to Kronecker's problem, Appl. Algebra in Engrg. Comm. Comput. 5 (1994), no. 6, 343-370. MR 95i:13026
  • 14. P. Gianni, B. Trager, and G. Zacharias, Gröbner bases and primary decomposition of polynomial ideals, J. Symbolic Comput. 6 (1988), no. 2-3, 149-167. MR 90f:68091
  • 15. R. Gilmer, Multiplicative Ideal Theory, Queen's Papers in Pure and Applied Mathematics, vol. 12, Queen's University, Kingston, Ont., 1968. MR 37:5198
  • 16. S. Glaz, Commutative Coherent Rings, Lecture Notes in Math., vol. 1371, Springer-Verlag, Berlin-Heidelberg-New York, 1989. MR 90f:13001
  • 17. S. Greco and P. Salmon, Topics in $\mathfrak m$-adic Topologies, Ergebnisse der Mathematik und ihrer Grenzgebiete, vol. 58, Springer-Verlag, New York-Berlin, 1971.MR 44:190
  • 18. R. Greenlaw, H. J. Hoover, and W. L. Ruzzo, Limits to Parallel Computation: $P$-Completeness Theory, Oxford University Press, Oxford, 1995.MR 96e:68033
  • 19. K. Hentzelt and E. Noether, Zur Theorie der Polynomideale und Resultanten, Math. Ann. 88 (1923), 53-79.
  • 20. G. Hermann, Die Frage der endlich vielen Schritte in der Theorie der Polynomideale, Math. Ann. 95 (1926), 736-788.
  • 21. A. Kandri-Rody and D. Kapur, Computing a Gröbner basis of a polynomial ideal over a Euclidean domain, J. Symbolic Comput. 6 (1988), no. 1, 37-57.MR 89h:13002
  • 22. J. Kollár, Sharp effective Nullstellensatz, J. Amer. Math. Soc. 1 (1988), 963-975.MR 89h:12008
  • 23. T. Krick, L. M. Pardo, and M. Sombra, Sharp estimates for the arithmetic Nullstellensatz, Duke Math. J. 109 (2001), no. 3, 521-598. MR 2002h:11060
  • 24. S. Lang, Fundamentals of Diophantine Geometry, Springer-Verlag, New York, 1983.MR 85j:11005
  • 25. -, Algebraic Number Theory, 2nd ed., Graduate Texts in Mathematics, vol. 110, Springer-Verlag, New York, 1994. MR 95f:11085
  • 26. E. Mayr, Membership in polynomial ideals over $\mathcal Q$ is exponential space complete, STACS 89 (Paderborn, 1989), Lecture Notes in Comput. Sci., vol. 349, Springer, Berlin, 1989, pp. 400-406.MR 90i:68014
  • 27. E. Mayr and A. Meyer, The complexity of the word problems for commutative semigroups and polynomial ideals, Adv. Math. 46 (1982), no. 3, 305-329.MR 84g:20099
  • 28. G. Moreno Socías, Length of polynomial ascending chains and primitive recursiveness, Math. Scand. 71 (1992), no. 2, 181-205. MR 94d:13019
  • 29. R. O'Leary and J. Vaaler, Small solutions to inhomogeneous linear equations over number fields, Trans. Amer. Math. Soc. 336 (1993), no. 2, 915-931.MR 93f:11032
  • 30. P. Philippon, Dénominateurs dans le théorème des zéros de Hilbert, Acta Arith. 58 (1991), no. 1, 1-25.MR 92i:13008
  • 31. B. Renschuch, Beiträge zur konstruktiven Theorie der Polynomideale. XVII/1. Zur Hentzelt/Noether/Hermannschen Theorie der endlich vielen Schritte, Wiss. Z. Pädagog. Hochsch. ``Karl Liebknecht'' Potsdam 24 (1980), no. 1, 87-99.MR 83d:13003
  • 32. F. Richman, Constructive aspects of Noetherian rings, Proc. Amer. Math. Soc. 44 (1974), 436-441.MR 54:4937
  • 33. D. Roy and J. L. Thunder, Bases of number fields with small height, Rocky Mountain J. Math. 26 (1996), no. 3, 1089-1098. MR 98d:11126
  • 34. K. Schmidt-Göttsch, Polynomial bounds in polynomial rings over fields, J. Algebra 125 (1989), 164-180.MR 91c:12001
  • 35. A. Seidenberg, Constructions in algebra, Trans. Amer. Math. Soc. 197 (1974), 273-313.MR 50:2141
  • 36. -, What is Noetherian?, Rend. Sem. Mat. Fis. Milano 44 (1974), 55-61.MR 54:4938
  • 37. H. Simmons, The solution of a decision problem for several classes of rings, Pacific J. Math. 34 (1970), 547-557.MR 42:1658
  • 38. M. Sombra, A sparse effective Nullstellensatz, Adv. in Appl. Math. 22 (1999), 271-295.MR 2000c:13041
  • 39. S. S. Wainer, A classification of the ordinal recursive functions, Arch. Math. Logik Grundlagenforsch. 13 (1970), 136-153. MR 45:3207

Similar Articles

Retrieve articles in Journal of the American Mathematical Society with MSC (2000): 13P10, 11C08

Retrieve articles in all journals with MSC (2000): 13P10, 11C08

Additional Information

Matthias Aschenbrenner
Affiliation: Mathematical Sciences Research Institute, 17 Gauss Way, Berkeley, California 94720; Department of Mathematics, University of California at Berkeley, Evans Hall, Berkeley, California 94720
Address at time of publication: Department of Mathematics, Statistics, and Computer Science, University of Illinois at Chicago, 851 S. Morgan St. (M/C 249), Chicago, Illinois 60607

Keywords: Ideal membership over the integers, bounds, restricted power series
Received by editor(s): May 2, 2003
Published electronically: January 15, 2004
Additional Notes: Partially supported by the Mathematical Sciences Research Institute
Article copyright: © Copyright 2004 American Mathematical Society

American Mathematical Society