暗号応用を見据えた機械学習によるグレブナー基底計算
三菱電機株式会社 神戸祐太
Co-workers
前田洋太、Tristan Vaccon（フランス、リモージュ大）名前：神戸祐太(Yuta Kambe)
出身：埼玉/春日部

簡単な経歴• 2017年 ~ 2021年

埼玉大学 博士（学術）• 指導教官：渡邊究先生（現：中央大学）• 専門：Gröbner basis + Hilbert scheme• 2020年 ~ 2022年

株式会社すうがくぶんか• 一般向け数学教室（大学数学、統計、機械学習）• 2020年 ~ 現在

立教大学・三菱電機との暗号共研• 安田雅哉先生（立教）、横山和弘先生（立教）、相川勇輔さん（東大）など• 2022年 ~ 現職

三菱電機株式会社

リサーチアソシエイト• 数学・情報系のポスドク。学振PD＋福利厚生＋研究費というイメージ• 研究内容は比較的自由。実応用を見据えた先進的研究を目指す！
• 神戸のテーマ：グレブナー基底の多角的研究、暗号応用、耐量子計算機暗号など

今日の話題動機：高速グレブナー基底計算ができるAI(Transformer)を作りたい• 暗号の安全性、実応用に大きな影響• AIに数学はできるか？
新たな問題の発見：学習用データ生成における課題• どのようにグレブナー基底𝑮を偏りなく大量に作る？
• どのように 𝑮 = ⟨𝑭⟩となる𝑭を偏りなく大量に作る？
主結果：上記課題の解決法の提案• これまでの実験方法と実験結果の紹介（with Kera et.al.）• 新たな学習用データセット生成法とその代数幾何的性質（with Maeda et.al）今日の話題主定理（K.-Maeda-Vaccon）
𝑅 = ℚ[𝑥1 , … , 𝑥𝑟 ]とする。
𝐺 = 𝑔1 , … , 𝑔𝑛 ∈ 𝑅𝑛 (𝑛 ≥ 2)、𝑚 ≥ 2𝑛、に対して、後述のヒューリスティックを仮定する。（発表後半で紹介）
このとき、イデアル⟨𝐺⟩の𝑚個の元からなる生成系全体の部分集合

𝓕𝟎 ⊂ ℱ = {𝐹 = 𝑓1 , … , 𝑓𝑚 ∈ 𝑅 𝑚 ∣ 𝐹 = 𝐺 }で、次をみたすものが存在する。
• ℱ0 のランダムな元を効率的に出力するアルゴリズムが存在する。
• ℱ0 はℱの中でザリスキー稠密である。
ザリスキー位相で稠密目次• イントロダクション• Transformerと学習データ生成における問題• グレブナー基底の基礎基本• グレブナー基底計算の機械学習• これまでの研究• 学習データがもつ代数幾何的性質

イントロダクション

Transformer

Transformer

ChatGPT= Chat Generative Pre-trained Transformer• Transformer＝NNモデルの一種• NNモデル＝ニューラルネットワークモデル＝ある関数の１次結合と合成
𝒩 𝑥 = 𝐴3 ⋅ 𝜎 𝐴2 ⋅ 𝜎 𝐴1 ⋅ 𝑥 + 𝑏1 + 𝑏2+ 𝑏3• Attention is all you need(’17)で提案• Attention：２ベクトルの「類似度」を評価• 非常に高い言語処理能力を持つTransformer＝人間によくフィットしたAIの素Transformer
事前に自然言語を学習済み

どうやったらフィールズ賞がとれますか？

Transformer×Math
Transformer（AI）に数学は解けるか？
事前に問題と解の関係を学習済み

この方程式を解いてください

𝑥 = ⋯が解ですTransformer×Math
Transformer（AI）に数学は解けるか？

Lample-Charton, “DEEP LEARNINGFOR SYMBOLIC MATHEMATICS”,
2019

Transformer×Math
積分問題

解答

SymPyで計算できず、Transformerには解けた問題例• 4 × 107 =400万個のサンプルから学習• （問題、解答）の組×(𝟒 × 𝟏𝟎𝟕 )個• 基本的に1秒未満で解答を与える• 機械学習モデル＝簡単な関数の１次結合と合成• Mathematica, Matlab, Maple
でも同様の例が発見された

Transformer×Math
Transformer（AI）に数学は解けるか？
A: 解ける例、解けない例が見つかり始めている！
• ℤの加減乗除• ℤでのGCD計算• 多項式の展開• 線形代数：できる（5桁くらいまで）：できる：できる（12次、20項くらいまで）：できる（4 × 4くらいまで）• 有限体上の加減乗除：非常に難しい（Q.数学的な理由は？）• 大きいサイズの問題たち ：入力も困難（Transformerの実装限界）

NP困難な問題はどうか？

Transformer×Math×Crypto
現代暗号の復号法
暗号文sdsaF%”goa変換

求解数学問題

メッセージ

Hallo

求解計算量
• ヒント無（攻撃者）：NP困難性などの計算困難性(安全性の根拠)• ヒント有（受信者）：多項式時間計算量以下Transformer×Math×Crypto
Transformer（AI）でNP困難問題は解ける？
A: よくわかっていないので研究進行中• LWE（Learning With Erros）• 様々な耐量子計算機暗号の安全性の根拠• Transformer×LWE：SALSA project（23~, Meta社が中心）• 暗号インスタンス：× 全数探索が困難な境界サイズ：○• グレブナー基底計算問題• 𝐼 = 𝐹 を入力として𝐼のグレブナー基底𝐺（特別な生成系）を算出• 様々な暗号、耐量子計算機暗号の安全性の根拠• 代数方程式の求解、様々な代数不変量、代数幾何不変量の計算• Transformer×グレブナー：計良-Vaccon-石原-神戸-横山(23~)• Buchberger’s Alg.より100倍速い例が見つかっている！
• Buchberger先生も独立して提案、強い関心を持っているTransformer×グレブナー
作りたい機械学習モデル
グレブナー基底
計算モデル

多項式系
𝑓1
𝐹= ⋮𝑓𝑚入力• 入力：多項式系𝐹 = 𝑓1 , … , 𝑓𝑚
• 出力：グレブナー基底𝐺 = (𝑔1 , … , 𝑔𝑛 )イデアル⟨𝐹⟩のグレブナー基底
出力

𝑔1
𝐺= ⋮
𝑔𝑛

大量の多項式系と大量のグレブナー基底が必要！！！

学習用データセット生成に伴う新たな課題
学習用データセット生成の２パターン：
1. 問題を大量に用意し、問題から解答を作る。（Forward型）
2. 解答を大量に用意し、解答から問題を作る。（Backward型）

Forward型（𝐹 ↦ 𝐺）の課題点：• グレブナー基底計算はNP困難→ 107 オーダーの回数の実行は不可能• （厳密には：それが可能なイデアルのクラスは非常に小さい）
Backward型（𝐺 ↦ 𝐹）の課題点：• どのようにグレブナー基底を大量に作る？
• どのように 𝐺 = ⟨𝐹⟩となる𝐹を偏りなく、ランダムに作る？

機械学習理論に基づいた新たなタイプの問題を発見

これまでの実験結果
Kera-Vaccon-Ishihara-Kambe-Yokoyama(’23, arXiv:2311.12904)• 項の数は疎密パラメータ𝜎で調整

結果• 正答率はあまりよくない→ただし、係数を除けばそこそこ高い⇒先頭イデアルは当てられる（オラクルとして使える？）

成功例

20

失敗例

イントロのまとめと今日の話題
グレブナー基底計算をTransformerに学習させたい• Transformerは数学が解けるか？
• 特に、NP困難な問題が解けると暗号や実応用への影響が大きい。
学習用データセット生成の課題点• どのようにグレブナー基底を大量に作る？
• どのように 𝐺 = ⟨𝐹⟩となる𝐹を偏りなく、ランダムに作る？
今日の話題• どのように上記課題を解決したか• これまでの実験方法と実験結果• 新たな学習用データセット生成法とその代数幾何的性質

グレブナー基底の基礎基本

グレブナー基底の基礎基本
Q：次の方程式をどう解く？
𝑓1 = 𝒙 + 𝑦 − 1 = 0
ቊ
𝑓2 = 𝟐𝒙 + 𝑦 − 1 = 0
A：消去法を使う＝項を消していく（代入法もあり）𝒙を消す：𝑓2 − 2𝑓1 = −𝑦 + 1 = 0 → 𝑦 = 1
𝑦を代入して𝑥を求める：𝑥 = −𝑦 + 1 = 0

グレブナー基底の基礎基本
Q：次の方程式をどう解く？
𝑓1 = 𝒙𝟐 + 𝑦 2 − 1 = 0
൝
𝑓2 = 𝟐𝒙 + 𝑦 − 1 = 0

実は、{𝑓1 , 𝑓2 , 𝑓3 , 𝑓4 , 𝑓5 }はグレブナー基底A：多変数の消去法をしてみる

𝒙𝟐 を消す：2𝑓1 − 𝑥𝑓2 = −𝒙𝒚 + 2𝑦 2 + 𝑥 − 2 = 0 = 𝑓3
𝒙𝒚を消す：2𝑓3 + 𝑦𝑓2 = 𝟐𝒙 + 5𝑦 2 − 𝑦 − 4 = 0 = 𝑓4
𝒙を消す：𝑓4 − 𝑓2 = 𝟓𝒚𝟐 − 𝟐𝒚 − 𝟑 = 𝟎 = 𝑓5 → 𝑦 = 1, −3/5
𝑦を代入して𝑥を求める：𝑥 = −(𝑦 − 1)/2 = 0,4/5• どの項からどのように消していく？
• 必ず解が求まる？
• 多変数の消去法を可換環論で定式化するのがグレブナー基底理論

グレブナー基底の基礎基本
基本アイデア• 各単項式に大小関係を入れる• 𝒇𝒊 と𝒇𝒋 の最も大きい項を互いに消去する：
𝑆 𝑓𝑖 , 𝑓𝑗 = 𝑐𝑖𝑗 𝑚𝑖𝑗 𝑓𝑖 − 𝑐𝑗𝑖 𝑚𝑗𝑖 𝑓𝑗（𝑚𝑖𝑗 , 𝑚𝑗𝑖 は単項式、𝑐𝑖𝑗 , 𝑐𝑗𝑖 はスカラー）• 𝑺(𝒇𝒊 , 𝒇𝒋 )の各項を、𝒇𝒊 の最も大きい項で消去していく：
𝑆 𝑓𝑖 , 𝑓𝑗 = 𝑎1 𝑛1 𝑓𝑘1 + 𝑎2 𝑛2 𝑓𝑘2 + ⋯ + 𝑎𝑡 𝑛𝑡 𝑓𝑘𝑡 + 𝑟（𝑎𝑘 はスカラー、𝑛𝑘 は単項式、𝑛1 ≻ 𝑛2 ≻ ⋯ ≻ 𝑛𝑡𝑟の項はもう割り切れない）

グレブナー基底の基礎基本• 各単項式に大小関係を入れる。
定義• 𝒏変数単項式を非負整数ベクトル𝛼 = (𝛼1 , … , 𝛼𝑛 )について、
𝛼𝛼 𝛼𝑥 𝛼 = 𝑥1 1 𝑥2 2 ⋯ 𝑥𝑛 𝑛で表す。
• 𝑛変数単項式全体の全順序≺が項順序であるとは、以下がなりたつことをいう：• 𝛼 ≠ 0 ⟹ 1 ≺ 𝑥 𝛼 (∀𝛼)
• 𝑥 𝛼 ≺ 𝑥 𝛽 ⟹ 𝑥 𝛼 ⋅ 𝑥 𝛾 ≺ 𝑥 𝛽 ⋅ 𝑥 𝛾 (∀𝛼, 𝛽, 𝛾)グレブナー基底の基礎基本
辞書式順序𝑥 𝛼 ≺ 𝑥 𝛽 ⟺ 𝛼1 = 𝛽1 , … , 𝛼𝑖−1 = 𝛽𝑖−1 , 𝛼𝑖 ≺ 𝛽𝑖

つまり、
• 第一変数が大きい方を大きいとする• 第一変数が同じなら第二変数を大きい方を大きいとする・・・• を繰り返す。
例：𝑦2 ≺ 𝑥𝑦 3 𝑧 3 ≺ 𝑥𝑦 2 𝑧 2 ,𝑥𝑦 ≺ 𝑥 2 𝑦以降、順序は辞書式順序とする。

グレブナー基底の基礎基本• 𝑓𝑖 と𝑓𝑗 の最も大きい項を互いに消去する：
𝑆 𝑓𝑖 , 𝑓𝑗 = 𝑐𝑖𝑗 𝑚𝑖𝑗 𝑓𝑖 − 𝑐𝑗𝑖 𝑚𝑗𝑖 𝑓𝑗（𝑚𝑖𝑗 , 𝑚𝑗𝑖 は単項式、𝑐𝑖𝑗 , 𝑐𝑗𝑖 はスカラー）

定義

多項式𝑓に対して、• 𝑓に現れる最も大きい単項式を先頭単項式といい、LM 𝑓 とかく。
• 𝑓の最も大きい項を先頭項といい、LT 𝑓 とかく。
𝑆 𝑓𝑖 , 𝑓𝑗 =lcm LM 𝑓𝑖 , LM 𝑓𝑗
𝐿𝑇 𝑓𝑖

𝑓𝑖 −

lcm LM 𝑓𝑖 , LM 𝑓𝑗
𝐿𝑇 𝑓𝑗

𝑓𝑗 をS多項式という。

LM 𝑓1 = LT 𝑓1 = 𝒙𝟐
𝑓1 = 𝒙𝟐 + 𝑦 2 − 1൝⇒൝
𝑓2 = 𝟐𝒙 + 𝑦 − 1
LM 𝑓2 = 𝒙, LT 𝑓2 = 𝟐𝒙
𝑺 𝒇𝟏 , 𝒇𝟐 = 𝟐𝒇𝟏 − 𝒙𝒇𝟐

グレブナー基底の基礎基本• 𝑆(𝑓𝑖 , 𝑓𝑗 )の各項を、𝑓𝑘 の先頭項で消去していく：

割り算はイデアル⟨𝑓1 , … , 𝑓𝑡 ⟩で閉じている

𝑆 𝑓𝑖 , 𝑓𝑗 = 𝑎1 𝑛1 𝑓𝑘1 + 𝑎2 𝑛2 𝑓𝑘2 + ⋯ + 𝑎𝑡 𝑛𝑡 𝑓𝑘𝑡 + 𝑟（𝑎𝑘 はスカラー、𝑛𝑘 は単項式、𝑛1 = LM(𝑆(𝑓𝑖 , 𝑓𝑗 )) ≻ 𝑛2 ≻ ⋯ ≻ 𝑛𝑡
命題・定義

𝑟の項はもう割り切れない）

多項式𝑓1 , … , 𝑓𝑡 と多項式𝑔について、• 𝑔 = ℎ1 𝑓1 + ℎ2 𝑓2 + ⋯ + ℎ𝑡 𝑓𝑡 + 𝑟,
• LM ℎ𝑖 𝑓𝑖 ≼ LM 𝑔 ,• 𝑟の項はLM(𝑓𝑖 )で割り切れないをみたす多項式ℎ1 , … , ℎ𝑡 , 𝑟が存在する。
上記の式を𝒈の𝒇𝟏 , … , 𝒇𝒕 による割り算といい、𝒓をその余りという。

グレブナー基底の基礎基本
定義（ Buchberger ’65 , Hironaka ‘64 ）多項式系𝐺 = {𝑔1 , … , 𝑔𝑠 }がイデアル⟨𝑮⟩のグレブナー基底であるとは、全てのS多項式𝑆(𝑔𝑖 , 𝑔𝑗 )の𝐺による割り算の余りが0であることをいう。
アルゴリズム（Buchberger ’65）

入力：多項式系𝐹 = {𝑓1 , … 𝑓𝑡 }出力：イデアル 𝑓1 , … , 𝑓𝑡 のグレブナー基底𝐺 = {𝑔1 , … , 𝑔𝑠 }1. 各S多項式𝑆(𝑓𝑖 , 𝑓𝑗 )の𝐹による割り算の余り𝑟𝑖𝑗 を求める。
2. 多項式系𝐹を𝐹 ∪ {𝑟𝑖𝑗 ∣ 𝑖, 𝑗 = 1, … , 𝑡}に更新
3. 全ての余り𝑟𝑖𝑗 が0になるまで1,2を繰り返す。
4. 多項式系𝐺 = 𝐹を返す。
命題
上記のアルゴリズムは終了し、グレブナー基底を出力する。

グレブナー基底の基礎基本
計算論的定義多項式系𝐺 = {𝑔1 , … , 𝑔𝑠 }がイデアル⟨𝑮⟩のグレブナー基底であるとは、全てのS多項式𝑆(𝑔𝑖 , 𝑔𝑗 )の𝐺による割り算の余りが0であることをいう。
このとき、𝐼 = ⟨𝐺⟩

環論的定義

多項式系𝐺 = 𝑔1 , … , 𝑔𝑠 ⊂ 𝐼がイデアル𝑰のグレブナー基底であるとは、任意の𝑓 ∈ 𝐼 ∖ {0}についてある元𝑔𝑖 ∈ 𝐺が存在し、LM 𝑔 |LM(𝑓)定義・命題
イデアル𝐼のイニシャルイデアル：in 𝐼 = LM 𝑓 𝑓 ∈ 𝐼 ∖ {0}𝐺がグレブナー基底⟺ in 𝐼 = 𝐿𝑀 𝑔𝑔∈𝐺

グレブナー基底の基礎基本消去定理

𝐹 = 𝐺⇒ 𝐹と𝐺の解は同じ

𝑅 = 𝐾[𝑥1 , … , 𝑥𝑛 ]：多項式環
𝐼 = ⟨𝑓1 , … , 𝑓𝑡 ⟩:0次元イデアル（𝑓1 , … , 𝑓𝑡 の零点が有限個）𝐼の辞書式順序に関するグレブナー基底𝐺について、
𝐺 ∩ 𝐾 𝑥𝑛−𝑘 , … , 𝑥𝑛 (⊂ 𝐼 ∩ 𝐾[𝑥𝑛−𝑘 , … , 𝑥𝑛 ])はイデアル𝐼 ∩ 𝐾[𝑥𝑛−𝑘 , … , 𝑥𝑛 ]のグレブナー基底、特に、生成系になる。

多項式求解法：解が有限個である方程式𝑓1 = ⋯ = 𝑓𝑡 = 0を解く。
1. イデアル𝐼 = ⟨𝑓1 , … , 𝑓𝑡 ⟩の辞書式順序グレブナー基底𝑮を求める。
2. 1変数多項式系𝐺 ∩ 𝐾 𝑥𝑛 = {𝑔1′ , … , 𝑔𝑠′ ′ }の解集合を求める。
3. 2で求めた解集合を𝐺 ∩ 𝐾[𝑥𝑛−1, 𝑥𝑛 ]の𝑥𝑛 に代入する。
０次元イデアルの4. 代入後の1変数多項式系𝐺 ∩ 𝐾 𝑥𝑛−1 , 𝑥𝑛 |𝑥𝑛 ={𝑎𝑛 } の解集合を求める。
グレブナー基底5. 以上を繰り返し、𝐺の解＝𝐹の解を得る！
計算はNP困難グレブナー基底計算の機械学習

学習用データセットの作り方
学習用データセット生成の課題点
1. どのようにグレブナー基底を大量に作る？
2. どのように 𝐺 = ⟨𝐹⟩となる𝐹を偏りなく、ランダムに作る？
Kera-Vaccon-Ishihara-Kambe-Yokoyama(‘23)の方法
1. Shape Position グレブナー基底に着目
2. 左正則多項式行列に着目

Shape Position グレブナー基底
命題(Gianni-Mora ‘89)
0次元radicalイデアル𝐼について、genericな線形座標変換𝐿を施すと、𝐿(𝐼)の辞書式順序グレブナー基底で次の形のものが存在する。
𝑔1 = 𝑥1 − ℎ1 (𝑥𝑛 )𝑔2 = 𝑥2 − ℎ2 (𝑥𝑛 )⋮𝑔𝑛−1 = 𝑥𝑛−1 − ℎ𝑛−1 (𝑥𝑛 )𝑔𝑛 = 𝑔𝑛 (𝑥𝑛 )この形のグレブナー基底をShape Positionグレブナー基底という。
• この形の多項式系は辞書式順序についてグレブナー基底• ⇒ Shape Position GBのデータセット＝𝟏変数多項式のデータセット• ⇒ 簡単にたくさん作れる！genericな0次元多様体を扱える！

学習用データセットの作り方

以降、グレブナー基底のデータセットは持っているとする。

学習用データセット生成の課題点
1. どのようにグレブナー基底を大量に作る？←OK!
2. どのように 𝐺 = ⟨𝐹⟩となる𝐹を偏りなく、ランダムに作る？
Kera-Vaccon-Ishihara-Kambe-Yokoyama(‘23)の方法
1. Shape Position グレブナー基底に着目
2. 左正則多項式行列に着目

左正則多項式行列記号• 𝐾：体、𝑅＝𝐾[𝑥1 , … , 𝑥𝑟 ]：多項式環• 多項式系𝐹 = (𝑓1 , … 𝑓𝑚 )を縦ベクトル𝐹 = 𝑓1 , … , 𝑓𝑚 𝑇 ∈ 𝑅𝑚×1 とみる
命題与えられた多項式系𝐺 = (𝑔1 , … , 𝑔𝑛 )について、
𝑓1 , … 𝑓𝑚 ∈ 𝐺 ⟺ ∃𝐴 ∈ 𝑅𝑚×𝑛 , 𝑭 = 𝑨𝑮
命題
𝐹 = 𝐴𝐺について、∃𝑩 ∈ 𝑹𝒏×𝒎 , 𝑩𝑨 = 𝑬𝒏 ⟹ 𝑭 = ⟨𝑮⟩左正則多項式行列

このような行列𝐴を左正則多項式行列と呼ぶ

命題
𝐹 = 𝐴𝐺について、∃𝑩 ∈ 𝑹𝒏×𝒎 , 𝑩𝑨 = 𝑬𝒏 ⟹ 𝑭 = ⟨𝑮⟩{𝐴𝐺 ∣ 𝐴 ∈ 𝑅 𝑚×𝑛 は左正則多項式行列} ⊂ {𝐹 ∈ 𝑅 𝑚 ∣ 𝐹 = ⟨𝐺⟩}
アルゴリズムのアイデア
1. 左正則多項式行列𝐴をランダムにとる
2. 多項式系𝐹 = 𝐴𝐺はイデアル⟨𝐺⟩の生成系！

左正則多項式行列の作り方
アルゴリズムのアイデア
1. 左正則多項式行列𝐴をランダムにとる
2. 多項式系𝐹 = 𝐴𝐺はイデアル⟨𝐺⟩の生成系！

命題（Kera-Vaccon-Ishihara-K.-Yokoyama）

𝑬𝒏
𝑨 = 𝑼𝟏 𝑷
𝑼𝟐𝑶は左正則多項式行列。ただし、• 𝑈1 ∈ 𝑅𝑚×𝑚 , 𝑈2 ∈ 𝑅𝑛×𝑛 は対角成分が1の上三角行列• 𝑃は置換行列• 𝑂は零行列

Bruhat-Like
Decompositionこれまでの実験結果
Kera-Vaccon-Ishihara-Kambe-Yokoyama(’23, arXiv:2311.12904)• 高々5次のShape Positionグレブナー基底に、高々3次の上三角多項式行列𝑈1 , 𝑈2 をかける。
• 項の数は疎密パラメータ𝜎で調整
結果• 正答率はあまりよくない→ただし、係数を除けばそこそこ高い⇒先頭イデアルは当てられる（オラクルとして使える？）

よりよい学習用データセットはあるか？
命題（Kera-Vaccon-Ishihara-K.-Yokoyama）

𝑬𝒏
𝑨 = 𝑼𝟏 𝑷𝑼𝟐𝑶は左正則多項式行列。ただし、• 𝑈1 ∈ 𝑅𝑚×𝑚 , 𝑈2 ∈ 𝑅𝑛×𝑛 は対角成分が1の上三角行列• 𝑃は置換行列• 𝑂は零行列

一般化命題（K.-Maeda-Vaccon）

𝑬𝒏
𝑨=𝑼𝑶𝒎×𝒎は左正則多項式行列。ただし、𝑼 ∈ 𝑹は基本行列の積

実は𝑨 = 𝑼𝑬𝒏
𝑶で十分！

以下の形の多項式行列𝑃 ∈ 𝑅𝑚×𝑚 をまとめて基本行列と呼ぶ：• 𝑃 = 𝒆1 , … , 𝒆𝑗 , … , 𝒆𝑖 , … , 𝒆𝑚 𝑖 < 𝑗 （置換行列）• 𝑃 = 𝒆1 , … , 𝒆𝑖 + 𝑓𝒆𝑗 , … , 𝒆𝑗 , … , 𝒆𝑚 𝑖 ≠ 𝑗, 𝒇 ∈ 𝑹 （列の多項式倍の和）• 𝑃 = 𝒆1 , … , 𝑐𝒆𝑖 , … , 𝒆𝑚 (𝒄 ∈ 𝑲) （列の体の元倍）⟹行列式が𝑲の元になる通常の意味での基本行列たち命題
𝐴 ∈ 𝑅𝑚×𝑚 の行列式が𝐾の元⟺ 𝐴は正則多項式行列（逆行列∈ 𝑅𝑚×𝑚 ）命題（K.-Maeda-Vaccon）
𝑚 ≥ 𝑛 ≥ 3のとき、
𝐴∈𝑅

𝑚×𝑛が左正則多項式行列⟺ 𝑨 = 𝑼𝑬𝒏𝑶, ∃𝑼:基本行列の積

実は𝑨 = 𝑼𝑬𝒏
𝑶で十分！
既知？

命題（K.-Maeda-Vaccon）
𝑚 ≥ 𝑛 ≥ 3のとき、𝐴 ∈ 𝑅𝑚×𝑛 が左正則多項式行列⟺ 𝑨 = 𝑼

𝑬𝒏𝑶, ∃𝑼:基本行列の積

𝐵𝐴 = 𝐸𝑛 となる𝐵 ∈ 𝑅𝑛×𝑚 に対し、

0 → Ker 𝐵 → 𝑅定理（Suslin ‘77）𝑚が分裂することを使う。

𝑚 ≥ 3のとき、𝑈 ∈ 𝑅𝑚×𝑚 について、
det 𝑈 ∈ 𝐾 ∖ {0} ⇔ 𝑈は基本行列の積定理（Quillen-Suslin ’76, or Serre’s Conj.）
有限生成射影𝑅加群は自由𝑅加群

𝐵×

𝑅𝑛 → 0学習用データセットの作り方
アルゴリズム1. 学習させたいイデアルクラスのグレブナー基底族𝒢をとる
2. 各𝐺 ∈ 𝒢に対して、ランダムな基本行列𝑈1 , … , 𝑈𝑡 をとる
𝐸

3. 多項式行列𝐴 = 𝑈1 𝑈2 ⋯ 𝑈𝑡 𝑛 を計算する。
𝑂
4. 多項式系𝐹 = 𝐴𝐺はイデアル⟨𝐺⟩の生成系！

理想：一様分布
現実：解析する方法がまだ無い！

機械学習的（統計的）疑問

アウトプット全体の集合
𝐸𝑛ℱ0 = {𝑈1 𝑈2 ⋯ 𝑈𝑡
𝐺 ∣ 𝑈1 , … , 𝑈𝑡 は基本行列}𝑂
とりあえず、ザリスキー稠密からの一様ランダムサンプリングは生成系全体
ではあるℱ = {𝐹 = 𝑓1 , … , 𝑓𝑚 ∈ 𝑅 𝑚 ∣ 𝐹 = 𝐺 }ことを示すでどのような分布をもっている？

学習用データセットの稠密性
主定理（K.-Maeda-Vaccon）

ヒルベルトの既約性定理
を使うため、
現状はℚ（の有限次拡大）のみ

𝑅 = ℚ[𝑥1 , … , 𝑥𝑟 ]とする。
𝐺 = 𝑔1 , … , 𝑔𝑛 ∈ 𝑅𝑛 (𝑛 ≥ 2)、整数𝑚 ≥ 2𝑛、に対して、後述のヒューリスティックを仮定する。
このとき、イデアル⟨𝐺⟩の𝑚個の元からなる生成系全体の部分集合

𝓕𝟎 ⊂ ℱ = {𝐹 = 𝑓1 , … , 𝑓𝑚 ∈ 𝑅 𝑚 ∣ 𝐹 = 𝐺 }で、次をみたすものが存在する。
• ℱ0 のランダムな元を効率的に出力するアルゴリズムが存在する。
• ℱ0 はℱの中でザリスキー稠密である。

証明のスケッチ

ヒルベルトの既約性定理が成り立つ体

記号と定義• K はℚの有限次拡大（より一般に、Hilbertian Field）
𝑟+𝑖• 𝑅≤𝐷 = {𝑓 ∈ 𝑅 = 𝐾 𝑥1 , … , 𝑥𝑟 ∣ deg(𝑓) ≤ 𝐷} ≅ 𝐾𝑁𝐷 , 𝑁𝐷 = σ𝐷𝑖=0 𝑖• 𝒰 = {𝑓 ∈ 𝑅 ∣ 𝑓は既約}• 𝛿: 𝑅𝑛×𝑛 → 𝑅, 𝛿 𝐶 = det(𝐶)
命題（K.-Maeda-Vaccon）

𝑛×𝑛𝑛×𝑛非負整数𝐷 ≥ 0に対し、𝛿 −1 𝒰 ∩ 𝑅≤𝐷は𝑅≤𝐷においてザリスキー稠密稠密

ヒルベルトの既約性定理：
Genericなℚ係数について多項式は既約証明のスケッチ
記号と定義• 𝐴=••••𝐴1𝐴2∈ 𝑅𝑚×𝑛 , 𝐴1 ∈ 𝑅𝑛×𝑛 , 𝐴2 ∈ 𝑅 𝑚−𝑛 ×𝑛

𝐵 = 𝐵1 𝐵2 ∈ 𝑅𝑛×𝑚 , 𝐵1 ∈ 𝑅𝑛×𝑛 , 𝐵2 ∈ 𝑅𝑛× 𝑚−𝑛𝑛×𝑚𝑚×𝑛𝑛×𝑛
𝒳≤𝐷 = 𝐵, 𝐴 ∈ 𝑅≤𝐷× 𝑅≤𝐷𝐵𝐴 − 𝐸𝑛 𝐺 = 𝑂, 𝐵1 𝐴1 ∈ 𝑅≤𝐷𝑛×𝑛
𝑝: 𝒳≤𝐷 → 𝑅≤𝐷, 𝑝 𝐵, 𝐴 = 𝐵1 𝐴1
𝜑: 𝒳≤𝐷 → ℱ≤𝐷 = 𝐹 ∈ ℱ ∃ 𝐵, 𝐴 ∈ 𝒳≤𝐷 , 𝐹 = 𝐴𝐺 , 𝜑 𝐵, 𝐴 = 𝐴𝐺

定理（K.-Maeda-Vaccon）

ヒューリスティック𝑚 ≥ 2𝑛かつ𝓧≤𝑫 (𝑫 ≫ 𝟎)が既約なら、ℱ0 ∩ ℱ≤𝐷 はℱ≤𝐷 において稠密証明のスケッチ定理（K.-Maeda-Vaccon）
𝑚 ≥ 2𝑛かつ𝓧≤𝑫 (𝑫 ≫ 𝟎)が既約なら、ℱ0 ∩ ℱ≤𝐷 はℱ≤𝐷 において稠密

𝑛×𝑛
1. 条件𝑚 ≥ 2𝑛から、𝑝がセクション𝜄: 𝑅≤𝐷→ 𝒳≤𝐷 をもつ。
2. 1から𝑝のflat locus 𝑌は空ではない。
3. 共通( 𝛿 ∘ 𝑝 −1 𝒰 ∩ 𝒳≤𝐷 ) ∩ 𝑌は𝑌の稠密部分集合（𝑝|𝑌 の平坦性）
4. 3から 𝛿 ∘ 𝑝 −1 𝒰 ∩ 𝒳≤𝐷 は𝒳≤𝐷 の稠密部分集合（𝒳≤𝐷 の既約性）
5. 包含𝜑 𝛿 ∘ 𝑝 −1 𝒰 ∩ 𝒳≤𝐷 ⊂ ℱ0 ∩ ℱ≤𝐷 よりℱ0 ∩ ℱ≤𝐷 は稠密

ℱ≤1 ⊂ ℱ≤2 ⊂ ⋯ ⊂ ℱ =∪𝐷 ℱ≤𝐷 から、ℱ0 ⊂ ℱも稠密

まとめと今後高速グレブナー基底計算ができるAI(Transformer)を作りたい• 現状：あまり正答率がよくない、学習データの分布が不明
ザリスキー稠密なデータセットを作成
定理（K.-Maeda-Vaccon）

𝑚 ≥ 2𝑛かつ𝓧≤𝑫 (𝑫 ≫ 𝟎)が既約なら、ℱ0 ∩ ℱ≤𝐷 はℱ≤𝐷 において稠密
•この定理はどれだけ「モデルの良さ」に影響する？

今後の課題• 統計的な学習用データの評価• 「いい」応用問題の探索• ひいてはベンチマークデータの構築