Official version here.
Preprint version: arXiv:1506.04478 [math.NT].
The defect of a curve over a finite field is the difference between the number of rational points on the curve and the Weil–Serre bound for the curve. We present a construction for producing genus-4 double covers of genus-2 curves over finite fields such that the defect of the double cover is not much more than the defect of the genus-2 curve. We give an algorithm that uses this construction to produce genus-4 curves with small defect. Heuristically, for large primes q, the algorithm is expected to produce a genus-4 curve over Fq with defect at most 4 in time q3/4, up to logarithmic factors.
As part of the analysis of the algorithm, we present a reinterpretation of results of Hayashida on the number of genus-2 curves whose Jacobians are isomorphic to the square of a given elliptic curve with complex multiplication by a maximal order. We show that a category of principal polarizations on the square of such an elliptic curve is equivalent to a category of right ideals in a certain quaternion algebra.
Soon, a Magma implementation of the algorithms in the paper will be made available here.