{
  "id": "2208.09890",
  "version": "v1",
  "published": "2022-08-21T14:24:05.000Z",
  "updated": "2022-08-21T14:24:05.000Z",
  "title": "Counting points on smooth plane quartics",
  "authors": [
    "Edgar Costa",
    "David Harvey",
    "Andrew V. Sutherland"
  ],
  "comment": "32 pages",
  "categories": [
    "math.NT"
  ],
  "abstract": "We present efficient algorithms for counting points on a smooth plane quartic curve $X$ modulo a prime $p$. We address both the case where $X$ is defined over $\\mathbb F_p$ and the case where $X$ is defined over $\\mathbb Q$ and $p$ is a prime of good reduction. We consider two approaches for computing $\\#X(\\mathbb F_p)$, one which runs in $O(p\\log p\\log\\log p)$ time using $O(\\log p)$ space and one which runs in $O(p^{1/2}\\log^2\\!p)$ time using $O(p^{1/2}\\log p)$ space. Both approaches yield algorithms that are faster in practice than existing methods. We also present average polynomial-time algorithms for $X/\\mathbb Q$ that compute $\\#X(\\mathbb F_p)$ for good primes $p\\le N$ in $O(N\\log^3\\! N)$ time using $O(N)$ space. These are the first practical implementations of average polynomial-time algorithms for curves that are not cyclic covers of $\\mathbb P^1$, which in combination with previous results addresses all curves of genus $g\\le 3$. Our algorithms also compute Cartier-Manin/Hasse-Witt matrices that may be of independent interest.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2022-08-21T14:24:05.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "11G40",
      "14G10",
      "14H25",
      "11Y16"
    ],
    "keywords": [
      "counting points",
      "average polynomial-time algorithms",
      "smooth plane quartic curve",
      "approaches yield algorithms",
      "efficient algorithms"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 32,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}