Beiträge zur Algebra und Geometrie Contributions to Algebra and Geometry Volume 39 (1998), No. 1, 1-5.

On Multivariate Descartes’ Rule — A Counterexample

T. Y. Li^{∗} and Xiaoshen Wang^{†}

Department of Mathematics, Michigan State University, East Lansing, MI 48824 e-mail: li@mth.msu.edu

Department of Mathematics,University of Central Arkansas Conway, AR 72035 e-mail: wangx@mth.msu.edu

Abstract. The purpose of this short note is to give a counterexample to a widely known conjecture on multivariate version of Descartes’ rule [2] proposed by I. Itenberg and M.-F. Roy [4]. The famous Descartes’ rule states that the number of positive real zeroes of a univariate polynomial is not greater than the number of sign changes in the list of its coefficients. MSC 1991: 65H10, 50F14, CR: G1.5

Let P_{1}, …, P_{k} be real polynomials in k variables, and let A_{1}, …, A_{k} and Δ_{1}, …, Δ_{k} be the supports and Newton polytopes of these polynomials. Each support A_{i} can be equipped with a distribution δ_{i} of signs at its integer points: a point gets the sign (”+” or ”−”) of the coefficient of the corresponding monomial of the polynomial P_{i}, Each polytope Δ_{i} with a distribution δ_{i} on A_{i} is called a signed Newton diagram and is denoted by Δ̃_{i}.

Let ω_{i} be a real-valued function defined on the set A_{i}. By taking the lower convex hull in R^{k+1} of the graph of ω_{i} and then projecting each facet to R^{k} × {0}, the function ω_{i} induces a polyhedral subdivision [5] τ_{i} of Δ_{i}.

Denote by Δ_{M} the Minkowski sum of the polytopes Δ_{1}, …, Δ_{k} and by A the set

{a ∈ Δ_{M}|a = a_{1} + … + a_{k}, where a_{i} ∈ A_{i}}.

∗Research was supported in part by NSF under Grant DMS - 9504953.

†Research was supported in part by a UCA summer stipend.

0138-4821/93 $ 2.50 \begin{matrix}c \\ ◯ \end{matrix} 1998 Heldermann Verlag

Define ω : A ⟶ R as,

ω(a) = min{ω_{1}(a_{1}) + … + ω_{k}(a_{k})}

for a_{1} + … + a_{k} = a. Such a function ω defines a polyhedral subdivision [3] τ_{ω} of Δ_{M}. The vertices of τ_{ω} belong to A and each polytope F of τ_{ω} has a unique representation

F = F_{1} + ⋮ + F_{k},

where F_{i} is a face of τ_{i}. Suppose the functions ω_{1}, …, ω_{k} are generic; that is, for any polytope F = F_{1} + … + F_{k} of τ_{ω}, we have

dim(F) = dim(F_{1}) + … + dim(F_{k}).

A polytope V = v_{1} + … + v_{k} of τ_{ω} such that

dim(v_{1}) = … = dim(v_{k}) = 1

is called a mixed cell. The mixed volume of A is the sum of the volumes of the mixed cells.

The index of parity p(V) of a mixed cell V = v_{1} +…+v_{k} is defined to be the corank (over Z/2Z) of the matrix V̂ whose rows are composed of the coordinates modulo 2 of the vectors representing the edges v_{1}, …, v_{k}. Let v_{i} be one of the edges of a mixed cell V. We call the edge v_{i} alternating if the distribution of signs δ_{i} associates different signs to the endpoints of v_{i}. A new k × (k + 1) matrix V̄ is defined by adding to V̂ a (k + 1)-th column, its (i, k + 1) -th element equal to 0 if the edge v_{i} is alternating and equal to 1 otherwise. A mixed cell V is called contributing if rank(V̂)= rank(V̄).

Let n(Δ̃, ω) = ∑_{V} 2^{p(V)}, where V ranges over all contributing mixed cells of τ_{ω} and n(Δ̃) be the maximum of n(Δ̃, ω) for all possible choices of generic functions ω_{1}, …, ω_{k}.

To each open orthant m of R^{k} we associate a vector m⃗ from Z/2Z in the following way: for (x_{1} …, x_{k}) belonging to m set the i-th coordinate of m⃗ equal to 0 if x_{i} > 0, and equal to 1 otherwise. To each point a_{i} ∈ A_{i} we also associate a vector a⃗_{i} from Z/2Z by replacing each coordinate of a_{i} by its parity (0 or 1).

The symmetric copy a_{i}^{(m)} of a point a_{i} in an orthant m is a point having the same coordinates as a_{i} equipped with a sign defined by

sign(a_{i}^{(m)}) = (−1)^{a⃗_{i}·m⃗}sign(a_{i})

where a⃗_{i} · m⃗ stands for the scalar product (over Z/2Z) of the vectors a⃗_{i} and m⃗ and sign(a_{i}) stands for the sign associated by δ_{i} to a_{i}. For a mixed cell V = v_{1} +…+v_{k} of the subdivision τ_{ω}, the symmetric copy V^{(m)} of V in an orthant m is called alternating if the endpoints of the symmetric copy of each v_{i} in the orthant m are of different signs. Let n(Δ̃, ω; m) be the number of alternating copies in an orthant m of all mixed cells of τ_{ω} and n(Δ̃; m) be the maximum of n(Δ̃, ω; m) for all possible choices of generic functions ω_{1}, …, ω_{k}.

For a univariate polynomial there are two orthants numbered 0 (corresponding to X > 0) and 1 (corresponding X < 0). A signed Newton diagram is simply a list of pairs of integers and associated signs, listed by increasing order of the integers. A mixed cell is given by two consecutive integers in this list. If the difference of two consecutive integers is even (resp. odd), the index of parity of the cell is 1 (resp. 0). The cell is contributing if its index of parity is 0, or if the index of parity is 1 and the two integers have different associated signs. By choosing ω with increasing slope, the number n(Δ̃, ω, 0) counts the number of sign changes in the list of coefficients [4] and the famous Descartes’ rule [2] states that the number of positive real zeroes of a polynomial is not greater than this number.

The multivariate Descartes’ rule proposed by I. Itenberg and M.-F. Roy [4] is the following:

Suppose that k real polynomials in k variables with signed Newton diagrams Δ̃_{1}, …, Δ̃_{k} have a finite number of common real zeroes. Then

(1) the number of common zeroes of these polynomials in an open orthant m of R^{k} is not greater than n(Δ̃, m);

(2) the number of common zeroes of these polynomials in (R^{∗})^{k} is not greater than n(Δ̃).

Now, let us consider the following polynomial system in C[x_{1}, x_{2}]:

\begin{aligned}p_{1} & =: & −1 − x_{1} + x_{2}, \\ p_{2} & =: & −2 − 9x_{1}^{3} + x_{2}^{3} + 0.01x_{1}^{3}x_{2}^{3} \end{aligned}

with supports

\begin{matrix}A_{1} = \{a = (0, 0), b = (1, 0), c = (0, 1)\}, \\ A_{2} = \{d = (0, 0), e = (3, 0), f = (3, 3), g = (0, 3)\} \end{matrix}

(as shown in Fig. 1 with their associate signs).

There are three solutions of this system in the first quadrant, they are:

(0.317659, 1.317659), (0.659995, 1.659995), and (8.12058, 9.12058).

In the first quadrant m⃗ = (0, 0), so

sign(a_{i}^{(m)}) = (−1)^{0}sign(a_{i}) = sign(a_{i}).

Hence, the possible alternating copies of mixed cells in the first quadrant under all possible choices of generic functions ω_{1} and ω_{2} are as follows:

V_{1} = \overline{ac} + \overline{df}  with Volume(V_{1}) = 3,
V_{2} = \overline{ac} + \overline{ge}  with Volume(V_{2}) = 3,
V_{3} = \overline{bc} + \overline{ef}  with Volume(V_{3}) = 3,
V_{4} = \overline{bc} + \overline{df}  with Volume(V_{4}) = 6,
V_{5} = \overline{bc} + \overline{gd}  with Volume(V_{5}) = 3.

However, the mixed volume of A = A_{1} + A_{2} is equal to [1]:

Volume(Δ_{1} + Δ_{2}) − (Volume(Δ_{2}) + Volume(Δ_{2})) = 15\frac{1}{2} − (9 + \frac{1}{2}) = 6.

Figure 1

Thus, no subdivisions resulting from any choices of ω_{1} and ω_{2} can admit more than 2 alternating copies listed above, for otherwise the sum of their volumes, being the mixed volume of A, would be more than 6. So, statement (1) in the proposed multivariate Descartes’ rule is inaccurate in this case.

In addition to the possible alternating mixed cells listed above, there are eight more possible mixed cells, namely,

V_{6} = \overline{ab} + \overline{dg}  with Volume(V_{6}) = 3,
V_{7} = \overline{ab} + \overline{ef}  with Volume(V_{7}) = 3,
V_{8} = \overline{ab} + \overline{eg}  with Volume(V_{8}) = 3,
V_{9} = \overline{ab} + \overline{df}  with Volume(V_{9}) = 3,
V_{10} = \overline{ac} + \overline{gf}  with Volume(V_{10}) = 3,
V_{11} = \overline{ac} + \overline{de}  with Volume(V_{11}) = 3,

V_{12} = \overline{bc} + \overline{de}  with Volume(V_{12}) = 3,
V_{13} = \overline{bc} + \overline{gf}  with Volume(V_{13}) = 3.

It is easy to check that all those cells V_{1}, …, V_{13} are contributing and the index of parity is 0 for those cells with volumes equal to 3 and is 1 for V_{4}, the only one with volume 6. For any subdivision resulting from any choices of ω_{1} and ω_{2}, it can tolerate either two mixed cells with volume 3 of each, or a single mixed cell with volume 6. In both cases,

n(Δ̃, ω) = ∑_{V} 2^{p(V)} ≤ 2.

Therefore, statement (2) in the conjecture also fails in this case.

References

[1] Bernstein, D.: The number of roots of a system of equations. Functional Analysis and its Applications 9 (1975), 1–4.

[2] Descartes, R.: Géométrie, 1636. In: A source book in Mathematics, Massachusetts, Harvard University Press, 1969, 90–93.

[3] Huber, B.; Sturmfels, B.: A polyhedral method for solving sparse polynomial systems. Math. Comp. 64 (212) (1995), 1541–1555.

[4] Itenberg, I.; Roy, M.-F.: Multivariate Descartes’ rule. Beiträge zur Algebra und Geometrie 37 (1996), 337–346.

[5] Ziegler, G. M.: Lectures on polytopes. vol. 152 of Graduate Texts in Mathematics, Springer-Verlag, New York, 1995.

Received May 15, 1997