2021-05-19

ぱらぱらめくる『トーリックイデアルの20年』

ぱらぱらめくるシリーズトーリックイデアル代数統計イデアル環多項式環グレブナー基底割り算倍数素数

http://www.math.sci.hokudai.ac.jp/sympo/100809/pdf/osugi.pdf

トーリックイデアルが興味深い対象として挙げられる理由３つ
- 凸多面体の三角形分割が、トーリックイデアルのイニシャルイデアルと対応する(三角形分割には団代数が付随し、そこにはローラン多項式な団変数があるが、トーリックイデアルの構成にもローラン多項式が登場する。コーラン多項式は「多項式環」の仲間ということで、「環」の「部分集合」で「代数的性質をもつもの」。この話にはルート系なども出てくるが、そもそも団代数はルート系の本体のような意味もあり、そういう意味でもつながっている
- トーリックイデアルにはグレブナー基底が取れて、これにより、整数計画問題の解法がもたらされた
- 同じくグレブナー基底をマルコフ基底(空間をうろうろするための一歩の集合)として分割表の取りうる空間をうろうろすることができて、それによって分割表検定のための情報が得られる
１　トーリックイデアル
- そもそも、イデアルって…
- 「数」の抽象的な概念なので、なじみの深い「数」における「イデアル」の位置づけを確認する
- 整数全体の集合として「部分集合に z=3の倍数の集合」というようなものが取れる。この部分集合はそれなりに演算に関して閉じている(３の倍数を足し合わせても、相変わらず３の倍数である、とか)。そういういい感じの性質を持った部分集合を考えたい
- z=3の倍数の集合を考えた時、zとして素数を取るのも悪くない発想。なので、イデアルには、「いい感じの取り方・取られ方」があって、それは素数的な意味合いもあるらしい
- 整数全体の部分集合を考えた。そのとき、いい感じの性質・演算で閉じているというものを考えた。その代数的性質が「環」なので、「倍数のようなものの一般化したもの」を作り出すことは、「環」に対して行うのがよい。…とそういうことらしい
- 大きな環としてローラン多項式環 $X[T,T^{-1}] = K[t_1^{\pm 1},t_2^{\pm 1},...,t_d^{\pm 1}]$ を取る
- その部分多項式集合を構成する種として、特定の単項式の集合 $\{T^{a1},T^{a2},...T^{an}\}$ , ( $T^{ai} = \prod_{p=1}^d t_p^{ai_p}$ を取る。ただし、 $a_i = (ai_1,ai_2,...,ai_d) \in Z^d$ のように $ai$ はd次元空間の格子点
- この種となる単項式を自由に決めると、「いい感じの取り方」になっていないので、「制約」が必要
- その制約として、n個のd次元格子点 $\{a1,...an\}$ は原点を通らないd次元空間超平面上にあるというものを定める。 $w \cdot ai=1;i=1,2,...,n$ となる $w$ (d次元実ベクトル)が存在する、とも言い換えられる制約である
- このような制約のことを、 $\{ai\}\subset Z^d$ が $R^d$ の配置であると呼ぶ
- このような制約を持った種になる単項式が構成する多項式集合は semigroup ringになると言う。これをトーリック環 $K[A]$ と呼ぶ(Aは配置の要素 $ai$ の集合
- このトーリック環に伴うイデアル、「トーリックイデアル」を定義するにあたり、もう一つ別の多項式環を準備する
- Tを使った多項式環はd変数だったが、トーリック環の構成に用いられた、もう一つの自然数、n(格子点の数n)

を用いて、n変数多項式環 $K[X]$ 考える( $x_1,...,x_n$ )

- このn変数多項式環の要素をトーリック環の要素に対応付ける。 $\pi (x_i) = T^{a_1}$ なる関係にする
- n変数多項式環はn変数の多項式の全体であるのに対して、トーリック環の要素は制約を持つ単項式が種となった多項式の集合なので、対応を取るにも１対１対応は取れない。うまく取ると、 $K[X]$ から $K[A]$ への全射になる。全射なので、 $K[A]$ の原点に対応する $K[X]$ は集合になる(カーネル)。この全射のカーネルのことをAのトーリックイデアルと言う
- 具体例を考える
- ... d = 5, n=6
  - 配置であることを確認。w = (0.5,0.5,...,0.5)を取ると、 $w A = (1,1,1,1,1,1)$ となっている
  - また、 $d=5$ 次元座標を $(t1,...,t5)$ とすれば、Aの６個の列ベクトルはすべて $t1 + t2 + ... + t5 = 2$ を満足するという意味で、d次元超平面上の点である
- このAに対して、トーリック環 $K [ A ] = K [ t_1t_3,t_1t_4,t_1t_5,t_2t_3,t_2t_4,t_2t_5 ]$ が定まる(Aの第１列ベクトルでは、第１、第３成分がそれぞれ１なので $t_1^1t_3^1$ となっている)
- このトーリック環のトーリックイデアルがだと言う
  - $x_1x_5-x_2x_4$ を例に取る。 $\pi(x_1) = T^{a1} = t_1t_3, \pi(x_5) = t_2t_4,\pi(x_2) = t_1t_4,\pi(x_4) = t_2t_3$ であるから、多項式環 $K[X]$ の要素 $x_1x_5 - x_2x_4$ に対応するトーリック環の要素は $t_1t_3 \times t_2t_4 - t_1t_4 \times t_2t_3 = 0$ となっており、確かに、 $x_1x_5- x_2x_4$ は全射 $\pi$ のカーネルに含まれている
  - トーリクイデアルの性質として、次のことも知られる
    - トーリックイデアルは素イデアルである。また、２項式で生成される。その生成ルールは $I_A = < p -q \in K[X] | \pi(p) - \pi(q) >$ ただし、 $p,q$ は単項式。これは $\pi(p) = \pi(x_1x_5) = t_1t_3t_2t_4$ であることに対応している
    - Aを行列とみなすと
      - $I_A = < X^u - X^v \in K[X] | u,v \in Z^n_{\ge 0}, Au = Av>$
      - $I_A = < X^{u^+} -X^{u^-} \in K[X] | u \in Z^n, Au = 0>$ ただし $u^+$ はuの正の部分、 $u^-$ はuの負の部分
      - これを実例でやってみる。 $u= (1,0,0,0,1,0),v = (0,1,0,1,0,0)$ とすると、 $A u = A v = (1,1,1,1,0)$ であり、これに対応する $X^u-X^v = x_1x_5 - x_2x_4$ である。また、 $u=(1,-1,0,-1,1,0)$ とすると、 $Au=(0,0,0,0,0)$ であり、 $X^{u^+} - X^{u^-} = X^{(1,0,0,0,1,0)} - X^{(0,1,0,1,0,0)} = x_1x_5- x_2x_4$ となる。このベクトルの成分の符号で分配する計算は団代数の変数変異ルールと通じるものになっている。ちなみに、トーリックイデアルは、 $x_i$ とその像 $T^{ai}$ とを考えた時に、像が $T^{ai}$ になる $K[X]$ の要素と $x_i$ との差で表される多項式の集合でもあるらしい
２　トーリックイデアルのグレブナー基底
- トーリックイデアルは多変数多項式。今、変数に順序を定めることで、単項式にも順序を定めることができる。それを「変数の順序の下での、単項式順序」と言う
- 単項式順序が定まると、多項式の各項にも順序ができる
- イデアルの多項式のそれぞれにも、「一番」の単項式を選ぶことができる。この「一番」単項式(イニシャルな単項式)を集めたものを、イデアルのイニシャルイデアルと言う
- イデアルの部分集合をとったときに、それぞれの要素のイニシャルな単項式を集めたものが、イデアルのイニシャルイデアルになっているとき、そのイデアルの部分集合をグレブナー基底と言う。そしてグレブナー基底はイデアルを生成するのだと言う(ちゃんとイデアルの要素を全部取れば、そのどれかには、このイデアルを構成するための、単項がイニシャル単項式として使われていないとイデアルとしての振る舞いができない、ということの裏返し(だろう))
３　凸多面体の三角形分割
- 配置Aが張る凸包を考え、その三角形分割(単体的複体とみなす)を取る。そういう意味での「三角形」への分割が、配置Aに変数順序を定めて取り出したトーリックイデアルのイニシャルイデアルと対応づくごとが証明されているという
- リンク先文書では細かいことが書いていないのだが…
４　整数計画問題への応用
- 整数最適化問題の条件を整数長方形行列として表現する
- 必ずしもこの長方形行列は「配置」でなくてもよい
- この長方形行列のトーリックイデアルは定義できる
- したがってグレブナー基底も定まる
- 多項式(変数の整数乗で表されたものになっている)なので、その割り算や余りを扱うことで、求めたい最適解が多項式の割り算・余りとして取り出せる
５　分割表の検定への応用
- 周辺度数を固定して分割表のセルの値(整数値)を色々と変えることは、モンテカルロな検定方法の１つ
- 分割表のあるセルの値を増やすことと別のセルの値を減らすことは、周辺度数制約のために相互依存している
- したがって、分割表のどのセルを増やしどのセルを減らすかのパターンが決まって来る
- このパターンがマルコフ基底によって張られる
- マルコフ基底はトーリックイデアルと関係しているという話
- トーリックイデアルを表す２項の差の形をした多項式の情報を使って、マルコフ基底(分割表と同じ形をした、整数値アレイ)が決まる