Constructing double-exponential number of vectors of multipilicities of solutions of polynomial systems

Dima Grigoriev^{∗}

Abstract

In [GV] it was proved an upper bound d^{O(\binom{n+d}{n})} on the number of vectors of multiplicities of the solutions of systems of the form g_{1} = ⋯ = g_{n} = 0 (provided, it has a finite number of solutions) of polynomials g_{1}, …, g_{n} ∈ F [X_{1}, …, X_{n}] with the degrees deg(g_{i}) ≤ d. In the present paper we show that this bound is close in order of growth to the exact one. In particular, in case d = n the construction provides a double-exponential (in n) number of vectors of multiplicities.

Introduction

We consider systems g_{1} = ⋯ = g_{n} = 0, g_{i} ∈ F [X_{1}, …, X_{n}] where deg(g_{i}) ≤ d, 1 ≤ i ≤ n and F is an algebraically closed field. To each 0-dimensional component a = (a_{1}, …, a_{n}) ∈ F^{n} of the variety of solutions V = {g_{1} = ⋯ = g_{n} = 0} ⊂ F^{n} one attaches its (finite) multiplicity

m_{a} = dim_{F} (F [X_{1}, …, X_{n}]/(g_{1}, …, g_{n}))_{(X_{1}−a_{1},...,X_{n}−a_{n})} [S].

One attributes to the system g_{1} = ⋯ = g_{n} = 0 the (ordered) vector {m_{a}}_{a} over all 0-dimensional components a of the variety V. Denote by M_{n,d} the number of all possible vectors of the form {m_{a}}_{a}.

It was proved in [GV] that for fields F of zero characteristics in case when dim(V) = 0, we have an upper bound M_{n,d} ≤ d^{O(\binom{n+d}{n})} (majorating M_{n,d} was motivated by the complexity issues, see [GV]). We mention that making use of the machinery of algorithmic perturbations of systems of polynomial equations developped in [CG], one could establish a similar upper bound on M_{n,d} getting rid of the restriction dim(V) = 0. We note that the exponent \binom{n+d}{n} in the bound is the number of the coefficients of polynomials of degree d, in other words, the number of parameters of systems under considerations. One could compare the upper bound from [GV] with the obvious upper bound 2^{O(d^{n})}, taking into account that {m_{a}}_{a} is in fact, a partition of an integer less or equal to d^{n} due to the Bezout inequality [S]. For d < n the bound from [GV] is better than this obvious upper bound.

∗IRMAR, Université de Rennes, Campus de Beaulieu, 35042 Rennes, cedex France

In the present paper we study a question, how sharp is the upper bound on M_{n,d} from [GV]? We prove the following theorem, from which particularly, in case d = n one gets a doubly-exponential (in n) lower bound M_{n,n} ≥ n^{n^{Ω(n^{1/(3+ε)})}} for any ε > 0 (we remind that an asymptotical lower bound f_{1} ≥ Ω(f_{2}) means that f_{1} ≥ cf_{2} for a suitable constant c > 0).

Theorem 1 a) M_{n,d} ≥ d^{d^{Ω(min{d^{1/(3+ε)},n})}} for any ε > 0; b) M_{n,d} ≥ d^{Ω(n)}.

The bound from a) is stronger than the one from b) when d > (Ω(\frac{log n}{log log n}))^{3+ε}. When d > Ω(n^{3+ε}) for a certain ε > 0 then the lower bound in a) d^{d^{Ω(n)}} grows with a similar order as the upper bound 2^{O(d^{n})} (cf. above).

Consider in the Zariski open set of all the systems f_{1} = ⋯ = f_{n} = 0 with a finite number of solutions the (discriminantal) subvariety of systems with at least one multiple solution. The question is whether on every stratum of a Whitney stratification of the discriminantal variety the vector of multiplicities is constant? If this would be true the above theorem would provide a lower bound on the number of strata. We mention that this is a challenging problem to clarify whether the number of strata (say, of a hypersurface) could be double-exponential or just a single-exponential?

Constructing vectors of multiplicities

Now we proceed to the proof of a).

Fix some pairwise distinct points y_{1}, …, y_{k} ∈ F and integers m_{1}, …, m_{k} > 0. Denote L = m_{1} + ⋯ + m_{k} and consider L × L matrix H of the Hermite interpolation as follows. The entry of H in a row (i, j) where 1 ≤ i ≤ k, 0 ≤ j < m_{i} and a column l, 0 ≤ l < L, equals to \binom{l}{j}y_{i}^{l−j} being the coefficient of the expansion of X^{l} in the powers {(X−y_{i})^{s}}_{s} at the power (X−y_{i})^{j}. It is well known that H is non-singular, moreover det(H) = ∏_{1≤p<q≤k}(y_{p} −y_{q})^{m_{p}m_{q}}. In other words, one can assign in an arbitrary way the values of the expansions of a (unique) polynomial of the degree L at the points y_{i}, 1 ≤ i ≤ k up to the powers m_{i} − 1, respectively.

For the sake of simplicity of notations we set m_{1} = … m_{k} = m and denote mk × mk matrix H_{m,k} = H. Denote by H^{(n)} the matrix of the size (mk)^{n}×(mk)^{n} being the n-th tensor power of H_{m,k}. Then H^{(n)} is non-singular and its entries correspond to the coefficients in the expansion of a polynomial of a degree at most mk − 1 with respect to each of n variables X_{1}, …, X_{n} at k^{n} points of the form (x_{1}, …, x_{n}) from the grid R = {y_{1}, …, y_{k}}^{n} ⊂ F^{n} up to the powers m − 1 with respect to each of n variables X_{1} − x_{1}, …, X_{n} − x_{n}. Thus, after assigning in an arbitrary way these coefficients one could find a unique polynomial in n variables X_{1}, …, X_{n} of the degrees at most mk − 1 with respect to each of the variables X_{1}, …, X_{n} just with these assigned coefficients in the expansions.

Choose for each point x = (x_{1}, …, x_{n}) from the grid R n integers 1 ≤ l_{1}, …, l_{n} ≤ m − 1 and take the (unique) family of polynomials f_{1}, …, f_{n} ∈ F [X_{1}, …, X_{n}] of the degrees at most mk − 1 with respect to each of the variables X_{1}, …, X_{n} such that the polynomial f_{j}, 1 ≤ j ≤ n in the expansion at the point x has the unique non-zero term among all the terms of the degrees at most m − 1 with respect to each of the variables X_{1} − x_{1}, …, X_{n} − x_{n}, namely, equal to (X_{j} − x_{j})^{l_{j}}.

The following lemma belongs to the folklore, but we still give its proof for the sake of self-containdness.

Lemma 1 The multiplicity of (the 0-dimensional component) x of the variety of solutions of the system f_{1} = … = f_{n} = 0 equals to l_{1} ⋯ l_{n}.

Proof. Consider the local algebra

A = (F [X_{1}, …, X_{n}]/(f_{1}, …, f_{n}))_{(X_{1}−x_{1},...,X_{n}−x_{n})}.

Clearly, the monomials (X_{1} − x_{1})^{l′_{1}} ⋯ (X_{n} − x_{n})^{l′_{n}} for 0 ≤ l1^{′} < l_{1}, …, 0 ≤

ln^{′} < l_{n} are linearly independent in A. Therefore, it suffices to show that these monomials constitute a basis in A.

Take any monomial G = (X_{1} − x_{1})^{s_{1}} ⋯ (X_{n} − x_{n})^{s_{n}} out of this set. Then s_{j} ≥ l_{j} for a certain 1 ≤ j ≤ n. In the algebra A the element

G = G − f_{j} \frac{G}{(X_{j} − x_{j})^{l_{j}}} ∈ (X_{1} − x_{1}, …, X_{n} − x_{n})^{m}  (1)

After that take any monomial G′ = (X_{1} − x_{1})^{s′_{1}} ⋯ (X_{n} − x_{n})^{s′_{n}} occurring in the latter element of A, then sj′^{′} ≥ m for a suitable 1 ≤ j′ ≤ n. Since m > l_{j′} we have in the algebra A

G′ = G′ − f_{j′} \frac{G′}{(X_{j′} − x_{j′})^{l_{j′}}} ∈ (X_{1} − x_{1}, …, X_{n} − x_{n})^{m+1}

Acting in a similar way with each monomial occurring in (1), we obtain as a result that G equals to a sum of monomials from the ideal A ∩ (X_{1} − x_{1}, …, X_{n} − x_{n})^{m+1}, moreover for any of these monomials (X_{1} − x_{1})^{s′′_{1}} ⋯ (X_{n} −x_{n})^{s′′_{n}} from the sum there exists 1 ≤ j′′ ≤ n such that s′′_{j′′} ≥ m.

Continuing further we conclude that G ∈ ∩_{1≤s<∞}(X_{1} −x_{1}, …, X_{n} −x_{n})^{s}, hence G = 0 due to Nakayama’s lemma (see e.g. [S]). This completes the proof of lemma. □

Thus, for every family of k^{n} integers of the form l_{1} ⋯ l_{n} where 1 ≤ l_{1}, …, l_{n} ≤ m − 1, one can construct a system of polynomials f_{1}, …, f_{n} ∈ F [X_{1}, …, X_{n}] with the multiplicities of the system f_{1} = … = f_{n} = 0 at k^{n} points of the grid R being equal to l_{1} ⋯ l_{n}, respectively. Let us bound from below, how many diverse vectors of multiplicities we have constructed totally.

Because deg(f_{j}) ≤ (km − 1)n the sum of the multiplicities of the 0dimensional solutions of the system f_{1} = … = f_{n} = 0 is less than (kmn)^{n} due to the Bezout inequality. As the integers l_{1}, …, l_{n} we choose the pairwise distinct prime numbers between m/2 and m − 1, so l_{1} ⋯ l_{n} ≥ (m/2)^{n}. Since there are Ω(m/ log m) such prime numbers (according to the law of distribution of prime numbers) we conclude that the number of diverse products of the form l_{1} ⋯ l_{n} is greater than P = \binom{Ω(m/ log m)}{n}, and the number of the con-

structed systems is at least \binom{P}{k^{n}}. Among the multiplicities of 0-dimensional solutions of a system f_{1} = … = f_{n} = 0 there are at most \frac{(kmn)^{n}}{(m/2)^{n}} multiplicities

which are greater or equal to (m/2)^{n}. Therefore, at most \binom{(2kn)^{n}}{k^{n}} of the vectors of multiplicities of the constructed systems of the form f_{1} = … = f_{n} = 0 could coincide with a given one.

Thus, under the condition P ≥ (2kn)^{n(1+ε_{1})} for a certain ε_{1} > 0, the number of diverse vectors of multiplicities of the constructed systems is greater than \binom{P^{Ω(1)}}{k^{n}}. The latter condition would be fulfilled when m > n^{2+ε} for a certain ε > 0 and if one takes k = ⌈(\frac{m}{log m})^{3/(3+ε)} \frac{1}{n^{2}} ⌉ then the number of diverse

vectors of multiplicities would be greater than \binom{P^{Ω(1)}}{k^{n}} > m^{m^{Ω(n)}}. The degrees of the constructed polynomials deg(f_{i}) ≤ kmn. This proves the theorem a) when d > Ω(n^{3+ε_{2}}) for an appropriate ε_{2} > 0.

To complete the proof of the theorem a) when d < O(n^{3+ε}) for any ε > 0 we first apply the above construction for the number of variables n_{0} = ⌈d^{1/(3+ε_{0})}⌉ for an arbitrary ε_{0} > 0, that provides the number of diverse vectors of multiplicities greater than d^{d^{Ω(d^{1/(3+ε_{0})})}}, and the remaining n − n_{0} variables we take as dum and imposing them to vanish. □

Now we proceed to the proof of the theorem b). Fix some constants c_{1}, c_{2} > 0, set s = ⌈c_{1}n⌉ and consider univariate polynomials of the form f = (X − 1)^{m_{1}} ⋯ (X − s)^{m_{s}} with the condition m_{1} ⋯ m_{s} ≤ d^{c_{2}n}. One can realize f as a “modified straight-line program” with three types of elementary operations: addition, multiplication and taking d_{1}-power with d_{1} ≤ d. To realize f at most N = O(log_{d} m_{1} + ⋯ + log_{d} m_{s} + s) operations of described types are sufficient. One can introduce N new variables Z_{1}, …, Z_{N}, we also agree that Z_{0} = X and represent such a “modified straight-line program” as a sequence of N equations of the form either

Z_{j} = Z_{j_{1}} + Z_{j_{2}}, either Z_{j} = Z_{j_{1}}Z_{j_{2}}, either Z_{j} = cZ_{j_{1}} or Z_{j} = Z_{j_{1}}^{d_{1}} (2)

where 1 ≤ j ≤ N, j_{1}, j_{2} < j, c ∈ F, d_{1} ≤ d. Then Z_{N} “calculates” f.

Adjoining to (2) an equation Z_{N} = 0 we obtain as a result a system in F^{N+1} having s solutions with the multiplicities m_{1}, …, m_{s}, respectively. Note that N ≤ O(n). We get greater or equal to d^{c_{2}n} distinct vectors of multiplicities m_{1}, …, m_{s} because to every value of the product m_{1} ⋯ m_{s} corresponds at least one vector m_{1}, …, m_{s}. This completes the proof of the theorem. □

Acknowledgement. The author would like to thank Vitya Vassiliev for useful discussions.

References

[CG] A.Chistov, D.Grigoriev. Subexponential time solving systems of algebraic equations I, II. Preprints LOMI E-9-83, E-10-83, Leningrad, 1983.

[GV] D.Grigoriev, N.Vorobjov. Bounds on the number of vectors of multiplicities for polynomials which are easy to compute. Proc. ACM Intern. Conf. Symbol. and Algebr. Comput., Scotland, 2000, p. 137–145.

[S] I.Shavarevich. Basic algebraic geometry, Springer, 1982.