A construction of small complete caps in projective spaces (Q2397251)

Let \(\mathrm{PG}(n,q)\) be the projective space of dimension \(n\) over the finite field \(\mathbb{F}_q\). A cap is a set of points of \(\mathrm{PG}(n,q)\) no three of which are collinear. A cap consisting of \(s\) points is called an \(s\)-cap. An \(s\)-cap is called complete if it is not contained in an \(s+1\)-cap. The trivial lower bound for the size of complete caps in \(\mathrm{PG}(n,q)\) is \[ \sqrt{2}q^{\frac{n-1}{2}}. \] The main result of the nice paper under review is the proof of existence of complete caps of \(\mathrm{PG}(n,q)\), \(n \geq 3\), of size \[ \mathcal{O}(q^{\frac{n-1}{2}} \mathrm{log}^{300} q) \] by probabilistic methods. The authors include an overview of earlier existence results, most of them being (aymptotically) improved by their main result. Using the fact that the columns of a parity check matrix of a quasi-perfect linear code that is both \(1\)-error correcting and \(2\)-error detecting form a complete \(n\)-cap in \(\mathrm{PG}(m-1,q)\), the main result implies an upper bound on the minimal length of such codes, which is described in particular detail in the paper.