Root Counts and Start Systems

A formal root count can be viewed as a count on the number of solutions of a system with a particular structure. The structure can be determined by the degrees or the Newton polytopes.

Each of the four root counts below is illustrated by a proper example.

total degree

The total degree is the product of the degrees of all polynomials in the system.

from phcpy.starters import total_degree
from phcpy.starters import total_degree_start_system

One family of polynomial systems for which the total degree equals the number of solutions is the Katsura benchmark problem.

from phcpy.families import katsura
k3 = katsura(3)
for pol in k3:
    print(pol)

Our example consists of one linear and three quadrics.

u3 + u2 + u1 + u0 + u1 + u2 + u3 - 1;
u3*u3 + u2*u2 + u1*u1 + u0*u0 + u1*u1 + u2*u2 + u3*u3 - u0;
u3*u3 + u2*u3 + u1*u2 + u0*u1 + u1*u0 + u2*u1 + u3*u2 - u1;
u3*u3 + u2 + u1*u3 + u0*u2 + u1*u1 + u2*u0 + u3*u1 - u2;

The total degree is 8, computed with

degk3 = total_degree(k3)

and the corresponding start system has also 8 solutions, as can be seen from the output of the code cell below.

q, qsols = total_degree_start_system(k3)
len(qsols)

The polynomials in the start system q are shown as

u3^1 - 1;
u2^2 - 1;
u1^2 - 1;
u0^2 - 1;

as output of

for pol in q:
    print(pol)

multihomogeneous Bezout numbers

Most polynomial systems arising in application have far fewer solutions than the total degree.

from phcpy.starters import m_homogeneous_bezout_number
from phcpy.starters import m_homogeneous_start_system"

We illustrate m-homogenous Bezout numbers with an application from game theory.

from phcpy.families import generic_nash_system
game4two = generic_nash_system(4)
for pol in game4two:
    print(pol)"

The (omitted) output of the code cell above shows four cubics. The output of

mbn = m_homogeneous_bezout_number(game4two)
mbn

is the tuple

(9, '{ p2 }{ p3 }{ p4 }{ p1 }')

The tuple on return contains first the root count, and then the partition of the variables. Observe the difference with the total degree, which is 81.

To construct a start system with 9 solutions, respecting the structure of the game4two system, we do:

q, qsols = m_homogeneous_start_system(game4two, partition=mbn[1])
len(qsols)

and we see 9 as the output of len(qsols).

linear-product start systems

The multihomogeneous Bezout numbers are computed based on a partition of the unknowns. This partition is the same for all polynomials in the system. A sharper bound can be obtained if this restriction is relaxed.

from phcpy.starters import linear_product_root_count
from phcpy.starters import random_linear_product_system

The example we use to illustrate this root count consists of cubics.

from phcpy.families import noon
n3 = noon(3)
for pol in n3:
    print(pol)

In dimension three, the system is then

x1*(x2^2 + x3^2) - 1.1*x1 + 1;
x2*(x1^2 + x3^2) - 1.1*x2 + 1;
x3*(x1^2 + x2^2) - 1.1*x3 + 1;

The linear-product root count for this system is computed by the instructions in the cell below:

lprc = linear_product_root_count(n3)
lprc

which gives as output the tuple

(21,
'{ x1 }{ x2 x3 }{ x2 x3 };{ x1 x3 }{ x1 x3 }{ x2 };{ x1 x2 }{ x1 x2 }{ x3 };')

The tuple on return contains first the upper bound on the number of solutions, followed by the set structure used to compute this bound. Every set corresponds to a linear equation in the linear-product start system.

The start system is constructed and solved by the following:

q, qsols = random_linear_product_system(n3, lprc[1])
len(qsols)

and len(qsols) returns 21.

mixed volumes

For sparse polynomial systems, that are systems with relatively few monomials appearing with nonzero coefficients, the mixed volume of the Newton polytopes provides a much sharper bound than any of the degree bounds.

from phcpy.volumes import mixed_volume
from phcpy.volumes import make_random_coefficient_system

The cyclic n-roots problem illustrates the need to apply mixed volumes very well.

from phcpy.families import cyclic
c5 = cyclic(5)
for pol in c5:
    print(pol)

which shows

x0 + x1 + x2 + x3 + x4;
x0*x1 + x1*x2 + x2*x3 + x3*x4 + x4*x0;
x0*x1*x2 + x1*x2*x3 + x2*x3*x4 + x3*x4*x0 + x4*x0*x1;
x0*x1*x2*x3 + x1*x2*x3*x4 + x2*x3*x4*x0 + x3*x4*x0*x1 + x4*x0*x1*x2;
x0*x1*x2*x3*x4 - 1;

The mixed volume equals 70 for this system, and is computed via

mv = mixed_volume(c5)

A random coefficient system has the same monomial structure as the input system, but random coefficients. The start system is made and solved with the code below

vol, q, qsols = make_random_coefficient_system(c5)
len(qsols)

and we see 70 as the output of len(qsols).

The mixed volume does not count the solutions with zero coordinates. To count all solutions, also those with zero coordinates, the stable mixed volume should be computed.

from phcpy.volumes import stable_mixed_volume

Consider the following example.

pols = ['x^3 + x*y^2 - x^2;', 'x + y - y^3;']

The command

stable_mixed_volume(pols)

returns a tuple of two integers. The first number in the tuple is the mixed volume, the second number is the stable mixed volume, which takes into account the solutions with zero coordinates.