{
  "id": "1706.01941",
  "version": "v1",
  "published": "2017-06-06T19:42:19.000Z",
  "updated": "2017-06-06T19:42:19.000Z",
  "title": "Upper bounds on the smallest size of a complete cap in $\\mathrm{PG}(N,q)$, $N\\ge3$, under a certain probabilistic conjecture",
  "authors": [
    "Alexander A. Davydov",
    "Giorgio Faina",
    "Stefano Marcugini",
    "Fernanda Pambianco"
  ],
  "comment": "22 pages, 42 references, 3 figures",
  "categories": [
    "math.CO",
    "cs.IT",
    "math.IT"
  ],
  "abstract": "In the projective space $\\mathrm{PG}(N,q)$ over the Galois field of order $q$, $N\\ge3$, an iterative step-by-step construction of complete caps by adding a new point on every step is considered. It is proved that uncovered points are evenly placed on the space. A natural conjecture on an estimate of the number of new covered points on every step is done. For a part of the iterative process, this estimate is proved rigorously. Under the conjecture mentioned, new upper bounds on the smallest size $t_{2}(N,q)$ of a complete cap in $\\mathrm{PG}(N,q)$ are obtained, in particular, \\begin{align*} t_{2}(N,q)<\\frac{\\sqrt{q^{N+1}}}{q-1}\\left(\\sqrt{(N+1)\\ln q}+1\\right)+2\\thicksim q^\\frac{N-1}{2}\\sqrt{(N+1)\\ln q},\\quad N\\ge3. \\end{align*} A connection with the Birthday problem is noted. The effectiveness of the new bounds is illustrated by comparison with sizes of complete caps obtained by computer in wide regions of $q$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2017-06-06T19:42:19.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "51E21",
      "51E22",
      "94B05"
    ],
    "keywords": [
      "complete cap",
      "upper bounds",
      "smallest size",
      "probabilistic conjecture",
      "iterative step-by-step construction"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 22,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}