A solution to Kronecker's problem |
| |
Authors: | Giovanni Gallo Bhubaneswar Mishra |
| |
Affiliation: | (1) Dipartimento di Matematica, Universitá di Catania, Italia;(2) Courant Institute of Mathematical Sciences, New York University, 715/719 Broadway, 12th Floor, 10003 New York, NY |
| |
Abstract: | Consider [x1,...,xn], the multivariate polynomial ring over integers involvingn variables. For a fixedn, we show that the ideal membership problem as well as the associated representation problem for [x1,...,xn] are primitive recursive. The precise complexity bounds are easily expressible by functions in the Wainer hierarchy.Thus, we solve a fundamental algorithmic question in the theory of multivariate polynomials over the integers. As a direct consequence, we also obtain a solution to certain foundational problem intrinsic to Kronecker's programme for constructive mathematics and provide an effective version of Hilbert's basis theorem. Our original interest in this area was aroused by Edwards' historical account of theKronecker's problem in the context of Kronecker's version of constructive mathematics.Supported by an Italian grant Italian MURST 40% Calcolo Algebraico e Simbolico 1993 and an NSF grant: #CCR-9002819. |
| |
Keywords: | Ascending chain condition E-bases Grö bner bases Ideal membership problem Rapidly growing functions Ring of polynomials over the integers S-polynomials syzygies Wainer hierarchy |
本文献已被 SpringerLink 等数据库收录! |
|