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

Abstract

Let $\mathbb{R}$ be a real closed field, $\mathcal{Q}\subset \mathbb{R}[Y_1,...,Y_{\ell },X_1,...,X_k],$ with $ °_{Y}(Q) \leq 2, °_{X}(Q) \leq d, Q \in {\mathcal Q}, #({\mathcal Q})=m,$ and $\mathcal{P}\subset \mathbb{R}[X_1,...,X_k]$ with $°_{X}(P) \leq d, P \in {\mathcal P}, #({\mathcal P})=s$, and $S\subset {\mathbb{R}}^{\ell +k}$ a semi-algebraic set defined by a Boolean formula without negations, with atoms $P=0,P\ge 0,P\le 0,P\in \mathcal{P}\cup \mathcal{Q}$. We prove that the sum of the Betti numbers of $S$ is bounded by \[ \ell^2 (O(s+\ell+m)\ell d)^{k+2m}. \] This is a common generalization of previous results 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, generalizing similar algorithms known before. The complexity of the algorithm is bounded by $(\ell smd{)}^{O(m(m+k))}$.

23 pages, 1 figure. Shortened revised version to appear in the J. Eur. Math. Soc

References in corpus (1)

• Symmetry groups, semidefinite programs, and sums of squares

Cited by in corpus (5)

• Distance-regular graphs
• Minimum energy configurations on a toric lattice as a quadratic assignment problem
• Hidden Hamiltonian Cycle Recovery via Linear Programming
• A Semidefinite Program for Structured Blockmodels
• Mutually unbiased bases: polynomial optimization and symmetry