New bounds for linear codes of covering radius 3 and 2-saturating sets in projective spaces

摘要

The length function ?q(r,R) is the smallest length of a q-ary linear code of covering radius R and codimension (redundancy) r. In this paper, we obtained new upper bounds on ?q(r, 3), r = 3t+1 ≥ 4, and r = 3t+2 ≥ 5, t ≥ 1. For r = 4, 5 we use the one-to-one correspondence between [n, n ? r]qR codes and (R ? 1)-saturating sets (e.g. complete arcs) in the projective space PG(r ? 1, q). Then, with the help of lift-constructions increasing r, we obtain new upper bounds on ?q(3t + 1, 3), ?q(3t + 2, 3). In particular, we show thategin{equation*}egin{array}{l}ell_q (r,3) lt 2.7sqrt[3]{ln q}cdot q^{(r - 3)/3} ,,r = 3t + 1 ge 4,t ge 1,,q le 6553; ell_q (r,3) lt 2.9sqrt[3]{ln q}cdot q^{(r - 3)/3} ,,r = 3t + 2 ge 5,t ge 1,,q le 839. end{array}end{equation*}Also, in PG(3, q) we consider an iterative step-by-step construction of complete arcs and prove that uncovered points are evenly placed on the space. A natural conjecture on an estimate of the number of new covered points in every step is done. Under this conjecture, the following bounds for values of q, not limited from above, are proposed:egin{equation*}ell_q (r,3) lt 3sqrt[3]{ln q}cdot q^{(r - 3)/3} ,,r = 3t + 1 ge 4,,t ge 1.end{equation*}