VC-Dimension vs Degree: An uncertainty principle for Boolean functions

Abstract

We prove a support--shattering uncertainty principle for functions on the Boolean cube. Let $\mathbb{F}$ be any field and let $f:\{0,1{\}}^n\to \mathbb{F}$ be nonzero. If $x^S$ is a maximum-degree monomial in the multilinear representation of $f$, then $\mathrm{supp}(f)$ shatters $S^c$. Consequently, \[ \mathrm{VC}(\mathrm{supp}(f))+\mathrm{deg}_{\mathbb{F}}(f)\ge n . \] For Boolean-valued functions this yields both the real-degree and algebraic-degree forms of the inequality. We derive several consequences. The real Fourier support of a nonzero Boolean function satisfies \[ \mathrm{VC}(\mathrm{Spec}(f))\ge \mathrm{deg}_{\mathbb{F}_2}(f), \qquad \mathrm{VC}(\mathrm{supp}(f))+\mathrm{VC}(\mathrm{Spec}(f))\ge n . \] The same principle gives a low-degree-obstruction proof of the Sauer--Shelah lemma and a product-space analogue based on the Efron--Stein decomposition, recovering the Karpovsky--Milman multivalued Sauer lemma. We also obtain polynomial-method applications, including an arbitrary-field Sziklai--Weiner lower bound and a shattering theorem for null designs, and discuss sharpness and equality examples.

14 pages. This version contains a simpler proof and several additional applications