ISSN 2148-838Xhttps://doi.org/10.13069/jacodesmath.935947 J. Algebra Comb. Discrete Appl. 8(2) • 73–90 Received: 23 April 2020 Accepted: 24 November 2020 Journal of Algebra Combinatorics Discrete Structures and Applications On optimal linear codes of dimension 4∗ Research Article Nanami Bono, Maya Fujii, Tatsuya Maruta Abstract: In coding theory, the problem of finding the shortest linear codes for a fixed set of parameters is central. Given the dimension k, the minimum weight d, and the order q of the finite field Fq over which the code is defined, the function nq(k, d) specifies the smallest length n for which an [n, k, d]q code exists. The problem of determining the values of this function is known as the problem of optimal linear codes. Using the geometric methods through projective geometry, we determine nq(4, d) for some values of d by constructing new codes and by proving the nonexistence of linear codes with certain parameters. 2010 MSC: 94B05, 94B27, 51E20 Keywords: Optimal linear codes, Griesmer bound, Geometric method 1. Introduction We denote by Fq the field of q elements. Let Fnq be the vector space of n-tuples over Fq. An [n,k,d]q code C is a k-dimensional subspace of Fnq with minimum weight d = min{wt(c) | c ∈ C,c 6= (0, . . . , 0)}, where wt(c) is the number of non-zero entries in the vector c. The weight distribution of C is the list of integers Ai where Ai is the number of codewords of weight i, 0 ≤ i ≤ n. The weight distribution with (A0,Ad, . . .) = (1,α, . . .) is also expressed as 01dα · · · . 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 [10, 11]. An [n,k,d]q code satisfies the inequality called the Griesmer bound [8, 10]: n ≥ gq(k,d) = k−1∑ i=0 ⌈ d/qi ⌉ , where dxe denotes the smallest integer greater than or equal to x. The values of nq(k,d) are determined for all d only for some small values of q and k. For k = 3, nq(3,d) is known for all d for q ≤ 9 [1]. See ∗ This research was partially supported by JSPS KAKENHI Grant Number 20K03722. Nanami Bono, Maya Fujii, Tatsuya Maruta (Corresponding Author); Department of Mathematical Sci- ences, Osaka Prefecture University, Sakai, Osaka 599-8531, Japan (email: bononanami@gmail.com, ddddy.maya0802@gmail.com, maruta@mi.s.osakafu-u.ac.jp). 73 https://orcid.org/0000-0001-7858-0787 N. Bono et. al. / J. Algebra Comb. Discrete Appl. 8(2) (2021) 73–90 [26] for the updated table of nq(k,d) for some small q and k. The following theorems give some known values of nq(4,d). Theorem 1.1 ([21, 25]). nq(4,d) = gq(4,d) for 1 ≤ d ≤ q−2, q2−2q + 1 ≤ d ≤ q2−q, q3−2q2 + 1 ≤ d ≤ q3−2q2 +q, q3−q2−q + 1 ≤ d ≤ q3 +q2−q, 2q3−5q2 + 1 ≤ d ≤ 2q3−5q2 + 3q and any d ≥ 2q3−3q2 + 1 for all q. Theorem 1.2 ([18, 21, 25]). nq(4,d) = gq(4,d) + 1 for the following d and q: (a) q2 −q + 1 ≤ d ≤ q2 − 1 with q ≥ 3, (b) q3 − 2q2 −q + 1 ≤ d ≤ q3 − 2q2 −b(q + 1)/2c with q ≥ 7, (c) 2q3 − 3q2 −q + 1 ≤ d ≤ 2q3 − 3q2 with q ≥ 4, (d) 2q3 − 3q2 − 2q + 1 ≤ d ≤ 2q3 − 3q2 −q with q ≥ 5. Our main results are the following theorems. Theorem 1.3. nq(4,d) = gq(4,d) for 2q3 − 4q2 + 1 ≤ d ≤ 2q3 − 4q2 + 2q for all q. Theorem 1.4. nq(4,d) = gq(4,d) + 1 for the following d and q: (a) 2q3 − 3q2 − 3q + 1 ≤ d ≤ 2q3 − 3q2 − 2q with q ≥ 7, (b) 2q3 − 4q2 − 3q + 1 ≤ d ≤ 2q3 − 4q2 with q ≥ 7, (c) 2q3 − 5q2 −q + 1 ≤ d ≤ 2q3 − 5q2 with q ≥ 7. We also tackle the problem to determine n8(4,d) for all d as a continuation of [14, 16, 24]. The problem to determine n8(4,d) for all d has been still open for the 447 values of d, see [26]. We determine n8(4,d) for 32 values of d and give new lower or upper bounds of n8(4,d) for 12 values of d as follows. Theorem 1.5. (a) n8(4,d) = g8(4,d) + 1 for d = 381-384, 574, 633-638, 690-701, 745-749, 809-812. (b) n8(4,d) ≤ g8(4,d) + 1 for d = 133, 134, 145, 194. (c) g8(4,d) + 1 ≤ n8(4,d) ≤ g8(4,d) + 2 for d = 173-176, 178, 179, 247, 248. Remark 1.6. (a) From Theorem 1.4 (a), the problem to determine nq(4,d) for d = 2q3 − 3q2 − 3q + 1 is still open only for q = 5, see [26]. (b) The nonexistence of a [gq(4,d), 4,d]q code for d = 2q3 −rq2 −q + 1 for 3 ≤ r ≤ q−q/p, q = ph with p prime, is proved in [19]. We conjecture that a [gq(4,d), 4,d]q code for d = 2q3 −rq2 − q + 1 with r = q −q/p− 1 does not exist for non-prime q ≥ 8, which is valid for q = 8, 9 by Theorem 1.5 and [17]. (c) We conjecture that nq(4,d) = gq(4,d) + 1 for q3 − 2q2 −q + 1 ≤ d ≤ q3 − 2q2 for all q ≥ 3. To prove this, we need to show the existence of a [gq(4,d) + 1, 4,d]q code for d = q3 − 2q2 by Theorem 1.2 (b). This is already known for q = 3, 4, 5 and is also valid for q = 8 by Theorem 1.5. We recall geometric methods through projective geometry and preliminary results in Section 2. We prove Theorem 1.3 and some upper bounds on nq(4,d) in Theorems 1.4 and 1.5 in Section 3. The proofs of Theorems 1.4 and 1.5 are completed by the nonexistence of some Griesmer codes, which are given in Section 4. 74 N. Bono et. al. / J. Algebra Comb. Discrete Appl. 8(2) (2021) 73–90 2. Geometric methods In this section, we give geometric methods to construct new codes or to prove the nonexistence of codes with certain parameters. We denote by PG(r,q) the projective geometry of dimension r over Fq. A j-flat is a projective subspace of dimension j in PG(r,q). The 0-flats, 1-flats, 2-flats, (r − 2)-flats and (r − 1)-flats are called points, lines, planes, secundums and hyperplanes, respectively. We denote by θj the number of points in a j-flat, i.e., θj = (qj+1 − 1)/(q − 1). 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. We see linear codes from this geometrical point of view. A point P in Σ is called an i-point if it has multiplicity mC(P) = 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. We denote by ∆1 + · · · + ∆s the multiset consisting of the s sets ∆1, ..., ∆s in Σ. We write s∆ for ∆1 + · · · + ∆s when ∆1 = · · · = ∆s. Then, MC = ∑γ0 i=1 iCi. For any subset S of Σ, we denote by MC(S) the multiset {mC(P)P | P ∈ S}. The multiplicity of S with respect to C, denoted by mC(S), is defined as the cardinality of MC(S), i.e., mC(S) = ∑ P∈S mC(P) = γ0∑ i=1 i·|S∩Ci|, where |T| denotes the number of elements in a set T. 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 in Σ. Such a partition of Σ is called an (n,n−d)-arc of Σ. Conversely an (n,n−d)-arc of Σ gives an [n,k,d]q code in the natural manner. A line l with t = mC(l) is called a t-line. A t-plane, a t-hyperplane and so on are defined similarly. For an m-flat Π in Σ we define γj(Π) = max{mC(∆) | ∆ ⊂ Π, ∆ ∈Fj}, 0 ≤ j ≤ m. Let λs(Π) be the number of s-points in Π. We denote simply by γj and by λs instead of γj(Σ) and λs(Σ), respectively. It holds that γk−2 = n−d, γk−1 = n. When C is Griesmer, the values γ0,γ1, ...,γk−3 are also uniquely determined ([22]) as follows: γj = j∑ u=0 ⌈ d qk−1−u ⌉ for 0 ≤ j ≤ k − 1. (1) When γ0 = 2, we obtain λ2 = λ0 + n−θk−1 (2) from λ0 + λ1 + λ2 = θk−1 and λ1 + 2λ2 = n. Denote by ai the number of i-hyperplanes in Σ. Note that ai = An−i/(q − 1) for 0 ≤ i ≤ n−d. (3) 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. Simple counting arguments yield the following: γk−2∑ i=0 ai = θk−1, (4) γk−2∑ i=1 iai = nθk−2, (5) 75 N. Bono et. al. / J. Algebra Comb. Discrete Appl. 8(2) (2021) 73–90 γk−2∑ i=2 i(i− 1)ai = n(n− 1)θk−3 + qk−2 γ0∑ s=2 s(s− 1)λs. (6) When γ0 ≤ 2, we get the following from (4)-(6): 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. (7) Lemma 2.1 ([17, 31]). Put � = (n−d)q−n and t0 = b(w + �)/qc, where bxc denotes the largest integer less than or equal to x. Let Π be a w-hyperplane through a t-secundum δ. Then t ≤ (w + �)/q and the following hold. (a) aw = 0 if an [w,k − 1,d0]q code with d0 ≥ w − t0 does not exist. (b) γk−3(Π) = t0 if an [w,k − 1,d1]q code with d1 ≥ w − t0 + 1 does not exist. (c) Let cj be the number of j-hyperplanes through δ other than Π. Then ∑ j cj = q and∑ j (γk−2 − j)cj = w + �−qt. (8) (d) A γk−2-hyperplane with spectrum (τ0, . . . ,τγk−3 ) satisfies τt > 0 if w + �−qt < q. (e) If any γk−2-hyperplane has no t0-secundum, then mC(Π) ≤ t0 − 1. An [n,k,d]q code is called m-divisible if all codewords have weights divisible by an integer m > 1. Lemma 2.2 ([31]). Let C be an m-divisible [n,k,d]q code with q = ph, p prime, whose spectrum is (an−d−(w−1)m,an−d−(w−2)m, . . . ,an−d−m,an−d) = (αw−1,αw−2, . . . ,α1,α0), where m = pr for some 1 ≤ r < h(k − 2) satisfying λ0 > 0 and⋂ H∈Fk−2, mC(H) qt, then there exists an [n−θt,k,d′]q code C′ with d′ ≥ d−qt. The punctured code C′ in Lemma 2.4 can be constructed from C by removing the t-flat ∆ from the multiset MC. We denote the resulting multiset by 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 [25]. Lemma 2.5 ([3]). Let C1 be an [n1,k,d1]q code containing a codeword of weight d1 + m with m > 0 and let C2 be an [n2,k− 1,d2]q code. Then, adding MC2 to an (n1 −d1 −m)-hyperplane for C1 gives an [n1 + n2,k,d]q code with d = d1 + m if m < d2 and d = d1 + d2 if m ≥ d2. 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 the extendability of codes with certain parameters in Sections 4 and 5. Theorem 2.6 ([23],[32]). Let C be an [n,k,d]q code with q ≥ 5, d ≡ −2 (mod q), k ≥ 3. Then C is extendable if Ai = 0 for all i 6≡ 0,−1,−2 (mod q). Theorem 2.7 ([30]). 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. Theorem 2.8 ([29]). Let C be an [n,k,d]q code with q = 2h, h ≥ 3, d odd, k ≥ 3. Then C is extendable if Ai = 0 for all i 6≡ 0,d (mod q/2). A set of s lines in PG(2,q) is called an s-arc of lines if no three of which are concurrent. An f- multiset F in PG(2,q) is an (f,m)-minihyper if every line meets F in at least m points and if some line meets F in exactly m points with multiplicity. Lemma 2.9 ([20]). For x = q 2 + 1 with q even, every (x(q + 1),x)-minihyper in PG(2,q) is either the sum of x lines or the union of the lines forming a (q + 2)-arc of lines. 3. Construction results In this section, we prove Theorems 1.3, 1.4(b) and a part of Theorem 1.5. Lemma 3.1. There exist [n = 2q3 − 2q2 + 1 − t(q + 1), 4, 2q3 − 4q2 + 2q − tq]q codes for 0 ≤ t ≤ q − 1 for q ≥ 7. Proof. For q ≥ 7, let H be a hyperbolic quadric in PG(3,q), see [12] for hyperbolic quadric. Let l1 and l2 be two skew lines contained in H. Take two skew lines l3 and l4 contained in H meeting l1, l2 and four points P1, . . . ,P4 of H so that l1 ∩ l3 = P1, l1 ∩ l4 = P2, l2 ∩ l3 = P3, l2 ∩ l4 = P4. Let l5 = 〈P1,P4〉, l6 = 〈P2,P3〉 and ∆ij = 〈li, lj〉, where 〈χ1,χ2, · · · 〉 denotes the smallest flat containing χ1,χ2, · · · . We set C0 = l1 ∪ l2 ∪·· ·∪ l6, C1 = (∆13 ∪ ∆14 ∪ ∆23 ∪ ∆24 ∪H) \C0 77 N. Bono et. al. / J. Algebra Comb. Discrete Appl. 8(2) (2021) 73–90 and C2 = PG(3,q) \ (C0 ∪ C1). Then λ0 = 6q − 2, λ1 = 5q2 − 10q + 5, λ2 = q3 − 4q2 + 5q − 2, where λi = |Ci|, and the multiset C1 + 2C2 gives a Griesmer [2q3 −3q2 + 1, 4, 2q3 −5q2 + 3q]q code, say C. This construction is due to [16]. Next, take a line l contained in H such that l is skew to l3 and l4. Let l ∩ l1 = Q1, l ∩ l2 = Q2 and let δ1, . . . ,δq−1 be the planes through l other than 〈l, l1〉, 〈l, l2〉. Then each δi meets l1 and l2 in the points Q1 and Q2, respectively, and meets l3, . . . , l6 in some points out of l. Hence, we can take a line mi in δi with mi ∩ C0 = ∅ for 1 ≤ i ≤ q − 1 such that m1 ∩ l, · · · ,mq−1 ∩ l are distinct points. Now, take an elliptic quadric E and let E′ be the projection of E from a point R ∈ E \ ∆13 on to ∆13. Since mC(∆13) = q2 − 2q + 1, it follows from Lemma 2.5 that the multiset M′ = MC + E′ gives a [2q3−2q2 + 1, 4, 2q3−4q2 + 2q]q code, say C′. Applying Lemma 2.4 by deleting t of the lines m1, . . . ,mq−1, we get an [n = 2q3 − 2q2 + 1 − tθ1, 4,d = 2q3 − 4q2 + 2q − tq]q code. The code constructed by Lemma 3.1 is Griesmer for t = 0, 1 and the length satisfies n = gq(4,d) + 1 for 2 ≤ t ≤ q−1. Hence, Theorem 1.3 follows from the existence of Griesmer codes with d = 2q3 −4q2 + 2q, 2q3 − 4q2 + 3q by puncturing. We also have that nq(4,d) ≤ gq(4,d) + 1 for 2q3 − 5q2 + 2q + 1 ≤ d ≤ 2q3−4q2−2q. Since Theorem 1.4 (2) is already known for q ≥ 9 [19], it suffices to show the nonexistence of Griesmer codes for d = 2q3 − 4q2 − 3q + 1 for q = 7, 8, which is given in Section 4, see Lemma 4.1. Next, we give a method to construct good codes by some orbits of a given projectivity in PG(k−1,q). For a non-zero element α ∈ Fq, let R = Fq[x]/(xN − α) be the ring of polynomials over Fq modulo xN −α. We associate the vector (a0,a1, ...,aN−1) ∈ FNq with the polynomial a(x) = ∑N−1 i=0 aix i ∈ R. For g = (g1(x), ...,gm(x)) ∈ Rm, Cg = {(r(x)g1(x), ...,r(x)gm(x)) | r(x) ∈ R} is called the 1-generator quasi-twisted (QT) code with generator g. Cg is usually called quasi-cyclic (QC) when α = 1. When m = 1, Cg is called α-cyclic or pseudo-cyclic or constacyclic. All of these codes are generalizations of cyclic codes (α = 1, m = 1). Take a monic polynomial g(x) = xk − ∑k−1 i=0 aix i in Fq[x] dividing xN − α with non-zero α ∈ Fq, and let T be the companion matrix of g(x). Let τ be the projectivity of PG(k − 1,q) defined by T. We denote by [gn] or by [a0a1 · · ·ank−1] the k ×n matrix [P,TP,T2P,...,Tn−1P ], where P is the column vector (1, 0, 0, ..., 0)T (hT stands for the transpose of a row vector h). Then [gN ] generates an α−1-cyclic code. Hence one can construct a cyclic or pseudo-cyclic code from an orbit of τ. For non-zero vectors PT2 , ...,P T m ∈ F k q, we denote the matrix [P,TP,T2P,...,Tn1−1P ; P2,TP2, ...,T n2−1P2; · · · ; Pm,TPm, ...,Tnm−1Pm] by [gn1 ] + Pn22 + · · ·+ P nm m . Then, the matrix [g N ] + PN2 + · · ·+ PNm defined from m orbits of τ of length N generates a QC or QT code, see [28]. It is shown in [28] that many good codes can be constructed from orbits of projectivities. Example 3.2. Take g(x) = 1 +x+x2 +x4 ∈ F2[x] and a point Q(1, 0, 0, 1) ∈ PG(3, 2). Then, the matrix [g7] generates a cyclic Hamming [7, 4, 3]2 code and the matrix [g7] + Q7 =   1 0 0 0 1 0 1 1 1 0 1 0 0 1 0 1 0 0 1 1 1 0 0 1 1 1 0 1 0 0 1 0 1 1 0 0 1 0 0 1 1 1 0 0 0 1 0 1 1 1 0 1 0 0 1 1  . generates a QC [14, 4, 7]2 code with weight distribution 017887. Let F8 = {0, 1,α,α2, . . . ,α6}, with α3 = α + 1. For simplicity, we denote α,. . . ,α6 by 2, 3, . . . , 7 so that F8 = {0, 1, 2, . . . , 7}. It sometimes happens that QC or QT codes are divisible or can be extended to divisible codes. Lemma 3.3. There exists a [440, 4, 384]8 code. 78 N. Bono et. al. / J. Algebra Comb. Discrete Appl. 8(2) (2021) 73–90 Proof. Let C be the QC [40, 4, 32]8 code with generator matrix [11115] + 01215 + 01245 + 01415 + 01655 + 01715 + 10355 + 10535. Then C is a 4-divisible code with weight distribution 0132115536280040140. Applying Lemma 2.2, as the projective dual of C, one can get a 16-divisible [440, 4, 384]8 code C∗ with weight distribution 013843815400280. Lemma 3.4. There exist codes with parameters [156, 4, 134]8, [169, 4, 145]8, [208, 4, 179]8, [225, 4, 194]8 and [286, 4, 248]8. Proof. The QC codes with generator matrices [146413] + 100413 + 150413 + 152413 + 162513 + 114513 + 127213 + 164313 + 112613 +106213 + 114413 + 101713, [146413] + 100413 + 150413 + 152413 + 152313 + 142713 + 147113 + 144513 + 164313 +112613 + 106213 + 151013 + 101713, [146413] + 100413 + 150413 + 152413 + 152313 + 162513 + 147113 + 144513 + 123213 +112613 + 106213 + 140113 + 175213 + 173113 + 151013 + 101713, [100115] + 100415 + 150415 + 152315 + 142315 + 113315 + 175715 + 127715 + 123215 +127315 + 103615 + 130715 + 170715 + 126515 + 114415, [146413] + 100413 + 150413 + 152413 + 152313 + 142313 + 162513 + 142713 + 146513 +113313 + 123213 + 116013 + 123113 + 133013 + 106213 + 126513 + 114413 + 174013 +105013 + 127413 + 173113 + 101713 give the desired codes with the following weight distributions 0113418201361183138364140364144182148182, 011451365146637147546148364149182150273152273154182156911579116091, 011791092180637181728182546184728193364, 0119417851961050198420200210202105204210206210208105, 012483003256100126491, respectively. Since it is known that g8(4,d) + 1 ≤ n8(4,d) ≤ g8(4,d) + 2 for 381 ≤ d ≤ 384, Theorem 1.5 (a) for 381 ≤ d ≤ 384, Theorem 1.5 (b) and (c) for d = 178, 179, 247, 248 follow from Lemmas 3.3 and 3.4. 4. Nonexistence of some Griesmer codes Note that one can get an [n− 1,k,d− 1]q code from a given [n,k,d]q code by puncturing and that the nonexistence of an [n−1,k,d−1]q code implies the nonexistence of an [n,k,d]q code. Hence, to prove (a) and (b) of Theorem 1.4, it suffices to show the following. Lemma 4.1. There exists no [gq(4,d), 4,d]q code for d = 2q3 −sq2 − 3q + 1 with s = 3, 4 for q ≥ 7. Lemma 4.1 was proved for q ≥ 9 in [19]. It follows from Theorem 1.5(a) that Lemma 4.1 is valid for q = 8, see Lemmas 4.14 and 4.17 in this section. We can also prove Lemma 4.1 for q = 7, but we omit the proof here because it is quite similar to the proof for q = 8, see [6] for the detail. The existence of a [gq(4,d) + 1, 4,d]q code for d = 2q3 − 3q2 − 2q is obtained from the result in [15]. It is also known that nq(4,d) = gq(4,d) + 1 for 2q3 − 5q2 − q + 1 ≤ d ≤ 2q3 − 5q2 with q ≥ 7 except fpr q = 8 [18]. Hence, Theorem 1.4(c) follows from Theorem 1.5(a), see Lemma 4.12 below. In this section, we prove that there exists no [g8(4,d), 4,d]8 code for d = 173, 574, 633, 690, 697, 745, 809, giving Theorem 1.5. n8(3,d) is already known for all d as follows, see [1, 7, 26]. 79 N. Bono et. al. / J. Algebra Comb. Discrete Appl. 8(2) (2021) 73–90 Table 1. The spectra of some [n, 3, d]8 codes. parameters possible spectra reference [6, 3, 4]8 (a0, a1, a2) = (34, 24, 15) [14] [7, 3, 5]8 (a0, a1, a2) = (31, 21, 21) [14] [8, 3, 6]8 (a0, a1, a2) = (29, 16, 28) [14] [9, 3, 7]8 (a0, a1, a2) = (28, 9, 36) [14] [10, 3, 8]8 (a0, a2) = (28, 45) [14] [26, 3, 22]8 (a0, a2, a3, a4) = (10, 1, 16, 46) Lemma 4.3 [33, 3, 28]8 (a0, a3, a5) = (9, 16, 48) [16] (a0, a1, a4, a5) = (4, 5, 28, 36) (a0, a3, a4, a5) = (6, 10, 18, 39) [42, 3, 36]8 (a0, a4, a5, a6) = (4, 6, 24, 39) [2] (a0, a3, a5, a6) = (3, 7, 21, 42) (a0, a4, a6) = (3, 21, 49) (a0, a2, a4, a6) = (2, 3, 18, 50) [60, 3, 52]8 (a4, a6, a8) = (3, 16, 54) [16] (a0, a4, a7, a8) = (1, 1, 32, 39) (a0, a5, a6, a7, a8) = (1, 1, 3, 27, 41) (a0, a6, a7, a8) = (1, 1, 6, 24, 42) [61, 3, 53]8 (a0, a5, a7, a8) = (1, 1, 24, 47) [16] (a0, a6, a7, a8) = (1, 3, 21, 48) [62, 3, 54]8 (a0, a6, a7, a8) = (1, 1, 16, 55) [16] [63, 3, 55]8 (a0, a7, a8) = (1, 9, 63) [9] [64, 3, 56]8 (a0, a8) = (1, 72) [9] [69, 3, 60]8 (a5, a8, a9) = (1, 32, 40) [9] (a6, a7, a8, a9) = (1, 3, 27, 42) (a7, a8, a9) = (6, 24, 43) [70, 3, 61]8 (a6, a8, a9) = (1, 24, 48) [9] (a7, a8, a9) = (3, 21, 49) [71, 3, 62]8 (a7, a8, a9) = (1, 16, 46) [9] [72, 3, 63]8 (a8, a9) = (9, 64) [9] [73, 3, 64]8 a9 = 73 [9] [92, 3, 80]8 (a0, a8, a12) = (1, 9, 63) [20] (a4, a12) = (6, 67) (a4, a8, a12) = (1, 10, 62) (a8, a12) = (12, 61) [101, 3, 88]8 (a5, a13) = (5, 68) [20] (a9, a13) = (10, 63) [108, 3, 94]8 (a4, a6, a13, a14) = (1, 3, 16, 53) [16] (a5, a6, a12, a13, a14) = (2, 2, 1, 14, 54) (a5, a6, a12, a13, a14) = (1, 3, 1, 15, 53) (a6, a12, a13, a14) = (4, 1, 16, 52) (a6, a12, a14) = (4, 9, 60) 80 N. Bono et. al. / J. Algebra Comb. Discrete Appl. 8(2) (2021) 73–90 Theorem 4.2. n8(3,d) = g8(3,d) + 1 for d = 13-16, 29-32, 37-40, 43-48 and n8(3,d) = g8(3,d) for any other d. Lemma 4.3. Every [26, 3, 22]8 code has spectrum (a0,a2,a3,a4) = (10, 1, 16, 46). Proof. Let C be a [26, 3, 22]8 code. By (1), γ0 = 1 and γ1 = 4. Since (γ1 − γ0)θ1 + γ0 − 2 = 26, any t-line though a fixed 1-point satisfies t ≥ γ1 − 2 = 2. Hence, there is no 1-line. From (4)-(6), we obtain (a0,a2,a3,a4) = (s, 61 − 6s, 8s − 64, 76 − 3s) with 8 ≤ s ≤ 10. Let l1, . . . , l8 be 0-lines. Then, L = {l1, . . . , ls} forms an s-arc of lines, for (θ1 − 3)γ1 < 26. Suppose s = 8. Then, one can find a line l so that L∪{l} forms a 9-arc of lines since every 8-arc is contained in a 10-arc, see [13]. Since l meets l1, . . . , l8 in different points, l must be a 1-line, a contradiction. Similarly, we can rule out the case s = 9. Hence, our assertion follows. Lemma 4.4. There exists no [199, 4, 173]8 code. Proof. Let C be a putative Griesmer [199, 4, 173]8 code. Then, γ0 = 1, γ1 = 4, γ2 = 26 from (1). By Lemma 4.3, the spectrum of a γ2-plane ∆1 is (τ0,τ2,τ3,τ4) = (10, 1, 16, 46). An i-plane with a t-line satisfies t ≤ i + 9 8 (10) by Lemma 2.1. We have a1 = 0 from Lemma 2.1(e) since ∆1 has no 1-line. If a 14-plane δ exists, it follows from (10) that M(δ) gives a [14, 3, 12]8 code, which does not exist. In this way, using Theorem 4.2 and Lemma 2.1, one can get ai = 0 for all i 6∈ {0, 7-10, 15, 23-26}. We refer to this procedure as the first sieve in the proofs of the nonexistence results. From (7), we get ∑ i≤24 ( 26 − i 2 ) ai = 4259. (11) Lemma 2.1(c) gives ∑ j cj = 8 and ∑ j (26 − j)cj = w + 9 − 8t. (12) Suppose a0 > 0. Then, a0 = 1 and ai > 0 with i > 0 implies i ≥ 23. Setting w = t = 0 in (12), the maximum possible contribution of cj’s to the LHS of (11) is (c23,c26) = (3, 5). Hence we get 4259 = (LHS of (11)) ≤ 9 × 73 + 325 = 982, which contradicts (11). Hence a0 = 0. Now, setting w = 26 in (12), the maximum possible contribution of cj’s to the LHS of (11) are (c7,c10,c26) = (1, 1, 6) for t = 0; (c7,c26) = (1, 7) for t = 2; (c15,c26) = (1, 7) for t = 3; (c23,c26) = (1, 7) for t = 4. Hence we get 4259 = (LHS of (11)) ≤ 291 × 10 + 171 × 1 + 55 × 16 + 3 × 46 = 4099, a contradiction. This completes the proof. The following lemma is needed to prove the nonexistence of a [657, 4, 574]8 code. Lemma 4.5 ([24]). There exists no [658, 4, 575]8 code. Lemma 4.6 ([24]). The spectrum of a [83, 3, 72]8 code satisfies ai = 0 for all i with i /∈{3, 5, 7, 9, 11}. Lemma 4.7. There exists no [657, 4, 574]8 code. 81 N. Bono et. al. / J. Algebra Comb. Discrete Appl. 8(2) (2021) 73–90 Proof. Let C be a putative [657, 4, 574]8 code. Using Theorem 4.2 and Lemmas 2.1 and 4.6, one can get ai = 0 for all i 6∈ {33, 49, 65-73, 81-83} by the first sieve. From (7), we get∑ i≤81 ( 83 − i 2 ) ai = 64λ2 − 2583. (13) Lemma 2.1(c) gives ∑ j cj = 8 and ∑ j (83 − j)cj = w + 7 − 8t. (14) Suppose a72 > 0. From Table 1, the spectrum of a 72-plane is (τ8,τ9) = (9, 64). Setting i = 72, the maximum possible contributions of cj’s in (14) to the LHS of (13) are (c68,c83) = (1, 7) for t = 8; (c81,c82,c83) = (3, 1, 4) for t = 9. Hence we get 64λ2 − 2583 = (LHS of (13)) ≤ (105 × 1 + 0 × 7)9 + (1 × 3 + 0 × 1 + 0 × 4)64 + 55 = 1192, giving λ2 ≤ 58. On the other hand, we have λ2 = λ0 + 72 = 72 from (2), a contradiction. Hence a72 = 0. Similarly, we can prove a71 = a70 = a69 = a68 = 0. Applying Theorem 2.6, C is extendable, which contradicts Lemma 4.5. This completes the proof. As 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 (7), (8) 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. Lemma 4.8. There exists no [725, 4, 633]8 code. Proof. Let C be a putative Griesmer [725, 4, 633]8 code. Then, γ0 = 2, γ1 = 12, γ2 = 92 by (1). From Table 1, the spectrum of a γ2-plane ∆1 is one of the following: (A) (τ0,τ8,τ12) = (1, 9, 63) with λ′0 = 9, (B) (τ4,τ12) = (6, 67) with λ ′ 0 = 15, (C) (τ4,τ8,τ12) = (1, 10, 62) with λ′0 = 5, (D) (τ8,τ12) = (12, 61) with λ ′ 0 = 3, where λ′0 = λ0(∆1). Using Theorem 4.2 and Lemma 2.1, one can get ai = 0 for all i 6∈ {0,21-28, 53-64, 69-73, 85-92} by the first sieve. From (7), we get ∑ i≤90 ( 92 − i 2 ) ai = 64λ2 − 5315. (15) Lemma 2.1(c) gives ∑ j cj = 8 and ∑ j (92 − j)cj = w + 11 − 8t. (16) We first prove ai = 0 for 0 ≤ i ≤ 28. Assume a t-plane δt with 0 ≤ t ≤ 28 exists. Then, the multiset MC + δt gives an [N = 798, 4,D = 697]8 code C′ since mC′(δt) = t + θ2 ≤ 28 + 73 ≤ 101 and since N = n + θ2 = 725 + 73 = 798 and N −D = n−d + θ1 = 92 + 9 = 101. This contradicts that a [798, 4, 697]8 code does not exist by Lemma 4.12. Hence, ai = 0 for all 0 ≤ i ≤ 28. Since ∆1 has no 9-line, we have a73 = 0. We can prove ai = 0 for i = 72, 71, 70, 69, 64, 63, 62, 61, 60 by (λ2, i)-ROM using the possible spectra of an i-plane in Table 1. Next, we prove ai = 0 for 53 ≤ i ≤ 59. Suppose a53 > 0 and let δ53 be a 53-plane with spectrum (τ0, . . . ,τ8). Then, we have ∑ i≤7 ( 8 − i 2 ) τi = 83. (17) 82 N. Bono et. al. / J. Algebra Comb. Discrete Appl. 8(2) (2021) 73–90 Setting w = 53 in (16), the maximum possible contribution of cj’s to the left hand side of (15) are (c53,c85,c88,c92) = (1, 3, 1, 3) for t = 0; (c53,c85,c87,c91) = (1, 1, 1, 5) for t = 1; (c53,c89,c91) = (1, 1, 6) for t = 2; (c59,c91) = (1, 7) for t = 3; (c85,c88,c92) = (4, 1, 3) for t = 4; (c85,c87,c91) = (2, 1, 5) for t = 5; (c85,c89,c91) = (1, 1, 6) for t = 6; c91 = 8 for t = 7; c92 = 8 for t = 8 since c92 = 0 for t = 1, 2, 3, 5, 6, 7. Hence we get 64λ2 − 5315 = (LHS of (15)) ≤ 810τ0 + 772τ1 + 744τ2 + 528τ3 + 90τ4 + 52τ5 + 24τ6 < 53 × (17) = 4399 giving λ2 ≤ 151. On the other hand, we have λ2 = 140 + λ0 ≥ 140 + 73 − 53 ≥ 160, a contradiction. Hence a53 = 0. We can prove a54 = a55 = a56 = a57 = a58 = a59 = 0 similarly, see [6] for the detail. Now, we have ai = 0 for all i < 85. Setting w = 92, (16) has no solution for t = 0, 4. Hence every 92-plane has spectrum (D). Then, we get a contradiction by (λ2, 92)-ROM. This completes the proof. Lemma 4.9. Let C be a [101, 3, 88]8 code and let Σ = PG(2, 8). Then, (A) C has spectrum (a5,a13) = (5, 68) with λ0 = 10 and MC = 2Σ − (l1 + · · · + l5), where {l1, . . . , l5} is a 5-arc of lines; or (B) C has spectrum (a9,a13) = (10, 63) with λ0 = 0 and MC = 2Σ −L, where L is the union of a 10-arc of lines. Proof. Let C be a [101, 3, 88]8 code. Then γ0 = 2 from (1) since C is Griesmer. Hence, our assertion follows from Lemma 2.9 since the multiset 2Σ −MC is a (45, 5)-minihyper. Lemma 4.10. Every [100, 3, 87]8 code C is extendable and its spectrum is one of the following: (a) (a5,a12,a13) = (5, 9, 59), (b) (a4,a5,a12,a13) = (1, 4, 8, 60), (c) (a8,a9,a12,a13) = (2, 8, 7, 56), (d) (a9,a12,a13) = (10, 9, 54). Proof. Let C be a [100, 3, 87]8 code. By Lemma 1, γ0 = 2 and γ1 = 13. Since (γ1 −γ0)θ1 + γ0 −1 = n, the lines though a fixed 2-point is one 12-line and eight 13-lines, and a10 = a11 = 0. Let l be a t-line containing a 1-point P. Considering the lines through P, we get n ≤ (γ1 − 1)8 + t, so 4 ≤ t. Hence a1 = a2 = a3 = 0. Suppose a 0-line l0 exists. Since there is no 9-line, for a point P on l0, there are four 12-lines and four 13-lines through P. Hence, the spectrum is (a0,a12,a13) = (1, 36, 36), Then, from (6), we have λ2 = 648−4950/8, a contradiction. Hence, there is no 0-line. Next, assume a6 > 0 and let l6 be a 6-line. For a 1-point P on l6, there are exactly two 12-lines and six 13-lines through P . Hence a9 = 0. For a 0-point Q on l6, there are at most two lines whose multiplicities are less than 9. Hence we have∑ i≡n,n−d ai ≤ (9 − 6)2 + 1 = 7, and C is extendable by Theorem 2.7. One can prove this similarly when a7 > 0. Finally, assume a6 = a7 = 0. Then, we have ai = 0 for all i 6∈ {4, 5, 8, 9, 12, 13}, which implies that Ai = 0 for all i 6≡ 0, 87 mod 4. Hence, C is extendable by Theorem 2.8. Assume that adding a point P to the multiset MC gives a 101-plane δ corresponding to a [101, 3, 88]8 code. Then, δ satisfies (A) or (B) in the previous lemma. So, one can get the spectra (a)-(d) according to the cases (a) P is a 2-point on δ with case (A); (b) P is a 1-point from a 5-line on δ with case (A); (c) P is a 1-point from a 9-line on δ with case (B); (d) P is a 2-point on δ with case (B), respectively. Lemma 4.11. There exists no [790, 4, 690]8 code. Proof. Let C be a putative Griesmer [790, 4, 690]8 code. Then, we have γ0 = 2, γ1 = 13, γ2 = 100 from (1). Since (γ1−γ0)θ2+γ0−15 = 790, an i-plane containing a 2-point satisfies i ≥ (γ1−γ0)θ1+γ0−15 = 86. From Table 1, the spectrum of a γ2-plane ∆1 is one of the following: (A) (τ5,τ12,τ13) = (5, 9, 59), (B) (τ4,τ5,τ12,τ13) = (1, 4, 8, 60), (C) (τ8,τ9,τ12,τ13) = (2, 8, 7, 56), (D) (τ9,τ12,τ13) = (10, 9, 54). 83 N. Bono et. al. / J. Algebra Comb. Discrete Appl. 8(2) (2021) 73–90 By the first sieve, one can get ai = 0 for all i 6∈ {22-28, 30-33, 54-73, 86-92, 94-100}. From (7), we get∑ i≤98 ( 100 − i 2 ) ai = 64λ2 − 8685. (18) Lemma 2.1(c) gives ∑ j cj = 8 and ∑ j (100 − j)cj = w + 10 − 8t. (19) We first prove ai = 0 for 22 ≤ i ≤ 33. Assume a t-plane δt with 22 ≤ t ≤ 33 exists. Then, the multiset MC + δt gives an [N = 863, 4,D = 754]8 code C′ since mC′(δt) = t + θ2 ≤ 33 + 73 ≤ 109 and since N = n + θ2 = 790 + 73 = 863 and N −D = n−d + θ1 = 790 − 690 + 9 = 109. This contradicts that a [863, 4, 754]8 code does not exist, see [26]. Hence, ai = 0 for all i ≤ 33. We can prove ai = 0 for i = 73, 72, 71, 70, 64, 63, 62, 61, 60, 69 in this order by (λ2, i)-ROM using the possible spectra of each i-plane from Table 1. Suppose a68 > 0 and let δ68 be a 68-plane. Since δ68 corresponds to a Griesmer [68, 3, 59]8 code, M(δ68) is obtained from δ68 by deleting five points, and the spectrum of δ68 is one of the following: (a) (τ4,τ8,τ9) = (1, 40, 32), (b) (τ5,τ7,τ8,τ9) = (1, 4, 33, 35), (c) (τ6,τ7,τ8,τ9) = (1, 7, 28, 37), (d) (τ6,τ7,τ8,τ9) = (2, 4, 31, 36), (e) (τ7,τ8,τ9) = (10, 25, 38). One can get a contradiction by the usual (λ2, 68)-ROM for the possible spectra (b)-(e). Hence δ68 has spectrum (a). From (19), there is at most one i-plane with i ≤ 68 other than δ68. We may assume that δ68 meets ∆1 in a 9-line. Then ∆1 has spectrum (C) or (D). Setting w = 100 in (19), the maximum possible contributions of cj’s to the LHS of (18) are (c54,c100) = (1, 7) for t = 8; (c86,c96,c100) = (3, 1, 4) for t = 8 when cj = 0 for j < 86; (c65,c97,c100) = (1, 1, 6) for t = 9; (c86,c90,c100) = (2, 1, 5) for t = 9 when cj = 0 for j < 86; (c86,c100) = (1, 7) for t = 12; (c94,c100) = (1, 7) for t = 13. Hence, we get 64λ2 − 8685 = (LHS of (18)) ≤ 1035 + 279(τ8 − 1) + 227τ9 + 91τ12 + 15τ13 = 4607 for the spectrum (C), giving λ2 ≤ 207. On the other hand, we have λ2 = λ0 +205 ≥ 205+(73−69) = 209, a contradiction. Similarly, we get a contradiction for spectrum (D). Hence a68 = 0. One can also prove a67 = a66 = 0 as well. Suppose a54 > 0. Let δ54 be a 54-plane and l be 8-line in δ54. Then, the other planes through l other than δ54 are 100-planes of spectrum (C), say ∆1, . . . , ∆8. Suppose that there is no plane with no 2-point meeting l in a 1-point. Then, one can get a contradiction by (λ2, 100)-ROM using the spectrum (C) of a 100-plane. So, there is a plane δ with no 2-point meeting l in a 1-point P . Since δ meets each of ∆1, . . . , ∆8 in a 9-line, we have mC(δ) ≥ (9 − 1)8 + 1 = 65, whence δ is a 65-plane with spectrum (τ1,τ8,τ9) = (1, 64, 8). Then, we get a a contradiction by (λ2, 65)-ROM. Hence a54 = 0. Similarly, we can prove a55 = a56 = a57 = a58 = a59 = 0. Suppose a65 > 0 and let δ65 be a 65-plane. Let l be a 9-line on δ65 and take a 100-plane ∆1 through l. Since δ65 has no 2-point, there are eight 0-points in δ65, and there are at most two lines on δ65 whose multiplicities are at most 5. Since any other 65-plane meets δ65 in some t-line with t ≤ 5 and since the spectrum of ∆1 is (C) or (D), we have a65 ≤ 3 from (19) with w = 100. Setting w = 100 in (19), the maximum possible contributions of cj’s to the LHS of (18) are (c65,c89,c100) = (1, 1, 6) for t = 8; (c86,c96,c100) = (3, 1, 4) for t = 8 with c65 = 0; (c65,c97,c100) = (1, 1, 6) for t = 9; (c86,c90,c100) = (2, 1, 5) for t = 9 with c65 = 0; (c86,c100) = (1, 7) for t = 12; (c94,c100) = (1, 7) for t = 13. It follows from λ2 = λ0 + 205 ≥ 205 + (73 − 65) = 213 that one can get a contradiction by (λ2, 100)-ROM as 64λ2 − 8685 = (LHS of (18)) ≤ 650τ8 + 227τ9 + 91τ12 + 15τ13 = 4593 when ∆1 has spectrum (C) and 64λ2 − 8685 = (LHS of (18)) ≤ 598 × 2 + 227(τ9 − 2) + 91τ12 + 15τ13 = 4641 84 N. Bono et. al. / J. Algebra Comb. Discrete Appl. 8(2) (2021) 73–90 when ∆1 has spectrum (D) since a65 ≤ 3, giving λ2 ≤ 208. Hence, a65 = 0. Now, we have ai = 0 for all i < 86. One can get a contradiction by (λ2, 100)-ROM using the possible spectra (A)-(D) as usual. This completes the proof. Lemma 4.12. There exists no [798, 4, 697]8 code. Proof. Let C be a putative Griesmer [798, 4, 697]8 code. By Lemma 4.9, the spectrum of a γ2-plane ∆1 is either (A) (τ5,τ13) = (5, 68) or (B) (τ9,τ13) = (10, 63). Using Theorem 4.2 and Lemma 2.1, one can get ai = 0 for all i 6∈ {30-33, 62-73, 94-101} by the first sieve. It follows from (7) that ∑ i≤99 ( 101 − i 2 ) ai = 64λ2 − 9123. (20) Lemma 2.1(c) gives ∑ j cj = 8 and ∑ j (101 − j)cj = w + 10 − 8t. (21) One can deduce that ai = 0 by (λ2, i)-ROM for 70 ≤ i ≤ 73 using the possible spectra of the [73 − j, 3, 64 − j]8 codes for 0 ≤ j ≤ 3, see Table 1. Suppose a30 > 0 and let δ30 be a 30-plane. It follows from (21) that a30 > 0 implies a30 = 1 and aj = 0 for other j < 94. Since γ1(δ30) = 5, one can find a 101-plane ∆ of spectrum (A) meeting δ30 in a 5-line. Take another 5-line l5 on ∆. Then, every plane through l5 has multiplicity at least 94, which is impossible from (21) with (w,t) = (101, 5). Hence a30 = 0. One can get a31 = a32 = a33 = 0, similarly. Then, using the possible spectra of the [70 − j, 3, 61 − j]8 codes, we can also prove that a70−j = 0 by (λ2, 70 − j)-ROM for 1 ≤ j ≤ 3. Now, we have ai = 0 for all i 6∈ {62-66, 94-101}. Note that a (62 + e)-plane with 0 ≤ e ≤ 3 could have a 2-point because it corresponds to a [62 + e, 3, 53 + e]8 code which is not Griesmer. Suppose a (62 + e)-plane δ with 0 ≤ e ≤ 3 has a 2-point. Then, one can find a 9-line l9 through the 2-point on δ and a 101-plane through l9 from (21) with (w,t) = (62 + e, 9). This contradicts that a 9-line in a 101-plane with spectrum (B) has no 2-point by Lemma 4.9. Thus, a (62 + e)-plane with 0 ≤ e ≤ 4 has no 2-point since a 66-plane corresponds to a Griesmer code. Suppose a62 > 0 and let δ62 be a 62-plane and let l be a 9-line on δ62. Then, the other planes through l are 101-planes, say ∆1, . . . , ∆8. For a fixed 1-point P on l, one can take a 9-line lj( 6= l) on ∆j for 1 ≤ j ≤ 8 from the geometric structure described in Lemma 4.9. Suppose that the plane δ = 〈l1, l2〉 is a (62 + e)-plane with 0 ≤ e ≤ 3 and let δ∩δ62 be an α-line. Since γ1(δ) = 9, δ contains all of l1, . . . , l8, and we have mC(δ) = 64 + α. One can rule out such cases by (λ2, 64 + α)-ROM. Hence, a62 > 0 implies that a62 = 1 and aj = 0 for other j < 94. Setting w = 101, the maximum possible contributions of cj’s in (21) to the LHS of (20) are (c62,c101) = (1, 7) for t = 9 with c62 > 0; (c94,c97,c101) = (5, 1, 2) for t = 9 with c62 = 0; (c94,c101) = (1, 7) for t = 13. Using the spectrum of a 101-plane of spectrum (B), one can get a contradiction by (λ2, 101)-ROM. Hence a62 = 0. One can similarly prove a63 = 0. To rule out a 101-plane of spectrum (A), let ∆1 be such a plane. From (21) with (w,t) = (101, 5), there exists a (64 + e)-plane with 0 ≤ e ≤ 2 through each of the 5-lines on ∆1. One can rule out such a 66-plane by (λ2, 66)-ROM using all possible spectra of a 66-plane with a 5-line. Hence a66 = 0. Note that λ0 ≥ 8 − 4 + 10 = 14 since a 101-plane of spectrum (A) has ten 0-points. Setting w = 101, the maximum possible contributions of cj’s in (21) to the LHS of (20) are (c64,c94,c95,c101) = (1, 4, 1, 2) for t = 5; (c94,c101) = (1, 7) for t = 13. Using the spectrum of a 101-plane of spectrum (A), one can get a contradiction by (λ2, 101)-ROM. Hence every 101-plane has spectrum (B). Suppose a66 > 0 and let δ66 be a 66-plane with spectrum (τ2, . . . ,τ9). Then, from the three equalities (4)-(6), we obtain τ2 + τ3 + τ4 ≤ 2 and τ5 + τ6 + τ7 ≤ 21. Setting w = 66, the maximum possible contributions of cj’s in (21) to the LHS of (20) are (c64,c94,c95,c99) = (1, 1, 1, 5) for t = 2 since a 100- plane has no 2-line by Lemma 4.10; (c94,c96,c100) = (4, 1, 3) for t = 5 since c101 = 0; (c96,c100) = (1, 7) 85 N. Bono et. al. / J. Algebra Comb. Discrete Appl. 8(2) (2021) 73–90 for t = 8; (c97,c101) = (1, 7) for t = 9. Using (τ2,τ5,τ8,τ9) = (2, 21, 49, 1) instead of all possible spectra of a 66-plane, one can get a contradiction by (λ2, 66)-ROM. Hence a66 = 0. we can prove a65 = a64 = 0 similarly. Hence, we have ruled out all possible i-planes with i < 94. Finally, using the spectrum (B) of a 101-plane, one can get a contradiction by (λ2, 101)-ROM. This completes the proof. Lemma 4.13. A [107, 3, 93]8 code C satisfies λ0 > 0. Proof. Suppose λ0 = 0. It follows from Lemma 2.4 that the multiset MC−PG(2, 8) gives a [34, 3, 29]8 code, which does not exist by Theorem 4.2, a contradiction. Lemma 4.14. There exists no [853, 4, 745]8 code. Proof. Let C be a putative Griesmer [853, 4, 745]8 code. From Table 1, the spectrum of a γ2-plane ∆1 is one of the following: (A) (τ4,τ6,τ13,τ14) = (1, 3, 16, 53), (B) (τ5,τ6,τ12,τ13,τ14) = (2, 2, 1, 14, 54), (C) (τ5,τ6,τ12,τ13,τ14) = (1, 3, 1, 15, 53), (D) (τ6,τ12,τ13,τ14) = (4, 1, 16, 52), (E) (τ6,τ12,τ14) = (4, 9, 60). One can get ai = 0 for all i 6∈ {21-33, 37-42, 61-64, 69-73, 85-108} by the first sieve. From (7), we get∑ i≤106 ( 108 − i 2 ) ai = 64λ2 − 12251. (22) Lemma 2.1(c) gives ∑ j cj = 8 and ∑ j (108 − j)cj = w + 9 − 8t. (23) We first prove ai = 0 for 21 ≤ i ≤ 42. Assume a t-plane δt with 21 ≤ t ≤ 42 exists. Then, the multiset MC + δt gives an [N = 926, 4,D = 809]8 code C′ since mC′(δt) = t + θ2 ≤ 42 + 73 ≤ 115 and since N = n + θ2 = 853 + 73 = 926 and N −D = n−d + θ1 = 853 − 745 + 9 = 117. This contradicts that a [926, 4, 809]8 code does not exist by Lemma 4.17. Hence, ai = 0 for all i ≤ 60. If a73 > 0, then any line on a 73-plane is a 9-line from Table 1, which contradicts that ∆1 has no 9-line. Hence a73 = 0. Similarly, a64 = a63 = a71 = a72 = 0. Suppose a62 > 0. The spectrum of a 62-plane is (τ0,τ6,τ7,τ8) = (1, 1, 16, 55) and a 62-plane meets ∆1 in a 6-line since the possible multiplicities of lines in ∆1 are 4, 5, 6, 12, 13, 14. Setting w = 62 in (23), the maximum possible contributions of cj’s to the LHS of (22) are (c106,c107) = (1, 7) for t = 8; (c98,c107) = (1, 7) for t = 7; (c85,c106,c108) = (1, 1, 6) for t = 6; (c42,c107) = (1, 7) for t = 0. Using the spectrum of a 62-plane, one can get a contradiction by (λ2, 62)-ROM since λ2 = λ0 + 268 ≥ 268. Hence a62 = 0. Similarly, we can prove a61 = a69 = a70 = 0 using the spectra from Table 1. Now, we have ai = 0 for all i < 85. Using the possible spectra (A)-(E) of a 108-plane, one can get a contradiction as follows. Take a 14-line L on a 108-plane so that L has no 0-point. Setting (w,t) = (108, 14) in (23), the solutions of cj’s are (c101,c108) = (1, 7), (c102,c107,c108) = (1, 1, 6), (c107,c108) = (7, 1) and so on. Counting the number of 0-points on the planes through L, we have λ0 ≥ 6 + 6 + 7 = 19 since a 108-plane has at least six 0-points and since a 107-plane has at least one 0-point by Lemma 4.13. Hence λ2 = λ0 + 268 ≥ 287. (24) Using the spectra (A)-(D) of a 108-plane, we get a contradiction by (λ2, 108)-ROM. Hence every 108-plane has spectrum (E). Then, we have 64λ2 − 12251 ≤ 6577, giving λ2 ≤ 294. (25) 86 N. Bono et. al. / J. Algebra Comb. Discrete Appl. 8(2) (2021) 73–90 Next, we rule out a possible 85-plane. Assume a 85-plane δ exists. Then, δ has a 12-line ` and the other planes through ` are 108-planes. Let s be the number of 0-points on `. Since s ≤ 3 and since a 108-plane of spectrum (E) has seven 0-point, we obtain λ2 = λ0 + 268 ≥ 268 + (7−s)8 + s ≥ 304, which contradicts (25). Hence, a85 = 0. Counting the number of 0-points on the planes through a fixed 14-line, the lower bound (24) can be improved to λ2 ≥ 289 since a 108-plane of spectrum (E) has seven 0-point. On the other hand, since the maximum possible contributions of cj’s in (23) with w = 108 to the LHS of (22) are (c86,c103,c108) = (3, 1, 4) for t = 6 and (c86,c108) = (1, 1, 6) for t = 12, the upper bound (25) can be also improved to λ2 ≤ 287, a contradiction. This completes the proof. We recall that the multiset for a [2q2 − q − 1, 3, 2q2 − 3q]q code with q ≥ 5 consists of two copies of PG(2,q) with three non-concurrent lines deleted [16]. The following code is obtained from this code by deleting two (not necessarily distinct) points. Lemma 4.15 ([16]). A [2q2 − q − 3, 3, 2q2 − 3q − 2]q code C′ with q ≥ 7 is extendable to a [2q2 − q − 1, 3, 2q2 − 3q]q code C and its spectrum is one of the following: (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), (e) (aq−1,a2q−3,a2q−1) = (3,q + 1,q2 − 3), according to the cases (a) P and Q are 1-points on the same (q− 1)-line on δ; (b) P and Q are 1-points from different (q − 1)-lines on δ; (c) P is a 1-point and Q is a 2-point on δ; (d) P and Q are distinct 2-points in on δ; (e) P and Q are the same 2-points in on δ, respectively, where P and Q are the points corresponding to the coordinates of C to be removed from the (2q2 −q− 1)-plane δ stated in the previous lemma. One can get the following similarly to Lemma 4.13. Lemma 4.16. A [116, 3, 101]8 code C satisfies λ0 > 0. Lemma 4.17. There exists no [926, 4, 809]8 code. Proof. Let C be a putative [926, 4, 809]8 code. From Lemma 4.15, the spectrum of a γ2-plane ∆ is one of the following: (A) (τ5,τ7,τ14,τ15) = (1, 2, 16, 54), (B) (τ6,τ7,τ13,τ14,τ15) = (2, 1, 1, 14, 55), (C) (τ6,τ7,τ13,τ14,τ15) = (1, 2, 1, 15, 54), (D) (τ7,τ13,τ14,τ15) = (3, 1, 16, 53), (E) (τ7,τ13,τ15) = (3, 9, 61). Using Theorem 4.2 and Lemma 2.1, we obtain ai = 0 for all i 6∈ {30-33,38-42,46-49,62-64,70-73,94-117} by the first sieve. From (7), we get ∑ i≤115 ( 117 − i 2 ) ai = 64λ2 − 17083. (26) Lemma 2.1(c) gives ∑ j cj = 8 and ∑ j (117 − j)cj = w + 10 −qt. (27) First, we prove ai = 0 for 30 ≤ i ≤ 33. Suppose a30 > 0 and let δ30 be a 30-plane. Then, it follows from (27) that a30 = 1 and any i-plane with i > 30 satisfies i ≥ 94. From Lemma 2.1, δ30 meets ∆ in a 5-line, say l, and ∆ has the spectrum (A). Recall from Lemma 4.15 that there are two 7-lines in the 117-plane of spectrum (A) meeting the 5-line in 0-points. Since the other planes ( 6= δ30, ∆) through l are 117-planes of spectrum (A), say ∆1, . . . , ∆7, and since there are four 0-points on l, one can take a 0-point Q on l which 87 N. Bono et. al. / J. Algebra Comb. Discrete Appl. 8(2) (2021) 73–90 is on at least four 7-lines, say l1, l2, l3, l4. Without loss of generality, we may assume that lj is on ∆j for 1 ≤ j ≤ 4. For the plane δ = 〈l1, l2〉, we have mC(δ) ≤ 7 + 7 + 5 + 15×6 = 109 since mC(δ30∩δ) ≤ 5. Since a 109-plane has no 15-line, we have mC(δ ∩ ∆j) = 7 for 1 ≤ j ≤ 4, and mC(δ) ≤ 7 × 4 + 5 + 14 × 4 = 89, a contradiction. Hence a30 = 0. One can similarly prove a31 = a32 = a33 = 0. If a73 > 0, then any line on a 73-plane is a 9-line from Table 1, which contradicts that ∆ has no 9-line. Hence a73 = 0. Similarly, a64 = a72 = 0. Using the spectrum of a w-plane from Table 1, one can get a contradiction by (λ2,w)-ROM for w = 62, 63, 70, 71. Hence, a62 = a63 = a70 = a71 = 0. Suppose a38 > 0. Then, a38 = 1 and aj > 0 with j 6= 38 implies j ≥ 94. Let δ0 be the 38-plane. Then, δ0 contains a 6-line, say L, and the other planes through L other than δ0 are 117-planes of spectrum (B) or (C), say ∆1, . . . , ∆8. Recall from Lemma 4.15 that there are two 7-lines (resp. one 6-line and one 7-line) in the 117-plane of spectrum (C) (resp. (B)) meeting the 6-line L in 0-points. Let lj and mj be the 6- or 7-lines in ∆j other than L. Since there are three 0-points on L, one can take a 0-point Q on l which is on at least six 6- or 7-lines. Without loss of generality, we may assume that l2 and l3 meet L in Q = l1 ∩L and that two of other lj,mj with j ≥ 2 meet L in Q′ = m1 ∩L. Note that there is no s-line with 7 < s < 14 in ∆1 through Q or Q′ by Lemma 4.15. Let δ be a t-plane through l1 other than ∆1. If t < 102, then δ meets ∆2 and ∆3 in l2 and l3, respectively, since a t-plane contains no 14- nor 15-line, whence mC(δ) ≤ 7 + 7 + 7 + |δ∩δ0|+ 5×14 ≤ 97. Then, from Lemma 2.1, δ contains no 14-plane, and we have mC(δ) ≤ 7 + 7 + 7 + 6 + 5 × 13 = 92, a contradiction. Hence any t-plane through l1 or m1 satisfies t ≥ 102. Take ∆1 as Π in Lemma 2.1, the maximum possible contribution of cj’s in (27) with w = 117 to the LHS of (26) are (c38,c117) = (1, 7) for t = 6 with c38 > 0; (c102,c113,c117) = (5, 1, 2) for t = 6 with c38 = 0; (c102,c106,c117) = (4, 1, 3) for t = 7; (c94,c117) = (1, 7) for t = 13; (c102,c117) = (1, 7) for t = 14; (c110,c117) = (1, 7) for t = 15. Note that λ2 = λ0 + 341 ≥ 341 + (73 − 38) + 8 = 384 since each of ∆1, . . . , ∆8 contains a 0-point out of L. Using the spectrum of a 117-plane of spectrum (B) or (C), one can get a contradiction by (λ2, 117)-ROM. Hence a38 = 0. One can prove a39 = a40 = a41 = a42 = 0 similarly. (When δ0 is a 42-plane, there are four 117-planes of spectrum (B) or (C), say ∆1, . . . , ∆4, through a fixed 6-line L in δ0, which contain 6- or 7-lines li,mj as above. It could happen that l2, l3, l4 meet L in Q = l1 ∩L, m2 meets L in Q′ = m1 ∩L and that m3 and m4 meet L in the remaining 0-point of L other than Q,Q′. In this case, any t-plane ( 6= 〈m1,m2〉) through m1 satisfies t ≥ 102. Considering this situation, one can get a contradiction by (λ2, 117)-ROM as above.) The above investigation for the case a38 > 0 is also valid to rule out possible i-planes for 46 ≤ i ≤ 49, see [6] for the detail. Now, we have ai = 0 for all i without 94 ≤ i ≤ 117. Using the spectrum (A)-(E) of a 117- plane, one can get a contradiction as follows. Take a 15-line with no 0-point on a 117-plane. Since the possible contributions of cj’s with w = 117 in (27) to the LHS of (26) are (c110,c117) = (1, 7), (c116,c117) = (7, 1) and so on for t = 15 and since a 116-plane has at least one 0-point by Lemma 4.16, we have λ2 = λ0 + 341 ≥ 341 + 3 + 3 × 1 + 1 × 7 ≥ 354. Hence, we can get a contradiction by (λ2, 117)- ROM when the spectrum of the w-plane is one of (A)-(D). Now, we may assume that any 117-plane has spectrum (E). We first rule out a possible 94-plane. Assume a 94-plane δ exists. Then, δ has a 13-line ` and the other planes through ` are 117-planes. Since ` has at most two 0-points and since ` is on a 117-plane of spectrum (E) which has four 0-points, we get λ2 = λ0 + 341 ≥ 341 + (4−2)8 + 2 ≥ 359. On the other hand, we obtain λ2 ≤ 358 by (λ2, 117)-ROM using the spectrum (E), a contradiction. Hence there is no 94-plane. Take a 15-line with no 0-point on a 117-plane. Counting the number of 0-points on the planes through the 15-line, we get a lower bound on λ2 as λ2 = λ0 + 341 ≥ 341 + 4 + 4×1 + 1×7 ≥ 356 since a 117-plane of spectrum (E) has four 0-points. Then, we get a contradiction by (λ2, 117)-ROM. This completes the proof. Now, Theorem 1.5 follows from Lemmas 4.4-4.17. Acknowledgment: The authors wish to express their thanks to the anonymous reviewers for their careful reading and valuable comments that improved the presentation and the content of the paper. 88 N. Bono et. al. / J. Algebra Comb. Discrete Appl. 8(2) (2021) 73–90 References [1] S. Ball, Table of bounds on three dimensional linear codes or (n,r)-arcs in PG(2,q), available at https://web.mat.upc.edu/people/simeon.michael.ball/codebounds.html. [2] A. Betten, E. J. Cheon, S. J. Kim, T. Maruta, The classification of (42, 6)8 arcs, Adv. Math. Commun. 5 (2011) 209–223. [3] I. Bouyukliev, Y. Kageyama, T. Maruta, On the minimum length of linear codes over F5, Discrete Math. 338 (2015) 938–953. [4] A. E. Brouwer, M. van Eupen, The correspondence between projective codes and 2-weight codes, Des. Codes Cryptogr. 11 (1997) 261–266. [5] M. van Eupen, R. Hill, An optimal ternary [69, 5, 45]3 codes and related codes, Des. Codes Cryptogr. 4 (1994) 271–282. [6] M. Fujii, Nonexistence of some Griesmer codes of dimension 4, Master Thesis, Osaka Prefecture University (2019). [7] M. Grassl, "Bounds on the minimum distance of linear codes and quantum codes." Online available at http://www.codetables.de. [8] J. H. Griesmer, A bound for error-correcting codes, IBM J. Res. Develop. 4 (1960) 532–542. [9] 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 (1993) 229–268. [10] R. Hill, Optimal linear codes, In: C. Mitchell(Ed.), Cryptography and Coding II, Oxford Univ. Press, Oxford (1992) 75–104. [11] R. Hill, E. Kolev, A survey of recent results on optimal linear codes, In: Combinatorial Designs and their Applications, F.C. Holroyd et al. Ed., Chapman and Hall/CRC Press Research Notes in Mathematics, CRC Press. Boca Raton (1999) 127–152. [12] J. W. P. Hirschfeld, Finite Projective Spaces of Three Dimensions, Clarendon Press, Oxford (1985). [13] J. W. P. Hirschfeld, Projective Geometries over Finite Fields, Clarendon Press, Oxford, second edition (1998). [14] C. Jones, A. Matney, H. Ward, Optimal four-dimensional codes over GF(8), Electron. J. Combin. 13 (2006) #R43, . [15] Y. Kageyama, T. Maruta, On the geometric constructions of optimal linear codes, Des. Codes Cryp- togr., 81 (2016) 469–480. [16] R. Kanazawa, T. Maruta, On optimal linear codes over F8, Electronic J. Combin., 18(1) (2011) #P34 [17] 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. [18] K. Kumegawa, T. Maruta, Nonexistence of some Griesmer codes over Fq, Discrete Math. 339 (2016) 515–521. [19] K. Kumegawa, T. Maruta, Non-existence of some 4-dimensional Griesmer codes over finite fields, J. Algebra Comb. Discrete Struct. Appl. 5 (2018) 101–116. [20] I. Landjev, L. Storme, A study of (x(q + 1),x; 2,q)-minihypers, Des. Codes Cryptogr. 54 (2010) 135–147. [21] T. Maruta, On the minimum length of q-ary linear codes of dimension four, Discrete Math., 208/209 (1999) 427–435. [22] T. Maruta, On the nonexistence of q-ary linear codes of dimension five, Des. Codes Cryptogr. 22 (2001) 165–177. [23] T. Maruta, A new extension theorem for linear codes, Finite Fields Appl. 10 (2004) 674–685. [24] T. Maruta, Optimal 4-dimensional linear codes over F8, Proceedings of 13th International Workshop on Algebraic and Combinatorial Coding Theory (ACCT 2012), Pomorie, Bulgaria (2012) 257–262. [25] T. Maruta, Construction of optimal linear codes by geometric puncturing, Serdica J. Computing 7 (2013) 73–80. [26] T. Maruta, Griesmer bound for linear codes over finite fields, available at http://mars39.lomo.jp/opu/griesmer.htm. [27] T. Maruta, Y. Oya, On optimal ternary linear codes of dimension 6, Adv. Math. Commun. 5 (2011) 505–520. [28] T. Maruta, M. Shinohara, M. Takenaka, Constructing linear codes from some orbits of projectivities, 89 https://web.mat.upc.edu/people/simeon.michael.ball/codebounds.html https://web.mat.upc.edu/people/simeon.michael.ball/codebounds.html http://dx.doi.org/10.3934/amc.2011.5.209 http://dx.doi.org/10.3934/amc.2011.5.209 https://doi.org/10.1016/j.disc.2015.01.010 https://doi.org/10.1016/j.disc.2015.01.010 https://doi.org/10.1023/A:1008294128110 https://doi.org/10.1023/A:1008294128110 https://doi.org/10.1007/BF01388456 https://doi.org/10.1007/BF01388456 http://www.codetables.de http://www.codetables.de https://doi.org/10.1147/rd.45.0532 https://doi.org/10.1016/0012-365X(93)90404-H https://doi.org/10.1016/0012-365X(93)90404-H https://doi.org/10.1007/BF00124893 https://doi.org/10.1007/BF00124893 https://doi.org/10.37236/1069 https://doi.org/10.37236/1069 https://doi.org/10.1007/s10623-015-0167-2 https://doi.org/10.1007/s10623-015-0167-2 https://doi.org/10.37236/521 https://doi.org/10.37236/6394 https://doi.org/10.37236/6394 https://doi.org/10.1016/j.disc.2015.09.030 https://doi.org/10.1016/j.disc.2015.09.030 https://doi.org/10.13069/jacodesmath.427968 https://doi.org/10.13069/jacodesmath.427968 https://doi.org/10.1007/s10623-009-9314-y https://doi.org/10.1007/s10623-009-9314-y 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://mars39.lomo.jp/opu/griesmer.htm http://mars39.lomo.jp/opu/griesmer.htm http://dx.doi.org/10.3934/amc.2011.5.505 http://dx.doi.org/10.3934/amc.2011.5.505 https://doi.org/10.1016/j.disc.2007.07.045 https://doi.org/10.1016/j.disc.2007.07.045 N. Bono et. al. / J. Algebra Comb. Discrete Appl. 8(2) (2021) 73–90 Discrete Math. 308 (2008) 832–841. [29] T. Maruta, T. Tanaka, H. Kanda, Some generalizations of extension theorems for linear codes over finite fields, Australas. J. Combin. 60 (2014) 150–157. [30] T. Maruta, Y. Yoshida, A generalized extension theorem for linear codes, Des. Codes Cryptogr. 62 (2012) 121–130. [31] M. Takenaka, K. Okamoto, T. Maruta, On optimal non-projective ternary linear codes, Discrete Math. 308 (2008) 842–854. [32] Y. Yoshida, T. Maruta, An extension theorem for [n,k,d]q codes with gcd(d,q) = 2, Australas. J. Combin. 48 (2010) 117–131. 90 https://doi.org/10.1016/j.disc.2007.07.045 https://doi.org/10.1016/j.disc.2007.07.045 https://mathscinet.ams.org/mathscinet-getitem?mr=3251934 https://mathscinet.ams.org/mathscinet-getitem?mr=3251934 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 Geometric methods Construction results Nonexistence of some Griesmer codes References