Search for: All records

Abstract Designing an algorithm with a singly exponential complexity for computing semialgebraic triangulations of a given semialgebraic set has been a holy grail in algorithmic semialgebraic geometry. More precisely, given a description of a semialgebraic set$$S \subset \mathbb {R}^k$$by a first-order quantifier-free formula in the language of the reals, the goal is to output a simplicial complex$$\Delta $$, whose geometric realization,$$|\Delta |$$, is semialgebraically homeomorphic toS. In this paper, we consider a weaker version of this question. We prove that for any$$\ell \geq 0$$, there exists an algorithm which takes as input a description of a semialgebraic subset$$S \subset \mathbb {R}^k$$given by a quantifier-free first-order formula$$\phi $$in the language of the reals and produces as output a simplicial complex$$\Delta $$, whose geometric realization,$$|\Delta |$$is$$\ell $$-equivalent toS. The complexity of our algorithm is bounded by$$(sd)^{k^{O(\ell )}}$$, wheresis the number of polynomials appearing in the formula$$\phi $$, andda bound on their degrees. For fixed$$\ell $$, this bound issingly exponentialink. In particular, since$$\ell $$-equivalence implies that thehomotopy groupsup to dimension$$\ell $$of$$|\Delta |$$are isomorphic to those ofS, we obtain a reduction (having singly exponential complexity) of the problem of computing the first$$\ell $$homotopy groups ofSto the combinatorial problem of computing the first$$\ell $$homotopy groups of a finite simplicial complex of size bounded by$$(sd)^{k^{O(\ell )}}$$. 

Abstract Given a sequence $$\{Z_d\}_{d\in \mathbb{N}}$$ of smooth and compact hypersurfaces in $${\mathbb{R}}^{n-1}$$, we prove that (up to extracting subsequences) there exists a regular definable hypersurface $$\Gamma \subset {\mathbb{R}}\textrm{P}^n$$ such that each manifold $$Z_d$$ is diffeomorphic to a component of the zero set on $$\Gamma$$ of some polynomial of degree $$d$$. (This is in sharp contrast with the case when $$\Gamma$$ is semialgebraic, where for example the homological complexity of the zero set of a polynomial $$p$$ on $$\Gamma$$ is bounded by a polynomial in $$\deg (p)$$.) More precisely, given the above sequence of hypersurfaces, we construct a regular, compact, semianalytic hypersurface $$\Gamma \subset {\mathbb{R}}\textrm{P}^{n}$$ containing a subset $$D$$ homeomorphic to a disk, and a family of polynomials $$\{p_m\}_{m\in \mathbb{N}}$$ of degree $$\deg (p_m)=d_m$$ such that $$(D, Z(p_m)\cap D)\sim ({\mathbb{R}}^{n-1}, Z_{d_m}),$$ i.e. the zero set of $$p_m$$ in $$D$$ is isotopic to $$Z_{d_m}$$ in $${\mathbb{R}}^{n-1}$$. This says that, up to extracting subsequences, the intersection of $$\Gamma$$ with a hypersurface of degree $$d$$ can be as complicated as we want. We call these ‘pathological examples’. In particular, we show that for every $$0 \leq k \leq n-2$$ and every sequence of natural numbers $$a=\{a_d\}_{d\in \mathbb{N}}$$ there is a regular, compact semianalytic hypersurface $$\Gamma \subset {\mathbb{R}}\textrm{P}^n$$, a subsequence $$\{a_{d_m}\}_{m\in \mathbb{N}}$$ and homogeneous polynomials $$\{p_{m}\}_{m\in \mathbb{N}}$$ of degree $$\deg (p_m)=d_m$$ such that (0.1)$$\begin{equation}b_k(\Gamma\cap Z(p_m))\geq a_{d_m}.\end{equation}$$ (Here $$b_k$$ denotes the $$k$$th Betti number.) This generalizes a result of Gwoździewicz et al. [13]. On the other hand, for a given definable $$\Gamma$$ we show that the Fubini–Study measure, in the Gaussian probability space of polynomials of degree $$d$$, of the set $$\Sigma _{d_m,a, \Gamma }$$ of polynomials verifying (0.1) is positive, but there exists a constant $$c_\Gamma$$ such that $$\begin{equation*}0<{\mathbb{P}}(\Sigma_{d_m, a, \Gamma})\leq \frac{c_{\Gamma} d_m^{\frac{n-1}{2}}}{a_{d_m}}.\end{equation*}$$ This shows that the set of ‘pathological examples’ has ‘small’ measure (the faster $$a$$ grows, the smaller the measure and pathologies are therefore rare). In fact we show that given $$\Gamma$$, for most polynomials a Bézout-type bound holds for the intersection $$\Gamma \cap Z(p)$$: for every $$0\leq k\leq n-2$$ and $t>0$: $$\begin{equation*}{\mathbb{P}}\left(\{b_k(\Gamma\cap Z(p))\geq t d^{n-1} \}\right)\leq \frac{c_\Gamma}{td^{\frac{n-1}{2}}}.\end{equation*}$$ 

Let $$\R$$ be a real closed field and $$\C$$ the algebraic closure of $$\R$$. We give an algorithm for computing a semi-algebraic basis for the first homology group, $$\HH_1(S,\mathbb{F})$$, with coefficients in a field $$\FF$$, of any given semi-algebraic set $$S \subset \R^k$$ defined by a closed formula. The complexity of the algorithm is bounded singly exponentially. More precisely, if the given quantifier-free formula involves $$s$$ polynomials whose degrees are bounded by $$d$$, the complexity of the algorithm is bounded by $$(s d)^{k^{O(1)}}$$. This algorithm generalizes well known algorithms having singly exponential complexity for computing a semi-algebraic basis of the zero-th homology group of semi-algebraic sets, which is equivalent to the problem of computing a set of points meeting every semi-algebraically connected component of the given semi-algebraic set at a unique point. 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 $$\HH_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_\C Z^{(i)} \leq i$, and $$\HH_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)}$$). 

We introduce harmonic persistent homology spaces for filtrations of finite simplicial complexes. As a result we can associate concrete subspaces of cycles to each bar of the barcode of the filtration. We prove stability of the harmonic persistent homology subspaces, as well as the subspaces associated to the bars of the barcodes, under small perturbations of functions defining them. We relate the notion of ``essential simplices'' introduced in an earlier work to identify simplices which play a significant role in the birth of a bar, with that of harmonic persistent homology. We prove that the harmonic representatives of simple bars maximizes the ``relative essential content'' amongst all representatives of the bar, where the relative essential content is the weight a particular cycle puts on the set of essential simplices. \footnote{An extended abstract of the paper appeared in the Proceedings of the IEEE Symposium on the Foundations of Computer Science, 2021.}