New covering codes of radius $R$, codimension $tR$ and $tR+\frac{R}{2}$, and saturating sets in projective spaces

The length function $\ell_q(r,R)$ is the smallest length of a $ q $-ary linear code of codimension $r$ and covering radius $R$. In this work we obtain new constructive upper bounds on $\ell_q(r,R)$ for all $R\ge4$, $r=tR$, $t\ge2$, and also for all even $R\ge2$, $r=tR+\frac{R}{2}$, $t\ge1$. The new bounds are provided by infinite families of new covering codes with fixed $R$ and increasing codimension. The new bounds improve upon the known ones. We propose a general regular construction (called ``Line+Ovals'') of a minimal $\rho$-saturating $((\rho+1)q+1)$-set in the projective space $\mathrm{PG}(2\rho+1,q)$ for all $\rho\ge0$. Such a set corresponds to an $[Rq+1,Rq+1-2R,3]_qR$ locally optimal$^1$ code of covering radius $R=\rho+1$. Basing on combinatorial properties of these codes regarding to spherical capsules$^1$, we give constructions for code codimension lifting and obtain infinite families of new surface-covering$^1$ codes with codimension $r=tR$, $t\ge2$. In addition, we obtain new 1-saturating sets in the projective plane $\mathrm{PG}(2,q^2)$ and, basing on them, construct infinite code families with fixed even radius $R\ge2$ and codimension $r=tR+\frac{R}{2}$, $t\ge1$. ($^1$ see the definitions in Section 1)

Abstract. The length function ℓ q (r, R) is the smallest length of a q-ary linear code of codimension r and covering radius R. In this work we obtain new constructive upper bounds on ℓ q (r, R) for all R ≥ 4 and r = tR with integer t ≥ 2, and also for all even R ≥ 2 and r = tR + R 2 with integer t ≥ 1. The new bounds are provided by new infinite families of covering codes with fixed R and growing codimension. The new bounds improve upon the known ones.
We propose a general regular construction (called "Line-Ovals") of a minimal ρ-saturating ((ρ + 1)q + 1)-set in the projective space PG(2ρ + 1, q) for all ρ ≥ 0. Such a set corresponds to an [Rq + 1, Rq + 1 − 2R] q R locally optimal 1 code of covering radius R = ρ + 1. In these codes, we investigate combinatorial properties regarding to spherical capsules (including the property to be a surface-covering code 1 ) and give corresponding constructions for code codimension lifting. Using the new codes as starting points in these constructions we obtained the desired infinite code families with growing r = tR.
In addition, we obtain new 1-saturating sets in the projective plane PG(2, q 2 ) and, founding on them, construct infinite code families with fixed even radius R ≥ 2 and growing codimension r = tR + R 2 , t ≥ 1.

Covering codes. The length function
Let F q be the Galois field with q elements, F * q = F q \ {0}. Let F n q be the n-dimensional vector space over F q . Denote by [n, n − r] q a q-ary linear code of length n and codimension (redundancy) r, that is a subspace of F n q of dimension n − r. The sphere of radius R with center c in F n q is the set {v : v ∈ F n q , d(v, c) ≤ R} where d(v, c) is the Hamming distance between the vectors v and c. Definition 1.1. (i) The covering radius of a linear [n, n − r] q code is the least integer R such that the space F n q is covered by the spheres of radius R centered at the codewords. (ii) A linear [n, n − r] q code has covering radius R if every column of F r q is equal to a linear combination of at most R columns of a parity check matrix of the code, and R is the smallest value with this property. Definitions 1.1(i) and 1.1(ii) are equivalent. Let an [n, n − r] q R code be an [n, n − r] q code of covering radius R. An [n, n − r] q R code of minimum distance d is denoted by [n, n − r, d] q R code. For an introduction to coverings of vector Hamming spaces over finite fields, see [5,7].
The covering density µ of an [n, n − r] q R-code is defined as the ratio of the total volume of all q n−r spheres of radius R centered at the codewords to the volume q n of the space F n q . By Definition 1.1(i), we have µ ≥ 1. In the other words, The covering quality of a code is better if its covering density is smaller. For fixed q, r, R, the covering density of an [n, n − r] q R code decreases with decreasing n. Codes investigated from the point of view of the covering quality are usually called covering codes [7]; see an online bibliography [28], works [5, 9-14, 17-20, 26, 27], and the references therein. Definition 1.2. [5,7] The length function ℓ q (r, R) is the smallest length of a q-ary linear code of codimension r and covering radius R.
From (1.1), see also Definition 1.1(ii), one obtains an implicit lower bound on ℓ q (r, R): In particular, for R = 1 we have ℓ q (r, 1) ≥ q r −1 q−1 . This means that the perfect Hamming code achieves the bound and has the covering density equal to one. The same is true for the perfect Golay codes [23,12,7] 2 3 and [11, 6, 5] 3 2. In the general case, note that the main term of the sum in (1.2) is (q − 1) R ℓq(r,R) R . If n is considerable larger than R (this is the natural situation in covering codes investigations) and if q is large enough, we have and, in a more general form, where c is independent of q but it is possible that c depends on r and R. Let t, s, R * be integers. Let q ′ be a prime power. In [11,13,14,17], see also the references therein, for the situations (i) r = tR, arbitrary q, (1.4) (ii) R = sR * , r = tR + s, q = (q ′ ) R * , [n, n − r] q R covering codes are obtained with lengths of the form n = c 1 (r, R)q (r−R)/R + i≥2 c i (r, R)q (r−R)/R−µ i , c 1 (r, R) > 1, µ i > 0, (1.5) where all c i (r, R) are constants independent of q. Also, for i ≥ 2, one usually has c i (r, R) ≥ 0, but it is possible that c i (r, R) < 0, see for example Propositions 1.6 and 1.7. For growing q, code length n of (1.5) is close (by order) to the bound (1.3) since all µ i > 0.
In this work, we consider the case (i) of (1.4) for R ≥ 4 and the situation (ii) for even R with R * = 2. We briefly describe the known results and then improve upon many of them by constructing new codes.
For new codes with r = tR we note and use interesting and useful combinatorial properties connected with the locally optimality, R, ℓ-capsules and R, ℓ-objects. Definition 1.3. [12] A linear covering code is called locally optimal if one cannot remove any column from its parity check matrix without increase in covering radius. A locally optimal code can be called also non-shortening in the sense mentioned.  [14,Sect,2] Let 0 ≤ ℓ ≤ R. A linear [n, n − r] q R code of covering radius R is called an R, ℓ-object and is denoted as an [n, n − r] q R, ℓ code if any of following holds.
(i) The space F n q is covered by the R, ℓ-capsules centered at the codewords. (ii) Every column of the space F r q (including the zero column) is equal to a linear combination with nonzero coefficients of at least ℓ and at most R distinct columns of a parity-check matrix of the code.
(iii) Every coset of the code (including the code itself) contains a weight w word of the space F n q such that ℓ ≤ w ≤ R. Definitions 1.4(i), 1.4(ii), and 1.4(iii) are equivalent. In [9,10,14] widened definitions of R, ℓ-objects are considered. But for this work, Definition 1.4 is sufficient.
Note that the R, R-capsule is the surface of the sphere of radius R.
Definition 1.5. An [n, n − r] q R, R code is called surface-covering code of radius R.
The value of ℓ is important for code codimension lifting constructions, see Section 4.

The known results
Codes with radius R = 2, 3 and codimension r = tR are widely investigated for arbitrary q, see [11], [14,Sects. 4,5], [17,Ths. 9,12]. At the same time, codes with R ≥ 4 and r = tR are investigated insufficiently; moreover, the known results on these codes are obtained by use of codes with R = 2, 3 in the so-called direct sum construction [14,Sect. 4.2]. The following results on codes with R ≥ 4 and r = tR are described in the literature.

Saturating sets in projective spaces
Effective methods to obtain upper bounds on ℓ q (r, R) are connected with saturating sets in projective spaces. Let PG(N, q) be the N-dimensional projective space over the field F q ; see [21][22][23] for an introduction to the projective spaces over finite fields, see also [19,22,26,27] for connections between coding theory and Galois geometries.
is ρ-saturating if for any point A of PG(N, q) \ S there exist ρ + 1 points in S generating a subspace of PG(N, q) containing A, and ρ is the smallest value with such property.
Note that for n < (ρ + 1)q + 1 = Rq + 1, no examples of ρ-saturating n-sets in PG(2ρ + 1, q) (resp. [n, n − 2R] q R codes with R = ρ + 1) seem to be known. Moreover, in [14,Prop. 4.2], it is proved that ℓ 4 (4, 2) = s 4 (3, 1) = 2 · 4 + 1. This strengthens the interest to Problem 2 and gives rise to the following.  If the positions of a column of a parity check matrix of an [n, n − r] q R locally optimal code are considered as homogeneous coordinates of a point in PG(r −1, q) then this parity check matrix defines a minimal (R − 1)-saturating n-set in PG(r − 1, q) [12]. So, there is a a one-to-one correspondence between [n, n − r] q R locally optimal codes and minimal (R − 1)-saturating n-sets in PG(r − 1, q).
Note that the codes providing the bounds of Proposition 1.7 are based on 1-saturating sets in the projective plane of square order. Improvements of these bounds could be connected with new 1-saturating sets of relatively small sizes.
Problem 4. In PG(2, q 2 ), construct new 1-saturating sets with sizes smaller than the known ones.

The goals and the structure of the paper
The goals of this paper: • solve Problem 2 and with the help of the new [Rq + 1, Rq + 1 − 2R] q R codes solve Problem 1(i) regarding codes of covering radius R ≥ 4 and codimension tR; • solve Problem 4 and with the help of the new 1-saturating sets solve Problem 1(ii) regarding codes with even covering radius R ≥ 2 and codimension tR + R 2 . The paper is organized as follows. In Section 2 we collect the main results of the paper. In Section 3, we propose a construction "line plus ρ ovals" for ρ-saturating sets in PG(2ρ+ 1, q) and codes of codimension 2R. This solves Problem 2. In Section 4, we describe two constructions from the family of the so-called "q m -concatenating constructions" for code codimension lifting. The constructions are convenient for [n, n − r] q R, ℓ codes with ℓ ∈ {R − 1, R}. In Section 5, we prove that the codes obtained in Section 3 have ℓ = R for odd q and ℓ = R − 1 for even q. (So, for odd q we have surface-covering codes.) Then we use these codes as starting ones for the constructions of Section 4. As the result, we obtained new infinite code families with fixed radius R ≥ 4 and growing codimension tR. This solves Problem 1(i) for the most part. In Section 6, using recent results on double blocking set, we obtain new 1-saturating sets in PG(2, q 2 ) that solve in part Problem 4. Then basing on these sets, we obtain new infinite code families for all fixed even radii R ≥ 2 and growing codimension tR + R 2 . This solves in part Problem 1(ii).
• Problem 1(i) is solved for the most part, see Sections 4 and 5. We described two constructions for code codimension lifting. Using the [Rq + 1, Rq + 1 − 2R] q R codes as a start for these constructions, we obtained infinite code families with fixed radius R ≥ 4 and growing codimension tR. These families improve the known results collected in Proposition 1.6 apart from t = 3. New bounds on the length function obtained in this paper are given in Theorem 2.1 based on Theorems 3.8, 3.10, 5.3, 5.4.
Theorem 2.1. Let t be a growing integer. For the length function ℓ q (r, R) and for the smallest size s q (r −1, R −1) of a (R −1)-saturating set in the projective space PG(r −1, q) the following constructive upper bounds (provided by infinite families of codes) hold: The new bounds of Theorem 2.1 are better than the known ones of Proposition 1.6. In particular, in Proposition 1.6, the coefficient for q (r−2R)/R is R 3 , whereas in Theorem 2.1 it is equal to 1 or 2, see (i)-(iii) and (iv)-(v), respectively. Note that in the cases (iv)-(v), the coefficient is equal to 2 since the term with j = 2 of the sum in ∆ q (r, R) is q (r−2R)/R .
• Problem 4 is solved in part, see Section 6. Throughout the paper we use the following notation: In Theorem 6.3(v),(vi), using recent results on double blocking set, it is shown that in PG(2, q) there are 1-saturating sets of the following sizes: The new 1-saturating sets have smaller sizes than the known ones, see Remark 6.4.
• Problem 1(ii) is solved in part, see Section 6. Using the new 1-saturating sets in P G(2, q), we obtained infinite families of codes with covering radius R = 2, see Theorem 6.9, and, basing on them, we constructed infinite code families with fixed even radius R ≥ 2 and growing codimension tR + R 2 , see Theorem 6.11 that gives rise to Theorem 2.2. Theorem 2.2. Assume that p is prime, q = p 2η , η ≥ 2, covering radius R ≥ 2 is even, and code codimension is be as in (2.1), (2.2). The following constructive upper bounds on the length function (provided by infinite families of codes with growing codimension) hold: 3 Construction "Line-Ovals" for ρ-saturating sets in PG(2ρ + 1, q) and codes of codimension 2R Notation. Throughout the paper we denote by x i , i = 0, 1, . . . , N, the homogeneous coordinates of points of P G(N, q). In the other words, a point ( The leftmost nonzero coordinate is equal to 1. In general, by default, Also, we can write explicit values 0,1 for some coordinates or denote coordinates by letters values of which is explained later.

The construction
Let F q = {a 1 = 0, a 2 , . . . , a q } be the Galois field of order q. Let F * q = F q \ {0} = {a 2 , . . . , a q }. Denote Σ ρ = PG(2ρ + 1, q). Let Σ u be the (2u + 1)-subspace of Σ ρ such that In Σ u , let π u be the plane such that In π u , let A 0 u and A ∞ u be the points of the form In π u , let C u and C * u be the conic and the truncated one, respectively, of the form Let T u be the nucleus of C u , if q is even, or the intersection of the tangents to C u in A 0 Also, let L 0 and L * 0 be the line and the truncated one, respectively, such that Construction S. ("Line-Ovals") Let ρ ≥ 0. Let S ρ be a point ((ρ + 1)q + 1)-subset of Σ ρ . Let P j be the j-th point of S ρ , j = 1, 2, . . . , (ρ + 1)q + 1. We construct S ρ as follows: The points P j of S ρ have the form

Saturation of Construction S for
Note that by Definition 1.8, a 0-saturating set in P G(N, q) is the whole space.
The following proposition is obvious.
If q is even, every point of a plane outside of a hyperoval C u ∪ {T u } lies on (q + 2)/2 its bisecants. If q is odd, every point of a plane outside of a conic C u lies on at least (q − 1)/2 its bisecants. At most two of aforementioned bisecants will be removed if The proof is similar to the case (i) taking into account that here we remove only one point A 0 ρ from C ρ .
Proof. (i) By Proposition 3.3(iii) and Lemma 3.4, Σ 0 (points (x 0 x 1 00)) and π 1 (points (0x 1 x 2 x 3 )) are 1-covered by So, we should consider points of the form We show that B in (3.5) is a linear combination of at most 2 points of S 1 .
From (3.9)-(3.12) we see that all points of S 2 \ S 1 are 2-essential. Also, we take into account that S 1 is a minimal 1-saturating set.
(i) By Propositions 3.3, 3.6, 3.7, Lemmas 3.4, 3.5, and Assumption, we have the following: So, we should consider points of the form (3.14) We show that B in (3.14) is a linear combination of at most Γ + 1 points of . By the hypothesis and by (3.13), 2) Let (x 0 . . .
From (3.15)-(3. 19) we see that all the points of S Γ \ S Υ are Γ-essential. Also, we take into account that S Υ is a minimal Υ-saturating set.

Codes of covering radius R and codimension 2R
In the coding theory language, the results of this section give the following theorem.
Theorem 3.10. Let V ρ be the code such that the columns of its parity check matrix are the points (in the homogeneous coordinates) of the ρ-saturating ((ρ + 1)q + 1)-set S ρ of Construction S (3.1), (3.2).
Proof. We use Theorem 3.8 and Proposition 3.9. The code V ρ is locally optimal as the corresponding ρ-saturating set S ρ is minimal. Minimum distance d = 3 is due to L * 0 .

The q m -concatenating constructions for code codimension lifting
The q m -concatenating constructions are proposed in [9] and are developed in [10-12, 14, 17,18], see also [5], [7,Sec. 5.4] and the references in these works. By using a starting code as a "seed", a q m -concatenating construction yields an infinite family of new codes with a fixed covering radius, growing codimension and with almost the same covering density. We give versions of the q m -concatenating constructions convenient for our goals. Several other versions of such constructions can be found in [9][10][11][12]14,17,18] and the references therein. In Construction QM 1 below, we use a surface-covering code as a starting one, whereas for Construction QM 2 we need to start with an [n, n − r] q R, ℓ code, ℓ = R − 1. Resulting codes of both the constructions are surface-covering.
Construction QM 1 . Let columns h j belong to F r 0 q and let H 0 = [h 1 h 2 . . . h n 0 ] be a parity check matrix of an [n 0 , n 0 − r 0 ] q R, R starting surface-covering code V 0 with R ≥ 2. Let m ≥ 1 be an integer such that q m ≥ n 0 − 1. To each column h j we associate an element where B j is an (r 0 + Rm) × q m matrix, 0 is the zero element of F q m , ξ u is an element of F q m , {ξ 1 , ξ 2 , . . . , ξ q m } = F q m . An element of F q m written in B j denotes an m-dimensional q-ary column vector that is a q-ary representation of this element.
Theorem 4.1. In Construction QM 1 , the new code V with the parity check matrix (4.1), (4.2) is an [n, n − (r 0 + Rm), 3] q R, R surface-covering code with covering radius R and length n = q m n 0 . Moreover, if the starting code V 0 is locally optimal (non-shortening), then the new code V is locally optimal too.
Proof. The length of the code V directly follows from the construction.
The minimum distance d is equal to 3 since for any pair of columns b j (ξ u 1 ), b j (ξ u 2 ) of B j , a 3-rd one can be found such that the column triple corresponds to a codeword of weight 3. Take a, b, c ∈ F * q with a + b + c = 0. Put ξ u 3 = (−aξ u 1 − bξ u 2 )/c. Then for all j we have where 0 is the zero (r 0 + Rm)-positional column. We show that covering radius R V of V is equal to R.
Since V 0 is an [n 0 , n 0 − r 0 ] q R, R code, there exists a linear combination of the form where values of x k are obtained from the linear system with nonzero determinant. If for j k in (4.4) we have β j k ∈ F q m for all k, then the system has the form As usual, we put 0 0 = 1. If in (4.4) we have, for example, β j R = * , then the system is as follows: If V 0 is a locally optimal code, then every column h j of H 0 takes part in a representation of the form (4.4). If we remove b j k (ξ u ) from B j k then there is (s 1 , s 2 , . . . , s Rm ) such that the system (4.6) or (4.7) gives x k = ξ u . As a result, for some t the representation (4.5) becomes impossible. So, all columns of H V are essential and the code V is locally optimal.
Construction QM 2 . Let θ m,q = q m+1 −1 q−1 . Let columns h j belong to F r 0 q and let H 0 = [h 1 h 2 . . . h n 0 ] be a parity check matrix of an [n 0 , n 0 − r 0 ] q R, ℓ 0 starting code V 0 with ℓ 0 = R − 1, R ≥ 2. Let m ≥ 1 be an integer such that q m ≥ n 0 . To each column h j we associate an element β j ∈ F q m so that β i = β j if i = j. Let a new code V be the [n, n − (r 0 + Rm)] q R V , ℓ V code with n = q m n 0 + θ m,q and parity check matrix of the form where B j is an (r 0 + Rm) × q m matrix as in (4.2), C is an (r 0 + Rm) × θ m,q matrix,  is an [n, n − (r 0 + Rm), 3] q R, R surface-covering code with covering radius R and length n = q m n 0 + q m+1 −1 q−1 . Moreover, if the starting code V 0 is locally optimal (non-shortening), then the new code V is locally optimal too.
Proof. The length of the code V directly follows from the construction.
The minimum distance is equal to 3 as the Hamming code is a code with d = 3. Also we can use (4.3) from the proof of Theorem 4.1.
We show that covering radius R V of V is equal to R.
Since V 0 is an [n 0 , n 0 − r 0 ] q R, ℓ 0 code with ℓ 0 = R − 1, there exists a linear combination of ϕ(f) distinct columns of H 0 of the form see Definition 1.4. If ϕ(f) = R we act similarly to the proof of Theorem 4.1.
Let ϕ(f) = R − 1. We represent t as a linear combination (with nonzero coefficients) of at most R distinct columns of H V . We have, see (4.2), (4.9), where c is a column of C and η = 0 means that the summand ηc is absent. Also, in (4.10), values of x k are obtained from the linear system with nonzero determinant. Finally, in (4.10), c = (0w) where 0 is the zero (r 0 +(R−1)m)positional column and w is a column of W m that satisfies the equality the needed column ηw always exists as the Hamming code has covering radius 1. Now we show that V is an [n, n − (r 0 + Rm), 3] q R, R code, i.e. ℓ V = R. The critical situation is when in (4.10) and (4.11) η = 0, i.e. the summand ηc is absent. We use the approach of the proof of Theorem 4.1 regarding (4.3). In (4.3) we put j = j 1 , ξ u 1 = x 1 , a = −c 1 with j 1 , x 1 , c 1 taken from (4.10). Then Thus, we always can represent t ∈ F r 0 +Rm q as a linear combination with nonzero coefficients of exactly R columns of H V .
By above, if we remove any column of H V , some representation of t becomes impossible. So, all columns of H V are essential and the code V is locally optimal.

New infinite code families with fixed radius R ≥ 4 and growing codimension tR
In the minimal ρ-saturating set of Construction S (3.1), (3.2), we consider a point P j (in the homogeneous coordinates) as a column h j of the parity check matrix H ρ that defines the [qR + 1, qR + 1 − 2R, 3] q R, ℓ locally optimal code V ρ of covering radius R = ρ + 1.
We consider some properties of H ρ useful to estimate ℓ. Let f ∈ F r q . Let J (f) = {h j 1 , . . . , h j β } and I w = {h i 1 , . . . , h iw } be sets of distinct columns of H ρ such that f = β k=1 c k h j k , h j k ∈ J (f) and c k ∈ F * q for all k; (5.1) w k=1 m k h i k = 0, h i k ∈ I w and m k ∈ F * q for all k, 0 ∈ F r q is the zero column; Note that I w is a set of columns corresponding to a weight w codeword of V ρ . In the representation (5.3), the number of distinct columns of H ρ , say β new , depends on the intersection I w ∩J (f) and the values of nonzero coefficients c k , m k , µ. For example, To use (5.3), (5.4), note that submatrices of H ρ can be treated as parity check matrices of codes; we call them component codes and write in Table 1, where u = 1, . . . , ρ, "MDS" notes a minimum distance separable code and "AMDS" says on an Almost MDS code.

AMDS
Remark 5.1. The weight spectrum of MDS codes is known, see e.g. [29]. In particular, in [n, n − r, d] q MDS code any d columns of a parity check matrix correspond to a weight d codeword. If q odd, for AMDS component codes C T u and C ∞T ρ we note that T u lies on two tangents to C u (in A 0 u , A ∞ u ) and on q−1 2 bisecants of C * u . Every of these bisecants gives rise to a weight 3 codeword. The (q − 1)-set of points of C * u is partitioned by q−1 2 point pairs; every pair forms a bisecant through T u .
Note that from the proofs of Section 3 it can be seen that for the representation of a column f ∈ F r q it is sufficient to use (for every u) at most 3 columns corresponding to C * u . Similarly, one can use 2 columns corresponding to {A 0 0 } ∪ L * 0 . Therefore, if q ≥ 7 we have in {A 0 0 } ∪ L * 0 and in every C * u several points (columns) that can be used to form sets I w useful to increase β and β new in (5.2)- (5.4).
Assume that for a column f ∈ F r q we have the representation (5.1) with 1 ≤ β < R. Then using weight w codewords of the component codes we can increase β by w, w − 1, w − 2, see (5.4). The increase by w − 1, w − 2 is possible if some column of J (f) and I w corresponds to the same component code. In particular, the situations with w = 3, w − 2 = 1 can be provided if some column or a column pair of J (f) and I w correspond to the same code L 0 (for all q) or to the same code C T u , C ∞T ρ (for q odd). There exist columns f ∈ F r q such that L 0 is not used for their representation. Therefore, in general, for even q (where MDS codes C T u , C ∞T ρ have minimum distance d = 4) we are not able to do β new = R when β = R − 1, see (5.3), (5.4). In the other side, for odd q, AMDS codes C T u , C ∞T ρ have d = 3 that allows us to increase β by w − 2 = 1. Note also, see Remark 5.1, that for q ≥ 7 the structure of minimum weight codewords in the component codes provides the situation that some columns of J (f) and I w correspond to the same code.
By above, we have the following lemma. In Theorems 5.3 and 5.4 we consider R ≥ 4 since for R = 1, 2, 3, several short covering codes with r = tR are given in detail in [11,13,14,16,17] and the references therein. Theorem 5.3. Let q ≥ 7 be odd. Let t be an integer. Then for all R ≥ 4 there is an infinite family of [n, n − r, 3] q R, R locally optimal surface-covering codes with the parameters n = Rq (r−R)/R + q (r−2R)/R , r = tR, t = 2 and t ≥ ⌈log q R⌉ + 3.
6 New infinite code families with fixed even radius R ≥ 2 and growing codimension tR + R

2
In the projective plane PG(2, q), a blocking (resp. double blocking) set S is a set of points such that every line of PG(2, q) contains at least one (resp. two) points of S. There is an useful connection between double blocking sets and 1-saturating sets.  [25] Let q be a square. Any double blocking set in the subplane PG(2, √ q ) ⊂ PG(2, q) is a 1-saturating set in the plane PG(2, q).
Note also that if q = p 2 , i.e. η = 1, then the size (i) is the smallest in Theorem 6.3. It is why we pay attention to this case, see Remarks 6.5-6.7 and Problem 5 below.
Remark 6.5. Let a point of PG(2, q) have the form (x 0 , x 1 , x 2 ) where x i ∈ F q , the leftmost nonzero coordinate is equal to 1. Let β be a primitive element of F q .
Proof. Let n q be the size of the 1-saturating sets of Theorem 6.3(iii),(iv). We treat every point (in homogeneous coordinates) of the set as a column of an 3×n q parity check matrix of an [n q , n q − 3] q 2 code. For these codes it can be shown that n q < q and q + 1 ≥ 2n q . Then we use Proposition 6.8.
The direct sum construction [14,Sect. 4.2] gives the following lemma.