On the Betti numbers of sign conditions

Source abstract

Let R \mathrm {R} be a real closed field and let Q {\mathcal Q} and P {\mathcal P} be finite subsets of R [ X 1 , … , X k ] \mathrm {R}[X_1,\ldots ,X_k] such that the set P {\mathcal P} has s s elements, the algebraic set Z Z defined by ⋀ Q ∈ Q Q = 0 \bigwedge _{Q \in {\mathcal Q}}Q=0 has dimension k ′ k’ and the elements of Q {\mathcal Q} and P {\mathcal P} have degree at most d d . For each 0 ≤ i ≤ k ′ , 0 \leq i \leq k’, we denote the sum of the i i -th Betti numbers over the realizations of all sign conditions of P {\mathcal P} on Z Z by b i ( P , Q ) b_i({\mathcal P},{\mathcal Q}) . We prove that $$b i ( P , Q ) ≤ ∑ j = 0 k ′ − i ( s j ) 4 j d ( 2 d − 1 ) k − 1 . b_i({\mathcal P},{\mathcal Q}) \le \sum _{j=0}^{k’ - i} {s \choose j} 4^{j} d(2d-1)^{k-1}.$$ This generalizes to all the higher Betti numbers the bound ( s k ′ ) O ( d ) k {s \choose k’}O(d)^k on b 0 ( P , Q ) b_0({\mathcal P},{\mathcal Q}) . We also prove, using similar methods, that the sum of the Betti numbers of the intersection of Z Z with a closed semi-algebraic set, defined by a quantifier-free Boolean formula without negations with atoms of the form P ≥ 0 P \geq 0 or P ≤ 0 P\leq 0 for P ∈ P P\in {\mathcal P} , is bounded by $$∑ i = 0 k ′ ∑ j = 0 k ′ − i ( s j ) 6 j d ( 2 d − 1 ) k − 1 , \sum _{i = 0}^{k’}\sum _{j = 0}^{k’ - i} {s \choose j} 6^{j} d(2d-1)^{k-1},$$ making the bound s k ′ O ( d ) k s^{k’} O(d)^k more precise.