Partitioning Theorems for Sets of Semi-Pfaffian Sets, with Applications

Abstract

We generalize the seminal polynomial partitioning theorems of Guth and Katz to a set of semi-Pfaffian sets. Specifically, given a set $\hat{I}“\subseteq {\mathbb{R}}^n$ of $k$-dimensional semi-Pfaffian sets, where each ${\hat{I}}^3\in \hat{I}“$ 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,\dots ,X_n]$ of degree at most $D$ such that each connected component of ${\mathbb{R}}^n\setminus Z(P)$ intersects at most $\sim \frac{|\hat{I}“|}{D^{n-k-r}}$ elements of $\hat{I}“$. Also, under some mild conditions on $\vec{q}$, for any $D\ge 1$, we prove the existence of a Pfaffian function $P^{\prime }$ of degree at most $D$ defined with respect to $\vec{q}$, such that each connected component of ${\mathbb{R}}^n\setminus Z(P^{\prime })$ intersects at most $\sim \frac{|\hat{I}“|}{D^{n-k}}$ elements of $\hat{I}“$. 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,\dots ,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 $\sim D^{k+r}$. Finally as applications, we derive Pfaffian versions of Szemerédi-Trotter type theorems, and also prove bounds on the number of joints between Pfaffian curves.

(v1) 29 pages, 0 figures (v2) Added hypothesis of algebraic independence of Pfaffian chain to avoid obtaining a zero Pfaffian partitioning function (v3) Final accepted version