A probabilistic construction of small complete caps in projective spaces

Abstract

In this work complete caps in $PG(N,q)$ of size $O(q^{\frac{N-1}{2}}{\log }^{300}q)$ are obtained by probabilistic methods. This gives an upper bound asymptotically very close to the trivial lower bound $\sqrt{2}{q}^{\frac{N-1}{2}}$ and it improves the best known bound in the literature for small complete caps in projective spaces of any dimension. The result obtained in the paper also gives a new upper bound for $l(m,2,q{)}_4$, that is the minimal length $n$ for which there exists an $[n,n-m,4{]}_{q}2$ covering code with given $m$ and $q$.

32 Pages