Refined bounds on the number of connected components of sign conditions on a variety

Abstract: Let

R

be a real closed field,

m a t h c a l P, m a t h c a l Q s u b s e t R [X_{1}, ..., X_{k}]

finite subsets of polynomials, with the degrees of the polynomials in

m a t h c a l P

(resp.

m a t h c a l Q

) bounded by

d

(resp.

d_{0}

). Let

V s u b s e t R^{k}

be the real algebraic variety defined by the polynomials in

m a t h c a l Q

and suppose that the real dimension of

V

is bounded by

k^{'}

. We prove that the number of semi-algebraically connected components of the realizations of all realizable sign conditions of the family

m a t h c a l P

on

V

is bounded by

displaylines{sum_{j=0}^{k'}4^j{s +1choose j}F_{d,d_0,k,k'}(j),}

where

s = c a r d; m a t h c a l P

, and

F_{d,d_0,k,k'}(j)= extstyle�inom{k+1}{k-k'+j+1} ;(2d_0)^{k-k'}d^j; max{2d_0,d}^{k'-j} +2(k-j+1) .

In case

2 d_{0} l e q d

, the above bound can be written simply as

displaylines{sum_{j = 0}^{k'} {s+1 choose j}d^{k'} d_0^{k-k'} O(1)^{k} = (sd)^{k'} d_0^{k-k'} O(1)^k}

(in this form the bound was suggested by J. Matousek. Our result improves in certain cases (when

d_{0} l l d

) the best known bound of

sum_{1 leq j leq k'} �inom{s}{j} 4^{j} d(2d-1)^{k-1}

on the same number proved earlier in the case

d = d_{0}

. The distinction between the bound

d_{0}

on the degrees of the polynomials defining the variety

V

and the bound

d

on the degrees of the polynomials in

m a t h c a l P

that appears in the new bound is motivated by several applications in discrete geometry.

Recommendations

Cites Work

Cited In (31)

This page was built for publication: Refined bounds on the number of connected components of sign conditions on a variety