On a real analog of Bezout inequality and the number of connected components of sign conditions

Let R be a real closed field andQ 1 , … , Q ℓ ∈ R [ X 1 , … , X k ]such that for each i , 1 ⩽ i ⩽ ℓ , deg ( Q i ) ⩽ d i . For 1 ⩽ i ⩽ ℓ , denote byQ i = { Q 1 , … , Q i } , V i the real variety defined by Q i , and k i an upper bound on the real dimension of V i (by conventionV 0 = R kandk 0 = k ). Suppose also that 2 ⩽ d 1 ⩽ d 2 ⩽ 1 k + 1d 3 ⩽ 1 ( k + 1 ) 2d 4 ⩽ ⋯ ⩽ 1 ( k + 1 ) ℓ − 3d ℓ − 1 ⩽ 1 ( k + 1 ) ℓ − 2d ℓ , and that ℓ ⩽ k . We prove that the number of semi‐algebraically connected components of V ℓ is bounded by O ( k ) 2 k∏ 1 ⩽ j < ℓd j k j − 1 − k jd ℓ k ℓ − 1. This bound can be seen as a weak extension of the classical Bezout inequality (which holds only over algebraically closed fields and is false over real closed fields) to varieties defined over real closed fields. Additionally, if P ⊂ R [ X 1 , … , X k ] is a finite family of polynomials with deg ( P ) ⩽ d for all P ∈ P , card P = s andd ℓ ⩽ 1 k + 1 d , then we prove that the number of semi‐algebraically connected components of the realizations of all realizable sign conditions of the family P restricted to V ℓ is bounded by O ( k ) 2 k( s d ) k ℓ∏ 1 ⩽ j ⩽ ℓd j k j − 1 − k j. These results have found applications in discrete geometry, for proving incidence bounds [11, 31], as well as in efficient range searching [20].