An empty interval in the spectrum of small weight codewords in the code from points and k-spaces of PG(n,q) 2 1 M. Lavrauw ∗ L. Storme P. Sziklai† G. Van de Voorde ‡ 0 2 January 17, 2012 n a J 6 Abstract 1 Let Ck(n,q) be the p-ary linear code defined by the incidence matrix ] of points and k-spaces in PG(n,q), q = ph, p prime, h ≥ 1. In this pa- O per, we show that there are no codewords of weight in the open interval C ]qkq+−11−1,2qk[ in Ck(n,q)\Cn−k(n,q)⊥ which implies that there are no h. codewords with this weight in Ck(n,q)\Ck(n,q)⊥ if k ≥ n/2. In par- t ticular, for the code Cn−1(n,q) of points and hyperplanes of PG(n,q), a we exclude all codewords in Cn−1(n,q) with weight in the open interval m ]qn−1,2qn−1[. This latter result implies a sharp bound on the weight of q−1 [ smallweight codewordsof Cn−1(n,q),aresult which waspreviously only knownforgeneraldimensionforqprimeandq=p2,withpprime,p>11, 1 and in the case n=2, for q=p3, p≥7 ([4],[5],[7],[8]). v 7 9 1 Definitions 2 3 1. Let PG(n,q) denote the n-dimensional projective space over the finite field Fq with q elements, where q = ph, p prime, h ≥ 1, and let V(n+1,q) denote the 0 2 underlying vector space. Let θn denote the number of points in PG(n,q), i.e., 1 θ =(qn+1−1)/(q−1). n : We define the incidence matrix A = (a ) of points and k-spaces in the v ij i projective space PG(n,q), q = ph, p prime, h ≥ 1, as the matrix whose rows X are indexed by the k-spaces of PG(n,q) and whose columns are indexed by the r points of PG(n,q), and with entry a 1 if point j belongs to k-space i, a = ij (cid:26) 0 otherwise. Thep-arylinearcodeofpointsandk-spacesofPG(n,q),q =ph,pprime,h≥1, is the F -span of the rows of the incidence matrix A. We denote this code by p ∗Thisauthor’sresearchwassupportedbytheFundforScientificResearch Flanders(FWO -Vlaanderen). †Thisauthor waspartiallysupportedbyOTKAT-049662, T-067867andBolyaigrants. ‡This author’s research was supported by the Institute for the Promotion of Innovation through Science and Technology in Flanders (IWT-Vlaanderen) and the Fund for Scientific Research Flanders(FWO -Vlaanderen). 1 C (n,q). The support of a codeword c, denoted by supp(c), is the set of all k non-zero positions of c. The weight of c is the number of non-zero positions of c and is denoted by wt(c). Often we identify the support of a codeword with the corresponding set of points of PG(n,q). We let (c ,c ) denote the scalar 1 2 product in F of two codewords c ,c of C (n,q). Furthermore, if T is a set of p 1 2 k points of PG(n,q), then the incidence vector of this set is also denoted by T. ⊥ The dual code C (n,q) is the set of all vectors orthogonalto all codewords of k C (n,q), hence k ⊥ C (n,q) ={v ∈V(θ ,p)||(v,c)=0, ∀c∈C (n,q)}. k n k ⊥ It is easy to see that c ∈ C (n,q) if and only if (c,K) = 0 for all k-spaces K k of PG(n,q). 2 Previous results The p-ary linear code of points and lines of PG(2,q), q =ph, p prime, h≥1, is studied in [1, Chapter 6]. In [1, Proposition 5.7.3], the codewords of minimum weight of the code of points and hyperplanes of PG(n,q), q = ph, p prime, h≥1, are determined. The first results on codewords of small weight in the p- arylinearcodeofpointsandlinesinPG(2,p),pprime,wereprovedbyMcGuire and Ward [10], where they proved that there are no codewords of C (2,p), p 1 an odd prime, in the interval [p+2,3(p+1)/2]. This result was extended by Chouinard (see [3], [4]) where he proves the following result. Result 1. [3],[4] In the p-ary linear code arising from PG(2,p), p prime, there are no codewords with weight in the closed interval [p+2,2p−1]. This result shows that there is a gap in the weight enumerator of the code C (2,p) of points and lines in PG(2,p), p prime. In Corollary 21, Result 1 is 1 extended to the code of points and k-spaces in PG(n,p), p prime, p>5. Inthecasewhereqisnotaprime,weimproveonresultsof[7]and[8],where the authors exclude codewords of small weight in Cn−1(n,q), q = ph, p prime, h ≥1, respectively C (n,q)\C (n,q)⊥, q = ph, p prime, h≥ 1, corresponding k k to linear smallminimal blockingsets, whichimplied Result2 andResult3. For the definition of a blocking set, see the next section. Result 2. [7, Corollary 3] The only possible codewords c of Cn−1(n,q), q =ph, p prime, h≥1, of weight in the open interval ]θn−1,2qn−1[ are the scalar mul- tiples of non-linear minimal blocking sets, intersecting every line in 1 (mod p) points. Result 3. [8, Corollary 2] For k ≥ n/2, the only possible codewords c of C (n,q)\C (n,q)⊥, q = ph, p prime, h ≥ 1, of weight in the open interval k k ]θ ,2qk[ are scalar multiples of non-linear minimal k-blocking sets of PG(n,q), k intersecting every line in 1 (mod p) or zero points. Remark 4. It is believed (and conjectured, see [11, Conjecture 3.1]) that all small minimal blocking sets are linear. If that conjecture is true, then Result 2 eliminates all possible codewords of Cn−1(n,q), q = ph, p prime, h ≥ 1, of weight in the open interval ]θn−1,2qn−1[, and Result 3 eliminates all codewords of C (n,q)\C (n,q)⊥, q = ph, p prime, h ≥ 1, of weight in the open interval k k ]θ ,2qk[ if k≥n/2. k 2 In this article, we avoid the obstacle of this non-solved conjecture and im- prove on Result 2 and Result 3 by showing that there are no codewords in Ck(n,q) \ Cn−k(n,q)⊥, q = ph, p prime, p > 5, h ≥ 1, in the open inter- val ]θ ,2qk[, which implies that there are no codewords in the open interval k ]θ ,2qk[ in C (n,q)\C (n,q)⊥ if k ≥ n/2. Using the results of [8], we show k k k that there are no codewords in C (n,q), q = ph, p prime, h ≥ 1, p > 7, with k weight in the open interval ]θ ,(12θ +6)/7[. k k Inthecasethatk=n−1,weshowthattherearenocodewordsinCn−1(n,q), q = ph, p prime, h ≥ 1, in the open interval ]θn−1,2qn−1[. These bounds are sharp: codewords of minimum weight in Cn−1(n,q) have been characterized as scalar multiples of incidence vectors of hyperplanes (see [1, Proposition 5.7.3]), and codewords of weight 2qn−1 can be obtained by taking the difference of the incidence vectors of two hyperplanes. 3 Blocking sets A blocking set of PG(n,q) is a set K of points such that each hyperplane of PG(n,q) contains at least one point of K. A blocking set K is called trivial if it containsa line ofPG(n,q). These blocking sets arealsocalled1-blocking sets in[2]. Ingeneral,ak-blocking set K inPG(n,q)isasetofpointssuchthatany (n−k)-dimensional subspace intersects K. A k-blocking set K is called trivial if there is a k-dimensional subspace contained in K. If an (n−k)-dimensional spacecontainsexactlyonepointofak-blockingsetK inPG(n,q), itiscalleda tangent(n−k)-spacetoK,andapointP ofK iscalledessentialwhenitbelongs to a tangent (n−k)-space of K. A k-blocking set K is called minimal when no proper subset of K is also a k-blocking set, i.e., when each point of K is es- sential. Ak-blockingsetiscalledsmallifitcontainslessthan3(qk+1)/2points. In order to define a linear k-blocking set, we introduce the notion of a De- sarguesianspread. Byfieldreduction,thepointsofPG(n,q),q =ph,pprime,h≥1,correspond to(h−1)-dimensionalsubspacesofPG((n+1)h−1,p),sinceapointofPG(n,q) is a 1-dimensional vector space over F , and so an h-dimensional vector space q overF . Inthisway,weobtainapartitionDofthepointsetofPG((n+1)h−1,p) p by (h−1)-dimensional subspaces. In general, a partition of the point set of a projective space by subspaces of a given dimension k is called a spread, or a k-spreadifwewanttospecifythedimension. Thespreadwehaveobtainedhere is calleda Desarguesian spread. Notethat the Desarguesianspreadsatisfiesthe propertythateachsubspacespannedbytwospreadelementsisagainpartitioned by spread elements. Definition 5. Let D be a Desarguesian (h−1)-spread of PG((n+1)h−1,p) as defined above. If U is a subset of PG((n+1)h−1,p), then we write B(U)= {R∈D||U ∩R6=∅}. In analogy with the correspondence between the points of PG(n,q) and the elements of a Desarguesian spread D in PG((n + 1)h − 1,p), we obtain the correspondence between the lines of PG(n,q) and the (2h−1)-dimensional subspaces ofPG((n+1)h−1,p)spanned by two elements of D, and in general, we obtain the correspondence between the (n−k)-spaces of PG(n,q) and the 3 ((n−k +1)h−1)-dimensional subspaces of PG((n+1)h−1,p) spanned by n−k+1 elements of D. With this in mind, it is clear that any hk-dimensional subspace U of PG(h(n+1)−1,p) defines a k-blocking set B(U) in PG(n,q). A blocking set constructed in this way is called a linear k-blocking set. Linear k-blockingsets werefirstintroducedbyLunardon[9, Section5],althoughthere a differentapproachis used. For moreonthe approachexplainedhere,we refer to [6, Chapter 1]. 4 Results In [12], Sz˝onyi and Weiner proved the following result on small blocking sets. Result 6. [12, Theorem 2.7] Let B be a minimal blocking set of PG(n,q) with respect to k-dimensional subspaces, q = ph, p > 2 prime, h ≥ 1, and assume that |B|<3(qn−k+1)/2. Then any subspace that intersects B, intersects it in 1 (mod p) points. In [8], Lavrauw et al. proved the following lemmas. Result 7. The support of a codeword c ∈ C (n,q), q = ph, p prime, h ≥ 1, k with weight smaller than 2qk, for which (c,S) 6= 0 for some (n−k)-space S, is a minimal k-blocking set in PG(n,q). Moreover, c is a scalar multiple of a certain incidence vector, and supp(c)intersects every (n−k)-dimensional space in 1 (mod p) points. Lemma 8. Let c ∈ C (n,q), q = ph, p prime, h ≥ 1, then there exists a k constant a ∈ F such that (c,U) = a, for all subspaces U of dimension at least p n−k. Inthe samewayasisdone bythe authorsin[8,Theorem19],onecanprove Lemma9,whichshowsthatallminimalk-blockingsetsofsizelessthan2qk and intersecting every (n−k)-space in 1 (mod p) points, are small. Lemma 9. Let B be a minimal k-blocking set in PG(n,q), n ≥ 2, q = ph, p prime, p>5, h≥1, intersecting every (n−k)-dimensional space in 1 (mod p) points. If |B|∈]θ ,2qk[, then k 3(qk−qk/p) |B|< . 2 Lemma 10. Let B and B be small minimal (n−k)-blocking sets in PG(n,q), 1 2 q =ph, p prime, h≥1. Then B −B ∈C (n,q)⊥. 1 2 k Proof. It follows from Result 6 that (B ,π ) = 1 for all k-spaces π , i = 1,2. i k k Hence (B − B ,π ) = 0 for all k-spaces π . This implies that B − B ∈ 1 2 k k 1 2 ⊥ C (n,q) . k Lemma 11. Let c be a codeword of C (n,q), q = ph, p prime, h ≥ 1, with k weight smaller than 2qk, for which (c,S) 6= 0 for some (n−k)-space S, and let B be a small minimal (n−k)-blocking set. Then supp(c) intersects B in 1 (mod p) points. 4 Proof. Let c be a codewordof C (n,q) with weight smaller than 2qk, for which k (c,S)6= 0 for some (n−k)-space S. Lemma 10 shows that (c,B −B )=0 = 1 2 (c,B )−(c,B ) for all small minimal (n−k)-blocking sets B and B . Hence 1 2 1 2 (c,B),withB asmallminimal(n−k)-blockingset,isaconstant. Result7shows that c is a codeword only taking values from {0,a}, so (c,B) = a(supp(c),B), hence (supp(c),B) is a constanttoo. Let B be an(n−k)-space,then Result 7 1 shows that (supp(c),B )=1. Since B is a smallminimal (n−k)-blocking set, 1 1 the number of intersection points of supp(c) and B is equal to 1 (mod p) for any small minimal blocking set B. ItfollowsfromLemma8that,forc∈C (n,q)andS an(n−k)-space,(c,S) k is a constant. Hence, either (c,S)6=0 for all (n−k)-spaces S, or (c,S)=0 for ⊥ all (n−k)-spaces S. In this latter case, c∈Cn−k(n,q) . Theorem 12. There arenocodewords inCk(n,q)\Cn−k(n,q)⊥, 1≤k ≤n−1, 2≤n, with weight in the open interval ]θ ,2qk[, q =ph, p prime, p>5, h≥1. k Proof. Let Y be a linear small minimal (n−k)-blocking set in PG(n,q). As explained in Section 3, Y correspondsto a set Y¯ =B(π) of (h−1)-dimensional spreadelements intersectingacertain(h(n−k))-spaceπ inPG(h(n+1)−1,p). Let c be a codeword of Ck(n,q)\Cn−k(n,q)⊥ with weight at most 2qk −1. Result 7 and Lemma 9 show that supp(c) is a small minimal k-blocking set B. This blockingset B correspondsto a setB¯ of |B| spreadelements inPG(h(n+ 1)−1,p). Since supp(c) and Y intersect in 1 (mod p) points (see Lemma 11), B¯ and Y¯ intersect in 1 (mod p) spread elements. Since all spread elements of Y¯ intersect π, there are 1 (mod p) spread elements of B¯ that intersect π. ′ But this holds for any (h(n−k))-space π in PG(h(n+1)−1,p), since any ′ (h(n−k))-space π corresponds to a linear small minimal (n−k)-blocking set ′ Y in PG(n,q). Let B˜ be the set of points contained in the spread elements of the set B¯. SinceaspreadelementthatintersectsasubspaceofPG(h(n+1)−1,p)intersects it in 1 (mod p) points, B˜ intersects any (h(n−k))-space in 1 (mod p) points. Moreover, |B˜|=|B|·(ph−1)/(p−1)≤3(phk−phk−1)·(ph−1)/(2(p−1))< 3(ph(k+1)−1+1)/2(seeLemma9). ThisimpliesthatB˜ isasmall(h(k+1)−1)- blocking set in PG(h(n+1)−1,p). Moreover, B˜ is minimal. This can be proved in the following way. Let R be a point of B˜. Since B is a minimal k-blocking set in PG(n,q), there is a ′ tangent (n−k)-space S through the point R of PG(n,q) corresponding to the ′ spread element B(R). Now S corresponds to an (h(n−k +1)−1)-space π in PG(h(n+1)−1,p), such that B(R) is the only element of B¯ in π′. This ′ implies that through R, there is an (h(n−k))-space in π containing only the point R of B˜. This shows that through every point of B˜, there is a tangent (h(n−k))-space, hence that B˜ is a minimal (h(k+1)−1)-blocking set. Result 6 implies that B˜ intersects any subspace of PG(h(n+1)−1,p) in 1 (mod p) or zero points. This implies that a line is skew, tangent or entirely contained in B˜, hence B˜ is a subspace of PG(h(n +1)−1,p), with at most 3(ph(k+1)−1+1)/2 points, intersecting every (h(n−k))-space. Moreover, it is the point set of a set of |B| spread elements. Hence, B¯ is the set of spread elements corresponding to a k-space in PG(n,q), so supp(c) has size θ . k In [8], Lavrauw et al. determined a lower bound on the weight of the code ⊥ C (n,q) . k 5 Result 13. The minimum weight of C (n,q)⊥, q =ph, p prime, h≥1, 2≤n, k 1 ≤k ≤ n−1, is at least (12θn−k+2)/7 if p =7, and at least (12θn−k+6)/7 if p>7. Theorem 14. For q = ph, p prime, h ≥ 1, 2 ≤ n, 1 ≤ k ≤ n−1, there are no codewords in C (n,q) with weight in the open interval ]θ ,(12θ +2)/7[ if k k k p = 7 and there are no codewords in C (n,q) with weight in the open interval k ]θ ,(12θ +6)/7[ if p>7. k k Proof. This follows immediately from Theorem 12 and Result 13. In [8], the authors proved the following result. Result 15. [8, Lemma 3] Assume that k ≥ n/2. A codeword c of C (n,q) k ⊥ is in C (n,q) ∩C (n,q) if and only if (c,U) = 0 for all subspaces U with k k dim(U)≥n−k. Corollary 16. If k ≥ n/2, Ck(n,q) \ Cn−k(n,q)⊥ = Ck(n,q) \ Ck(n,q)⊥, q =ph, p prime, h≥1. ⊥ Proof. It follows from Result 15 that Ck(n,q) ∩ Cn−k(n,q) = Ck(n,q) ∩ ⊥ C (n,q) if k ≥n/2. k In [7], the authors proved the following result. Result 17. [7, Theorem 5] The minimum weight of Cn−1(n,q)∩Cn−1(n,q)⊥ is equal to 2qn−1. Result 18. [8, Theorem 12] The minimum weight of C (n,p)⊥, where p is k a prime, is equal to 2pn−k, and the codewords of weight 2pn−k are the scalar multiples of the difference of two (n−k)-spaces intersecting in an (n−k−1)- space. Theorem12,Corollary16,andResult17yieldthefollowingcorollary,which givesasharpemptyintervalonthesizeofsmallweightcodewordsofCn−1(n,q), since θn−1 is the weight of a codeword arising from the incidence vector of an (n−1)-space and 2qn−1 is the weightof a codewordarising from the difference of the incidence vectors of two (n−1)-spaces. Corollary19. Therearenocodewordswithweightintheopeninterval]θn−1,2qn−1[ in the code Cn−1(n,q), q =ph, p prime, h≥1, p>5. Inthe planarcase,this yields the followingcorollary,whichimprovesonthe result of Chouinard mentioned in Result 1. Corollary20. Therearenocodewordswithweightintheopeninterval]q+1,2q[ in the p-ary linear code of points and lines of PG(2,q), q =ph, p prime, h≥1, p>5. In this case, the weight q+1 corresponds to the incidence vector of a line, and the weight 2q can be obtained by taking the difference of the incidence vectors of two different lines. Theorem12andResult18yieldthe followingcorollary,extendingthe result of Chouinard mentioned in Result 1 to general dimension. Corollary 21. Therearenocodewords withweightintheopen interval]θ ,2qk[ k in the code C (n,q), n≥2, 1≤k ≤n−1, q prime, q >5. k 6 References [1] E.F. Assmus, Jr. and J.D. Key. Designs and their codes. Cambridge Uni- versity Press, 1992. [2] A. Beutelspacher. Blocking sets and partial spreads in finite projective spaces. Geom. Dedicata 9 (1980), 130–157. [3] K.Chouinard.Weightdistributionsofcodesfromplanes(PhDThesis,Uni- versity of Virginia) (August 1998). [4] K. Chouinard. On weight distributions of codes of planes of order 9. Ars Combin. 63 (2002), 3–13. [5] V.Fack,Sz.L.Fancsali,L.Storme,G.VandeVoorde,andJ.Winne.Small weightcodewordsinthecodesarisingfromDesarguesianprojectiveplanes. Des. Codes Cryptogr. 46 (2008), 25–43. [6] M. Lavrauw. Scattered spaces with respect to spreads, and eggs in finite projective spaces. PhD Dissertation, Eindhoven University of Technology, Eindhoven, 2001. viii+115 pp. [7] M. Lavrauw,L. Storme, and G. Van de Voorde. On the code generated by the incidence matrix of points and hyperplanes in PG(n,q) and its dual. Des. Codes Cryptogr., 48 (2008), 231–245. [8] M. Lavrauw,L. Storme, and G. Van de Voorde. On the code generated by theincidencematrixofpointsandk-spacesinPG(n,q)anditsdual.Finite Fields Appl., 14 (2008), 1020–1038. [9] G. Lunardon. Normal spreads. Geom. Dedicata 75 (1999), 245–261. [10] G. McGuire and H. Ward. The weight enumerator of the code of the pro- jective plane of order 5. Geom. Dedicata 73 (1998), no. 1, 63–77. [11] P. Sziklai. On small blocking sets and their linearity. J. Combin. Theory, Ser. A, to appear. [12] T. Sz˝onyi and Zs. Weiner. Small blocking sets in higher dimensions. J. Combin. Theory, Ser. A 95 (2001), 88–101. Address of the authors: Michel Lavrauw,Leo Storme, Geertrui Van de Voorde: Department of pure mathematics and computer algebra, Ghent University Krijgslaan 281-S22 9000 Ghent (Belgium) {ml,ls,gvdvoorde}@cage.ugent.be http://cage.ugent.be/ ∼ {ml,ls,gvdvoorde} Peter Sziklai: Department of Computer Science, 7 Eo¨tv¨os Lora´nd University Pa´zm´any P. s´et´any 1/C H-1117 Budapest (Hungary) [email protected] http://www.cs.elte.hu/∼sziklai 8