Effective cylindrical cell decompositions for restricted sub-Pfaffian sets

DOI10.1093/IMRN/RNAA285MaRDI QIDQ5862786zbMATH OpenOpenAlexFDO

Authors Gal Binyamini, Nicolai Vorobjov

Publication date 10 March 2022

Published in IMRN. International Mathematics Research Notices (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2004.06411

zbMATH Keywords

Betti numbercell decompositioncomplexitysub-Pfaffian set

Mathematics Subject Classification ID

Model theory of ordered structures; o-minimality (03C64) Semialgebraic sets and related spaces (14P10)

Abstract: The o-minimal structure generated by the restricted Pfaffian functions, known as restricted sub-Pfaffian sets, admits a natural measure of complexity in terms of a format $mathcalF$, recording information like the number of variables and quantifiers involved in the definition of the set, and a degree $D$ recording the degrees of the equations involved. Khovanskii and later Gabrielov and Vorobjov have established many effective estimates for the geometric complexity of sub-Pfaffian sets in terms of these parameters. It is often important in applications that these estimates are polynomial in $D$. Despite much research done in this area, it is still not known whether cell decomposition, the foundational operation of o-minimal geometry, preserves polynomial dependence on $D$. We slightly modify the usual notions of format and degree and prove that with these revised notions this does in fact hold. As one consequence we also obtain the first polynomial (in $D$) upper bounds for the sum of Betti numbers of sets defined using quantified formulas in the restricted sub-Pfaffian structure.

Recommendations

• Complexity of cylindrical decompositions of sub-Pfaffian
• scientific article; zbMATH DE number 2209738
• Computer Science Logic
• New complexity bounds for cylindrical decompositions of sub-Pfaffian sets
• scientific article; zbMATH DE number 2209727

Cited in

(11)

• New complexity bounds for cylindrical decompositions of sub-Pfaffian sets
• On sets ∀-definable from Pfaffian functions
• scientific article; zbMATH DE number 1984323 (Why is no real title available?)
• scientific article; zbMATH DE number 2209727 (Why is no real title available?)
• scientific article; zbMATH DE number 2209738 (Why is no real title available?)
• Complexity of cylindrical decompositions of sub-Pfaffian
• Tameness in geometry and arithmetic: beyond o-minimality
• Wilkie's conjecture for Pfaffian structures
• Rolle models in the real and complex world
• On the complexity of quantum field theory
• Sharp o-minimality and lattice point counting

This page was built for publication: Effective cylindrical cell decompositions for restricted sub-Pfaffian sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5862786)