Multiple blocking sets in finite projective spaces and improvements to the Griesmer bound for linear codes (Q1035813): Difference between revisions

The Griesmer bound states that for any linear \([n, k, d]\) \(q\)-ary code \(C\), \[ n\geq g(k,d,q)=\sum_{i=0}^{k-1}\lceil d/q^i\rceil. \] In general, it is very interesting to investigate the properties of codes which attain this bound exactly, that is codes such that \(n = g(k, d, q)\). One of the main results of this paper is to show that for several values of \(d < q^{k-1}\) there are no such codes. In particular, the authors observe that any \([n, k]\)-code \(C\) with minimum distance \(d\leq q^{k-1}\) meeting the Griesmer bound is necessarily projective; that is no generator matrix for \(C\) has repeated columns. There is a close relationship between projective codes and \(t\)-fold blocking sets in \(\text{PG}(k-1, q)\); namely, if \(G\) is the \(k \times n\) generator matrix of a projective code C, then the set \(B\) of the \(|\text{PG}(k-1, q)|-n\) points of \(\text{PG}(k-1, q)\) which do not correspond to any of the columns of \(G\) forms a \(t\)-fold blocking set for the hyperplanes of \(\text{PG}(k-1, q)\), where \(t =|B|-q^{k-1} + d\). Suppose now \(B \subseteq \text{PG}(\delta, q)\) to be \(t\)-fold blocking set with respect to hyperplanes of \(\text{PG}(\delta, q)\) for which there actually exists a \(t\)-secant hyperplane. As a shorthand, write \[ t=[t_{\delta-2},t_{\delta-1},\dots,t_0]= \sum_{i=0}^{\delta-2}t_i\frac{q^{i+1}-1}{q-1} \] with \(0\leq t_i \leq q\) and \(t_0=t_1=\dots=t_j-1=0\) if \(t_j = q\). Then, the authors show that \[ |B|\leq qt+\sum_{i=0}^{\delta-2}t_i+q-1 \] implies \[ |B|\geq qt+\sum_{i=0}^{\delta-2}t_i. \] Furthermore, when \(q=p\) is a prime, they show that: {\parindent=5mm \begin{itemize}\item[1.] if \(B\) is a \([1, t_{\delta-3} , \ldots , t_0 ]\)-fold blocking set with respect to the hyperplanes of \(\text{PG}(\delta, p)\), \(\delta\geq 3\), \(t_i\leq p-1\) for all \(i\), \(t_{\delta-3}=0\) and \[ \sum_{i=0}^{\delta-3}t_i(p^{i+2}-1)<\frac{p-3}{2}(p^{\delta-1}-1)-(p-1)^2, \] then \[ |B|\geq tp+\sum_{i=0}^{\delta-2}t_i+p; \] \item[2.] if \(B\) is a \(t\)-fold blocking set with respect to hyperplanes of \(PG(\delta, p)\) with \(t_0 \geq 1\) and \(\delta\geq 3\), \([t_{\delta-2} , \dots , t_2 , t_1 +1]= t_1 + 1\) and \([t_{\delta-2} , \dots , t_2 ]=0\) for \(\delta=3\), then, if there exists a \([t_{\delta-2},\dots,t_2,t_1+1]\) secant \((\delta-2)\)-dimensional subspace contained in a \(t\)-secant hyperplane but not contained in any hyperplane incident with \(B\) in at least \(p+t\) points, we have \[ |B|\geq pt+\sum_{i=0}^{\delta-2}t_i+\min\{(p+1)/2,p-t_0\}. \] \end{itemize}} Fix now a prime \(p\) and and integers \(k, d\) so that \(d=\sum_{i=0}^{k-2}d_ip^i\) is the \(p\)-ary expansion of \(d\). In the paper it is shown that for any \(p\) ary \([n,k,d]\)-linear code \(C\), necessarily \[ n\geq g(k,d,p)+1 \] under any of the following conditions: {\parindent=6.5mm \begin{itemize}\item[(1)] \(p^{k-3}\) divides \(d<p^{k-1}-2p^{k-2}\) and \(d_{k-3}\geq\max\{(p +1)/2, p-d_{k-2}\}\); \item[(2)] \(p^{k-3}\) does not divide \(d<p^{k-1}-2p^{k-2}\) and \(d_{k-3}\geq\max\{(p-1)/2, p-1-d_{k-2}\}\); \item[(3)] \(d<p^{k-1}\) , \(k\geq 4\), \(d_{k-2}=p-2\) and \(p-2\geq d_{k-3}\geq (p + 3)/2\). \end{itemize}} Furthermore, it is shown that almost all the \(p\)-ary \([n, d, k]\)-linear codes with minimum distance \(d<q^{k-1}\) attaining the Griesmer bound have codewords of weight at least \(d+p\) in some chosen subcodes.