| Introduction | Results | Table | Generator matrices for caps |
Denote by m_{2}(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,2^{k-1}-1)-matrix of strength 2, where the number of rows is clearly maximal. The dual is a binary code [2^{k-1}-1,2^{k-1}-k,3]. Addition of a parity-check bit yields [2^{k-1},2^{k-1}-k,4]. We conclude
m_{2}(k-1,2)=2^{k-1}.
We can assume q >2 in the sequel. For small dimensions there is no problem. Trivially m_{2}(1,q)=2. It is an easy exercise to show that the solution of the homogeneous equation Z^{2}=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
m_{2}(2,q)=q+1 if q is odd
m_{2}(2,q)=q+2 if q is even
In projective dimension 3 the situation is just as clear:
m_{2}(3,q)=q^{2}+1 if q >2.
(q^{2}+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 m_{2}(k,q) were known when q >2,k >3. These are m_{2}(4,3)=20 (the Pellegrino caps) and m_{2}(5,3)=56 (the Hill cap).
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 q^{2}).
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)(q^{2}+3)}-caps in PG(5,q), of {q^{4}+2q^{2}}-caps in PG(6,q) and of {q^{2}(q^{2}+1)^{2}}-caps in PG(9,q).
In 41 is the largest size of a cap in PG(4,4) we show that m_{2}(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 q^{r}-1 cyclic caps, each of size (q^{2r}-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 F_{3} 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 m_{2}(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 m_{2}(6,3) ‹= 136. So now we know that 112 ‹= m_{2}(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 m_{2}(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 m_{2}(4,7) to m_{2}(4,7) ‹= 238. We also present the known upper bounds on m_{2}(N,5) and m_{2}(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.
k\q | 3 | 4 | 5 | 7 | 8 | 9 | 11 | 13 | 16 | 32 |
2 | 4 | 6 | 6 | 8 | 10 | 10 | 12 | 14 | 18 | 34 |
3 | 10 | 17 | 26 | 50 | 65 | 82 | 122 | 170 | 257 | 1025 |
4 | 20 | 41 | 66 | 132 | 208 | 212 | 316 | 388 | 629 | 3136 |
5 | 56 | 126 | 195 | 434 | 695 | 840 | ||||
6 | 112 | 288 | 675 | 2499 | 4224 | 6723 | ||||
7 | 248 | 756 | 1715 | 6472 | 13520 | 17220 | ||||
8 | 541 | 2110 | 5069 | 21555 | 45174 | 68070 | ||||
9 | 1216 | 5040 | 17124 | 122500 | 270400 | 544644 | ||||
10 | 2744 | 15423 | 43876 | 323318 | 878800 | 1411830 | ||||
11 | 6464 | 34566 | 130951 | 1067080 | 2931457 | 5580100 |
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 C_{k}(q) the maximum cardinality of a cap in AG(k,q), and c_{k}(q)=C_{k}(q)/q^{k}. Clearly c_{k}(2)=1. Henceforth we assume q› 2. The values C_{k}(q) for k‹ 4 are well-known. Aside of these only the value C_{4}(3)=20 was known.
In The classification of the largest caps in AG(5,3) we prove that C_{5}(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 C_{4}(4)=40. Moreover we show the uniqueness and investigate its structure. The 40 cap, viewed as cap in PG(4,4) is complete.
Clearly C_{k}(q)‹= qC_{k-1}(q), hence c_{k}(q)‹= c_{k-1}(q). Our main results in Bounds on affine caps may be seen as lower bounds on c_{k-1}(q)-c_{k}(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 C_{6}(3)‹=114.
In Caps with O(3q^{2}) points in affine 4-space in characteristic 2 we prove that for q=2^{f}, f odd, a class of q-ary dual BCH-codes produce (3q^{2}+4)-caps. This is the first family of caps of O(3q^{2}) 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.
A 40 Cap in AG(4,4).
A 756 Cap in PG(7,4).
A 2110 Cap in PG(8,4).
A 5040Cap in PG(9,4).
A 15423 Cap in PG(10,4).
A 66 Cap in PG(4,5).
A 195 Cap in AG(5,5).
A 5069 Cap in PG(8,5).
A 17124 Cap in PG(9,5).
A complete 32 Cap in PG(3,7).
A 132 Cap in PG(4,7).
A 434 Cap in PG(5,7).
A 6472 Cap in PG(7,7).
A 21555 Cap in PG(8,7).
A 208 Cap in AG(4,8).
A 695 Cap in PG(5,8).
A 210 Cap in AG(4,9).
A 212 Cap in PG(4,9).
A 316 Cap in PG(4,11).
A 388 Cap in PG(4,13).
A 629 Cap in PG(4,16).
A 3136 Cap in AG(4,32).
| Introduction | Results | Table | Generator matrices for caps |
| home |
Last changed: April 28, 2010.