关于模r矩阵存在满足0-范数模r为0的非零向量的证明问询

阿华AIGC实验室

2026-4-22

定义

记$\lVert \vec x \rVert_0$为向量$\vec x$中非零元素的个数。
为了简便，将整数模$r$的环$\mathbb{Z} / r\mathbb{Z}$记作$\mathbb{Z}_r$。

待证命题

对于所有满足$r \geq 2$的自然数$r$（不一定是质数），当自然数$n$足够大时，对任意自然数$m$以及任意矩阵$A \in \mathbb{Z}_r^{m \times n}$，都存在非零向量$\vec x \in \mathbb{Z}_r^{n \times 1}$，使得$\lVert A \vec x \rVert_0 \equiv 0 \mod r$。这里的矩阵乘法和0-范数的计算都是在模$r$意义下进行的。

当前进展

当$m < n$时，矩阵$A$是奇异的，显然存在非零$\vec x$使得$A\vec x = \vec 0$，此时$\lVert A\vec x \rVert_0 = 0$，自然满足模$r$同余于0的条件，所以这种情况命题成立。
当$r$是质数时，整个命题成立：我们可以利用费马小定理，将$\lVert A \vec x \rVert_0 \mod r$改写为关于$\vec x$各分量的多项式，该多项式的次数为$r-1$。这里有个关键的结论：任何一个仅在零输入处取0、其余非零输入处取非零的多项式（也就是在$\mathbb{Z}_r$上表示逻辑或的多项式），它的次数至少为$n$——因为唯一满足“仅在$\vec 0$处取1、其余取0”的多项式是$NOR(\vec x) = \prod_i (1-x_i^{r-1})$，其次数为$n(r-1)$。如果存在一个表示逻辑或的多项式次数小于$n$，那么我们可以写出$NOR(\vec x) = 1 - OR(\vec x)^{r-1}$，这样$NOR(\vec x)$的次数就会小于$n(r-1)$，这与前面的结论矛盾。因此，只要$n \geq r$，就一定存在非零$\vec x$使得$\lVert A \vec x \rVert_0 \equiv 0 \mod r$。
我很确定当$r$是质数幂时，类似的多项式技巧同样适用，只是还没把具体的细节推导完整。