{
  "id": "2007.13214",
  "version": "v1",
  "published": "2020-07-26T20:38:10.000Z",
  "updated": "2020-07-26T20:38:10.000Z",
  "title": "Computing zeta functions of large polynomial systems over finite fields",
  "authors": [
    "Qi Cheng",
    "J. Maurice Rojas",
    "Daqing Wan"
  ],
  "categories": [
    "math.NT",
    "cs.CC"
  ],
  "abstract": "In this paper, we improve the algorithms of Lauder-Wan \\cite{LW} and Harvey \\cite{Ha} to compute the zeta function of a system of $m$ polynomial equations in $n$ variables over the finite field $\\FF_q$ of $q$ elements, for $m$ large. The dependence on $m$ in the original algorithms was exponential in $m$. Our main result is a reduction of the exponential dependence on $m$ to a polynomial dependence on $m$. As an application, we speed up a doubly exponential time algorithm from a software verification paper \\cite{BJK} (on universal equivalence of programs over finite fields) to singly exponential time. One key new ingredient is an effective version of the classical Kronecker theorem which (set-theoretically) reduces the number of defining equations for a \"large\" polynomial system over $\\FF_q$ when $q$ is suitably large.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2020-07-26T20:38:10.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "finite field",
      "large polynomial systems",
      "computing zeta functions",
      "doubly exponential time algorithm",
      "software verification paper"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}