Partitioning theorems for sets of semi-Pfaffian sets, with applications

Abstract We generalize the seminal polynomial partitioning theorems of Guth and Katz [33, 28] to a set of semi-Pfaffian sets. Specifically, given a set $\Gamma \subseteq \mathbb {R}^n$ of k -dimensional semi-Pfaffian sets, where each $\gamma \in \Gamma $ is defined by a fixed number of Pfaffian functions, and each Pfaffian function is in turn defined with respect to a Pfaffian chain $\vec {q}$ of length r , for any $D \ge 1$ , we prove the existence of a polynomial $P \in \mathbb {R}[X_1, \ldots , X_n]$ of degree at most D such that each connected component of $\mathbb {R}^n \setminus Z(P)$ intersects at most $\sim \frac {|\Gamma |}{D^{n - k - r}}$ elements of $\Gamma $ . Also, under some mild conditions on $\vec {q}$ , for any $D \ge 1$ , we prove the existence of a Pfaffian function $P'$ of degree at most D defined with respect to $\vec {q}$ , such that each connected component of $\mathbb {R}^n \setminus Z(P')$ intersects at most $\sim \frac {|\Gamma |}{D^{n-k}}$ elements of $\Gamma $ . To do so, given a k -dimensional semi-Pfaffian set $\mathcal {X} \subseteq \mathbb {R}^n$ , and a polynomial $P \in \mathbb {R}[X_1, \ldots , X_n]$ of degree at most D , we establish a uniform bound on the number of connected components of $\mathbb {R}^n \setminus Z(P)$ that $\mathcal {X}$ intersects; that is, we prove that the number of connected components of $(\mathbb {R}^n \setminus Z(P)) \cap \mathcal {X}$ is at most