Sandbox

From Metabolomics.JP
(Difference between revisions)
Jump to: navigation, search
m
m
 
(24 intermediate revisions by 2 users not shown)
Line 1: Line 1:
−
{| class ="wikitable"
+
==根基イデアルとイデアル多様体対応==
−
{{#replace:
+
イデアルとアフィン多様体の対応は1対1ではない。
−
{{#lua:
+
例えば <x> と <x<sup>2</sup>> は k[x] の異なるイデアルだが、多様体は同じである '''V'''(x) = '''V'''(x<sup>2</sup>) = { 0 } 。
−
  function atomicNum(atom, str)
+
体 k が代数的閉体でない場合、複素数解が生じる多項式は対応する多様体が空集合になってしまう。しかし代数的閉体である場合は k[x] の多項式は必ず根を持ち、空集合に対応するイデアルが複数にならず、'''V'''(I) = { } となるには多項式環全体つまり I = k[x] となる。これを示したのがヒルベルトの零点定理であった。
−
    if (str == "") then return 0; end
+
−
    if (str == atom) then return 1; end
+
−
    return tonumber(string.sub(str,2));
+
−
  end
+
  
−
  function mass(str)
+
§2では零点定理をイデアルの言葉で書きなおしてみる。
−
    local c,h,n,o=string.match(str,"(C?[1-9]?[0-9]?)(H?[1-9]?[0-9]?)(N?[1-9]?[0-9]?)(O?[1-9]?[0-9]?)");
+
−
    c = atomicNum("C", c) * 12;
+
−
    h = atomicNum("H", h);
+
−
    n = atomicNum("N", n) * 14;
+
−
    o = atomicNum("O", o) * 16;
+
−
    return c + h + n + o;
+
−
  end
+
  
−
  function diff(str1, str2)
+
零点定理によるとイデアル I が '''V'''(I) で消える多項式全体のなすイデアルとならない唯一の理由は、 I に含まれない多項式 f のベキ f<sup>m</sup> が I に含まれるからであった。そこで根基イデアルという概念を導入する。
−
    ---computes str1 - str2. If negative, returns nil.---
+
−
    local c1,h1,n1,o1=string.match(str1,"(C?[1-9]?[0-9]?)(H?[1-9]?[0-9]?)(N?[1-9]?[0-9]?)(O?[1-9]?[0-9]?)");
+
−
    local c2,h2,n2,o2=string.match(str2,"(C?[1-9]?[0-9]?)(H?[1-9]?[0-9]?)(N?[1-9]?[0-9]?)(O?[1-9]?[0-9]?)");
+
−
    c1 = atomicNum("C", c1);
+
−
    h1 = atomicNum("H", h1);
+
−
    n1 = atomicNum("N", n1);
+
−
    o1 = atomicNum("O", o1);
+
−
    c2 = atomicNum("C", c2);
+
−
    h2 = atomicNum("H", h2);
+
−
    n2 = atomicNum("N", n2);
+
−
    o2 = atomicNum("O", o2);
+
−
    if (c2 > c1) then return nil; else c1 = c1 - c2; end
+
−
    if (h2 > h1) then return nil; else h1 = h1 - h2; end
+
−
    if (n2 > n1) then return nil; else n1 = n1 - n2; end
+
−
    if (o2 > o1) then return nil; else o1 = o1 - o2; end
+
−
    local ret = "";
+
−
    if (c1 > 1) then ret = ret .. "C" .. c1;
+
−
      else if (c1 == 1) then ret = ret .. "C"; end end
+
−
    if (h1 > 1) then ret = ret .. "H" .. h1;
+
−
      else if (h1 == 1) then ret = ret .. "H"; end end
+
−
    if (n1 > 1) then ret = ret .. "N" .. n1;
+
−
      else if (n1 == 1) then ret = ret .. "N"; end end
+
−
    if (o1 > 1) then ret = ret .. "O" .. o1;
+
−
      else if (o1 == 1) then ret = ret .. "O"; end end
+
−
    return ret;
+
−
  end
+
  
−
  local ruler;
+
;定義：ある整数 m に対しf<sup>m</sup>∈ I ならば f ∈ I を満たすとき、 I を根基 (radical) イデアルという。また、イデアル I に対してある整数 m があり f<sup>m</sup> ∈ I となる関数 f の集合を、イデアルの根基といって √I と記す。
−
  local fragments = {};
+
 
−
  local x, y;
+
定義における整数 m は 1 でもよいので、明らかに I ⊂ √I である。しかし I ≠ √I はありえる。例えばイデアル J = < x<sup>2</sup>, y<sup>3</sup> > ⊂ k[x,y] を考えよう。 x , y は J に属さないが x ∈ √J, y ∈ √J である。 (xy)<sup>2</sup> ∈ J から、xy ∈ √J 、さらに x + y ∈ √J である。しかし xy や x+y は J には属さないので、J ⊂ √J である。
−
  for line in stdin:gmatch("[%S ,]+") do
+
 
−
    if (string.find(line, "=") == nil) then ruler = line;
+
;補題： I が k[x ...] のイデアルなら、 √I もイデアルになる。
−
    else ---register fragments---
+
: f , g ∈ √I なら f<sup>m</sup>, g<sup>l</sup> ∈ I となる。そこで (f + g)<sup>m+l-1</sup>の2項展開を考えると 各項は f<sup>i</sup>g<sup>j</sup> を含んでいる(ただし i+j = m+l-1 ) 。このとき f<sup>i</sup> または g<sup>j</sup> のいずれかが I に含まれるので (f + g)<sup>m+l-1</sup> ∈ I になる。つまり (f + g) ∈ √I。 また同様に f ∈ √I なら hf ∈ √I となるので √I はイデアルである。さらに√Iは根基イデアルである。
−
      head, tail = string.match(line, "([CHNO0-9]+) *= *([CHNO0-9 ]+)");
+
 
−
      y = {};
+
 
−
      for x in string.gmatch(tail,"[CHNO0-9]+") do
+
;強形の零点定理 k を代数的閉体とする。 I を k[x, ...] のイデアルとすると、'''I'''('''V'''(I) ) = √Iとなる。
−
        y[x] = x;
+
:f ∈ √I とすると f<sup>m</sup> ∈I であり '''V'''(I) で消える。このとき f も消えるから f ∈ '''I'''('''V'''(I))。
−
      end
+
:逆に　 f ∈ '''I'''('''V'''(I)) のとき、f は '''V'''(I) で消えるから、零点定理よりある整数 m に対して f<sup>m</sup> ∈ I。すなわち f ∈ √I となる。
−
      fragments[head] = y;
+
 
−
    end
+
;定理（イデアル多様体対応）
−
  end
+
:(i) アフィン多様体　→　イデアル　と、イデアル　→ アフィン多様体　は包含関係が逆になる。つまりイデアルが I<sub>1</sub> ⊂ I<sub>2</sub> なら、'''V'''(I<sub>1</sub>) ⊃ '''V'''(I<sub>2</sub>) になる。また多様体が V<sub>1</sub> ⊂ V<sub>2</sub> なら、'''I'''(V<sub>1</sub>) ⊃ '''I'''(V<sub>2</sub>) になる。また任意の多様体に対し '''V'''('''I'''(V)) = V となって'''I'''は常に1対1である。
−
  local axis  = {};
+
:(ii) k が代数的閉体の場合、根基イデアルだけを考えると上記の写像は互いに逆写像となる全単射である。
−
  local i = 1;
+
 
−
  for formula in string.gmatch(ruler, "([%S]+)") do
+
以上から、多様体に関する問題は根基イデアルに関する代数の問題に言い換えられる。イデアルに対し、次の3つの問が考えられる。
−
    axis[i] = formula;
+
* 根基の生成元: √I = <g, ...> となるような多項式の集合を生成するアルゴリズム ... 実用的でないものはHermann(1926)により示され、Gianni et al (1988)らにより数式処理システムに組み込まれたものが示された
−
    i = i + 1;
+
* 根基イデアル: I が根基かどうかの判定アルゴリズム ... Gianni et al (1988)らにより数式処理システムに組み込まれたものが示された
−
  end
+
* 根基所属: 与えられた多項式 f が f ∈ √I かどうかの判定アルゴリズム ... ここで解説
−
  print("#-\n");
+
 
−
   print("## sample \n");
+
イデアル I = <f, ...> を与えられた時、多項式 f が f ∈ √I であるかをみるには、I' = <f, ..., 1-yf> に定数多項式 1 が含まれるかどうかを判定するだけで良い。なぜなら
−
  for i=1, table.getn(axis) do
+
<math>\begin{align}
−
    print("#style='text-align:right'# " .. mass(axis[i]) .. "<br/>" .. axis[i]);
+
1 = y^m f^m + (1 - y^m f^m ) = y^m f^m + (1 - yf)(1 + ...)
−
   end
+
\end{align}</math>
−
   for i=1, table.getn(axis) do
+
であるから、もし 1 ∈ I' なら f<sup>m</sup> ∈ I を意味している。 また f ∈ √I ならある m に対して f<sup>m</sup> ∈ I を満たすから、1 ∈ I' となるため、 f ∈ √I の判定の必要十分条件になっている。
−
    print("#-\n");
+
 
−
    print("#style='text-align:right'# " .. mass(axis[i]) .. "<br/>" .. axis[i]);
+
このことは、適当な順序で I' = <f, ..., 1-yf> の簡約グレブナ基底を計算し、その結果が { 1 } であれば f ∈ √I, そうでなければ含まれないという結論になる。
−
    for j=1, table.getn(axis) do
+
 
−
      if (j < i) then
+
;例
−
        s = diff(axis[j],axis[i]);
+
: k[x,y] のイデアル <math> I = \langle xy^2 + 2 y^2 , x^4 - 2x^2 + 1> \rangle </math> に <math> f = y - x^2 + 1 </math> が所属するか判定する
−
        if (s == nil)
+
: k[x,y,z] の lex 順序で
−
          then print('#style="background-color:gray"# ');
+
<math> I' = \langle xy^2 + 2y^2,  x^4 - 2x^2 + 1, 1 - z(y - x^2 + 1)\rangle \subset k[x,y,z]</math>
−
        else
+
は簡約グレブナ規定 { 1 } を持つ。よって <math> f = y - x^2 + 1 \isin \sqrt{I} </math> 。
−
          if (fragments[axis[j]] ~= nil and fragments[axis[j]][axis[i]] ~= nil) then
+
 
−
            print('#style="background-color:orange"# ' .. s);
+
 
−
          else print('## ' .. s); end
+
<!----------コメントアウト
−
        end
+
{{#graph:pie|size=300x200;margin=0,0,0,0;title="Family";legend=0x0;a=1;b=2;c=3}}
−
      else print('#style="background-color:white"# ');
+
 
−
      end
+
<table cellpadding="1" cellspacing="0">
−
    end
+
<tr>
−
    print("\n");
+
   <td valign="bottom">
−
  end
+
  <table cellpadding="0" cellspacing="0" style="background-color: #ff0000; width: 8px; height: 20px">
−
|
+
    <tr><td>&nbsp;</td></tr>
−
C7H14NO3 C7H11O3 C5H8NO2 C4H8NO2 C7H13 C4H10NO C6H11 C6H7 C4H7O C5H9 C3H8N C4H7
+
  </table>
−
C7H14NO3 = C7H11O3 C4H8NO2 C4H10NO C3H8N
+
   </td>
−
C4H10NO = C3H8N
+
 
−
}}
+
   <td valign="bottom">
−
|#|{{#bar:}}}}
+
  <table cellpadding="0" cellspacing="0" style="background-color: #cc0000; width: 8px; height: 40px">
 +
    <tr><td>&nbsp;</td></tr>
 +
  </table>
 +
  </td>
 +
 
 +
  <td valign="bottom">
 +
  <table cellpadding="0" cellspacing="0" style="background-color: #aa0000; width: 8px; height: 30px">
 +
    <tr><td>&nbsp;</td></tr>
 +
  </table>
 +
  </td>
 +
</tr>
 +
</table>
 +
 
 +
 
 +
{{#graph:hbar|size=30x40;margin=1,1,1,1;title=;legend=0x0;label=;=10,34,20,10,33}}
 +
 
 +
{|cellpadding="1" cellspacing="0"
 +
|-
 +
|valign="bottom"|
 +
{| cellpadding="0" cellspacing="0" style="width: 8px; height: 20px"
 +
|- style="background-color:#ff0000"
 +
|
 +
|}
 +
 
 +
|valign="bottom"|
 +
{| cellpadding="0" cellspacing="0" style="width: 8px; height: 40px"
 +
|- style="background-color:#dd0000"
 +
|
 +
|}
 +
 
 +
|valign="bottom"|
 +
{| cellpadding="0" cellspacing="0" style="width: 8px; height: 30px"
 +
|- style="background-color:#aa0000"
 +
|
 +
|}
 
|}
 
|}
  
−
<!----
+
{|cellpadding="1" cellspacing="0"
−
{{#lua:
+
|-
−
  local H = {};
+
|valign="bottom"|
−
  local I = {};
+
{| cellpadding="0" cellspacing="0" style="width: 8px; height: 20px"
−
  for id, name in stdin:gmatch("&&(%w+).Common Name=&&([%S ]+)") do
+
|- style="background-color:#ff0000"
−
    name = string.lower(name);
+
|
−
    for term in string.gmatch(name,"(%w+)") do
+
|}
−
      if ((string.len(term) < 5)) then
+
 
−
        if (H[term] == nil) then
+
|valign="bottom"|
−
          table.insert(I, term);
+
{| cellpadding="0" cellspacing="0" style="width: 8px; height: 40px"
−
      -- else
+
|- style="background-color:#dd0000"
−
      --  H[term] = H[term] .. ";" .. id;
+
|
−
        end
+
|}
−
        H[term] = id;
+
 
−
      end
+
|valign="bottom"|
−
    end
+
{| cellpadding="0" cellspacing="0" style="width: 8px; height: 30px"
−
  end
+
|- style="background-color:#aa0000"
−
  table.sort(I, function (x,y) return string.len(x)<string.len(y) end);
+
|
−
  local ret = "";
+
|}
−
  for i=1,table.getn(I) do
+
|}
−
    local k = I[i];
+
 
−
    ret = ret .. "* '''" .. k;
+
 
−
    for id in string.gmatch(H[k],"%w+") do
+
{|
−
      ret = ret .. "'''&nbsp;&nbsp; [[" .. id .."]] &nbsp; ";
+
|-
−
    end
+
|style="background-color:#ff0000;font-size:4pt;"|
−
    ret = ret .. "\n";
+
|style="background-color:#dd0000;color:#dd0000;"|
−
  end
+
|style="background-color:#aa0000;"|
−
  print(ret);
+
|style="background-color:#880000;"|
−
|
+
|style="background-color:#660000;"|
−
{{#SearchLine:Common Name=||FL%}}
+
|}<math>\longrightarrow</math>
−
}}
+
---->
−
--->
+

Latest revision as of 14:56, 22 April 2013

[edit] 根基イデアルとイデアル多様体対応

イデアルとアフィン多様体の対応は1対1ではない。 例えば <x> と <x2> は k[x] の異なるイデアルだが、多様体は同じである V(x) = V(x2) = { 0 } 。 体 k が代数的閉体でない場合、複素数解が生じる多項式は対応する多様体が空集合になってしまう。しかし代数的閉体である場合は k[x] の多項式は必ず根を持ち、空集合に対応するイデアルが複数にならず、V(I) = { } となるには多項式環全体つまり I = k[x] となる。これを示したのがヒルベルトの零点定理であった。

§2では零点定理をイデアルの言葉で書きなおしてみる。

零点定理によるとイデアル I が V(I) で消える多項式全体のなすイデアルとならない唯一の理由は、 I に含まれない多項式 f のベキ fm が I に含まれるからであった。そこで根基イデアルという概念を導入する。

定義：ある整数 m に対しfm∈ I ならば f ∈ I を満たすとき、 I を根基 (radical) イデアルという。また、イデアル I に対してある整数 m があり fm ∈ I となる関数 f の集合を、イデアルの根基といって √I と記す。

定義における整数 m は 1 でもよいので、明らかに I ⊂ √I である。しかし I ≠ √I はありえる。例えばイデアル J = < x2, y3 > ⊂ k[x,y] を考えよう。 x , y は J に属さないが x ∈ √J, y ∈ √J である。 (xy)2 ∈ J から、xy ∈ √J 、さらに x + y ∈ √J である。しかし xy や x+y は J には属さないので、J ⊂ √J である。

補題： I が k[x ...] のイデアルなら、 √I もイデアルになる。
f , g ∈ √I なら fm, gl ∈ I となる。そこで (f + g)m+l-1の2項展開を考えると 各項は figj を含んでいる(ただし i+j = m+l-1 ) 。このとき fi または gj のいずれかが I に含まれるので (f + g)m+l-1 ∈ I になる。つまり (f + g) ∈ √I。 また同様に f ∈ √I なら hf ∈ √I となるので √I はイデアルである。さらに√Iは根基イデアルである。


強形の零点定理 k を代数的閉体とする。 I を k[x, ...] のイデアルとすると、I(V(I) ) = √Iとなる。
f ∈ √I とすると fm ∈I であり V(I) で消える。このとき f も消えるから f ∈ I(V(I))。
逆に　 f ∈ I(V(I)) のとき、f は V(I) で消えるから、零点定理よりある整数 m に対して fm ∈ I。すなわち f ∈ √I となる。
定理（イデアル多様体対応）
(i) アフィン多様体　→　イデアル　と、イデアル　→ アフィン多様体　は包含関係が逆になる。つまりイデアルが I1 ⊂ I2 なら、V(I1) ⊃ V(I2) になる。また多様体が V1 ⊂ V2 なら、I(V1) ⊃ I(V2) になる。また任意の多様体に対し V(I(V)) = V となってIは常に1対1である。
(ii) k が代数的閉体の場合、根基イデアルだけを考えると上記の写像は互いに逆写像となる全単射である。

以上から、多様体に関する問題は根基イデアルに関する代数の問題に言い換えられる。イデアルに対し、次の3つの問が考えられる。

  • 根基の生成元: √I = <g, ...> となるような多項式の集合を生成するアルゴリズム ... 実用的でないものはHermann(1926)により示され、Gianni et al (1988)らにより数式処理システムに組み込まれたものが示された
  • 根基イデアル: I が根基かどうかの判定アルゴリズム ... Gianni et al (1988)らにより数式処理システムに組み込まれたものが示された
  • 根基所属: 与えられた多項式 f が f ∈ √I かどうかの判定アルゴリズム ... ここで解説

イデアル I = <f, ...> を与えられた時、多項式 f が f ∈ √I であるかをみるには、I' = <f, ..., 1-yf> に定数多項式 1 が含まれるかどうかを判定するだけで良い。なぜなら \begin{align} 1 = y^m f^m + (1 - y^m f^m ) = y^m f^m + (1 - yf)(1 + ...) \end{align} であるから、もし 1 ∈ I' なら fm ∈ I を意味している。 また f ∈ √I ならある m に対して fm ∈ I を満たすから、1 ∈ I' となるため、 f ∈ √I の判定の必要十分条件になっている。

このことは、適当な順序で I' = <f, ..., 1-yf> の簡約グレブナ基底を計算し、その結果が { 1 } であれば f ∈ √I, そうでなければ含まれないという結論になる。

例
k[x,y] のイデアル I = \langle xy^2 + 2 y^2 , x^4 - 2x^2 + 1> \rangle に f = y - x^2 + 1 が所属するか判定する
k[x,y,z] の lex 順序で

I' = \langle xy^2 + 2y^2, x^4 - 2x^2 + 1, 1 - z(y - x^2 + 1)\rangle \subset k[x,y,z] は簡約グレブナ規定 { 1 } を持つ。よって f = y - x^2 + 1 \isin \sqrt{I} 。


Retrieved from "http://metabolomics.jp/mediawiki/index.php?title=Sandbox&oldid=304422"
Personal tools
Namespaces

Variants
Actions
Navigation
metabolites
Toolbox