new

Get trending papers in your email inbox!

Subscribe

Daily Papers

byAK and the research community

Apr 29

Complexity of counting points on curves and the factor P_1(T) of the zeta function of surfaces

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 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(Dlog 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 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 F_{Q}/F_{q} of poly-bounded degree. This explicitization of the theory yields the first nontrivial upper bounds on the computational complexity.

  • 3 authors
·
Nov 4, 2025

Tessellations and Speiser graphs arising from meromorphic functions on simply connected Riemann surfaces

Motivated by W. P. Thurston, we ask: What is the shape of a meromorphic function on a simply connected Riemann surface Ω_z? We consider Speiser functions, i.e. meromorphic functions on a simply connected Riemann surface, that have a finite number q at least 2 of singular (critical or asymptotic) values. As a first result, we make precise the correspondence between: Speiser functions w(z), Speiser Riemann surfaces R_w(z), Speiser q-tessellation, and analytic Speiser graphs of index q. As the second main result, we characterize tessellations with alternating colors (equivalently abstract pre-Speiser graphs) that are realized by Speiser functions on Ω_z. The characterization is in terms of the q-regular extension problem of bipartite planar graphs. As third main results, the Speiser Riemann surface R_w(z) can be constructed by isometric glueing of a finite number of types of sheets, where each sheet is a maximal domain of single-valuedness of the inverse of w(z). Furthermore, a unique decomposition of R_w(z) into maximal logarithmic towers and a soul is provided. Using vector fields we recognize that logarithmic towers come in two flavors: exponential or h-tangent blocks, directly related to the exponential or the hyperbolic tangent functions on the upper half plane. The surface R_w(z) of a finite Speiser function is characterized by surgery of a rational block and a finite number of exponential or h-tangent blocks.

  • 2 authors
·
Jan 30