VC-Dimension vs Degree: An Uncertainty Principle for Boolean Functions

In this paper, we uncover a new uncertainty principle that governs the complexity of Boolean functions. This principle manifests as a fundamental trade-off between two central measures of complexity: a combinatorial complexity of its supported set, captured by its Vapnik-Chervonenkis dimension ($\mathrm{V}\mathrm{C}(f)$), and its algebraic structure, captured by its polynomial degree over various fields. We establish two primary inequalities that formalize this trade-off: $\mathrm{V}\mathrm{C}(f)+\mathrm{d}\mathrm{e}\mathrm{g}(f)\ge n,$ and $\mathrm{V}\mathrm{C}(f)+{\mathrm{d}\mathrm{e}\mathrm{g}}_{{\mathbb{F}}_2}(f)\ge n$. In particular, these results recover the classical uncertainty principle on the discrete hypercube, as well as the Sziklai–Weiner’s bound in the case of ${\mathbb{F}}_2$.