Complexity of counting points on curves and the factor $P_1(T)$ of the zeta function of surfaces
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914134089531392 |
|---|---|
| author | Roy, Diptajit Saxena, Nitin Venkatesh, Madhavan |
| author_facet | Roy, Diptajit Saxena, Nitin Venkatesh, Madhavan |
| contents | 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 $\mathrm{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 to the first Betti number, of the zeta function; by using the counting oracle. We give the first algorithm to compute $P_{1}(T)$ that is poly($\log q$)-time if the degree $D$ of the input surface is fixed; and in quantum poly($D\log q$)-time in general.
Our technique in the curve case, is to sample hash functions using the Weil and Riemann-Roch bounds, to certify the group order of its Jacobian. For higher dimension varieties, we first reduce to the case of a surface, which is fibred as a Lefschetz pencil of hyperplane sections over $\mathbb{P}^{1}$. The formalism of vanishing cycles, and the inherent big monodromy, enable us to prove an effective version of Deligne's `theoreme du pgcd' using the hard-Lefschetz theorem and an equidistribution result due to Katz. These reduce our investigations to that of computing the zeta function of a curve, defined over a finite field extension $\mathbb{F}_{Q}/\mathbb{F}_{q}$ of poly-bounded degree. This explicitization of the theory yields the first nontrivial upper bounds on the computational complexity. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_02262 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Complexity of counting points on curves and the factor $P_1(T)$ of the zeta function of surfaces Roy, Diptajit Saxena, Nitin Venkatesh, Madhavan Computational Complexity Algebraic Geometry Number Theory 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 $\mathrm{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 to the first Betti number, of the zeta function; by using the counting oracle. We give the first algorithm to compute $P_{1}(T)$ that is poly($\log q$)-time if the degree $D$ of the input surface is fixed; and in quantum poly($D\log q$)-time in general. Our technique in the curve case, is to sample hash functions using the Weil and Riemann-Roch bounds, to certify the group order of its Jacobian. For higher dimension varieties, we first reduce to the case of a surface, which is fibred as a Lefschetz pencil of hyperplane sections over $\mathbb{P}^{1}$. The formalism of vanishing cycles, and the inherent big monodromy, enable us to prove an effective version of Deligne's `theoreme du pgcd' using the hard-Lefschetz theorem and an equidistribution result due to Katz. These reduce our investigations to that of computing the zeta function of a curve, defined over a finite field extension $\mathbb{F}_{Q}/\mathbb{F}_{q}$ of poly-bounded degree. This explicitization of the theory yields the first nontrivial upper bounds on the computational complexity. |
| title | Complexity of counting points on curves and the factor $P_1(T)$ of the zeta function of surfaces |
| topic | Computational Complexity Algebraic Geometry Number Theory |
| url | https://arxiv.org/abs/2511.02262 |