New upper bounds on the smallest size of a complete cap in the space PG(3, q)
Daniele Bartoli, Alexander A. Davydov, Giorgio Faina, Stefano Marcugini, Fernanda Pambianco · 2013
In the projective spaces PG(3, q), more than 370 new small complete caps are obtained for q ≤ 3109, q prime. This implies new upper bounds on the smallest size t2(3, q) of a complete cap in PG(3, q). From the new bounds it follows that the relation t2(3, q) < 6q holds for q ∈ R, where R is a set of 400 prime value in the interval [2, 3109]. The new upper bounds are obtained by finding new small complete caps in PG(3, q) with the help of a computer search using FOP (Fixed Order of Points) algorithm. Let PG(3, q) be the projective 3-dimensional space over the Galois field Fq. An n-cap is a set of n points no three of which are collinear. An n-cap is called complete if it is not contained in an (n + 1)-cap of PG(3, q). In [10] the relationship among the theory of n-caps, coding theory and mathematical statistics is presented. In particular, a complete cap in PG(3, q), points of which are treated as 4-dimensional q-ary columns, defines a parity check matrix of a q-ary linear code with codimension 4, Hamming distance 4, and covering radius 2. Caps in PG(3, q) can be interpreted as linear almost maximum distance separable (AMDS) codes; see [10]. One of the most important problems in the study of projective spaces, which is also of interest in coding theory, is determining the smallest size t2(3, q) of a complete cap in PG(3, q). The trivial lower bound for the size of a complete cap in PG(3, q) is √ 2q. The exact value of t2(3, q) is known only for q ≤ 7; see [6, Table 3] and the references therein. Bartoli, Davydov, Faina, Marcugini, Pambianco 27 If q is even the trivial bound is substantially sharp. In the case q odd, the known constructions yield complete caps of size far from √ 2q; see the survey papers [6, 10] and the more recent works [1, 2, 7]. In 1959 Segre constructed complete caps in PG(3, q) of size 3q+2, consisting of three conics plus two points; see [13]. In 1995, Pambianco and Storme announced the following result, cited in [10, Table 4.8] and proven in [6, Theorem 6]: for q even, we have t2(3, q) ≤ 2q + t2(2, q), where t2(2, q) is the smallest size of a complete arc in PG(2, q). In [6, Theorem 6] this result was proven in a generalized form: for q even, if a complete k-arc in PG(2, q) exists, then there exists a complete 2q +k cap in PG(3, q). For q odd, infinite families of complete caps of size approximately q2/2 and q2/3 [8], see also references in [6], sharing many points with an elliptic quadric, have been obtained by generalizing a classical method by Segre and Lombardo Radice for constructing complete plane caps. In general the problem of determining t2(3, q) remains still an open hard question. According to the survey papers [6, 10], the smallest known complete caps in three-dimensional spaces of arbitrarily high odd order q have size approximately q √ q/2. These constructions were presented by Pellegrino in 1998 [12]: unfortunately, as pointed out in [4], there are some gaps in the proofs and some counterexamples can be easily found also for small q. In [6, Theorem 8, Table 7] it is proven that t2(3, q) ≤ 3q for 2 ≤ q ≤ 17, t2(3, q) < 4q for 2 ≤ q ≤ 89. In [4] the authors show the existence of complete caps in the affine threedimensional space AG(3, q) of size at most 10q for q ≤ 30000, q odd prime, using ideas similar to those contained in [12] and a computer-assisted search. These results imply that t2(3, q) ≤ 11q, q ≤ 30000, q odd. In this work we apply the same techniques that were used in [3] in the search for small complete arcs in PG(2, q) to obtain estimations on the upper bounds on t2(3, q). In the following let t2(3, q) be smallest size of a known complete cap in PG(3, q) and R be a set of 400 prime values in the interval [2, 3109] (see Table 1). Let θup(q) = 1 2 ln(0.01 · q) + 0.605, φup(q) = 1 ln 0.2 · q + 0.706. (1) Our results can be summarized in the following theorem.