凸几何与离散几何

$\operatorname{conv}(S)$中的凸组合表面上可以涉及$S$中任意多个点,但在$\mathbb{R}^d$中任意$d + 2$个或更多点必然仿射相关。利用这一线性关系可以每次消去一个点并保持所有权重非负,直到至多剩下$d + 1$个点(一个单纯形)。赫利定理——$\mathbb{R}^d$中有限个凸集只要任取$d + 1$个有公共点则全体必有公共点——正是这一维数界的直接姊妹结果。

取项数$k$最小的表示$x = \sum_{i=1}^{k} \lambda_i x_i$,其中$x_i \in S$,$\lambda_i > 0$,且$\sum_{i=1}^{k} \lambda_i = 1$。我们断言$k \le d + 1$。

反证假设$k \ge d + 2$。则$\mathbb{R}^d$中的$k - 1 \ge d + 1$个差向量$x_2 - x_1, x_3 - x_1, \ldots, x_k - x_1$线性相关,故存在不全为零的标量$\mu_2, \ldots, \mu_k$使得$\sum_{i=2}^{k} \mu_i (x_i - x_1) = 0$。令$\mu_1 = -\sum_{i=2}^{k} \mu_i$,便得到$\sum_{i=1}^{k} \mu_i x_i = 0$且$\sum_{i=1}^{k} \mu_i = 0$,并且至少有一个$\mu_i > 0$。

对任意实数$t$,都有$x = \sum_{i=1}^{k} (\lambda_i - t \mu_i) x_i$且系数之和仍为$1$。取$t = \min_{\mu_i > 0} (\lambda_i / \mu_i) > 0$;此时每个新系数$\lambda_i - t \mu_i$都非负,且至少有一个变为$0$,从而将$x$表为$S$中至多$k - 1$个点的凸组合,与$k$的最小性矛盾。

这是数论中的连续鸽巢原理:一旦中心对称凸体的体积超过格的$2^d$个基本区域的体积,将它按比例$2$缩小后体积仍大于一个基本区域,迫使缩小后图形中有两点相差一个非零格向量——随后对称性加上凸性又把该格向量拉回到$K$内部。

考虑缩小一半的凸体$\frac{1}{2} K = \{\, x / 2 : x \in K \,\}$。在$d$维空间中缩放会使体积乘以$2^{-d}$,因此假设$\operatorname{vol}(K) > 2^d \det(\Lambda)$变为$\operatorname{vol}(\frac{1}{2} K) > \det(\Lambda)$。

设$F$是$\Lambda$的基本平行多面体,使得$\mathbb{R}^d = \bigsqcup_{v \in \Lambda} (F + v)$且$\operatorname{vol}(F) = \det(\Lambda)$。将$\frac{1}{2} K$切成碎片$A_v = (\frac{1}{2} K) \cap (F + v)$,再通过$B_v = A_v - v \subseteq F$将每块碎片平移回$F$中。由于所有$B_v$的体积之和等于$\operatorname{vol}(\frac{1}{2} K) > \operatorname{vol}(F)$,这些集合$B_v$不可能两两不相交(布利希费尔特原理)。

在$\Lambda$中取不同的格向量$u \neq v$使得$B_u \cap B_v \neq \emptyset$。于是存在两个不同的点$p, q \in \frac{1}{2} K$满足$p - u = q - v$,故$p - q = u - v \in \Lambda \setminus \{0\}$。由$p, q \in \frac{1}{2} K$知$2p, 2q \in K$;由$K$的中心对称性得$-2q \in K$,再由$K$的凸性知中点$\frac{1}{2}(2p) + \frac{1}{2}(-2q) = p - q$属于$K$。因此$p - q$就是$K \cap (\Lambda \setminus \{0\})$中的非零格点。