The Ideal Membership Problem and Abelian Groups
Open Access
- 4 May 2026
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Computation Theory
- Vol. 18 (2) , 1-34
Abstract
Given polynomials f 0 , f 1 , …, f k the Ideal Membership Problem, IMP for short, asks if f 0 belongs to the ideal generated by f 1 , …, f k . In the search version of this problem, the task is to find a proof of this fact. The IMP is a well-known fundamental problem with numerous applications. For instance, it underlies many proof systems based on polynomials such as Nullstellensatz, Polynomial Calculus, and Sum-of-Squares. Although the IMP is in general intractable, in many important cases it can be efficiently solved. Mastrolilli [SODA’19] initiated a systematic study of IMPs for ideals arising from Constraint Satisfaction Problems (CSPs), parameterized by constraint languages, denoted IMP(Γ). The ultimate goal of this line of research is to classify all such IMPs accordingly to their complexity. Mastrolilli achieved this goal for IMPs arising from CSP(Γ) where Γ is a Boolean constraint language, while Bulatov and Rafiey [STOC’22] advanced these results to several cases of CSPs over finite domains. In this article, we consider IMPs arising from CSPs over “affine” constraint languages, in which constraints are subgroups (or their cosets) of direct products of Abelian groups. This kind of CSPs include systems of linear equations and are considered one of the most important types of tractable CSPs. Some special cases of the problem have been considered before by Bharathi and Mastrolilli [MFCS’21] for linear equations modulo 2, and by Bulatov and Rafiey [STOC’22] for systems of linear equations over GF ( p ), p prime. Here, we prove that if Γ is an affine constraint language then IMP(Γ) is solvable in polynomial time assuming the input polynomial has bounded degree.Keywords
Funding Information
- NSERC Discovery
This publication has 25 references indexed in Scilit:
- Representing and solving finite-domain constraint problems using systems of polynomialsAnnals of Mathematics and Artificial Intelligence, 2013
- Dualities for Constraint Satisfaction Problems2008
- Bruno Buchberger’s PhD thesis 1965: An algorithm for finding the basis elements of the residue class ring of a zero dimensional polynomial idealJournal of Symbolic Computation, 2006
- Membership in polynomial ideals over Q is exponential space complete2005
- An Algebraic Approach to Multi-sorted ConstraintsLecture Notes in Computer Science, 2003
- Gröbner Bases1993
- The membership problem for unmixed polynomial ideals is solvable in single exponential timeDiscrete Applied Mathematics, 1991
- The complexity of the word problems for commutative semigroups and polynomial idealsAdvances in Mathematics, 1982
- Galois theory for post algebras. ICybernetics and Systems Analysis, 1972
- Die Frage der endlich vielen Schritte in der Theorie der PolynomidealeMathematische Annalen, 1926