技术摘要：关于最优多项式逼近常数的代数复杂度

1. 问题陈述

本文研究了对函数 $f(t) = \sqrt{1+t^2}$ 在区间 $[0, 1]$ 上进行切比雪夫等波纹（minimax）多项式逼近时所产生的常数的代数性质。该函数对于计算欧几里得范数 $\sqrt{x^2+y^2}$ 至关重要，这是数字信号处理中的常见操作，而平方根运算的计算成本较高。

核心问题是寻找最优系数，用于构建度数为 $n$ 的多项式 $h(t)$，以最小化 $h(t)$ 与 $\sqrt{1+t^2}$ 之间的最大误差（绝对误差或相对误差）。虽然切比雪夫定理保证了此类多项式的存在性和唯一性，但其最优系数的具体代数性质（特别是它们是否可以用根式进行闭式表达）此前尚未得到分析。

作者重点研究了从度数 $n=1$（线性逼近，即已知的 $\alpha$-max+$\beta$-min 算法）到度数 $n=2$（带有有理修正项的二次逼近）的过渡。

2. 研究方法

作者结合代数几何、伽罗瓦理论和计算代数来分析等波纹条件。

• 等波纹系统的代数化： 最优逼近由误差函数 $d(t) = h(t) - f(t)$ 在 $n+2$ 个点处达到最大幅值且符号交替的特征来表征。作者通过引入辅助变量（例如 $w^2 = 1+t^2$）来消除平方根，从而将这些条件（误差值和导数零点）转化为多项式方程组。
• 结式消元法（Resultant Elimination）： 为了寻找关键点（特别是第一个内部交替点 $k$）的极小多项式，作者使用经典的结式消元法将多元系统简化为单变量多项式。
• 伽罗瓦群分析： 通过计算所得多项式的伽罗瓦群来确定其可解性。作者利用了 乔丹定理（Jordan's Theorem） (1870)，该定理指出：包含一个对换（transposition）和一个 $p$-循环（对于特定范围内的素数 $p$）的传递子群是全对称群 $S_n$。作者通过在特定素数（如 $p=17, 257$）下对多项式进行取模分解，来验证这些条件，从而识别 Frobenius 元的循环类型。
• 希尔伯特不可约性定理： 为了将发现推广到各种范数之外，作者应用希尔伯特不可约性定理，证明对于代数目标函数族，不可解性是一个泛型属性（generic property）。
• 分段逼近分析： 本文将分析扩展到具有联合优化断点的分段多项式，分析了这些断点的代数次数以及算术效率的增益。

3. 主要贡献与结果

3.1 可解性相变

本文确立了在度数 1 和度数 2 逼近之间存在的代数复杂度上的尖锐相变：

• 度数 1（可解）： 对于绝对误差和相对误差形式，最优常数满足 4 次多项式。

  • 相对误差： 最优系数 $\alpha$ 满足一个伽罗瓦群为 $C_4$（循环群）的 4 次不可约多项式。这些常数可以用嵌套根式表示。
  • 绝对误差： 常数满足一个伽罗瓦群为 $D_4$（二面体群）的多项式。
  • 机制： 系统发生了解耦（decoupling）。关键点的位置是独立于误差水平确定的，从而允许顺序求解。

• 度数 2（不可解）： 二次逼近的最优常数被证明无法用根式表示。

  • 绝对误差： 第一个内部交替点 $k$ 是一个 20 次不可约多项式的根。其伽罗瓦群为 $S_{10} \times C_2$（阶数为 7,257,600）。由于 $S_{10}$ 包含非阿贝尔单群 $A_5$，因此该群是不可解的。
  • 相对误差： 相应的常数满足一个伽罗瓦群为 $S_{12}$（阶数为 479,001,600）的 12 次不可约多项式。
  • 机制： 系统是**不可约耦合（irreducibly coupled）**的；关键点与误差水平同时依赖于彼此，任何变量都无法在不求解整个系统的情况下被孤立出来。

3.2 向 $L_p$ 范数的扩展

作者将分析扩展到 $L_p$ 范数，即逼近 $(1+t^p)^{1/p}$。

• 对于 $p=3$（$L_3$ 范数），度数为 2 的等波纹常数的极小多项式次数跃升至 246。
• 代数复杂度随 $p$ 的增加而迅速增长。作者推测，不可约因子的次数遵循与 $p$ 相关的模式，且伽罗瓦群通常是全对称群（或其外积/乘积群）。

3.3 一般性不可解定理

利用希尔伯特不可约性定理，作者证明了对于函数族 $f_\lambda(t) = \sqrt{1+\lambda t^2}$，度数 2 的等波纹常数泛型而言是无法用根式表示的。具体而言，对于所有不在“稀集”（密度为零的集合）之外的有理数 $\lambda$，其伽罗瓦群保持为 $S_{10} \times C_2$。

3.4 分段逼近与断点

本文分析了将区间 $[0, 1]$ 划分为 $k$ 个子区间并对断点进行联合优化的分段等波纹逼近。

• 精度增益： 每当子区间数量翻倍，可以在不增加额外算术成本的情况下获得大约 $n+1$ 位的精度（因为在硬件中比较操作被视为免费）。
• 断点的代数复杂度： 即便是最优断点也是高复杂度代数数。对于 $k=2$ 个子区间的度数-1 逼近，最优断点是阶数为 $S_8 \times C_2$ 的不可约多项式的根，该群同样是不可解的。

3.5 数值数据

作者提供了度数 1 到 8 的数值等波纹解，分析了受 Bernstein 椭圆参数 $\rho \approx 4.612$ 控制的收敛速率。他们还提供了在 x86-64 硬件上评估这些逼近的并行执行调度方案，展示了尽管系数具有复杂性，但仍能高效计算更高阶的逼近。

4. 意义与主张

本文声称建立了一个此前未被观察到的、切比雪夫逼近理论与代数方程不可解性之间的联系。

• 结构性洞察： 作者解释说，从可解到不可解的转变是由一种结构性二分法驱动的：线性逼近中关键点的解耦与高阶逼近中关键点的耦合。
• 泛型不可解性： 研究结果表明，对于代数族中的几乎所有目标函数，所需的最优极小逼近常数是无法用根式表示的。这意味着“闭式”解（即根式表达）对于最优逼近常数而言是例外（仅限度数 1），而非普遍规律。
• 方法论贡献： 本文展示了通过模约减（Frobenius 元）应用乔丹定理来确定高次多项式（度数为 20 和 246）伽罗瓦群的效用，而在这些情况下直接计算是不可行的。

作者并不声称提供计算这些常数的实际新算法（因为它们是不可解的），而是旨在刻画此类逼近的根本代数极限。这项工作强调，尽管最优系数存在且可以精确到极高精度地进行数值计算，但它们缺乏经典工程近似中常见的代数简洁性（根式可表达性）。