On a real analog of Bezout inequality and the number of connected components of sign conditions
Sal Barone, Saugata Basu · Proceedings of the London Mathematical Society · 2016
Let R be a real closed field and Q 1 , … , Q ℓ ∈ R [ X 1 , … , X k ] such that for each i , 1 ⩽ i ⩽ ℓ , deg ( Q i ) ⩽ d i . For 1 ⩽ i ⩽ ℓ , denote by Q 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 convention V 0 = R k and k 0 = k ). Suppose also that 2 ⩽ d 1 ⩽ d 2 ⩽ 1 k + 1 d 3 ⩽ 1 ( k + 1 ) 2 d 4 ⩽ ⋯ ⩽ 1 ( k + 1 ) ℓ − 3 d ℓ − 1 ⩽ 1 ( k + 1 ) ℓ − 2 d ℓ , 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 j d ℓ 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 and d ℓ ⩽ 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].