New bounds for covering codes of radius 3 and codimension 3t+1

The smallest possible length of a $q$-ary linear code of covering radius $R$ and codimension (redundancy) $r$ is called the length function and is denoted by ${\mathrm{\ell }}_q(r,R)$. In this work, for $q$ \emph{an arbitrary prime power}, we obtain the following new constructive upper bounds on ${\mathrm{\ell }}_q(3t+1,3)$: ${\mathrm{\ell }}_q(r,3)⪅\sqrt[3]{k}\cdot q^{(r-3)\mathrm{/}3}\cdot \sqrt[3]{\ln q},r=3t+1,t\ge 1,q\ge \lceil \mathcal{W}(k)\rceil ,18<k\le 20.339,\mathcal{W}(k)\text{ is a decreasing function of }k;$ ${\mathrm{\ell }}_q(r,3)⪅\sqrt[3]{18}\cdot q^{(r-3)\mathrm{/}3}\cdot \sqrt[3]{\ln q},r=3t+1,t\ge 1,q\text{ large enough}\mathrm{.}$ For $t=1$, we use a one-to-one correspondence between codes of covering radius 3 and codimension 4, and 2-saturating sets in the projective space $\mathrm{P}\mathrm{G}(3,q)$. A new construction providing sets of small size is proposed. The codes, obtained by geometrical methods, are taken as the starting ones in the lift-constructions (so-called ``$q^m$-concatenating constructions’') to obtain infinite families of codes with radius 3 and growing codimension $r=3t+1$, $t\ge 1$. The new bounds are essentially better than the known ones.