有限群的支撑与秩不确定性

形式陈述

一份非零函数如果只占很少几个群坐标，它的全部平移还能只张成很小的空间吗？设 $G$ 是阶为 $N\ge1$ 的有限群， $k$ 是任意域， $0\ne f\in k^G$ 。定义

A=\operatorname{supp}f=\{x\in G:f(x)\ne0\},\qquad a=|A|,

以及右平移与其张成空间

(R_tf)(x)=f(xt^{-1}),\qquad V_f=\operatorname{span}_k\{R_tf:t\in G\}. \tag{1}

每个 $R_tf$ 的支撑是 $At$ ，所以大小仍为 $a$ 。以函数 $h$ 的坐标作为输入，定义左卷积

(L_fh)(x)=\sum_{t\in G}f(xt^{-1})h(t).

其各列恰好是式(1)的右平移，因此 $r=\dim V_f=\operatorname{rank}L_f$ ，其中秩在指定域 $k$ 上计算。支撑与秩不确定性断言

\boxed{\quad a\,r\ge N.\quad} \tag{2}

这里的 $a,r,N$ 是普通整数，乘积与比较也在整数中进行，不是在基域中取剩余类。条件 $f\ne0$ 必须保留：零函数的支撑与秩都是零。

在 $k=\mathbb C$ 时，使用完整不可约矩阵分块，可把式(2)改写为

|\operatorname{supp}f|\sum_\rho d_\rho\operatorname{rank}F_\rho(f)\ge N. \tag{3}

式(2)对任意特征成立；式(3)在这里采用前页的复数表示合同。不能在模特征中换上一份简单表示列表就宣布同样的秩等式。

直觉

每个平移最多覆盖 $a$ 个坐标。如果只需 $r$ 个真实平移就能生成全部平移，那么这 $r$ 份支撑的并集必须覆盖整个群。否则某个坐标在所有线性组合中都永远为零，却又应该能由一个平移搬入非零值。

这个证明只用有限集合与线性张成，不需要平均、内积、复数绝对值或除以群阶。因此它比“先作Fourier变换再数频率”拥有更宽的基域范围。

S3被H等于e与s的三个右陪集分成三对；每对常值的函数空间维数为三，删去一格仍可由同对另一格恢复，删完整一对则留下自由值。 — 支撑覆盖给统一保证，保留行的秩给精确判据

例子与边界

子群指示函数达到等号

取任意子群 $H\le G$ ，令 $f=1_H$ 。其右平移是各右陪集 $Ht$ 的指示函数。不同陪集互不相交，所以这些指示函数线性无关，且全部平移只给这 $N/|H|$ 个方向。于是

|\operatorname{supp}f|=|H|,\qquad r=N/|H|,

恰好达到式(2)的等号，任何域都如此。

等号不要求每个非零值相同。如果 $\psi:H\to k^\times$ 是群同态，将 $f(h)=\psi(h)$ 定义在 $H$ 内、其余处取零。同一右陪集上的不同平移仅相差非零标量，而不同陪集的支撑不交，仍有 $r=N/|H|$ 。这是另一族等号例；本页不借此宣称已经给出一般等号分类。

不要只数非零表示块

在 $S_3$ 上， $\delta_e$ 的三个不可约块分别是 $1,1,I_2$ 。它的支撑大小为1，而加权秩为

1\cdot1+1\cdot1+2\cdot2=6.

若只数“有三个非零块”，就会得到错误的 $1\cdot3\ge6$ 。二维块拥有两个输入列，每列都有两个输出方向，重数不能省。

前页的 $u=(0,-1,1,0,1,-1)$ 只有标准块 $2\sqrt3E_{12}$ 非零，因此支撑为4、加权秩为2，乘积为8，严格大于6。该块只有一个非零条目，但换表示基后非零条目数可能改变；矩阵秩不变。所以式(3)记录的是独立方向，不是某次排版下看到几个非零数字。

模特征中，秩界仍在而简单表示可能漏信息

在 $k=\mathbb F_2$ 、 $G=C_2=\{e,s\}$ 中，取 $f=\delta_e+\delta_s$ 。原卷积矩阵为

L_f=\begin{pmatrix}1&1\\1&1\end{pmatrix},

它的秩为1、支撑大小为2，所以乘积仍等于群阶2。同时 $f*f=0$ ，因为每个系数都是 $1+1=0$ 。

这里 $k[C_2]\cong k[t]/((t-1)^2)$ ，唯一简单表示令 $t$ 作用为1；在这份表示里 $f$ 的像为零。若只读取简单表示的零块，就会错误地把秩1判成0。式(2)从原平移矩阵计算秩，不受这项半单分解失效影响。

推论与应用

支撑覆盖的完整证明

从有限生成族 $\{R_tf:t\in G\}$ 中选出一组基

R_{t_1}f,\ldots,R_{t_r}f.

令 $U=At_1\cup\cdots\cup At_r$ 。每个基向量在 $G\setminus U$ 上为零，所以它们的每个线性组合也在那里为零。

然而对任意 $x\in G$ ，选一个 $z\in A$ ，令 $t=z^{-1}x$ ，则 $xt^{-1}=z$ ，从而 $(R_tf)(x)=f(z)\ne0$ 。这份平移必须是所选基的线性组合，所以 $x$ 必在 $U$ 内。故 $U=G$ ，并有

N=|U|\le\sum_{j=1}^r|At_j|=ra.

证明完成。这里必须从真实平移中选基；若随意换成一组稠密基，就不能再说每个基向量的支撑大小都等于 $a$ 。

平移不变空间中的最小支撑

更一般地，设 $0\ne V\subseteq k^G$ 在所有右平移下保持不变，维数为 $r$ 。任取 $0\ne v\in V$ ，其平移张成 $V_v\subseteq V$ ，故 $\operatorname{rank}L_v\le r$ 。式(2)立即给出

|\operatorname{supp}v|\ge\left\lceil\frac Nr\right\rceil. \tag{4}

有限域上， $V$ 是长度 $N$ 、维数 $r$ 的线性码，这就是其最小非零Hamming重量的下界。此处只是使用该码的既有距离含义，没有声称给任意噪声建立了高效译码算法。

例如 $G=S_3$ 、 $H=\{e,s\}$ ， $V=V_{1_H}$ 是在三个右陪集上分别常值的空间，维数3，最小非零支撑恰为2。按前页顺序，三个右陪集为

\{e,s\},\qquad\{r,r^2s\},\qquad\{r^2,rs\}. \tag{5}

这里必须用右陪集；一般群中不能将它悄悄改成左陪集。若每对的共同值依次为 $\alpha,\beta,\gamma$ ，函数表为 $(\alpha,\beta,\gamma,\alpha,\gamma,\beta)$ 。

从保证唯一到真正恢复擦除

假定发送的函数确实在已知空间 $V$ 内，擦除位置集合为 $E\subseteq G$ ，其余坐标准确已知。如果两份候选在保留坐标上相同，它们的差支撑在 $E$ 内。由式(4)，只要

|E|\,r<N, \tag{6}

这个差就只能为零。因此式(6)是对所有这种擦除位置都有效的充分保证。它不是必要条件，也不保证输入数据本来就来自 $V$ 。

实际给出 $V$ 的列基矩阵 $B\in k^{N\times r}$ ，令 $K=G\setminus E$ 。未知函数写成 $Bc$ ，恢复任务便是

B_Kc=y_K. \tag{7}

用精确消元同时判断相容性和保留行的秩。对任意合法右端都唯一恢复的精确条件是 $\operatorname{rank}B_K=r$ ；若秩不足，则每个相容右端都有非零核方向的歧义；若不相容，就应报告数据违反空间模型，而非硬填一个“恢复值”。

式(5)的空间允许任意一个擦除。如果删去 $e,r$ 两处，仍每对留一处，故式(7)满列秩，依旧能唯一恢复，虽然式(6)已不满足。若删去 $e,s$ 整对，共同值 $\alpha$ 完全未知，便有非唯一解。这同时区分统一数量保证与具体位置判据。

这些结论针对位置已知、剩余值无误的擦除。未知错误的位置、近似零的阈值以及浮点病态性是其他输入条件，不能从整数支撑计数自动获得保证。可在四项终点任务中逐个验出恢复、歧义与不相容的证书。

参考资料

Daniel Goldstein、Robert M. Guralnick、I. M. Isaacs，Inequalities for finite group permutation modules，arXiv:math/0310169v1，2003-10-11，§1，Theorem B及其完整证明、紧接的等号讨论：任意域、传递右群集上的平移基支撑覆盖。
Avi Wigderson、Yuval Wigderson，The uncertainty principle: variations on a theme，2020-09-10版，§3.2，Definition 3.7与Theorem 3.9：复数有限群的加权矩阵秩版本。本文显式保留非零函数条件，并用前一来源的任意域证明推导擦除应用。

形式陈述 ​

子群指示函数达到等号 ​

不要只数非零表示块 ​

模特征中，秩界仍在而简单表示可能漏信息 ​

支撑覆盖的完整证明 ​

平移不变空间中的最小支撑 ​

从保证唯一到真正恢复擦除 ​

反向链接