インテジャーズ

インテジャーズ

数、特に整数に関する記事。

ミンコフスキーの凸体定理

所謂"数の幾何学"における基本的定理である、Minkowskiの凸体定理を紹介します。

nを正整数とし、この記事では\mathbb{R}^nの格子として\mathbb{Z}^nのみを扱います。また、体積について厳密にはRiemann積分論などを用いて証明する必要がある事実を断りなしに使います。

Minkowskiの凸体定理 Sは体積を持ち*1\mathrm{vol}(S) > 2^nを満たすような\mathbb{R}^n内の凸体とする。このとき、非自明な格子点 x \in \mathbb{Z}^n\setminus\{0\}が存在して、x \in Sが成り立つ。

未定義用語を定義します。

定義 \mathbb{R}^nの空でない部分集合S凸集合であるとは、
\displaystyle x, y \in S, \ t \in [0, 1) \Longrightarrow tx+(1-t)y \in S
が成り立つときにいう。また、S原点対称であるとは
\displaystyle x \in S \Longrightarrow -x \in S
が成り立つときにいう。Sが有界かつ凸集合かつ原点対称であれば、S凸体であるという。

定理の証明のために補題から始めましょう。

補題 Sは体積を持ち、\mathrm{vol}(S) > 1を満たすような\mathbb{R}^nの有界部分集合とする。このとき、x, y \in Sが存在して、x-y \in \mathbb{Z}^n\setminus\{0\}が成り立つ。

証明. a=(a_1, \dots, a_n) \in \mathbb{Z}^nに対して

\mathrm{Box}(a):=\{(x_1, \dots, x_n) \in \mathbb{R}^n \mid a_i \leq x_i < a_i+1, \ 1 \leq i \leq n\}

とし、S(a):=S\cap \mathrm{Box}(a)とする。このとき、

\displaystyle \sum_{a \in \mathbb{Z}^n}\mathrm{vol}(S(a)) = \mathrm{vol}(S)

である(実質有限和)。平行移動で体積は変わらないので、

\displaystyle \sum_{a \in \mathbb{Z}^n}\mathrm{vol}(S(a)-a) = \mathrm{vol}(S) > 1

が得られるが、任意のa \in \mathbb{Z}^nに対してS(a)-a \subset \mathrm{Box}(0) かつ \mathrm{vol}(\mathrm{Box}(0))=1なので、相異なる a, b \in \mathbb{Z}^nが存在して

\displaystyle \left(S(a)-a\right) \cap \left(S(b)-b\right) \neq \emptyset

が成り立つ(鳩ノ巣原理)。よって、x \in S(a), \ y \in S(b)が存在して、x-a=y-b、すなわち x-y=a-b \in \mathbb{Z}^n \setminus\{0\}が成り立つ。 Q.E.D.

凸体定理の証明. Sを定理の主張における凸体とし、S'

S':=\{(\frac{x_1}{2}, \dots, \frac{x_n}{2}) \in \mathbb{R}^n \mid (x_1, \dots, x_n) \in S\}

と定義する。このとき、S'は体積を持ち、\mathrm{vol}(S') > 1を満たすような\mathbb{R}^nの有界部分集合なので、補題より x, y \in S'が存在して

x-y \in \mathbb{Z}^n\setminus \{0\}

が成り立つ。S'の定義より2x, 2y \in SSは原点対称なので -2y \in S。よって、Sは凸集合なので

\displaystyle x-y = \frac{2x+(-2y)}{2} \in S

となり、Sは非自明な格子点(x-y)を持つことが示された。 Q.E.D.


私は若い頃、この定理のことがとてつもなく好きだった時期がありました。

*1:Jordan可測。