# Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

Count the roots to a system of polynomials

Contributed by:
Daniel Lichtblau

ResourceFunction["CountPolynomialSolutions"][ counts the number of solutions of the polynomial system given by | |

ResourceFunction["CountPolynomialSolutions"][ counts the number of solutions in terms of the variables in |

ResourceFunction["CountPolynomialSolutions"] counts all solutions over the complex numbers.

ResourceFunction["CountPolynomialSolutions"] counts solutions by multiplicity.

If the solution set has dimension greater than zero then ResourceFunction["CountPolynomialSolutions"] will return Infinity.

If the input has coefficients that are approximate numerical values then ResourceFunction["CountPolynomialSolutions"] will use approximate arithmetic. This can fail if precision is not sufficient for the method used.

The input for *polys* can be either a list of polynomials or a list of polynomial equations. In the former case the system in question is obtained by setting all polynomials to zero. The set of zeros is known as the variety defined by the polynomials.

If there are parameters then the count will be based on generic values for those parameters. For special cases the solution count might be either smaller or infinite (but never both finite and larger).

If the precision is finite and there are parameters then random values of that precision will be substituted for them before assessing the count.

If no *vars* are specified then the variables will be taken as Variables[*polys*] (so there will be no parameters in this situation). The *vars* list must be provided explicitly in order to have some unknowns regarded as variables.

ResourceFunction["CountPolynomialSolutions"] uses a method related to one of those used by NSolve, wherein a Gröbner basis is computed and the normal set is found.

ResourceFunction["CountPolynomialSolutions"] is typically more efficient than Solve since it does not attempt to form the solutions and also can use a (typically) more efficient term ordering.

In contrast to NSolve, ResourceFunction["CountPolynomialSolutions"] will use exact methods provided the input system is exact and WorkingPrecision is set to either Automatic (the default) or Infinity.

One can sometimes improve speed using a non-default MonomialOrder option setting.

One can count solutions in an algebraic closure of a prime field using the Modulus option. For all but finitely many primes this will agree with the solution count over the complexes. This gives a probabilistic method that is often facter than working over the complexes.

Count the number of solutions to a bivariate system:

In[1]:= |

Out[2]= |

Compare to the number of solutions produced by Solve:

In[3]:= |

Out[3]= |

Compare instead to the number of solutions produced by NSolve:

In[4]:= |

Out[4]= |

Count the solutions to a trivariate system with two polynomials of degree 3 and one of degree 4:

In[5]:= |

Out[6]= |

Count the solutions to a larger system:

In[7]:= |

Out[8]= |

Count the solutions to an "offset" system, wherein the polynomials are set equal to nonzero constants:

In[9]:= |

Out[9]= |

Coefficients need not be rational:

In[10]:= |

Out[11]= |

This is somewhat faster than explicitly solving the system:

In[12]:= |

Out[12]= |

It is faster still to do the computation at modest finite precision:

In[13]:= |

Out[13]= |

Coefficients can be parameters, that is, unknown values:

In[14]:= |

Out[15]= |

We check that this is in fact the count for a specific set of parameter values:

In[16]:= |

Out[16]= |

An overdetermined system often will have no solutions:

In[17]:= |

Out[17]= |

A system of *n* polynomials in *n* variables might fail to have a finite solution set:

In[18]:= |

Out[19]= |

If we allow *z* to be a parameter then the solution count is finite:

In[20]:= |

Out[20]= |

This is a test system from an ISSAC 2001 conference paper:

In[21]:= |

It is quite slow to handle at exact precision:

In[22]:= |

Out[22]= |

It can be done quite efficiently at a working precision of 200 digits:

In[23]:= |

Out[23]= |

This is moreover several times faster than numerically solving the system at the same precision:

In[24]:= |

Out[24]= |

A more extreme example comes from a 2009 ISSAC conference paper:

In[25]:= |

Out[26]= |

NSolve on this example is 2-3 orders of magnitude slower:

In[27]:= |

Out[27]= |

Again, using a probabilistic approach, we count solutions in a certain prime field; with high probability this will agree with the total over the complexes:

In[28]:= |

Out[28]= |

Provide a weight matrix for the term ordering:

In[29]:= |

Out[30]= |

Use a prime modulus to count solutions for a large system:

In[31]:= |

Out[32]= |

This can be done much faster using a monomial order that is particularly well-suited for this system:

In[33]:= |

Out[34]= |

The Caprasse system has 32 distinct solutions:

In[35]:= |

Out[36]= |

A count by multiplicity shows a larger value:

In[37]:= |

Out[37]= |

If we slightly perturb the system then Solve will find 56 distinct solutions in agreement with CountPolynomialSolutions:

In[38]:= |

Out[39]= |

Inconsistent results can arise if the system (taken from this Mathematica.StackExchange post) has coefficients with low precision:

In[40]:= |

Out[41]= |

We can get a different count by raising the precision:

In[42]:= |

Out[42]= |

As is indicated in the StackExchange thread, there are further subtleties-- six of the eight solutions are quite large:

In[43]:= |

Out[44]= |

This is because the exact system from which this was taken lives on the "discriminant variety" for systems with the same polynomial structure but having generic coefficients. Had we an exact form for the coefficients, these six would not be present (they go to infinity as the coefficients approach the discriminant variety).

One can isolate to the two expected solutions with some amount of trial and error in setting the Tolerance option of GroebnerBasis:

In[45]:= |

Out[46]= |

- StackExchange thread about root counting from 2014
- Similar StackExchange thread from 2023
- StackExchange thread from 2016 for handling the parametrized case

Wolfram Language 13.0 (December 2021) or above

This work is licensed under a Creative Commons Attribution 4.0 International License