Computational Complexity of Polynomial Subalgebras

Leonie Kayser · 2025

Read Computational Complexity of Polynomial Subalgebras by Leonie Kayser (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-05278.txt.

Introduction

Leonie Kayser asks how hard it is, in computing terms, to test whether a given polynomial belongs to a set built from other polynomials. Her 2025 paper studies polynomial subalgebras, a topic close to the older study of ideals and their Gröbner bases. Interest in fast methods for these sets has grown in recent years.

Kayser pins down the cost of the membership test and of bounds on polynomial degree. The general problem turns out to fill a very high cost class, while the uniform-degree case sits one level lower. She draws out where the subalgebra setting matches the ideal setting and where it parts ways. Special families, such as sets built from single-term polynomials, get separate treatment in the paper.

Catalog record

CREATORLeonie Kayser
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE44 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2502-05278

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Computational Complexity of Polynomial Subalgebras Leonie Kayser Abstract The computational complexity of polynomial ideals and Gröbner bases has been studied since the 1980s. In recent years, the related notions of polynomial subalgebras and SAGBI bases have gained more and more attention in computational algebra, with a view towards effective algorithms. We investigate the computational complexity of the subalgebra membership problem and degree bounds. In particular, we show completeness for the complexity class EXPSPACE and prove PSPACE -completeness for homogeneous algebras. We highlight parallels and differences compared to the settings of ideals, and also look at important classes of polynomials such as monomial algebras. 1 Introduction Let \mathbb{K} be a field equipped with a suitable encoding over a finite alphabet, for example, the rational numbers \mathbb{Q} or a finite field \mathbb{F}_{q} . At the heart of many algorithms in computer algebra lie efficient algorithms manipulating polynomial ideals and Gröbner bases, dating back at least to the 1960s [ 5 ] . Since the late 1980s, algorithms for computations with subalgebras have been studied [ 29 , 27 ] , which have applications in toric degenerations and polynomial system solving [ 3 ] . A fundamental computational problem for ideals and subalgebras of polynomial rings \mathbb{K}[{\underline{x}}]=\mathbb{K}[x_{1},\dots,x_{n}] is deciding membership . Of special interest are classes C of polynomials such as homogeneous polynomials ( Homog ), monomials ( Mon ), or polynomials with bounded degree or number of variables. \textsc{IdealMem}_{\mathbb{K}}(\textsf{C}) , \textsc{IdealMem}_{\mathbb{K}} Input: f_{1},\dots,f_{s}\in\textsf{C} (or \mathbb{K}[{\underline{x}}] ); g\in\mathbb{K}[{\underline{x}}] Output: Is g\in\langle f_{1},\dots,f_{s}\rangle ? \textsc{AlgMem}_{\mathbb{K}}(\textsf{C}) , \textsc{AlgMem}_{\mathbb{K}} Input: f_{1},\dots,f_{s}\in\textsf{C} (or \mathbb{K}[{\underline{x}}] ); g\in\mathbb{K}[{\underline{x}}] Output: Is g\in\mathbb{K}[f_{1},\dots,f_{s}] ? Recall that g\in\langle f_{1},\dots,f_{s}\rangle if and only if there is a representation g=h_{1}f_{1}+\dots+h_{s}f_{s} with h_{1},\dots,h_{s}\in\mathbb{K}[{\underline{x}}] ; the representation degree (of the tuple f_{1},\dots,f_{s},g ) is the smallest possible value of D=\max\{\deg h_{1},\dots,\deg h_{s}\} . Similarly, g\in\mathbb{K}[f_{1},\dots,f_{s}] if and only if g=p(f_{1},\dots,f_{s}) for some certificate p\in\mathbb{K}[t_{1},\dots,t_{s}] ; we call the smallest possible degree of p the certification degree . The computational complexity and representation degree bounds of \textsc{IdealMem}_{\mathbb{K}} and its variants have been studied since the 1980s, we give a brief overview in Section 2.3 . The complexity of algebras in a more general sense has been studied before [ 18 ] , though so far not for the concrete case of polynomial subalgebras. This paper is concerned with filling this gap and proving analogous results for \textsc{AlgMem}_{\mathbb{K}} and bounds on the certification degree. In order to obtain reasonable upper bounds on the computational complexity, we assume that arithmetic in the base field \mathbb{K} can be performed efficiently; this is formalized as being well-endowed [ 4 ] . A main theorem is the EXPSPACE - and PSPACE -completeness of the subalgebra membership problem and the homogeneous variant, combining the upper bounds Theorem 3.1 and 3.4 and the complementing lower bound Theorem 4.2 . 1.1 . Over a well-endowed field \mathbb{K} , the subalgebra membership problem \emph{\textsc{AlgMem}}_{\mathbb{K}} is EXPSPACE -complete and the homogeneous version \emph{\textsc{AlgMem}}_{\mathbb{K}}(\textsf{{Homog}}) is PSPACE -complete. One of the goals of this paper is to be accessible both to commutative algebraists and computer scientists. For this reason, we introduce the relevant results from algebra and complexity theory on ideals and Gröbner bases in Section 2 . In Section 3 we prove various upper bound results on variations of \textsc{AlgMem}_{\mathbb{K}} , as well as an upper bound on the certification degree. In Section 4 we present a complexity-theoretic reduction from \textsc{IdealMem}_{\mathbb{K}} to \textsc{AlgMem}_{\mathbb{K}} , proving matching lower bounds. In Section 5 we study the case of monomial subalgebras, which is still NP -complete, and discuss related questions with SAGBI bases. 2 Background in algebra and complexity theory 2.1 Ideals, subalgebras and their bases Let \mathbb{K} be a field, denote by \mathbb{K}[{\underline{x}}]\coloneqq\mathbb{K}[x_{1},\dots,x_{n}] the polynomial ring in n variables, consisting of finite linear combinations f=\sum_{\alpha\in\mathbb{N}^{n}}c_{\alpha}x^{\alpha},\qquad x^{\alpha}=x_{1}^{\alpha_{1}}\dotsm x_{n}^{\alpha_{n}},\quad c_{\alpha}\in\mathbb{K}. Ideals and subalgebras arise naturally in algebra as the kernels and images of ( \mathbb{K} -linear) ring homomorphisms. We briefly recall the basic definitions for both of them in parallel. 2.1 . A subset I\subseteq\mathbb{K}[{\underline{x}}] is an ideal if it is an additive subgroup (contains 0 and is closed under addition and subtraction) and also closed under multiplication with arbitrary polynomials f\in\mathbb{K}[{\underline{x}}] . A subset A\subseteq\mathbb{K}[{\underline{x}}] is a subalgebra if it is an additive subgroup containing \mathbb{K} and is closed under multiplication within A . Given a set S\subseteq\mathbb{K}[{\underline{x}}] , we denote by \displaystyle\langle S\rangle \displaystyle=\Set{\sum_{\text{finite}}h_{i}f_{i}}{\!\!\!\begin{array}[]{c}f_{i}\in S,\\ h_{i}\in\mathbb{K}[{\underline{x}}]\end{array}\!\!\!}=\set{\text{lin.\ comb.\ of $S$ over $\mathbb{K}[{\underline{x}}]$}} \displaystyle\mathbb{K}[S] \displaystyle=\Set{\sum_{\text{finite}}c_{\alpha}f^{\alpha}}{\!\!\!\begin{array}[]{c}f_{i}\in S,\\ c_{\alpha}\in\mathbb{K}\end{array}\!\!\!}=\set{\text{polynomial expressions in $S$}} the ideal and subalgebra generated by S ; it is the smallest ideal resp. subalgebra containing S . 2.2 . An important class of ideals and algebras are those generated by monomials x^{\alpha} , or binomials x^{\alpha}-x^{\beta} . For example, monomial algebras show up as coordinate rings of affine toric varieties, and binomial ideals are related to commutative Thue systems, capturing the combinatorial worst-case complexity of ideal membership (see Theorem 2.12 ). 2.3 . A monomial order \prec is a total order on the set of monomials x^{\alpha} stable under multiplication ( x^{\alpha}\preceq x^{\beta} implies x^{\alpha}x^{\gamma}\preceq x^{\beta}x^{\gamma} ) and such that 1=x^{0} is the minimal element. The initial term \ini_{\prec}(f) of a nonzero polynomial f=\sum_{\alpha}c_{\alpha}x^{\alpha} is the nonzero term c_{\alpha}x^{\alpha} with the largest monomial. For convenience define \ini_{\prec}(0)=0 . Given an ideal I or a subalgebra A , its initial ideal or initial algebra, respectively, is \ini_{\prec}(I)=\langle\set{\ini_{\prec}(f)}{f\in I}\rangle,\quad\ini_{\prec}(A)=\mathbb{K}[\set{\ini_{\prec}(f)}{f\in A}]. In the following fix such a monomial order, for example, the lexicographic order \prec_{\text{lex}} ; we may assume x_{1}>\dots>x_{n} . 2.4 . A Gröbner basis of an ideal I is a finite subset G\subseteq I such that \ini_{\prec}(I)=\langle\set{\ini_{\prec}(g)}{g\in G}\rangle . A Gröbner basis is reduced if the leading coefficients are 1 and no term of g\in G is in \ini_{\prec}(G\setminus\{g\}) . On the other hand, a SAGBI basis of a subalgebra A is any subset S\subseteq A such that \ini_{\prec}(A)=\mathbb{K}[\set{\ini_{\prec}(f)}{f\in S}] . In both cases, such bases generate I and A respectively, hence the (historical) name “basis” . The reduced Gröbner basis of an ideal I is unique and has the smallest number of elements and smallest degree among all Gröbner bases of I . For more background on Gröbner bases see for example [ 7 , Chapter 2] , [ 15 , Chapter 21] or [ 19 , Chapter 2] . By Hilbert’s basis theorem , every ideal can be generated by a finite set of polynomials; in fact one can find such a finite set in any generating set. This implies the existence of (finite) Gröbner bases for any ideal. On the other hand, finite SAGBI bases may not exist; we will come back to this topic in Section 5.1 . 2.5 . Given an ideal I\subseteq\mathbb{K}[{\underline{x}}] , the normal form \NF_{\prec}(f,I) of an element f\in\mathbb{K}[{\underline{x}}] against I is the unique polynomial r\in f+I such that no monomial of r is in \ini_{\prec}(I) [ 19 , Definition 2.4.8] . One can compute \NF_{\prec}(f,I) by dividing f by a Gröbner basis G , the remainder is the normal form [ 7 , Proposition 2.6.1] . This gives a membership test for polynomial ideals: f\in I if and only if \NF_{\prec}(f,I)=0 . 2.2 Complexity theory We use the Turing model of computation, though the details of this formalism are not required to follow

Read the complete text