{
  "id": "2310.02715",
  "version": "v1",
  "published": "2023-10-04T10:30:48.000Z",
  "updated": "2023-10-04T10:30:48.000Z",
  "title": "Further results on covering codes with radius R and codimension tR + 1",
  "authors": [
    "Alexander A. Davydov",
    "Stefano Marcugini",
    "Fernanda Pambianco"
  ],
  "comment": "24 pages. arXiv admin note: text overlap with arXiv:2108.13609",
  "categories": [
    "math.CO"
  ],
  "abstract": "The length function $\\ell_q(r,R)$ is the smallest possible length $n$ of a $ q $-ary linear $[n,n-r]_qR$ code with codimension (redundancy) $r$ and covering radius $R$. Let $s_q(N,\\rho)$ be the smallest size of a $\\rho$-saturating set in the projective space $\\mathrm{PG}(N,q)$. There is a one-to-one correspondence between $[n,n-r]_qR$ codes and $(R-1)$-saturating $n$-sets in $\\mathrm{PG}(r-1,q)$ that implies $\\ell_q(r,R)=s_q(r-1,R-1)$. In this work, for $R\\ge3$, new asymptotic upper bounds on $\\ell_q(tR+1,R)$ are obtained in the following form: $\\hspace{0.7cm} \\bullet~\\ell_q(tR+1,R) =s_q(tR,R-1)\\le \\sqrt[R]{\\frac{R!}{R^{R-2}}}\\cdot q^{(r-R)/R}\\cdot\\sqrt[R]{\\ln q}+o(q^{(r-R)/R}), \\hspace{0.3cm}r=tR+1,~t\\ge1,~ q\\text{ is an arbitrary prime power},~q\\text{ is large enough};$ $\\hspace{0.7cm} \\bullet~\\text{ if additionally }R\\text{ is large enough, then }\\sqrt[R]{\\frac{R!}{R^{R-2}}}\\thicksim\\frac{1}{e}\\thickapprox0.3679. $ The new bounds are essentially better than the known ones. For $t=1$, a new construction of $(R-1)$-saturating sets in the projective space $\\mathrm{PG}(R,q)$, providing sets of small sizes, is proposed. The $[n,n-(R+1)]_qR$ codes, obtained by the construction, have minimum distance $R + 1$, i.e. they are almost MDS (AMDS) codes. These codes are taken as the starting ones in the lift-constructions (so-called ``$q^m$-concatenating constructions'') for covering codes to obtain infinite families of codes with growing codimension $r=tR+1$, $t\\ge1$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2023-10-04T10:30:48.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "94B05",
      "51E21",
      "51E22"
    ],
    "keywords": [
      "covering codes",
      "codimension tr",
      "saturating set",
      "projective space",
      "asymptotic upper bounds"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 24,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}