Quantitative semi-algebraic basic lemma conjecture

At least 4 years old · documented by

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

Z(n−1)⊃⋯⊃Z(1)⊃Z(0)Z^{(n-1)} \supset \cdots \supset Z^{(1)} \supset Z^{(0)}

with dim⁡Z(i)≤i\dim Z^{(i)}\leq i and H⁡q(X,Z(i))=0\operatorname{H}_q(X,Z^{(i)})=0 for 0≤q≤i0\leq q\leq i. Quantitative semi-algebraic basic lemma conjecture. Such a filtration exists so that, for each ii with 0≤i≤n−10\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 0≤ℓ≤n−10\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.

References

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.