ウーの特性集合法

呉文俊法は、 1970年代後半に中国の数学者呉文俊によって導入された多変数多項式方程式を解くアルゴリズムである、1940年代後半にJF Rittによって導入された特性集合という数学的概念に基づいている。特性集合を計算するためにグレブナー基底が使用されることがあるが、この方法はブルーノ・ブッフバーガー（1965）によって導入されたグレブナー基底法とは完全に独立している。 ^{[1] [2]}

ウーの方法は初等幾何学における機械的な定理の証明に強力であり、特定の種類の問題に対して完全な決定プロセスを提供する。この方法は彼の研究室（KLMM、中国科学院数学機械化重点研究室）および世界中で研究に使用されている。ウーの方法に関する研究の主な傾向は、正の次元の多項式方程式のシステムと微分代数に関するもので、そこではリットの結果が有効になっている。^{[3] [4]ウーの方法は、生物学、}コンピュータービジョン、ロボット運動学、特に幾何学の自動証明など、さまざまな科学分野に応用されている。 ^[5]

Wu 法では、多項式除算を使用して次の形式の問題を解決します。

${\displaystyle \forall x,y,z,\dots I(x,y,z,\dots )\implies f(x,y,z,\dots )\,}$

ここで、fは多項式方程式、I は多項式方程式の連言です。このアルゴリズムは、複素領域上のこのような問題に対して完全です。

このアルゴリズムの核となる考え方は、ある多項式を別の多項式で割って剰余を求めるというものです。繰り返して除算を行うと、剰余が消滅するか (この場合、Iはf を意味するというステートメントは真です)、または既約剰余が残ります (この場合、ステートメントは偽です)。

より具体的には、体k上の環k [ x ₁ , ...,  x _n ] のイデアル Iに対して、 Iの(Ritt) 特性集合Cは、三角形状のI内の多項式の集合で構成されます。 C内の多項式には、異なる主変数があります (下記の正式な定義を参照)。 Iの特性集合Cが与えられれば、多項式fがI を法としてゼロであるかどうかを判断できます。つまり、Iの特性集合が与えられれば、Iの所属テストはチェック可能です。

リット特性集合は、イデアルの三角形の形の多項式の有限集合です。この三角形集合は、リット順序に関して特定の最小条件を満たし、イデアルの多くの興味深い幾何学的特性を保持します。ただし、その生成元システムではない可能性があります。

R を体k上の多変数多項式環k [ x ₁ , ..., x _n ] とする。変数は添え字に従って線形に順序付けられる: x ₁ < ... < x _n 。R の非定数多項式pの場合、 pに実質的に存在する最大の変数(主変数またはクラスと呼ばれる) は特別な役割を果たす: pは自然に、 k [ x ₁ , ..., x _{k −1} ]に係数を持つ主変数x _kの単変数多項式と見なすことができる。主変数の単変数多項式としての p の次数は、主次数とも呼ばれる。

非定数多項式の集合T は、 T内のすべての多項式が異なる主変数を持つ場合、三角集合と呼ばれます。これにより、自然な方法で 三角線形方程式系が一般化されます。

2 つの非定数多項式pとqについて、次のいずれかの条件が成立する場合、 p はRitt 順序に関してqより小さいと言い、p  < _r qと表記されます。  

（１） pの主変数はqの主変数より小さい、すなわちmvar( p )<mvar( q )である。

（２）pとqは同じ主変数を持ち、pの主次数はqの 主次数より小さい、つまりmvar( p ) = mvar( q )かつmdeg( p ) < mdeg( q )である。

このように、 ( k [ x ₁ , ...,  x _n ],< _r )は完全な部分順序を形成します。ただし、 Ritt 順序付けは全順序ではありません。 p  < _r  qでもp  > _r  qでもない多項式 p と q が存在します。この場合、pとq は比較できないと言います。 Ritt 順序付けは、pとqのランクを比較します。非定数多項式pのランク (rank( p ) で表される) は、その主変数の累乗として定義されます: mvar( p ) ^{mdeg( p )。}ランクは、最初に変数を比較し、次に変数が等しい場合は次数を比較することで比較されます。

リット順序付けの重要な一般化は、三角集合を比較することです。T  = {  t ₁ , ...,  t _u } とS  = {  s ₁ , ...,  s _v } を、 TとS内の多項式が主変数に従って増分順に並べられている2 つの三角集合とします。次の主張のいずれかが成り立つ場合、 Tはリット順序付けに関して S より小さいと 言えます。

1. 1 ≤  i  <  kかつt _k  < _{rs k}に対して rank( t _i ) = rank( s i ₎となるk  ≤ min( u ,  v )が存在する。 
2. u  >  vかつ rank( t _i ) = rank( s _i ) （1 ≤  i  ≤  v ）。

また、Ritt 順序に関して比較できない三角集合も存在します。

_{Iをk[x 1} , ..., x _n ]の非ゼロイデアルとする。Iの部分集合Tは、以下の条件のいずれかが成立する場合、Iの Ritt特性集合である。

1. Tはkの単一の非ゼロ定数から成り、
2. T は三角集合であり、T は I に含まれるすべての三角集合の集合内で Ritt 順序に関して最小です。

リット順序は半順序であるため、多項式イデアルは（無限に）多くの特性集合を持つことができます。

Ritt によって最初に考案され、その後 Wu によって改良された Ritt-Wu プロセスは、Ritt 特性ではなく、Wu 特性セットまたは昇順チェーンと呼ばれる拡張特性を計算します。

F によって生成されるイデアル⟨F⟩の空でない部分集合 T は、次の条件のいずれかが満たされる場合、F の Wu 特性集合である。

1. T = {a}（aは非ゼロの定数）
2. Tは三角集合であり、 ⟨F⟩の部分集合Gが存在し、 ⟨F⟩ = ⟨G⟩であり、G内のすべての多項式はTに関して擬似的にゼロに簡約されます。

Wu特性集合は、Fによって生成されるイデアル⟨F⟩ではなく、多項式の集合Fに対して定義されます。また、 ⟨F⟩のRitt特性集合TはFのWu特性集合であることが示されます。Wu特性集合は、疑似剰余計算のみを必要とし、因数分解を必要としないWuアルゴリズムCHRST-REMによって計算できます。

ウーの特性集合法は指数関数的な計算量を持ち、弱い連鎖、正規連鎖、飽和連鎖による計算効率の改善が導入された^[6]

アプリケーションは、特性セットを使用して代数方程式のシステムを解くアルゴリズムです。より正確には、多項式の有限部分集合 F が与えられた場合、次のような特性セットT ₁、...、T _eを計算するアルゴリズムがあります。

${\displaystyle V(F)=W(T_{1})\cup \cdots \cup W(T_{e}),}$

ここで、W ( T _i )はV ( T _i )とV ( h _i )の差であり、h _iはT _iの多項式の頭値の積である。

• レギュラーチェーン
• 数学・機械化プラットフォーム

• P. Aubry、M. Moreno Maza (1999) 多項式システムを解くための三角集合: 4 つの方法の比較実装。J. Symb. Comput. 28(1–2): 125–154
• David A. Cox、John B. Little、Donal O'Shea。理想、多様性、アルゴリズム。2007 年。
• Hua-Shan, Liu (2005 年 8 月 24 日)。「WuRittSolva: Wu-Ritt 特性集合法の実装」。Wolframライブラリ アーカイブ。Wolfram。2012年11 月 17 日閲覧。
• ヘック、アンドレ (2003)。Maple入門(第3版)。ニューヨーク: シュプリンガー。pp. 105, 508。ISBN 9780387002309。
• Ritt, J. (1966). 微分代数. ニューヨーク、Dover Publications.
• 王東明 (1998)。除去方法。シュプリンガー フェルラーク, ウィーン, シュプリンガー フェルラーク
• ドンミン・ワン（2004年）エリミネーション・プラクティス、インペリアル・カレッジ・プレス、ロンドンISBN 1-86094-438-8 
• ウー、WT (1984)。初等幾何学における機械的定理証明の基本原理。J. Syst. Sci. Math. Sci.、4、207–35
• ウー、WT（1987）。多項式方程式を解くためのゼロ構造定理。MMリサーチプレプリント、1、2-12
• Xiaoshan, Gao; Chunming, Yuan; Guilin, Zhang (2009). 「任意の順序を持​​つ通常の差分多項式システムに対する Ritt-Wu の特性集合法」. Acta Mathematica Scientia . 29 (4): 1063–1080. CiteSeerX  10.1.1.556.9549 . doi :10.1016/S0252-9602(09)60086-2.

• wsolve Maple パッケージ
• 特性セット法