凸幾何学と離散幾何学

$\operatorname{conv}(S)$内の凸結合は一見すると$S$の任意に多くの点を含み得るが、$\mathbb{R}^d$では$d + 2$個以上の点は必ずアフィン従属である。その線形関係を使って重みを非負に保ったまま点を一つずつ消去でき、最終的にたかだか$d + 1$個の点(単体)しか残らない。$\mathbb{R}^d$内の有限個の凸集合族において任意の$d + 1$個が共通点を持てば全体も共通点を持つというヘリーの定理は、この次元限界と表裏一体である。

項数$k$が最小になるように、$x_i \in S$、$\lambda_i > 0$、$\sum_{i=1}^{k} \lambda_i = 1$として$x = \sum_{i=1}^{k} \lambda_i x_i$と表す。$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$に対して係数の和が$1$のまま$x = \sum_{i=1}^{k} (\lambda_i - t \mu_i) x_i$と書ける。$t = \min_{\mu_i > 0} (\lambda_i / \mu_i) > 0$と選べば、新しい係数$\lambda_i - t \mu_i$はすべて非負となり、少なくとも一つが$0$になる。これは$x$を$S$のたかだか$k - 1$個の点の凸結合として表すことになり、$k$の最小性に矛盾する。

これは整数論における連続版の鳩の巣原理である。対称な凸体の体積が格子の基本領域$2^d$個分を超えると、それを$2$分の1に縮小しても体積は基本領域1個分より大きく、縮小された図形の異なる二点の差が非零の格子ベクトルにならざるを得ない。そして対称性と凸性がその格子ベクトルを$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$は互いに素ではあり得ない(ブリッヒフェルトの原理)。

$B_u \cap B_v \neq \emptyset$となる相異なる格子ベクトル$u \neq v$を$\Lambda$から選ぶ。すると$p - u = q - v$を満たす相異なる二点$p, q \in \frac{1}{2} K$が存在し、$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\})$内の非零格子点である。