Equivariant ideals of polynomials

技術的概要：多項式の等変イデアル

問題提起
本論文は、可換環論の古典的結果、特にヒルベルトの基底定理とブヒバーガーのアルゴリズムを、無限個の変数を持つ多項式環の文脈へ一般化する課題に取り組む。古典的な設定では、変数は有限集合から選ばれるため、すべてのイデアルが有限生成（ネーター的）であることが保証される。しかし、変数が無限集合から選ばれる場合、標準的なネーター性は失われる。なぜなら、有限生成されたイデアルは、その生成元の変数を置き換えて作られるすべての多項式を含むとは限らないからである。

著者らは、変数のドメインとなる可算な関係構造 $A$ に対する多項式環 $K[A]$ において、埋め込み $A \to A$ の作用に対して不変であるイデアルとして定義される等変イデアルを調査する。核心的な問いは以下の通りである：

1. ドメイン $A$ に対してどのような条件の下であれば、すべての等変イデアルが（等変の意味で）有限生成されるか？
2. このようなイデアルの所属問題は決定可能か？
3. これらの結果を、オートマトン理論、ペトリネット、および無限構造上の線形代数にどのように適用できるか？

手法と枠組み
本論文は、アトム付き集合の理論の枠組み内で動作し、等変性と軌道有限性の概念を利用する。

• ドメイン：変数は関係構造 $A$ の要素である。埋め込みのモノイド $\text{Emb}_A$ は、変数を置き換えることで多項式に作用する。
• 等変ネーター性：イデアル $I$ が有限生成であるとは、$I$ が $B$ を含む最小の等変イデアルとなるような有限集合 $B$ が存在することを意味する。これは、$I$ が「軌道有限」（埋め込みの作用の下で有限）な基底を持つことと同値である。
• 整然と構造化されたドメイン：著者らは$\omega$-整然と構造化された（$\omega$-well structured）ドメインの概念を導入する。ドメイン $A$ が $\omega$-整然と構造化されているとは、自然数でラベル付けされたその有限誘導部分構造の集合が、埋め込み関係の下で整列半順序（wqo）をなすことをいう。
• 辞書式積：より大きなドメインを構成するために、本論文は整然と構造化された性質を保存する辞書式積（$A \otimes A'$）を利用する。これは直積とは対照的である。

主要な貢献と結果

1. ヒルベルトの基底定理の一般化（第 3 節）
著者らは、等変ネーター性に対する必要十分条件を証明する：

• 定理 12：$A$ が全順序かつ $\omega$-整然と構造化されたドメインであり、$K$ がネーター的である可換環であれば、多項式環 $K[A]$ は等変ネーター的である。$K[A]$ 内のすべての等変イデアルは有限基底を持つ。
• 定理 11：逆に、ある環 $K$ に対して $K[A]$ が等変ネーター的であれば、$A$ は $\omega$-整然と構造化されなければならない。
• 適用範囲：この結果は、等式ドメイン、有理数順序 $\mathbb{Q}$、順序数、およびそれらの辞書式積に適用される。証明は、ヒルベルトの基底定理の古典的証明を適応させたもので、標準的な除法順序に代えて、「特性対」（先頭単項式、変数の集合）上で定義された準順序 $\sqsubseteq$ を用いる。これにより、これらの対の wqo 性質が利用される。

2. 計算可能性とブヒバーガーのアルゴリズム（第 5〜7 節）
所属問題に対処するため、著者らは $A$ が計算可能（要素が有限に表現可能であり、局所的な埋め込みが決定・計算可能）かつ整列順序であると仮定する。

• グレブナー基底：著者らは等変イデアルに対するグレブナー基底を定義する。集合 $G$ がグレブナー基底であるとは、任意の $f \in \langle G \rangle$ に対して、ある $g \in G$ の先頭単項式（埋め込みの下で）が $f$ の先頭単項式を割り切ることをいう。
• アルゴリズム 1（等変ブヒバーガー）：著者らはブヒバーガーのアルゴリズムを拡張する。無限集合 $\text{Emb}_A(G)$ 内のすべての対に対して S-多項式を計算する代わりに、S-多項式の軌道有限集合の有限表現 $P_G$ に対してのみ計算を行う。
  • アルゴリズムは、安定するまで、簡約された非ゼロの剰余を基底に反復的に追加する。
  • 終了性：単項式上の準順序の wqo 性質によって保証される。
  • 正しさ：出力は生成された等変イデアルに対するグレブナー基底となる。
• 決定可能性（定理 54）：計算可能で、$\omega$-整然と構造化され、かつ整列順序であるドメインに対して、イデアル所属問題は決定可能である。
• 還元ゲーム（第 7 節）：整列順序でないドメイン（例えば有理数順序 $\mathbb{Q}$）を扱うために、著者らは「還元ゲーム」$G(A, A')$ を導入する。Reducer が整列順序ドメイン $A'$ に対して勝利戦略を持つ場合、$A$ に対する所属問題は $A'$ に対する所属問題に還元される。これにより、決定可能性を $\mathbb{Q}$ およびその辞書式積に拡張できる。

3. 応用（第 4、8、9 節）
本論文は、これらの代数的結果の有用性を以下の 3 つの分野で実証する：

• 軌道有限生成ベクトル空間（第 4 節）：著者らは、軌道有限生成ベクトル空間が有限長さ（等変部分空間の無限の狭義増加鎖を持たない）を持つことを証明する。これは [6] の結果を一般化し、より単純な証明を提供する。
  • 応用：これは、これらのドメイン上の重み付きレジスタオートマトンに対する零性問題の決定可能性を意味する。
• データ付き可逆ペトリネット（第 8 節）：データ付き可逆ペトリネットの到達可能性問題は、データドメイン上の多項式環におけるイデアル所属問題に還元される。
  • 結果：$\mathbb{Q}$ およびその辞書式積上のデータ付き可逆ペトリネットに対する到達可能性は決定可能である。これは、順序付きデータを持つ非可逆ペトリネットの到達可能性の非決定可能性と対照的である。
• 軌道有限線形系（第 9 節）：軌道有限の線形方程式系を解く問題は、イデアル所属問題に還元される。
  • 結果：これは [15] の主要な結果を、広範なドメイン（等式、有理数順序など）に一般化し、明示的な複雑性の上限を提供しないものの、より単純な証明を提供する。

意義と主張
本論文は、無限構造上のイデアルの研究を統合する基礎的な理論的枠組みを提供すると主張する。

• 理論的深さ：$\omega$-整然と構造化性が、ヒルベルトの基底定理を等変イデアルへ一般化するために必要な正確な条件であることを確立する。
• アルゴリズム的貢献：これらの無限構造に対するグレブナー基底を計算する構成的方法（アルゴリズム 1）を提供し、抽象的な存在証明を決定可能な手続きへと変換する。
• 単純化：著者らは、応用（ベクトル空間の有限性、線形系）に対する証明が、明示的な複雑性上限を提供していないにもかかわらず、先行研究（[6], [15]）と比較して「驚くほど単純」であると指摘する。
• 範囲：結果は、等式、有理数順序、複雑な辞書式積を含む多様なデータドメインを網羅しており、オートマトンおよび検証理論における代数的手法の適用範囲を大幅に拡大する。

本論文は結論において、結果は一般的であるものの、アルゴリズムの複雑性（特にブヒバーガーアルゴリズムにおける安定化点）は有界ではないと指摘し、それを将来の研究のための未解決領域として残している。