Optimal Lower Bounds for Symmetric Modular Circuits

这篇论文《Symmetric Modular Circuits 的最优下界》（Optimal Lower Bounds for Symmetric Modular Circuits）由 Benedikt Pago 撰写，发表于 2026 年 4 月（注：根据文中日期，这是一篇未来的或假设性的论文，但内容基于现有的复杂性理论框架）。该论文解决了电路复杂性领域一个长期存在的开放问题，即在使用模计数门（MOD gates）构建的电路中，计算布尔 AND 函数的最优规模下界。

以下是对该论文的详细技术总结：

1. 研究背景与问题 (Problem)

• 核心问题：在电路复杂性中，一个著名的未解之谜是：是否可以使用仅包含模计数门（MOD gates）的常数深度电路，以多项式规模高效地表达任意阶的布尔运算（特别是 $n$ 元布尔 AND 函数）？
  • 形式化问题：对于固定的深度 $h$ 和模数 $m$，计算 $AND_n$ 的最小 $CCh[m]$ 电路（仅含 MOD 门的深度 $h$ 电路）的规模是多少？
  • 复杂性类关系：这等价于问 $CC^0 = ACC^0$ 是否成立？已知 $CC^0$ 是仅含模计数门的常数深度电路类，而 $ACC^0$ 允许额外的布尔与、或、非门。
• 现状：
  • 对于对偶问题（用布尔门模拟模计数），Håstad 的 Switching Lemma 已经给出了指数级下界。
  • 对于模电路模拟布尔 AND 函数，尽管已有近 30 年历史，但仅知道略超线性的下界（针对连线数而非门数）。
  • 普遍猜想（Exponential Size Hypothesis, ESH）认为，对于复合模数 $m$，计算 $AND_n$ 需要指数级规模 $2^{\Omega(n^\epsilon)}$。
• 本文切入点：作者引入了对称性（Symmetry）限制。由于 $AND_n$ 函数本身是对称的（输入置换不变），研究其对称电路表示（即电路结构在输入置换下保持同构）是自然的。作者旨在确定在强对称性约束下，模电路计算 $AND_n$ 的精确复杂度。

2. 核心定义与模型 (Definitions & Model)

• 完全对称电路 (Fully Symmetric / $Sym_n$-symmetric)：
  • 电路 $C$ 是完全对称的，如果对于输入变量集合 $\{x_1, \dots, x_n\}$ 的任意置换 $\pi \in Sym_n$，都存在电路的一个自同构，该自同构将输入门按照 $\pi$ 进行置换。
• 嵌套块对称电路 (Nested Block Symmetric / $Aut(T^k_n)$-symmetric)：
  • 这是一种更宽松对称性。电路结构对应于一棵深度为 $h$ 的树 $T^k_n$，叶子节点对应输入变量。
  • 对称群是树的自同构群 $Aut(T^k_n)$，即保持树结构不变的置换群。这允许电路在局部块（block）内对称，但全局上不一定完全对称。
• 模电路 ($MOD_m$-circuit)：
  • 内部门执行 $MOD^R_m$ 操作：当输入之和模 $m$ 属于集合 $R$ 时输出 1，否则输出 0。

3. 主要贡献与结果 (Key Contributions & Results)

3.1 完全对称电路的下界 (Theorem 1.1)

• 定理内容：设 $m \ge 6$ 且至少有 $r \ge 2$ 个不同的素因子。对于任何计算 $AND_n$ 的 $Sym_n$-对称 $MOD_m$ 电路族，其规模下界为：
  $$|C_n| \ge 2^{\Omega(n^{1/r} \cdot \log n)}$$
• 最优性：该下界与 Idziak, Kawałek, Krzaczkowski (LICS'22) 提出的深度为 2 的构造精确匹配。
• 关键发现：在完全对称的假设下，深度 2 的构造已经是规模最优的。增加电路深度（$h > 2$）并不能在保持完全对称性的前提下减少电路规模。只有打破对称性（如使用更深层的嵌套结构）才能进一步减小规模。

3.2 嵌套块对称电路的下界 (Theorem 1.2)

• 定理内容：对于具有嵌套块对称性（由树 $T^k_n$ 定义，块大小序列为 $k=(k_1, \dots, k_h)$）的电路，其规模下界由最大块大小 $k_{max}(n)$ 决定：
  $$|C_n| \ge 2^{\Omega(k_{max}(n)^{1/r} \cdot \log k_{max}(n))}$$
• 推论 (Corollary 1.3)：为了最小化规模，最优的块大小分配是均匀分布，即 $k_1 = \dots = k_h = n^{1/h}$。此时规模为 $2^{\Theta(n^{1/(h \cdot r)} \cdot \log n)}$。
• 对比：之前的文献 [24] 提出了一种深度为 $h+1$ 的构造，其规模约为 $2^{\Theta(n^{1/(h \cdot (r-1))} \cdot \log n)}$。本文证明，如果坚持对称性约束，深度 $2h$ 的递归构造（规模指数为 $1/r$）比深度 $h+1$ 的构造（指数为 $1/(r-1)$）在规模上更优。

4. 方法论与技术路径 (Methodology)

作者采用了一种基于**群论支撑（Group-theoretic Supports）**的归纳证明框架，克服了以往技术无法处理任意深度和复合模数 $m$ 的障碍。

1. 支撑（Support）概念：

   • 对于对称电路中的每个门 $g$，定义其稳定子群 $Stab(g)$的**最小支撑**$sup(g)$。支撑是输入变量集合的一个小子集，使得固定该子集上的值后，门的行为在剩余变量的置换下保持不变。
   • 对于嵌套对称性，引入了**块支撑（Block-wise Support）**的概念。

2. 周期性论证（Periodicity Argument）：

   • 核心引理 (Lemma 3.3 & 4.5)：如果一个对称模电路的支撑大小 $s(n)$ 很小（具体为 $o(n)$），那么该电路计算的函数必然具有某种周期性。
   • 具体来说，如果支撑大小受限，计算出的函数在模 $m$ 意义下，其值随输入中 1 的个数变化呈现周期性，周期长度由 $m$ 的素因子和支撑大小决定，形式为 $m \cdot \prod p_i^{\lfloor \log_{p_i} s(n) \rfloor}$。
   • 矛盾导出：$AND_n$ 函数是**非周期（Aperiodic）**的（Lemma 2.6），因为它仅在输入全为 1 时输出 1，而在其他任何位置（包括 $n-\ell$ 个 1 时）输出 0，这破坏了任何长度 $\le n$ 的周期性。
   • 因此，为了计算 $AND_n$，电路的支撑大小必须足够大，从而迫使电路规模（门数和连线数）必须达到指数级下界。

3. 归纳证明：

   • 通过对电路层数进行归纳，证明每一层门的函数在固定支撑变量后，其关于剩余变量中 1 的个数的函数具有特定的周期性结构。
   • 利用组合数学（二项式系数模 $m$ 的周期性）来推导整个电路输出的周期性上界。

5. 上界构造 (Upper Bounds)

• 深度 2 构造：引用并总结了 Idziak 等人的工作，利用 $Z_{pq}$-表达式（基于中国剩余定理和素数幂的线性组合）在深度 2 内实现 $AND_n$，规模匹配下界。
• 递归构造：对于嵌套块对称情况，作者提出了一种简单的递归方法：在树的每一层，利用深度 2 的对称电路计算子块的 AND 结果。这导致了深度 $2h$ 的电路，规模达到理论下界。

6. 意义与结论 (Significance & Conclusion)

1. 解决开放问题：在对称电路模型下，彻底解决了 $CC^0$ 计算 $AND_n$ 的规模复杂度问题，证明了 $2^{\Omega(n^{1/r} \log n)}$ 是最优下界。
2. 深度与规模的权衡：
   • 在完全对称约束下，深度 2 即是最优，增加深度无益。
   • 在嵌套块对称约束下，增加深度（$h$）可以指数级降低规模（指数从 $n^{1/r}$ 变为 $n^{1/(hr)}$）。
   • 揭示了“打破对称性”是获得更小规模电路的关键，但同时也指出了在保持特定对称性（如 $Aut(T^k_n)$）时的极限。
3. 对 $CC^0$ vs $ACC^0$ 的启示：
   • 如果所有 $CC^0$ 电路都能以较小的代价“对称化”（Symmetrized），那么本文的下界将直接适用于所有 $CC^0$ 电路，从而证明 $CC^0 \neq ACC^0$。
   • 如果存在非对称的 $CC^0$ 电路能以更小规模计算 $AND_n$，则意味着必须打破对称性。这为寻找 $CC^0$ 的上界构造提供了新的方向。
4. 技术贡献：将群论支撑理论成功扩展到复合模数 $m$ 和任意深度的对称电路，为处理更复杂的对称性结构（如嵌套群）提供了新的工具。

总结：这篇论文通过引入精细的群论支撑分析和周期性论证，确立了模计数电路在对称约束下的严格下界，证明了在保持对称性的前提下，深度 2 的构造已是最优，并量化了通过分层对称结构（嵌套块）换取规模缩减的潜力。这不仅解决了特定模型下的复杂度问题，也为解决更广泛的 $CC^0$ vs $ACC^0$ 问题提供了重要的理论基石。