ISSN 2148-838Xhttp://dx.doi.org/10.13069/jacodesmath.427968 J. Algebra Comb. Discrete Appl. 5(2) • 101–116 Received: 18 May 2016 Accepted: 25 April 2018 Journal of Algebra Combinatorics Discrete Structures and Applications Non–existence of some 4–dimensional Griesmer codes over finite fields∗ Research Article Kazuki Kumegawa, Tatsuya Maruta Abstract: We prove the non–existence of [gq(4, d), 4, d]q codes for d = 2q3 − rq2 − 2q + 1 for 3 ≤ r ≤ (q + 1)/2, q ≥ 5; d = 2q3 − 3q2 − 3q + 1 for q ≥ 9; d = 2q3 − 4q2 − 3q + 1 for q ≥ 9; and d = q3 − q2 − rq − 2 with r = 4, 5 or 6 for q ≥ 9, where gq(4, d) = ∑3 i=0 ⌈ d/qi ⌉ . This yields that nq(4, d) = gq(4, d) + 1 for 2q3−3q2−3q+1 ≤ d ≤ 2q3−3q2, 2q3−5q2−2q+1 ≤ d ≤ 2q3−5q2 and q3−q2−rq−2 ≤ d ≤ q3−q2−rq with 4 ≤ r ≤ 6 for q ≥ 9 and that nq(4, d) ≥ gq(4, d) + 1 for 2q3 − rq2 − 2q + 1 ≤ d ≤ 2q3 − rq2 − q for 3 ≤ r ≤ (q + 1)/2, q ≥ 5 and 2q3 − 4q2 − 3q + 1 ≤ d ≤ 2q3 − 4q2 − 2q for q ≥ 9, where nq(4, d) denotes the minimum length n for which an [n, 4, d]q code exists. 2010 MSC: 94B05, 94B27, 51E20 Keywords: Optimal linear codes, Griesmer bound, Arcs in PG(r, q) 1. Introduction An [n,k,d]q code C is a linear code of length n, dimension k and minimum Hamming weight d over Fq, the field of q elements. A fundamental problem in coding theory is to find nq(k,d), the minimum length n for which an [n,k,d]q code exists. The Griesmer bound gives a lower bound on nq(k,d) as nq(k,d) ≥ gq(k,d) = k−1∑ i=0 ⌈ d/qi ⌉ , where dxe denotes the smallest integer ≥ x. An [n,k,d]q code is called Griesmer if n = gq(k,d). The values of nq(k,d) are determined for all d only for some small values of q and k, see [22]. For k = 4, ∗ This research was partially supported by JSPS KAKENHI Grant Number JP16K05256. Kazuki Kumegawa; Department of Mathematics and Information Sciences, Osaka Prefecture University, Sakai, Osaka 599-8531, Japan (email: hmjwj674@yahoo.co.jp). Tatsuya Maruta (Corresponding Author); Department of Mathematical Sciences, Osaka Prefecture University, Sakai, Osaka 599-8531, Japan (email: maruta@mi.s.osakafu-u.ac.jp). 101 https://orcid.org/0000-0001-7858-0787 K. Kumegawa, T. Maruta / J. Algebra Comb. Discrete Appl. 5(2) (2018) 101–116 the exact value of nq(4,d) is known for all d only for q = 2, 3, 4. Recently, one of the open cases for (q,k) = (5, 4) was solved in [16]. For general q, see [18] and [11] for known results on nq(4,d). We have recently proved the following. Theorem 1.1 ([12]). There exists no [gq(4,d), 4,d]q code for (1) d = q3/2 −q2 − 2q + 1 for q = 2h, h ≥ 3, (2) d = 2q3 − 3q2 − 2q + 1 for q ≥ 5, (3) d = 2q3 −rq2 −q + 1 for 3 ≤ r ≤ q −q/p, q = ph with p prime. As a continuation on the non–existence of Griesmer codes for k = 4, we prove the following four theorems. Theorem 1.2. There exists no [gq(4,d), 4,d]q code for d = 2q3 − rq2 − 2q + 1 for 3 ≤ r ≤ (q + 1)/2, q ≥ 5. Theorem 1.3. There exists no [gq(4,d), 4,d]q code for d = 2q3 − 3q2 − 3q + 1 for q ≥ 9. Theorem 1.4. There exists no [gq(4,d), 4,d]q code for d = 2q3 − 4q2 − 3q + 1 for q ≥ 9. Theorem 1.5. There exists no [gq(4,d), 4,d]q code for d = q3 −q2 −rq − 2 with 4 ≤ r ≤ 6 for q ≥ 9. Theorem 1.2 is a generalization of the non–existence of Griesmer [209, 4, 166]5 codes. We note that the existence of a [gq(4,d), 4,d]q code for d = 2q3 − 3q2 − 3q + 1 is known for q = 4 but unknown and still open for q = 5, 7, 8. The existence of a [gq(4,d), 4,d]q code for d = 2q3 − 4q2 − 3q + 1 is known for q = 5 but unknown and still open for q = 7, 8. For the non–existence of [gq(4,d), 4,d]q codes for q3 − q2 − 4q + 1 ≤ d ≤ q3 − q2 − q, see [23]. The non–existence of [gq(4,d), 4,d]q codes for d = q3 − q2 − rq − 2 is known for (q,r) = (8, 4) but unknown and still open for (q,r) = (8, 5) and (q,r) = (8, 6). While the existence of a [gq(4,d) + 1, 4,d]q code for d = 2q3 − rq2 − q with 4 ≤ r ≤ q − 1 and for d = 2q3 − 4q2 − 2q is unknown in general, such a code exists for d = 2q3 − 5q2 −sq with 0 ≤ s ≤ q − 4, q ≥ 7 [21]. The existence of a [gq(4,d) + 1, 4,d]q code for d = 2q3 − 3q2 − 2q and for d = q3 − q2 − rq with 1 ≤ r ≤ q − 1 follows from the recent result from [10]. It is also known that nq(4,d) = gq(4,d) for d ≥ 2q3 − 3q2 + 1 for all q and that nq(4,d) = gq(4,d) + 1 for 2q3 − 3q2 − 2q + 1 ≤ d ≤ 2q3 − 3q2 for q ≥ 5 [12]. Since the existence of an [n,k,d]q code implies the existence of an [n− 1,k,d− 1]q code by puncturing, we get the following results from Theorems 1.2-1.5. Corollary 1.6. nq(4,d) = gq(4,d) + 1 for (1) 2q3 − 3q2 − 3q + 1 ≤ d ≤ 2q3 − 3q2 for q ≥ 9, (2) 2q3 − 5q2 − 2q + 1 ≤ d ≤ 2q3 − 5q2 for q ≥ 9, (3) q3 −q2 −rq − 2 ≤ d ≤ q3 −q2 −rq with 4 ≤ r ≤ 6 for q ≥ 9. Corollary 1.7. nq(4,d) ≥ gq(4,d) + 1 for (1) 2q3 −rq2 − 2q + 1 ≤ d ≤ 2q3 −rq2 −q for 4 ≤ r ≤ (q + 1)/2, q ≥ 7, (2) 2q3 − 4q2 − 3q + 1 ≤ d ≤ 2q3 − 4q2 − 2q for q ≥ 9. The remainder of the paper is organized as follows. In Section 2, we give the geometric preliminaries and some results on linear codes of dimension 3. We prove Theorems 1.2, 1.3 and 1.5 in Sections 3, 4 and 5, respectively. The proof of Theorem 1.4 is similar to that of Theorem 1.3 and therefore skipped. We give some remarks in Section 6 as Conclusion. 102 K. Kumegawa, T. Maruta / J. Algebra Comb. Discrete Appl. 5(2) (2018) 101–116 2. Preliminaries In this section, we give the geometric method and preliminary results to prove the non–existence of some Griesmer codes. We denote by PG(r,q) the projective geometry of dimension r over Fq. The 0-flats, 1-flats, 2-flats, (r−2)-flats and (r−1)-flats in PG(r,q) are called points, lines, planes, secundums and hyperplanes, respectively. Let C be an [n,k,d]q code having no coordinate which is identically zero. The columns of a generator matrix of C can be considered as a multiset of n points in Σ = PG(k−1,q), denoted by MC. An i-point is a point of Σ which has multiplicity i in MC. Denote by γ0 the maximum multiplicity of a point from Σ in MC and let Ci be the set of i-points in Σ, 0 ≤ i ≤ γ0. For any subset S of Σ, the multiplicity of S with respect to MC, denoted by mC(S), is defined as mC(S) = ∑γ0 i=1 i·|S∩Ci|, where |T | denotes the number of elements in a set T . A line l with t = mC(l) is called a t-line. A t-plane and so on are defined similarly. Then we obtain the partition Σ = ⋃γ0 i=0 Ci such that n = mC(Σ) and n−d = max{mC(π) | π ∈Fk−2}, where Fj denotes the set of j-flats of Σ. Conversely, such a partition Σ = ⋃γ0 i=0 Ci as above gives an [n,k,d]q code in the natural manner. For an m-flat Π in Σ, we define γj(Π) = max{mC(∆) | ∆ ⊂ Π, ∆ ∈Fj} for 0 ≤ j ≤ k − 2. We denote simply by γj instead of γj(Σ). Then γk−2 = n−d, γk−1 = n. For a Griesmer [n,k,d]q code, it is known (see [19]) that γj = j∑ u=0 ⌈ d qk−1−u ⌉ for 0 ≤ j ≤ k − 1. (1) So, every Griesmer [n,k,d]q code is projective if d ≤ qk−1. We denote by λs the number of s-points in Σ. Note that we have λ2 = λ0 + n−θk−1 (2) when γ0 = 2. Denote by ai the number of i-hyperplanes in Σ. The list of ai’s is called the spectrum of C. We usually use τj’s for the spectrum of a hyperplane of Σ to distinguish from the spectrum of C. Let θj be the number of points in a j-flat, i.e., θj = (qj+1 − 1)/(q− 1). Simple counting arguments yield the following. Lemma 2.1 ([15]). (1) n−d∑ i=0 ai = θk−1. (2) n−d∑ i=1 iai = nθk−2. (3) n−d∑ i=2 i(i− 1)ai = n(n− 1)θk−3 + qk−2 γ0∑ s=2 s(s− 1)λs. When γ0 ≤ 2, the above three equalities yield the following: n−d−2∑ i=0 ( n−d− i 2 ) ai = ( n−d 2 ) θk−1 −n(n−d− 1)θk−2 + ( n 2 ) θk−3 + q k−2λ2. (3) If ai = 0 for all i < n−d, then every point in Σ is an s-point for some integer s. This fact is known as follows. Lemma 2.2 ([2]). Any linear code over a finite field with constant Hamming weight is a replication of simplex (i.e., dual Hamming) codes. 103 K. Kumegawa, T. Maruta / J. Algebra Comb. Discrete Appl. 5(2) (2018) 101–116 Lemma 2.3 ([27]). Let Π be an w-hyperplane through a t-secundum δ. Then (1) t ≤ γk−2 − (n−w)/q = (w + qγk−2 −n)/q. (2) aw = 0 if a [w,k − 1,d0]q code with d0 ≥ w − ⌊ w+qγk−2−n q ⌋ does not exist, where bxc denotes the largest integer less than or equal to x. (3) γk−3(Π) = ⌊ w+qγk−2−n q ⌋ if a [w,k − 1,d1]q code with d1 ≥ w − ⌊ w+qγk−2−n q ⌋ + 1 does not exist. (4) Let cj be the number of j-hyperplanes through δ other than Π. Then ∑ j cj = q and∑ j (γk−2 − j)cj = w + qγk−2 −n−qt. (4) (5) For a γk−2-hyperplane Π0 with spectrum (τ0, · · · ,τγk−3 ), τt > 0 holds if w + qγk−2 −n−qt < q. The next two lemmas are needed to prove Theorems 1.3 and 1.4. Lemma 2.4 ([11]). The spectrum of a [2q2 − 2q − 4, 3, 2q2 − 4q − 2]q code with q ≥ 8 is one of the followings: (a) (aq−4,aq−2,a2q−3,a2q−2) = (1, 3, 2q,q2 −q − 3), (b) (aq−3,aq−2,a2q−4,a2q−3,a2q−2) = (2, 2, 1, 2q − 2,q2 −q − 2), (c) (aq−3,aq−2,a2q−4,a2q−3,a2q−2) = (1, 3, 1, 2q − 1,q2 −q − 3), (d) (aq−2,a2q−4,a2q−3,a2q−2) = (4, 1, 2q,q2 −q − 4) or (e) (aq−2,a2q−4,a2q−2) = (4,q + 1,q2 − 4). Lemma 2.5 ([11]). The spectrum of a [2q2−q−3, 3, 2q2−3q−2]q code with q ≥ 7 is one of the followings: (a) (aq−3,aq−1,a2q−2,a2q−1) = (1, 2, 2q,q2 −q − 2), (b) (aq−2,aq−1,a2q−3,a2q−2,a2q−1) = (2, 1, 1, 2q − 2,q2 −q − 1), (c) (aq−2,aq−1,a2q−3,a2q−2,a2q−1) = (1, 2, 1, 2q − 1,q2 −q − 2), (d) (aq−1,a2q−3,a2q−2,a2q−1) = (3, 1, 2q,q2 −q − 3) or (e) (aq−1,a2q−3,a2q−1) = (3,q + 1,q2 − 3). An n-set K in PG(2,q) is an (n,r)-arc if every line meets K in at most r points and if some line meets K in exactly r points. Let mr(2,q) denote the largest value of n for which an (n,r)-arc exists in PG(2,q). See Table 1 for the known values and bounds on mr(2,q) for 3 ≤ q ≤ 13 [1]. An (n, 2)-arc is simply called an n-arc in PG(2,q), see [8]. A set L of s lines in Σ = PG(2,q) is called an s-arc of lines in Σ if L forms an s-arc in the dual space Σ∗ of Σ, that is, no three lines of L are concurrent. Lemma 2.6 ([9]). (1) mr(2,q) ≤ (r − 1)q + r. (2) mr(2,q) ≤ (r − 1)q + r − 3 for 4 ≤ r < q with r 6 |q. (3) mr(2,q) ≤ (r − 1)q + r − 4 for 9 ≤ r < q with r 6 |q. (4) mq−2(2,q) = q2 − 2q − 3 √ q − 2 for odd square q > 112. (5) mq−2(2,q) ≤ q2 − 2q −pedp e+1+1 pe+1 e− 2 for q = p2e+1 > 17. 104 K. Kumegawa, T. Maruta / J. Algebra Comb. Discrete Appl. 5(2) (2018) 101–116 Table 1. The known values and bounds on mr(2, q). q 3 4 5 7 8 9 11 13 r 2 4 6 6 8 10 10 12 14 3 9 11 15 15 17 21 23 4 16 22 28 28 32 38–40 5 29 33 37 43–45 49–53 6 36 42 48 56 64–66 7 49 55 67 79 8 65 78 92 9 89–90 105 10 100–102 118–119 11 132–133 12 145–147 (6) mq−2(2,q) ≤ q2 − 2q − 2 √ q − 2 for q = 22e > 4 or q ∈{52, 72, 92, 112}. (7) mq−1(2,q) = q2 −q − 2 √ q − 1 for square q > 4. (8) mq−1(2,q) ≤ q2 −q −pedp e+1+1 pe+1 e− 1 for q = p2e+1 > 19. Lemma 2.7 ([12]). Let C be a [gq(3,d), 3,d]q code for d = 2q2 − rq, 3 ≤ r ≤ q − q/p, q = ph with p prime. Then, (1) the multiset MC consists of two copies of the plane with an r-arc of lines deleted, (2) C has spectrum (aq−r+2,a2q−r+2) = (r,θ2 −r). Lemma 2.8 ([25]). Let C be an [n,k,d]q code and let ∪ γ0 i=0Ci be the partition of Σ = PG(k − 1,q) obtained from C. If ∪i≥1Ci contains a t-flat ∆ and if d > qt, then there exists an [n−θt,k,d′]q code C′ with d′ ≥ d−qt. The punctured code C′ in Lemma 2.8 can be constructed from C by removing the t-flat ∆ from the multiset MC. The method to construct new codes from a given [n,k,d]q code by deleting the coordinates corresponding to some geometric object in PG(k − 1,q) is called geometric puncturing, see [21]. An [n,k,d]q code with generator matrix G is called extendable if there exists a vector h ∈ Fkq such that the extended matrix [G,hT] generates an [n + 1,k,d + 1]q code. The following theorems will be applied to prove that a [gq(3,d), 3,d = 2q2 −rq − 1]q code is extendable in Lemma 2.12. Theorem 2.9 ([6, 7]). Let C be an [n,k,d]q code with d ≡ −1 (mod q), k ≥ 3. Then C is extendable if Ai = 0 for all i 6≡ 0, −1 (mod q). Theorem 2.10 ([20, 28]). Let C be an [n,k,d]q code with d ≡ −2 (mod q), k ≥ 3, q ≥ 5. Then C is extendable if Ai = 0 for all i 6≡ 0,−1,−2 (mod q). Theorem 2.11 ([26]). Let C be an [n,k,d]q code with gcd(d,q) = 1. Then C is extendable if∑ i 6≡n,n−d (mod q) ai < q k−2. Lemma 2.12. The spectrum of a [2q2−(r−2)q−(r−1), 3, 2q2−rq−1]q code for 3 ≤ r ≤ q+12 , q = p h with p prime is (aq−r+1,aq−r+2,a2q−r+1,a2q−r+2) = (1,r − 1,q,q2 − r + 1) or (aq−r+2,a2q−r+1,a2q−r+2) = (r,q + 1,q2 −r). 105 K. Kumegawa, T. Maruta / J. Algebra Comb. Discrete Appl. 5(2) (2018) 101–116 Proof. Let C be an [n = 2q2 − (r − 2)q − (r − 1), 3,d = 2q2 − rq − 1]q code for 3 ≤ r ≤ q+12 , q = p h with p prime. Note that C is extended to the code in Lemma 2.7 if C is extendable. From (1), we have γ0 = 2 and γ1 = 2q − (r − 2). Since (γ1 − γ0)θ1 + γ0 − 1 = n, the lines through a fixed 2-point is one (γ1 −1)-line and q γ1-lines. Hence ai = 0 for θ1 + 1 ≤ i ≤ γ1 −2. Let l be a t-line containing a 1-point P . Considering the lines through P , we get n = 2q2−(r−2)q−(r−1) ≤ (γ1−1)q + t, giving q−(r−1) ≤ t. So, ai = 0 for 1 ≤ i ≤ q −r. Suppose aθ1 > 0. Then, C is not extendable by Lemma 2.7. Let l be a θ1-line. Since n = (γ1 −1)q + θ1−r, the lines (6= l) through a fixed 1-point on l are r (γ1−1)-lines and (q−r) γ1-lines if q ≥ 2r. Then, C is extendable from Theorem 2.11, a contradiction. When q = 2r − 1, the lines ( 6= l) through a fixed 1-point on l are either “one θ1-line and (q − 1) γ1-lines" or “r (γ1 − 1)-lines and (q − r) γ1-lines". If a 0-point exists, we have n ≥ (γ1 − 1)θ1 = n + q, a contradiction. Hence [q2 − (r− 1)q −r, 3,q2 −rq − 1]q code exists by Lemma 2.8. However, there exists no (q2 − (r − 1)q −r,q − (r − 1))-arc from Lemma 2.6 (2) when q = 2r − 1 ≥ 7 and from Table 1 when (q,r) = (5, 3), a contradiction. Thus aθ1 = 0. Next, suppose a0 > 0. Then, C is not extendable by Lemma 2.7. Let l be a 0-line. Since n = γ1q + 0 − (r − 1) and γ1 − (r − 1) > θ1, the lines ( 6= l) through a fixed 0-point on l are (γ1 − 1)-lines or γ1-lines. Hence aj > 0 implies j ∈ {0,γ1 − 1,γ1} and a0 = 1. Then, C is extendable by Theorem 2.11, a contradiction. Hence a0 = 0. Finally, suppose ai > 0 for some q − r + 3 ≤ i ≤ q. Then, C is not extendable by Lemma 2.7. Let l be a (q −e)-line with 0 ≤ e ≤ r− 3 and let Q be a 0-point on l. If four of the lines through Q have multiplicities at most q, then we have n ≤ 4q + (q − 3)γ1 = n− 2q + 4(r − 2) < n, a contradiction. So, at most two of the lines ( 6= l) through Q have no 2-point and∑ i6≡n,n−d (mod q) ai ≤ 2(e + 1) + 1 ≤ 2r − 3 < 2r − 1 ≤ q. Then, applying Theorem 2.11, C is extendable, a contradiction. Hence ai = 0 for all i 6∈ {q − r + 1,q − r + 2, 2q − r + 1, 2q − r + 2}. Applying Theorem 2.9, C is extendable. Hence C can be obtained from a [2q2−(r−2)q−(r−2), 3, 2q2−rq]q code C′ by removing one coordinate. Let R be the point corresponding to the coordinate. There are two possible spectra (aq−r+1,aq−r+2,a2q−r+1,a2q−r+2) = (1,r−1,q,q2−r+ 1) or (aq−r+2,a2q−r+1,a2q−r+2) = (r,q + 1,q2 − r), according to the cases R is a 1-point or a 2-point, respectively. Lemma 2.13. The spectrum of a [q2 − r, 3,q2 − q − r]q code with 1 ≤ r ≤ q − 2 satisfies ai = 0 for 1 ≤ i ≤ q −r − 1. Proof. Let C be a [q2−r, 3,q2−q−r]q code, which is Griesmer. From (1), we have γ0 = 1 and γ1 = q. Let l be an i-line with i > 0 containing a 1-point P . Counting the 1-points on the lines through P , we get n = q2 −r ≤ (q − 1)q + i, whence q −r ≤ i. 3. Proof of Theorem 1.2 We assume q ≥ 7 since the theorem is already known for (r,q) = (3, 5) [14]. We first prove the non–existence of [gq(4,d), 4,d]q code for d = 2q3 −rq2 − 2q + 2. Lemma 3.1. There exists no [n = 2θ3 −rθ2 − 2θ1 + 3, 4,d = 2q3 −rq2 − 2q + 2]q code for 3 ≤ r ≤ q+12 , q = ph ≥ 7 with p prime. Proof. Let C be a putative [n = 2q3 − (r − 2)q2 − rq − (r − 3), 4,d = 2q3 − rq2 − 2q + 2]q code with 3 ≤ r ≤ (q+ 1)/2, q ≥ 5. Note that n = gq(4,d) and hence γ0 = 2, γ1 = 2θ1−r, γ2 = n−d = 2θ2−rθ1−1 from (1). Let ∆ be a γ2-plane. Since γ2 = (γ1 −2)(q + 1) + 2−1 and n = (γ1 −2)θ2 + 2−(2q−1), every line on ∆ through a 2-point is a γ1-line or a (γ1 − 1)-line, and any i-plane through a 2-point satisfies (γ1−2)(q + 1) + 2−(2q−1) = γ2−2(q−1) ≤ i ≤ γ2. By Lemma 2.3 (1), any t-line in an i-plane satisfies t ≤ i + r − 3 q + 1. (5) 106 K. Kumegawa, T. Maruta / J. Algebra Comb. Discrete Appl. 5(2) (2018) 101–116 The spectrum of ∆ is either (A) (τq−r+1,τq−r+2,τ2q−r+1,τ2q−r+2) = (1,r − 1,q,q2 − r + 1) or (B) (τq−r+2,τ2q−r+1,τ2q−r+2) = (r,q + 1,q 2 −r) by Lemma 2.12. Let δ be an i-plane. It follows from (5) and ∆’s possible spectra that q − r + 1 ≤ i+q+r−3 q , i.e., q2−rq−(r−3) ≤ i. Assume i ≤ θ2. Since δ has no 2-point, δ∩∆ is a (q−r + 1)-line or a (q−r + 2)-line. So, i ≤ θ2 − r + 1. Now, let i = q2 −uq − (r − 3) + s with 0 ≤ u ≤ r − 2, 0 ≤ s ≤ q − 1. From (5), we have t ≤ q −u + 1. If t = q −u + 1, then i + q + r − 3 − qt = s ≤ q − 1, and the γ2-plane ∆ contains a t-line by Lemma 2.3 (5), a contradiction. Hence t ≤ q −u. Considering the lines in δ through a fixed 1-point of δ∩ ∆, i ≤ (q−u− 1)q + (q−r + 2) = q2 −uq− (r− 2) < i, a contradiction. Thus, ai = 0 for q2 − (r − 2)q − (r − 3) ≤ i ≤ θ2, and ai > 0 implies q2 −rq − (r − 3) ≤ i ≤ q2 − (r − 2)q − (r − 2) or γ2 − 2q + 2 ≤ i ≤ γ2. From (3), we get ∑ i ( γ2 − i 2 ) ai = q 2λ2 −q5 + 3r − 2 2 q4 − r2 − 3r − 4 2 q3 − r2 + 6 2 q2 − 2q + 3. (6) For any w-plane through a t-line, (4) gives ∑ j cj = q and∑ j (2q2 − (r − 2)q − (r − 1) − j)cj = w + q + r − 3 −qt. (7) Suppose ai > 0 for i = q2 − rq − (r − 3) + e with 0 ≤ e ≤ q − 1. Since δ ∩ ∆ is a (q − r + 1)-line by (5), ∆ has spectrum (A). If ai > 0, the RHS of (7) is q2 − (r − 1)q + e− qt ≤ q2 − (r − 2)q − 1. Since the coefficient of cq2−(r−2)q−(r−2) in (7) is q2 − 1 > q2 − (r − 2)q − 1, we get ai = 1 and aj = 0 for q2 − rq − (r − 3) ≤ j ≤ q2 − (r − 2)q − (r − 2) with j 6= i. Setting w = n − d, the maximum possible contributions of cj’s in (7) to the LHS of (6) on ∆ are (cq2−rq−(r−3)+e,cn−d−e,cn−d) = (1, 1,q − 2) for t = q−r+ 1; (cγ2−2(q−1),cγ2−(q−1),cn−d) = ( q+1 2 , 1, q−3 2 ) if q is odd and (cγ2−2(q−1),cn−d) = ( q 2 + 1, q 2 −1) if q is even for t = q−r + 2; (cγ2−2(q−1),cn−d) = (1,q−1) for t = 2q−r + 1; (cγ2−(q−2),cn−d) = (1,q−1) for t = 2q −r + 2. Hence, when q is odd, we get (LHS of (6)) ≤ (( q2 + 2q − 2 −e 2 ) + ( e 2 )) τq−r+1 + (q + 1 2 ( 2(q − 1) 2 ) + ( q − 1 2 )) τq−r+2 + ( 2(q − 1) 2 ) τ2q−r+1 + ( q − 2 2 ) τ2q−r+2 ≤ ( q2 + 2q − 2 2 ) τq−r+1 + (q + 1 2 ( 2(q − 1) 2 ) + ( q − 1 2 )) τq−r+2 + ( 2(q − 1) 2 ) τ2q−r+1 + ( q − 2 2 ) τ2q−r+2, giving λ2 < q 3 − 3r − 4 2 q2 + r2 −r − 3 2 q + r2 − 3r + 4 2 . When q is even, we can similarly obtain λ2 < q 3 − 3r − 4 2 q2 + r2 −r − 3 2 q + r2 − 2r + 3 2 . On the other hand, since λ0 ≥ |δ ∩C0|, we have λ2 = n−θ3 + λ0 ≥ n−θ3 + θ2 − (q2 −rq − (r − 3) + e) ≥ q3 − (r − 1)q2 −q + 1 107 K. Kumegawa, T. Maruta / J. Algebra Comb. Discrete Appl. 5(2) (2018) 101–116 giving a contradiction for q ≥ 2r − 1 with q ≥ 7 and r ≥ 3. Thus, ai = 0 for q2 − rq − (r − 3) ≤ i ≤ q2 − (r − 1)q − (r − 2). By a similar argument using Lemma 2.3, (6) and (7), we can get ai = 0 for all q2−(r−1)q−(r−3) ≤ i ≤ q2 − (r − 2)q − (r − 2). Hence, ai > 0 implies γ2 − 2q + 2 ≤ i ≤ γ2. Finally, we investigate (6) and (7) with i = n − d again. We only give the proof when ∆ has spectrum (A) since one can prove similarly for spectrum (B). Assume q is odd. The maximum possible contributions of cj’s in (7) to the LHS of (6) on ∆ are (cγ2−2(q−1),cn−d−1,cn−d) = ( q+3 2 , 1, q−5 2 ) for t = q−r + 1; (cγ2−2(q−1),cγ2−(q−1),cn−d) = ( q+1 2 , 1, q−3 2 ) for t = q−r + 2; (cγ2−2(q−1),cn−d) = (1,q−1) for t = 2q −r + 1; (cγ2−(q−2),cn−d) = (1,q − 1) for t = 2q −r + 2. Hence we get (LHS of (6)) ≤ q + 3 2 ( 2(q − 1) 2 ) τq−r+1 + ( q + 1 2 ( 2(q − 1) 2 ) + ( q − 1 2 ) )τq−r+2 + ( 2(q − 1) 2 ) τ2q−r+1 + ( q − 2 2 ) τ2q−r+2, giving λ2 < q 3 − 3r − 3 2 q2 + r2 −r − 5 2 q + r2 − 3r + 6 2 . On the other hand, we have λ2 = n−θ3 + λ0 ≥ (2θ3 −rθ2 − 2θ1 + 3) −θ3 = q3 − (r − 1)q2 − (r + 1)q − (r − 2), giving a contradiction for q ≥ 2r−1. One can get a contradiction similarly when q is even. This completes the proof. In the above proof, we often obtain a contradiction to rule out the existence of some i-plane by eliminating the value of λ2 using (4), (3) and the possible spectra for a fixed w-plane. We refer to this proof technique as "(λ2,w)-ruling out method ((λ2,w)-ROM)" in what follows. Proof of Theorem 1.2. Let C be a putative [n = 2q3−(r−2)q2−rq−(r−2), 4,d = 2q3−rq2−2q + 1]q code with 3 ≤ r ≤ (q + 1)/2, q ≥ 5. By Lemma 1, γ0 = 2, γ1 = 2q−(r−2), γ2 = n−d = 2θ2−rθ1−1. By Lemma 2.12, the spectrum of a γ2-plane ∆ is (A) (τq−r+1,τq−r+2,τ2q−r+1,τ2q−r+2) = (1,r−1,q,q2−r+1) or (B) (τq−r+2,τ2q−r+1,τ2q−r+2) = (r,q + 1,q2 −r). So a j-line on ∆ satisfies j ∈{q −r + 1,q −r + 2, 2q −r + 1, 2q −r + 2}. (8) By Lemma 2.3, an i-plane satisfies i ≥ (q−r + 1)q−(q + r−2) = q2 −rq−(r−2). Hence ai = 0 for any i < q2 −rq− (r− 2). Assume that an i-plane contains a 2-point. Since (γ1 − 2)θ2 + 2 = n + 2q, we have i ≥ (γ1 − 2)θ1 + 2 − 2q = (2q −r)θ1 + 2 − 2q = 2q2 −rq − (r − 2) > θ2 for q ≥ 2r−1. Hence an i-plane with i ≤ θ2 = q2 +q+ 1 has no 2-point. Thus ai = 0 if i < q2−rq−(r−2) or θ2 < i < 2q2 −rq − (r − 2). Let δ be a i-plane, s = γ1(δ). Then, δ ∩C is an (i,s)-arc, corresponding to an [i, 3, i−s]q code. By Lemma 2.3(1), s ≤ i + r − 2 q + 1 (9) By Lemma 2.3 (5), δ contains a t-line if i + q + (r − 2) −qt < q. (10) (Case 1) Assume q2 −rq − (r − 2) ≤ i < q2 − (r − 1)q − (r − 2). We have s ≤ q−(r−1) by (9). Since δ∩∆ is a j-plane satisfying (8), we get s = q−(r−1). By Lemma 108 K. Kumegawa, T. Maruta / J. Algebra Comb. Discrete Appl. 5(2) (2018) 101–116 2.6 (2), i ≤ (q −r)q + (q −r + 1) − 3 = q2 − (r − 1)q − (r + 2). (Case 2) Assume q2 − (r − 1)q − (r − 2) ≤ i < q2 − (r − 2)q − (r − 2). By (9), s ≤ q − (r − 2). It follows from (Case 1) that s = q − (r − 2). By Lemma 2.6 (2), we get i ≤ q2 − (r − 2)q − (r + 1). (Case 3) Assume q2 − (r − 2)q − (r − 2) ≤ i < q2 − (r − 3)q − (r − 2). By (9), s ≤ q − (r− 3). It follows from (Case 2) that s = q − (r− 3). Then, by Lemma 2.3 (5), ∆ has a (q − (r − 3))-line, a contradiction. Hence ai = 0. (Case 4) Assume q2 −uq − (r − 2) ≤ i < q2 − (u− 1)q − (r − 2), 0 ≤ u ≤ r − 3. By (9), s ≤ q − u + 1. If s = q − u + 1, then ∆ contains a (q − u + 1)-line by Lemma 2.3 (5), a contradiction. Hence s ≤ q − u, and δ ∩ ∆ is a (q − r + 1)-line or a (q − r + 2)-line. Considering the lines in δ through a fixed 1-point on δ ∩ ∆, we have i ≤ (q − u − 1)q + q − r + 2 = q2 − uq − (r − 2). Hence i = q2 − uq − (r − 2), and δ ∩ ∆ is a (q − r + 2)-line. Let P be any 1-point in δ. Then, there exists a γ2-plane through P meeting δ in a (q − r + 2)-line. Otherwise, one can get an [n + 1, 4,d + 1]q code by adding P to the multiset for C, which contradicts Theorem 3.1. Thus, the lines through P in δ are one (q − r + 2)-line and q (q −u)-lines, and other possible lines in δ are 0-lines. Let Ci be the code corresponding to δ. Then Ci is an [i, 3, i− (q −u) = q2 − (u + 1)q − (r − 2 −u)]q code with spectrum (µ0,µq−r+2,µq−u) = ( q ( r − 2 q −u − r −u− 3 q −r + 2 ) , i q −r + 2 , iq q −u ) , (11) where µj is the number of j-lines in δ. Since (q −u)(q − 1) < i from the assumption q ≥ 2r − 1, we get µ0 = 0 or 1. Take a 0-point Q not on a 0-line in δ. It follows from (q − u)q + q − r + 2 = i + q that r − 2 −u divides q. So, r − 2 −u = pm (12) for some integer m ≥ 0. If m = 0, then u = r−3 and i = q2−(r−3)q−(r−2). Since gcd(q−r+2,q−r+3) = 1, (q −r + 2)|i implies (q −r + 3)|q. From (11), µ0 = q q −r + 3 (r− 2) 6= 0. Hence µ0 = 1, r = 3, u = 0, and i = q2 − 1. Assume m > 0. Then h ≥ 2 and 1 ≤ m ≤ h− 1, for r − 2 ≤ (q − 3)/2. Suppose µ0 = 0. From (11) and (12), we have (u + 1)q = p2m + u(r − 1). (13) If h ≤ 2m, then, from (12) and (13), q divides either u or r − 1, a contradiction. Hence 2m ≤ h − 1. From (13), we get q = p2m u + 1 + u(r − 1) u + 1 < ph−1 + r − 1 ≤ q 2 + q − 1 2 < q, a contradiction. Hence µ0 = 1. Since (q −u)(q − 1) + q − r + 2 = i + u, the number of (q − r + 2)-lines through a fixed 0-point on the 0-line in δ is 1 + u/(r− 2 −u). So, pm divides u and r− 2 also from (12). From µ0 = 1 and (11), we have (q −u)(q −r + 2) q = q(u + 1) −u(r − 1) −p2m. (14) Suppose h ≤ 2m. Then, from (14), we obtain (r − 2)((1 −u)q −u) ≡ 0 (mod q2). (15) Since q divides u(r − 2), (15) yields (r − 2)(q − u) ≡ 0 (mod q), a contradiction. Hence 2m ≤ h − 1. If u = 0, then (14) gives r − 2 = p2m, which contradicts (12). Thus, u > 0. Then, from (14), we have q(u + 1) −u(r − 1) −p2m < q −r + 2, giving qu < u(r − 1) − (r − 1) + 1 + p2m, i.e., q ≤ (u− 1)(r − 1) u + p2m u < pm + r − 1 ≤ √ q p + q − 1 2 < q, 109 K. Kumegawa, T. Maruta / J. Algebra Comb. Discrete Appl. 5(2) (2018) 101–116 a contradiction. Hence ai = 0 except for the case (r,u) = (3, 0). (Case 5) Assume q2 + q − (r − 2) ≤ i ≤ θ2. By (9), s ≤ q + 2. If s = q + 2, then ∆ contains a (q + 2)-line by Lemma 2.3 (5), a contradiction. Hence s ≤ q + 1. So, δ ∩ ∆ is a (q − r + 1)-line or a (q − r + 2)-line. Considering the lines through a fixed 1-point on δ ∩ ∆, we get i ≤ q · q + (q − r + 2) = q2 + q − (r − 2). Hence i = q2 + q − (r − 2). Since θ2 − (q2 + q − (r− 2)) = r− 1 and θ1 − (r− 1) = q −r + 2, a t-line on δ satisfies θ1 ≥ t ≥ q −r + 2. So, δ ∩ ∆ is a (q −r + 2)-line. Hence, the spectrum of δ is (τq−r+2,τq,τq+1) = (1, (r − 1)q, (q − r + 2)q). Then any point of δ\∆ is not contained in a γ2-plane, and C is extendable, which contradicts Lemma 2.11. Hence ai = 0. From the above (Case 1) - (Case 5), ai > 0 implies i ∈{q2 −rq − (r − 2), · · · ,q2 − (r − 1)q − (r + 2),q2 − (r − 1)q − (r − 2), · · · , q2 − (r − 2)q − (r + 1), 2q2 −rq − (r − 2), · · · , 2q2 − (r − 2)q − (r − 1)}, or i = q2 − 1 when r = 3. By (3), we get ∑ j ( γ2 − j 2 ) = q2λ2 −q5 + 3r − 2 2 q4 − r2 − 3r − 4 2 q3 − r2 + 2 2 q2 − 2q + 1. (16) Note that the LHS of (16) contains the term ( q2−q−1 2 ) aq2−1 only for r = 3. For any w-plane through a t-line, (4) gives ∑ j cj = q and∑ j (2q2 − (r − 2)q − (r − 1) − j)cj = w + q + (r − 2) −qt. (17) Now, we rule out the possible i-planes for q2−rq−(r−2) ≤ i ≤ q2−(r−1)q−r−2 by (λ2,γ2)-ROM. Suppose ai > 0 for i = q2 −rq − (r− 2) + e with 0 ≤ e ≤ q − 4 and let δ be an i-plane. We may assume that ∆ has spectrum (A) since δ∩∆ is a (q−r + 1)-line. It follows from (4) that ai = 1 and that aj = 0 for q2 − rq − (r − 2) ≤ j ≤ q2 + q − (r − 2) with j 6= i. Assume q is odd. Setting w = n − d, the maximum possible contributions of cj’s in (17) to the LHS of (16) are (cq2−rq−(r−2)+e,cn−d−e,cn−d) = (1, 1,q − 2) for t = q − r + 1; (c2q2−rq−(r−2),c2q2−(r−3 2 )q−(r−3 2 ),cn−d) = ( q+1 2 , 1, q−3 2 ) for t = q − r + 2; (c2q2−rq−(r−2),cn−d) = (1,q−1) for t = 2q−r + 1; (c2q2−(r−1)q−(r−2),cn−d) = (1,q−1) for t = 2q−r + 2. Hence we get (LHS of (16)) ≤ ( ( q2 + 2q − 1 −e 2 ) + ( e 2 ) )τq−r+1 + ( q + 1 2 ( 2q − 1 2 ) + (q−1 2 2 ) )τq−r+2 + ( 2q − 1 2 ) τ2q−r+1 + ( q − 1 2 ) τ2q−r+2 ≤ ( q2 + 2q − 1 2 ) τq−r+1 + ( q + 1 2 ( 2q − 1 2 ) + (q−1 2 2 ) )τq−r+2 + ( 2q − 1 2 ) τ2q−r+1 + ( q − 1 2 ) τ2q−r+2, giving λ2 < q 3 + 4 − 3r 2 q2 + r2 −r − 1 2 q + 4r2 − 7r + 3 8 . On the other hand, since λ0 ≥ |δ ∩C0| = θ2 − i, we have λ2 = n−θ3 + λ0 ≥ n−θ3 + (θ2 − (q2 − (r − 1)q − (r + 2))) = q3 + (1 −r)q2 −q + 4, 110 K. Kumegawa, T. Maruta / J. Algebra Comb. Discrete Appl. 5(2) (2018) 101–116 giving a contradiction. One can get a contradiction similarly when q is even. Hence ai = 0. One can also rule out possible i-planes for i = q2 − (r − 1)q − (r − 2) + e with 0 ≤ e ≤ q − 3 by (λ2,γ2)-ROM. Next, we rule out the possible (q2−1)-plane by (λ2,q2−1)-ROM. Suppose aq2−1 > 0 for r = 3. The spectrum of a (q2−1)-plane is (τ0,τq−1,τq) = (1,q+1,q2−1) since it corresponds to a [q2−1, 3,q2−q−1]q code. From (17) we have aq2−1 = 1 and aj = 0 for q2−2q−1 ≤ j ≤ q2−q−5. Then, the maximum possible contributions of cj’s in (17) with w = q2 − 1 to the LHS of (16) are (ci,c2q2−2q−5,cn−d−1) = (1, 1,q − 2) for t = 0; (c2q2−3q−1,cn−d−1,cn−d) = (1, 1,q − 2) for t = q − 1; c2q2−q−3 = q for t = q. Hence we get (LHS of (16)) ≤ ( q2 −q − 1 2 ) + ( ( q2 −q − 1 2 ) + ( q + 3 2 ) )τ0 + ( 2q − 1 2 ) τq−1 + 0 · τq giving λ2 < q3 − 5q2/2 − 2q + 4. On the other hand, since λ0 ≥ θ2 − i, we have λ2 = n−θ3 + λ0 ≥ 2q3 −q2 − 3q − 1 −θ3 + θ2 − (q2 − 1) = q3 − 2q2 − 3q, giving a contradiction. Hence aq2−1 = 0. Finally, we apply (λ2,γ2)-ROM for i = γ2 to get a contradiction. We only give the proof when ∆ has spectrum (A) since one can prove similarly for spectrum (B). Assume q is odd. The maximum possible contributions of cj’s in (17) to the LHS of (16) on ∆ are (c2q2−rq−(r−2),c2q2−(r−1 2 )q−(r−3 2 ),cn−d) = (q+1 2 , 1, q−3 2 ) for t = q − r + 1; (c2q2−rq−(r−2),c2q2−(r−3 2 )q−(r−3 2 ),cn−d) = ( q+1 2 , 1, q−3 2 ) for t = q − r + 2; (c2q2−rq−(r−2),cn−d) = (1,q−1) for t = 2q−r + 1; (c2q2−(r−1)q−(r−2),cn−d) = (1,q−1) for t = 2q−r + 2. Hence (LHS of (16)) ≤ ( q + 1 2 ( 2q − 1 2 ) + (3q−1 2 2 ) )τq−r+1 + ( q + 1 2 ( 2q − 1 2 ) + (q−1 2 2 ) )τq−r+2 + ( 2q − 1 2 ) τ2q−r+1 + ( q − 1 2 ) τ2q−r+2, giving λ2 < q 3 + 3 − 3r 2 q2 + r2 −r − 3 2 q + 4r2 − 7r + 4 4 . On the other hand, it follows from λ0 ≥ θ2 − i that λ2 = n−θ3 + λ0 ≥ n−θ3 = q3 − (r − 1)q2 − (r + 1)q − (r − 1), giving a contradiction. One can get a contradiction similarly when q is even. This completes the proof. 4. Proof of Theorem 1.3 To prove Theorems 1.3 and 1.4, the possible spectra of some 3-dimensional codes in Table 2 are needed. We omit the proof of Theorem 1.4 as noted in Section 1. See [13] for the proof of Theorem 1.3 for q = 9. Let C be a putative [n = 2q3−q2−4q−2, 4,d = 2q3− 3q2−3q+1]q code for q ≥ 11. It follows from (1) that γ0 = 2, γ1 = 2q−1, γ2 = 2q2−q−3. The spectrum of a γ2-plane ∆ is one of the followings by Lemma 2.5: (A) (τq−3,τq−1,τ2q−2,τ2q−1) = (1, 2, 2q,q2 −q− 2), (B) (τq−2,τq−1,τ2q−3,τ2q−2,τ2q−1) = (2, 1, 1, 2q − 2,q2 − q − 1), (C) (τq−2,τq−1,τ2q−3,τ2q−2,τ2q−1) = (1, 2, 1, 2q−1,q2−q−2), (D) (τq−1,τ2q−3,τ2q−2,τ2q−1) = (3, 1, 2q,q2−q−3), or (E) (τq−1,τ2q−3,τ2q−1) = (3,q + 1,q2 − 3). Hence, a j-line on ∆ satisfies j ∈{q − 3,q − 2,q − 1, 2q − 3, 2q − 2, 2q − 1}. (18) 111 K. Kumegawa, T. Maruta / J. Algebra Comb. Discrete Appl. 5(2) (2018) 101–116 Table 2. The spectra of some [n, 3, d]q codes for q ≥ 9 ([5, 8]). parameters possible spectra [q2 − 3, 3,q2 −q − 3]q, q ≥ 11 (a0,aq−3,aq−1,aq) = (1, 1, 3q,q2 − 2q − 1) (a0,aq−2,aq−1,aq) = (1, 3, 3q − 3,q2 − 2q) [q2 − 3, 3,q2 −q − 3]q, q = 9 (a0,a6,a8,a9) = (1, 1, 27, 62) (a0,a7,a8,a9) = (1, 3, 24, 63) (a6,a9) = (13, 78) [q2 − 2, 3,q2 −q − 2]q (a0,aq−2,aq−1,aq) = (1, 1, 2q,q2 −q − 1) [q2 − 1, 3,q2 −q − 1]q (a0,aq−1,aq) = (1,q + 1,q2 − 1) [q2, 3,q2 −q]q (a0,aq) = (1,q2 + q) [q2 + q − 3, 3,q2 − 4]q (aq−3,aq,aq+1) = (1, 4q,q2 − 3q) (aq−2,aq−1,aq,aq+1) = (1, 3, 4q − 5,q2 − 3q + 2) (aq−1,aq,aq+1) = (6, 4q − 8,q2 − 3q + 3) [q2 + q − 2, 3,q2 − 3]q (aq−2,aq,aq+1) = (1, 3q,q2 − 2q) (aq−1,aq,aq+1) = (3, 3q − 3,q2 − 2q + 1) [q2 + q − 1, 3,q2 − 2]q (aq−1,aq,aq+1) = (1, 2q,q2 −q) [q2 + q, 3,q2 − 1]q (aq,aq+1) = (q + 1,q2) [q2 + q + 1, 3,q2]q aq+1 = q 2 + q + 1 From Lemma 2.1 (3), we have λ0(∆) = 5, 5, 4, 3, 4 for the cases A,B,C,D,E, respectively. By Lemma 2.3, an i-plane satisfies i ≥ q(q−3)−(q+2) = q2−4q−2. Hence ai = 0 for any i < q2−4q−2. Assume that an i-plane contains a 2-point. Since (γ1−2)θ2+2 = n+3q+1, we have i ≥ (γ1−2)θ1+2−(3q+1) = 2q2−4q−2. Let δ be an i-plane, r = γ1(δ). Then, δ∩C is an (i,r)-arc, corresponding to an [i, 3, i−r]q code. Lemma 2.3 (1) gives r ≤ i + 2 q + 1. (19) For any w-plane through a t-line, (4) gives∑ j (γ2 − j)cj = w + q + 2 −qt (20) with ∑ j cj = q. The equality (2) yields: λ2 = q 3 − 2q2 − 5q − 3 + λ0. (21) Assume q2−4q−2 ≤ i < q2−3q−2. From (19), and (18) we have r = q−3. Then, i ≤ (q−4)q+(q−3)−4 = q2 − 3q − 7 for q ≥ 13 by Lemma 2.6 (3) and i ≤ 78 for q = 11 by Table 1. We also have that q2 − 3q − 2 ≤ i < q2 − 2q − 2 implies r = q − 2 and i ≤ (q − 3)q + (q − 2) − 4 = q2 − 2q − 6 and that q2−2q−2 ≤ i < q2−q−2 implies r = q−1 and i ≤ (q−2)q+ (q−1)−4 = q2−q−5. Hence, i > q2−q−5 implies r ≥ q. Assume q2−q−2 ≤ i < q2−2. By (19), r = q. (20) with (w,t) = (i,q) yields that cγ2 > 0, which contradicts that a γ2-plane has no q-line. Hence ai = 0. Similarly, q2 − 2 ≤ i < q2 + q − 2 implies r = q and i ≤ q2. The spectrum of a q2-plane is (τ0,τq) = (1,q2 + q) from Table 2, which contradicts (18). Hence qq2 = 0. We have aq2+q = aθ2 = 0 similarly. Thus, we have ai = 0 for all i /∈{q2 − 4q − 2, . . . ,q2 − 3q − 7,q2 − 3q − 2, . . . ,q2 − 2q − 6,q2 − 2q − 2, . . . , q2 −q − 5,q2 − 2,q2 − 1,q2 + q − 2,q2 + q − 1, 2q2 − 4q − 2, . . . , 2q2 −q − 3}. Note that a79 = a80 = a81 = 0 for q = 11. From (3), we get γ2−2∑ i=0 ( γ2 − i 2 ) ai = q 2λ2 − (q5 − 7 2 q4 − 7 2 q3 + 13 2 q2 + 7 2 q − 1). (22) 112 K. Kumegawa, T. Maruta / J. Algebra Comb. Discrete Appl. 5(2) (2018) 101–116 We first rule out possible (q2 +q−2)-planes by (λ2,q2 +q−2)-ROM. Suppose aq2+q−2 > 0. The spectrum of a [q2+q−2, 3,q2−3]q code is (X) (τq−2,τq,τq+1) = (1, 3q,q2−2q) or (Y) (τq−1,τq,τq+1) = (3, 3q−3,q2− 2q+1) from Table 2. Setting w = q2 +q−2 in (20), the maximum possible contributions of cj’s to the LHS of (22) are (c2q2−4q−2,c2q2−2q−4,cn−d) = (1, 1,q−2) for t = q−2; (c2q2−4q−2,cn−d−1,cn−d) = (1, 1,q−2) for t = q − 1; (c2q2−2q−4,cn−d−1) = (1,q − 1) for t = q; cn−d−1 = q for t = q + 1. Estimating the LHS of (22) for spectrum (X), we get (LHS of (22)) ≤ ( q2 − 2q − 1 2 ) + ( ( 3q − 1 2 ) + ( q + 1 2 ) )τq−2 + ( 3q − 1 2 ) τq−1 + ( q + 1 2 ) τq, giving λ2 ≤ (2q3 − 6q2 − 8q + 27)/2. On the other hand, (21) gives λ2 ≥ q3 − 2q2 − 5q, a contradiction. We also get a contradiction similarly for spectrum (Y). Hence aq2+q−2 = 0. One can prove aq2+q−1 = aq2−2 = aq2−1 = 0 for q ≥ 11 using the spectra in Table 2, similarly. Next, we rule out the possible i-planes for q2−4q−2 ≤ i ≤ q2−3q−7 for q ≥ 13 and for 75 ≤ i ≤ 78 for q ≥ 11 by (λ2,γ2)-ROM. Suppose ai > 0 for i = q2 −4q−2 + e with 0 ≤ e ≤ q−5, q ≥ 13. Then, we may assume that ∆ has spectrum (A). Note that RHS of (20) is at most q2 − 3q + e−qt ≤ q2 − 4q − 5. Since ∆ has no 0-line and the coefficient of cq2−q−5 in (20) is q2 + 2, we get ai = 1 and aj = 0 for j ≤ q2 − q − 5 with j 6= i. Setting w = n−d in (20), the maximum possible contributions of cj’s to the LHS of (22) are (ci,cn−d−e,cn−d) = (1, 1,q−2) for t = q−3; (c2q2−4q−2,cn−d−y,cn−d) = (x, 1,q−x−1) for t = q − 1; (c2q2−3q−2,cn−d) = (1,q − 1) for t = 2q − 2; (c2q2−2q−2,cn−d) = (1,q − 1) for t = 2q − 1, where (x,y) = (q/3, 4q/3 − 1), (x,y) = ((q− 1)/3, (7q− 4)/3), (x,y) = ((q + 1)/3, (q− 2)/3) if q ≡ 0, 1, 2 (mod 3), respectively. Estimating the LHS of (22), we get (LHS of (22)) ≤ ( ( q2 + 3q − 1 −e 2 ) + ( e 2 ) )τq−3 + ( ( 3q − 1 2 ) x + ( y 2 ) )τq−1 + ( 2q − 1 2 ) τ2q−2 + ( q − 1 2 ) τ2q−1 ≤ ( q2 + 3q − 1 2 ) τq−3 + ( ( 3q − 1 2 ) q + 1 3 + (q−2 3 2 ) )τq−1 + ( 2q − 1 2 ) τ2q−2 + ( q − 1 2 ) τ2q−1, giving λ2 ≤ (18q3−45q2 + 81q + 92)/18. On the other hand, since ∆ has five 0-points and one (q−3)-line, say l, ∆\l has one 0-point. Since cn−d ≥ q−e−1 ≥ 4 for t = q−3, there are at least four γ2-planes with spectrum (A) through l and (21) yields λ2 ≥ q3 − 2q2 − 5q − 3 + (θ2 − (q2 − 3q − 7)) + 4 = q3 − 2q2 −q + 5, giving a contradiction for q ≥ 13. For q = 11, we consider a putative i-plane with i = q2 − 4q − 2 + e with 0 ≤ e ≤ 3 in the same way. Since cn−d ≥ q − e − 1 ≥ 7 for t = q − 3, we can get a contradiction as above. Hence ai = 0 for q2 − 4q − 2 ≤ i ≤ q2 − 3q − 7. One can similarly prove that ai = 0 for q2 − 3q − 2 ≤ i ≤ q2 − 2q − 6 and for q2 − 2q − 2 ≤ i ≤ q2 −q − 5 by (λ2,γ2)-ROM. Thus, we have proved that ai = 0 for all i < 2q2 −4q−2. Finally, applying (λ2,γ2)-ROM for i = λ2, we get a contradiction as follows. Setting w = n−d, the maximum possible contributions of cj’s in (20) to the LHS of (22) are (c2q2−4q−2,cn−d−w,cn−d) = (z, 1,q−z−1) for t = q−3; (c2q2−4q−2,cn−d−b,cn−d) = (a, 1,q−a−1) for t = q−2; (c2q2−4q−2,cn−d−y,cn−d) = (x, 1,q−x−1) for t = q−1; (c2q2−4q−2,cn−d) = (1,q − 1) for t = 2q − 3; (c2q2−3q−2,cn−d) = (1,q − 1) for t = 2q − 2; (c2q2−2q−2,cn−d) = (1,q − 1) for t = 2q − 1, where (a,b,x,y,z,w) = (q/3, 7q/3 − 1,q/3, 4q/3 − 1,q/3 + 1,q/3), ((q + 2)/3, (q − 1)/3, (q − 1)/3, (7q− 4)/3, (q + 2)/3, (4q− 1)/3), ((q + 1)/3, (4q− 2)/3, (q + 1)/3, (q− 2)/3, (q + 1)/3, (7q− 2)/3) if q ≡ 0, 1, 2 (mod 3), respectively. Estimating the LHS of (22), we get (LHS of (22)) ≤ ( ( 3q − 1 2 ) z + ( w 2 ) )τq−3 + ( ( 3q − 1 2 ) a + ( b 2 ) )τq−2 +( ( 3q − 1 2 ) x + ( y 2 ) )τq−1 + ( 3q − 1 2 ) τ2q−3 + ( 2q − 1 2 ) τ2q−2 + ( q − 1 2 ) τ2q−1 113 K. Kumegawa, T. Maruta / J. Algebra Comb. Discrete Appl. 5(2) (2018) 101–116 giving λ2 ≤ (6q3−18q2 + 24q + 37)/6 if ∆ has spectrum (D) and if q ≡ 2 mod 3. On the other hand, (21) yields λ2 ≥ q3 −2q2 −5q−3, giving a contradiction for q ≥ 11. One can get a contradiction similarly for the other cases. This completes the proof. 5. Proof of Theorem 1.5 Lemma 5.1. There exists no [gq(4,d), 4,d]q code for d = q3 −q2 − 4q − 2 for q ≥ 9. Proof. Let C be a putative [n = q3 − 4q− 6, 4,d = q3 −q2 − 4q− 2]q code. Note that n = gq(4,d) and hence γ0 = 1, γ1 = q, γ2 = n − d = q2 − 4 from (1). Let ∆ be a γ2-plane and let δ be an i-plane. By Lemma 2.13, the spectrum of ∆ satisfies τj = 0 for 1 ≤ j ≤ q−5. Since a t-line in δ satisfies t ≤ (i+ 6)/q, we have ai = 0 for 1 ≤ i ≤ q − 7. Assume i = sq − 6 + e with 0 ≤ e ≤ q − 1. For 2 ≤ s ≤ q − 5, we have γ1(δ) ≤ s−1 by Lemma 2.3 (5). Then, it follows from Lemma 2.6 (1) that i ≤ (s−2)q+s−1 < sq−6+e, a contradiction. For s = q−4, from Lemma 2.6 (2), we have i ≤ (q−5)q+q−4−3 < i, a contradiction again. Similarly, using Lemma 2.6 and Table 1, we can deduce that ai = 0 for all i /∈ {0,q2 − 6,q2 − 5,q2 − 4} for q ≥ 11 and that ai = 0 for all i /∈ {0, 48, 75, 76, 77} for q = 9. For q = 9, a 48-plane has a 0-line [24], but the equation (4) with (i,t) = (48, 0) has no solution. Hence a48 = 0. From (4), we have a0 = 0 or 1. The equality (3) gives aq2−6 = (q 4 + 4q3 − 9q2 + 14q + 2)/2 − ( q2 − 4 2 ) a0 ≥ 2q3 + 7q − 9 > θ3, a contradiction. Lemma 5.2. There exists no [gq(4,d), 4,d]q code for d = q3 −q2 − 6q for q ≥ 9. Proof. Let C be a putative [n = q3 − 6q− 6, 4,d = q3 −q2 − 6q]q code. Then, n = gq(4,d) and γ0 = 1, γ1 = q, γ2 = n−d = q2 − 6 from (1). Let ∆ be a γ2-plane and let δ be an i-plane. By Lemma 2.13, the spectrum of ∆ satisfies τj = 0 for 1 ≤ j ≤ q− 7. Since a t-line in δ satisfies t ≤ (i + 6)/q, we have ai = 0 for 1 ≤ i ≤ q−7. Using Lemmas 2.3, 2.6 and Table 1 similarly to the proof of Lemma 5.1, we can deduce that ai = 0 for all i /∈ {0,q2 − 6} for q ≥ 11 and that ai = 0 for all i /∈ {0, 48, 75} for q = 9. Since the equation (4) with (i,t) = (0, 0) has no solution for q ≥ 9, we obtain a0 = 0. Then, the three equations in Lemma 2.1 have no solution for q = 9, a contradiction. We also get a contradiction for q ≥ 11 from Lemma 2.2. Lemma 5.3. There exists no [gq(4,d), 4,d]q code for d = q3 −q2 − 6q − 1 for q ≥ 9. Proof. Let C be a putative [n = q3 − 6q− 7, 4,d = q3 −q2 − 6q− 1]q code. Then, n = gq(4,d), γ0 = 1, γ1 = q, γ2 = n − d = q2 − 6 from (1). Let ∆ be a γ2-plane and let δ be an i-plane. By Lemma 2.13, the spectrum of ∆ satisfies τj = 0 for 1 ≤ j ≤ q − 7. Since a t-line in δ satisfies t ≤ (i + 7)/q, we have ai = 0 for 1 ≤ i ≤ q − 8. Using Lemmas 2.3, 2.6 and Table 1, it can be shown that ai = 0 for all i /∈{0,q2 − 3q − 7,q2 − 7,q2 − 6} for q ≥ 11 and that ai = 0 for all i /∈{0, 47, 48, 65, 74, 75} for q = 9. Suppose a0 > 0. It follows from (4) that a0 = 1 and that aj = 0 for 0 < j < q2 − 7. Then, C is extendable by Theorem 2.11, contradicting Lemma 5.2. Hence a0 = 0. Then, C is extendable by Theorem 2.9, a contradiction again. Lemma 5.4. There exists no [gq(4,d), 4,d]q code for d = q3 −q2 − 6q − 2 for q ≥ 9. Proof. Let C be a putative [n = q3 − 6q− 8, 4,d = q3 −q2 − 6q− 2]q code. Then, n = gq(4,d), γ0 = 1, γ1 = q, γ2 = n−d = q2 − 6 from (1). Let ∆ be a γ2-plane and let δ be an i-plane. By Lemma 2.13, the spectrum of ∆ satisfies τj = 0 for 1 ≤ j ≤ q− 7. Since a t-line in δ satisfies t ≤ (i + 8)/q, we have ai = 0 for 1 ≤ i ≤ q − 9 for q ≥ 11. Using Lemmas 2.3, 2.6 and Table 1, it can be shown that 114 K. Kumegawa, T. Maruta / J. Algebra Comb. Discrete Appl. 5(2) (2018) 101–116 ai = 0 for all i /∈{0,q2 − 4q − 8,q2 − 3q − 8,q2 − 3q − 7,q2 − 8,q2 − 7,q2 − 6} for q ≥ 13, ai = 0 for all i /∈{0, 102, 113, 114, 115} for q = 11, ai = 0 for all i /∈{0, 28, 37, 46, 47, 48, 55, 64, 65, 73, 74, 75} for q = 9. Suppose a0 > 0. It follows from (4) that a0 = 1 and that aj = 0 for 0 < j < q2 − 8 for q ≥ 9. Then, the equality (3) gives aq2−8 = 3q3 + 10q − 20 > θ3, a contradiction. Hence a0 = 0. Then, C is extendable by Theorem 2.10, a contradiction again. The following three lemmas can be proved similarly to Lemmas 5.2, 5.3, 5.4, respectively. Lemma 5.5. There exists no [gq(4,d), 4,d]q code for d = q3 −q2 − 5q for q ≥ 9. Lemma 5.6. There exists no [gq(4,d), 4,d]q code for d = q3 −q2 − 5q − 1 for q ≥ 9. Lemma 5.7. There exists no [gq(4,d), 4,d]q code for d = q3 −q2 − 5q − 2 for q ≥ 9. Now, Theorem 1.5 follows from Lemmas 5.1, 5.4, 5.7. This completes the proof. 6. Conclusion To solve the problem finding the exact values of nq(k,d) for all d for fixed q and k, it is sufficient to determine nq(k,d) for finite values of d since nq(k,d) = gq(k,d) for all d ≥ (k−2)qk−1 −(k−1)qk−2 + 1, k ≥ 3 for all q [17]. For k = 4, it is known that nq(4,d) = gq(4,d) for q3 − q2 − q + 1 ≤ d ≤ q3 + q2 + q, d ≥ 2q3 − 3q2 + 1 for all q and for 2q3 − 5q2 + 1 ≤ d ≤ 2q3 − 5q2 + 3q for q ≥ 7 ([18, 21]). The key contribution here is showing the non–existence of [gq(4,d), 4,d]q codes for many values of d close to these "Griesmer area", and it seems reasonable to seek a generalization for larger k. To this direction, see [3] and [4]. References [1] S. Ball, Table of bounds on three dimensional linear codes or (n,r)–arcs in PG(2,q), 2018, available at https://mat-web.upc.edu/people/simeon.michael.ball/codebounds.html [2] A. Bonisoli, Every equidistant linear code is a sequence of dual Hamming codes, Ars Combin. 18 (1984) 181–186. [3] E. J. Cheon, The non–existence of Griesmer codes with parameters close to codes of Belov type, Des. Codes Cryptogr. 61(2) (2011) 131–139. [4] E. J. Cheon, T. Maruta, On the minimum length of some linear codes, Des. Codes Cryptogr. 43(2–3) (2007) 123–135. [5] N. Hamada, A characterization of some [n,k,d; q]–codes meeting the Griesmer bound using a mini- hyper in a finite projective geometry, Discrete Math. 116(1–3) (1993) 229–268. [6] R. Hill, An extension theorem for linear codes, Des. Codes Cryptogr. 17(1–3) (1999) 151–157. [7] R. Hill, P. Lizak, Extensions of linear codes, Proc. 1995 IEEE International Symposium on Informa- tion Theory, 1995, p. 345. [8] J. W. P. Hirschfeld, Projective Geometries over Finite Fields, Second Edition, Clarendon Press, Oxford, 1998. [9] J. W. P. Hirschfeld, L. Storme, The packing problem in statistics, coding theory and finite projective spaces: update 2001, in: A. Blokhuis et al. (eds.), Finite Geometries, Developments in Mathematics Vol. 3, Springer, (2001) 201–246. 115 https://mat-web.upc.edu/people/simeon.michael.ball/codebounds.html https://mat-web.upc.edu/people/simeon.michael.ball/codebounds.html https://mathscinet.ams.org/mathscinet-getitem?mr=823843 https://mathscinet.ams.org/mathscinet-getitem?mr=823843 https://doi.org/10.1007/s10623-010-9443-3 https://doi.org/10.1007/s10623-010-9443-3 https://doi.org/10.1007/s10623-007-9070-9 https://doi.org/10.1007/s10623-007-9070-9 https://doi.org/10.1016/0012-365X(93)90404-H https://doi.org/10.1016/0012-365X(93)90404-H https://doi.org/10.1023/A:1008319024396 https://doi.org/10.1109/ISIT.1995.550332 https://doi.org/10.1109/ISIT.1995.550332 https://doi.org/10.1007/978-1-4613-0283-4_13 https://doi.org/10.1007/978-1-4613-0283-4_13 https://doi.org/10.1007/978-1-4613-0283-4_13 K. Kumegawa, T. Maruta / J. Algebra Comb. Discrete Appl. 5(2) (2018) 101–116 [10] Y. Kageyama, T. Maruta, On the geometric constructions of optimal linear codes, Des. Codes Cryp- togr. 81(3) (2016) 469–480. [11] R. Kanazawa, T. Maruta, On optimal linear codes over F8, Electron. J. Combin. 18(1) (2011) #P34. [12] K. Kumegawa, T. Maruta, Non–existence of some Griesmer codes over Fq, Discrete Math. 339(2) (2016) 515–521. [13] K. Kumegawa, T. Okazaki, T. Maruta, On the minimum length of linear codes over the field of 9 elements, Electron. J. Combin. 24(1) (2017) #P1.50. [14] I. N. Landjev, Optimal linear codes of dimension 4 over GF(5), Lecture Notes in Comp. Science 1255 (1997) 212–220. [15] I. N. Landjev, T. Maruta, On the minimum length of quaternary linear codes of dimension five, Discrete Math. 202(1–3) (1999) 145–161. [16] I. Landjev, A. Rousseva, The non–existence of (104, 22; 3, 5)–arcs, Adv. Math. Commun. 10(3) (2016) 601–611. [17] T. Maruta, On the achievement of the Griesmer bound, Des. Codes Cryptogr. 12(1) (1997) 83–87. [18] T. Maruta, On the minimum length of q–ary linear codes of dimension four, Discrete Math. 208–209 (1999) 427–435. [19] T. Maruta, On the non–existence of q–ary linear codes of dimension five, Des. Codes Cryptogr. 22(2) (2001) 165–177. [20] T. Maruta, A new extension theorem for linear codes, Finite Fields Appl. 10(4) (2004) 674–685. [21] T. Maruta, Construction of optimal linear codes by geometric puncturing, Serdica J. Comput. 7(1) (2013) 73–80. [22] T. Maruta, Griesmer bound for linear codes over finite fields, 2018, available at http://www.mi.s.osakafu-u.ac.jp/∼maruta/griesmer/ [23] T. Maruta, I. N. Landjev, A. Rousseva, On the minimum size of some minihypers and related linear codes, Des. Codes Cryptogr. 34(1) (2005) 5–15. [24] T. Maruta, A. Kikui, Y. Yoshida, On the uniqueness of (48, 6)–arcs in PG(2, 9), Adv. Math. Commun. 3(1) (2009) 29–34. [25] T. Maruta, Y. Oya, On optimal ternary linear codes of dimension 6, Adv. Math. Commun. 5(3) (2011) 505–520. [26] T. Maruta, Y. Yoshida, A generalized extension theorem for linear codes, Des. Codes Cryptogr. 62(1) (2012) 121–130. [27] M. Takenaka, K. Okamoto, T. Maruta, On optimal non–projective ternary linear codes, Discrete Math. 308(5–6) (2008) 842–854. [28] Y. Yoshida, T. Maruta, An extension theorem for [n,k,d]q codes with gcd(d,q) = 2, Aust. J. Combin. 48 (2010) 117–131. 116 https://doi.org/10.1007/s10623-015-0167-2 https://doi.org/10.1007/s10623-015-0167-2 https://mathscinet.ams.org/mathscinet-getitem?mr=2776810 https://doi.org/10.1016/j.disc.2015.09.030 https://doi.org/10.1016/j.disc.2015.09.030 https://mathscinet.ams.org/mathscinet-getitem?mr=3651932 https://mathscinet.ams.org/mathscinet-getitem?mr=3651932 https://doi.org/10.1007/3-540-63163-1_17 https://doi.org/10.1007/3-540-63163-1_17 https://doi.org/10.1016/S0012-365X(98)00354-9 https://doi.org/10.1016/S0012-365X(98)00354-9 http://dx.doi.org/10.3934/amc.2016029 http://dx.doi.org/10.3934/amc.2016029 https://doi.org/10.1023/A:1008250010928 https://doi.org/10.1016/S0012-365X(99)00088-6 https://doi.org/10.1016/S0012-365X(99)00088-6 https://doi.org/10.1023/A:1008317022638 https://doi.org/10.1023/A:1008317022638 https://doi.org/10.1016/j.ffa.2004.02.001 https://mathscinet.ams.org/mathscinet-getitem?mr=3204747 https://mathscinet.ams.org/mathscinet-getitem?mr=3204747 http://www.mi.s.osakafu-u.ac.jp/~maruta/griesmer/ http://www.mi.s.osakafu-u.ac.jp/~maruta/griesmer/ https://doi.org/10.1007/s10623-003-4191-2 https://doi.org/10.1007/s10623-003-4191-2 http://dx.doi.org/10.3934/amc.2009.3.29 http://dx.doi.org/10.3934/amc.2009.3.29 http://dx.doi.org/10.3934/amc.2011.5.505 http://dx.doi.org/10.3934/amc.2011.5.505 https://doi.org/10.1007/s10623-011-9497-x https://doi.org/10.1007/s10623-011-9497-x https://doi.org/10.1016/j.disc.2007.07.044 https://doi.org/10.1016/j.disc.2007.07.044 https://mathscinet.ams.org/mathscinet-getitem?mr=2732106 https://mathscinet.ams.org/mathscinet-getitem?mr=2732106 Introduction Preliminaries Proof of Theorem 1.2 Proof of Theorem 1.3 Proof of Theorem 1.5 Conclusion References