On the cardinality of a semi-algebraic set
Giorgi Nikolaevich Khimshiashvili · Georgian Mathematical Journal · 1994
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 = {fi = 0, gj> 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 fi, gj belonging to the ring Kn 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 = R 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.