2025-11-10T03:13:53.693617

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

Chang, Fang
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{VC}(f)$), and its algebraic structure, captured by its polynomial degree over various fields. We establish two primary inequalities that formalize this trade-off:$\mathrm{VC}(f)+°(f)\ge n,$ and $\mathrm{VC}(f)+°_{\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$.
academic

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

基本信息

  • 论文ID: 2510.13705
  • 标题: VC-Dimension vs Degree: An Uncertainty Principle for Boolean Functions
  • 作者: Fan Chang (南开大学统计与数据科学学院 & 韩国基础科学研究院), Yijia Fang (新加坡国立大学数学系)
  • 分类: math.CO cs.CC cs.DM
  • 发表时间: 2025年10月17日
  • 论文链接: https://arxiv.org/abs/2510.13705

摘要

本文揭示了一个支配布尔函数复杂性的新不确定性原理。该原理体现为两个核心复杂性度量之间的基本权衡：支撑集的组合复杂性（由Vapnik-Chervonenkis维度VC(f)刻画）和代数结构复杂性（由各种域上的多项式度数刻画）。论文建立了两个主要不等式来形式化这种权衡：VC(f) + deg(f) ≥ n 和 VC(f) + deg_F₂(f) ≥ n。这些结果特别地恢复了离散超立方体上的经典不确定性原理，以及F₂情况下的Sziklai-Weiner界。

研究背景与动机

问题背景

  1. 布尔函数的基础性: 定义在布尔超立方体{0,1}ⁿ上的函数是组合数学和理论计算机科学中的基本对象
  2. Fourier展开表示: 每个这样的函数f : {0,1}ⁿ → ℝ都可以表示为线性组合f = Σ_{S⊆n} f̂(S)·χ_S
  3. 复杂性度量的多样性: 存在多种刻画布尔函数复杂性的方式，包括组合复杂性和代数复杂性

研究动机

  1. 低影响布尔函数研究: 受低影响布尔函数研究的启发，探索有界VC维布尔函数的Fourier谱结构性质
  2. 复杂性度量的关系: 研究VC维度（组合复杂性）与多项式度数（代数复杂性）之间的根本关系
  3. 理论统一: 寻求连接极值组合学和布尔函数分析的桥梁

现有方法局限性

现有的Sauer-Perles-Shelah定理和Schwartz-Zippel定理的组合只能给出较弱的权衡关系d log₂(en/d) + d* ≥ n，而本文的结果将其加强为d + d* ≥ n。

核心贡献

  1. 建立新的不确定性原理: 证明了VC维度与实数域上多项式度数之间的基本权衡关系：VC(f) + deg(f) ≥ n
  2. 扩展到有限域: 证明了VC维度与F₂域上多项式度数的权衡关系：VC(f) + deg_F₂(f) ≥ n
  3. 理论结果的统一: 恢复了离散超立方体上的经典不确定性原理和Sziklai-Weiner界
  4. 建立与null d-design的联系: 揭示了与Frankl和Pach引入的null d-design概念的深刻联系
  5. 扩展到其他复杂性度量: 探索了VC维度与决策树复杂性、敏感度、证书复杂性等其他布尔函数复杂性度量的权衡关系

方法详解

任务定义

研究布尔函数f : {0,1}ⁿ → {0,1}的VC维度VC(f)与其多项式度数deg(f)、deg_F₂(f)之间的定量关系。

核心定理

定理1.2: 对于任意非零布尔函数f : {0,1}ⁿ → {0,1}，有VC(f) + deg(f) ≥ n。

定理1.5: 对于任意非零布尔函数f : {0,1}ⁿ → {0,1}，有VC(f) + deg_F₂(f) ≥ n。

证明策略

定理1.2的证明思路

  1. 反证法设置: 假设deg(f) ≤ n - d - 1，其中d = VC(f)
  2. Fourier系数约束: 利用度数约束得到f̂(S^c) = 0对所有|S| ≤ d成立
  3. 组合条件导出: 通过Fourier分析推导出#{F ∈ ℱ | F ∩ S = T} ≡ 0 (mod 2)的条件
  4. null d-design连接: 证明该条件等价于null d-design的定义
  5. 矛盾产生: 利用Lemma 2.3证明满足null d-design的族必须有VC维度≥ d+1，产生矛盾

定理1.5的证明思路

  1. 组合引理: 首先证明Lemma 2.4，建立偶交集计数条件与VC维度的关系
  2. F₂多项式表示: 利用Proposition 2.7给出F₂多项式系数的公式
  3. 直接构造: 通过构造具体的单项式证明度数下界

技术创新点

  1. null d-design的应用: 创新性地将Frankl-Pach的null d-design概念应用到布尔函数复杂性分析中
  2. Möbius反演的使用: 巧妙运用布尔格上的Möbius反演公式建立不同计数条件的等价性
  3. 统一的证明框架: 为实数域和F₂域的结果提供了统一的证明思路

实验设置

计算验证

论文通过编程枚举验证了低维情况下等号成立的函数：

n总函数数deg(f)+VC(f)=n的函数数deg_F₂(f)+VC(f)=n的函数数
1433
216911
32565583
4655366332491

代码可获得性

相关计算代码已在GitHub上公开：https://github.com/FangYijia/deg-VC

实验结果

主要结果验证

  1. 等号情况的复杂性: 计算结果显示等号成立的情况相当复杂，不仅限于子立方体
  2. 具体反例: 给出了n=4时deg(f)=VC(f)=2但支撑集不是子立方体的具体函数例子
  3. 刻画困难性: 完全刻画等号成立条件是极其困难的任务

理论应用

  1. 经典结果恢复: 成功恢复了布尔函数的经典不确定性原理（Corollary 1.6）
  2. Sziklai-Weiner界: 在F₂情况下恢复了权重约束多项式的Sziklai-Weiner下界（Corollary 1.7）

相关工作

核心相关研究

  1. Sauer-Perles-Shelah定理: 提供了VC维度与集合族大小的经典关系
  2. Schwartz-Zippel引理: 给出了多项式非零点数量的下界
  3. Frankl-Pach的null d-design: 提供了本文证明的关键工具
  4. 布尔函数分析: 与Fourier分析、敏感度猜想等经典理论的联系

本文的独特贡献

相比现有工作，本文首次建立了VC维度与多项式度数之间的紧致权衡关系，并提供了统一的理论框架。

结论与讨论

主要结论

  1. 建立了布尔函数复杂性的新不确定性原理：VC(f) + deg(f) ≥ n和VC(f) + deg_F₂(f) ≥ n
  2. 这些不等式是紧致的，子立方体指示函数达到等号
  3. 恢复并统一了多个经典结果

扩展方向

  1. 布尔切片: 探索在布尔超立方体切片上的类似权衡关系
  2. 一般阿贝尔群: 研究在任意有限阿贝尔群上的推广
  3. 其他复杂性度量: 与决策树复杂性、敏感度、证书复杂性的关系

局限性

  1. 等号刻画: 完全刻画等号成立的条件仍然困难
  2. 计算复杂性: 对于高维情况的计算验证变得不可行
  3. 推广限制: 某些推广（如与敏感度的关系）存在反例

深度评价

优点

  1. 理论深度: 建立了组合复杂性与代数复杂性之间的深刻联系
  2. 技术创新: 巧妙运用null d-design等高级技术
  3. 结果统一: 在统一框架下恢复了多个经典结果
  4. 证明优雅: 提供了简洁而深刻的证明思路

不足

  1. 等号刻画不完整: 对于等号成立条件的刻画仍不够完善
  2. 某些推广的限制: 如与敏感度关系的推广存在反例
  3. 计算验证范围: 只能在低维情况下进行完整验证

影响力

  1. 理论贡献: 为布尔函数复杂性理论提供了新的基础工具
  2. 方法论价值: null d-design的应用为相关研究提供了新思路
  3. 连接桥梁: 在极值组合学和布尔函数分析之间建立了新联系

适用场景

  1. 理论计算机科学: 复杂性理论、学习理论中的应用
  2. 极值组合学: 集合族的结构性质研究
  3. 布尔函数分析: Fourier分析、影响度分析等领域

参考文献

论文引用了33篇重要文献，涵盖了布尔函数分析、极值组合学、复杂性理论等多个领域的经典和前沿工作，为研究提供了坚实的理论基础。

总结: 这是一篇在布尔函数复杂性理论方面具有重要贡献的论文，建立了VC维度与多项式度数之间的基本权衡关系，为理解布尔函数的内在复杂性提供了新的理论工具。