In this paper we present and analyze computational results concerning small complete caps in the projective spaces $\mathrm{ PG}(N,q)$ of dimension $N=3$ and $N=4$ over the finite field of order $q$. The results have been obtained using randomized greedy algorithms and the algorithm with fixed order of points (FOP). The computations have been done in relatively wide regions of $q$ values; such wide regions are not considered in literature for $N=3,4$. The new complete caps are the smallest known. Basing on them, we obtained new upper bounds on $t_2(N,q)$, the minimum size of a complete cap in $\mathrm{ PG}(N,q)$, in particular, \begin{ align*} &t_{ 2}(N,q)<\sqrt{ N+2}\cdot q^{ \frac{ N-1}{ 2^{ \vphantom{ H}}}}\sqrt{ \ln q},\quad q\in L_{ N},\quad N=3,4,\\ &t_{ 2}(N,q)<\left(\sqrt{ N+1}+\frac{ 1.3}{ \ln (2q)}\right)q^{ \frac{ N-1}{ 2^{ \vphantom{ H}}}}\sqrt{ \ln q},\quad q\in L_{ N},\quad N=3,4, \end{ align*} where \begin{ align*} &L_{ 3}:=\{ q\le 4673, ~q\ \textrm{ prime}\} \cup \{ 5003,6007,7001,8009\},\\ &L_{ 4}:=\{ q\le 1361, ~q\ \textrm{ prime}\} \cup \{ 1409\}. \end{ align*} Our investigations and results allow to conjecture that these bounds hold for all $q$.
Categories: math.CO