Effective cylindrical cell decompositions for restricted sub-Pfaffian sets

Gal Binyamini, Nicolai Vorobjov

Research output: Contribution to journalArticlepeer-review

1 Citation (SciVal)
54 Downloads (Pure)

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 F⁠, 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.
Original languageEnglish
Pages (from-to)3493-3510
Number of pages18
JournalInternational Mathematics Research Notices
Volume2022
Issue number5
Early online date24 Nov 2020
DOIs
Publication statusPublished - 31 Mar 2022

Bibliographical note

Funding Information:
This work was supported by the Israel Science Foundation (1167/17); the Minerva Stiftung with the funds from the Ministry for Education and Research of the Federal Republic of Germany; and the European Research Council under the European Union's Horizon 2020 research and innovation programme (802107).

ASJC Scopus subject areas

  • General Mathematics

Fingerprint

Dive into the research topics of 'Effective cylindrical cell decompositions for restricted sub-Pfaffian sets'. Together they form a unique fingerprint.

Cite this