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

preprint2011arXivOpen access

Abstract

Let R\R be a real closed field, P,Q⊂R[X1,...,Xk]\mathcal{P},\mathcal{Q} \subset \R[X_1,...,X_k] finite subsets of polynomials, with the degrees of the polynomials in P\mathcal{P} (resp. Q\mathcal{Q}) bounded by dd (resp. d0d_0). Let V⊂RkV \subset \R^k be the real algebraic variety defined by the polynomials in Q\mathcal{Q} and suppose that the real dimension of VV is bounded by k′k'. We prove that the number of semi-algebraically connected components of the realizations of all realizable sign conditions of the family P\mathcal{P} on VV is bounded by $$ \displaylines{\sum_{j=0}^{k'}4^j{s +1\choose j}F_{d,d_0,k,k'}(j),}$$ where $s = \card \; \mathcal{P}$, and Fd,d0,k,k′(j)=(k+1k−k′+j+1)  (2d0)k−k′dj  max⁡2d0,dk′−j+2(k−j+1).F_{d,d_0,k,k'}(j)= \textstyle\binom{k+1}{k-k'+j+1} \;(2d_0)^{k-k'}d^j\; \max{2d_0,d}^{k'-j} +2(k-j+1) . In case 2d0≤d2 d_0 \leq 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 d0≪dd_0 \ll d) the best known bound of ∑1≤j≤k′(sj)4jd(2d−1)k−1 \sum_{1 \leq j \leq k'} \binom{s}{j} 4^{j} d(2d-1)^{k-1} on the same number proved earlier in the case d=d0d=d_0. The distinction between the bound d0d_0 on the degrees of the polynomials defining the variety VV and the bound dd on the degrees of the polynomials in P\mathcal{P} that appears in the new bound is motivated by several applications in discrete geometry.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.