Premium
On a real analog of Bezout inequality and the number of connected components of sign conditions
Author(s) -
Barone Sal,
Basu Saugata
Publication year - 2016
Publication title -
proceedings of the london mathematical society
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.899
H-Index - 65
eISSN - 1460-244X
pISSN - 0024-6115
DOI - 10.1112/plms/pdv059
Subject(s) - algebraically closed field , mathematics , dimension (graph theory) , bounded function , combinatorics , upper and lower bounds , field (mathematics) , sign (mathematics) , discrete mathematics , mathematical analysis , pure mathematics
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].