Complexity of counting points on curves and the factor P_1(T) of the zeta function of surfaces
Diptajit Roy, Nitin Saxena and Madhavan Venkatesh
本文研究数论中一个基本问题的计算复杂度：有限域上曲线和曲面的点计数。目前尚无已知的亚指数时间算法，且不清楚该问题是否为NP难。对于给定曲线，我们提出了第一个高效的Arthur-Merlin协议来验证其点计数、雅可比群结构及其Hasse-Weil zeta函数。我们将此结果推广到光滑射影曲面，通过使用计数预言机来验证zeta函数中对应于第一贝蒂数的因子P_1(T)。我们给出了第一个计算P_1(T)的算法：当输入曲面的度D固定时，该算法在poly(log q)时间内运行；在一般情况下，在量子poly(Dlog q)时间内运行。我们在曲线情形下的技术是使用Weil和Riemann-Roch边界采样哈希函数，以验证其雅可比群的阶数。对于高维簇，我们首先约化到曲面的情形，该曲面可纤维化为ℙ^1上超平面截面的Lefschetz铅笔。消失循环的形式体系及其固有的大单值群，使我们能够利用硬Lefschetz定理和Katz的等分布结果证明Deligne的"最大公因式定理"的有效版本。这些将我们的研究约化到计算定义在有限域扩张𝔽_Q/𝔽_q（具有多项式有界次数）上曲线的zeta函数。该理论的显式化给出了计算复杂度的第一个非平凡上界。
This article concerns the computational complexity of a fundamental problem in number theory: counting points on curves and surfaces over finite fields. There is no subexponential-time algorithm known and it is unclear if it can be NP-hard. Given a curve, we present the first efficient Arthur-Merlin protocol to certify its point-count, its Jacobian group structure, and its Hasse-Weil zeta function. We extend this result to a smooth projective surface to certify the factor P_1(T), corresponding t...