| Introduction | Results | Table | Generator matrices for caps |

Introduction

A cap in PG(k-1,q) is a set of points no three of which are collinear. If we write the n points as columns of a matrix we obtain a (k,n)-matrix such that every set of three columns is linearly independent, hence the generator matrix of a linear orthogonal array of strength 3. This is a check matrix of a linear code with distance 4.

Denote by m2(k-1,q) the maximum cardinality of a cap in PG(k-1,q). In the binary case this is a trivial problem. In fact, choosing all nonzero (k-1)-tuples as columns we obtain a binary (k-1,2k-1-1)-matrix of strength 2, where the number of rows is clearly maximal. The dual is a binary code [2k-1-1,2k-1-k,3]. Addition of a parity-check bit yields [2k-1,2k-1-k,4]. We conclude

m2(k-1,2)=2k-1.

We can assume q >2 in the sequel. For small dimensions there is no problem. Trivially m2(1,q)=2. It is an easy exercise to show that the solution of the homogeneous equation Z2=XY form a set of q+1 points in PG(2,q) no three of which are collinear. This is maximal if q is odd. If q is a power of 2, then each such oval on q+1 points may be embedded in a hyperoval of q+2 points. In other words

m2(2,q)=q+1 if q is odd
m2(2,q)=q+2 if q is even

In projective dimension 3 the situation is just as clear:

m2(3,q)=q2+1 if q >2.

(q2+1)-caps in PG(3,q) are known as ovoids. Just as in dimension 2 they may be constructed as elliptic quadrics. Only two values m2(k,q) were known when q >2,k >3. These are m2(4,3)=20 (the Pellegrino caps) and m2(5,3)=56 (the Hill cap).

Results

 In A family of caps in projective 4-space in characteristic 2 we construct (2q2+q+9)-caps in projective 4-space PG(4,q) in characteristic two for every q>4. For q=2f, f odd, now better caps are known, see below.

In A family of caps in projective 4-space in odd characteristic we construct caps in projective 4-space PG(4,q) in odd characteristic, whose cardinality is O(5/2 q2).

In Recursive constructions for large caps we introduce several recursive constructions for caps in projective spaces. These generalize the known constructions in an essential way and lead to new large caps in many cases. Among our results we mention the construction of {(q+1)(q2+3)}-caps in PG(5,q), of {q4+2q2}-caps in PG(6,q) and of {q2(q2+1)2}-caps in PG(9,q).

In 41 is the largest size of a cap in PG(4,4) we show that m2(4,4)=41.

A family of caps constructed by Ebert, Metsch and T. Szönyi results from projecting a Veronesian or a Grasmannian to a suitable lower-dimensional space. In Caps on classical varieties and their projections we improve on this construction by projecting to a space of much smaller dimension. More precisely we partition PG(3r-1,q) into a (2r-1)-space, an (r-1)-space and qr-1 cyclic caps, each of size (q2r-1)/(q-1). We also decide when one of our caps can be extended by a point from the (2r-1)-space or the (r-1)-space.

In Large caps in small spaces we construct large caps in projective spaces of small dimension (up to 11) defined over fields of order at most 9. The constructions are both theoretical and computer-supported. Some more computer-generated 4-dimensional caps over larger fields are also mentioned. The generator matrices of the computer-generated caps can be found below.

In Extensions of generalized product caps we give some variants of a new construction for caps. As an application of these constructions we obtain a 1216-cap in PG(9,3) a 6464-cap in PG(11,3) and several caps in ternary affine spaces of larger dimension, which lead to better asymptotics than the caps constructed by Calderbank and Fishburn. These asymptotic improvements become visible in dimensions as low as 62, whereas the bound from Calderbank and Fishburn is based on caps in dimension 13,500.
The capsets and admissible sets mentioned in the paper can be found here.

In On complete caps in the projective geometries over F3 II: New improvements, using computer searches, we prove that every 49-cap in PG(5,3) is contained in a 56-cap, and that every 48-cap, having a 20-hyperplane with at most 8-solids, is also contained in a 56-cap. These computer results enable us to present a geometrical proof that m2(6,3) ‹= 147. A computer search for caps in PG(6,3) which uses the computer results of PG(5,3) then lowers this upper bound to m2(6,3) ‹= 136. So now we know that 112 ‹= m2(6,3) ‹= 136.

In New upper bounds for the sizes of caps in PG(N,5) and PG(N,7) we improve the upper bound for PG(N,5) to m2(4,5) ‹= 88. Computer searches in PG(3,7) show that m'2(3,7)=32 and this latter result then improves the upper bound on m2(4,7) to m2(4,7) ‹= 238. We also present the known upper bounds on m2(N,5) and m2(N,7) for N>4.

In Large caps in projective Galois spaces we give an overview on the lower bounds on caps. Also new constructions are presented such as a construction of an 541-cap in PG(8,3) an 195-cap in AG(5,5) an 5069-cap in PG(8,5) and an 130951-cap in PG(11,5). Related topics as quantum caps and a problem in additive number theory are discussed.

Upper bounds, entries for larger n or some other q can be found at the MinT data base of linear codes, orthogonal arrays, OOA and tms-nets. Look for the tables with the code with d=4 or for the OA-tables for linear OA of strength 3. The entries of the MinT-tables are linked to further references.

Denote by Ck(q) the maximum cardinality of a cap in AG(k,q), and ck(q)=Ck(q)/qk. Clearly ck(2)=1. Henceforth we assume q› 2. The values Ck(q) for k‹ 4 are well-known. Aside of these only the value C4(3)=20 was known.

In The classification of the largest caps in AG(5,3) we prove that C5(3)=45 , and such a 45-cap is always obtained from the 56-cap in PG(5,3) by deleting an 11-hyperplane.

In The largest cap in AG(4,4) and its uniqueness we prove that C4(4)=40. Moreover we show the uniqueness and investigate its structure. The 40 cap, viewed as cap in PG(4,4) is complete.

Clearly Ck(q)‹= qCk-1(q), hence ck(q)‹= ck-1(q). Our main results in Bounds on affine caps may be seen as lower bounds on ck-1(q)-ck(q). Meshulam proves an upper bound on the size of subsets of abelian groups of odd order, which do not contain 3-term arithmetic progressions. A more careful analysis of Meshulam's method in the case of caps shows that it can be generalized to cover also the characteristic 2 case. Moreover stronger bounds can be obtained. For q=3 the main theorem also leads to good nonasymptotic bounds, especially C6(3)‹=114.

In Caps with O(3q2) points in affine 4-space in characteristic 2 we prove that for q=2f, f odd, a class of q-ary dual BCH-codes produce (3q2+4)-caps. This is the first family of caps of O(3q2) points in PG(4,q). They are in fact affine. It is proved that our caps are complete in PG(4,q). We determine the weight distribution of the codes generated by the caps, via a close link to the binary Kloosterman codes.

Generator matrices for caps

We write the n points as columns of a (k,n)-matrix. This is a check matrix of a linear code with distance 4. We also give the dual weight distribution of this Code. The last row of the checkmatrix is a word of maximal weight.

| Introduction | Results | Table | Generator matrices for caps |

| home |

Last changed: April 28, 2010.