Bounding the Betti numbers and computing the Euler–Poincaré characteristic of semi-algebraic sets defined by partly quadratic systems of polynomials

Bounding the Betti numbers and computing the Euler–Poincaré characteristic of semi-algebraic sets defined by partly quadratic systems of polynomials

Let R be a real closed field, Q ⊂ R[Y1 , . . . , Yl, X1 , . . . , Xk], with degY(Q) ≤ 2, degX(Q) ≤ d, Q ∈ Q, #(Q) = m, and P ⊂ R[X1, . . . , Xk] with degX(P) ≤ d, P ∈ P, #(P) = s, and S ⊂ Rl+k a semi-algebraic set defined by a Boolean formula without negations, with atoms P = 0, P ≥ 0, P ≤ 0, P ∈ P ∪...

Full description

Saved in:
Bibliographic Details
Main Authors: Basu, Saugata, Roy, Marie-Françoise, Pasechnik, Dmitrii V.
Other Authors: School of Physical and Mathematical Sciences
Format: Article
Language:English
Published: 2013
Subjects:
DRNTU::Science::Mathematics::Algebra
Online Access:https://hdl.handle.net/10356/98233
http://hdl.handle.net/10220/9277
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Nanyang Technological University
Language: English
Description
Summary:Let R be a real closed field, Q ⊂ R[Y1 , . . . , Yl, X1 , . . . , Xk], with degY(Q) ≤ 2, degX(Q) ≤ d, Q ∈ Q, #(Q) = m, and P ⊂ R[X1, . . . , Xk] with degX(P) ≤ d, P ∈ P, #(P) = s, and S ⊂ Rl+k a semi-algebraic set defined by a Boolean formula without negations, with atoms P = 0, P ≥ 0, P ≤ 0, P ∈ P ∪ Q. We prove that the sum of the Betti numbers of S is bounded by l2 (O(s + l + m)ld)k+2m. This is a common generalization of previous results in [4] and [3] on bounding the Betti numbers of closed semi-algebraic sets defined by polynomials of degree d and 2, respectively. We also describe an algorithm for computing the Euler–Poincaré characteristic of such sets, e generalizing similar algorithms described in [4, 9]. The complexity of the algorithm is bounded by (lsmd)O(m(m+k)).

Similar Items