Further results on covering codes with radius R and codimension tR + 1

The length function ${\mathrm{\ell }}_q(r,R)$ is the smallest possible length $n$ of a $q$-ary linear $[n,n-r{]}_{q}R$ 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{P}\mathrm{G}(N,q)$. There is a one-to-one correspondence between $[n,n-r{]}_{q}R$ codes and $(R-1)$-saturating $n$-sets in $\mathrm{P}\mathrm{G}(r-1,q)$ that implies ${\mathrm{\ell }}_q(r,R)=s_q(r-1,R-1)$. In this work, for $R\ge 3$, new asymptotic upper bounds on ${\mathrm{\ell }}_q(tR+1,R)$ are obtained in the following form: $\bullet {\mathrm{\ell }}_q(tR+1,R)=s_q(tR,R-1)\le \sqrt[R]{\frac{R!}{R^{R-2}}}\cdot q^{(r-R)\mathrm{/}R}\cdot \sqrt[R]{\ln q}+o(q^{(r-R)\mathrm{/}R}),r=tR+1,t\ge 1,q\text{ is an arbitrary prime power},q\text{ is large enough};$ $\bullet \text{ if additionally }R\text{ is large enough, then }\sqrt[R]{\frac{R!}{R^{R-2}}}\sim \frac{1}{e}\approx \mathrm{0.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{P}\mathrm{G}(R,q)$, providing sets of small sizes, is proposed. The $[n,n-(R+1){]}_{q}R$ 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\ge 1$.