×

Maximum distance separable codes and arcs in projective spaces. (English) Zbl 1126.94017

An \((n,k,q)\)-MDS code \(C\) is a collection of \(q^k\) distinct \(n\)-tuples, called codewords, over an alphabet \({\mathcal A}\) of size \(q\), satisfying the following condition: no two codewords of \(C\) agree in as many as \(k\) coordinate positions. The importance of these MDS codes is that they satisfy the Singleton bound of coding theory, that is, they are codes of length \(n\), containing \(q^k\) codewords, and whose minimal distance \(d\) is equal to \(d=n-k+1\).
Linear \([n,k,n-k+1]\)-MDS codes over the finite field of order \(q\) are equivalent to \(n\)-arcs in PG\((k-1,q)\) and to \(n\)-arcs in PG\((n-k-1,q)\). This geometrical link to arcs has made it possible to prove many results on linear MDS codes. In particular, great attention has been paid to the problem of the extendability of \(n\)-arcs in PG\((k-1,q)\) to \((n+1)\)-arcs in PG\((k-1,q)\); in this way studying the problem of the extendability of the corresponding \([n,k,n-k+1]\)-MDS codes to \([n+1,k,n-k+2]\)-MDS codes.
In some cases, the non-extendability of linear \([n,k,n-k+1]\)-MDS codes to linear \([n+1,k,n-k+2]\)-MDS codes is known. But could these codes be extended to non-linear MDS codes of length \(n+1\)?
The authors contribute to this particular extendability problem. They obtain new results by using new geometrical links. The new links are with Rédei-type blocking sets.
Consider an affine plane \(A\) of order \(q\), with line \(\ell\) at infinity. Let \(\pi\) be the projective plane defined by \(A\) and \(\ell\). A Rédei-type blocking set of \(\pi\), w.r.t. the line \(\ell\), is a set \(B\) consisting of \(q\) points of \(A\), together with the intersection points of all secants to \(A\) with the line \(\ell\).
These Rédei-type blocking sets in PG\((2,q)\) have been studied in great detail by A. Blokhuis, S. Ball, A.E. Brouwer, L. Storme and T. Szőnyi [J. Comb. Theory, Ser. A 86, No. 1, 187–196 (1999; Zbl 0945.51002)] and S. Ball [J. Comb. Theory, Ser. A 104, No. 2, 341–350 (2003; Zbl 1045.51004)]. Let \({\mathcal P}_q>1\) be the smallest size for the intersection \(B\cap \ell\) of a Rédei-type blocking set \(B\), different from a line, w.r.t. \(\ell\).
To illustrate the link between the extendability problem of linear MDS codes and Rédei-type blocking sets of PG\((2,q)\), we mention the following result: Let \(C\) be a linear \([n,3,n-2]\)-MDS code, with \(n>q+2-{\mathcal P}_q\). Then any arbitrary extension of \(C\) to an MDS code of length \(n+1\) must be linear.
We also wish to mention with respect to Section 7.1 the results of L. Storme and J. A. Thas [J. Comb. Theory, Ser. A 62, No. 1, 139–154 (1993; Zbl 0771.51006)] on arcs in PG\((N,q)\), \(q\) even.
Reviewer: Leo Storme (Gent)

MSC:

94B25 Combinatorial codes
05B25 Combinatorial aspects of finite geometries
51E14 Finite partial geometries (general), nets, partial spreads
51E20 Combinatorial structures in finite projective spaces
51E21 Blocking sets, ovals, \(k\)-arcs
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Alderson, T. L., Extending MDS codes, Ann. Comb., 9, 2, 125-135 (2005) · Zbl 1112.51002
[2] T.L. Alderson, On MDS codes and Bruen-Silverman codes, PhD thesis, University of Western Ontario, 2002; T.L. Alderson, On MDS codes and Bruen-Silverman codes, PhD thesis, University of Western Ontario, 2002
[3] Ball, S., The number of directions determined by a function over a finite field, J. Combin. Theory Ser. A, 104, 2, 341-350 (2003) · Zbl 1045.51004
[4] Blokhuis, A.; Ball, S.; Brouwer, A. E.; Storme, L.; Szőnyi, T., On the number of slopes of the graph of a function defined on a finite field, J. Combin. Theory Ser. A, 86, 1, 187-196 (1999) · Zbl 0945.51002
[5] Blokhuis, A.; Bruen, A. A.; Thas, J. A., Arcs in \(PG(n, q)\), MDS-codes and three fundamental problems of B. Segre—Some extensions, Geom. Dedicata, 35, 1-3, 1-11 (1990) · Zbl 0709.51013
[6] Bruen, A. A., Collineations and extensions of translation nets, Math. Z., 145, 3, 243-249 (1975) · Zbl 0297.50017
[7] Bruen, A. A., Nuclei of sets of \(q + 1\) points in \(PG(2, q)\) and blocking sets of Rédei type, J. Combin. Theory Ser. A, 55, 1, 130-132 (1990) · Zbl 0706.51011
[8] Bruen, A. A.; Forcinito, Mario A., Cryptography, Information Theory, and Error-Correction, Wiley-Intersci. Ser. Discrete Math. Optim. (2005), Wiley-Interscience: Wiley-Interscience Hoboken, NJ, A handbook for the 21st century · Zbl 1071.94001
[9] Bruen, A. A.; Levinger, B., A theorem on permutations of a finite field, Canad. J. Math., 25, 1060-1065 (1973) · Zbl 0269.12011
[10] Bruen, A. A.; Silverman, R., On extendable planes, M.D.S. codes and hyperovals in \(PG(2, q), q = 2^t\), Geom. Dedicata, 28, 1, 31-43 (1988) · Zbl 0661.94016
[11] Bruen, A. A.; Thas, J. A.; Blokhuis, A., On M.D.S. codes, arcs in \(PG(n, q)\) with \(q\) even, and a solution of three fundamental problems of B. Segre, Invent. Math., 92, 3, 441-459 (1988) · Zbl 0654.94014
[12] Calderbank, A. R.; Shor, Peter W., Good quantum error-correcting codes exist, Phys. Rev. A, 54, 1098 (1996)
[13] Casse, Louis Reynolds Antoine, A solution to Beniamino Segre’s “Problem \(I_{r, q}\)” for \(q\) even, Atti Accad. Naz. Lincei Rend. Cl. Sci. Fis. Mat. Natur. (8), 46, 13-20 (1969) · Zbl 0176.17901
[14] Hirschfeld, J. W.P., Projective Geometries over Finite Fields, Oxford Math. Monogr. (1998), Clarendon Press, Oxford Univ. Press: Clarendon Press, Oxford Univ. Press New York · Zbl 0899.51002
[15] Lovász, L.; Schrijver, A., Remarks on a theorem of Rédei, Studia Sci. Math. Hungar., 16, 3-4, 449-454 (1983) · Zbl 0535.51009
[16] MacWilliams, F. J.; Sloane, N. J.A., The Theory of Error-Correcting Codes. I, North-Holland Math. Library, vol. 16 (1977), North-Holland: North-Holland Amsterdam · Zbl 0369.94008
[17] Maneri, Carl; Silverman, Robert, A vector-space packing problem, J. Algebra, 4, 321-330 (1966) · Zbl 0151.01602
[18] Rédei, L., Lacunary Polynomials over Finite Fields (1973), North-Holland: North-Holland Amsterdam, Translated from the German by I. Földes · Zbl 0255.12009
[19] Segre, Beniamino, Curve razionali normali e \(k\)-archi negli spazi finiti, Ann. Mat. Pura Appl. (4), 39, 357-379 (1955) · Zbl 0066.14001
[20] Segre, Beniamino, Introduction to Galois geometries, Atti Accad. Naz. Lincei Mem. Cl. Sci. Fis. Mat. Natur. Sez. I (8), 8, 133-236 (1967) · Zbl 0194.21503
[21] Silverman, Robert, A metrization for power-sets with applications to combinatorial analysis, Canad. J. Math., 12, 158-176 (1960) · Zbl 0092.01201
[22] Szőnyi, T., \(k\)-Sets in \(PG(2, q)\) having a large set of internal nuclei, (Combinatorics ’88, vol. 2. Combinatorics ’88, vol. 2, Ravello, 1988. Combinatorics ’88, vol. 2. Combinatorics ’88, vol. 2, Ravello, 1988, Res. Lecture Notes Math. (1991), Mediterranean: Mediterranean Rende), 449-458 · Zbl 0945.51521
[23] Szőnyi, Tamás, Around Rédei’s theorem, Discrete Math., 208/209, 557-575 (1999), Combinatorics (Assisi, 1996) · Zbl 0952.11027
[24] Thas, J. A., Normal rational curves and \((q + 2)\)-arcs in a Galois space \(S_{q - 2, q}(q = 2^h)\), Atti Accad. Naz. Lincei Rend. Cl. Sci. Fis. Mat. Natur. (8), 47, 249-252 (1970), 1969 · Zbl 0189.51901
[25] Thas, J. A., Complete arcs and algebraic curves in \(PG(2, q)\), J. Algebra, 106, 2, 451-464 (1987) · Zbl 0608.14016
[26] J.A. Thas, Finite geometries, varieties and codes, in: Proceedings of the International Congress of Mathematicians, Extra vol. III, Berlin, 1998, 1998, pp. 397-408 (electronic); J.A. Thas, Finite geometries, varieties and codes, in: Proceedings of the International Congress of Mathematicians, Extra vol. III, Berlin, 1998, 1998, pp. 397-408 (electronic) · Zbl 0905.51005
[27] Wettl, F., Internal nuclei of \(k\)-sets in finite projective spaces of three dimensions, (Advances in Finite Geometries and Designs. Advances in Finite Geometries and Designs, Chelwood Gate, 1990. Advances in Finite Geometries and Designs. Advances in Finite Geometries and Designs, Chelwood Gate, 1990, Oxford Sci. Publ. (1991), Oxford Univ. Press: Oxford Univ. Press New York), 407-419 · Zbl 0734.51008
[28] Wicker, Stephen B., Error Control Systems for Digital Communication and Storage (1995), Prentice Hall: Prentice Hall Upper Saddle River, NJ · Zbl 0847.94001
[29] Avi Wigderson, On the work of Madhu Sudan, Notices Amer. Math. Soc., 2002, pp. 45-50; Avi Wigderson, On the work of Madhu Sudan, Notices Amer. Math. Soc., 2002, pp. 45-50 · Zbl 1159.01352
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.