整数解稀疏性的理论分析与证明

### 整数解稀疏性的理论分析与证明 在数学领域中，对于整数解稀疏性的研究有着重要的意义。本文将围绕相关定理的证明，深入探讨群论、格理论以及Ehrhart理论在其中的应用。 #### 1. 定理证明基础 定理1的证明基于群论、格理论和Ehrhart理论的结合。从高层次来看，群论和格理论的结合与Gomory以及Aliev等人的论文有相似之处。Gomory研究了整数规划（IP）的值函数，并证明了当右侧向量足够大时其具有周期性；Aliev等人则证明了函数$\sigma(A, b)$在$b$足够大时的周期性。而本文的精细分析能够量化支持函数较小时右侧向量的数量，这不仅需要群论和格理论，还需要Ehrhart理论。 #### 2. 平行六面体的群结构 设$W \in Z^{m×m}$是一个可逆矩阵，也可将其视为一组$m$个线性无关的列向量。定义$\Pi(W)$为$W$生成的基本平行六面体内的整数向量集合： $\Pi(W) := \{z \in Z^{m} : z = W\lambda, \lambda \in [0, 1)^m\}$ 对于每个$b \in Z^{m}$，存在唯一的$g \in \Pi(W)$，使得$b = g + Wz$，其中$z \in Z^{m}$。由此可以定义一个余数函数$\rho_W : Z^{m} \to \Pi(W)$： $\rho_W(b) = \rho_W(g + Wz) \to g$ $Z^{m}$在$\rho_W$下的像（即$\Pi(W)$）通过运算$+_{G_W} : \Pi(W) × \Pi(W) \to \Pi(W)$定义为一个群$G_W(Z^{m})$，其中$g +_{G_W} h \to \rho_W(g + h)$。$G_W(Z^{m})$的单位元是$Z^{m}$中的零向量，且$|G_W(Z^{m})| = |\det(W)|$，这表明$G_W(Z^{m})$是有限群。 对于任意子集$B \subseteq Z^{m}$，可以定义$G_W(Z^{m})$的子群$G_W(B)$： $G_W(B) := \{\rho_W(Bz) : z \in Z^{|B|}\}$ 若$B = \varnothing$，则$G_W(B) := \{0\}$。$G_W(B)$是$G_W(Z^{m})$的子群，因为$\{Bz : z \in Z^{|B|}\}$是$Z^{m}$的子格。 下面是关于群$G_W(B)$的两个重要引理： - **引理1**：设$W \in Z^{m×m}$是可逆矩阵，对于任意$B \subseteq Z^{m}$，有$G_W(B) = \{\rho_W(Bz) : z \in Z^{|B|}_{\geq 0}\}$。 - **证明**：对于每个$z \in Z^{|B|}$，可将$Bz$写为$Bz = \sum_{b \in B:z_b \geq 0} z_bb + \sum_{b \in B:z_b < 0} z_bb$。因此，只需证明对于每个$b \in B$，$\rho_W(-b) \in \{\rho_W(By) : y \in Z^{|B|}_{\geq 0}\} =: C$。若$\rho_W(b) = 0$，则$\rho_W(-b) = \rho_W(b) = 0 \in C$；若$\rho_W(b) \neq 0$，由于$G_W(B)$是有限的，存在$\tau \in Z_{\geq 2}$使得$\rho_W(\tau b) = 0$。注意到$\rho_W((\tau - 1)b) + \rho_W(b) = 0 = \rho_W(b) + \rho_W(-b)$，所以$\rho_W(-b) = \rho_W((\tau - 1)b) \in C$。 - **引理2**：设$W \in Z^{m×m}$是可逆矩阵，$B \subseteq Z^{m}$。若$t \in Z_{\geq 0}$且$t \geq \varphi(W)$，则存在$w_1, \cdots, w_t \in B$（可能有重复），使得$G_W(\{w_1, \cdots, w_t\}) = G_W(B)$。 - **证明**：设$s := \varphi(W)$。首先证明对于每个$r \in \{0, \cdots, s\}$，存在$w_1, \cdots, w_r \in B$（可能有重复），使得要么$G_W(\{w_1, \cdots, w_r\}) = G_W(B)$，要么$G_W(\varnothing) \subsetneq G_W(\{w_1\}) \subsetneq \cdots \subsetneq G_W(\{w_1, \cdots, w_r\})$。通过对$r$进行归纳证明该结论。当$r = 0$时，结论显然成立。假设对于$r \in Z_{\geq 0}$结论成立，考虑$r + 1$的情况。定义$G_r := G_W(\{w_1, \cdots, w_r\})$。若$G_r = G_W(B)$，则$w_{r + 1} := w_r$可证明$r + 1$时的结论；若$G_r \subsetneq G_W(B)$，由于$G_0 \subsetneq \cdots \subsetneq G_r$，且若对于每个$b \in B$都有$\rho_W(b) \in G_r$，则会导致矛盾。因此，存在$w_{r + 1} \in B$使得$\rho_W(w_{r + 1}) \notin G_r$，从而序列$G_0, \cdots, G_r, G_{r + 1} := G_W(\{w_1, \cdots, w_{r + 1}\})$满足条件。若$G_s = G_W(B)$，则令$w_{s + 1} = \cdots = w_t := w_s$可得出$G_W(\{w_1, \cdots, w_t\}) = G_W(B)$；若$G_s \subsetneq G_W(B)$，会导致矛盾，因为$|G_W(Z^{m})|$的质因数个数有限，而$|G_s|$的质因数个数过多。 #### 3. 锥中的格点 一个集合$\Lambda \subseteq Z^{m}$是格，若满足$0 \in \Lambda$，对于$x, y \in \Lambda$有$x + y \in \Lambda$，且若$x \in \Lambda$则$-x \in \Lambda$。这里假设格$\Lambda$包含$m$个线性无关的向量。对于$B \subseteq R^{m}$和$x \in R^{m}$，定义$B + x := \{b + x : b \in B\}$。 下面是两个关于锥中格点的重要引理： - **引理3**：设$v_1, \cdots, v_m \in Z^{m}$是线性无关的向量，$K := cone(\{v_1, \cdots, v_m\})$。对于$t \in Z_{\geq 0}$和$x_1, \cdots, x_t \in Z^{m}$，存在$z = \sum_{i = 1}^{m} k_iv_i \in K \cap Z^{m}$，其中$k_1, \cdots, k_m \in Z_{\geq 0}$，使得$K + z \subseteq K \cap \bigcap_{i = 1}^{t}(K + x_i)$。（该引理的证明在附录B中） - **引理4**：设$W \subseteq Z^{m}$使得$cone(W)$是$m$维的。设$s \in Z_{\geq 1}$，$W^1, \cdots, W^s \subseteq W$是线性无关的子集，且$cone(W) = \bigcup_{i = 1}^{s} cone(W^i)$。设$\Lambda \subseteq Z^{m}$是格，且$W^1, \cdots, W^s \subseteq \Lambda$。对于每个$i \in \{1, \cdots, s\}$，选择任意$k_w \in Z_{\geq 0}$，定义$z_i := \sum_{w \in W^i} k_w w$。则$\lim_{t \to \infty} \frac{|\{-t, \cdots, t\}^m \cap \bigcup_{i = 1}^{s}(\Lambda \cap (cone(W^i) + z_i))|}{|\{-t, \cdots, t\}^m \cap \bigcup_{i = 1}^{s}(\Lambda \cap cone(W^i))|} = 1$。 - **证明**：对于$i \in \{1, \cdots, s\}$，设$K_i := cone(W^i)$。要证明该极限等于1，只需证明$\lim_{t \to \infty} \frac{|\{-t, \cdots, t\}^m \cap \bigcap_{i = 1}^{s}(\Lambda \cap [K_i \setminus (K_i + z_i)])|}{|\{-t, \cdots, t\}^m \cap \bigcup_{i = 1}^{s}(\Lambda