技术摘要：有限域上代数曲线类群与游走度（Gonality）的计算

1. 问题陈述

本文解决了确定有限域上代数曲线两个基本不变量的计算挑战：除子类群（在作者的设定下同构于皮卡群/Picard group）以及游走度（即到射影直线非恒定映射的最小次数）。

显式计算这些不变量对于数论中的各种应用至关重要，包括通过 Mordell-Weil 筛法研究有理点、分析雅可比簇（Jacobian）的挠子群，以及研究模曲线上的点。然而，现有方法面临严重的性能瓶颈，特别是在处理大亏格或大剩余域的曲线时。其主要限制在于需要为成千上万甚至数百万个除子计算 Riemann-Roch 空间。标准的算法（如 Hess 的算法）依赖于理想和多项式算术，虽然在单次计算中效率较高，但在需要进行数百万次操作以获取这些不变量时，这种方式变得难以承受。

2. 方法论

作者提出了一种新的方法，将计算负担从重复的多项式算术转向高效的线性代数。该核心方法论依赖于一个涉及幂级数展开的预计算步骤，这使得大量 Riemann-Roch 空间的摊还计算成为可能。

2.1 通过级数展开进行预计算

算法不再独立地计算每个 Riemann-Roch 空间 $L(D)$，而是固定一个大的除子 $D_0$，并预计算 $L(D_0)$ 以及其基函数的级数展开。

• 理论基础： 定理 3.1 确立了对于固定的 $L(D_0)$ 基，子空间 $L(D_0 - D)$（其中 $D$ 是一个有效除子）可以被识别为特定矩阵 $A$ 的零空间。矩阵 $A$ 的条目源自基函数在支撑 $D$ 的点处的级数展开系数。
• 效率： 一旦定义矩阵 $A$ 的向量被预计算完成，确定 $L(D_0 - D)$ 的维数就简化为对有限域上的矩阵进行秩计算，这比多项式算术要快得多。

2.2 针对级数展开的优化

为了确保预计算步骤具有实用性，作者引入了三项针对现有 Magma 内置函数的改进：

1. 均匀化参数（算法 3.2）： 算法不使用通常会产生高次多项式的标准算法，而是计算作为坐标函数的低次多项式的均匀化参数。这避免了昂贵的多项式除法。
2. 避免 Hensel 提升： 算法避免通过 Hensel 提升来计算子环 $k(x) \subset \hat{O}_{X,x}$。相反，它使用其剩余类构成剩余域 $k(x)$ 之基的函数，这些函数更容易构造。
3. 归一化： 通过乘以精心选择的函数 $g_x$ 来对基函数进行缩放，算法避免了计算均匀化参数的高次幂，从而进一步降低了计算开销。

2.3 在游走度中的应用（第 4 节）

游走度算法（算法 4.3）遍历目标次数为 $d$ 的有效除子 $D$。

• 它将搜索限制在支撑于特定数量有理点的除子上（基于引理 4.1）。
• 它利用 Riemann-Roch 定理，通过计算由预计算的规范除子空间 $L(K_X)$ 的级数展开所导出的矩阵 $A$ 的秩，来检查是否满足 $\ell(D) \ge 2$。
• 这用快速的线性代数运算取代了为每个除子计算 $\ell(D)$ 的昂贵过程。

2.4 在类群中的应用（第 5 节）

类群算法（算法 5.3）遵循指数演算（index calculus）方法（Hess 的方法），但优化了关系收集阶段。

• 因子基： 选择一组闭点集 $S$ 来生成类群。
• 关系收集： 算法不再生成随机的小有效除子，而是固定一个大的除子 $D_0$（其支撑集在 $S$ 中），并为随机的 $S$-光滑除子 $D$ 计算空间 $L(D_0 - D)$。
• 光滑性检查： 一个新算法（算法 5.2）通过分析函数分子和分母的零除子来检查该函数的除子是否为 $S$-光滑，从而避免了完整的理想分解。
• 这些关系构成一个格（lattice），类群的结构通过关系矩阵的 Smith 标准型导出。

3. 主要贡献

1. 算法框架： 引入了一个基于预计算的框架，将计算大量 Riemann-Roch 空间的问题简化为线性代数问题（零空间/秩计算）。
2. 实现： 在 Magma 中实现了这些算法（软件包 CurveArith），对于足够大的亏格或剩余域，其速度比现有方法快出数个数量级。
3. 优化的均匀化参数： 一种用于计算均匀化参数的新程序（算法 3.2），它产生的表达式比标准库函数更简单，显著加快了级数展开的速度。
4. 高效的光滑性检查： 一种用于检查函数除子光滑性的优化方法，避免了代价高昂的理想分解。

4. 结果

作者将他们的算法与现有方法（用于游走度的算法 4.2 和用于类群的 Magma ClassNumber 内置函数）在三组曲线上进行了基准测试：随机平面曲线、随机空间曲线以及模曲线 $X_0(N)$。

• 游走度：

  • 对于模曲线 $X_0(N)$，新算法 (4.3) 相比于旧方法 (4.2) 实现了约两个数量级的加速。例如，使用新方法计算 $X_0(154)$ 在 $\mathbb{F}_5$ 上的游走度耗时 10 小时，而估计旧方法需要 860 小时。
  • 对于随机曲线，在亏格较大（$g \ge 10$）且域较大（$q \ge 30$）时，加速效果最为显著，运行时间减少了两个数量级以上。
  • 性能增益由预计算成本与测试除子数量的比率驱动；当除子数量很大时，线性代数方法占据主导地位。

• 类群：

  • 新算法 (5.3) 通常优于 Magma 的 ClassNumber 内置函数，对于大亏格和大域上的曲线，提升接近两个数量级。
  • 类群的提升不如游走度那样剧烈，因为类群算法存在第二个瓶颈：光滑性检查（算法 5.2），该步骤仍然依赖于多项式和理想算术。作者指出，在许多情况下，加速受到这一步的限制。

5. 重要性与声明

本文声称其主要意义在于提供了显式的、实用的实现，这些实现不仅在理论上可行，而且在实践中非常快速。作者强调，以往的类群计算往往需要数小时甚至数周，迫使研究人员放弃某些证明策略。

这些新算法使得此前难以实现的计算成为可能，例如：

• 为 LMFDB 计算数百万个模曲线的 $\mathbb{Q}$-游走度下界。
• 将关于挠子群和有理点的研究扩展到更高的次数和更大的域。

作者对局限性保持了谦逊的态度，承认：

• 类群算法仍受限于光滑性检查，他们计划在未来的工作中通过开发仅基于线性代数的版本来解决这一问题。
• 均匀化参数的计算性能在特定边缘情况（例如 $X_0(198)$ 上的特定点）下仍可能不是最优，这表明进一步的表示改进可能会带来额外的收益。
• 当需要计算的 Riemann-Roch 空间数量相对于预计算成本较大时，加速效果最为明显；对于小亏格和小域，这种改进微乎其微。

总之，本文展示了从直接算术计算向摊还线性代数的转变，成功克服了此前阻碍复杂曲线在有限域上进行显式计算的扩展性障碍。