Quantitative semi-algebraic basic lemma conjecture

Let XRkX \subset \mathbb{R}^k be a semi-algebraic set defined by a closed formula of complexity bounded by CC, and let dimX=n\dim X=n. A nested semi-algebraic filtration is a sequence of closed semi-algebraic subsets

Z(n1)Z(1)Z(0)Z^{(n-1)} \supset \cdots \supset Z^{(1)} \supset Z^{(0)}

with dimZ(i)i\dim Z^{(i)}\leq i and Hq(X,Z(i))=0\operatorname{H}_q(X,Z^{(i)})=0 for 0qi0\leq q\leq i. Quantitative semi-algebraic basic lemma conjecture. Such a filtration exists so that, for each ii with 0in10\leq i\leq n-1, the complexity of Z(i)Z^{(i)} is bounded by CO(ki+1)C^{O(k^{i+1})}. Moreover, there is an algorithm computing closed formulas describing Z(0),,Z()Z^{(0)},\ldots,Z^{(\ell)}, for 0n10\leq\ell\leq n-1, whose complexity is bounded by CkO()C^{k^{O(\ell)}}. This would provide a potentially more efficient semi-algebraic replacement for the filtration obtained from skeleta of a triangulation, whose construction can have doubly exponential complexity; the conjecture remains open in the supplied text.

Sources & referencesView supporting material

Primary source

Saugata Basu and Sarah Percival, “Efficient computation of a semi-algebraic basis of the first homology group of a semi-algebraic set”, arXiv:2107.08947 (2021).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.