块复杂度与幂等Schur乘子：Green-Sanders定理的矩阵类比及其多对数上界

《International Mathematics Research Notices》：Block Complexity and Idempotent Schur Multipliers

为解决布尔矩阵作为Schur乘子时其范数与结构表征的关系问题，Marcel K. Goh与Hamed Hatami开展了关于块复杂度与幂等Schur乘子的研究。他们证明了具有有界Schur乘子范数γ的n×n整数矩阵的块复杂度上界为2O(γ?)log(n)2，该结果首次实现了对Conjecture 1.2的多对数级依赖，为Cohen幂等定理在Schur乘子代数中的定量类比提供了关键进展。

　　

在泛函分析与组合矩阵论的交叉领域，一个长期悬而未决的核心问题是如何刻画Schur乘子代数中的幂等元。经典Cohen幂等定理表明，局部紧阿贝尔群上的幂等测度其傅里叶变换必属于陪集环，而Green与Sanders的定量版本进一步揭示：有限群上傅里叶代数范数有界的布尔函数可表示为有限个陪集示性函数的带符号和。受此启发，Katavolos与Paulsen首次提出矩阵版本的对应猜想：是否每个具有有界Schur乘子范数的布尔矩阵都能表示为有限个块矩阵（blocky matrices）的带符号和？这一猜想被领域内视为挑战性难题（见[23]与[4]问题3.13）。

块矩阵是指可通过单位矩阵经过行复制、列复制或添加零行/零列操作得到的布尔矩阵，其Schur乘子范数恰好为1。然而，对于范数大于1的布尔矩阵，其结构分解的定量控制一直缺乏有效工具。Goh与Hatami的突破性工作首次给出了块复杂度的显式上界，证明了对于Schur乘子范数不超过γ的m×n整数矩阵，其块复杂度（即分解所需块矩阵的最少个数）至多为2^O(γ?)log(min(m,n))2。这一结果不仅将维度依赖从线性降低至多对数级，更通过引入加权Littlestone维度等新工具，为后续研究提供了全新视角。

本研究主要采用以下关键技术方法：首先利用Grothendieck定理将Schur乘子范数等价转化为γ₂分解范数；其次通过定义α-加权Littlestone维度（α-weighted Littlestone dimension）作为实值矩阵的组合复杂度度量，并建立其与γ₂范数的多项式关系；进而设计贪心算法对矩阵列空间进行自适应划分，结合向量平均技术构造渐进改进的近似分解；最后通过迭代引理控制误差积累，实现整体块复杂度的多对数上界估计。

加权Littlestone维度的创新引入

研究团队将在线学习理论中的Littlestone维度推广至实值矩阵场景。通过定义加权决策树结构，提出α-粉碎（α-shattering）概念：当存在加权决策树使得每条根叶路径都能找到对应列，其与节点标记值的偏差始终超过α/2时，称矩阵具有d维α-加权Littlestone维度。Proposition 3.2证明该维度被γ₂范数多项式控制，即d=O_α(γ?)，为后续分解算法提供复杂度理论基础。

列空间自适应划分技术

Lemma 4.3设计贪心划分算法，将矩阵列集划分为若干子集S_i，每个子集存在特定行x_i使得A_Z(x_i,y)恒为非零整数b_i。关键创新点在于控制各行值分布：对任意行x与非零整数b，满足Pr_y∈Si[A_Z(x,y)=b]≥δ的子集数量不超过(log|Y|+1)/δ。该性质确保后续构造的近似矩阵其整数部分具有可控的块复杂度。

向量平均与范数递减引理

Lemma 5.1为核心迭代引理，通过计算各子集S_i对应列向量的平均值?v_i，并应用Lemma 4.2筛选出满足‖v_y-?v_i‖2≤‖v_y‖2-1/8的子列。据此构造近似矩阵?，其与原始矩阵的γ₂范数差平方至少下降1/8，而?的整数部分块复杂度被控制在2^O(γ?)(log|Y|)2内。该引理通过保持行向量不变、迭代更新列向量的方式，实现分解误差的逐次降低。

多对数依赖性的迭代证明

Theorem 5.2通过递归应用Lemma 5.1完成最终证明。每次迭代保留?-近整值性（?-almost integer-valued）条件（?=2^-20γ2），将矩阵分解为近似部分与残差部分。近似部分块复杂度由列划分算法控制，残差部分γ₂范数逐步递减，经过至多2^O(γ?)log|Y|次迭代后范数降至1/2以下，此时矩阵整数部分为零矩阵。复杂度上界由几何级数求和得出，关键步骤依赖加权Littlestone维度与γ₂范数的多项式关系。

本研究通过引入加权Littlestone维度与自适应列划分算法，首次实现了对布尔矩阵块复杂度的多对数上界估计。研究结论表明，Schur乘子范数有界的整数矩阵其结构复杂性可由γ₂范数及维度对数项联合控制，这为完全解决Conjecture 1.2奠定了理论基础。值得关注的是，Gs等人近期证明[6]：对任意?>0，存在布尔矩阵其?-近似版本γ₂范数为O_?(1)，而原始矩阵范数达2^{Ω_?(√log n)}，这提示整数性条件在本研究中的本质作用。该成果不仅推进了Cohen幂等定理在非交换背景下的定量化进程，更为矩阵分解理论、在线学习算法设计等跨学科领域提供了新的工具链。