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

技术摘要：穷尽符号积分与符号可积性景观

问题陈述
尽管微分对于初等函数而言是算法化的，并且可通过链式法则和乘积法则普遍计算，但积分缺乏通用算法。尽管基于刘维尔定理（1835 年）的里斯算法（1969 年）为判定初等函数是否拥有初等原函数提供了决策过程，但它并未解决一个根本的结构性问题：在特定类别的符号表达式中，可积性有多普遍？具体而言，如果从一个定义明确且复杂度有界的符号语法中随机抽取一个函数，其原函数能够用同一语法表示的概率是多少？先前的工作主要集中在生成随机表达式以用于机器学习训练，或在精心策划的测试集上对现有的计算机代数系统（CAS）进行基准测试，但尚无研究系统地测量作为复杂度和算子基函数的“可积性分数”。

方法论：穷尽符号积分（ESI）
作者引入了穷尽符号积分（Exhaustive Symbolic Integration, ESI），该方法在指定的算子基内枚举所有复杂度不超过给定值 $k$ 的不同符号函数，并确定其中哪些函数在该同类别内具有闭式原函数。方法论步骤如下：

1. 函数空间构建：利用穷尽符号回归（ESR），作者为五种不同的算子基生成了所有节点数不超过 $k$ 的表达式树。复杂度由树中的节点数量定义。所研究的算子基范围从最小有理运算到包含指数、对数和三角函数的集合。
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 对比：该方法作为积分算法被部署，通过在预计算的目录中搜索匹配目标被积函数的原函数。将这些结果与六种 CAS 引擎（SymPy、Mathematica、RUBI、FriCAS、Maxima、Giac）使用各种策略和超时设置进行比较，以识别那些抗拒标准算法的积分。

关键结果
该研究分析了五个算子基中超过 $10^6$ 个唯一函数，复杂度最高达 $k=10$。

• 高复杂度下的可积性下降：对于具有高复杂度覆盖范围的算子基（例如 core_maths、ext_maths、trig_maths），随着 $k$ 的增加，$\rho(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 成功识别出三个在所有策略下均抗拒所有六种测试 CAS 引擎的积分。这些积分共享一种结构模式：一个平方根代数扩展与一个超越塔（例如 $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）的积分，ESI 突显了当前计算机代数系统中的特定结构差距，特别是关于指数 - 对数塔上的代数扩展方面。

作者指出，他们的定量结果（例如 $k=6$ 峰值的具体位置）取决于所使用的特定表达式语法和复杂度度量（节点计数），但更广泛的趋势——对数增强和高复杂度下降——是所测试语法的稳健特征。