Ideal membership in polynomial rings over the integers
By Matthias Aschenbrenner. 2003
62 citations recorded by the source corpus.
We will reproduce a proof, using Hermann's classical method, in Section 3 below. Note that the computable character of this bound reduces the question of whether fo G (fi,..., fn) for given fj G F[X] to solving an (enormous) system of linear equations over F. Hence, in this way one obtains a (naive) algorithm for solving the ideal membership problem for F[X] (provided F is given in some explicitly computable manner). Later, Buchberger in his Ph.D. thesis (1965) introduced the important concept of a Gr?bner basis and gave an algorithm for deciding ideal membership for F[X] which is widely used today (see, e.g., [6]). The doubly exponential nature of ? above is essentially unavoidable, as a family of examples due to Mayr and Meyer [27] shows. In fact, they prove that ideal membership for Q[X] is exponential-space hard: the amount of space needed by any algorithm to decide ideal membership for Q[X] (or Z[X]) grows exponentially in the size of the input. If we restrict to/o,...,/n ofa special form, often dramatic
Subfields: Algebra and Number Theory, Computational Theory and Mathematics, Geometry and Topology
View Paper: https://www.semanticscholar.org/paper/ae9c6cffbf526cd658badc7b19845105d9470f9b
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Algebra and Number Theory
In Computational Theory and Mathematics
In Geometry and Topology
Citations in the corpus
- Heights of varieties in multiprojective spaces and arithmetic Nullstellensatze (2011, methodology): “In particular, they apply to problems in complexity and computability [16, 1, 9], to counting problems over finite fields or over the rationals [4, 34], and to effectivity in existence results in arithmetic geometry [17, 3].”