Complexity and speed of semi-algebraic multi-persistence

Abstract

Let $\mathrm{R}$ be a real closed field, $S\subset {\mathrm{R}}^n$ a closed and bounded semi-algebraic set, and $\mathbf{f}=(f_1,\dots ,f_p):S\to {\mathrm{R}}^p$ a continuous semi-algebraic map inducing a $p$-parameter semi-algebraic filtration by sublevel sets. We introduce a barcode invariant for such filtrations that directly extends the classical ($p=1$) barcode. After scaling of the parameter space, in each homological degree $\ell$ the invariant is encoded by a ${\mathbb{Z}}_{\ge 0}$-valued function \[ μ_\ell(S,\mathbf{f}):\ \Big(({-}1,1)^p\times(({-}1,1)^p \cup\{(1,\ldots,1)\}) \Big)\ \cap\ \{(\mathbf a,\mathbf b)\mid \mathbf a\preceq \mathbf b\} \ \longrightarrow\ \mathbb{Z}_{\ge 0}, \] where $⪯$ denotes the product order on ${\mathrm{R}}^p$. We prove that $\hat{I}{¼}_{\ell }(S,\mathbf{f})$ is semi-algebraically constructible and establish a singly exponential upper bound on its description complexity. Moreover, we give a singly exponential-time algorithm to compute $\hat{I}{¼}_{\ell }(S,\mathbf{f})$, extending to arbitrary $p$ the corresponding result for $p=1$ by Basu and Karisani. Finally, for semi-algebraic filtrations of bounded description complexity we bound the number of equivalence classes of finite poset modules realizable in this way, yielding a tight analogue of "speed" bounds for algebraically defined graph classes.

42 pages. Extensive revision from previous version. Comments welcome