Georgian Mathematical Journal 1(1994), No. 3, 277-286

ON THE CARDINALITY OF A SEMI-ALGEBRAIC SET

G. KHIMSHIASHVILI

Abstract. It is shown that the cardinality of a finite semi-algebraic subset over a real closed field can be computed in terms of signatures of effectively constructed quadratic forms.

1. The problem under consideration may be described as follows. Let X be a semi-algebraic set over an ordered field K [1]

X = {f_{i} = 0, g_{j} > 0; i ∈ I, j ∈ J} ⊂ K^{n},  (1)

where I and J are some finite sets of indices, and suppose we are a priori guaranteed that X is finite (e.g. it is a part of the zero-set of a nondegenerate polynomial endomorphism). Now the problem is how to estimate its cardinality in some reasonable way without solving any equations.

More formally, there are given f_{i}, g_{j} belonging to the ring K_{n} of polynomials in n variables with coefficients from K and we want to find effectively (by means of some algebraic operations over coefficients of these polynomials) the cardinality #X, i.e. the number of elements in X (geometrically distinct or counted with the multiplicities).

Similar problems for the case when K = ℝ is the usual field of reals often arise in applications [2] and they are well-studied [3]. We will show below that a number of general results may be formulated in terms which are valid in the context of real closed fields. We will not treat the problem in full even for reals preferring to exclude variuos possible degenerations. In fact, cases considered below are principal in the sense that most of reasonable situations may be reduced to them.

From now on we always suppose K to be a real closed field and all points of X to be simple in the sense of the algebraic geometry (i.e. having the multiplicity 1). Thus we are going to deal, in fact, with the number of geometrically distinct points.

1991 Mathematics Subject Classification. 14G30, 58C27.

We will consider two important cases: when X is the zero-set of a nondegenerate endomorphism (i.e. #I = n and f_{i} define a proper endomorphism of K̄^{n}, where K̄ = K(\sqrt{−1}) is the algebraic closure of K), and when one has no inequalities (i.e. J = ∅).

In the first case the solution may be obtained by means of a suitable modification of the classical signature method going back to Hermite and Jacobi [3] which was outlined in [4] and then thoroughly studied in the Candidate Dissertation of T.Aliashvili for the field of reals (see [5]). The proposed generalisation is based on the existence of a purely algebraic definition of the Grothendieck residue symbol [6].

The same approach is also valid in the second case but better results may be obtained by means of more sophisticated algebraical tools used by G.Khimshiashvili [7], also by D. Eisenbud and H.Levine [8], and developed later in [9] and [10]. This enables us to get rid of the multiplicity one assumption, which seems impossible in the framework of the signature method.

In fact, some other approaches, e.g., the so-called Newton polygon method developed in the works of A.G.Khovansky [11], are possible, but the author has never seen any published results of that kind. Moreover, it seems that the named method does not in principle enable one to consider the case when inequalities are really present in the definition of X.

2. Consider now a set X of the type (1) and let f_{j} define a nondegenerate polynomial endomorphism f̄: K̄^{n} → K̄^{n} with simple roots. Nondegeneracy here means as usual the absence of ”roots at the infinity”, that is, the ”leaders” (homogeneous forms of the highest degree deg f_{i}) f_{i}^{∗} have no nontrivial common roots in K̄^{n} [2] (for K = ℝ this is equivalent to f̄ being proper).

The Bezout theorem for real closed fields [12] implies that f̄ has exactly N = ∏ deg f_{j} roots in K̄^{n} so that we have f̄^{−1}(0) = {z_{0}, z_{1} …, z_{N−1}} with z_{i} ≠ z_{j} for i ≠ j.

Without loss of generality we may assume that the first coordinates of roots are pairwise distinct and in such a case we say that the endomorphism is separable. This condition may always be verified effectively in terms of resultants and one can always reduce the problem to this case by performing not more than N(N-1)/2 rotations of the coordinate system.

Write now every root in the form z_{j} = (u_{j}, z′_{j}) with the first coordinate singled out and introduce an auxiliary quadratic form on K^{N} which depends on an arbitrary g ∈ K_{n} :

Q_{f}^{g}(ξ) = ∑_{j=0}^{N−1} g(z_{j})(ξ_{0} + u_{j}ξ_{1} + ⋯ + +u_{j}^{N−1}ξ_{N−1})^{2}.  (2)

It is easy to verify that all coefficients of this form belong to K because here we have a complete analogy with the case of reals. More precisely, the roots which do not belong to K^{n} appear in conjugated pairs with respect to the natural ”complex conjugation” operation in K̄, which implies the assertion.

Recall that one can define as usual the rank rk Q_{f}^{g} and the signature sig Q_{f}^{g} of the form Q_{f}^{g} [1].

The following result provides a multidimensional analogue of the Sturm algorithm [1] and enables one to solve the problem for #J = 1, i.e. for domains of the type {g > 0}.

Theorem 1. If f : K^{n} → K^{n} is a separable polynomial endomorphism over a real closed field K and g ∈ K_{n}, then the rank and signature of the form (2) satisfy the relations:

N − rk Q_{f}^{g} = #(f^{−1}(0) ∩ g^{−1}(0)),  (3)
sig Q_{f}^{g} = #[f^{−1}(0) ∩ {g > 0}] − #[f^{−1}(0) ∩ {g < 0}].  (4)

Denoting by Q_{f} the form (2) for g ≡ 1, we are able to derive some corollaries.

Corollary 1. Under conditions of the theorem the form Q_{f} is nondegenerate and one has:

sig Q_{f} = #f^{−1}(0)  (5)

Corollary 2. Under the same conditions for X = f^{−1}(0) ∩ {g > 0} one has:

#X = ( sig Q_{f} + sig Q_{f}^{g} + rk Q_{f}^{g} − N)/2  (6)

Using some simple combinatorics we may also increase the number of inequalities determining X.

Corollary 3. If besides f^{−1}(0) ∩ g_{j}^{−1}(0) = ∅ holds for every j ∈ J, then

#X = ( ∑_{α} sig Q_{f}^{α})/2^{#J},

where a runs through all multiindices of the form α = (α_{1}, …, α_{k}) with 1 ≤ k ≤ #J and α_{1} < ⋯ < α_{k}, and Q_{f}^{α} = Q_{f}^{g_{α}} with g_{α} = g_{α_{1}} · . . . · g_{k}.

For the sake of simplicity we have excluded here degenerations connected with the presence of roots on boundaries of domains {g_{j} > 0}.

Before presenting the proof of the theorem let us explain why it gives a solution of our problem. It suffices to show that coefficients of the form (2) may be computed by a finite sequence of rational operations over coefficients of f_{j} and g.

After trivial modifications of the formula (2) it is easy to see that the coefficients c_{ij} in the standard presentation of the form Q_{f}^{g}(ξ) = ∑ c_{ij}ξ_{i}ξ_{j} are expressed algebraically in terms of the so-called mixed Newton sums of roots

S_{α}(f) = ∑_{j=0}^{N−1}(z_{j}^{1})^{α_{1}} · . . . · (z_{j}^{n})^{α_{n}},  (7)

where α ∈ (ℤ_{+})^{n}, z_{j} = (z_{j}^{1}, …, z_{j}^{n}), j = 0, 1, …, N − 1.

In fact, certain sums S_{α} may be easily computed using iterated resultants. For example, this is so for small |α| and for ”pure” Newton sums with only one nonzero α_{j} and this enables one already to provide the separation of roots, which was the original classical problem [3]. There are some hints in [3] about such a possibility but without any details and with a remark that this is not a universal method. For n = 2 the storage of easily computable Newton sums was described by T.Aliashvili who has also shown using the Hilbert theorem on invariants that all Newton sums may be computed algebraically in this case [4], [5]. Unfortunately, this approach is not constructive and it meets with serious difficulties for arbitrary n.

For K = ℝ a radical tool for suppressing this difficulties is provided by an ingenious algebraic device called the Grothendieck residue symbol [6, 13]. It was shown in [7] and [8] how this residue serves to compute the topological degree of a smooth map-germ and so we naturally used it in our situation. In fact, here we need the global variant of this notion which was outlined in [6] and further investigated in [13].

For the sake of completeness we recall that the global residue of a polynomial g ∈ ℝ_{n} with respect to a nondegenerate endomorphism f ∈ (ℝ_{n})^{n} is defined by the integral

Res_{f}g = \frac{1}{(2πi)^{n}} ∫_{Γ_{R}} \frac{g(z)}{f_{1}(z) · . . . · f_{n}(z)} dμ,  (8)

where the cycle Γ_{R} = {z ∈ ℂ^{n} : |f_{j}(z)| = R for j = 1, …, n} is defined for sufficiently large R > 0, its orientation is induced by the differential form d(arg f_{1}) ∧ ⋯ ∧ d(arg f_{n}) and the integral is taken with respect to the usual Lebesque measure.

This integral doesn’t depend on R and vanishes on the ideal (f) generated by the components of f in ℝ_{n} [13]. Moreover, if all roots of f are simple, one has the relation

Res_{f}g = ∑_{z∈f^{−1}(0)} \frac{g(z)}{J_{f}(z)},  (9)

where J_{f}(z) = det(∂f_{j}/∂z_{k})(z) is the Jacobian of f.

Now it is clear that in the situation of Theorem 1 we have

S_{α}(f) = Res_{f}(J_{f}e_{α}),  (10)

where α ∈ (ℤ_{+})^{n}, e_{α} = x_{1}^{α_{1}} · . . . · x_{n}^{α_{n}} is a monomial in ℝ_{n}.

Consequently, it remains to show that Res_{f}g itself can be computed by the coefficients of f and g. This circumstance should not seem strange because the global residue is the sum of local residues [13] and the latter are known to be algebraically computable but, of course, a technical difficulty arises here because we cannot assume the positions z_{j} of local residues are known.

Nevertheless, it turns out that the situation can be saved by means of a clever use of the transformation formula for global residues [13]. In fact, one may always reduce the problem to the case of the so-called ”pure powers” f_{j} = z_{j}^{k_{j}}, where it is trivialized. The necessary transformation can be obtained from the so-called Hefer decomposition of polynomials f_{j} and all the procedures rise up to algorithms. We have no space here for presenting details which may be borrowed from [13], but for future generalizations it is important to notice that the main point was just the transformation formula. Thus we conclude that the Newton sums can be also computed algebraically, which gives a principal solution of our problem.

Now we observe that the same arguments can be used also for an arbitrary real closed field K because there exists a pure algebraic definition of the Grothendieck residue symbol [6] which generalizes (8) and possesses the same functorial properties.

As was already mentioned, a straightforward analysis of the residue computation in [13] shows that it uses, in fact, only the formal properties of residues and therefore also extends to the general case.

Thus we arrive to the following conclusion which complements Theorem 1 and completes the desired solution.

Theorem 2. Under the conditions of Theorem 1 coefficients of the form Q_{f}^{g} may be algebraically expressed through coefficients of given polynomials.

Now it is time to return to the proof of Theorem 1 which proceeds as follows. Write first f̄^{−1}(0) in the form f̄^{−1}(0) = {x_{1}, ..., x_{r}, z_{1}, ..., z_{k}, z̄_{1}, ..., z̄_{k}}, where x_{1}, …, x_{r} ∈ K^{n}, z ∉ K^{n}, r + 2k = N, which is always possible in virtue of the observation following the formula (2).

Define now a linear transformation T in K^{N} by the formulas

\begin{cases}η_{j} = ξ_{0} + ξ_{1}u_{j} + ⋯ + ξ_{N−1}u_{j}^{N−1}, & j = 1, …, r; \\ η_{r+j} = Re(ξ_{0} + ⋯ + ξ_{N−1}u_{r+j}^{N−1}), & j = 1, …, k; \\ η_{r+k+j} = Im(ξ_{0} + ⋯ + ξ_{N−1}u_{r+j}^{N−1}), & j = 1, …, k. \end{cases}

Evidently, this transformation diagonalizes our form, this immediately implying (3) and (4). It remains to verify that this is a genuine change of coordinates, that is its determinant is nonzero. Anyone who is fond of linear algebra can easily compute it by reducing it to a Vandermonde of the first coordinates which is nonzero due to the separability of f. Another way is to observe that the form Q_{f} becomes nondegenerate; hence rk T ≥ N, which again finishes the proof. ■

All corollaries become immediate now. We have only to introduce numbers m_{α} of roots belonging to U_{α} = ∩{g_{α_{k}} > 0} and to sum up all relations (4) for functions g_{α}, which terminates all the numbers m except the required m_{1,...,n} = #X.

Turning again to the proof of Theorem 2 we shall also point out that there were two nearly equivalent possibilities of deducing the general case from the case of real numbers. Firstly, one can mimic the algorithm from [13] referring to the properties of the general notion from [6]. Secondly, one can directly define the global residue Res_{f}g by the formula presented in [13], page 60, and verify that it possesses all necessary properties forcing it to coincide with the residue from [6].

In both cases details are routine and we have omitted them. In fact, the shortest though a little mistifying way is concerned with the Zaidenberg– Tarski principle [12], which makes all these troubles unnecessary as soon as a formula for Res_{f} is proven for reals so that the proof of our generalization becomes complete.

Nevertheless, we preferred to recall the analytical formula for the global residue having in mind an effective algorithm for dealing with the problem in practice, which is by no means available by the Zaidenberg–Tarski yoga.

A number of curious questions arise here. For example, one can try to estimate the computational complexity of corresponding algorithms and compare it with that of the cylindrical decomposition method from [14]. When g = J_{f} and we are dealing with the topological degree of f necessary estimates were obtained by T.Aliashvili [5] and they witness in favour of the approach outlined above.

3. Let now X be an affine algebraic subset of K^{n}, that is a set of the type (1) with J = ∅. We are going to describe an ano ther solution of our problem also valid without assuming that all points of X are simple.

As is well known, every such subset may be represented as a hypersurface X = {F = 0} with F = f_{1}^{2} + ⋯ + f_{#I}^{2} so that we may assume that X is a hypersurface consisting of a finite number of points. At first glance such an object may seem unusual but the point is that for a hypersurface one can always compute its Euler characteristic in a pure algebraic form as in [7, 9, 10]. In our situation the Euler characteristic simply reduces to the number of geometrically distinct points so that we become able to give a very concise solution of our problem.

The discussion below can be adapted for arbitrary real closed fields, but this requires some caution and additional work so that we consider here only the case when K = ℝ.

Recall that we deal with the usual Euler characteristic χ(X) which is the alternated sum of homology groups ranks (Betti numbers) of a topological space X under consideration. We write deg_{p} f for the local degree of an endomorphism f : ℝ^{n} → ℝ^{n} in an isolated preimage of the origin p ∈ f^{−1}(0) which is defined as the topological degree of a mapping f̂ = f/∥f∥ : S_{ε}^{n−1}(p) → S_{1}^{n−1}(0) = S^{n−1}.

All the results below are based on the following formulas obtained by the author in [7].

Theorem 3. Let F : ℝ^{n} → ℝ be a polynomial with an isolated singularity at the origin. Then for a sufficiently small enough λ > 0 one has

χ({F < λ} ∩ B_{δ}^{n}) = 1 + (−1)^{n−1} deg_{0}(grad F),  (11)

where B_{δ}^{n} is a ball of the small radius δ.

If the polynomial F is homogeneous then for sufficiently small λ, δ > 0 one has also the equality

χ({F ≥ 0} ∩ S_{δ}^{n−1}) = 1 + (−1)^{n−1} deg_{0}(grad F).  (12)

These results are local but there is a natural link with the global ones provided by the projectivization.

With this in mind, suppose that f_{1}, …, f_{p} are homogeneous polynomials of the degrees d_{1} ≤ d_{2} ≤ ⋯ ≤ d_{p} , respectively. Then, besides X, they also define a projective algebraic variety V_{f} in ℝℙ^{n−1} which can also be determined by a single homogeneous polynomial f = ∑ f_{j}^{2} · ∥x∥^{2(d_{p}−d_{j})} of the degree 2d_{p}, where ∥x∥ is the usual euclidean norm of x ∈ ℝ^{n}. Now it is not difficult to tie together the invariants of X with those of its projectivization using the following lemma established in [10].

Lemma. Under these conditions for all λ ≠ 0 the polynomial F_{λ} = f^{2} − λ^{2}(∑ x_{j}^{2d+2}) has an isolated singularity at 0 and for a sufficiently small |λ| the real hypersurface {F_{λ} = 0} does not have singularities inside small balls and is transversal to their boundaries. Moreover, denoting Z = {x ∈ S_{1}^{n−1} : f(x) = 0}, Z_{λ} = {x ∈ S_{1}^{n−1} : F_{λ}(x) ≤ 0}, one has that Z_{λ}\Z is diffeomorphic to Y_{λ} × (0, λ], where Y_{λ} = {x ∈ S_{1}^{n−1} : F_{λ}(x) = 0}.

Collecting together these observations, we are able to obtain the final result.

Theorem 4. Let f_{1}, …, f_{p} ∈ ℝ_{n} be real polynomials of degrees not exceeding d. Suppose that they have only a finite number M of real common zeroes. Set

h_{i}(x_{0}, x_{1}, …, x_{n}) = x_{0}^{d+1}f_{i}(x_{1}/x_{0}, …, x_{n}/x_{0}),

H = ∑_{i=1}^{p} h_{i}^{2} − ∑_{k=0}^{n} x_{k}^{2d+4}.

Then H has an algebraically isolated critical point at the origin and the following equality holds:

M = [(−1)^{n} − deg_{0}(grad H)]/2.  (13)

Proof. Evidently, all polynomials h_{j} are homogeneous of the degree d + 1, which enables us to transplant considerations on the unit sphere S^{n} ⊂ ℝ^{n+1} and use the lemma.

With this purpose we introduce a subset Y = S^{n} ∩ {h_{1} = ⋯ = h_{p} = 0} and observe that Y = Y_{+}∪Y_{−}∪S^{n−1} with Y_{±} = {x ∈ S^{n} : ±x_{0} > 0, h_{1}(x) = ⋯ = h_{p}(x) = 0}.

Evidently, Y_{+} and Y_{−} are homeomorphic to X so that we obtain χ(Y) = 2χ(X)−χ(S^{n−1}) or, equivalently, χ(X) = [χ(Y)+χ(S^{n−1})]/2 and it remains to compute χ(Y), which is already possible using (11) for H.

Working with homology with integer coefficients, in virtue of the Lefshetz duality [2] we obtain

χ(S\Y) = ∑(−1)^{k} rk H_{k}(S\Y) = ∑(−1)^{k} rk H_{n−k−1}(S, Y) =
= (−1)^{n+1}χ(S, Y) = (−1)^{n+1}[χ(S) − χ(Y)] =
= (−1)^{n}χ(Y) + (−1)^{n+1} + 1.

On the other hand, applying the lemma to H instead of F one gets S\Y = (S ∩ {F_{λ} ≤ 0}) ∪ (S ∩ {F_{λ} ≤ 0}).

The first set is fibred in virtue of the lemma and the second one cannot contain any points of Y because there we have ∑ x_{j}^{2d+4} > 0. Consequently, we obtain

χ(S\Y)=χ({F_{λ} =0} ∩ S)+χ({F_{λ} ≥0} ∩ S)−χ({F_{λ} =0} ∩ S)=
=χ({F_{λ} ≥ 0})=1 + (−1)^{n+1} deg_{0}(grad F_{λ}).

This naturally implies

χ(Y) = (−1)^{n}[(−1)^{n} + (−1)^{n+1} deg_{0}(grad F_{λ})] = 1 − deg_{0}(grad F_{λ}).

Now, our lemma yields that the family F provides an admissible homotopy with F_{1} = H so that we may put λ = 1 and get χ(Y) = 1 − deg_{0}(grad H), which immediately gives (13) and finishes the proof.

Granted formula (13) we have only to observe that the local topological degree is algebraically computable being, in fact, equal to the signature of an effectively constructible quadratic form on the coordinate algebra of a given mapping [7, 8]. Thus, we obtain another way of computing #X, which turns out to be more convenient and effective than the method of §2.

One could now combine our results with those on algorithmic computation of the local degree in order to estimate the computational complexity of this method. We shall not pursue this topic here but rather make several remarks in conclusion.

An interesting open problem is to generalize all these things for arbitrary real closed fields. In fact, most of necessary algebraical and topological notions are also available in the general case. One has only to obtain a formula expressing the local Euler characteristic in terms of the local topological degree as in [7]. The author feels that a portion of the semi-algebraic topology in the spirit of [15] should be helpful here. One could also try to combine this with the discussion of real singularities in [16].

Some concrete results become more or less immediate now. For example, one can directly verify a result of R.Thom stating that the number of cusps of a stable smooth mapping from the real projective plane into real plane is always odd because such maps may be approximated by rational ones given by ratios of polynomials of even degrees for which the result follows directly from the formula (11). Perhaps, some other ”oddity results” may be obtained in a similar manner.

One can also give a closed algebraical formula for the number of cusps of a polynomial Whitney mapping (stable mapping of ℝ^{2} in itself) which complements recent results of K.Aoki and T.Fukuda [17] and provides sharp estimates for such numbers.

References

1. S. Lang, Algebra. Addison–Wesley, New York, 1965.

2. I. Shafarevich, Foundations of Algebraic Geometry. (Russian) ”Nauka”, Moscow, 1972.

3. M. Krein and M. Neimark, Method of quadratic forms for separation of roots of polynomials. (Russian) ”GNTI”, Kharkov, 1936.

4. G. Khimshiashvili, On the number of zeroes of a real polynomial endomorphism. Bull. Acad. Sci. Georgia, 146(1992), No.3, 469-473.

5. T. Aliashvili, On the topological degree of a polynomial endomorphism. (Russian) Collection of works in the homology theory. 6. (Russian) Trudy Tbiliss. Mat. Inst. Razmadze 103, to appear.

6. R. Hartshorne, Residues and Duality. Lect. Notes Math.11, Springer, Berlin etc., 1971.

7. G. Khimshiashvili, On the local degree of a smooth mapping. (Russian) Soobsch. Akad. Nauk Gruzin. SSR 85(1977), No.2, 27-30.

8. D. Eisenbud and H. Levine, An algebraic formula for the degree of a smooth map-germ. Ann. Math. 106(1977), No.1, 64-79.

9. Z. Szafraniec, On the Euler characteristics of real algebraic varieties. Topology, 25(1986), No.3, 253-259.

10. J. Bruce, The Euler characteristic of a real affine algebraic variety. Bull. Lond. Math. Soc. 22(1990), No.4, 213-219.

11. A. Khovansky, Newton polyedra. (Russian) Current problems in mathematics. Fundamental directions, vol. 36 (Russian), 75-110, Itogi Nauki i Tekhniki, Akad. Nauk SSSR, Vsesoyuzn. Inst. Nauchn. i Tekh. Inform., Moscow, 1990.

12. J. Bochnak, J. Cost and M.-F. Roy, Geometrie Algebrique Réelle. Springer, Berlin etc., 1988.

13. A. Tsikh, Multidimensional residues and their applications. (Russian) ”Nauka”, Novosibirsk, 1988.

14. J. Davenport, Y. Siret and E. Tournier, Calcul formel. Masson, Paris, 1987.

15. H. Delfs and M. Knebush, Algebraic varieties over real closed fields. Lect. Notes Math. 1173, Springer, Berlin etc., 1985.

16. J. Milnor, Singular points of complex hypersurfaces. Princeton Lecture Notes, Princeton, 1967.

17. K. Aoki and T.Fukuda, On the number of branches of zero loci. Top. and Comp. Sci. 3(1987), 347-363.

(Received 15.01.1993)

Author’s address: A.Razmadze Mathematical Institute Georgian Academy of Sciences 1, Z.Rukhadze St., 380093 Tbilisi Republic of Georgia