Why Polynomial Subalgebras Have Their Own Complexity Frontier

Changing the allowed multipliers changes the question

Take the single generator x² in the polynomial ring over the rationals. Its generated ideal contains x³, because x times x² equals x³ and ideal membership permits multiplication by the ambient polynomial x. The subalgebra generated by x² contains constants and combinations of powers of x². Every exponent appearing in such a combination is even, so x³ does not belong. The same input generator therefore yields two different membership answers.

The contrast is not a matter of numerical approximation or choosing a cleverer search. It comes from different closure rules. A subalgebra allows multiplication of elements already constructed inside it. An ideal absorbs multiplication by every polynomial in the larger ring. If an algorithm silently uses the second rule while claiming to solve the first problem, it changes the mathematics. This small example is a useful first check before comparing software or complexity statements that use similar vocabulary.

Membership includes a hidden expression

With two generators x² and x³, the polynomial x⁶ has at least two straightforward construction certificates: the cube of the first generator and the square of the second. The polynomial x⁵ is their product. By contrast, x cannot be obtained, because no product of positive powers of the generators has degree one, and constants cannot create a missing degree by addition. Here the exponent arithmetic makes membership transparent.

For general generators, a certificate is a polynomial in new formal variables that becomes the target after substituting the generators. Its degree and written size may be much larger than the original input. Finding a short input does not guarantee a short explanation of the answer. Even the univariate example x raised to a huge exponent changes character depending on whether exponents are encoded as ordinary digit strings or by fully expanding repeated multiplication. Complexity claims must specify the encoding before input length has a definite meaning.

What the 2025 classification actually says

Kayser's revised paper proves that, over a well-endowed field, general polynomial-subalgebra membership is EXPSPACE-complete, while the homogeneous version is PSPACE-complete. The field assumption formalizes efficient access to the necessary arithmetic. The paper also studies degree bounds and more restricted classes, including monomial subalgebras. These are worst-case classifications in a stated computational model, rather than predictions of how long every small example will take.

PSPACE concerns problems solvable with memory bounded by a polynomial in input length; EXPSPACE permits an exponential amount of memory. Completeness combines an upper bound with reductions demonstrating hardness for the relevant class. It does not provide a stopwatch estimate, and it does not prove that every practical implementation always needs its worst-case memory allocation. The classification identifies the possibility of difficult encoded families. Good performance on a selection of examples is compatible with that conclusion.

Homogeneity gives a useful grading without making everything easy

A polynomial is homogeneous when all its monomials have the same total degree. For example, x² + xy + y² is homogeneous of degree two, while x² + y is not. Multiplication adds degrees, so homogeneous generators give a structured way to organize candidate expressions into graded pieces. This can constrain which combinations might produce a target of a specified degree.

Consider generators u = x² and v = xy. Every product uᵃvᵇ equals x raised to 2a + b times y raised to b. To obtain x³y, solve b = 1 and 2a + b = 3, giving a = 1. To obtain y², the equations demand b = 2 and a = minus 1, which is not allowed for polynomial powers. These are direct membership checks for this particular monomial pair. They show how structural information can help while leaving room for hard families with many generators and more complicated interactions.

For the same pair of generators, nonnegative exponent equations describe every attainable monomial: the exponent of y fixes b, and the remaining x exponent must differ from b by an even nonnegative integer. Thus x⁴y² is attainable with a = 1 and b = 2, whereas x³y² is not. This reasoning works because the generators are monomials and distinct monomial exponents are linearly independent over the field. Replacing them by sums introduces cancellation and changes what this direct exponent test can certify.

The June 2026 result uses a different structural window

Kennerland and Torstensson study finite-codimension subalgebras, including univariate polynomial subalgebras over an algebraically closed field. Their June 2026 paper describes such objects through chains of codimension-one inclusions and associated linear conditions. It proves a finite-intersection description using single-clustered subalgebras and gives a linear-method algorithm for computing conditions in that class. These hypotheses are substantial; the paper does not erase the general multivariate complexity classification.

Finite codimension means that the ambient algebra has only finitely many independent linear directions left after quotienting by the subalgebra as a vector space. For a simple illustration, the algebra generated by x² and x³ contains every monomial of degree at least two and also contains constants. Only the degree-one direction is missing, so its codimension in the full univariate polynomial ring is one. This transparent example explains why finite-dimensional linear data can sometimes describe an infinite set of polynomials.

A derivative condition can encode an entire algebra

Over a field of characteristic zero, consider polynomials whose derivative at zero vanishes. The derivative at zero is exactly the coefficient of x, so these are precisely the polynomials with no linear term. They contain constants, are closed under addition, and are closed under multiplication: the product rule gives the derivative of a product at zero as the first derivative times the second value plus the first value times the second derivative, which is zero when both derivatives vanish.

This algebra is exactly the one generated by x² and x³. Every degree at least two is an even degree or an odd degree at least three, so each corresponding monomial is a power of x² or x³ times a power of x². One linear condition therefore describes infinitely many elements. This worked example is an independent explanation of the appeal of condition-based descriptions; it is not the full single-cluster algorithm from the 2026 paper.

Code helps inspect the reductions

The Max Planck Institute's MathRepo page accompanying Kayser's paper provides Macaulay2 code for the binary-counting homogeneous polynomial algebra in Theorem 4.3. Such a research artifact serves a different purpose from a production membership solver: it makes a construction used in the complexity argument available for inspection. Reproducibility can therefore mean checking the machinery of a reduction, not just repeating a timing table.

For readers, the central question is which structure an algorithm exploits and which structure a hardness construction permits. Number of variables, homogeneity, coefficient field, codimension, generator encoding, and requested certificate format all affect the answer. The recent papers advance different sides of that map. One sharpens the boundary of general tractability; the other extracts usable descriptions from a constrained family. Their coexistence is a guide to asking better computational questions, rather than a contradiction that needs to be resolved.