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

Basic Information

• Paper ID: 2510.13705
• Title: VC-Dimension vs Degree: An Uncertainty Principle for Boolean Functions
• Authors: Fan Chang (School of Statistics and Data Science, Nankai University & Korea Institute for Advanced Study), Yijia Fang (Department of Mathematics, National University of Singapore)
• Classification: math.CO cs.CC cs.DM
• Publication Date: October 17, 2025
• Paper Link: https://arxiv.org/abs/2510.13705

Abstract

This paper reveals a novel uncertainty principle governing the complexity of Boolean functions. The principle manifests as a fundamental trade-off between two core complexity measures: the combinatorial complexity of the support set (characterized by the Vapnik-Chervonenkis dimension VC(f)) and the algebraic structural complexity (characterized by polynomial degree over various fields). The paper establishes two main inequalities formalizing this trade-off: VC(f) + deg(f) ≥ n and VC(f) + deg_F₂(f) ≥ n. These results particularly recover the classical uncertainty principle on the discrete hypercube and the Sziklai-Weiner bound in the F₂ case.

Research Background and Motivation

Problem Background

1. Fundamentality of Boolean Functions: Functions defined on the Boolean hypercube {0,1}ⁿ are fundamental objects in combinatorics and theoretical computer science
2. Fourier Expansion Representation: Every such function f : {0,1}ⁿ → ℝ can be represented as a linear combination f = Σ_{S⊆n} f̂(S)·χ_S
3. Diversity of Complexity Measures: Multiple approaches exist for characterizing Boolean function complexity, including combinatorial and algebraic complexity measures

Research Motivation

1. Low-Influence Boolean Functions: Inspired by research on low-influence Boolean functions, exploring Fourier spectral structure properties of bounded VC-dimension Boolean functions
2. Relationships Between Complexity Measures: Investigating fundamental relationships between VC-dimension (combinatorial complexity) and polynomial degree (algebraic complexity)
3. Theoretical Unification: Seeking bridges connecting extremal combinatorics and Boolean function analysis

Limitations of Existing Approaches

Existing combinations of the Sauer-Perles-Shelah theorem and Schwartz-Zippel lemma only yield weaker trade-off relationships d log₂(en/d) + d* ≥ n, whereas this paper strengthens the result to d + d* ≥ n.

Core Contributions

1. Establishing a New Uncertainty Principle: Proving the fundamental trade-off relationship between VC-dimension and polynomial degree over the reals: VC(f) + deg(f) ≥ n
2. Extension to Finite Fields: Proving the trade-off relationship between VC-dimension and polynomial degree over F₂: VC(f) + deg_F₂(f) ≥ n
3. Unification of Theoretical Results: Recovering the classical uncertainty principle on the discrete hypercube and the Sziklai-Weiner bound
4. Connection to Null d-designs: Revealing deep connections to the null d-design concept introduced by Frankl and Pach
5. Extension to Other Complexity Measures: Exploring trade-off relationships between VC-dimension and other Boolean function complexity measures such as decision tree complexity, sensitivity, and certificate complexity

Methodology Details

Task Definition

Investigating quantitative relationships between the VC-dimension VC(f) of a Boolean function f : {0,1}ⁿ → {0,1} and its polynomial degrees deg(f) and deg_F₂(f).

Core Theorems

Theorem 1.2: For any nonzero Boolean function f : {0,1}ⁿ → {0,1}, we have VC(f) + deg(f) ≥ n.

Theorem 1.5: For any nonzero Boolean function f : {0,1}ⁿ → {0,1}, we have VC(f) + deg_F₂(f) ≥ n.

Proof Strategy

Proof Approach for Theorem 1.2

1. Proof by Contradiction Setup: Assume deg(f) ≤ n - d - 1, where d = VC(f)
2. Fourier Coefficient Constraints: Using degree constraints to derive f̂(S^c) = 0 for all |S| ≤ d
3. Derivation of Combinatorial Conditions: Through Fourier analysis, deriving the condition #{F ∈ ℱ | F ∩ S = T} ≡ 0 (mod 2)
4. Connection to Null d-designs: Proving this condition is equivalent to the definition of null d-design
5. Contradiction Generation: Using Lemma 2.3 to prove that families satisfying null d-design must have VC-dimension ≥ d+1, yielding a contradiction

Proof Approach for Theorem 1.5

1. Combinatorial Lemma: First proving Lemma 2.4, establishing the relationship between even intersection counting conditions and VC-dimension
2. F₂ Polynomial Representation: Using Proposition 2.7 to provide formulas for F₂ polynomial coefficients
3. Direct Construction: Proving degree lower bounds through constructing specific monomials

Technical Innovations

1. Application of Null d-designs: Innovatively applying the Frankl-Pach null d-design concept to Boolean function complexity analysis
2. Use of Möbius Inversion: Skillfully employing Möbius inversion formulas on Boolean lattices to establish equivalence between different counting conditions
3. Unified Proof Framework: Providing unified proof strategies for results over both the reals and F₂

Experimental Setup

Computational Verification

The paper verifies through programming enumeration functions achieving equality in low-dimensional cases:

Code Availability

Related computational code is publicly available on GitHub: https://github.com/FangYijia/deg-VC

Experimental Results

Main Results Verification

1. Complexity of Equality Cases: Computational results show that equality cases are quite complex, not limited to subcubes
2. Concrete Counterexamples: Providing specific functions for n=4 where deg(f)=VC(f)=2 but the support set is not a subcube
3. Difficulty of Complete Characterization: Complete characterization of equality conditions is an extremely difficult task

Theoretical Applications

1. Recovery of Classical Results: Successfully recovering the classical uncertainty principle for Boolean functions (Corollary 1.6)
2. Sziklai-Weiner Bound: Recovering the Sziklai-Weiner lower bound for weight-constrained polynomials in the F₂ case (Corollary 1.7)

Related Work

Core Related Research

1. Sauer-Perles-Shelah Theorem: Providing classical relationships between VC-dimension and set family size
2. Schwartz-Zippel Lemma: Giving lower bounds on the number of nonzero points of polynomials
3. Frankl-Pach's Null d-designs: Providing key tools for this paper's proofs
4. Boolean Function Analysis: Connections to classical theories including Fourier analysis and sensitivity conjecture

Unique Contributions of This Paper

Compared to existing work, this paper is the first to establish tight trade-off relationships between VC-dimension and polynomial degree, providing a unified theoretical framework.

Conclusions and Discussion

Main Conclusions

1. Establishing new uncertainty principles for Boolean function complexity: VC(f) + deg(f) ≥ n and VC(f) + deg_F₂(f) ≥ n
2. These inequalities are tight, with subcube indicator functions achieving equality
3. Recovering and unifying multiple classical results

Future Directions

1. Boolean Slices: Exploring similar trade-off relationships on Boolean hypercube slices
2. General Abelian Groups: Investigating generalizations to arbitrary finite Abelian groups
3. Other Complexity Measures: Relationships with decision tree complexity, sensitivity, and certificate complexity

Limitations

1. Incomplete Equality Characterization: Complete characterization of equality conditions remains difficult
2. Computational Complexity: Computational verification for high-dimensional cases becomes infeasible
3. Generalization Restrictions: Some generalizations (such as relationships with sensitivity) have counterexamples

In-Depth Evaluation

Strengths

1. Theoretical Depth: Establishing profound connections between combinatorial and algebraic complexity
2. Technical Innovation: Skillfully employing advanced techniques such as null d-designs
3. Result Unification: Recovering multiple classical results within a unified framework
4. Elegant Proofs: Providing concise and profound proof strategies

Weaknesses

1. Incomplete Equality Characterization: Characterization of equality conditions remains incomplete
2. Limitations of Some Generalizations: Such as counterexamples in generalizations relating to sensitivity
3. Limited Computational Verification Range: Complete verification only feasible in low-dimensional cases

Impact

1. Theoretical Contribution: Providing new foundational tools for Boolean function complexity theory
2. Methodological Value: The application of null d-designs provides new insights for related research
3. Bridge Building: Establishing new connections between extremal combinatorics and Boolean function analysis

Applicable Scenarios

1. Theoretical Computer Science: Applications in complexity theory and learning theory
2. Extremal Combinatorics: Research on structural properties of set families
3. Boolean Function Analysis: Applications in Fourier analysis, influence analysis, and related fields

References

The paper cites 33 important references covering classical and cutting-edge work in Boolean function analysis, extremal combinatorics, and complexity theory, providing a solid theoretical foundation for the research.

Summary: This is an important paper in Boolean function complexity theory that establishes fundamental trade-off relationships between VC-dimension and polynomial degree, providing new theoretical tools for understanding the intrinsic complexity of Boolean functions.