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)} \leq i$, and $\mathrm{ H}_q(X,Z^{ (i)}) = 0$ for $0 \leq q \leq 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$).

Categories: math.AG math.AT

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