Ehrhart多項式

同義語:Ehrhart polynomial

概要

Ehrhart多項式(Ehrhart polynomial)とは、頂点がすべて格子点である $\mathbb{R}^d$ の $d$ 次元の凸多面体 $P$ について、$tP$ に含まれる格子点の個数を正の整数 $t$ の関数として表す多項式である。Ehrhart の定理により、この個数は $t$ の $d$ 次多項式に一致し、最高次の係数は $P$ の体積、定数項は $1$ である。二項係数 $\binom{t+d-j}{d}$ で展開した係数($h^*$ ベクトル)は非負整数で、負の整数での値は内部の格子点の個数を符号付きで与える(Ehrhart–Macdonald の相反定理)。平面の凸な格子多角形では Pick の定理にあたるが、3 次元では $P$ 自身の境界と内部の格子点の個数だけから体積は決まらない。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: 格子点, 多面体, 凸包, 三角形分割, 重心座標, 二項係数

格子多角形 $Q$ を $t$ 倍した図形の格子点の個数は、Pickの定理 から $\operatorname{Area}(Q)\,t^2+\frac{B}{2}t+1$($B$ は $Q$ の境界の格子点の個数)という $t$ の多項式になる(格子点 の系「格子多角形を整数倍したときの格子点の個数」)。Ehrhart の定理は、これが任意の次元の格子多面体で成り立つことを主張する。すなわち、頂点がすべて格子点である $\mathbb{R}^d$ の $d$ 次元の凸多面体 $P$ について、$tP$ に含まれる格子点の個数は正の整数 $t$ の $d$ 次多項式であり、その最高次の係数は $P$ の体積、定数項は $1$ である。この多項式を Ehrhart 多項式 という。
この記事では、格子単体の半開の錐の格子点を「基本平行体」の格子点で数える方法と、三角形分割を半開の単体の非交和に組み直す方法を使って、Ehrhart の定理を完全に証明する。同じ証明から、Ehrhart 多項式を二項係数の基底で展開した係数が非負整数であること(Stanley の非負性)も得られる。次に単体の場合の相反定理を証明し、Reeve の四面体で 3 次元では Pick の定理の類似が成り立たないことを確かめる。

定義

以下 $d\ge1$ とし、$\mathbb{Z}^d$ の点を格子点という(格子点)。

格子多面体

$\mathbb{R}^d$ の有限個の格子点の 凸包 を 格子多面体(lattice polytope)という。格子多面体は 多面体 の意味の凸多面体で、その頂点はすべて格子点である。$P$ を含む最小のアフィン部分空間の次元を $P$ の 次元 といい、$\dim P=d$ のとき $P$ は 全次元 であるという。有限個の有理点(座標がすべて有理数の点)の凸包を 有理多面体 という。

格子点の数え上げ関数

有界な集合 $S\subset\mathbb{R}^d$ と正の整数 $t$ について $tS:=\{tx\mid x\in S\}$ とおき、
$$ L_S(t):=\#\bigl(tS\cap\mathbb{Z}^d\bigr) $$
を $S$ の 格子点の数え上げ関数 という。$P$ が格子多面体で、多項式 $E_P(x)\in\mathbb{Q}[x]$ がすべての正の整数 $t$ について $E_P(t)=L_P(t)$ をみたすとき、$E_P$ を $P$ の Ehrhart 多項式(Ehrhart polynomial)という(無限個の点で値が決まるので、存在すれば一意である)。$P$ の相対的な内部($P$ を含む最小のアフィン部分空間の中での内部)を $P^\circ$ と書く。

二項係数を多項式として $\binom{x+d}{d}:=\frac{(x+1)(x+2)\cdots(x+d)}{d!}$ と書く。整数 $s\ge0$ では $\binom{s+d}{d}$ は通常の二項係数で、$\{k\in\mathbb{Z}_{\ge0}^{d+1}\mid k_0+\cdots+k_d=s\}$ の元の個数に等しい(二項係数)。また $s=-1,-2,\dots,-d$ では $\binom{s+d}{d}=0$ である。

Ehrhart の定理

Ehrhartの定理

$P\subset\mathbb{R}^d$ を全次元の格子多面体とする。このとき非負整数 $h_0^*,h_1^*,\dots,h_d^*$ があって、すべての正の整数 $t$ について
$$ L_P(t)=\sum_{j=0}^{d}h_j^*\binom{t+d-j}{d} $$
が成り立つ。とくに $P$ の Ehrhart 多項式 $E_P(x)=\sum_j h_j^*\binom{x+d-j}{d}$ が存在して、次をみたす。

  1. $E_P$ は $d$ 次多項式で、$x^d$ の係数は $P$ の体積 $\operatorname{vol}(P)$ である。
  2. $E_P(0)=1$ である($h_0^*=1$)。
  3. $h_0^*+h_1^*+\cdots+h_d^*=d!\operatorname{vol}(P)$ であり、$E_P$ の各係数に $d!$ を掛けると整数になる。
証明の方針と $h^*$ ベクトル

$(h_0^*,\dots,h_d^*)$ を $P$ の $h^*$ ベクトル という。$\binom{x+d-j}{d}$($j=0,\dots,d$)は次数 $d$ 以下の多項式の空間の基底なので、$h^*$ ベクトルは $E_P$ から一意に決まる。証明では、単体の半開の錐の格子点を数える補題(lem-ehr-half-open)と、三角形分割を半開の単体の非交和に組み直す補題(lem-ehr-decomposition)を用意し、両者を足し合わせる(prf-ehr-main)。

格子単体の半開の錐

$\Delta\subset\mathbb{R}^d$ を頂点 $v_0,\dots,v_d$ が格子点の $d$ 次元単体とし、$x\in\Delta$ の 重心座標 を $\lambda_0(x),\dots,\lambda_d(x)$($\lambda_i\ge0$、$\sum_i\lambda_i=1$、$x=\sum_i\lambda_iv_i$)と書く。$\lambda_i$ は $\mathbb{R}^d$ 全体のアフィン関数に延びる。$I\subset\{0,\dots,d\}$ について
$$ \Delta_I:=\{x\in\Delta\mid i\in I\text{ ならば }\lambda_i(x)>0\} $$
を 半開の単体 という($\Delta_\emptyset=\Delta$。$I$ に属する $i$ について、$v_i$ の対面を除いたもの)。$w_i:=(v_i,1)\in\mathbb{Z}^{d+1}$ とおき、
$$ \Pi_I:=\Bigl\{\sum_{i=0}^d\mu_iw_i\Bigm| i\in I\text{ なら }0< \mu_i\le1,\ i\notin I\text{ なら }0\le\mu_i<1\Bigr\} $$
を 半開の基本平行体 という。$p=(p',p_{d+1})\in\mathbb{R}^{d+1}$ の最後の座標 $p_{d+1}$ を $p$ の 高さ といい、$\operatorname{ht}(p)$ と書く。

半開の単体の格子点

$I\neq\{0,1,\dots,d\}$ とし、$h_{I,j}$ を $\Pi_I\cap\mathbb{Z}^{d+1}$ の高さ $j$ の点の個数とする。このとき $h_{I,j}=0$($j>d$)、$h_{I,0}=1$($I=\emptyset$ のとき)、$h_{I,0}=0$($I\neq\emptyset$ のとき)であり、すべての正の整数 $t$ について
$$ L_{\Delta_I}(t)=\sum_{j=0}^{d}h_{I,j}\binom{t+d-j}{d} $$
が成り立つ。右辺の多項式の $t=0$ での値は $h_{I,0}$ である。

$\Delta$ は $d$ 次元なので $w_0,\dots,w_d$ は $\mathbb{R}^{d+1}$ の基底であり、点 $y\in\mathbb{R}^d$ と実数 $t>0$ について、$(y,t)=\sum_ic_iw_i$ と一意に書け、$y\in t\Delta$ は $c_i\ge0$(すべての $i$)と同値で、このとき $c_i=t\lambda_i(y/t)$、$\sum_ic_i=t$ である。したがって $y\in t\Delta_I$ は、$c_i\ge0$(すべての $i$)かつ $c_i>0$($i\in I$)と同値である。
正の整数 $t$ と $y\in t\Delta_I\cap\mathbb{Z}^d$ をとる。$i\notin I$ では $k_i:=\lfloor c_i\rfloor$、$\mu_i:=c_i-k_i\in[0,1)$、$i\in I$ では $k_i:=\lceil c_i\rceil-1$、$\mu_i:=c_i-k_i\in(0,1]$ とおく。$c_i>0$($i\in I$)なので $k_i\ge0$ である。$w_i$ は格子点なので $p:=(y,t)-\sum_ik_iw_i=\sum_i\mu_iw_i$ は $\Pi_I\cap\mathbb{Z}^{d+1}$ の点で、$\operatorname{ht}(p)=t-\sum_ik_i$ である。逆に $p\in\Pi_I\cap\mathbb{Z}^{d+1}$ と $\sum_ik_i=t-\operatorname{ht}(p)$ をみたす $k\in\mathbb{Z}_{\ge0}^{d+1}$ から、$(y,t):=p+\sum_ik_iw_i$ は $y\in t\Delta_I\cap\mathbb{Z}^d$ を与える(係数 $c_i=\mu_i+k_i$ が上の条件をみたす)。$c_i$ から $(k_i,\mu_i)$ は一意に決まるので、この 2 つの対応は互いに逆である。よって
$$ L_{\Delta_I}(t)=\sum_{p\in\Pi_I\cap\mathbb{Z}^{d+1}}\#\Bigl\{k\in\mathbb{Z}_{\ge0}^{d+1}\Bigm|\sum_ik_i=t-\operatorname{ht}(p)\Bigr\} $$
である。$\Pi_I$ は有界なので和は有限和である。
高さを調べる。$p=\sum_i\mu_iw_i$ の高さは $\sum_i\mu_i$ で、$I\neq\{0,\dots,d\}$ なので $\mu_i<1$ となる $i$ があり、$0\le\operatorname{ht}(p)< d+1$ である。高さは整数なので $0\le\operatorname{ht}(p)\le d$ である。高さ $0$ の点はすべての $\mu_i$ が $0$ の点、すなわち原点だけで、原点が $\Pi_I$ に属するのは $I=\emptyset$ のときに限る。
最後に、高さ $j$($0\le j\le d$)の点 $p$ について、内側の個数は $t\ge j$ なら $\binom{t-j+d}{d}$、$t< j$ なら $0$ である。$0\le t< j\le d$ では $t-j\in\{-d,\dots,-1\}$ なので、多項式 $\binom{t-j+d}{d}$ の値も $0$ である。したがって主張の式がすべての正の整数 $t$(と $t=0$)で成り立ち、$t=0$ での値は高さ $0$ の点の個数 $h_{I,0}$ である。$\square$

三角形分割を半開の単体に分ける

全次元の格子多面体 $P$ は、頂点が $P$ の頂点である $d$ 次元単体 $\Delta^{(1)},\dots,\Delta^{(m)}$ に三角形分割できる。すなわち、$P=\bigcup_k\Delta^{(k)}$ で、どの 2 つの単体も共通の面(空集合でもよい)で交わる(BR15 Theorem 3.1。この記事では証明しない)。各 $\Delta^{(k)}$ は格子単体である。$\Delta^{(k)}$ の面のうち次元が $d-1$ のもの(ファセット)を含む超平面を、すべての $k$ にわたって $A_1,\dots,A_N$ とする。
$P$ の内部は空でない開集合なので、$A_1\cup\cdots\cup A_N$ に属さない内部の点 $q$ がとれる。$\Delta^{(k)}$ の重心座標を $\lambda^{(k)}_i$ と書き、
$$ I_k:=\{i\mid\lambda^{(k)}_i(q)<0\} $$
とおく($q$ から見て $\Delta^{(k)}$ の向こう側にあるファセットの番号の集合)。

半開の単体への分割
  1. 各 $k$ について $I_k\neq\{0,\dots,d\}$ である。
  2. $P$ は半開の単体 $\Delta^{(1)}_{I_1},\dots,\Delta^{(m)}_{I_m}$ の非交和である。
  3. $I_k=\emptyset$ となる $k$ はちょうど 1 つである。

まず、どの $A_l$ にも属さない $P$ の点 $z$ は、ちょうど 1 つの $\Delta^{(k)}$ の内部に属する。実際、$z$ はある $\Delta^{(k)}$ に属し、$\Delta^{(k)}$ の境界はファセットの和なので $z$ はその内部にある。$z$ が $\Delta^{(k)}$ と $\Delta^{(l)}$ の内部に属すれば、共通の面 $\Delta^{(k)}\cap\Delta^{(l)}$ が $\Delta^{(k)}$ の内部の点を含むので、この面は $\Delta^{(k)}$ 自身であり、同様に $\Delta^{(l)}$ 自身でもあるから $k=l$ である。
1.$\sum_i\lambda^{(k)}_i(q)=1$ なので、すべての $\lambda^{(k)}_i(q)$ が負になることはない。
3.$q$ はどの $A_l$ にも属さないので $\lambda^{(k)}_i(q)\neq0$ である。よって $I_k=\emptyset$ はすべての $\lambda^{(k)}_i(q)$ が正であること、すなわち $q$ が $\Delta^{(k)}$ の内部にあることと同値で、そのような $k$ は上の注意からちょうど 1 つである。
2.$x\in P$ と $0< \varepsilon\le1$ について $x_\varepsilon:=x+\varepsilon(q-x)$ とおくと、$P$ は凸なので $x_\varepsilon\in P$ である。$x=q$ なら $x_\varepsilon=q$ はどの $A_l$ にも属さないので、以下 $x\neq q$ とする。$\varepsilon\mapsto x_\varepsilon$ は直線のパラメータ表示で、$x_\varepsilon$ が $A_l$ に属する $\varepsilon$ は、直線が $A_l$ に含まれないかぎり高々 1 つである。直線が $A_l$ に含まれれば $q=x_1\in A_l$ となり $q$ のとり方に反する。よって $\varepsilon_0>0$ があって、$0< \varepsilon< \varepsilon_0$ の $x_\varepsilon$ はどの $A_l$ にも属さず、ちょうど 1 つの $\Delta^{(k)}$ の内部にある。内部どうしは交わらない開集合で、区間 $(0,\varepsilon_0)$ は連結なので、この $k$ は $\varepsilon$ によらない。これを $k(x)$ と書く。
一方、各 $k$ と $x\in\mathbb{R}^d$ について $\lambda^{(k)}_i(x_\varepsilon)=(1-\varepsilon)\lambda^{(k)}_i(x)+\varepsilon\lambda^{(k)}_i(q)$ である。したがって「十分小さいすべての $\varepsilon>0$ で $x_\varepsilon$ が $\Delta^{(k)}$ の内部にある」ことは、「各 $i$ について $\lambda^{(k)}_i(x)>0$、または $\lambda^{(k)}_i(x)=0$ かつ $\lambda^{(k)}_i(q)>0$」と同値であり、これは $x\in\Delta^{(k)}$ かつ「$i\in I_k$ なら $\lambda^{(k)}_i(x)>0$」、すなわち $x\in\Delta^{(k)}_{I_k}$ と同値である($\lambda^{(k)}_i(q)\ne0$ を使った)。よって $x\in\Delta^{(k)}_{I_k}$ と $k=k(x)$ は同値で、$P$ の各点はちょうど 1 つの $\Delta^{(k)}_{I_k}$ に属する。$\square$

定理の証明

半開の単体の個数を足す

lem-ehr-decomposition の 2 から、正の整数 $t$ について $tP$ は $t\Delta^{(k)}_{I_k}$ の非交和で、
$$ L_P(t)=\sum_{k=1}^mL_{\Delta^{(k)}_{I_k}}(t)=\sum_{j=0}^d h_j^*\binom{t+d-j}{d},\qquad h_j^*:=\sum_{k=1}^mh_{I_k,j} $$
である(2 つめの等号は lem-ehr-half-open。lem-ehr-decomposition の 1 によりこの補題を使える)。$h_j^*$ は非負整数である。
2:lem-ehr-half-open により $h_{I_k,0}$ は $I_k=\emptyset$ のとき $1$、そうでないとき $0$ なので、lem-ehr-decomposition の 3 から $h_0^*=1$ である。$\binom{d-j}{d}$ は $j=0$ で $1$、$1\le j\le d$ で $0$ なので $E_P(0)=h_0^*=1$ である。
1:$\binom{x+d-j}{d}$ は $x^d$ の係数が $\frac{1}{d!}$ の $d$ 次多項式なので、$E_P$ の $x^d$ の係数は $c_d:=\frac{1}{d!}\sum_jh_j^*$ で、$E_P$ の次数は $d$ 以下である。凸多面体は Jordan 可測なので、格子点 の定理「格子点の個数と体積」により $L_P(t)/t^d\to\operatorname{vol}(P)$($t\to\infty$)であり、左辺は $c_d$ に収束するので $c_d=\operatorname{vol}(P)$ である。$P$ は全次元なので $\operatorname{vol}(P)>0$ で、$E_P$ はちょうど $d$ 次である。
3:前半は 1 の計算そのものである。$d!\binom{x+d-j}{d}=\prod_{i=1}^d(x-j+i)$ は整数係数なので後半も従う。$\square$

$h^*$ ベクトルの成分が非負であることは Stanley の非負性定理 と呼ばれる(BR15 Theorem 3.12)。上の証明では、$h_j^*$ が半開の基本平行体の高さ $j$ の格子点の個数の和として表されることから従った。

全次元でない場合

$\dim P=k< d$ の格子多面体でも $L_P$ は $k$ 次多項式に一致する。頂点 $v$ を 1 つとり、$U$ を $P-v$ が張る $k$ 次元部分空間、$\Lambda:=U\cap\mathbb{Z}^d$ とする($U$ は格子点の差 $v'-v$ で張られるので、$\Lambda$ は $U$ を張る)。$\mathbb{Z}^d/\Lambda$ は有限生成で、$nz\in\Lambda$($n\ne0$)なら $z\in U$ なので捩れがなく、有限生成アーベル群の構造定理 により自由である。よって $\mathbb{Z}^d=\Lambda\oplus\Lambda'$ と分解でき、$\Lambda$ は階数 $k$ の自由加群で、$\Lambda$ の基底と $\Lambda'$ の基底を並べると $\mathbb{Z}^d$ の基底になる。この基底を標準基底に送る $A\in GL_d(\mathbb{Z})$ をとると、$tv\in\mathbb{Z}^d$ なので $y\mapsto A(y-tv)$ は $tP\cap\mathbb{Z}^d$ から $tA(P-v)\cap\mathbb{Z}^d$ への全単射であり、$A(P-v)$ は $\mathbb{R}^k\times\{0\}$ の中の全次元の格子多面体である。こうして thm-ehr-main に帰着する。最高次の係数は $A(P-v)$ の $k$ 次元体積になる。これは格子 $\Lambda$ を基準にした $P$ の体積(相対体積)で、$U$ の中の Euclid 体積とは一般に異なる。たとえば $(0,0)$ と $(1,1)$ を結ぶ線分では $L_P(t)=t+1$ で、最高次の係数は長さ $\sqrt2$ ではなく $1$ である。

相反定理

Ehrhart 多項式に負の整数を代入すると、内部の格子点の個数が現れる。

Ehrhart–Macdonaldの相反定理

$P\subset\mathbb{R}^d$ を全次元の格子多面体とすると、すべての正の整数 $t$ について
$$ L_{P^\circ}(t)=(-1)^dE_P(-t) $$
が成り立つ。

証明の所在

一般の格子多面体(さらに有理多面体)についての証明は BR15 Theorem 4.1 にある。この記事では一般の場合は証明せず、次の命題で単体の場合を証明する。

単体の場合の相反定理

$\Delta$ を $d$ 次元の格子単体とし、$h_j:=h_{\emptyset,j}$(lem-ehr-half-open)とする。すべての正の整数 $t$ について
$$ L_{\Delta^\circ}(t)=\sum_{j=0}^dh_j\binom{t+j-1}{d}=(-1)^dE_\Delta(-t) $$
である。

要点:内部 $\Delta^\circ$ は全部の対面を除いた半開の単体で、その基本平行体の格子点は $p\mapsto\sum_iw_i-p$ で $\Pi_\emptyset$ の格子点と 1 対 1 に対応し、高さ $j$ が $d+1-j$ に替わる。

証明を開く

$\Delta^\circ$ は $I=\{0,\dots,d\}$ の半開の単体 $\Delta_I$ である。prf-ehr-half-open の前半は $I$ によらず成り立ち、$L_{\Delta^\circ}(t)$ は $p\in\Pi_I\cap\mathbb{Z}^{d+1}$ にわたる $\#\{k\in\mathbb{Z}_{\ge0}^{d+1}\mid\sum_ik_i=t-\operatorname{ht}(p)\}$ の和である。$w:=\sum_iw_i$ とおくと、$p\mapsto w-p$ は $\Pi_\emptyset\cap\mathbb{Z}^{d+1}$ から $\Pi_I\cap\mathbb{Z}^{d+1}$ への全単射で(係数 $\mu_i$ を $1-\mu_i$ に替える)、高さ $j$ を $d+1-j$ に送る。よって $\Pi_I$ の格子点の高さは $1$ 以上 $d+1$ 以下で、高さ $d+1-j$ の点が $h_j$ 個ある。

高さ $j'=d+1-j$ の点の寄与は、$t\ge j'$ なら $\binom{t-j'+d}{d}=\binom{t+j-1}{d}$ である。$1\le t< j'$ では $t+j-1\in\{j,\dots,d-1\}$ で、多項式 $\binom{t+j-1}{d}=\frac{(t+j-d)\cdots(t+j-1)}{d!}$ の因子のどれかが $0$ になるので値は $0$ であり、実際の寄与 $0$ と一致する。これで 1 つめの等号を得る。2 つめは、各 $j$ について

$$(-1)^d\binom{-t+d-j}{d}=(-1)^d\frac{(-t-j+1)\cdots(-t-j+d)}{d!}=\frac{(t+j-1)\cdots(t+j-d)}{d!}=\binom{t+j-1}{d}$$

であることを $j$ について足せばよい。$\square$

平面の場合と Pick の定理

$P$ を平面の凸な格子多角形とし、面積を $A$、境界の格子点の個数を $B$、内部の格子点の個数を $I$ とすると、$E_P(x)=Ax^2+\frac{B}{2}x+1$ であり、$A=I+\frac B2-1$ が成り立つ。

thm-ehr-main により $E_P(x)=Ax^2+cx+1$ と書ける。$t=1$ と thm-ehr-reciprocity($t=1$)から $I+B=L_P(1)=A+c+1$、$I=L_{P^\circ}(1)=E_P(-1)=A-c+1$ である。差をとると $c=\frac B2$、これを戻すと $A=I+\frac B2-1$ である。$\square$

この系は凸な格子多角形についての Pickの定理 である。ここでは一般の相反定理を引用して導いたので、Pick の定理の独立な証明にはなっていない(Pickの定理 では、凸でない多角形も含めて初等的に証明している)。

例

立方体と標準単体
  1. 単位立方体 $C=[0,1]^d$ では $tC\cap\mathbb{Z}^d=\{0,1,\dots,t\}^d$ なので $E_C(x)=(x+1)^d$ である。内部は $\{1,\dots,t-1\}^d$ で $L_{C^\circ}(t)=(t-1)^d=(-1)^dE_C(-t)$ となり、相反定理と合う。$x^d$ の係数 $1$ は体積である。
  2. 標準単体 $\Delta=\operatorname{conv}\{0,e_1,\dots,e_d\}$ では、$t\Delta\cap\mathbb{Z}^d$ は $y_i\ge0$、$\sum_iy_i\le t$ をみたす整数点で、$y_0:=t-\sum_iy_i$ を加えると $\binom{t+d}{d}$ 個ある。よって $E_\Delta(x)=\binom{x+d}{d}$、$h^*=(1,0,\dots,0)$ で、体積は $\frac1{d!}$ である。
Reeve の四面体

正の整数 $r$ について、$T_r:=\operatorname{conv}\{(0,0,0),(1,0,0),(0,1,0),(1,1,r)\}$ とおく(BR15 Example 3.22)。このとき
$$ E_{T_r}(x)=\frac r6x^3+x^2+\Bigl(2-\frac r6\Bigr)x+1,\qquad h^*=(1,0,r-1,0) $$
である。$T_r$ の格子点は 4 つの頂点だけで、内部にも辺・面の内部にも格子点はない。それにもかかわらず体積 $\frac r6$ は $r$ とともにいくらでも大きくなる。したがって 3 次元では、境界と内部の格子点の個数から体積を求める Pick の定理の類似の公式は成り立たない。また $r\ge13$ では $x$ の係数が負になり、Ehrhart 多項式の係数は正とは限らない($h^*$ ベクトルの成分は非負である)。

要点:$T_r$ の格子点が頂点だけであることを確かめ、$L_{T_r}(1)=4$、prop-ehr-reciprocity-simplex による $L_{T_r^\circ}(1)=0$、$\sum_jh_j=3!\operatorname{vol}(T_r)=r$ から $h^*$ ベクトルを決める。

証明を開く

体積は $\frac16\lvert\det((1,0,0),(0,1,0),(1,1,r))\rvert=\frac r6$ である。$T_r$ の点を $a(0,0,0)+b(1,0,0)+c(0,1,0)+e(1,1,r)$($a,b,c,e\ge0$、和が $1$)と書くと、$x$ 座標は $b+e$、$y$ 座標は $c+e$ で、どちらも $0$ 以上 $1$ 以下である。格子点ならこれらは $0$ か $1$ で、$(x,y)=(0,0)$ なら $b=c=e=0$、$(1,0)$ なら $c=e=0$、$b=1$、$(0,1)$ なら $b=e=0$、$c=1$、$(1,1)$ なら $b=c=1-e$ と $a=e-1\ge0$ から $e=1$ となり、いずれも頂点である。よって $L_{T_r}(1)=4$、$L_{T_r^\circ}(1)=0$ である。

$E_{T_r}(x)=\sum_jh_j\binom{x+3-j}{3}$(thm-ehr-main)で $h_0=1$ である。$x=1$ を代入すると $\binom{4}{3}+h_1\binom33=4+h_1=4$ から $h_1=0$ である。prop-ehr-reciprocity-simplex を $t=1$ で使うと $0=L_{T_r^\circ}(1)=\sum_jh_j\binom{j}{3}=h_3$ である。$\sum_jh_j=3!\cdot\frac r6=r$ から $h_2=r-1$ となる。したがって

$$E_{T_r}(x)=\binom{x+3}{3}+(r-1)\binom{x+1}{3}=\frac{x^3+6x^2+11x+6+(r-1)(x^3-x)}{6}$$

で、整理すると主張の式になる。$\square$

反例:仮定を外すと成り立たないこと

thm-ehr-main の仮定のうち 1 つを外すと、数え上げ関数は多項式にならない。

外す条件反例成り立たなくなること
頂点が格子点(有理点にゆるめる)$P=[0,\frac12]\subset\mathbb{R}$$L_P(t)=\lfloor t/2\rfloor+1$ は多項式でない
頂点が格子点(無理数の座標を許す)$P=[0,\sqrt2]\subset\mathbb{R}$$L_P(t)=\lfloor t\sqrt2\rfloor+1$ は多項式でない
拡大率 $t$ が整数$P=[0,1]$、実数 $t>0$$\#(tP\cap\mathbb{Z})=\lfloor t\rfloor+1$ は実数 $t$ の多項式でない
反例の確認

各行を確かめる。

各行の確認を開く

1 行目:多項式 $f$ が正の整数 $t$ で $\lfloor t/2\rfloor+1$ に等しいとすると、偶数 $t=2s$ で $f(2s)=s+1$ なので、無限個の点で一致する $f(x)=\frac x2+1$ である。しかし奇数 $t$ では $f(t)=\frac t2+1$ は整数でなく、$\lfloor t/2\rfloor+1$ と異なる。有理多面体では、数え上げ関数は周期的な係数をもつ多項式(擬多項式)になる(BR15 Theorem 3.23)。この例では $t$ の偶奇で式が変わる。

2 行目:多項式 $f$ が正の整数で $\lfloor t\sqrt2\rfloor+1$ に等しいとすると、$f(t)/t\to\sqrt2$ かつ $f(t)/t^2\to0$ なので $f(x)=\sqrt2x+b$ の形である。すると $t\sqrt2-\lfloor t\sqrt2\rfloor=1-b$ が $t$ によらず一定で、$t=1,2$ の差をとると $\sqrt2=\lfloor2\sqrt2\rfloor-\lfloor\sqrt2\rfloor=1$ となり矛盾する。

3 行目:$\lfloor t\rfloor+1$ は $t=1$ で不連続なので、どの多項式とも区間 $(0,2)$ 上で一致しない。整数 $t$ に制限すれば $t+1$ で、多項式である。

補足

  • 体積の計算.thm-ehr-main の 1 から、$E_P$ を $d+1$ 個の値 $L_P(1),\dots,L_P(d)$ と $E_P(0)=1$ から補間すれば、格子点を数えるだけで $\operatorname{vol}(P)$ が求まる(BR15 Corollary 3.20 と §3.7)。
  • $h^*$ ベクトル.単体では $h_j^*$ は基本平行体 $\Pi_\emptyset$ の高さ $j$ の格子点の個数で、$\sum_jh_j^*=d!\operatorname{vol}(\Delta)=\lvert\det(w_0,\dots,w_d)\rvert$ である(BR15 Corollary 3.11・3.21)。
  • 数え上げの多項式.超平面配置 の特性多項式も、$-1$ での値が別のもの(実超平面配置の領域の個数)を数える(超平面配置 の Zaslavsky の定理)。グラフの 彩色多項式 では、$-1$ での値の絶対値が非巡回的な向きの個数になる。

関連項目

参考文献

[1]
Matthias Beck, Sinai Robins, Computing the Continuous Discretely: Integer-Point Enumeration in Polyhedra, 2nd ed., Undergraduate Texts in Mathematics, Springer, 2015, Chapter 3(Theorem 3.1 三角形分割の存在、Theorem 3.8 Ehrhart の定理、Corollary 3.11、Theorem 3.12 Stanley の非負性、Corollary 3.20・3.21、§3.7、Example 3.22 Reeve の四面体、Theorem 3.23 有理多面体)、Chapter 4(Theorem 4.1 Ehrhart–Macdonald の相反定理)

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する