Exhaustive Symbolic Integration: Integration by Differentiation and the Landscape of Symbolic Integrability

技術的概要：網羅的記号積分と記号積分可能性の風景

問題提起
微分は連鎖律と積の規則を通じて初等関数に対してアルゴリズム的かつ普遍的に計算可能であるのに対し、積分には普遍的なアルゴリズムが存在しない。1969 年のリス（Risch）アルゴリズムは、1835 年のリウヴィルの定理に基づき、初等関数が初等関数の原始関数を持つかどうかを決定する手続きを提供するが、それは以下の根本的な構造的問いには答えていない：特定の記号式クラスにおいて、積分可能性はどの程度普遍的か？具体的には、定義された記号文法から複雑性が制限された関数がランダムに抽出された場合、その原始関数が同じ文法内で表現できる確率はどれほどか？先行研究は、機械学習のトレーニング用ランダム式の生成や、既存のコンピュータ代数システム（CAS）をキュレーションされたテストセットでベンチマークすることに焦点を当ててきたが、複雑性と演算子基底の関数としての「積分可能分数」を体系的に測定した研究は存在しない。

手法：網羅的記号積分（ESI）
著者らは、指定された演算子基底内で与えられた複雑さ $k$ までのすべての異なる記号関数を列挙し、そのクラス内で閉形式の原始関数を持つものを特定する手法である「網羅的記号積分（Exhaustive Symbolic Integration: ESI）」を導入する。手法は以下の通り進行する：

1. 関数空間の構築：網羅的記号回帰（ESR）を用いて、5 つの異なる演算子基底に対して、最大 $k$ 個のノードを持つすべての式木を生成する。複雑さは木内のノード数によって定義される。研究対象の基底は、最小限の有理演算から、指数関数、対数関数、三角関数を含む集合まで多岐にわたる。
2. 重複除去：同じ数学的関数の構文的多様性によって積分可能分数が過大評価されないよう、著者らは 2 段階の重複除去プロセスを採用する：
   • 記号簡略化：式を SymPy オブジェクトに変換して簡略化する。
   • 数値フィンガープリント：記号簡略化で見逃された重複を捕捉するため、式を固定されたパラメータ値で $N=60$ 個のランダムな点において評価する。得られた値を丸め、MD5 でハッシュ化してコンパクトなフィンガープリントを作成する。フィンガープリントが同一の関数は同等とみなされる。
3. 微分とマッピング：集合 $\mathcal{F}_{\le k}$ 内の各関数 $F$ を微分して $F'$ を生成する。$F'$ のフィンガープリントを、$\mathcal{F}_{\le k}$ 内のすべての関数のフィンガープリントの集合と比較する。
4. 積分可能分数（$\rho(k)$）：その集合内にとどまる導関数（したがって逆写像の定義により原始関数）を持つ関数の割合は、以下のように計算される：
   $$\rho(k) = \frac{|\{F \in \mathcal{F}_{\le k} : \text{hash}(F') \in \text{hash}(\mathcal{F}_{\le k})\}|}{|\mathcal{F}_{\le k}|}$$
5. CAS との比較：この手法は、ターゲットとなる被積分関数に一致する原始関数を事前計算されたカタログから検索することで、積分アルゴリズムとして展開される。これらの結果は、標準的なアルゴリズムに抵抗する積分を特定するために、様々な戦略とタイムアウトを用いて 6 つの CAS エンジン（SymPy、Mathematica、RUBI、FriCAS、Maxima、Giac）と比較される。

主要な結果
本研究は、複雑さ $k=10$ までの 5 つの演算子基底にわたる $10^6$ 以上の一意の関数を分析した。

• 高複雑さにおける積分可能性の低下：高複雑さのカバレッジを持つ基底（例：core_maths、ext_maths、trig_maths）において、$\rho(k)$ は $k$ の増加とともに減少する。例えば、core_maths は $k=7$ で約 5.5% から $k=10$ で 3.5% まで低下する。これは、異なる導関数の形式の空間が、関数空間そのものよりも急速に成長するためである。
• 対数関数の効果：対数演算子の導入は、風景を劇的に変える。ext_log_maths と core_log_maths の基底は、対数を持たない対応する基底と比較して、$\rho(k)$ が約 2.5 倍から 3.6 倍高い。さらに、これらの基底は $k=6$ で明確な非単調なピークを示し（ext_log_maths で約 11.6%、core_log_maths で 19.2% に達する）。
  • メカニズム：対数関数の導関数 $d/dx[\log(f)] = f'/f$ は、既存の関数カタログと効率的に重なり合う有理形式を生成する。一方、指数関数の導関数 $d/dx[\exp(f)] = f' \exp(f)$ は、新しい指数因子を導入し、それがしばしば列挙の限界を超えて複雑さを押し上げ、一致するものを見つける確率を低下させる。
• 三角関数の独立性：trig_maths 基底（sin/cos）は、対数基底のような高い積分可能性を示さない。sin/cos が微分に対して閉じた軌道を持つにもかかわらず、連鎖律が乗法的因子（$f'$）を導入し、急速な複雑さの成長を招いて閉包の利点を相殺する。
• 新規積分と CAS の限界：ESI は、すべての戦略において 6 つのテストされた CAS エンジンのすべてに抵抗する 3 つの積分を特定することに成功した。これらの積分は、閉形式の置換では元に戻すことができない方法で、平方根代数的拡張と超越的タワー（例：$e^x$、$e^{-x}$、または $x^x$）が結合された構造的パターンを共有する。例としては以下が挙げられる：
  • $\int (2x+1)e^{\sqrt{x}+e^{-x}} dx = 2\sqrt{x}e^{\sqrt{x}+e^{-x}}$
  • $\int (2x+1)e^{\sqrt{|x-e^{-x}|}} dx$
  • $\int x^{x-3/2}(1-x-x\log x) dx = 2\sqrt{|x-x^x|}$
    さらに、ESI は多くのケースで CAS よりも単純な原始関数形式を発見し、展開形式よりも因数分解またはネストされた表現を優先することで、大幅なノード数の削減を実現している。

意義と主張
本論文は、記号積分可能性の風景は、初等関数の均質な性質というよりも、主に演算子の選択によって形作られると主張する。対数演算子の導入は、「閉包密度」を生み出し、制限された複雑さクラス内で原始関数を見つける確率を大幅に高める。

著者らは、ESI をすべての積分タスクに対する汎用 CAS との競合としてではなく、網羅的な構造的カバレッジのためのツールとして位置づけている。その意義は以下の点にある：

1. 体系的発見：現在のリスの実装やヒューリスティックな手法が見逃す、新規のものを含む積分可能な形式を体系的に発見できる。
2. 定量的分析：特定の演算子が積分に対する閉包を促進または阻害する方法を明らかにする、積分可能分数 $\rho(k)$ の最初の定量的測定を提供する。
3. アルゴリズム的ギャップの診断：最も完全なリスの実装（FriCAS など）さえも抵抗する積分を特定することにより、特に指数 - 対数タワー上の代数的拡張に関する現在のコンピュータ代数システムにおける特定の構造的ギャップを浮き彫りにする。

著者らは、定量的結果（$k=6$ のピークの具体的な位置など）は使用された特定の式文法と複雑さの指標（ノード数）に依存するが、より広範な傾向（対数による増強と高複雑さにおける低下）は、テストされた文法の頑健な特徴であると指摘している。