The geometry of covering codes: small complete caps and saturating sets in Galois spaces
Massimo Giulietti · Cambridge University Press eBooks · 2013
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 F q , 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].