Efficient computation of a semi-algebraic basis of the first homology group of a semi-algebraic set

Abstract

Let $\mathrm{R}$ be a real closed field and $\mathrm{C}$ the algebraic closure of $\mathrm{R}$. We give an algorithm for computing a semi-algebraic basis for the first homology group, ${\mathrm{H}}_1(S,\mathbb{F})$, with coefficients in a field $\mathbb{F}$, of any given semi-algebraic set $S\subset {\mathrm{R}}^k$ defined by a closed formula. The complexity of the algorithm is bounded singly exponentially. It is not known how to compute such a basis for the higher homology groups with singly exponential complexity. As an intermediate step in our algorithm we construct a semi-algebraic subset $\Gamma$ of the given semi-algebraic set $S$, such that ${\mathrm{H}}_q(S,\Gamma )=0$ for $q=0,1$. We relate this construction to a basic theorem in complex algebraic geometry stating that for any affine variety $X$ of dimension $n$, there exists Zariski closed subsets \[ Z^{(n-1)} \supset \cdots \supset Z^{(1)} \supset Z^{(0)} \] with ${\dim }_{\mathrm{C}}{Z}^{(i)}\le i$, and ${\mathrm{H}}_q(X,Z^{(i)})=0$ for $0\le q\le i$. We conjecture a quantitative version of this result in the semi-algebraic category, with $X$ and $Z^{(i)}$ replaced by closed semi-algebraic sets. We make initial progress on this conjecture by proving the existence of $Z^{(0)}$ and $Z^{(1)}$ with complexity bounded singly exponentially (previously, such an algorithm was known only for constructing $Z_0$).

30 pages, 3 figures. Comments welcome