Book contents
- Frontmatter
- Contents
- Preface
- 1 Graph removal lemmas
- 2 The geometry of covering codes: small complete caps and saturating sets in Galois spaces
- 3 Bent functions and their connections to combinatorics
- 4 The complexity of change
- 5 How symmetric can maps on surfaces be?
- 6 Some open problems on permutation patterns
- 7 The world of hereditary graph classes viewed through Truemper configurations
- 8 Structure in minor-closed classes of matroids
- 9 Automatic counting of tilings of skinny plane regions
- References
2 - The geometry of covering codes: small complete caps and saturating sets in Galois spaces
Published online by Cambridge University Press: 05 July 2013
Book contents
- Frontmatter
- Contents
- Preface
- 1 Graph removal lemmas
- 2 The geometry of covering codes: small complete caps and saturating sets in Galois spaces
- 3 Bent functions and their connections to combinatorics
- 4 The complexity of change
- 5 How symmetric can maps on surfaces be?
- 6 Some open problems on permutation patterns
- 7 The world of hereditary graph classes viewed through Truemper configurations
- 8 Structure in minor-closed classes of matroids
- 9 Automatic counting of tilings of skinny plane regions
- References
Summary
Abstract
Complete caps and saturating sets in projective Galois spaces are the geometrical counterpart of linear codes with covering radius 2. The smaller the cap/saturating set, the better the covering properties of the code. In this paper we survey the state of the art of the research on these geometrical objects, with particular emphasis on the recent developments and on the connections with algebraic curves over finite fields.
Introduction
Galois spaces, that is affine and projective spaces of dimension N > 2 defined over a finite (Galois) field Fq, are well known to be rich in nice geometric, combinatorial and group-theoretic properties that have also found wide and relevant applications in several branches of combinatorics, especially to design theory and graph theory, as well as in more practical areas, notably coding theory and cryptography.
The systematic study of Galois spaces was initiated in the late 1950's by the pioneering work of B. Segre [77]. The trilogy [53, 55, 58] covers the general theory of Galois spaces including the study of objects which are linked to linear codes. Typical such objects are plane arcs and their generalizations, especially caps, saturating sets and arcs in higher dimensions, whose code-theoretic counterparts are distinguished types of error-correcting and covering linear codes, such as MDS codes. Their investigation has received a great stimulus from coding theory, especially in the last decades; see the survey papers [56, 57].
- Type
- Chapter
- Information
- Surveys in Combinatorics 2013 , pp. 51 - 90Publisher: Cambridge University PressPrint publication year: 2013
References
[1] , Complete caps in a Galois space PG(3, q), q even, Atti Sem. Mat. Fis. Univ. Modena 29 (1980), no. 2, 215–221.Google Scholar
[2] , , , and , Small complete caps from singular cubics, submitted, 2012.
[3] and , Bicovering arcs and small complete caps from elliptic curves, submitted, 2012.
[4] and , Covering radii of ternary linear codes of small dimensions and codimensions, IEEE Trans. Inform. Theory 43 (1997), no. 6, 2057–2061.Google Scholar
[5] and , Correction to: “Covering radii of ternary linear codes of small dimensions and codimensions” [IEEE Trans. Inform. Theory 43 (1997), no. 6, 2057–2061], IEEE Trans. Inform. Theory 44 (1998), no. 5, 2032.Google Scholar
[6] , Dense k-systems in Galois planes, Boll. Un. Mat. Ital. D (6) 2 (1983), no. 1, 71–77.Google Scholar
[7] , Private communication, 2012.
[8] , , , and , New upper bounds on the smallest size of a complete arc in the plane PG(2, q), Proceedings XIII Int. Workshop on Algebraic and Combin. Coding Theory, ACCT2012, June 2012, pp. 60–66.
[9] , , , and , On sizes of complete arcs in PG(2, q), Discrete Math. 312 (2012), no. 3, 680–698.Google Scholar
[10] , , , and , Multiple coverings of the farthest-off points, In preparation, 2012.
[11] , , , and , New type of estimations for the smallest size of complete arcs in PG(2, q), Proceedings XIII Int. Workshop on Algebraic and Combin. Coding Theory, ACCT2012, June 2012, pp. 67–72.
[12] and , Small complete caps in PG(3, q), In preparation, 2012.
[13] , , and , On defining sets for projective planes, Discrete Math. 303 (2005), no. 1–3, 17–31.Google Scholar
[14] , , and , Covering radius, Handbook of coding theory, Vol. I, II, North-Holland, Amsterdam, 1998, pp. 755–826.
[15] , , and , Short codes with a given covering radius, IEEE Trans. Inform. Theory 35 (1989), no. 1, 99–109.Google Scholar
[16] , , and , Cubic curves, finite geometry and cryptography, Acta Appl. Math. 115 (2011), no. 3, 265–278.Google Scholar
[17] and , The geometry of two-weight codes, Bull. London Math. Soc. 18 (1986), no. 2, 97–122.Google Scholar
[18] , , , and , Covering codes, North-Holland Mathematical Library, vol. 54, North-Holland Publishing Co., Amsterdam, 1997.
[19] , , and , Further results on the covering radius of codes, IEEE Trans. Inform. Theory 32 (1986), no. 5, 680–694.Google Scholar
[20] , Construction of linear covering codes, Problems of Information Transmission 26 (1990), no. 4, 317–331.Google Scholar
[21] , Constructions and families of covering codes and saturated sets of points in projective geometry, IEEE Trans. Inform. Theory 41 (1995), no. 6, part 2, 2071–2080.Google Scholar
[22] , Constructions and families of nonbinary linear codes with covering radius 2, IEEE Trans. Inform. Theory 45 (1999), no. 5, 1679–1686.Google Scholar
[23] , New constructions of covering codes, Des. Codes Cryptogr. 22 (2001), no. 3, 305–316.Google Scholar
[24] and , Constructions, families, and tables of binary linear covering codes, IEEE Trans. Inform. Theory 40 (1994), no. 4, 1270–1279.Google Scholar
[25] , , , and , Computer search in projective planes for the sizes of complete arcs, J. Geom. 82 (2005), no. 1–2, 50–62.Google Scholar
[26] , , , and , Locally optimal (nonshortening) linear covering codes and minimal saturating sets in projective spaces, IEEE Trans. Inform. Theory 51 (2005), no. 12, 4378–4387.Google Scholar
[27] , , , and , On sizes of complete caps in projective spaces PG(n, q) and arcs in planes PG(2, q), J. Geom. 94 (2009), no. 1–2, 31–58.Google Scholar
[28] , , , and , New inductive constructions of complete caps in PG(N, q), q even, J. Combin. Des. 18 (2010), no. 3, 177–201.Google Scholar
[29] , , , and , Linear nonbinary covering codes and saturating sets in projective spaces, Adv. Math. Commun. 5 (2011), no. 1, 119–147.Google Scholar
[30] , , and , On saturating sets in projective spaces, J. Combin. Theory Ser. A 103 (2003), no. 1, 1–15.Google Scholar
[31] , , and , Complete caps in projective spaces PG(n, q), J. Geom. 80 (2004), no. 1–2, 23–30.Google Scholar
[32] , , and , Linear codes with covering radius 2, 3 and saturating sets in projective geometry, IEEE Trans. Inform. Theory 50 (2004), no. 3, 537–541.Google Scholar
[33] and , New linear codes with covering radius 2 and odd basis, Des. Codes Cryptogr. 16 (1999), no. 1, 29–39.Google Scholar
[34] and , New quaternary linear codes with covering radius 2, Finite Fields Appl. 6 (2000), no. 2, 164–174.Google Scholar
[35] and , On saturating sets in small projective geometries, European J. Combin. 21 (2000), no. 5, 563–570.Google Scholar
[36] and , Linear codes with covering radius R = 2, 3 and codimension tR, IEEE Trans. Inform. Theory 47 (2001), no. 1, 416–421.Google Scholar
[37] and , Recursive constructions of complete caps, J. Statist. Plann. Inference 95 (2001), no. 1–2, 167–173, Special issue on design combinatorics: in honor of .Google Scholar
[38] and , Linear codes with covering radius 3, Des. Codes Cryptogr. 54 (2010), no. 3, 253–271.Google Scholar
[39] and , Quasi-perfect codes with small distance, IEEE Trans. Inform. Theory 51 (2005), no. 11, 3938–3946.Google Scholar
[40] , Complete caps having less than (q2 + 1)/2 points in common with an elliptic quadric of PG(3, q), q odd, Rend. Mat. Appl. (7) 8 (1988), no. 2, 277–281.Google Scholar
[41] and , A class of complete k-caps in PG(3, q) for q an odd prime, J. Geom. 57 (1996), no. 1–2, 93–105.Google Scholar
[42] , , and , Small complete caps in galois spaces, Ars Combin., to appear.
[43] and , On the number of rational points of generalized Fermat curves over finite fields, Int. J. Number Theory 8 (2012), no. 4, 1087–1097.Google Scholar
[44] , , and , Linear codes with covering radius 2 and other new covering codes, IEEE Trans. Inform. Theory 37 (1991), no. 1, 219–224.Google Scholar
[45] , On small dense sets in Galois planes, Electron. J. Combin. 14 (2007), no. 1, Research Paper 75.Google Scholar
[46] , Small complete caps in Galois affine spaces, J. Algebraic Combin. 25 (2007), no. 2, 149–168.Google Scholar
[47] , Small complete caps in PG(N, q), q even, J. Combin. Des. 15 (2007), no. 5, 420–436.Google Scholar
[48] and , On dense sets related to plane algebraic curves, Ars Combin. 72 (2004), 33–40.Google Scholar
[49] , , , and , Bounds for binary multiple covering codes, Des. Codes Cryptogr. 3 (1993), no. 3, 251–275.Google Scholar
[50] , , , and , Football pools – a game for mathematicians, Amer. Math. Monthly 102 (1995), no. 7, 579–588.Google Scholar
[51] , , , and , Bounds for binary codes that are multiple coverings of the farthest-off points, SIAM J. Discrete Math. 8 (1995), no. 2, 196–207.Google Scholar
[52] and , Upper bounds for football pool problems and mixed covering codes, J. Combin. Theory Ser. A 56 (1991), no. 1, 84–95.Google Scholar
[53] , Finite projective spaces of three dimensions, Oxford Mathematical Monographs, The Clarendon Press Oxford University Press, New York, 1985, Oxford Science Publications.
[54] , Algebraic curves, arcs, and caps over finite fields, Quaderni del Dipartimento di Matematica dell' Università del Salento 5, Dipartimento di Matematica, Università del Salento, Lecce, 1986.
[55] , Projective geometries over finite fields, second ed., Oxford Mathematical Monographs, The Clarendon Press Oxford University Press, New York, 1998.
[56] and , The packing problem in statistics, coding theory and finite projective spaces, J. Statist. Plann. Inference 72 (1998), no. 1–2, 355–380, R. C. Bose Memorial Conference (Fort Collins, CO, 1995).Google Scholar
[57] and , The packing problem in statistics, coding theory and finite projective spaces: update 2001, Finite geometries, Dev. Math., vol. 3, Kluwer Acad. Publ., Dordrecht, 2001, pp. 201–246.
[58] and , General Galois geometries, Oxford Mathematical Monographs, The Clarendon Press Oxford University Press, New York, 1991, Oxford Science Publications.
[59] , On the normality of multiple covering codes, Discrete Math. 125 (1994), no. 1–3, 229–239, 13th British Combinatorial Conference (Guildford, 1991).Google Scholar
[60] and , Generalizations of the covering radius problem in coding theory, Bull. Inst. Combin. Appl. 17 (1996), 39–46.Google Scholar
[61] and , Small complete arcs in projective planes, Combinatorica 23 (2003), no. 2, 311–363.Google Scholar
[62] , , , , and , A note on a geometric construction of large Cayley graphs of given degree and diameter, Stud. Univ. Babeş-Bolyai Math. 54 (2009), no. 3, 77–84.Google Scholar
[63] , New examples of complete k-arcs in PG(2, q), European J. Combin. 4 (1983), no. 4, 329–334.Google Scholar
[64] , Small saturated sets in finite projective planes, Rend. Mat. Appl. (7) 12 (1992), no. 1, 157–164.Google Scholar
[65] and , Finite fields, Encyclopedia of Mathematics and its Applications, vol. 20, Addison-Wesley Publishing Company Advanced Book Program, Reading, MA, 1983, With a foreword by P. M. Cohn.
[66] , Sul problema dei k-archi completi in S2, q (q = pt, p primo dispari), Boll. Un. Mat. Ital. (3) 11 (1956), 178–181.Google Scholar
[67] and , Moore graphs and beyond: A survey of the degree/diameter problem, Electronic Journal of Combinatorics Dynamic Survey DS14 (2005), Online journal, print version is known as Journal of Combinatorics (electronic ISSN 1077–8926, print ISSN 1097–1440).Google Scholar
[68] and , A new table of binary/ternary mixed covering codes, Des. Codes Cryptogr. 11 (1997), no. 2, 151–178.Google Scholar
[69] and , Unpublished manuscript, 1995.
[70] and , Small complete caps in spaces of even characteristic, J. Combin. Theory Ser. A 75 (1996), no. 1, 70–84.Google Scholar
[71] , On complete caps, not ovaloids, in the space PG(3, q) with q odd, Rend. Circ. Mat. Palermo (2) 47 (1998), no. 1, 141–168.Google Scholar
[72] , On codes with given minimum distance and covering radius, Beiträge Algebra Geom. 41 (2000), no. 2, 469–478.Google Scholar
[73] , Correction: “On codes with given minimum distance and covering radius” [Beiträge Algebra Geom. 41 (2000), no. 2, 469–478; MR1801437 (2001i:94082)] by J. Quistorff, Beiträge Algebra Geom. 42 (2001), no. 601–611.Google Scholar
[74] , A note on elliptic curves over finite fields, Math. Comp. 49 (1987), no. 179, 301–304.Google Scholar
[75] , On complete caps and ovaloids in three-dimensional Galois spaces of characteristic two, Acta Arith. 5 (1959), 315–332.Google Scholar
[76] , Ovali e curve s nei piani di Galois di caratteristica due., Atti Accad. Naz. Lincei Rend. Cl. Sci. Fis. Mat. Nat. (8) 32 (1962), 785–790.Google Scholar
[77] , Introduction to Galois geometries, Atti Accad. Naz. Lincei Mem. Cl. Sci. Fis. Mat. Natur. Sez. I (8) 8 (1967), 133–236.Google Scholar
[78] , Proprietà elementari relative ai segmenti ed alle coniche sopra un campo qualsiasi ed una congettura di Seppo Ilkka per il caso dei campi di Galois, Ann. Mat. Pura Appl. (4) 96 (1972), 289–337.Google Scholar
[79] and , Ovali ed altre curve nei piani di Galois di caratteristica due, Acta Arith. 18 (1971), 423–449.Google Scholar
[80] , Algebraic function fields and codes, second ed., Graduate Texts in Mathematics, vol. 254, Springer-Verlag, Berlin, 2009.
[81] , Covering codes, Ph.D. thesis, Eindhoven University of Technology, 1994.
[82] , Complete arcs in finite projective geometries, Ph.D. thesis, Univ. L. Eötvös, Budapest, 1984.
[83] , Small complete arcs in Galois planes, Geom. Dedicata 18 (1985), no. 2, 161–172.Google Scholar
[84] , Note on the order of magnitude of k for complete k-arcs in PG(2,q), Discrete Math. 66 (1987), no. 3, 279–282.Google Scholar
[85] , Arcs in cubic curves and 3-independent subsets of abelian groups, Combinatorics (Eger, 1987), Colloq. Math. Soc. János Bolyai, vol. 52, North-Holland, Amsterdam, 1988, pp. 499–508.
[86] , Complete arcs in galois planes: a survey, Quaderni del Seminario di Geometrie Combinatorie 94, Dipartimento di Matematica “G. Castelnuovo”, Università degli Studi di Roma “La Sapienza”, Roma, January 1989.
[87] , Some applications of algebraic curves in finite geometry and combinatorics, Surveys in combinatorics, 1997 (London), London Math. Soc. Lecture Note Ser., vol. 241, Cambridge Univ. Press, Cambridge, 1997, pp. 197–236.
[88] , Codes, Handbook of combinatorics, Vol. 1 (, , and , eds.), MIT Press, Cambridge, MA, USA, 1995, pp. 773–807.
[89] , A note on elliptic curves over finite fields, Bull. Soc. Math. France 116 (1988), no. 4, 455–458 (1989).Google Scholar
[90] , On the completeness of certain plane arcs. II, European J. Combin. 11 (1990), no. 5, 491–496.Google Scholar
[91] , Private communication, 2011.
[92] , Elliptic curves, second ed., Discrete Mathematics and its Applications (Boca Raton), Chapman & Hall/CRC, Boca Raton, FL, 2008, Number theory and cryptography.
[93] , Abelian varieties over finite fields, Ann. Sci. École Norm. Sup. (4) 2 (1969), 521–560.Google Scholar
- 16
- Cited by