A solution to Kronecker's problem

Giovanni Gallo, Bhubaneswar Mishra

Research output: Contribution to journalArticlepeer-review

Abstract

Consider ℤ[x1,..., xn], the multivariate polynomial ring over integers involving n variables. For a fixed n, 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 the Kronecker's problem in the context of Kronecker's version of constructive mathematics.

Original languageEnglish (US)
Pages (from-to)343-370
Number of pages28
JournalApplicable Algebra in Engineering, Communication and Computing
Volume5
Issue number6
DOIs
StatePublished - Nov 1994

Keywords

  • Ascending chain condition
  • E-bases
  • Gröbner bases
  • Ideal membership problem
  • Rapidly growing functions
  • Ring of polynomials over the integers
  • S-polynomials
  • Wainer hierarchy
  • syzygies

ASJC Scopus subject areas

  • Algebra and Number Theory
  • Applied Mathematics

Fingerprint Dive into the research topics of 'A solution to Kronecker's problem'. Together they form a unique fingerprint.

Cite this