こんにちは、すく(0214sh7)です。
東工大数学系の4年生で、traPではアルゴリズム班のリーダーをやっています。そろそろ引退

東京工業大学プログラミングコンテスト2022 に運営･作問者として参加しました。そこに出題した問題にエルハート多項式を用いるものがあるのですが、エルハート多項式についてを簡潔にまとめてみたくなったのでこの記事を書いています。

ところで、ピックの定理はご存知ですか？

ピックの定理

ピックの定理

平面上の凸多角形 $\mathcal{P}$ は、その頂点の座標がすべて整数で、

• (位相的な)内部にある座標が整数である点の個数が $I$
• (位相的な)境界にある座標が整数である点の個数が $B$

であるとき、その面積 $A$ は

$$A=I+\frac{B}{2}-1$$

で表される。

この定理は発見者であるゲオルク･アレクサンダー･ピック(Georg Alexander Pick)の名前からピックの定理と呼ばれています。小学校で習うこともあります。

この定理は実は $3$ 次元以上の多次元に拡張することができます。それを説明するにあたり、まずは多角形の拡張を説明しましょう。

多面体

多面体の定義は主に二通りありますが、今回はそのうち頂点記述と呼ばれる方法を使います。
もう片方は超平面記述と呼ばれています。

$d$ 次元空間 ${\mathbb{R}}^d$ 上の集合 $\mathcal{P}$ が多面体(polytope) であるとは、 ${\mathbb{R}}^d$ の有限個の点 $\{v_1,\cdots ,v_n\}$ の凸包として $\mathcal{P}$ が表せることを言います。つまり、

$$\mathcal{P}=\{{\lambda }_1{v}_1+\cdots +{\lambda }_n{v}_n\mid \forall {\lambda }_k\ge 0,\sum {\lambda }_k=1\}$$

で表せるような $\mathcal{P}$ のことを多面体と呼び、 $\mathcal{P}=conv\{v_1,\cdots ,v_n\}$ と書きます。また、 $v_k$ を $\mathcal{P}$ の頂点(vertex)といいます。

多面体の他にも前提知識がいくつかあるので並べます。

格子点

ユークリッド空間 ${\mathbb{R}}^d$ の部分集合 ${\mathbb{Z}}^d$ は格子(lattice,束とは異なる)と呼ばれる集合の代表例であり、今回は ${\mathbb{Z}}^d$ の元、つまり全ての座標が整数である点を格子点(lattice point)と呼ぶことにします。

拡大

${\mathbb{R}}^d$ の部分集合 $S$ について、その $n$ 次拡大( $n$ th dilation) $nS$ とは、

$$\{(n{x}_1,n{x}_2,\cdots ,n{x}_d)\mid (x_1,x_2,\cdots ,x_n)\in S\}$$

で定義される集合のことです。

$0$ 次拡大は原点のみから成ります。

凸

集合 $S$ が凸(convex)であるとは、任意の $x,y\in S$ と実数 $t(0\le t\le 1)$ について $tx+(1-t)y\in S$ が満たされることを言います。

左は凸ですが、右は灰色の線分がはみ出すので凸ではありません。

整

多面体 $\mathcal{P}$ が整(integral)とは、 $\mathcal{P}$ の頂点がすべて整数座標、つまり格子点であることを言います。

離散体積

多面体 $\mathcal{P}$ に含まれる格子点の個数を離散体積(dicrete volume)といいます。
そして、 $t$ 次拡大 $t\mathcal{P}$ の離散体積を $L_{\mathcal{P}}(t)$ と書きます。( $:=\#(t\mathcal{P}\cap {\mathbb{Z}}^d)$ )

例1

たとえば、立方体 $C:={[0,1]}^3$ を考えます。
$C$ には $8$ つの格子点 $(0,0,0),(0,0,1),(0,1,0),(0,1,1),(1,0,0),(1,0,1),(1,1,0),(1,1,1)$ が含まれているため $L_C(1)=8$ です。
同様に $2C$ には格子点が $27$ 個含まれており $L_C(2)=27$ です。同様に、 $L_C(t)=(t+1{)}^3=t^3+3t^2+3t+1$ であることを調べることができます。

例2

四面体 $R:=conv\{(0,0,0),(1,0,0),(0,1,0),(0,0,1)\}$ を考えます。
$R$ には格子点が $4$ つ含まれており $L_R(1)=4$ です。
$2R$ には格子点が $10$ 個含まれており $L_R(2)=10$ です。
$tR$ には格子点が $\frac{1}{6}(t+1)(t+2)(t+3)$ 個含まれており $L_R(t)=\frac{1}{6}{t}^3+t^2+\frac{11}{6}t+1$ です。

以上の $2$ つの例では $L_{\mathcal{P}}(t)$ がともに多項式になっています。実はこれらは多くの多面体において多項式になるのです！

エルハート多項式

エルハートの定理

$d$ 次元整凸多面体 $\mathcal{P}$ について、$L_{\mathcal{P}}(t)$ は $t$ について $d$ 次多項式になる。

この定理はこれを証明したフランスの数学者ウジェーヌ・エルハート(Eugène Ehrhart)にちなんでエルハートの定理と、$L_{\mathcal{P}}(t)$ はエルハート多項式(Ehrhart polynomial)と呼ばれています。

証明を書こうと思ったのですがとてもここで書けるようなボリュームじゃなかったので諦めました。
Springerの"Computing the Continuous Discretely"(
Matthias Beck, Sinai Robins)という本に書いてあるので興味がある方はそちらをご覧ください。

このため、 $L_{\mathcal{P}}(0),L_{\mathcal{P}}(1),\cdots ,L_{\mathcal{P}}(d)$ がわかっていれば多項式補完によってエルハート多項式を求めることができます。さらに定義から $L_{\mathcal{P}}(t)$ はすべて整数なので、多項式の係数はすべて有理数になります。
しかし、 $0$ 次拡大 $0\mathcal{P}$ は原点のみから成るので、 $L_{\mathcal{P}}(0)=1$ であることはすぐにわかります。
実装する際には $d$ が小さかったり、どの $t$ を使うのかが決まっていることが多いので、ヴァンデルモンド行列の逆行列を埋め込むとよいでしょう。

他にも、エルハート多項式を求めるための便利な性質を紹介します。

先頭係数

$d$ 次元整凸多面体 $\mathcal{P}$ のエルハート多項式を $L_{\mathcal{P}}(t)=c_d{t}^d+\cdots +c_{1}t+c_0$ とする。
このとき、先頭係数 $c_d$ は $\mathcal{P}$ の体積と一致する。

これを証明するには、${\lim }_{t\to \infty }\frac{L_{\mathcal{P}}(t)}{t^d}(={\lim }_{t\to \infty }\frac{\#(t\mathcal{P}\cap {\mathbb{Z}}^d)}{t^d}={\lim }_{t\to \infty }\#(\mathcal{P}\cap (\frac{1}{t}\mathbb{Z}{)}^d))=vol(\mathcal{P})$ を示すとよいでしょう。これはリーマン積分と同じノリで $\mathcal{P}$ を小さなキューブで近似するとわかります。

多面体の頂点からうまく体積を求められればエルハート多項式を求めるために必要な情報が一つ減ります。
たとえば $3$ 次元多面体については表面を構成する三角形(ポリゴン)がわかれば体積が求まるので先頭係数を求めることができます。

例1

立方体 $C:={[0,1]}^3$ のエルハート多項式は $t^3+3t^2+3t+1$ であり、その先頭係数 $1$ は $C$ の体積と一致しています。

例2

四面体 $R:=conv\{(0,0,0),(1,0,0),(0,1,0),(0,0,1)\}$ のエルハート多項式は $\frac{1}{6}{t}^3+t^2+\frac{11}{6}t+1$ であり、その先頭係数 $\frac{1}{6}$ は $R$ の体積と一致しています。

エルハート-マクドナルドの相互法則

エルハート-マクドナルドの相互法則

$d$ 次元凸整多面体 $\mathcal{P}$ とその(位相的な)内部 ${\mathcal{P}}^{\circ }$ 、正整数 $t$ に対し、

$$L_{\mathcal{P}}(-t)=(-1{)}^d{L}_{{\mathcal{P}}^{\circ }}(t)$$

が成り立つ。

これを エルハート-マクドナルドの相互法則 (Ehrhalt-Macdonald reciprocity) といいます。
このため、$\mathcal{P}$ またはその拡大 $t\mathcal{P}$ の内部の格子点の個数がわかっていれば $\mathcal{P}$ のエルハート多項式の負の項を調べることができるわけですね。

例1

1辺の長さが $2$ の立方体 $D:={[0,2]}^3$ を考えます。
$C$ には格子点が $27$ 個含まれており、その内部には $1$ つだけあります。
また $2$ 次拡大 $2D$ には格子点が $125$ 個含まれています。
このため、

$$L_D(2)=125,L_D(1)=27,L_D(0)=1,L_D(-1)=-1$$

がわかります。
多項式補完によって $L_D(t)=8t^3+12t^2+6t+1$ が求まります。

$3$ 次拡大 $3D$ には格子点が $343$ 個含まれており、これは $L_D(3)$ と一致します。

例2

一般の多角形( $2$ 次元多面体) $\mathcal{P}$ のエルハート多項式を考えてみましょう。
$\mathcal{P}$ の内部の格子点の数を $I$、 $\mathcal{P}$ の境界の格子点の数を $B$ とします。すると

$$L_{\mathcal{P}}(1)=I+B$$

$$L_{\mathcal{P}}(0)=1$$

$$L_{\mathcal{P}}(-1)=I$$

なので、 $L_{\mathcal{P}}(t)=c_2{t}^2+c_{1}t+c_0$ として

$$c_2+c_1+c_0=I+B$$

$$c_0=1$$

$$c_2-c_1+c_0=I$$

なので、これを解いて

$$c_2=I+\frac{B}{2}-1,c_1=\frac{B}{2},c_0=1$$

になります。なので、 $L_{\mathcal{P}}(t)=(I+\frac{B}{2}-1)t^2+\frac{B}{2}t+1$ です。

先述したように先頭係数 $c_2$ は $\mathcal{P}$ の面積 $A$ なので、

$$L_{\mathcal{P}}(t)=A{t}^2+\frac{B}{2}t+1$$

と書くこともできます。特に、

$$A=I+\frac{B}{2}-1$$

が成り立っており、これはピックの定理そのものです。

おまけ

$3$ 次元多面体に対して、

• 内部の格子点の数
• 境界の格子点の数
• 体積

からエルハート多項式を求めることができます。考えてみましょう！

おわりに

ちなみに多面体 $\mathcal{P}$ が凸かつ頂点が有理数座標なら、 $L_{\mathcal{P}}(t)$ は準多項式(quasipolynomial)になり、やや面倒です。

本格的な作問はCPCTF22に続きTTPC2022が2回目なのですが、作問って楽しいですね。これを使う問題の作問の想定解書くのは苦行だったけどな！！！

いい数学ライフを！！！！！(半ギレ)