2010-08-08

駆け足で読む『離散体積計算による組合せ数学入門』第２章　離散体積の展覧会

駆け足で読むシリーズアプリケーション

凸多面体
- 頂点記述(頂点座標を与える記述)
  - 頂点 $\mathbf{v}=\{v_1,v_2,...,v_k}$ を与えれば、 $\sum_{i=1}^k \lambda_i v_i$ , $\lambda_i \ge 0$ , $\sum_{i=1}^k \lambda_i=1$ として与えられる凸多面体
- 超平面記述(囲んでいる超平面を与える記述)
  - $(x_1,x_2,...,x_k)\in \mathbf{R}^d$ , $x_i \ge 0$ , $\sum_{i=1}^k x_i a_i =1$ として与えるのは、超平面記述の1つ
  - 超平面は $x \in \mathbf{R}^d: \text{innter product} (a,x)=b$ として与えられる。 $b=0$ の場合は $a$ を法線ベクトルとする( $a$ に垂直な)面になる
- d-多面体の頂点数はd+1以上であり、ちょうどd+1のときに、d-単体(simplex)と呼ぶ
- 頂点座標がすべて整数のとき整数多面体(integral polytope)と呼び、すべての有理数であるとき有理多面体(rational polytope)と呼ぶ
立方体
- 辺の長さが１の立方体が単位立方体、そのt-dilateの格子点数(格子点列挙) $L_{d-cube}(t):=#(tP \bigcap \mathbf{Z}^d)$
- $L_{d-cube}(t)=(t+1)^d=\sum_{k=0}^d \text{Combination}(d,k) t^k$
- d-cubeの内部の点の数は $(-1)^d L_{d-cube}(-t)$
- 次元d(0,1,2,...)について、を係数に持つような級数(Ehrhart級数)を多項式の係数として持つ関数の母関数があって、それは、d-cubeの場合には、Eulerian number (AT&Tの数列大事典ならこちら) ()を使って次の様に表される(もともと、Eulerial numberがこのようにして定められたという感じでもある？)
  - $\frac{\sum_{k=1}^d A(d,k)z^{k-1}}{(1-z)^{d+1}}$
標準単体の場合には
- - ただし、 $\text{stirl}(a,b)$ は第一スターリング数
- 標準単体の内部の格子点数は $\text{combination}(t-1,d)$
- ここでも標準単体の内部の点の数は内部の点の数は $(-1)^d L_{standard simplex}(-t)$ になる
- Ehrhart級数の母関数は $\frac{1}{(1-z)^{d+1}}$
ピラミッド(底面が(d-1)-cubeでそこからの点へ辺を伸ばしたもの
- Bernoulli多項式
  - $B_k(x)$ は母関数 $\frac{ze^{xz}}{e^z-1}=\sum_{k\ge 0} \frac{B_k(x)}{k!}z^k$ によって定義される
  - $B_k=B_k(0)$ と特別な場合
- $L_{pyramid}(t)\frac{1}{d}(B_d(t+2)-B_d)$
- ここでも内部の点の数は $(-1)^d L_{pyramid}(t)$
- Ehrhart級数は $\frac{\sum_{k=1}^{d-1} A(d-1,k)z^{k-1}}{(1-z)^{d+1}}$ となる
十字多面体
- 双ピラミッド(ピラミッドを張り合わせたもの)
- これも同様のルールがあてはまって
- $L_{dual pyramid}(t)=\sum_{k=0}^d \text{combination}(d,k)\text{combination}(t-k+d,d)$
- 内部の点は $(-1)^d L_{dual pyramid}(t)$
- Ehrhart級数は $\frac{(1+z)^d}{(1-z)^{d+1}}$
整数凸多角形の場合〜Pickの定理
- 整数凸多角形に対して面積 $A=I+\frac{1}{2}B-1$ 、ただし、 $I$ は内部格子点数、 $B$ は境界上格子点数
有理凸多角形の場合
- Fourier-Dedekind和が登場する
- 準多項式(quasipolynomial)という考えが登場する
- 準多項式の主項が面積、もうひとつの項がそこからの補正の量を表している
一般化有理多面体
- 有理多面体ならば、多面体を表す式の係数を整数にできるから、有理多面体とする
- いくつかの工夫があることで格子点数を表すEhrhart級数が導けるという
  - 凸多面体を囲む超平面とその不等式で表しているときに、変数を新たに加えることで、連立方程式に変換することができる。それを行う
  - 複数の変数に関する級数表現にする
polymakeというアプリケーションが使えるという