Ideal membership in polynomial rings over the integers

Aschenbrenner, Matthias^1, 2

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

Journal of the American Mathematical Society, Tome 17 (2004) no. 2, pp. 407-441

Résumé

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.

Détail

DOI : 10.1090/S0894-0347-04-00451-5

Bibliographie

[1] Ayoub, Christine W. On constructing bases for ideals in polynomial rings over the integers J. Number Theory 1983 204 225

[2] Baur, Walter Rekursive Algebren mit Kettenbedingungen Z. Math. Logik Grundlagen Math. 1974 37 46

[3] Becker, Thomas, Weispfenning, Volker Gröbner bases 1993

[4] Berenstein, Carlos A., Yger, Alain Bounds for the degrees in the division problem Michigan Math. J. 1990 25 43

[5] Bosch, S., Gã¼Ntzer, U., Remmert, R. Non-Archimedean analysis 1984

[6] Cohen, Henri A course in computational algebraic number theory 1993

[7] Dickenstein, Alicia, Fitchas, Noaã¯, Giusti, Marc, Sessa, Carmen The membership problem for unmixed polynomial ideals is solvable in single exponential time Discrete Appl. Math. 1991 73 94

[8] Edwards, Harold M. Kronecker’s views on the foundations of mathematics 1989 67 77

[9] Evans, Trevor Some connections between residual finiteness, finite embeddability and the word problem J. London Math. Soc. (2) 1969 399 403

[10] Gallo, Giovanni, Mishra, Bhubaneswar A solution to Kronecker’s problem Appl. Algebra Engrg. Comm. Comput. 1994 343 370

[11] Gianni, Patrizia, Trager, Barry, Zacharias, Gail Gröbner bases and primary decomposition of polynomial ideals J. Symbolic Comput. 1988 149 167

[12] Gilmer, Robert W. Multiplicative ideal theory 1968

[13] Glaz, Sarah Commutative coherent rings 1989

[14] Greco, Silvio, Salmon, Paolo Topics in 𝔪-adic topologies 1971

[15] Greenlaw, Raymond, Hoover, H. James, Ruzzo, Walter L. Limits to parallel computation: 𝑃-completeness theory 1995

[16] Kandri-Rody, Abdelilah, Kapur, Deepak Computing a Gröbner basis of a polynomial ideal over a Euclidean domain J. Symbolic Comput. 1988 37 57

[17] Kollã¡R, Jã¡Nos Sharp effective Nullstellensatz J. Amer. Math. Soc. 1988 963 975

[18] Krick, Teresa, Pardo, Luis Miguel, Sombra, Martã­N Sharp estimates for the arithmetic Nullstellensatz Duke Math. J. 2001 521 598

[19] Lang, Serge Fundamentals of Diophantine geometry 1983

[20] Lang, Serge Algebraic number theory 1994

[21] STACS 89 1989

[22] Mayr, Ernst W., Meyer, Albert R. The complexity of the word problems for commutative semigroups and polynomial ideals Adv. in Math. 1982 305 329

[23] Moreno Socã­As, Guillermo Length of polynomial ascending chains and primitive recursiveness Math. Scand. 1992 181 205

[24] O’Leary, Robbin, Vaaler, Jeffrey D. Small solutions to inhomogeneous linear equations over number fields Trans. Amer. Math. Soc. 1993 915 931

[25] Philippon, Patrice Dénominateurs dans le théorème des zéros de Hilbert Acta Arith. 1991 1 25

[26] Renschuch, Bodo 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 1980 87 99

[27] Richman, Fred Constructive aspects of Noetherian rings Proc. Amer. Math. Soc. 1974 436 441

[28] Roy, Damien, Thunder, Jeffrey Lin Bases of number fields with small height Rocky Mountain J. Math. 1996 1089 1098

[29] Schmidt-Gã¶Ttsch, Karsten Polynomial bounds in polynomial rings over fields J. Algebra 1989 164 180

[30] Seidenberg, A. Constructions in algebra Trans. Amer. Math. Soc. 1974 273 313

[31] Seidenberg, Abraham What is Noetherian? Rend. Sem. Mat. Fis. Milano 1974

[32] Simmons, H. The solution of a decision problem for several classes of rings Pacific J. Math. 1970 547 557

[33] Sombra, Martã­N A sparse effective Nullstellensatz Adv. in Appl. Math. 1999 271 295

[34] Wainer, S. S. A classification of the ordinal recursive functions Arch. Math. Logik Grundlag. 1970 136 153