Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

 PolynomialIdealDimension

Source Notebook

Compute the dimension of a polynomial ideal

Contributed by: Daniel Lichtblau

ResourceFunction["PolynomialIdealDimension"][polys,vars]

computes the dimension of the ideal defined by polys in the polynomial ring ℚ[vars].

Details and Options

PolynomialIdealDimension computes the Krull dimension of an ideal.
PolynomialIdealDimension supports a Modulus option (default 0). If nonzero, the modulus p must be prime. It will regard the polynomials as belonging to the ring ℤp[vars].
Unknowns in the input polynomials that are not specified in vars are regarded as parameters, that is, they lie in the coefficient field.
An ideal containing 1 is considered to have dimension -1.

Examples

Basic Examples (3) 

Find the dimension of an ideal defined by three polynomials in five variables:

In[1]:=
polys = {x^2*y + 3*w*x*z - 4, t*y^2 - w^2*x*y + t*z + 2*x - 3, w*x^2*y + 2*t^2*x*z^2 - 5*w*y*z^2 + 7}; vars = {t, w, x, y, z}; ResourceFunction["PolynomialIdealDimension"][polys, vars]
Out[3]=

When we remove the first variable and regard it as a coefficient parameter the dimension decreases by 1:

In[4]:=
ResourceFunction["PolynomialIdealDimension"][polys, Rest@vars]
Out[4]=

If instead we remove the first polynomial then the dimension increases by 1:

In[5]:=
ResourceFunction["PolynomialIdealDimension"][Rest@polys, vars]
Out[5]=

Scope (3) 

Find an ideal dimension:

In[6]:=
polys = {x^2*y + 3*w*x*z - 6, t*y^2 - 9*w^2*x*y + 6 t*z + 12*x - 3, w*x^2*y + 3*t^2*x*z^2 - 14*w*y*z^2 + 12}; vars = {t, w, x, y, z}; ResourceFunction["PolynomialIdealDimension"][polys, vars]
Out[8]=

Provide a nonzero modulus:

In[9]:=
ResourceFunction["PolynomialIdealDimension"][polys, vars, Modulus -> Prime[1234]]
Out[9]=

For most prime moduli the dimension is the same as in the case of working over the rationals, but there can be finitely many exceptions:

In[10]:=
Table[ResourceFunction["PolynomialIdealDimension"][polys, vars, Modulus -> Prime[j]], {j, 10}]
Out[10]=

Properties and Relations (4) 

Square systems typically have dimension zero; we show this in particular for the Cassou-Nouges benchmark polynomial ideal:

In[11]:=
cnpolys = {15*b^2*c*d^2 + 6*b^2*c^3 + 21*b^2*c^2*d - 144*b*c - 8*b*c^2*e - 28*b*c*d*e - 648*b*d + b*d^2*e + 9*b^2*d^3 - 120, 30*b^2*c^3*d - 32*c*d*e^2 - 720*b*c*d - 24*b*c^3*e - 432*b*c^2 + 576*c*e - 576*d*e + 16*b*c*d^2*e + 16*d^2*e^2 + 16*c^2*e^2 + 9*b^2*c^4 + 5184 + 39*b^2*c^2*d^2 + 18*b^2*c*d^3 - 432*b*d^2 + 24*b*d^3*e - 16*b*c^2*d*e - 240*c, 216*b*c*d - 162*b*d^2 - 81*b*c^2 + 5184 + 1008*c*e - 1008*d*e + 15*b*c^2*d*e - 15*b*c^3*e - 80*c*d*e^2 + 40*d^2*e^2 + 40*c^2*e^2, 261 + 4*b*c*d - 3*b*d^2 - 4*b*c^2 + 22*c*e - 22*d*e}; cnvars = {b, c, d, e}; ResourceFunction["PolynomialIdealDimension"][cnpolys, cnvars]
Out[13]=

Adding a polynomial makes the system overdetermined, so the dimension becomes -1:

In[14]:=
ResourceFunction["PolynomialIdealDimension"][ Append[cnpolys, b*c^2 - 3*c*d + e^3 - 7], cnvars]
Out[14]=

Here is a benchmark example from an ISSAC 2001 conference paper with more polynomials than variables; it arose in the context of locating all singular points on a particular algebraic curve:

In[15]:=
g0 = -84 + 41*x + 23*y + 99*x^2*y^5 - 61*x^2*y^4 - 50*x^2*y^3 - 12*x^2*y^2 - 18*x^2*y - 26*x*y^7 - 62*x*y^6 + x*y^5 - 47*x*y^4 - 91*x*y^3 - 47*x*y^2 + 66*x^3*y - 55*x^7*y - 35*x^6*y^2 + 97*x^6*y + 79*x^5*y^3 + 56*x^5*y^2 + 49*x^5*y + 57*x^4*y^4 - 59*x^4*y^3 + 45*x^4*y^2 - 8*x^4*y + 92*x^3*y^5 + 77*x^3*y^2 + 54*x^3 + 53*y^6 + 31*x^2 - 90*y^7 - 58*y^8 - 85*x^8 - 37*x^7 - 86*y^2 + 50*x^6 + 83*y^3 + 63*x^5 + 94*y^4 - 93*x^4 - y^5 - 5*x^2*y^6 - 61*x*y + 43*x^3*y^4 - 62*x^3*y^3; h0 = -76 - 53*x + 88*y + 66*x^2*y^5 - 29*x^2*y^4 - 91*x^2*y^3 - 53*x^2*y^2 - 19*x^2*y + 68*x*y^6 - 72*x*y^5 - 87*x*y^4 + 79*x*y^3 + 43*x*y^2 + 80*x^3*y - 50*x^6*y - 53*x^5*y^2 + 85*x^5*y + 78*x^4*y^3 + 17*x^4*y^2 + 72*x^4*y + 30*x^3*y^2 + 72*x^3 - 23*y^6 - 47*x^2 - 61*y^7 + 19*x^7 - 42*y^2 + 88*x^6 - 34*y^3 + 49*x^5 + 31*y^4 - 99*x^4 - 37*y^5 - 66*x*y - 85*x^3*y^4 - 86*x^3*y^3; f0 = Expand[g0*h0]; polys = {f0, D[f0, x], D[f0, y]};

Such a polynomial ideal can still have dimension 0 rather than -1; we use a nonzero modulus for speed:

In[16]:=
ResourceFunction["PolynomialIdealDimension"][polys, {x, y}, Modulus -> Prime[123456]]
Out[16]=

Possible Issues

As with any computation that requires computing a Gröbner basis, this function can be slow.

Version History

  • 1.0.0 – 08 May 2023

Source Metadata

Related Resources

Author Notes

Possible extensions include (i) allowing for approximate coefficients (ii) Using random slicing hyperplanes to determine when solution set is zero dimensional (# planes required = dimension)

License Information